Rutgers Discrete Mathematics Seminar

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.