3 citations · 4 across the 12 of their papers we have counts for
14 papers
Potential Hessian Ascent IV: Sampling the Sherrington-Kirkpatrick model at
Holden Lee, Juspreet Singh Sandhu, Jonathan Shi
We give a polynomial-time algorithm to sample from the Gibbs measure of the Sherrington-Kirkpatrick (SK) model with error in total-variation distance (TVD) at any inverse-…
On overlap concentration in the Curie-Weiss Random Field model
Yutong Li, Juspreet Singh Sandhu, Jonathan Shi
We show that the overlaps of two independent replicas drawn from the Gibbs measure of the Curie--Weiss model with random field (CWRF) exhibit sub-Gaussian tails when the inverse te…
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…
Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians
Zackary Jorquera, Alexandra Kolla, Steven Kordonowy +2
We prove new monogamy of entanglement bounds for two-local qudit Hamiltonians of rank-one projectors without one-local terms. In particular, we certify the maximum energy in terms…
Potential Hessian Ascent: The Sherrington-Kirkpatrick Model
David Jekel, Juspreet Singh Sandhu, Jonathan Shi
We present the first iterative spectral algorithm to find near-optimal solutions for a random quadratic objective over the discrete hypercube, resolving a conjecture of Subag [Suba…
Sum-of-Squares & Gaussian Processes I: Certification
Juspreet Singh Sandhu, Jonathan Shi
We introduce a class of distributions which may be considered as a smoothed probabilistic version of the ultrametric property that famously characterizes the Gibbs distributions of…
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu +1
We study random constraint satisfaction problems (CSPs) in the unsatisfiable regime. We relate the structure of near-optimal solutions for any Max-CSP to that for an associated spi…
Efficient Quantum Voting with Information-Theoretic Security
Emil T. Khabiboulline, Juspreet Singh Sandhu, Marco Ugo Gambetta +2
Ensuring security and integrity of elections constitutes an important challenge with wide-ranging societal implications. Classically, security guarantees can be ensured based on co…
Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond
Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu +1
We introduce a notion of \emph{generic local algorithm} which strictly generalizes existing frameworks of local algorithms such as \emph{factors of i.i.d.} by capturing local \emph…
A General Framework for Analyzing Stochastic Dynamics in Learning Algorithms
Chi-Ning Chou, Juspreet Singh Sandhu, Mien Brabeeba Wang +1
One of the challenges in analyzing learning algorithms is the circular entanglement between the objective value and the stochastic noise. This is also known as the "chicken and egg…