Eli Ben-Sasson, Madhu Sudan

We continue the investigation of locally testable codes, i.e.,

error-correcting codes for whom membership of a given word in the

code can be tested probabilistically by examining it in very few

locations. We give two general results on local testability:

First, motivated by the recently proposed notion of robust

probabilistically ...
more >>>

Ran Raz

We show how to encode $2^n$ (classical) bits $a_1,...,a_{2^n}$

by a single quantum state $|\Psi \rangle$ of size $O(n)$ qubits,

such that:

for any constant $k$ and any $i_1,...,i_k \in \{1,...,2^n\}$,

the values of the bits $a_{i_1},...,a_{i_k}$ can be retrieved

from $|\Psi \rangle$ by a one-round Arthur-Merlin interactive ...
more >>>

Dana Moshkovitz, Ran Raz

Given a function f:F^m \rightarrow F over a finite

field F, a low degree tester tests its proximity to

an m-variate polynomial of total degree at most d

over F. The tester is usually given access to an oracle

A providing the supposed restrictions of f to

affine subspaces of ...
more >>>