Locally testable code: Difference between revisions

Revision as of 15:52, 19 June 2018

Revision as of 15:38, 24 October 2019

Line 9:

:<math>\Delta(x,y)=|\{i:x_i \neq y_i\}|</math>

The distance of a string <math>w</math> from a code <math>C:\{0,1\}^k\to\{0,1\}^n</math> is computed by

:<math>\Delta(w,C)=\min_x\{\Delta(w,C(x))\}</math>

Relative distances are computed as a fraction of the number of bits

:<math>\delta(x,y)=\Delta(x,y)/n \text{ and } \delta(w,C)=\Delta(w,C)/n</math>