Document Open Access Logo

Lower Bound Methods for Sign-Rank and Their Limitations

Authors Hamed Hatami, Pooya Hatami , William Pires, Ran Tao, Rosie Zhao

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.22.pdf
  • Filesize: 0.83 MB
  • 24 pages

Document Identifiers

Author Details

Hamed Hatami
  • School of Computer Science, McGill University, Montreal, Canada
Pooya Hatami
  • Department of Computer Science and Engineering, The Ohio State University, Columbus, OH, USA
William Pires
  • School of Computer Science, McGill University, Montreal, Canada
Ran Tao
  • Department of Mathematics and Statistics, McGill University, Montreal, Canada
Rosie Zhao
  • School of Computer Science, McGill University, Montreal, Canada

Funding

  • Hatami, Hamed: Supported by an NSERC grant.
  • Hatami, Pooya: Supported by NSF grant CCF-1947546.

Acknowledgements

We wish to thank Shachar Lovett and Shay Moran for helpful discussions. We would like to thank Shay Moran for sharing the proof of Proposition B.3 with us.

Cite As Get BibTex

Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, and Rosie Zhao. Lower Bound Methods for Sign-Rank and Their Limitations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 22:1-22:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.22

Abstract

The sign-rank of a matrix A with ±1 entries is the smallest rank of a real matrix with the same sign pattern as A. To the best of our knowledge, there are only three known methods for proving lower bounds on the sign-rank of explicit matrices: (i) Sign-rank is at least the VC-dimension; (ii) Forster’s method, which states that sign-rank is at least the inverse of the largest possible average margin among the representations of the matrix by points and half-spaces; (iii) Sign-rank is at least a logarithmic function of the density of the largest monochromatic rectangle. 
We prove several results regarding the limitations of these methods.  
- We prove that, qualitatively, the monochromatic rectangle density is the strongest of these three lower bounds. If it fails to provide a super-constant lower bound for the sign-rank of a matrix, then the other two methods will fail as well.
- We show that there exist n × n matrices with sign-rank n^Ω(1) for which none of these methods can provide a super-constant lower bound.
- We show that sign-rank is at most an exponential function of the deterministic communication complexity with access to an equality oracle. We combine this result with Green and Sanders' quantitative version of Cohen’s idempotent theorem to show that for a large class of sign matrices (e.g., xor-lifts), sign-rank is at most an exponential function of the γ₂ norm of the matrix. We conjecture that this holds for all sign matrices.
- Towards answering a question of Linial, Mendelson, Schechtman, and Shraibman regarding the relation between sign-rank and discrepancy, we conjecture that sign-ranks of the ±1 adjacency matrices of hypercube graphs can be arbitrarily large. We prove that none of the three lower bound techniques can resolve this conjecture in the affirmative.

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
  • Theory of computation → Boolean function learning
Keywords
  • Average Margin
  • Communication complexity
  • margin complexity
  • monochromatic rectangle
  • Sign-rank
  • Unbounded-error communication complexity
  • VC-dimension

Metrics

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

Related Versions

