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 applications 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 tool in the area. The course will also cover more recent deterministic algorithms based on correlation decay and geometry of polynomials. The class is open to graduate students and exceptionally well-prepared undergraduates (with the permission of the instructor). Prerequisites include a solid background in algorithms and complexity theory and appropriate mathematical sophistication. Lectures will be in person only, supplemented by notes provided by the instructor and/or scribe notes written by students. Assessment will be via some combination of classroom participation, homeworks, scribe notes and a final project, depending on the composition of the class.

*Prerequisites include a solid background in algorithms
and complexity theory and appropriate mathematical sophistication.

*No time conflicts

Requisites

• Graduate students NOT in the Master of Engineering Program other those in EECS

Repeat Rules