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




next up previous
Next: About this document ...
Bill Gasarch 2018-09-21