Document Open Access Logo

Lifting Theorems for Equality

Authors Bruno Loff , Sagnik Mukhopadhyay

PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.50.pdf
  • Filesize: 0.6 MB
  • 19 pages

Document Identifiers

Author Details

Bruno Loff
  • INESC-TEC and University of Porto, Porto, Portugal
Sagnik Mukhopadhyay
  • Computer Science Institute of Charles University, Prague, Czech Republic

Funding

  • Loff, Bruno: The research leading to these results has received funding from the Foundation for Science and Technology (FCT), Portugal, grant number SFRH/BPD/116010/2016. This work is partially funded by the ERDF through the COMPETE 2020 Programme within project POCI-01-0145-FEDER-006961, and by National Funds through the FCT as part of project UID/EEA/50014/2013.
  • Mukhopadhyay, Sagnik: Most of the work is done while the author was a post-doctoral researcher at KTH Royal Institute of Technology, Stockholm. The author is now supported by European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013)/ERC Grant Agreement n. 616787.

Acknowledgements

We are thankful to Suhail Sherif, Mark Vinyals, and Susanna de Rezende for many helpful discussions, and Or Meir for pointing out an important bug in an earlier draft of the paper. We also thank the anonymous referees whose insights improved the paper by a substantial amount. We owe an extraordinary debt to Arkadev Chattopadhyay, an outstanding companion of many tea-break conversations on the subject of this paper.

Cite As Get BibTex

Bruno Loff and Sagnik Mukhopadhyay. Lifting Theorems for Equality. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 50:1-50:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.STACS.2019.50

Abstract

We show a deterministic simulation (or lifting) theorem for composed problems f o Eq_n where the inner function (the gadget) is Equality on n bits. When f is a total function on p bits, it is easy to show via a rank argument that the communication complexity of f o Eq_n is Omega(deg(f) * n). However, there is a surprising counter-example of a partial function f on p bits, such that any completion f' of f has deg(f') = Omega(p), and yet f o Eq_n has communication complexity O(n). Nonetheless, we are able to show that the communication complexity of f o Eq_n is at least D(f) * n for a complexity measure D(f) which is closely related to the AND-query complexity of f and is lower-bounded by the logarithm of the leaf complexity of f. As a corollary, we also obtain lifting theorems for the set-disjointness gadget, and a lifting theorem in the context of parity decision-trees, for the NOR gadget.
As an application, we prove a tight lower-bound for the deterministic communication complexity of the communication problem, where Alice and Bob are each given p-many n-bit strings, with the promise that either all of the strings are distinct, or all-but-one of the strings are distinct, and they wish to know which is the case. We show that the complexity of this problem is Theta(p * n).

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Theory of computation → Communication complexity
  • Theory of computation → Oracles and decision trees
Keywords
  • Communication complexity
  • Query complexity
  • Simulation theorem
  • Equality function

Metrics

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

Related Versions

References

  1. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. SIAM Journal on Computing, 42(3):1327-1363, 2013. Google Scholar
  2. Paul Beame, Toniann Pitassi, Nathan Segerlind, and Avi Wigderson. A direct sum theorem for corruption and the multiparty NOF communication complexity of set disjointness. In Proceedings of the 20th CCC, pages 52-66, 2005. Google Scholar
  3. Anna Bernasconi and Bruno Codenotti. Spectral Analysis of Boolean Functions as a Graph Eigenvalue Problem. IEEE Transactions on Computers, 48(3):345-351, 1999. Google Scholar
  4. Mark Braverman and Anup Rao. Information Equals Amortized Communication. IEEE Transactions on Information Theory, 60(10):6058-6069, 2014. Google Scholar
  5. Mark Braverman, Anup Rao, Omri Weinstein, and Amir Yehudayoff. Direct Product via Round-Preserving Compression. In Proceedings of the 40th ICALP, pages 232-243, 2013. Google Scholar
  6. Mark Braverman, Anup Rao, Omri Weinstein, and Amir Yehudayoff. Direct Products in Communication Complexity. In Proceedings of the 54th FOCS, pages 746-755, 2013. Google Scholar
  7. Joshua Brody, Harry Buhrman, Michal Kouckỳ, Bruno Loff, Florian Speelman, and Nikolay Vereshchagin. Towards a reverse Newman’s theorem in interactive information complexity. In Proceedings of the 28th CCC, pages 24-33, 2013. Google Scholar
  8. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288(1):21-43, 2002. Google Scholar
  9. Amit Chakrabarti and Oded Regev. An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. SIAM Journal on Computing, 41(5):1299-1317, 2012. Google Scholar
  10. Arkadev Chattopadhyay. Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits. In Proceedings of the 48th FOCS, pages 449-458, 2007. Google Scholar
  11. Arkadev Chattopadhyay and Anil Ada. Multiparty Communication Complexity of Disjointness. Technical Report TR08-002, ECCC, 2008. Google Scholar
  12. Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay. Simulation Theorems via Pseudorandom Properties. CoRR, abs/1704.06807, 2017. Google Scholar
  13. Arkadev Chattopadhyay, Michal Kouckỳ, Bruno Loff, and Sagnik Mukhopadhyay. Simulation beats richness: new data-structure lower bounds. In Proceedings of the 50th STOC, pages 1013-1020. ACM, 2018. Google Scholar
  14. Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals. How Limited Interaction Hinders Real Communication. In Proceedings of the 56th FOCS, 2016. Google Scholar
  15. Irit Dinur and Or Meir. Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. Computational Complexity, 27(3):375-462, 2018. Google Scholar
  16. Andrew Drucker. Improved direct product theorems for randomized query complexity. Computational Complexity, 21(2):197-244, 2012. Google Scholar
  17. Jeff Edmonds, Russell Impagliazzo, Steven Rudich, and Jirí Sgall. Communication complexity towards lower bounds on circuit depth. Computational Complexity, 10(3):210-246, 2001. Google Scholar
  18. Tomás Feder, Eyal Kushilevitz, Moni Naor, and Noam Nisan. Amortized Communication Complexity. SIAM Journal on Computing, 24(4):736-750, 1995. Google Scholar
  19. Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov. Monotone circuit lower bounds from resolution. In Proceedings of the 50th STOC, pages 902-911, 2018. Google Scholar
  20. Dmitry Gavinsky, Troy Lee, and Miklos Santha. On the randomised query complexity of composition. CoRR, abs/1801.02226, 2018. Google Scholar
  21. Dmitry Gavinsky, Or Meir, Omri Weinstein, and Avi Wigderson. Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture. In Proceedings of the 46th STOC, pages 213-222, 2014. Google Scholar
  22. Mika Göös, Rahul Jain, and Thomas Watson. Extension complexity of independent set polytopes. SIAM Journal on Computing, 47(1):241-269, 2018. Google Scholar
  23. Mika Göös, TS Jayram, Toniann Pitassi, and Thomas Watson. Randomized Communication versus Partition Number. In Proceedings of the 44th ICALP, 2017. Google Scholar
  24. Mika Göös, Pritish Kamath, Toniann Pitassi, and Thomas Watson. Query-to-communication Lifting for 𝖯^NP. In Proceedings of the 32nd CCC, 2017. Google Scholar
  25. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. In Proceedings of the 47th STOC, pages 257-266. ACM, 2015. Google Scholar
  26. Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. In Proceedings of the 56th FOCS, 2015. Google Scholar
  27. Mika Göös, Toniann Pitassi, and Thomas Watson. The landscape of communication complexity classes. Computational Complexity, pages 1-60, 2015. Google Scholar
  28. Michelangelo Grigni and Michael Sipser. Monotone Separation of Logspace from NC. In Proceedings of the 6th Annual Structure in Complexity Theory Conference, pages 294-298, 1991. Google Scholar
  29. Prahladh Harsha, Rahul Jain, David McAllester, and Jaikumar Radhakrishnan. The communication complexity of correlation. In Proceedings of the 22nd CCC, pages 10-23, 2007. Google Scholar
  30. Johan Håstad and Avi Wigderson. Composition of the Universal Relation. In Proceedings of the DIMACS Workshop, pages 119-134, 1990. Google Scholar
  31. Hamed Hatami, Kaave Hosseini, and Shachar Lovett. Structure of Protocols for XOR Functions. SIAM Journal on Computing, 47(1):208-217, 2018. Google Scholar
  32. Rahul Jain. New strong direct product results in communication complexity. Journal of the ACM, 62(3):20, 2015. Google Scholar
  33. Rahul Jain, Hartmut Klauck, and Ashwin Nayak. Direct product theorems for classical communication complexity via subdistribution bounds. In Proceedings of the 40th STOC, pages 599-608, 2008. Google Scholar
  34. Rahul Jain, Attila Pereszlényi, and Penghui Yao. A direct product theorem for the two-party bounded-round public-coin communication complexity. In Proceedings of the 53rd FOCS, pages 167-176, 2012. Google Scholar
  35. Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. A direct sum theorem in communication complexity via message compression. In Proceedings of the 20th ICALP, pages 300-315, 2003. Google Scholar
  36. Rahul Jain and Penghui Yao. A strong direct product theorem in terms of the smooth rectangle bound. CoRR, abs/1209.0263, 2012. Google Scholar
  37. Stasys Jukna. Boolean Function Complexity - Advances and Frontiers. Springer, 2012. Google Scholar
  38. Mauricio Karchmer, Eyal Kushilevitz, and Noam Nisan. Fractional Covers and Communication Complexity. SIAM Journal on Discrete Mathematics, 8(1):76-92, 1995. Google Scholar
  39. Mauricio Karchmer, Ran Raz, and Avi Wigderson. Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity. Computational Complexity, 5(3/4):191-204, 1995. Google Scholar
  40. Mauricio Karchmer and Avi Wigderson. Monotone Circuits for Connectivity Require Super-Logarithmic Depth. SIAM Journal on Discrete Mathematics, 3(2):255-265, 1990. Google Scholar
  41. Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, and David Xiao. Lower bounds on information complexity via zero-communication protocols and applications. SIAM Journal on Computing, 44(5):1550-1572, 2015. Google Scholar
  42. 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 STOC, pages 590-603. ACM, 2017. Google Scholar
  43. Alexander Kozachinskiy. Comment on Meir’s paper The Direct Sum of Universal Relations. Available at the address URL: https://eccc.weizmann.ac.il/report/2017/128/comment/1/download/.
  44. Alexander Kozachinskiy. From Expanders to Hitting Distributions and Simulation Theorems. In Proceedings of the 43rd MFCS, pages 4:1-4:15, 2018. Google Scholar
  45. Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997. Google Scholar
  46. James Lee, Raghu Meka, and Thomas Vidick. (Less) heavy lifting: from conic junta degree to non-negative rank. Presented in the workshop Hardness Escalation in Communication Complexity and Query Complexity, FOCS 2017. Google Scholar
  47. Troy Lee, Adi Shraibman, and Robert Spalek. A Direct Product Theorem for Discrepancy. In Proceedings of the 23rd CCC, pages 71-80, 2008. Google Scholar
  48. Bruno Loff and Sagnik Mukhopadhyay. Lifting Theorems for Equality. Electronic Colloquium on Computational Complexity (ECCC), 25:175, 2018. Google Scholar
  49. László Lovász. On the ratio of optimal integral and fractional covers. Discrete mathematics, 13(4):383-390, 1975. Google Scholar
  50. Or Meir. The direct sum of universal relations. Information Processing Letters, 136:105-111, 2018. Google Scholar
  51. Gatis Midrijanis. Exact quantum query complexity for total Boolean functions. CoRR, abs/quant-ph/0403168, 2004. Google Scholar
  52. Alon Orlitsky. Worst-case interactive communication. I. Two messages are almost optimal. IEEE Transactions on Information Theory, 36(5):1111-1126, 1990. Google Scholar
  53. Denis Pankratov. Direct sum questions in classical communication complexity. Master’s thesis, University of Chicago, 2012. Google Scholar
  54. Toniann Pitassi and Robert Robere. Lifting nullstellensatz to monotone span programs over any field. In Proceedings of the 50th STOC, pages 1207-1219, 2018. Google Scholar
  55. Anup Rao and Amir Yehudayoff. Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness. In Proceedings of the 30th CCC, pages 88-101, 2015. Google Scholar
  56. Ran Raz. Fourier analysis for probabilistic communication complexity. Computational Complexity, 5(3-4):205-221, 1995. Google Scholar
  57. Ran Raz and Pierre McKenzie. Separation of the Monotone NC Hierarchy. Combinatorica, 19(3):403-435, 1999. Google Scholar
  58. Robert Robere. Unified Lower Bounds for Monotone Computation. PhD thesis, University of Toronto, 2018. Google Scholar
  59. Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen A Cook. Exponential lower bounds for monotone span programs. In Proceedings of the 57th FOCS, pages 406-415, 2016. Google Scholar
  60. Swagato Sanyal. A Composition Theorem via Conflict Complexity. CoRR, abs/1801.03285, 2018. URL: http://arxiv.org/abs/1801.03285.
  61. Alexander A Sherstov. The pattern matrix method. SIAM Journal on Computing, 40(6):1969-2000, 2011. Google Scholar
  62. Alexander A. Sherstov. The Communication Complexity of Gap Hamming Distance. Theory of Computing, 8(1):197-208, 2012. Google Scholar
  63. Alexander A. Sherstov. The multiparty communication complexity of set disjointness. In Proceedings of the 44th STOC, pages 525-548, 2012. Google Scholar
  64. Alexander A. Sherstov. Communication lower bounds using directional derivatives. In Proceedings of the 45th STOC, pages 921-930, 2013. Google Scholar
  65. Yaoyun Shi and Yufan Zhu. Quantum communication complexity of block-composed functions. Quantum Information & Computation, 9(5):444-460, 2009. Google Scholar
  66. Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang. Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture. In Proceedings of the 54th FOCS, pages 658-667, 2013. Google Scholar
  67. Thomas Vidick. A concentration inequality for the overlap of a vector on a large set, with application to the communication complexity of the Gap-Hamming-Distance problem. Chicago Journal of Theoretical Computer Science, 2013, 2013. Google Scholar
  68. Thomas Watson. A ZPP^NP Lifting Theorem. Unpublished preprint, 2017. Google Scholar
  69. David P. Woodruff. Efficient and private distance approximation in the communication and streaming models. PhD thesis, Massachusetts Institute of Technology, 2007. Google Scholar
  70. Andrew Chi-Chih Yao. Some Complexity Questions Related to Distributive Computing (Preliminary Report). In Proceedings of the 11h STOC, pages 209-213, 1979. 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