9 papers
On the self-intersection time of non-backtracking random walks
Ferenc Bencs, Leslie Ann Goldberg, Matthew Jenssen +4
We study the self-intersection time of the non-backtracking random walk on connected undirected graphs. For every fixed we show that the expected self-intersection time i…
On the complex zeros and the computational complexity of approximating the reliability polynomial
Ferenc Bencs, Chiara Piombi, Guus Regts
In this paper we relate the location of the complex zeros of the reliability polynomial to parameters at which a certain family of rational functions derived from the reliability p…
Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
Ferenc Bencs, Guus Regts
We prove that for any graph the (complex) zeros of its chromatic polynomial, , lie inside the disk centered at of radius , where denotes the ma…
Deterministic approximate counting of colorings with fewer than colors via absence of zeros
Ferenc Bencs, Khallil Berrekkal, Guus Regts
Let be integers. We prove that there exists such that if , then there exists an open set that contains t…
On zeros and algorithms for disordered systems: mean-field spin glasses
Ferenc Bencs, Brice Huang, Daniel Z. Lee +2
Spin glasses are fundamental probability distributions at the core of statistical physics, the theory of average-case computational complexity, and modern high-dimensional statisti…
Barvinok's interpolation method meets Weitz's correlation decay approach
Ferenc Bencs, Guus Regts
In this paper we take inspiration from Weit'z algorithm for approximating the independence polynomial to provide a new algorithm for computing the coefficients of the Taylor series…