Combinatorics Seminar
When: Sunday, February 27, 10am
Where: Schreiber 309
Speaker: Amir Yehudayoff, Technion
Title: On the rank of design matrices with applications
Abstract:
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 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:
(1) Impossibility results for 2-query LCCs over the complex
numbers: 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 the
complex numbers.
(2) Generalization of results in combinatorial geometry: We prove a
quantitative analog of the Sylvester-Gallai theorem: Let V =
{v_1,...,v_m} be a set of points in C^d such that for every i in
[m]
there exists at least em values of j in [m] such that the line
through
v_i,v_j contains a third point in the set. We show that the
dimension
of V is at most O(1/e^2) . We also provide a quantitative variant
and
a three-color variant of the Motzkin-Rabin theorem (which is a
colored
version of the Sylvester-Gallai theorem).
Joint work with Boaz Barak, Zeev Dvir and Avi Wigderson.