Approximating CSPs in the streaming setting


Santhoshini Velusamy March 03, 2023.


Constraint satisfaction problems (CSPs) are ubiquitous in computer science and encompass optimization problems such as Max-CUT, Max-DICUT, Max-k-SAT, Max-q-Coloring, Unique Games, etc. Until recently, Max-CUT and a few Max-2CSPs were the only CSPs studied in the streaming setting. The main focus of my talk will be the following dichotomy theorem: For every CSP, there is a constant ⍺ such that the CSP is ⍺-approximable in polylogarithmic space by a linear sketching algorithm and any sketching algorithm that beats ⍺-approximation requires polynomial space. I will also briefly discuss latest works which address some of the gaps in the above dichotomy theorem, and conclude with some interesting open problems in this area.

Based on joint works with Chi-Ning Chou, Alexander Golovnev, Raghuvansh Saxena, Madhu Sudan, Noah Singer, and Ameya Velingker that appeared in STOC, FOCS, SODA, and APPROX.

Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits
  • Foundations of Lattice-based Cryptography
  • Why we couldn't prove SETH hardness of CVP for even norms, Subset-SUM, and Many more!
  • Interior Point Methods for Nearly Linear Time Algorithms
  • Collaborative Top Distribution Identifications with Limited Interaction