Locally testable code: Difference between revisions

Revision as of 14:09, 3 March 2009

Revision as of 03:50, 4 March 2009

Line 4:

==Definition==

A family of error-correcting codes ''C_n'' ⊆ {0, 1}^''n'' is '''locally testable''' with ''soundness'' ''s''(δ) (where ''ns'',(δ) < 1 for every δ > 0), and ''query complexity'' ''q''(''n'') if there exists a non-adaptive [[oracle machine|oracle algorithm]] ''T'' (the ''tester'') that on input 1^''n'' and given oracle access to a string ''y ∈ {0, 1}^''n'' satisfies the following:

* '''Completeness''': If ''y ∈ C'', then ''T''^''y''(1^''n'') accepts with probability 1.

* '''Soundness''': If the [[Hamming distance]] between ''y'' and ''C'' is δ''n'', then ''T''^''y''(1^''n'') accepts with probability at most ''s''(''n'', δ).

In theoretical computer science, one is typically interested in locally testable codes whose query complexity is constant or at most logarithmic.

==Examples==