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:
Related books and surveys which may be of interest: