Cover Image

On the complex zeros and the computational complexity of approximating the reliability polynomial

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bencs, Ferenc, Piombi, Chiara, Regts, Guus
Format:	Preprint
Published:	2025
Subjects:	Combinatorics Computational Complexity Discrete Mathematics 5C31 primary, 82B20, 68W25 secondary
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
by: Bencs, Ferenc, et al.
Published: (2025)

On sampling symmetric Gibbs distributions on sparse random graphs and hypergraphs
by: Efthymiou, Charilaos
Published: (2020)

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
by: Bencs, Ferenc, et al.
Published: (2024)

Approximating the volume of a truncated relaxation of the independence polytope
by: Bencs, Ferenc, et al.
Published: (2024)

Barvinok's interpolation method meets Weitz's correlation decay approach
by: Bencs, Ferenc, et al.
Published: (2025)

Near optimal bounds for weak and strong spatial mixing for the anti-ferromagnetic Potts model on trees
by: Bencs, Ferenc, et al.
Published: (2023)

Algorithms for the ferromagnetic Potts model on expanders
by: Carlson, Charlie, et al.
Published: (2022)

Robust Classification of Dynamic Bichromatic point Sets in R2
by: Glazenburg, Erwin, et al.
Published: (2024)

The reflection complexity of sequences over finite alphabets
by: Allouche, Jean-Paul, et al.
Published: (2024)

On sampling two spin models using the local connective constant
by: Efthymiou, Charilaos
Published: (2024)

Zero-free regions of partition functions with applications to algorithms and graph limits
by: Regts, Guus
Published: (2015)

Improved Randomized Approximation of Hard Universality and Emptiness Problems
by: Andreou, Pantelis, et al.
Published: (2024)

Greedy Matchings in Bipartite Graphs with Ordered Vertex Sets
by: Simon, Hans U.
Published: (2024)

On the Parenthesisations of Matrix Chains: All are Useful, Few Are Essential
by: López, Francisco, et al.
Published: (2023)

On Finding Randomly Planted Cliques in Arbitrary Graphs
by: Agrimonti, Francesco, et al.
Published: (2025)

Belief Propagation Guided Decimation on Random k-XORSAT
by: Chatterjee, Arnab, et al.
Published: (2025)

Worst-Case Examples for the Computation of Persistent Homology
by: Çetin, Uzay, et al.
Published: (2026)

The Shift-Dimension of Multipersistence Modules
by: Chachólski, Wojciech, et al.
Published: (2021)

A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
by: Hougardy, Stefan, et al.
Published: (2025)

A dynamical approach to studying the Lee-Yang zeros for the Potts Model on the Cayley Tree
by: Pannipitiya, Diyath, et al.
Published: (2025)

On the zeros of partition functions with multi-spin interactions
by: Barvinok, Alexander
Published: (2024)

Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem
by: Jenssen, Matthew, et al.
Published: (2023)

A study of distributional complexity measures for Boolean functions
by: Köhler-Schindler, Laurin, et al.
Published: (2024)

Symmetric Rule-Based Achlioptas Processes for Random $k$-SAT
by: Chatterjee, Arnab
Published: (2025)

On the irrationality exponent of real numbers with low complexity expansion
by: Bugeaud, Yann, et al.
Published: (2025)

Homomorphism Counts to Trees
by: Dawar, Anuj
Published: (2024)

Multipole Semantic Attention: A Fast Approximation of Softmax Attention for Pretraining
by: Mitchell, Rupert, et al.
Published: (2025)

Induced Disjoint Paths Without an Induced Minor
by: Aboulker, Pierre, et al.
Published: (2025)

Polynomial-Time Algorithms for Black-Box Distributive Expanded Groups
by: Anokhin, Mikhail
Published: (2025)

Conservative Maltsev Constraint Satisfaction Problems
by: Bodirsky, Manuel, et al.
Published: (2025)

A near-optimal zero-free disk for the Ising model
by: Patel, Viresh, et al.
Published: (2023)

Boundary-driven quantum systems near the Zeno limit: steady states and long-time behavior
by: Carlen, Eric A., et al.
Published: (2025)

On the Approximation Ratio of the $k$-Opt and Lin-Kernighan Algorithm
by: Zhong, Xianghui
Published: (2019)

Bigraded Betti numbers and Generalized Persistence Diagrams
by: Kim, Woojin, et al.
Published: (2021)

A universal $\overline\partial$ solution operator on nonsmooth strongly pseudoconvex domains
by: Yao, Liding
Published: (2024)

Chain Tutte polynomials
by: Wakefield, Max
Published: (2023)

The Parity-Constrained Four-Peg Tower of Hanoi Problem and Its Associated Graph
by: Mehiri, El-Mehdi
Published: (2025)

Improved bounds for randomized Schatten norm estimation of numerically low-rank matrices
by: Chu, Ya-Chi, et al.
Published: (2024)

Bounded Distance Decoding for Random Lattices
by: Gao, Shuhong
Published: (2025)

On the complexity of the Maker-Breaker happy vertex game
by: Hilaire, Mathieu, et al.
Published: (2026)