Document Open Access Logo

Lifting with Sunflowers

Authors Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, Jiapeng Zhang

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.104.pdf
  • Filesize: 0.94 MB
  • 24 pages

Document Identifiers

Author Details

Shachar Lovett
  • Department of Computer Science, University of California San Diego, CA, USA
Raghu Meka
  • Department of Computer Science, University of California Los Angeles, CA, USA
Ian Mertz
  • Department of Computer Science, University of Toronto, Canada
Toniann Pitassi
  • Department of Computer Science, University of Toronto, Canada
  • Department of Mathematics, Institute for Advanced Study, Princeton, NJ, USA
Jiapeng Zhang
  • Department of Computer Science, University of Southern California, Los Angeles, CA, USA

Funding

  • Lovett, Shachar: Research supported by NSF Award DMS-1953928.
  • Mertz, Ian: Research supported by NSERC.
  • Pitassi, Toniann: Research supported by NSF Award CCF-1900460 and NSERC.

Acknowledgements

The authors thank Paul Beame for comments.

Cite AsGet BibTex

Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, and Jiapeng Zhang. Lifting with Sunflowers. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 104:1-104:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.104

Abstract

Query-to-communication lifting theorems translate lower bounds on query complexity to lower bounds for the corresponding communication model. In this paper, we give a simplified proof of deterministic lifting (in both the tree-like and dag-like settings). Our proof uses elementary counting together with a novel connection to the sunflower lemma. In addition to a simplified proof, our approach opens up a new avenue of attack towards proving lifting theorems with improved gadget size - one of the main challenges in the area. Focusing on one of the most widely used gadgets - the index gadget - existing lifting techniques are known to require at least a quadratic gadget size. Our new approach combined with robust sunflower lemmas allows us to reduce the gadget size to near linear. We conjecture that it can be further improved to polylogarithmic, similar to the known bounds for the corresponding robust sunflower lemmas.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
  • Theory of computation → Communication complexity
  • Theory of computation → Complexity theory and logic
  • Theory of computation → Circuit complexity
  • Theory of computation → Proof complexity
Keywords
  • Lifting theorems
  • communication complexity
  • combinatorics
  • sunflowers

Metrics

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

Related Versions

