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: 

There will also be a weekly seminar held every Friday from 1:00-4:00pm in room G10. A list of speakers and seminar topics can be found on the Combinatorics and Complexity seminar page.

Combinatorics will also be featured in this year’s Ahlfors Lecture Series, given by Timothy Gowers (University of Cambridge) on October 11-12.

Participation: Researchers interested in participating in the special year through a short- or long-term visit to CMSA are encouraged to contact the organizers through the CMSA Administrative Coordinator, Sarah LaBauve (  Each of the workshops is also open to participation by all interested researchers subject to capacity. Registration forms can be found on the webpages for the individual workshops. 

A list of lodging options convenient to the Center can also be found on our recommended lodgings page.

In addition, the program will feature a series of public lectures held at Askwith Hall at the Harvard Graduate School of Education. The scheduled speakers are:

Date Name Title


Askwith Hall


Noga Alon


Title: Graph Coloring: Local and Global

Abstract: Graph Coloring is arguably the most popular subject in Discrete Mathematics, and its combinatorial, algorithmic and computational aspects have been studied intensively. The most basic notion in the area, the chromatic number of a graph, is an inherently global property. This is demonstrated by the hardness of computation or approximation of this invariant as well as by the existence of graphs with arbitrarily high chromatic number and no short cycles. The investigation of these graphs had a profound impact on Graph Theory and Combinatorics. It combines
combinatorial, probabilistic, algebraic and topological techniques with number theoretic tools. I will describe the rich history of the subject focusing on some recent results.

Poster here
Video here



Askwith Hall

Jennifer Chayes


Title: Network Science: From the Online World to Cancer Genomics

Abstract: Everywhere we turn these days, we find that networks can be used to describe relevant interactions. In the high tech world, we see the Internet, the World Wide Web, mobile phone networks, and a variety of online social networks. In economics, we are increasingly experiencing both the positive and negative effects of a global networked economy. In epidemiology, we find disease spreading over our ever growing social networks, complicated by mutation of the disease agents. In biomedical research, we are beginning to understand the structure of gene regulatory networks, with the prospect of using this understanding to manage many human diseases. In this talk, I look quite generally at some of the models we are using to describe these networks, processes we are studying on the networks, algorithms we have devised for the networks, and finally, methods we are developing to indirectly infer network structure from measured data. I’ll discuss in some detail particular applications to cancer genomics, applying network algorithms to suggest possible drug targets for certain kinds of cancer.

Poster here
Video here



Askwith Hall

Jacob Fox


Title: Arithmetic patterns, games, and the quest for fast algorithms

Abstract: In this talk, I will discuss recent advances on three seemingly disparate questions and how they relate to each other.

1. What patterns can we find in prime numbers?
2. How many cards do we need in the popular card game SET® to guarantee a valid set?
3. Can we find faster algorithms to better analyze large networks?

Finding patterns like arithmetic progressions in prime numbers has fascinated mathematicians for many centuries. More recently, people have enjoyed playing the card game SET®, and natural questions that arise from this game have been shown to be closely related to longstanding open problems in mathematics and computer science. Over the last few decades, as we strive to better understand the world through large networks, analyzing enormous data sets has become a priority. Traditional algorithms are insufficient for these purposes, and the need for faster algorithms has become apparent.

Advances (some quite surprising) on these questions have used tools from a variety of areas of mathematics, including combinatorics, analysis, algebra, probability, geometry, and number theory. No prior knowledge is assumed.

Poster here
Video here


03-20-18 Dan Spielman


Title: The Laplacian Matrices of Graphs: Algorithms and Applications

Abstract: The Laplacian matrices of graphs arise in many fields, including Machine Learning, Computer Vision, Optimization, Computational Science, and of course Network Analysis. We will explain what these matrices are and why they appear in so many applications.

We then survey recent ideas that allow us to solve systems of linear equations in Laplacian matrices in nearly linear time, emphasizing the utility of graph sparsification—the approximation of a graph by a sparser one—and a recent algorithm of Kyng and Sachdeva that uses random sampling to accelerate Gaussian Elimination.

Poster here