Cap-sets in $(F_q)^n$ and related problems

Computer Science/Discrete Mathematics Seminar II
Topic:Cap-sets in $(F_q)^n$ and related problems
Speaker:Zeev Dvir
Affiliation:Princeton University; von Neumann Fellow, School of Mathematics
Date:Tuesday, October 31
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/2017/1031-ZeevDvir

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.