Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Local Testability:
TR03-006 | 23rd January 2003
Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova

3CNF Properties are Hard to Test

For a boolean formula \phi on n variables, the associated property
P_\phi is the collection of n-bit strings that satisfy \phi. We prove
that there are 3CNF properties that require a linear number of queries,
even for adaptive tests. This contrasts with 2CNF properties
that are testable with O(\sqrt{n}) ... more >>>

TR08-033 | 21st March 2008
Elena Grigorescu, Tali Kaufman, Madhu Sudan

2-Transitivity is Insufficient for Local Testability

A basic goal in Property Testing is to identify a
minimal set of features that make a property testable.
For the case when the property to be tested is membership
in a binary linear error-correcting code, Alon et al.~\cite{AKKLR}
had conjectured that the presence of a {\em single} low weight
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