Locally decodable code: Difference between revisions

Revision as of 18:52, 7 August 2018

Revision as of 18:53, 7 August 2018

Line 81:

Each individual query is distributed uniformly at random over the codeword. Thus, if the codeword is corrupted in at most a <math>\delta</math> fraction of locations, by the union bound, the probability that the algorithm samples only uncorrupted coordinates (and thus correctly recovers the bit) is at least <math>1 - (d+1)\delta</math>.<ref name=LDC1/>

For other decoding algorithms, see.<ref name=LDC1/>

== See also ==

* [[Private information retrieval]]

* [[Linear cryptanalysis]]

== References ==