TY - GEN

T1 - Tight lower bounds for 2-query LCCs over finite fields

AU - Bhattacharyya, Arnab

AU - Dvir, Zeev

AU - Shpilka, Amir

AU - Saraf, Shubhangi

PY - 2011/12/1

Y1 - 2011/12/1

N2 - A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic self-correcting algorithm that, with high probability, can correct any coordinate of the codeword by looking at only a few other coordinates, even if a fraction δ of the coordinates are corrupted. LCCs are a stronger form of LDCs (Locally Decodable Codes) which have received a lot of attention recently due to their many applications and surprising constructions. In this work we show a separation between 2-query LDCs and LCCs over finite fields of prime order. Specifically, we prove a lower bound of the form p Ω(δd) on the length of linear 2-query LCCs over double-struck F p, that encode messages of length d. Our bound improves over the known bound of 2 Ω(δd) [9], [12], [8] which is tight for LDCs. Our proof makes use of tools from additive combinatorics which have played an important role in several recent results in theoretical computer science. Corollaries of our main theorem are new incidence geometry results over finite fields. The first is an improvement to the Sylvester-Gallai theorem over finite fields [14] and the second is a new analog of Beck's theorem over finite fields.

AB - A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic self-correcting algorithm that, with high probability, can correct any coordinate of the codeword by looking at only a few other coordinates, even if a fraction δ of the coordinates are corrupted. LCCs are a stronger form of LDCs (Locally Decodable Codes) which have received a lot of attention recently due to their many applications and surprising constructions. In this work we show a separation between 2-query LDCs and LCCs over finite fields of prime order. Specifically, we prove a lower bound of the form p Ω(δd) on the length of linear 2-query LCCs over double-struck F p, that encode messages of length d. Our bound improves over the known bound of 2 Ω(δd) [9], [12], [8] which is tight for LDCs. Our proof makes use of tools from additive combinatorics which have played an important role in several recent results in theoretical computer science. Corollaries of our main theorem are new incidence geometry results over finite fields. The first is an improvement to the Sylvester-Gallai theorem over finite fields [14] and the second is a new analog of Beck's theorem over finite fields.

KW - Sylvester-Gallai theorem

KW - additive combinatorics

KW - locally decodable codes

UR - http://www.scopus.com/inward/record.url?scp=84863301031&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863301031&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2011.28

DO - 10.1109/FOCS.2011.28

M3 - Conference contribution

AN - SCOPUS:84863301031

SN - 9780769545714

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 638

EP - 647

BT - Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011

T2 - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011

Y2 - 22 October 2011 through 25 October 2011

ER -