Combinatorics and Complexity

During Academic year 2017-18, the CMSA will be hosting a Program on Combinatorics and Complexity.  This year will be organized by Noga Alon, Boaz Barak, Jacob Fox, Madhu Sudan, Salil Vadhan, and Leslie Valiant.

Combinatorics and Computational Complexity have enjoyed a rich history of interaction leading to many significant developments in the two fields, such as the theories of NP-completeness, expander graphs, pseudorandomness, and property testing. Lately these fields have seen many new points of intersection such as in the development of the polynomial method (used, for example, in recent advances on the cap-set problem as well as in development of optimal list-decodable codes), the method of interlacing families of polynomials (yielding Ramanujan graphs and the resolution of the Kadison-Singer problem), and the theory of randomness extractors (yielding explicit constructions of Ramsey graphs).  This special program will bring together experts in the fields to collaborate, to learn about the latest advances in the area, and to forge new connections.

The program will include a series of workshops in the intersection of the two fields. These four workshops will be on: 

The program will also feature a series of public lectures held at the center. The scheduled speakers are:

Date Name Title
09-07-17 Noga Alon

NogaAlon

 TBA
11-02-17 Jennifer Chayes

JenniferChayes

TBA
02-01-2018 Jacob Fox

JacobFox

TBA
03-20-18 Dan Spielman

DanSpielman

TBA

Researchers interested in participating in the special year are encouraged to contact the organizers through the CMSA Administrative Coordinator, Sarah LaBauve (slabauve@math.harvard.edu).  Prospective postdocs are encouraged to apply at http://toc.seas.harvard.edu/theory-group-postdocs.