|Computer Science/Discrete Mathematics Seminar II|
|Topic:||Cap-sets in $(F_q)^n$ and related problems|
|Affiliation:||Princeton University; von Neumann Fellow, School of Mathematics|
|Date:||Tuesday, October 31|
|Time/Room:||10:30am - 12:30pm/S-101|
A cap set in $(F_q)^n$ is a set not containing a three term arithmetic progression. Last year, in a surprising breakthrough, Croot-Lev-Pach and a follow up paper of Ellenberg-Gijswijt showed that such sets have to be of size at most $c^n$ with $c < q$ (as $n$ goes to infinity). The simple algebraic proof of this result has since led to new progress and insights on several other related problems in combinatorics and theoretical computer science. In this survey I will describe these results including some new work (joint with B. Edelman) relating to matrix rigidity.