SIGACT News Open Problem Columns edited by William Gasarch

Vol 54, 2023

No. 1 The Complexity of the Shortest Value Problem by H.Bennett

Vol 53, 2022

No. 1 On the smallest open Diophantine equations by Grechuk

No. 2 Comp of chi(G) Restriced to Bdd Cr-Num or Genus-Gasarch-Hayes-Ostuni-Park

No. 3 An Intriguing Sequence by Gasarch, Kaplitz, and Metz

No. 4 Open Problems By or Insired by Juris Hartmanis by many people

Vol 52, 2021

No. 1 Generalizing the 3SUM Problem by Gasarch and Metz

No. 2 Hilbert's 10th Problem by Gasarch,Long Version Longer

No. 3 Worlds to Die For: Open Oracle Questionss for the 21st Century by Fortnow

No. 4 27 open problems in Kolm. Comp. by Romashchenko, Shen, Zimand

Vol 51, 2020

No. 1 The testtakers–Testmakers Dilemma by Bajaj and Gasarch

No. 2 A Known Problem in Ramsey Theory: Ramsey Multiplicity by Gasarch

No. 3 The Busy Beaver Frontier by Aaronson

No. 4 When Ramsey Theory Fails, Settle for More Colors by Dobrinen and Gasarch

Vol 50, 2019

No. 1 My Answers to My P vs NP Poll by Gasarch

No. 2 The Muffin Problem by Gasarch

No. 3 Sliding Scale Conjectures in PCP by Moshkovitz

No. 4 A Number-Sequence Problem Inspired by an O.Roeder Col, by Gasarch

Vol 49, 2018

No. 1 Different ways to prove a language not regular by Frishberg and Gasarch

No. 2 P vs NP: Invitation to a Poll by Gasarch

No. 3 Vol Fixed-Param Extrapolation and Aperiodic Order by Fenner, Green, Homer

No. 4 Some Open Problems in Fine-Grained Complexity by V.W.Williams

Vol 48, 2017

No. 1 Selected challenges in computational lower bounds By Viola

No. 2 Wanted: A Communication Complexity Proof of lower bounds on PARITY by Gasarch

No. 3 Open Problems in Computational Topology by Fasy and Wang

No. 4 Some Open Problems in Algorithmic Fractal Geometry by Neil Lutz

Vol 47, 2016.

No. 3 Grid Coloring and The Complexity of Grid Colorings by Gasarch

No. 4 Some Open Problems Regarding Lower Bounds For NP By R.Williams

Future (in progress)

Seeking Better Bound on the Large Canonical Ramsey No. by Gasarch and Metz

Wanted: Easier Proof of Lower Bounds on Approximating Set Cover

description of languages by Gasarch