Document Open Access Logo

Sign Rank vs Discrepancy

Authors Hamed Hatami, Kaave Hosseini, Shachar Lovett

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.18.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Hamed Hatami
  • McGill University, Montreal, Canada
Kaave Hosseini
  • Carnegie Mellon University, Pittsburgh, PA, USA
Shachar Lovett
  • University of California San Diego, CA, USA

Funding

  • Hatami, Hamed: Supported by an NSERC grant.
  • Hosseini, Kaave: Supported by NSF grant CCF-1614023.
  • Lovett, Shachar: Supported by NSF grant CCF-1614023.

Cite AsGet BibTex

Hamed Hatami, Kaave Hosseini, and Shachar Lovett. Sign Rank vs Discrepancy. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CCC.2020.18

Abstract

Sign-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 the strongest possible separation by constructing a boolean matrix whose sign-rank is only 3, and yet its discrepancy is 2^{-Ω(n)}. We note that every matrix of sign-rank 2 has discrepancy n^{-O(1)}. Our result in particular implies that there are boolean functions with O(1) unbounded error randomized communication complexity while having Ω(n) weakly unbounded error randomized communication complexity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
Keywords
  • Discrepancy
  • sign rank
  • Unbounded-error communication complexity
  • weakly unbounded error communication complexity

Metrics

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

References

  1. Noga Alon, Shay Moran, and Amir Yehudayoff. Sign rank versus vc dimension. In Conference on Learning Theory, pages 47-80, 2016. Google Scholar
  2. László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 337-347. IEEE, 1986. Google Scholar
  3. Ronen Basri, Pedro F Felzenszwalb, Ross B Girshick, David W Jacobs, and Caroline J Klivans. Visibility constraints on features of 3d objects. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 1231-1238. IEEE, 2009. Google Scholar
  4. Amey Bhangale and Swastik Kopparty. The complexity of computing the minimum rank of a sign pattern matrix. arXiv preprint, 2015. URL: http://arxiv.org/abs/1503.04486.
  5. Harry Buhrman, Nikolay Vereshchagin, and Ronald de Wolf. On computation and communication with small bias. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), pages 24-32. IEEE, 2007. Google Scholar
  6. Mark Bun and Justin Thaler. Improved bounds on the sign-rank of AC⁰. In 43rd International Colloquium on Automata, Languages, and Programming, volume 55 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 37, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016. Google Scholar
  7. Arkadev Chattopadhyay and Toniann Pitassi. The story of set disjointness. ACM SIGACT News, 41(3):59-85, 2010. Google Scholar
  8. Benny Chor and Oded Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing, 17(2):230-261, 1988. Google Scholar
  9. Hartmut Klauck. Lower bounds for quantum communication complexity. In Proceedings 2001 IEEE International Conference on Cluster Computing, pages 288-297. IEEE, 2001. Google Scholar
  10. Adam R. Klivans and Rocco A. Servedio. Learning DNF in time 2^O(n^1/3). J. Comput. System Sci., 68(2):303-318, 2004. URL: https://doi.org/10.1016/j.jcss.2003.07.007.
  11. Troy Lee and Adi Shraibman. An approximation algorithm for approximation rank. In 2009 24th Annual IEEE Conference on Computational Complexity, pages 351-357. IEEE, 2009. Google Scholar
  12. Nati Linial, Shahar Mendelson, Gideon Schechtman, and Adi Shraibman. Complexity measures of sign matrices. Combinatorica, 27(4):439-463, 2007. URL: https://doi.org/10.1007/s00493-007-2160-5.
  13. Nati Linial and Adi Shraibman. Learning complexity vs. communication complexity. Combin. Probab. Comput., 18(1-2):227-245, 2009. URL: https://doi.org/10.1017/S0963548308009656.
  14. Nati Linial and Adi Shraibman. Lower bounds in communication complexity based on factorization norms. Random Structures &Algorithms, 34(3):368-394, 2009. Google Scholar
  15. Noam Nisan. The communication complexity of threshold gates. Combinatorics, Paul Erdos is Eighty, 1:301-315, 1993. Google Scholar
  16. Ramamohan Paturi and Janos Simon. Probabilistic communication complexity. Journal of Computer and System Sciences, 33(1):106-123, 1986. Google Scholar
  17. 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.
  18. Alexander A Sherstov. Halfspace matrices. Computational Complexity, 17(2):149-178, 2008. Google Scholar
  19. Alexander A Sherstov. The pattern matrix method. SIAM Journal on Computing, 40(6):1969-2000, 2011. Google Scholar
  20. Alexander A Sherstov. Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. Combinatorica, 33(1):73-96, 2013. Google Scholar
  21. Alexander A. Sherstov. The hardest halfspace. CoRR, abs/1902.01765, 2019. URL: http://arxiv.org/abs/1902.01765.
  22. Justin Thaler. Lower bounds for the approximate degree of block-composed functions. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  23. Hugh E. Warren. Lower bounds for approximation by nonlinear manifolds. Trans. Amer. Math. Soc., 133:167-178, 1968. URL: https://doi.org/10.2307/1994937.
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