TY - JOUR

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

AU - Bhattacharyya, Arnab

AU - Dvir, Zeev

AU - Saraf, Shubhangi

AU - Shpilka, Amir

N1 - Publisher Copyright:
© 2016, János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.

PY - 2016/2/1

Y1 - 2016/2/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 is 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 linear 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 Fp, that encode messages of length d. Our bound improves over the known bound of 2Ω(δd) [8,10,6] 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. We also obtain, as corollaries of our main theorem, new results in incidence geometry 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. The paper also contains an appendix, written by Sergey Yekhanin, showing that there do exist nonlinear LCCs of size 2O(d) over Fp, thus highlighting the importance of the linearity assumption for our result.

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 is 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 linear 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 Fp, that encode messages of length d. Our bound improves over the known bound of 2Ω(δd) [8,10,6] 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. We also obtain, as corollaries of our main theorem, new results in incidence geometry 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. The paper also contains an appendix, written by Sergey Yekhanin, showing that there do exist nonlinear LCCs of size 2O(d) over Fp, thus highlighting the importance of the linearity assumption for our result.

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

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

U2 - 10.1007/s00493-015-3024-z

DO - 10.1007/s00493-015-3024-z

M3 - Article

AN - SCOPUS:84948673948

SN - 0209-9683

VL - 36

SP - 1

EP - 36

JO - Combinatorica

JF - Combinatorica

IS - 1

ER -