Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019)
2019-03-18..2019-03-22
Berkeley, United States
Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop ) ·
[Approximate Counting, Markov Chains and Phase Transitions, Functional Inequalities in Discrete Spaces with Applications 2013, The Classification Program of Counting Complexity, Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017), Neo-Classical Methods in Discrete Analysis 2013, Computational Phase Transitions (Simons Institute, 2020)]
| title | author | length |
|---|---|---|
| Reflection Positivity as Complement to the Location of Zeros of Partition Functions | Elliott Lieb | 57m |
Reflection positivity is presented as a concrete tool that produces periodic minimizers and an exponential bound e^{-a n} on the probability that any chosen… | ||
| Computation of the Multivariate Independence Polynomial by Correlation Decay | Jan Vondrák | 50m |
Gives a deterministic algorithm that approximates the multivariate independence polynomial whenever the evaluation point stays a definite distance from the… | ||
| Inapproximability of the Independent Set Polynomial in the Complex Plane | Ivona Bezáková | 54m |
Shows Sharp-P hardness of approximating the independent-set polynomial (partition function) outside the cardioid region: approximating its norm or angle is… | ||
| Deterministic Approximation of the Ising Partition Function | Piyush Srivastava | 51m |
Proves deterministic approximation by combining Liang/Lee–Yang zeros on the unit circle with Barvinok-style Taylor expansion and the Barvinok +… | ||
| The Six- and the Eight-vertex Models and Counting Perfect Matchings | Tianyu Liu | 42m |
Gives an FPRAS claim: a directed-loop Markov chain rapidly mixes when Z2/Z0 is polynomially bounded, yielding an FPS in disordered region for many six- and… | ||
| Zeros for Partition Functions and Graph-counting Polynomials. | David Ruelle | 47m |
Extends Asano’s lemma to multi-affine polynomials and uses repeated Asano contraction of vertex polynomials to produce edge-variable subgraph-counting… | ||
| Counting Degree-constrained Subgraphs and Orientations | Péter Csikvári | 43m |
Péter Csikvári (Eötvös Loránd University)
https://simons.berkeley.edu/talks/talk-32
Deterministic Counting, Probability, and Zeros of Partition Functions | ||
| Approximating the Permanent of a Random Matrix with Vanishing Mean | Saeed Mehraban | 46m |
Shows that exact permanent remains #P-hard on average for Gaussian matrices with vanishing mean, but approximation becomes quasi-polynomial time once the mean… | ||
| Entropy, Capacity, and Counting | Nisheeth Vishnoi | 56m |
Generalizes Gurvits' capacity to compute sums of polynomial coefficients over a polytope and gives a concrete algorithmic claim: with an oracle to evaluate the… | ||
| Counting Matchings via the Capacity Method | Jonathan Leake | 54m |
Gives an explicit analytic route to lower-bound matchings: proves Gurvits-style capacity inequalities that reproduce Schrijver’s lower bound for perfect… | ||
| Zeros of Moment Generating Functions and the Riemann Hypothesis | Chuck Newman | 59m |
Defines the Riemann hypothesis as the statement that the Laplace transform of a specific even positive rapidly decaying Phi has all zeros on the imaginary… | ||
| Approximating the Matching Polynomial | Leslie Ann Goldberg | 48m |
Gives a deterministic algorithmic boundary: positive real weights admit the classical Markov-chain FPRAS, bounded-degree graphs admit a deterministic… | ||
| Approximate Deterministic Counting via Marginal Entropy Optimization | Nima Anari | 51m |
Deterministic algorithm maximizes the sum of marginal entropies over the matroid base polytope via convex optimization (using a separation oracle) and… | ||
| Zeros of the Partition Function of the Ising Model on Bounded Degree Graphs | Guus Regts | 49m |
Proves explicit zero-free interval on the unit circle for the ferromagnetic Ising partition function on bounded-degree graphs by analyzing tree recursions via… | ||
| A Poly-time Deterministic Algorithm for Simply Exponential Approximation... | Leonid Gurvits | 53m |
Leonid Gurvits (City University of New York)
https://simons.berkeley.edu/talks/talk-50
Deterministic Counting, Probability, and Zeros of Partition Functions | ||
| Abstract Polymer Models and the Cluster Expansion | Will Perkins | 44m |
Gives an FPTAS and efficient sampler for the ferromagnetic Q‑state Potts partition function on max‑degree Δ, α‑expander graphs when β ≥ C·(log(QΔ))/α (C… | ||
| Counting Independent Sets and Colorings on Almost Every Random Regular Bipartite Graph | Pinyan Lu | 38m |
Shows a deterministic FPTAS for counting independent sets and q‑colorings on almost every random Δ‑regular bipartite graph when Δ is sufficiently large (Δ is a… | ||
| Algorithmic Pirogov-Sinai Theory | Tyler Helmuth | 44m |
Paper proves a deterministic FPTAS for the hard‑core partition function and sampling on large finite subsets of Z^d at sufficiently high density (lambda above… | ||
| Finding Eigenvalues in Exponential Size Space:... | Zeph Landau | 55m |
An algorithm finds a principal eigenvalue and eigenvector of an exponentially large local Hamiltonian under the promise the target has a succinct description… | ||
| Gauges, Loops, and Polynomials for Partition Functions of Graphical Models | Michael Chertkov | 45m |
Michael Chertkov (University of Arizona, Tucson)
https://simons.berkeley.edu/talks/talk-48
Deterministic Counting, Probability, and Zeros of Partition Functions | ||
| Negative Dependence and Lorentzian Polynomials | Petter Brändén | 54m |
Claims that the random cluster / q‑state Potts partition function is Lorentzian for q ≤ 1, proves the support is a matroid/poly‑matroid and reduces many checks… | ||
| Counting Hypergraph Colorings in the Local Lemma Regime | Heng Guo | 43m |
Deterministic algorithm gives a polynomial-time deterministic approximation scheme for counting q-colorings of k-uniform hypergraphs in a Local Lemma regime… | ||
| Christoffel-Darboux Type Identities for the Independence Polynomial | Ferenc Bencs | 35m |
A new Christoffel-Darboux type identity expresses differences like I(G−u)I(G−v)−I(G)I(G−{u,v}) as a signed sum over connected induced bipartite subgraphs, with… | ||
| A Combinatorial Approach to Complexity Transitions in Quantum Physics | Ryan Mann | 36m |
Deterministic polynomial time algorithms approximate Ising partition functions on graphs of maximum degree Δ when interactions and small external fields lie… | ||
| nothing matches | ||