"Extremal Problems for Linear Dependencies"

Jacques Verstraete

(UCSD)

Monday, May 12th, 2014, 2:00 pm

EBU3B, Room 4140

Abstract:

A fundamental problem at the intersection of coding theory and combinatorics is to determine the maximum size $f(n,k,r)$ of a set of vectors of hamming weight at most $r$ in $F_2^n$ such that no subset of at most $k$ of the vectors form a linear dependency. Motivated by the refutation problem for random 3-CNF formulas, U. Feige conjectured that for each integer $r \geq 2$, there exist constants $a,b > 0$ depending only on $r$ such that $f(n,k,r) \leq k(\log n)^{a} (n/k)^{r/2 + b/k}$ for all $k \in \{2,3,\dots,n\}$. We sketch the proof of this conjecture, improving earlier results by a number of authors, and we give an application to a problem in combinatorial number theory, answering a question of Erdos.

Partly joint work with Assaf Naor