next up previous
Next: About this document ...

I am the SIGACT NEWS open problems column editor starting in 2016. Below are all of the columns that have been published so far.

  1. Vol 47, No 3, 2016. Open Problems About Grid Coloring and The Complexity of Grid Colorings. By William Gasarch. compgrid.pdf
  2. Vol 47, No 4. 2016 Some Open Problems Regarding Lower Bounds For NP. By Ryan Williams. lbfornp.pdf
  3. Vol 48, No 1, 2017 Selected challenges in computational lower bounds. By Emanuele Viola map-column.pdf
  4. Vol 48, No 2, 2017 Wanted: A Communication Complexity Proof of lower bounds on PARITY. By William Gasarch, parity.pdf
  5. Vol 48, No 3, 2017 Open Problems in Computational Topology. By Brittany Terese Fasy and Bei Wang with contributions from members of the WinCompTop community. tda.pdf

  6. Vol 48, No 4, 2017 Some Open Problems in Algorithmic Fractal Geometry. By Neil Lutz fracgeom.pdf

  7. Vol 49, No 1, 2018 Different ways to prove a language not regular. By Daniel Frishberg and William Gasarch regular.pdf

  8. Vol 49, No 2, 2018 P vs NP: Invitation to a Poll. By William Gasarch pnp.pdf

  9. Vol 49, No 3, 2018 Fixed-Parameter Extrapolation and Aperiodic Order: Open Problems By Stephen Fenner, Fred Green, Steven Homer convexfgh.pdf

  10. Vol 49, No 4, 2018 Some Open Problems in Fine-Grained Complexity by Virginia Vassilevska Williams finegrain.pdf

  11. Vol 50, No 1, 2019 My Answers to My P vs NP Poll. by William Gasarch pnpme.pdf

  12. Vol 50, No 2, 2019 They Muffin Problem. by William Gasarch mufsigopen.pdf This was really a pointer to a much longer article: muffinarticleforsigact.pdf

  13. Vol 50, No 3, 2019 Sliding Scale Conjectures in PCP by Dana Moshkovitz sliding.pdf

  14. Vol 50, No 4, 2019 A Number-Sequence Problem Inspired by an Oliver Roeder Column by William Gasarch. nate.pdf

next up previous
Next: About this document ...
Bill Gasarch 2019-09-07