"Subspace-evasive sets"
Shachar Lovett
Institute for Advanced Studies
Monday, April 9th, 2012, 2:00 pm
EBU3B, Room 4140
Abstract
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.
Short biography
Shachar Lovett is a post-doc at the Institute of Advanced Study in Princeton, NJ. He is part of the Theoretical Computer Science / Discrete Math group, headed by Avi Wigderson. Before that he did his PhD at the Weizmann Institute of Science under the supervision of Omer Reingold and Ran Raz.
He is interested in the relations between structure, randomness and pseudo-randomness in many areas of mathematics and computer science, and in particular in computational complexity, additive combinatorics and coding theory. He is also very interested in algebraic techniques.