☆ 4.3 Article

Absence of zeros implies strong spatial mixing

PROBABILITY THEORY AND RELATED FIELDS (2023)

相关参考文献

注意：仅列出部分参考文献，下载原文获取全部文献信息。

Article Computer Science, Software Engineering

Correlation decay and the absence of zeros property of partition functions

David Gamarnik

Summary: The absence of (complex) zeros property is the core of Barvinok's interpolation method, which is used to design deterministic approximation algorithms for graph counting and related problems. The author establishes the relationship between this property and the correlation decay property, and proves it using a certain graph polynomial representation. The conjecture that this result holds for all graphs has recently been confirmed by Regts.

RANDOM STRUCTURES & ALGORITHMS (2023)

添加到收藏夹

Article Computer Science, Theory & Methods

Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions

Jingcheng Liu et al.

SIAM JOURNAL ON COMPUTING (2022)

添加到收藏夹

Proceedings Paper Computer Science, Theory & Methods

Approximate Counting and Sampling via Local Central Limit Theorems

Vishesh Jain et al.

Summary: The paper presents an FPTAS for computing the number of matchings and independent sets in a graph G with maximum degree Delta, based on exploiting the local central limit theorems. It also proposes quasi-linear time randomized algorithms for sampling from the uniform distribution on matchings and independent sets.

PROCEEDINGS OF THE 54TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '22) (2022)

添加到收藏夹

Proceedings Paper Computer Science, Theory & Methods

Spectral Independence via Stability and Applications to Holant-Type Problems

Zongchen Chen et al.

Summary: This paper explores the connection between stability of polynomials and convergence rates of Markov Chain Monte Carlo (MCMC) algorithms. The authors prove the spectral independence holds at a real point lambda if the partition function is nonzero in the region around lambda. The improved running time guarantees for Holant-type problems and various other applications are also discussed.

2021 IEEE 62ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2021) (2022)

添加到收藏夹

Article Mathematics, Applied

Some applications of Wagner's weighted subgraph counting polynomial

Ferenc Bencs et al.

Summary: Researchers used Wagner's weighted subgraph counting polynomial to prove the real rootedness of the partition function of the anti-ferromagnetic Ising model on line graphs, as well as to show that the absolute value of roots of the edge cover polynomial is at most 4. Furthermore, they demonstrated that the absolute value of roots of the edge cover polynomial of a k-uniform hypergraph is at most 2(k), and discussed applications of this to the roots of domination polynomials of graphs. They also discussed the relationship between these results and efficient algorithms for approximating evaluations of these polynomials.

ELECTRONIC JOURNAL OF COMBINATORICS (2021)

添加到收藏夹

Article Physics, Mathematical

Contraction: A Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems

Shuai Shao et al.

Summary: This study explores the connection between correlation decay property and the zero-freeness of the partition function of 2-spin systems on graphs of bounded degree. The research shows that the contraction property for certain real parameters implies zero-freeness of the partition function and correlation decay for corresponding complex neighborhoods. By extending real parameters to complex neighborhoods, new zero-free regions are identified where correlation decay exists, leading to approximation algorithms for computing the partition function of 2-spin systems on graphs of bounded degree under complex parameter settings.

JOURNAL OF STATISTICAL PHYSICS (2021)

添加到收藏夹

Proceedings Paper Computer Science, Theory & Methods

Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More

Yeganeh Alimohammadi et al.

Summary: This study presents a fully polynomial time randomized approximation scheme for counting matchings in planar graphs and discusses methods for sampling and counting monomer-dimer systems. The research shows that multi-site Glauber dynamics can efficiently mix on specific graph families, providing a new tool for establishing spectral independence based on polynomial geometry. This work also demonstrates the concept of fractional log-concavity in avoiding roots of polynomials in a complex plane sector.

STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (2021)

添加到收藏夹

Article Statistics & Probability

Algorithmic Pirogov-Sinai theory

Tyler Helmuth et al.

PROBABILITY THEORY AND RELATED FIELDS (2020)

添加到收藏夹

Article Mathematics

Cayley Trees do Not Determine the Maximal Zero-Free Locus of the Independence Polynomial

Pjotr Buys

MICHIGAN MATHEMATICAL JOURNAL (2020)

添加到收藏夹

Article Computer Science, Theory & Methods

INAPPROXIMABILITY OF THE INDEPENDENT SET POLYNOMIAL IN THE COMPLEX PLANE

Ivona Bezakova et al.

SIAM JOURNAL ON COMPUTING (2020)

添加到收藏夹

Article Physics, Mathematical

Fisher zeros and correlation decay in the Ising model

Jingcheng Liu et al.

JOURNAL OF MATHEMATICAL PHYSICS (2019)

添加到收藏夹

Article Mathematics

Central limit theorems from the roots of probability generating functions

Marcus Michelen et al.

ADVANCES IN MATHEMATICS (2019)

添加到收藏夹

Article Mathematics

On a Conjecture of Sokal Concerning Roots of the Independence Polynomial

Han Peters et al.

MICHIGAN MATHEMATICAL JOURNAL (2019)

添加到收藏夹

Article Computer Science, Theory & Methods

Christoffel-Darboux Type Identities for the Independence Polynomial

Ferenc Bencs

COMBINATORICS PROBABILITY & COMPUTING (2018)

添加到收藏夹

Article Mathematics

COMPUTING THE PARTITION FUNCTION FOR GRAPH HOMOMORPHISMS

Alexander Barvinok et al.

COMBINATORICA (2017)

添加到收藏夹

Article Computer Science, Theory & Methods

DETERMINISTIC POLYNOMIAL-TIME APPROXIMATION ALGORITHMS FOR PARTITION FUNCTIONS AND GRAPH POLYNOMIALS

Viresh Patel et al.

SIAM JOURNAL ON COMPUTING (2017)

添加到收藏夹

Article Mathematics

Central limit theorems, Lee-Yang zeros, and graph-counting polynomials

J. L. Lebowitz et al.

JOURNAL OF COMBINATORIAL THEORY SERIES A (2016)

添加到收藏夹

Article Computer Science, Software Engineering

Left and right convergence of graphs with bounded degree

Christian Borgs et al.

RANDOM STRUCTURES & ALGORITHMS (2013)

添加到收藏夹

Article Mathematics

The roots of the independence polynomial of a clawfree graph

Maria Chudnovsky et al.

JOURNAL OF COMBINATORIAL THEORY SERIES B (2007)

添加到收藏夹

Proceedings Paper Computer Science, Theory & Methods

Simple Deterministic Approximation Algorithms for Counting Matchings

Mohsen Bayati et al.

STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING (2007)

添加到收藏夹

Review Physics, Mathematical

The repulsive lattice gas, the independent-set polynomial, and the Lovasz local lemma

AD Scott et al.

JOURNAL OF STATISTICAL PHYSICS (2005)

添加到收藏夹

Review Computer Science, Theory & Methods

Bounds on the complex zeros of (Di)Chromatic polynomials and Potts-model partition functions

AD Sokal

COMBINATORICS PROBABILITY & COMPUTING (2001)

添加到收藏夹

© Peeref 2019-2024. All rights reserved.