Revision as of 14:08, 3 March 2009 edit Tcshasaposse (talk \| contribs) 244 edits introduced basic definition, still needs examples		Revision as of 14:09, 3 March 2009 edit undo Tcshasaposse (talk \| contribs) 244 edits mNo edit summary Next edit →
Line 5: ==Definition== A family of error-correcting codes ''C<sub>n</sub>'' ⊆ {0, 1}<sup>''n''</sup> is '''locally testable''' with ''soundness'' ''s''(''n'', δ), and ''query complexity'' ''q''(''n'') if there exists a non-adaptive [[oracle machine\|oracle algorithm]] ''T'' (the ''tester'') that on input 1<sup>''n''</sup> and given oracle access to a string ''y ∈ {0, 1}<sup>''n''</sup> satisfies the following: * '''Completeness''': If ''y ∈ C'', then ''T''(1<sup>''ny''</sup>)(1<sup>''yn''</sup>) accepts with probability 1. * '''Soundness''': If the [[Hamming distance]] between ''y'' and ''C'' is δ''n'', then ''T''(1<sup>''ny''</sup>)(1<sup>''yn''</sup>) accepts with probability at most ''s''(''n'', εδ). ==Examples==

Locally testable code: Difference between revisions