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