Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > UNBOUNDED-ERROR COMMUNICATION COMPLEXITY:
Reports tagged with Unbounded-error communication complexity:
TR07-112 | 25th September 2007
Alexander A. Sherstov

#### Unbounded-Error Communication Complexity of Symmetric Functions

The sign-rank of a real matrix M is the least rank
of a matrix R in which every entry has the same sign as the
corresponding entry of M. We determine the sign-rank of every
matrix of the form M=[ D(|x AND y|) ]_{x,y}, where
D:{0,1,...,n}->{-1,+1} is given and ... more >>>

TR16-075 | 9th May 2016
Mark Bun, Justin Thaler

#### Improved Bounds on the Sign-Rank of AC$^0$

Revisions: 1

The sign-rank of a matrix $A$ with entries in $\{-1, +1\}$ is the least rank of a real matrix $B$ with $A_{ij} \cdot B_{ij} > 0$ for all $i, j$. Razborov and Sherstov (2008) gave the first exponential lower bounds on the sign-rank of a function in AC$^0$, answering an ... more >>>

TR19-067 | 6th May 2019
Hamed Hatami, Kaave Hosseini, Shachar Lovett

#### Sign rank vs Discrepancy

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 ... more >>>

ISSN 1433-8092 | Imprint