CSE 291E, Additive Combinatorics and its Applications, Fall 2024

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.

Instructors:

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

Class Times

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

Grading

Grades will be based on homework and a final project.

Homework

HW1, due 10/21

Online tools

Discussion board on Piazza: https://piazza.com/ucsd/fall2024/cse291e
Homework submission and grades on gradescope: https://www.gradescope.com/courses/858527; enrollment code YRJP62

Topics (tentative)

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.

If time permits, we will cover the following recent breakthroughs:

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

A tentative class schedule with references is available here. It will most likely change as we go through the course, depending on our pace and topics of interest by students.

Extra reading

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.