Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with hypercontractive inequality:
TR10-143 | 19th September 2010
Bo'az Klartag, Oded Regev

Quantum One-Way Communication is Exponentially Stronger Than Classical Communication

In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol
communicating only $O(\log n)$ qubits, but for which any classical (randomized, bounded-error) protocol requires $\poly(n)$ bits of communication. That quantum protocol requires two rounds of communication. Ever since Raz's paper it was open whether the ... more >>>

TR17-138 | 17th September 2017
Srikanth Srinivasan, Madhu Sudan

Local decoding and testing of polynomials over grids

The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that $n$-variate
polynomials of total degree at most $d$ over
grids, i.e. sets of the form $A_1 \times A_2 \times \cdots \times A_n$, form
error-correcting codes (of distance at least $2^{-d}$ provided $\min_i\{|A_i|\}\geq 2$).
In this work we explore their local
decodability and local testability. ... more >>>

ISSN 1433-8092 | Imprint