Computer Science/Discrete Mathematics Seminar II

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.