The Classification Program of Counting Complexity

Mar. 28 – Apr. 1, 2016

Click on the titles of individual talks for abstract, slides and archived video.

All events take place in the Calvin Lab Auditorium.

If you are tweeting about the workshop, please use the designated hashtag to enable other participants to follow the discussions online. The hashtag for this workshop is #sicpcc.

Monday, March 28th, 2016
9:00 am – 9:20 am		Coffee & Check-In
9:20 am – 9:30 am		Opening Remarks
9:30 am – 10:15 am		Approximately Counting Graph Homomorphisms Leslie Ann Goldberg, University of Oxford
10:30 am – 11:15 am		Spin Systems: Hardness of Approximate Counting via Phase Transitions Andreas Galanis, University of Oxford
11:15 am – 11:45 am		Break
11:45 am – 12:30 pm		Approximating 2-State Spin Systems Heng Guo, Queen Mary, University of London
12:30 pm – 2:00 pm		Lunch
2:00 pm – 2:45 pm		Counting in Sparse Classes of Structures Jaroslav Nesetril, Charles University
2:45 pm – 3:15 pm		Fine-Grained Complexity Classification of Counting Problems Holger Dell, Universität des Saarlandes
3:30 pm – 4:00 pm		Light Refreshments (Banatao Auditorium, Sutardja Dai Hall)
4:00 pm – 5:00 pm		Simons Institute Open Lecture: The Complexity of Computing Quantities Leslie Valiant, Harvard University

Tuesday, March 29th, 2016
9:00 am – 9:30 am		Coffee & Check-In
9:30 am – 10:15 am		On the Power of Holographic Algorithms with Matchgates Jin-Yi Cai, The University of Wisconsin
10:30 am – 11:15 am		Basis Collapse for Holographic Algorithms Over all Domain Sizes Sitan Chen, Harvard University
11:15 am – 11:45 am		Break
11:45 am – 12:30 pm		Approximation Algorithms for Partition Functions of Edge-Coloring Models Guus Regts, University of Amsterdam
12:30 pm – 2:00 pm		Lunch
2:00 pm – 2:45 pm		Path Coupling, Metrics, and Sampling Problems in Graphs and Hypergraphs Martin Dyer, University of Leeds
3:00 pm – 3:45 pm		Counting Matrix Partitions of Graphs David Richerby, University of Oxford
3:45 pm – 4:15 pm		Break
4:15 pm – 5:00 pm		How to Not Prove Two Important Theorems Richard Lipton, Georgia Institute of Technology
5:00 pm – 6:00 pm		Reception

Wednesday, March 30th, 2016
9:00 am – 9:30 am		Coffee & Check-In
9:30 am – 10:15 am		The Computational Complexity of Counting List H-Colourings, and Related Problems Mark Jerrum, Queen Mary, University of London
10:30 am – 11:15 am		Towards Understanding the Complexity of the Ising Partition Function Martin Loebl, Charles University
11:15 am – 11:45 am		Break
11:45 am – 12:30 pm		The Complexity of Computing Averages Piyush Srivastava, California Institute of Technology
12:30 pm – 2:00 pm		Lunch
2:00 pm – 2:45 pm		The Complexity of Approximating Small Degree Boolean #CSP Pinyan Lu, Shanghai University of Finance and Economics
3:00 pm – 3:45 pm		Canonical Paths for MCMC: From Art to Science Chihao Zhang, Shanghai Jiao Tong University
3:45 pm – 4:15 pm		Break
4:15 pm – 5:00 pm		Dichotomies for Counting Subgraphs Radu Curticapean, Saarland University

Thursday, March 31st, 2016
9:00 am – 9:30 am		Coffee & Check-In
9:30 am – 10:15 am		Counting Approximation Complexity Classification Through Clones and Invariants Andrei Bulatov , Simon Fraser University
10:30 am – 11:15 am		Enumerator Polynomials: Completeness and Intermediate Complexity Meena Mahajan, Institute of Mathematical Sciences
11:15 am – 11:45 am		Break
11:45 am – 12:30 pm		Dichotomy Theorems for Generalized Chromatic Polynomials Johann Makowsky, Technion Israel Institute of Technology
12:30 pm – 2:00 pm		Lunch
2:00 pm – 2:45 pm		Geometric Perspectives on Problems in Complexity Theory J.M. Landsberg, Texas A&M University
3:00 pm – 3:45 pm		Categories, Representations, and Counting Complexity Jason Morton, Pennsylvania State University
3:45 pm – 4:15 pm		Break
4:15 pm – 5:00 pm		Hilbert's Nullstellensatz Certificates of Infeasibility for Combinatorial Problems Susan Margulies, United States Naval Academy

Friday, April 1st, 2016
9:00 am – 9:30 am		Coffee & Check-In
9:30 am – 10:15 am		Finding a Large Submatrix of a Random Matrix, and the Overlap Gap Property David Gamarnik, Massachusetts Institute of Technology
10:30 am – 11:15 am		LP Relaxations for Valued CSPs Stanislav Zivny, University of Oxford
11:15 am – 11:45 am		Break
11:45 am – 12:30 pm		Counting with Bounded Treewidth Yitong Yin, Nanjing University