Title: Subspace-evasive sets
Speaker: Shachar Lovett, IAS
Date: Tuesday, November 1, 2011 2:00pm
Location: Hill Center, Room 425, Rutgers University, Busch Campus, Piscataway, NJ
We construct explicit subspace-evasive sets. These are subsets of $F^n$ of size $|F|^{(1-eps)n}$ whose intersection with any $k$-dimensional subspace is bounded by a constant $c(k,eps)$. This problem was raised by Guruswami (CCC 2011) as it leads to optimal rate list-decodable codes of constant list size. The main technical ingredient is the construction of $k$ low-degree polynomials whose common set of zeros has small intersection with any $k$-dimensional subspace. Joint work with Zeev Dvir.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math