Playlist: 26 videos

The Classification Program of Counting Complexity

Mar. 28 – Apr. 1, 2016

Recent years have seen dramatic progress in counting complexity. In exact computation, we now have a complete classification of counting CSPs into those that are polynomial-time solvable and those that are hard for the...

0:41:31

How to Not Prove Two Important Theorems

Richard Lipton, Georgia Institute of Technology
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/richard-lipton-2016-03-29
Visit talk page
0:47:2

The Computational Complexity of Counting List H-Colourings, and Related Problems

Mark Jerrum, Queen Mary, University of London
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/mark-jerrum-2016-03-30
Visit talk page
0:46:4

Towards Understanding the Complexity of the Ising Partition Function

Martin Loebl, Charles University
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/martin-loebl-2016-03-30
Visit talk page
0:42:32

The Complexity of Computing Averages

Piyush Srivastava, California Institute of Technology
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/piyush-srivastava-2016-03-30
Visit talk page
0:33:59

The Complexity of Approximating Small Degree Boolean #CSP

Pinyan Lu, Shanghai University of Finance and Economics
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/pinyan-lu-2016-03-30
Visit talk page
0:39:41

Canonical Paths for MCMC: From Art to Science

Chihao Zhang, Shanghai Jiao Tong University
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/chihao-zhang-2016-03-30
Visit talk page
0:46:27

Dichotomies for Counting Subgraphs

Radu-Cristian Curticapean, Universität des Saarlandes
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/radu-curticapean-2016-03-30
Visit talk page
0:47:20

Counting Approximation Complexity Classification Through Clones and Invariants

Andrei Bulatov, Simon Fraser University
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/andrei-bulatov-2016-04-31
Visit talk page
0:47:42

Enumerator Polynomials: Completeness and Intermediate Complexity

Meena Mahajan, Institute of Mathematical Sciences
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/meena-mahajan-2016-03-31
Visit talk page
0:46:54

Dichotomy Theorems for Generalized Chromatic Polynomials

Johann Makowsky, Technion Israel Institute of Technology
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/johann-makowsky-2016-03-31
Visit talk page