TY - GEN
T1 - Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes
AU - Barak, Boaz
AU - Dvir, Zeev
AU - Yehudayoff, Amir
AU - Wigderson, Avi
PY - 2011
Y1 - 2011
N2 - A (q,k,t)-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most q non-zeros, each column has at least k non-zeros and the supports of every two columns intersect in at most t rows. We prove that for m ≥ n, the rank of any (q,k,t)-design matrix over a field of characteristic zero (or sufficiently large finite characteristic) is at least n - (qtn/2k)2. Using this result we derive the following applications: Impossibility results for 2-query LCCs over large fields: A 2-query locally correctable code (LCC) is an error correcting code in which every codeword coordinate can be recovered, probabilistically, by reading at most two other code positions. Such codes have numerous applications and constructions (with exponential encoding length) are known over finite fields of small characteristic. We show that infinite families of such linear 2-query LCCs do not exist over fields of characteristic zero or large characteristic regardless of the encoding length. Generalization of known results in combinatorial geometry: We prove a quantitative analog of the Sylvester-Gallai theorem: Let v1,...,vm be a set of points in Cd such that for every i ∈ [m] there exists at least δ m values of j ∈ [m] such that the line through vi,vj contains a third point in the set. We show that the dimension of v 1,...,vm is at most O(1/δ2). Our results generalize to the high-dimensional case (replaceing lines with planes, etc.) and to the case where the points are colored (as in the Motzkin-Rabin Theorem).
AB - A (q,k,t)-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most q non-zeros, each column has at least k non-zeros and the supports of every two columns intersect in at most t rows. We prove that for m ≥ n, the rank of any (q,k,t)-design matrix over a field of characteristic zero (or sufficiently large finite characteristic) is at least n - (qtn/2k)2. Using this result we derive the following applications: Impossibility results for 2-query LCCs over large fields: A 2-query locally correctable code (LCC) is an error correcting code in which every codeword coordinate can be recovered, probabilistically, by reading at most two other code positions. Such codes have numerous applications and constructions (with exponential encoding length) are known over finite fields of small characteristic. We show that infinite families of such linear 2-query LCCs do not exist over fields of characteristic zero or large characteristic regardless of the encoding length. Generalization of known results in combinatorial geometry: We prove a quantitative analog of the Sylvester-Gallai theorem: Let v1,...,vm be a set of points in Cd such that for every i ∈ [m] there exists at least δ m values of j ∈ [m] such that the line through vi,vj contains a third point in the set. We show that the dimension of v 1,...,vm is at most O(1/δ2). Our results generalize to the high-dimensional case (replaceing lines with planes, etc.) and to the case where the points are colored (as in the Motzkin-Rabin Theorem).
KW - Sylvester Gallai
KW - matrix rigidity
KW - matrix scaling
UR - http://www.scopus.com/inward/record.url?scp=79959750951&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79959750951&partnerID=8YFLogxK
U2 - 10.1145/1993636.1993705
DO - 10.1145/1993636.1993705
M3 - Conference contribution
AN - SCOPUS:79959750951
SN - 9781450306911
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 519
EP - 528
BT - STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing
PB - Association for Computing Machinery
T2 - 43rd ACM Symposium on Theory of Computing, STOC 2011
Y2 - 6 June 2011 through 8 June 2011
ER -