8 papers
Random independent sets and local sparsity
Ewan Davies
We analyze random constructions of independent sets in locally sparse graphs, specifically graphs with bounded maximum average degree in neighborhoods or with fractionally -colo…
First-order phase transitions in the hard-core model
Ewan Davies, Juspreet Singh Sandhu, Brian Tan
We give a rigorous proof that the hard-core model on a natural family of infinite graphs exhibits a first-order phase transition.
Weak Poincaré Inequalities via Approximate Stochastic Localization: Application to Sampling the Sherrington-Kirkpatrick Model
Ewan Davies, Holden Lee, Juspreet Singh Sandhu +1
We develop a new method for proving a weak functional inequality by first proving it for a sufficiently regular sequence of distributions approximating the stochastic localization…
Potential Hessian Ascent III: Sampling the Sherrington--Kirkpatrick Model at Beta < 1/2
Ewan Davies, Holden Lee, Juspreet Singh Sandhu +1
We give a polynomial-time algorithm to sample from the Gibbs measure of the Sherrington-Kirkpatrick model with negligible total-variation distance (TVD) error up to inverse tempera…
Degree-sequence bounds for independent sets via multivariate local occupancy
Ewan Davies, Juspreet Singh Sandhu, Jaehyeon Seo +1
We present new degree-sequence lower bounds on the expected size of an independent set from the hard-core model. For arbitrary graphs, we establish a multivariate lower bound inspi…
Safety Analysis in the NGAC Model
Brian Tan, Ewan S. D. Davies, Indrakshi Ray +1
We study the safety problem for the next-generation access control (NGAC) model. We show that under mild assumptions it is coNP-complete, and under further realistic assumptions we…
On expectations and variances in the hard-core model on bounded degree graphs
Ewan Davies, Juspreet Singh Sandhu, Brian Tan
We extend the study of the occupancy fraction of the hard-core model in two novel directions. One direction gives a tight lower bound in terms of individual vertex degrees, extendi…
On the occupancy fraction of the antiferromagnetic Ising model
Ewan Davies, Olivia LeBlanc
We study the maximum and minimum occupancy fraction of the antiferromagnetic Ising model in regular graphs. The minimizing problem is known to determine a computational threshold i…