License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2020.18
URN: urn:nbn:de:0030-drops-125700
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12570/
Go to the corresponding LIPIcs Volume Portal

Hatami, Hamed ; Hosseini, Kaave ; Lovett, Shachar

Sign Rank vs Discrepancy

pdf-format:
LIPIcs-CCC-2020-18.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{hatami_et_al:LIPIcs:2020:12570,
  author =	{Hamed Hatami and Kaave Hosseini and Shachar Lovett},
  title =	{{Sign Rank vs Discrepancy}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Shubhangi Saraf},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12570},
  URN =		{urn:nbn:de:0030-drops-125700},
  doi =		{10.4230/LIPIcs.CCC.2020.18},
  annote =	{Keywords: Discrepancy, sign rank, Unbounded-error communication complexity, weakly unbounded error communication complexity}
}

Keywords: Discrepancy, sign rank, Unbounded-error communication complexity, weakly unbounded error communication complexity
Collection: 35th Computational Complexity Conference (CCC 2020)
Issue Date: 2020
Date of publication: 17.07.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI