Type of Talk: ACT Seminar

Speaker/Affiliation: Zeev Dvir/P

rinceton University

Date/Time: Tuesday, November 16, 2010, 4:00 p.m

.

Location: ACES 2.402

Host: David Zuckerman

Talk Title: "Ra

nk Bounds for Design Matrices with Applications to Combinatorial Geometry
and Locally Correctable Codes"

Talk Abstract:
A (q,k,t)-design m

atrix is an m x n matrix whose pattern of
zeros/non-zeros satisfies the f

ollowing 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 int

ersect 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 thi

s result we derive the following applications:

(1) Impossibility resul

ts for 2-query LCCs over large fields: A
2-query locally correctable code
(LCC) is an error correcting code in
which every codeword coordinate ca

n be recovered, probabilistically,
by reading at most two other code po

sitions. Such codes have numerous
applications and constructions (with
exponential encoding length)
are known over finite fields of small chara

cteristic. We show that
infinite families of such linear 2-query LCCs do

not exist over
fields of characteristic zero or large characteristic rega

rdless of
the encoding length.

(2) Generalization of known results i

n combinatorial geometry: We
prove a quantitative analog of the Sylvester

-Gallai theorem: Let
v_1,...,v_m be a set of points in C^d such that fo

r every i in [m]
there exists at least delta*m values of j in [m] such th

at the line
through v_i,v_j contains a third point in the set. We show t

hat the
dimension of { v_1,...,v_m } is at most O(1/delta^2). We also p

rovide
a quantitative variant and a three-color variant of the Motzkin-Ra

bin
theorem (which is a colored version of the Sylvester-Gallai theorem).

Joint work with Boaz Barak, Avi Wigderson and Amir Yehudayoff