References

  1. Noga Alon, Peter Frankl, and Vojtech Rödl. Geometrical realization of set systems and probabilistic communication complexity. In 26th Annual Symposium on Foundations of Computer Science, FOCS 1985, pages 277-280. IEEE Computer Society, 1985. Google Scholar
  2. Noga Alon, Shay Moran, and Amir Yehudayoff. Sign rank versus VC dimension. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, volume 49, pages 47-80, 2016. Google Scholar
  3. Noga Alon, János Pach, Rom Pinchasi, Radoš Radoičić, and Micha Sharir. Crossing patterns of semi-algebraic sets. Journal of Combinatorial Theory, Series A, 111(2):310-326, 2005. Google Scholar
  4. Franck Barthe. On a reverse form of the Brascamp-Lieb inequality. Invent. Math., 134(2):335-361, 1998. Google Scholar
  5. Shai Ben-David, Nadav Eiron, and Hans Ulrich Simon. Limitations of learning via embeddings in Euclidean half spaces. J. Mach. Learn. Res., 3(Spec. Issue Comput. Learn. Theory):441-461, 2002. Google Scholar
  6. Mark Bun, Nikhil S. Mande, and Justin Thaler. Sign-rank can increase under intersection. ACM Trans. Comput. Theory, 13(4):Art. 24, 17, 2021. URL: https://doi.org/10.1145/3470863.
  7. Mark Bun and Justin Thaler. Improved Bounds on the Sign-Rank of AC0. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 37:1-37:14, 2016. Google Scholar
  8. Arkadev Chattopadhyay, Shachar Lovett, and Marc Vinyals. Equality alone does not simulate randomness. In 34th Computational Complexity Conference (CCC 2019), 2019. Google Scholar
  9. Arkadev Chattopadhyay and Nikhil S. Mande. Separation of unbounded-error models in multi-party communication complexity. Theory Comput., 14(1):1-23, 2018. Google Scholar
  10. Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom., 9(2):145-158, 1993. URL: https://doi.org/10.1007/BF02189314.
  11. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT Press, Cambridge, MA; McGraw-Hill Book Co., Boston, MA, second edition, 2001. Google Scholar
  12. Marek Eliáš, Jiří Matoušek, Edgardo Roldán-Pensado, and Zuzana Safernová. Lower bounds on geometric Ramsey functions. SIAM J. Discrete Math., 28(4):1960-1970, 2014. Google Scholar
  13. Vitaly Feldman. A general characterization of the statistical query complexity. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, volume 65 of Proceedings of Machine Learning Research, pages 785-830, 2017. Google Scholar
  14. Vitaly Feldman, Cristóbal Guzmán, and Santosh Vempala. Statistical query algorithms for mean vector estimation and stochastic convex optimization. Math. Oper. Res., 46(3):912-945, 2021. Google Scholar
  15. Jürgen Forster. A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. System Sci., 65(4):612-625, 2002. Special issue on complexity, 2001 (Chicago, IL). URL: https://doi.org/10.1016/S0022-0000(02)00019-3.
  16. Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, and Hans Ulrich Simon. Relations between communication complexity, linear arrangements, and computational complexity. In FST TCS 2001: Foundations of software technology and theoretical computer science, volume 2245, pages 171-182. Springer, 2001. Google Scholar
  17. Jürgen Forster and Hans Ulrich Simon. On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes. Theoret. Comput. Sci., 350(1):40-48, 2006. URL: https://doi.org/10.1016/j.tcs.2005.10.015.
  18. Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, and János Pach. Overlap properties of geometric expanders. J. Reine Angew. Math., 671:49-83, 2012. Google Scholar
  19. Jacob Fox, János Pach, Adam Sheffer, Andrew Suk, and Joshua Zahl. A semi-algebraic version of Zarankiewicz’s problem. J. Eur. Math. Soc. (JEMS), 19(6):1785-1810, 2017. Google Scholar
  20. Jacob Fox, János Pach, and Andrew Suk. A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing. SIAM Journal on Computing, 45(6):2199-2223, 2016. URL: https://doi.org/10.1137/15M1007355.
  21. Ben Green and Tom Sanders. Boolean functions with small spectral norm. Geometric and Functional Analysis, 18(1):144-162, 2008. URL: https://doi.org/10.1007/s00039-008-0654-y.
  22. Ben Green and Tom Sanders. A quantitative version of the idempotent theorem in harmonic analysis. Ann. of Math. (2), 168(3):1025-1054, 2008. Google Scholar
  23. Lianna Hambardzumyan, Hamed Hatami, and Pooya Hatami. Dimension-free bounds and structural results in communication complexity. Israel J. Math., 2021. To appear. Google Scholar
  24. Hamed Hatami, Kaave Hosseini, and Shachar Lovett. Sign rank vs discrepancy. In 35th Computational Complexity Conference, volume 169 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 18, 14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  25. Max Hopkins, Daniel Kane, Shachar Lovett, and Gaurav Mahajan. Point location and active learning: Learning halfspaces almost optimally. In In 61st Annual Symposium on Foundations of Computer Science (FOCS 2020), pages 1034-1044. IEEE Computer Society, 2020. Google Scholar
  26. Michael Kallweit and Hans Ulrich Simon. A close look to margin complexity and related parameters. In Sham M. Kakade and Ulrike von Luxburg, editors, COLT 2011 - The 24th Annual Conference on Learning Theory, volume 19 of JMLR Proceedings, pages 437-456. JMLR.org, 2011. Google Scholar
  27. Adam R. Klivans and Alexander A. Sherstov. Unconditional lower bounds for learning intersections of halfspaces. Mach. Learn., 69(2-3):97-114, 2007. Google Scholar
  28. Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, Cambridge, 1997. Google Scholar
  29. Nati Linial, Shahar Mendelson, Gideon Schechtman, and Adi Shraibman. Complexity measures of sign matrices. Combinatorica, 27(4):439-463, 2007. Google Scholar
  30. Nati Linial and Adi Shraibman. Learning complexity vs. communication complexity. Combin. Probab. Comput., 18(1-2):227-245, 2009. Google Scholar
  31. Nati Linial and Adi Shraibman. Lower bounds in communication complexity based on factorization norms. Random Structures & Algorithms, 34(3):368-394, 2009. Google Scholar
  32. Leo Livshits. A note on 0-1 Schur multipliers. Linear Algebra Appl., 222:15-22, 1995. URL: https://doi.org/10.1016/0024-3795(93)00268-5.
  33. Jiří Matoušek. On the distortion required for embedding finite metric spaces into normed spaces. Israel J. Math., 93:333-344, 1996. Google Scholar
  34. J. Milnor. On the Betti numbers of real varieties. Proc. Amer. Math. Soc., 15:275-280, 1964. URL: https://doi.org/10.2307/2034050.
  35. Assaf Naor. Metric dimension reduction: a snapshot of the Ribe program. In Proceedings of the International Congress of Mathematicians - Rio de Janeiro 2018. Vol. I. Plenary lectures, pages 759-837. World Sci. Publ., Hackensack, NJ, 2018. Google Scholar
  36. Ramamohan Paturi and Janos Simon. Probabilistic communication complexity. Journal of Computer and System Sciences, 33(1):106-123, 1986. Google Scholar
  37. Alexander A. Razborov and Alexander A. Sherstov. The sign-rank of AC⁰. SIAM J. Comput., 39(5):1833-1855, 2010. URL: https://doi.org/10.1137/080744037.
  38. Tom Sanders. A quantitative version of the non-abelian idempotent theorem. Geom. Funct. Anal., 21(1):141-221, 2011. Google Scholar
  39. Tom Sanders. Boolean functions with small spectral norm, revisited. Math. Proc. Cambridge Philos. Soc., 167(2):335-344, 2019. Google Scholar
  40. Tom Sanders. Bounds in Cohen’s idempotent theorem. J. Fourier Anal. Appl., 26(2):Paper No. 25, 64, 2020. Google Scholar
  41. Alexander A. Sherstov. The unbounded-error communication complexity of symmetric functions. In Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS '08, pages 384-393, 2008. Google Scholar
  42. Alexander A. Sherstov. Halfspace matrices. Comput. Complexity, 17(2):149-178, 2008. Google Scholar
  43. Alexander A. Sherstov and Pei Wu. Near-optimal lower bounds on the threshold degree and sign-rank of AC0. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 401-412, New York, NY, USA, 2019. Association for Computing Machinery. Google Scholar
  44. Nathan Srebro and Adi Shraibman. Rank, trace-norm and max-norm. In Learning theory, volume 3559 of Lecture Notes in Comput. Sci., pages 545-560. Springer, Berlin, 2005. Google Scholar
  45. Andrew Suk. Semi-algebraic Ramsey numbers. J. Combin. Theory Ser. B, 116:465-483, 2016. URL: https://doi.org/10.1016/j.jctb.2015.10.001.
  46. René Thom. Sur l'homologie des variétés algébriques réelles. In Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), pages 255-265. Princeton Univ. Press, Princeton, N.J., 1965. Google Scholar
  47. Hugh E. Warren. Lower bounds for approximation by nonlinear manifolds. Trans. Amer. Math. Soc., 133:167-178, 1968. Google Scholar
  48. Zhiqiang Zhang and Yaoyun Shi. Communication complexities of symmetric XOR functions. Quantum Inf. Comput., 9(3-4):255-263, 2009. 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