2026-07-22T16:01:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12570 2024-03-06T10:50:28Z ddc:004 open_access

Sign Rank vs Discrepancy Hatami, Hamed Hosseini, Kaave Lovett, Shachar Discrepancy sign rank Unbounded-error communication complexity weakly unbounded error communication complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hamed Hatami and Kaave Hosseini and Shachar Lovett 2020 Is Part Of LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2020.18 urn:nbn:de:0030-drops-125700 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.18 eng https://creativecommons.org/licenses/by/3.0/legalcode