Bo'az Klartag, Oded Regev

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

Srikanth Srinivasan, Madhu Sudan

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

Andrej Bogdanov, Gautam Prakriya

A function $f(x_1, \dots, x_n)$ from a product domain $\mathcal{D}_1 \times \cdots \times \mathcal{D}_n$ to an abelian group $\mathcal{G}$ is a direct sum if it is of the form $f_1(x_1) + \cdots + f_n(x_n)$. We present a new 4-query direct sum test with optimal (up to constant factors) soundness error. ... more >>>