7 papers
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…
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…
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…