References

  1. Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang. Improved bounds for the sunflower lemma. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 624-630. ACM, 2020. Google Scholar
  2. Tolson Bell, Suchakree Chueluecha, and Lutz Warnke. Note on sunflowers. Discrete Mathematics, 344(7):112367, 2021. Google Scholar
  3. Bruno Pasqualotto Cavalar, Mrinal Kumar, and Benjamin Rossman. Monotone circuit lower bounds from robust sunflowers. In LATIN 2020: Theoretical Informatics - 14th Latin American Symposium, São Paulo, Brazil, January 5-8, 2021, Proceedings, volume 12118 of Lecture Notes in Computer Science, pages 311-322. Springer, 2020. Google Scholar
  4. Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer. Approximate constraint satisfaction requires large LP relaxations. J. ACM, 63(4):34:1-34:22, 2016. Google Scholar
  5. Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann Pitassi. Query-to-communication lifting using low-discrepancy gadgets. Technical Report TR19-103, Electronic Colloquium on Computational Complexity (ECCC), 2019. URL: https://eccc.weizmann.ac.il/report/2019/103/.
  6. Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay. Simulation theorems via pseudo-random properties. Comput. Complex., 28(4):617-659, 2019. Google Scholar
  7. Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, and Marc Vinyals. Lifting with simple gadgets and applications to circuit and proof complexity. Technical Report TR19-186, Electronic Colloquium on Computational Complexity (ECCC), 2019. URL: https://eccc.weizmann.ac.il/report/2019/186/.
  8. Susanna de Rezende, Jakob Nordström, and Marc Vinyals. How limited interaction hinders real communication (and what it means for proof and circuit complexity). In Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS), pages 295-304. IEEE, 2016. Google Scholar
  9. Paul Erdös and R. Rado. Intersection theorems for systems of sets. Journal of the London Mathematical Society, 35(1):85-90, 1960. Google Scholar
  10. Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Jinyoung Park. Thresholds versus fractional expectation-thresholds. Annals of Mathematics, 194(2):475-495, 2021. Google Scholar
  11. Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov. Monotone circuit lower bounds from resolution. In Proceedings of the 50th Symposium on Theory of Computing (STOC), pages 902-911. ACM, 2018. Google Scholar
  12. Mika Göös. Lower bounds for clique vs. independent set. In Proceedings of the 56th Symposium on Foundations of Computer Science (FOCS), pages 1066-1076. IEEE Computer Society, 2015. Google Scholar
  13. Mika Göös, Rahul Jain, and Thomas Watson. Extension complexity of independent set polytopes. SIAM J. Comput., 47(1):241-269, 2018. Google Scholar
  14. Mika Göös, Sajin Koroth, Ian Mertz, and Toniann Pitassi. Automating cutting planes is NP-hard. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 68-77. ACM, 2020. Google Scholar
  15. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. SIAM J. Comput., 45(5):1835-1869, 2016. Google Scholar
  16. Mika Göös and Toniann Pitassi. Communication lower bounds via critical block sensitivity. SIAM Journal on Computing, 47(5):1778-1806, 2018. Google Scholar
  17. Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. In Proceedings of the 56th Symposium on Foundations of Computer Science (FOCS), pages 1077-1088. IEEE, 2015. Google Scholar
  18. Mika Göös, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for BPP. In Proceedings of the 58th Symposium on Foundations of Computer Science (FOCS), pages 132-143, 2017. Google Scholar
  19. Danny Harnik and Ran Raz. Higher lower bounds on monotone size. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 378-387. ACM, 2000. Google Scholar
  20. Trinh Huynh and Jakob Nordström. On the virtue of succinct proofs: Amplifying communication complexity hardness to time-space trade-offs in proof complexity. In Proceedings of the 44th Symposium on Theory of Computing (STOC), pages 233-248. ACM, 2012. Google Scholar
  21. Stasys Jukna. Boolean function complexity: advances and frontiers, volume 27. Springer Science & Business Media, 2012. Google Scholar
  22. Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra. Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of csps. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 590-603. ACM, 2017. Google Scholar
  23. Jan Krajíček. Interpolation by a game. Mathematical Logic Quarterly, 44:450-458, 1998. Google Scholar
  24. Eyal Kushilevitz. Communication complexity. In Advances in Computers, volume 44, pages 331-360. Elsevier, 1997. Google Scholar
  25. James R. Lee, Prasad Raghavendra, and David Steurer. Lower bounds on the size of semidefinite programming relaxations. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 567-576. ACM, 2015. Google Scholar
  26. Xin Li, Shachar Lovett, and Jiapeng Zhang. Sunflowers and quasi-sunflowers from randomness extractors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA, volume 116 of LIPIcs, pages 51:1-51:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  27. Toniann Pitassi and Robert Robere. Strongly exponential lower bounds for monotone computation. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1246-1255. ACM, 2017. Google Scholar
  28. Toniann Pitassi and Robert Robere. Lifting nullstellensatz to monotone span programs over any field. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1207-1219. ACM, 2018. Google Scholar
  29. Anup Rao. Coding for sunflowers. Discrete Analysis, 2:8, 2020. Google Scholar
  30. Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. Combinatorica, 19(3):403-435, 1999. Google Scholar
  31. Robert Robere. Unified lower bounds for monotone computation. Ph.D Thesis, 2018. Google Scholar
  32. Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen A. Cook. Exponential lower bounds for monotone span programs. In Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS), pages 406-415. IEEE Computer Society, 2016. Google Scholar
  33. Benjamin Rossman. The monotone complexity of k-clique on random graphs. Proceedings of the 51st Symposium on Foundations of Computer Science (FOCS), pages 193-201, 2010. Google Scholar
  34. Alexander A. Sherstov. The pattern matrix method. SIAM J. Comput., 40(6):1969-2000, 2011. Google Scholar
  35. Alexander A Sherstov. Communication lower bounds using directional derivatives. Journal of the ACM (JACM), 61(6):1-71, 2014. Google Scholar
  36. Xiaodi Wu, Penghui Yao, and Henry S. Yuen. Raz-McKenzie simulation with the inner product gadget. Electronic Colloquium on Computational Complexity (ECCC), 24:10, 2017. 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