Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOW DEGREE TEST:
Reports tagged with Low degree test:
TR04-046 | 4th June 2004
Eli Ben-Sasson, Madhu Sudan

Robust Locally Testable Codes and Products of Codes

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


TR05-038 | 10th April 2005
Ran Raz

Quantum Information and the PCP Theorem

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


TR05-086 | 14th August 2005
Dana Moshkovitz, Ran Raz

Sub-Constant Error Low Degree Test of Almost Linear Size

Revisions: 1

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




ISSN 1433-8092 | Imprint