Counting Approximation Complexity Classification Through Clones and Invariants

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


Duration: 47:20
276 views
1

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



Other Videos By Simons Institute for the Theory of Computing


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-04Counting Matrix Partitions of Graphs
2016-04-04How to Not Prove Two Important Theorems
2016-04-04The Computational Complexity of Counting List H-Colourings, and Related Problems
2016-04-04The Complexity of Computing Averages
2016-04-04Path Coupling, Metrics, and Sampling Problems in Graphs and Hypergraphs
2016-04-04Towards Understanding the Complexity of the Ising Partition Function
2016-04-04Approximation Algorithms for Partition Functions of Edge-Coloring Models
2016-04-04Counting Approximation Complexity Classification Through Clones and Invariants
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
2016-04-04Categories, Representations, and Counting Complexity
2016-04-04Counting with Bounded Treewidth
2016-03-29The Complexity of Computing Quantities
2016-03-22Decoding the Human Microbiome
2016-03-21Threshold Phenomena in Combinatorics
2016-03-11Discovery of Transcription Factor Binding Motifs from Large Sequence Sets
2016-03-11Algorithms for Single Cell RNAseq Analysis


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