# ACT Seminar - Zeev Dvir/Princeton University: "Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes", ACES 2.402

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

- About
- Research
- Faculty
- Awards & Honors
- Undergraduate
- Graduate
- Careers
- Outreach
- Industry
- Alumni
- UTCS Direct