Document Open Access Logo

Streaming Hardness of Unique Games

Authors Venkatesan Guruswami , Runzhou Tao

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.5.pdf
  • Filesize: 476 kB
  • 12 pages

Document Identifiers

Author Details

Venkatesan Guruswami
  • Computer Science Department, Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PA, USA, 15213
Runzhou Tao
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China 100084

Funding

  • Guruswami, Venkatesan: Research supported in part by NSF grants CCF-1422045 and CCF-1526092.
  • Tao, Runzhou: Most of this work was done during a visit by the author to Carnegie Mellon University.

Cite AsGet BibTex

Venkatesan Guruswami and Runzhou Tao. Streaming Hardness of Unique Games. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.5

Abstract

We study the problem of approximating the value of a Unique Game instance in the streaming model. A simple count of the number of constraints divided by p, the alphabet size of the Unique Game, gives a trivial p-approximation that can be computed in O(log n) space. Meanwhile, with high probability, a sample of O~(n) constraints suffices to estimate the optimal value to (1+epsilon) accuracy. We prove that any single-pass streaming algorithm that achieves a (p-epsilon)-approximation requires Omega_epsilon(sqrt n) space. Our proof is via a reduction from lower bounds for a communication problem that is a p-ary variant of the Boolean Hidden Matching problem studied in the literature. Given the utility of Unique Games as a starting point for reduction to other optimization problems, our strong hardness for approximating Unique Games could lead to downstream hardness results for streaming approximability for other CSP-like problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
  • Theory of computation → Streaming models
Keywords
  • Communication complexity
  • CSP
  • Fourier Analysis
  • Lower bounds
  • Streaming algorithms
  • Unique Games

Metrics

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

References

  1. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Near-optimal algorithms for unique games. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 205-214, 2006. Google Scholar
  2. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Towards a proof of the 2-to-1 games conjecture? In Proceedings of the 50th Annual ACM Symposium on Theory of Computing, pages 376-389, 2018. Google Scholar
  3. Uriel Feige and Daniel Reichman. On Systems of Linear Equations with Two Variables per Equation. In Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques (APPROX, RANDOM), pages 117-127, 2004. Google Scholar
  4. Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald De Wolf. Exponential separations for one-way quantum communication complexity, with applications to cryptography. In Proceedings of the 39th annual ACM symposium on Theory of computing, pages 516-525. ACM, 2007. Google Scholar
  5. Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, and Moses Charikar. Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant. SIAM Journal on Computing, 40(3):878-914, 2011. Google Scholar
  6. Venkatesan Guruswami, Rajsekar Manokaran, and Prasad Raghavendra. Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pages 573-582, 2008. Google Scholar
  7. Venkatesan Guruswami, Ameya Velingker, and Santhoshini Velusamy. Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph. In 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 8:1-8:19, 2017. Google Scholar
  8. Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on Boolean functions. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 68-80, 1988. Google Scholar
  9. Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Streaming lower bounds for approximating MAX-CUT. In Proceedings of the 26 annual ACM-SIAM symposium on Discrete Algorithms, pages 1263-1282. Society for Industrial and Applied Mathematics, 2015. Google Scholar
  10. Michael Kapralov and Dmitry Krachun. An Optimal Space Lower Bound for Approximating MAX-CUT. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 277-288, 2019. Google Scholar
  11. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, pages 767-775, 2002. Google Scholar
  12. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? SIAM Journal on Computing, 37(1):319-357, 2007. Google Scholar
  13. Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014. Google Scholar
  14. Alessandro Panconesi and Aravind Srinivasan. Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds. SIAM Journal on Computing, 26(2):350-368, 1997. Google Scholar
  15. Khot Subhash, Dor Minzer, and Muli Safra. Pseudorandom sets in grassmann graph have near-perfect expansion. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 592-601. IEEE, 2018. Google Scholar
  16. Elad Verbin and Wei Yu. The streaming complexity of cycle counting, sorting by reversals, and other problems. In Proceedings of the 26 annual ACM-SIAM symposium on Discrete Algorithms, pages 11-25, 2011. 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 Imprint Privacy Contact