Topics will vary from semester to semester. See Computer Science Division announcements.

Partition functions are a class of polynomials with combinatorial coefficients that count weighted combinatorial structures. Originally introduced in statistical physics, they have more recently found widespread application in combinatorics, theoretical computer science, statistics and machine learning, and have become a vibrant research area in their own right. This course will cover algorithmic and complexity theoretic aspects of partition functions, as well as their connections to physical and combinatorial phase transitions. A large portion of the class will be devoted to the Markov chain Monte Carlo method, which remains the most widely applicable algorithmic paradigm in the area and has recently seen a new surge of activity through the development of analytical tools such as spectral independence. The course will also cover deterministic algorithms based on correlation decay and geometry of polynomials.

* Time conflicts NOT allowed.

Requisites

• Students not in the Master of Engineering Program

Repeat Rules