We prove a quantitative version of the multi-colored Motzkin-Rabin theorem in the spirit of [BDWY12]: Let $V_1,ldots,V_n subset R^d$ be $n$ disjoint sets of points (of $n$ `colors). Suppose that for every $V_i$ and every point $v in V_i$ there are at
least $delta |V_i|$ other points $u in V_i$ so that the line connecting $v$ and $u$ contains a third point of another color. Then the union of the points in all $n$ sets is contained in a subspace of dimension bounded by a function of $n$ and $delta$ alone.
We describe a construction of explicit affine extractors over large finite fields with exponentially small error and linear output length. Our construction relies on a deep theorem of Deligne giving tight estimates for exponential sums over smooth varieties in high dimensions.
We prove that 3-query linear locally correctable codes over the Reals of dimension $d$ require block length $n>d^{2+lambda}$ for some fixed, positive $lambda >0$. Geometrically, this means that if $n$ vectors in $R^d$ are such that each vector is spa
nned by a linear number of disjoint triples of others, then it must be that $n > d^{2+lambda}$. This improves the known quadratic lower bounds (e.g. {KdW04, Wood07}). While a modest improvement, we expect that the new techniques introduced in this work will be useful for further progress on lower bounds of locally correctable and decodable codes with more than 2 queries, possibly over other fields as well. Our proof introduces several new ideas to existing lower bound techniques, several of which work over every field. At a high level, our proof has two parts, {it clustering} and {it random restriction}. The clustering step uses a powerful theorem of Barthe from convex geometry. It can be used (after preprocessing our LCC to be {it balanced}), to apply a basis change (and rescaling) of the vectors, so that the resulting unit vectors become {it nearly isotropic}. This together with the fact that any LCC must have many `correlated pairs of points, lets us deduce that the vectors must have a surprisingly strong geometric clustering, and hence also combinatorial clustering with respect to the spanning triples. In the restriction step, we devise a new variant of the dimension reduction technique used in previous lower bounds, which is able to take advantage of the combinatorial clustering structure above. The analysis of our random projection method reduces to a simple (weakly) random graph process, and works over any field.
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 mo
st 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_1,...,v_m$ be a set of points in $C^d$ such that for every $i in [m]$ there exists at least $delta m$ 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_1,...,v_m }$ is at most $O(1/delta^2)$. Our results generalize to the high dimensional case (replacing lines with planes, etc.) and to the case where the points are colored (as in the Motzkin-Rabin Theorem).
