Computer Science/Discrete Mathematics Seminar I

The "cap set problem" asks for the size of the largest subset $S$ of the vector space $\mathbb F_3^n$ containing no three elements summing to 0. Progress on this problem was slow for many years, until the spring of 2016, when a very short argument yielding a much better upper bound was developed. This is another startling success of "the polynomial method," which, especially since the 2008 theorem of Zeev Dvir on the finite Kakeya problem, has had an amazing run of providing short proofs of old problems that were thought to be hard. I'll explain the proof and some of the subsequent applications of the ideas: especially interesting is the notion of "slice rank," an invariant of higher tensors which seems to ripe for exploration.Relevant papers:

• http://arxiv.org/abs/1605.01506
• https://arxiv.org/abs/1605.09223
• https://arxiv.org/abs/1612.01929
• https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound/