The Classification Program of Counting Complexity
2016-03-28..2016-04-01
Berkeley, United States
[Approximate Counting, Markov Chains and Phase Transitions, Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms, Interactive Complexity 2018, Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019), Connections Between Algorithm Design and Complexity Theory, Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015)]
| title | author | length |
|---|---|---|
| Approximately Counting Graph Homomorphisms | Leslie Ann Goldberg | 48m |
Fixing any nontrivial template H, approximately counting H‑colorings is never easier than approximately counting independent sets in bipartite graphs: the… | ||
| Spin Systems: Hardness of Approximate Counting via Phase Transitions | Andreas Galanis | 47m |
Andreas Galanis, University of Oxford
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/andreas-galanis-2016-03-28 | ||
| Approximating 2-State Spin Systems | Heng Guo | 43m |
Survey of which 2‑state spin parameters are approximable versus hard with concrete claims and tools For antiferromagnetic cases there is a near‑complete… | ||
| Counting in Sparse Classes of Structures | Jaroslav Nesetril | 45m |
Jaroslav Nesetril, Charles University
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/jaroslav-nesetril-2016-02-28 | ||
| Fine-Grained Complexity Classification of Counting Problems | Holger Dell | 31m |
Fine-grained classification ties concrete running times to counting problems: CNF counting resists sub- (1+δ)^n algorithms under SETH/ETH, with examples like… | ||
| On the Power of Holographic Algorithms with Matchgates | Jin-Yi Cai | 48m |
Classifies every Boolean complex-weighted counting CSP into exactly three cases: polynomial-time for all graphs, #P-hard on general graphs but polynomial-time… | ||
| Basis Collapse for Holographic Algorithms Over all Domain Sizes | Sitan Chen | 45m |
Proves a collapse: for domain size K any holographic algorithm that uses a full‑rank matchgate can be simulated with basis size l = floor(log2 K). Proof uses… | ||
| Approximation Algorithms for Partition Functions of Edge-Coloring Models | Guus Regts | 49m |
Guus Regts, University of Ansterdam
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/guus0regts-2016-03-29 | ||
| Path Coupling, Metrics, and Sampling Problems in Graphs and Hypergraphs | Martin Dyer | 40m |
Uses path coupling with a custom metric chosen by solving a linear program metric to prove rapid mixing of the independent set Markov chain on hypergraphs… | ||
| Counting Matrix Partitions of Graphs | David Richerby | 45m |
Proves a precise dichotomy: for any fixed symmetric 0/1/ matrix M, counting list M‑partitions is either polynomial‑time computable or #P‑complete, decided by… | ||
| How to Not Prove Two Important Theorems | Richard Lipton | 42m |
Proposes an approach that amplifies a small-error 3‑edge‑coloring into a full counterexample and proves a reduction showing that an algorithm that colors… | ||
| The Computational Complexity of Counting List H-Colourings, and Related Problems | Mark Jerrum | 47m |
Gives a concrete trichotomy for approximating list H‑colourings: if every component of H is trivial it is in FP; if H is an irreflexive bipartite permutation… | ||
| Towards Understanding the Complexity of the Ising Partition Function | Martin Loebl | 46m |
Study links Ising partition function (even-subgraph generating function) to topology and shows a concrete 4^g lower bound on the number of Pfaffian terms… | ||
| The Complexity of Computing Averages | Piyush Srivastava | 43m |
Computing exact averages — mean magnetization and mean energy for the Ising model, plus average sizes of matchings and independent sets — is #P-hard under the… | ||
| The Complexity of Approximating Small Degree Boolean #CSP | Pinyan Lu | 34m |
Pinyan Lu, Shanghai University of Finance and Economics
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/pinyan-lu-2016-03-30 | ||
| Canonical Paths for MCMC: From Art to Science | Chihao Zhang | 40m |
Presents a concrete criterion that turns the canonical-paths trick into an algorithmic test: symmetric (Hamming-weight) constraints are windable exactly when a… | ||
| Dichotomies for Counting Subgraphs | Radu-Cristian Curticapean | 46m |
Classifies when counting copies of H in G is fixed-parameter tractable: if the class C has bounded matching size (equivalently bounded vertex-cover) the… | ||
| Counting Approximation Complexity Classification Through Clones and Invariants | Andrei Bulatov | 47m |
Classifies approximation complexity of counting CSPs by the closure of constraint sets under gadget constructions and limits, using gadget reductions, Fourier… | ||
| Enumerator Polynomials: Completeness and Intermediate Complexity | Meena Mahajan | 48m |
Defines “enumerator” polynomials that sum monomials encoding combinatorial objects, gives five concrete families (cliques, Hamilton cycles, perfect matchings… | ||
| Dichotomy Theorems for Generalized Chromatic Polynomials | Johann Makowsky | 47m |
Johann Makowsky, Technion Israel Institute of Technology
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/johann-makowsky-201… | ||
| Geometric Perspectives on Problems in Complexity Theory | J.M. Landsberg | 47m |
Shows that huge row/column pairings built from vectors of minors or sub‑Pfaffians reduce to a single M×M determinant/Pfaffian, with polynomial tests for… | ||
| Categories, Representations, and Counting Complexity | Jason Morton | 44m |
Jason Morton, Pennsylvania State University
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/jason-morton-2016-03-31 | ||
| Hilbert's Nullstellensatz Certificates of Infeasibility for Combinatorial Problems | Susan Marguiles | 39m |
Models NP problems as polynomial systems and uses Hilbert's Nullstellensatz to produce infeasibility certificates; for independent set the minimum certificate… | ||
| Finding a Large Submatrix of a Random Matrix, and the Overlap Gap Property | Davin Gamarnik | 45m |
Random n×n Gaussian matrix has an explicit asymptotic optimum for the largest k×k submatrix average given by a tail/extreme-value moment calculation; naive… | ||
| LP Relaxations for Valued CSPs | Stanislav Zivny | 41m |
Gives an exact algebraic characterization of when linear-program relaxations solve valued CSPs: the basic LP (BLP) or a bounded Sherali–Adams level is tight… | ||
| Counting with Bounded Treewidth | Yitong Yin | 41m |
Claim: for Holant instances defined by symmetric signatures whose pinning profiles have at most R distinct outcomes the partition function is computable by a… | ||
| nothing matches | ||