Additive combinatorics is an active area of research that bridges combinatorics, number theory, harmonic analysis and ergodic theory. It studies the structure of "approximate algebraic" objects, such as sets of integers, or subsets of finite groups, and their behavior under algebraic operations such as addition and multiplication. While originally, the development of this field was motivated by problems in number theory, in recent years deep connections between additive combinatorics and fundamental problems in theoretical computer science have been discovered. In this course, we will cover basic topics in additive combinatorics, some recent developments in the field, and their applications in theoretical computer science. There are no specific prerequisites beyond a certain level of mathematical maturity.

- Professor: Shachar Lovett, email: slovett@ucsd.edu
- TA: Anthony Ostuni, email: aostuni@ucsd.edu

- Lectures: Tue, Thu 11:00am-12:20pm, Computer Science building (EBU3B), room 4258
- Office Hours: Mon 11:00am-12:00pm, Computer Science building (EBU3B), room B275

Grades will be based on homework and a final project.

- HW1, due 10/21

Homework submission and grades on gradescope: https://www.gradescope.com/courses/858527; enrollment code YRJP62

- Basics of set addition: Ruzsa distance, Plünneke-Ruzsa theorem, Ruzsa theorem, Frieman theorem, polynomial Frieman-Ruzsa (PFR) theorem (statement).
- Property testing: basic definitions, linearity testing, testing of linear maps and its connection to PFR.
- Statistical set addition: Balog-Szemerédi-Gowers (BSG) theorem; application to fast algorithm for 3-SUM with pre-processing.
- Arithmetic progressions: statement of important results (Van der Warden, Szemerédi, Green-Tao, Kelley-Meka); sets without arithmetic progressions (Behrend construction); Ruzsa-Szemerédi graphs; Application: impossibility of witness compression for NP languages.
- Communication complexity: connection between Ramsey problems in additive combinatorics and the Number-On-Forehead (NOF) model in communication complexity.
- Polynomial method: cap-set problem, connection to matrix multiplication algorithms.

- Proof of PFR theorem over vector spaces (Gowers-Green-Manners-Tao)
- Strong bounds for sets without 3-term arithmetic progressions (Kelley-Meka)

Related books and surveys which may be of interest:

- The book Additive Combinatorics by Tao and Vu.
- Guest column in ACM SIGACT: Additive Combinatorics and Theoretical Computer Science by Trevisan.
- Graduate survey Additive Combinatorics and its Applications in Theoretical Computer Science by Lovett.
- Mini-course on additive combinatorics by Barak, Trevisan and Wigderson.
- Selected Results in Additive Combinatorics: An Exposition by Viola.
- Notes on the polynomial Freiman-Ruzsa conjecture by Green.
- Montreal Lecture Notes on Quadratic Fourier Analysis by Green.
- Incidence Theorems and their Applications by Dvir.
- Additive combinatorics with a view towards computer science and cryptography: An exposition by Bibak.
- Additive Combinatorics over Finite Fields: New Results and Applications by Shparlinski.