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:47:37

Approximately Counting Graph Homomorphisms

Leslie Ann Goldberg, University of Oxford
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/leslie-ann-goldberg-2016-03-28
Visit talk page
0:46:31

Spin Systems: Hardness of Approximate Counting via Phase Transitions

Andreas Galanis, University of Oxford
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/andreas-galanis-2016-03-28
Visit talk page
0:42:54

Approximating 2-State Spin Systems

Heng Guo, Queen Mary, University of London
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/heng-guo-2016-03-28
Visit talk page
0:45:8

Counting in Sparse Classes of Structures

Jaroslav Nesetril, Charles University
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/jaroslav-nesetril-2016-02-28
Visit talk page
0:30:56

Fine-Grained Complexity Classification of Counting Problems

Holger Dell, Universität des Saarlandes
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/holger-dell-2016-03-28
Visit talk page
0:48:16

On the Power of Holographic Algorithms with Matchgates

Jin-Yi Cai, University of Wisconsin-Madison
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/jin-yi-cai-2016-03-29
Visit talk page
0:44:44

Basis Collapse for Holographic Algorithms Over all Domain Sizes

Sitan Chen, Harvard University
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/sitan-chen-2016-03-29
Visit talk page
0:49:22

Approximation Algorithms for Partition Functions of Edge-Coloring Models

Guus Regts, University of Ansterdam
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/guus0regts-2016-03-29
Visit talk page
0:39:35

Path Coupling, Metrics, and Sampling Problems in Graphs and Hypergraphs

Martin Dyer, University of Leeds
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/martin-dyer-2016-03-29
Visit talk page
0:45:8

Counting Matrix Partitions of Graphs

David Richerby, University of Oxford
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/david-richerby-2016-03-29
Visit talk page