Document Open Access Logo

Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly

Authors Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Huacheng Yu

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.80.pdf
  • Filesize: 0.73 MB
  • 15 pages

Document Identifiers

Author Details

Gillat Kol
  • Princeton University, NJ, USA
Dmitry Paramonov
  • Princeton University, NJ, USA
Raghuvansh R. Saxena
  • Microsoft, Cambridge, MA, USA
Huacheng Yu
  • Princeton University, NJ, USA

Cite As Get BibTex

Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, and Huacheng Yu. Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 80:1-80:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.80

Abstract

We study boolean constraint satisfaction problems (CSPs) Max-CSP^f_n for all predicates f: {0,1}^k → {0,1}. In these problems, given an integer v and a list of constraints over n boolean variables, each obtained by applying f to a sequence of literals, we wish to decide if there is an assignment to the variables that satisfies at least v constraints. We consider these problems in the streaming model, where the algorithm makes a small number of passes over the list of constraints.
Our first and main result is the following complete characterization: For every predicate f, the streaming space complexity of the Max-CSP^f_n problem is Θ̃(n^deg(f)), where deg(f) is the degree of f when viewed as a multilinear polynomial. While the upper bound is obtained by a (very simple) one-pass streaming algorithm, our lower bound shows that a better space complexity is impossible even with constant-pass streaming algorithms. 
Building on our techniques, we are also able to get an optimal Ω(n²) lower bound on the space complexity of constant-pass streaming algorithms for the well studied Max-CUT problem, even though it is not technically a Max-CSP^f_n problem as, e.g., negations of variables and repeated constraints are not allowed.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming models
Keywords
  • Streaming algorithms
  • Constraint Satisfaction Problems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Ami Paz. Smaller cuts, higher lower bounds. ACM Transactions on Algorithms (TALG), 17(4):1-40, 2021. Google Scholar
  2. Sepehr Assadi, Gillat Kol, Raghuvansh R Saxena, and Huacheng Yu. Multi-pass graph streaming lower bounds for cycle counting, max-cut, matching size, and other problems. In Symposium on Foundations of Computer Science (FOCS), 2020. Google Scholar
  3. Sepehr Assadi and Ran Raz. Near-quadratic lower bounds for two-pass graph streaming algorithms. In Symposium on Foundations of Computer Science (FOCS), pages 342-353, 2020. Google Scholar
  4. Sepehr Assadi and N Vishvajeet. Graph streaming lower bounds for parameter estimation and property testing via a streaming xor lemma. In Symposium on Theory of Computing (STOC), pages 612-625. Association for Computing Machinery, 2021. Google Scholar
  5. Per Austrin. Balanced max 2-sat might not be the hardest. In David S. Johnson and Uriel Feige, editors, Symposium on Theory of Computing (STOC), pages 189-197, 2007. Google Scholar
  6. Per Austrin. Towards sharp inapproximability for any 2-csp. SIAM J. Comput., 39(6):2430-2463, 2010. Google Scholar
  7. Nir Bacrach, Keren Censor-Hillel, Michal Dory, Yuval Efron, Dean Leitersdorf, and Ami Paz. Hardness of distributed optimization. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 238-247, 2019. Google Scholar
  8. Aditya Bhaskara, Samira Daruki, and Suresh Venkatasubramanian. Sublinear algorithms for maxcut and correlation clustering. In International Colloquium on Automata, Languages, and Programming (ICALP), 2018. Google Scholar
  9. Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, and Santhoshini Velusamy. Closed-form expressions for the sketching approximability of (some) symmetric boolean csps. arXiv preprint, 2021. URL: http://arxiv.org/abs/2112.06319.
  10. Andrei A. Bulatov. A dichotomy theorem for nonuniform csps. In Symposium on Foundations of Computer Science (FOCS), pages 319-330, 2017. Google Scholar
  11. Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R Saxena, Zhao Song, and Huacheng Yu. Almost optimal super-constant-pass streaming lower bounds for reachability. In Symposium on Theory of Computing (STOC), pages 570-583, 2021. Google Scholar
  12. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy. Linear space streaming lower bounds for approximating csps. In Symposium on Theory of Computing (STOC), pages 275-288. ACM, 2022. Google Scholar
  13. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. Approximability of all finite csps with linear sketches. In Symposium on Foundations of Computer Science (FOCS), pages 1197-1208. IEEE, 2021. Google Scholar
  14. Chi-Ning Chou, Alexander Golovnev, and Santhoshini Velusamy. Optimal streaming approximations for all boolean max-2csps and max-ksat. In Symposium on Foundations of Computer Science (FOCS), pages 330-341. IEEE, 2020. Google Scholar
  15. Nadia Creignou, Sanjeev Khanna, and Madhu Sudan. Complexity classifications of Boolean constraint satisfaction problems. SIAM, 2001. Google Scholar
  16. Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1):57-104, 1998. Google Scholar
  17. Venkatesan Guruswami and Krzysztof Onak. Superlinear lower bounds for multipass graph processing. Algorithmica, 76(3):654-683, 2016. Google Scholar
  18. Venkatesan Guruswami and Runzhou Tao. Streaming hardness of unique games. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), 2019. Google Scholar
  19. Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. Journal of the ACM (JACM), 53(3):307-323, 2006. Google Scholar
  20. Daniel M Kane, Jelani Nelson, and David P Woodruff. On the exact space complexity of sketching and streaming small norms. In Symposium on Discrete Algorithms (SODA), pages 1161-1178. SIAM, 2010. Google Scholar
  21. Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Streaming lower bounds for approximating MAX-CUT. In Symposium on Discrete Algorithms (SODA), pages 1263-1282, 2015. Google Scholar
  22. Michael Kapralov, Sanjeev Khanna, Madhu Sudan, and Ameya Velingker. (1+ ω (1))-approximation to max-cut requires linear space. In Symposium on Discrete Algorithms (SODA), pages 1703-1722, 2017. Google Scholar
  23. Michael Kapralov and Dmitry Krachun. An optimal space lower bound for approximating max-cut. In Symposium on Theory of Computing (STOC), pages 277-288, 2019. Google Scholar
  24. Subhash Khot. On the unique games conjecture (invited survey). In Conference on Computational (CCC), pages 99-121. IEEE Computer Society, 2010. Google Scholar
  25. Dmitry Kogan and Robert Krauthgamer. Sketching cuts in graphs and hypergraphs. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 367-376, 2015. Google Scholar
  26. W. Mantel. Vraagstuk XXVIII. Wiskundige Opgaven, 10:60-61, 1907. Google Scholar
  27. Elchanan Mossel. Gaussian bounds for noise correlation of functions. In Geometric and Functional Analysis, volume 19(6), pages 1713-1756, 2010. Google Scholar
  28. Christos H Papadimitriou and Michael Sipser. Communication complexity. In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 196-200, 1982. Google Scholar
  29. Prasad Raghavendra. Optimal algorithms and inapproximability results for every csp? In Symposium on Theory of Computing (STOC), pages 245-254, 2008. Google Scholar
  30. Alexander A Razborov. On the distributional complexity of disjointness. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 249-253. Springer, 1990. Google Scholar
  31. Thomas J. Schaefer. The complexity of satisfiability problems. In Symposium on Theory of Computing (STOC), pages 216-226, 1978. Google Scholar
  32. Noah Singer, Madhu Sudan, and Santhoshini Velusamy. Streaming approximation resistance of every ordering CSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), volume 207 of LIPIcs, pages 17:1-17:19, 2021. Google Scholar
  33. Madhu Sudan. Streaming and sketching complexity of csps: A survey (invited talk). In International Colloquium on Automata, Languages, and Programming (ICALP), volume 229 of LIPIcs, pages 5:1-5:20, 2022. Google Scholar
  34. Paul Turán. On an external problem in graph theory. Mat. Fiz. Lapok, 48:436-452, 1941. Google Scholar
  35. Mariano Zelke. Intractability of min- and max-cut in streaming graphs. Inf. Process. Lett., 111(3):145-150, 2011. Google Scholar
  36. Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. Journal of the ACM (JACM), 67(5):30:1-30:78, 2020. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact