Sign-rank Can Increase under Intersection
Article No.: 24, Pages 1 - 17
Abstract
The communication class UPPcc is a communication analog of the Turing Machine complexity class PP. It is characterized by a matrix-analytic complexity measure called sign-rank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds.
For a communication problem f, let f ∧ f denote the function that evaluates f on two disjoint inputs and outputs the AND of the results. We exhibit a communication problem f with UPPcc(f) = O(log n), and UPPcc(f ∧ f) = Θ (log2 n). This is the first result showing that UPP communication complexity can increase by more than a constant factor under intersection. We view this as a first step toward showing that UPPcc, the class of problems with polylogarithmic-cost UPP communication protocols, is not closed under intersection.
Our result shows that the function class consisting of intersections of two majorities on n bits has dimension complexity nOmegaΩ(log n). This matches an upper bound of (Klivans, O’Donnell, and Servedio, FOCS 2002), who used it to give a quasipolynomial time algorithm for PAC learning intersections of polylogarithmically many majorities. Hence, fundamentally new techniques will be needed to learn this class of functions in polynomial time.
References
[1]
Noga Alon, Peter Frankl, and Vojtech Rödl. 1985. Geometrical realization of set systems and probabilistic communication complexity. In Proceedings of the 26th Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 277–280.
[2]
Noga Alon, Shay Moran, and Amir Yehudayoff. 2016. Sign rank versus VC dimension. In Proceedings of the 29th Conference on Learning Theory (COLT). JMLR.org, 47–80. Retrieved from http://jmlr.org/proceedings/papers/v49/alon16.html.
[3]
Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, and Shengyu Zhang. 2010. Any AND-OR formula of size can be evaluated in time on a quantum computer. SIAM J. Comput. 39, 6 (2010), 2513–2530.
[4]
László Babai, Peter Frankl, and Janos Simon. 1986. Complexity classes in communication complexity theory (preliminary version). In Proceedings of the 27th Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 337–347.
[5]
Richard Beigel, Nick Reingold, and Daniel A. Spielman. 1995. PP Is closed under intersection. J. Comput. Syst. Sci. 50, 2 (1995), 191–202.
[6]
Arnab Bhattacharyya, Suprovat Ghoshal, and Rishi Saket. 2018. Hardness of learning noisy halfspaces using polynomial thresholds. In Proceedings of the Conference On Learning Theory (COLT). PMLR, 876–917. Retrieved from http://proceedings.mlr.press/v75/bhattacharyya18a.html.
[7]
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan. 2017. On the power of statistical zero knowledge. In Proceedings of the 58th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 708–719.
[8]
Mark Bun, Nikhil S. Mande, and Justin Thaler. 2019. Sign-rank can increase under intersection. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 30:1–30:14.
[9]
Mark Bun and Justin Thaler. 2016. Improved bounds on the sign-rank of AC. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 37:1–37:14.
[10]
Mark Bun and Justin Thaler. 2019. The large-error approximate degree of AC. In Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 55:1–55:16.
[11]
Arkadev Chattopadhyay and Nikhil S. Mande. 2018. A short list of equalities induces large sign rank. In Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 47–58.
[12]
Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. 2006. New results for learning noisy parities and halfspaces. In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, IEEE Computer Society, 563–574.
[13]
Jürgen Forster. 2002. A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. Syst. Sci. 65, 4 (2002), 612–625.
[14]
Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, and Hans Ulrich Simon. 2001. Relations between communication complexity, linear arrangements, and computational complexity. In Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science. Springer, 171–182.
[15]
Jürgen Forster and Hans Ulrich Simon. 2006. On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes. Theor. Comput. Sci. 350, 1 (2006), 40–48.
[16]
Mika Göös, Pritish Kamath, Toniann Pitassi, and Thomas Watson. 2019. Query-to-communication lifting for P. Comput. Complex. 28, 1 (2019), 113–144.
[17]
Mika Göös, Toniann Pitassi, and Thomas Watson. 2017. Query-to-communication lifting for BPP. In Proceedings of the 58th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 132–143.
[18]
Mika Göös, Toniann Pitassi, and Thomas Watson. 2018. The landscape of communication complexity classes. Comput. Complex. 27, 2 (2018), 245–304.
[19]
Michael Kearns. 1998. Efficient noise-tolerant learning from statistical queries. J. ACM 45, 6 (1998), 983–1006.
[20]
Subhash Khot and Rishi Saket. 2011. On the hardness of learning intersections of two halfspaces. J. Comput. Syst. Sci. 77, 1 (2011), 129–141.
[21]
Adam R. Klivans, Ryan O’Donnell, and Rocco A. Servedio. 2004. Learning intersections and thresholds of halfspaces. J. Comput. Syst. Sci. 68, 4 (2004), 808–840.
[22]
Adam R. Klivans and Rocco A. Servedio. 2004. Learning DNF in time. J. Comput. Syst. Sci. 68, 2 (2004), 303–318.
[23]
Adam R. Klivans and Alexander A. Sherstov. 2009. Cryptographic hardness for learning intersections of halfspaces. J. Comput. Syst. Sci. 75, 1 (2009), 2–12.
[24]
Nati Linial, Shahar Mendelson, Gideon Schechtman, and Adi Shraibman. 2007. Complexity measures of sign matrices. Combinatorica 27, 4 (2007), 439–463.
[25]
Marvin Minsky and Seymour Papert. 1969. Perceptrons. The MIT Press.
[26]
Ramamohan Paturi and Janos Simon. 1986. Probabilistic communication complexity. J. Comput. Syst. Sci. 33, 1 (1986), 106–123.
[27]
Alexander A. Razborov and Alexander A. Sherstov. 2010. The sign-rank of AC. SIAM J. Comput. 39, 5 (2010), 1833–1855.
[28]
Alexander A. Sherstov. 2011. The pattern matrix method. SIAM J. Comput. 40, 6 (2011), 1969–2000.
[29]
Alexander A. Sherstov. 2011. The unbounded-error communication complexity of symmetric functions. Combinatorica 31, 5 (2011), 583–614.
[30]
Alexander A. Sherstov. 2013. The intersection of two halfspaces has high threshold degree. SIAM J. Comput. 42, 6 (2013), 2329–2374.
[31]
Alexander A. Sherstov. 2013. Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. Combinatorica 33, 1 (2013), 73–96.
[32]
Alexander A. Sherstov. 2018. Breaking the Minsky-Papert barrier for constant-depth circuits. SIAM J. Comput. 47, 5 (2018), 1809–1857.
[33]
Alexander A. Sherstov and Pei Wu. 2019. Near-optimal lower bounds on the threshold degree and sign-rank of AC. In Proceedings of the 51st ACM SIGACT Symposium on Theory of Computing (STOC). ACM, 401–412.
Index Terms
- Sign-rank Can Increase under Intersection
Recommendations
The Sign-Rank of AC$^0$
The sign-rank of a matrix $A=[A_{ij}]$ with $\pm1$ entries is the least rank of a real matrix $B=[B_{ij}]$ with $A_{ij}B_{ij}>0$ for all $i,j$. We obtain the first exponential lower bound on the sign-rank of a function in $\mathsf{AC}^0$. Namely, let $f(...
A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of ComputingWe introduce a new topological argument based on the Borsuk-Ulam theorem to prove a lower bound on sign-rank.
This result implies the strongest possible separation between randomized and unbounded-error communication complexity. More precisely, we ...
Sign rank vs discrepancy
CCC '20: Proceedings of the 35th Computational Complexity ConferenceSign-rank and discrepancy are two central notions in communication complexity. The seminal work of Babai, Frankl, and Simon from 1986 initiated an active line of research that investigates the gap between these two notions. In this article, we establish ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
December 2021
198 pages
Copyright © 2021 Association for Computing Machinery.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 September 2021
Accepted: 01 April 2021
Revised: 01 February 2021
Received: 01 May 2020
Published in TOCT Volume 13, Issue 4
Check for updates
Author Tags
Qualifiers
- Research-article
- Refereed
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 54Total Downloads
- Downloads (Last 12 months)9
- Downloads (Last 6 weeks)3
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format