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

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=WASbpJ8uTyI


Duration: 47:02
204 views
1

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



Other Videos By Simons Institute for the Theory of Computing


2016-04-15Spatial Gene Expression Patterns in Drosophila
2016-04-15Moving Beyond Local Patterns: New Ways to Reason about Biological Network Comparisons
2016-04-15Mapping the Online World: Social Connectedness in the Digital Age
2016-04-04Spin Systems: Hardness of Approximate Counting via Phase Transitions
2016-04-04Approximately Counting Graph Homomorphisms
2016-04-04On the Power of Holographic Algorithms with Matchgates
2016-04-04Approximating 2-State Spin Systems
2016-04-04Counting in Sparse Classes of Structures
2016-04-04Basis Collapse for Holographic Algorithms Over all Domain Sizes
2016-04-04Fine-Grained Complexity Classification of Counting Problems
2016-04-04The Computational Complexity of Counting List H-Colourings, and Related Problems
2016-04-04Geometric Perspectives on Problems in Complexity Theory
2016-04-04The Complexity of Approximating Small Degree Boolean #CSP
2016-04-04Dichotomies for Counting Subgraphs
2016-04-04Counting Approximation Complexity Classification Through Clones and Invariants
2016-04-04Dichotomy Theorems for Generalized Chromatic Polynomials
2016-04-04Canonical Paths for MCMC: From Art to Science
2016-04-04Enumerator Polynomials: Completeness and Intermediate Complexity
2016-04-04Hilbert's Nullstellensatz Certificates of Infeasibility for Combinatorial Problems
2016-04-04Finding a Large Submatrix of a Random Matrix, and the Overlap Gap Property
2016-04-04LP Relaxations for Valued CSPs


Tags:
Simons Institute
UC Berkeley
computer science
theory of computing
Counting Complexity and Phase Transitions
Mark Jerrum