Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Unbounded-error communication:
TR16-138 | 3rd September 2016
Alexander A. Sherstov

On multiparty communication with large versus unbounded error

The communication complexity of $F$ with unbounded error is the limit of the $\epsilon$-error randomized complexity of $F$ as $\epsilon\to1/2.$ Communication complexity with weakly bounded error is defined similarly but with an additive penalty term that depends on $1/2-\epsilon$. Explicit functions are known whose two-party communication complexity with unbounded error ... more >>>

TR16-140 | 9th September 2016
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

On SZK and PP

Revisions: 3

In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] ... more >>>

TR19-003 | 2nd January 2019
Alexander A. Sherstov, Pei Wu

Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0

The threshold degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{ij}]$ as the minimum rank of a real matrix $M$ with $\mathrm{sgn}\; M_{ij}=(-1)^{F_{ij}}$. Determining the maximum ... more >>>

ISSN 1433-8092 | Imprint