Email: slovett@cs.ucsd.edu

**Class Times**: MW 12:00-1:30pm, Computer Science building (EBU3B), room 4109

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

The course material will be broadly based on the survey Additive Combinatorics and its Applications in Theoretical Computer Science, as well as some more advanced topics, based on audience interest and time permitting. Topics which will be covered include: structure of set addition, arithmetic progressions in sets, sum-product theorems and higher-order Fourier analysis. We will discuss applications of these to several areas in theoretical computer science, including: property testing, explicit constructions of pseudo-random objects, and hardness results in complexity.

Grades will be based on homework.

Homework:

- Homework 1, due 1/27.
- Homework 2, due 2/17.
- Homework 2, due 3/14.

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.
- 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.