My papers can be found on DBLP or Google Scholar.

I work with Jonathan Shi on obstructing algorithms in the presence of ultrametric OGPs and designing unifying sum-of-squares (SoS) relaxations for spin glasses and random Max-CSPs. Questions and techniques that excite me include the qPCP conjecture, ultrametric OGPs, Guerra-Tonnineli interpolations, small-set expansion/unique-games conjectures and analytic sparsity proofs.

More broadly, my interests lie in the confluence of Convex Optimization, Random Matrix Theory & Free Probability Theory, Mathematical Spin-Glass Theory, Quantum Statistical Mechanics and Max-CSPs.

Publications

Spin-Glass Geometry and Sum-of-Squares I: Spherical Case
Juspreet Singh Sandhu, Jonathan Shi
Submitted, SODA 2024
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, Jonathan Shi
ITCS 2023
PDF
Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond
Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, Jonathan Shi
ICALP 2022
PDF
Efficient Quantum Voting with Information-Theoretic Security
Emil T. Khabiboulline, Juspreet Singh Sandhu, Marco Ugo Gambetta, Mikhail D. Lukin, Johannes Borregaard
Under Revision, PRX Quantum
PDF
A General Framework for Analyzing Stochastic Dynamics in Learning Algorithms
Chi-Ning Chou, Juspreet Singh Sandhu, Mien Brabeeba Wang, Tiancheng Yu
Submitted, JMLR
PDF

Preprints

Stable Algorithms for Sparse Random Max-CSPs
Juspreet Singh Sandhu, Jonathan Shi
In Preparation
Spin-Glass Geometry and Sum-of-Squares II: Ising Case
Juspreet Singh Sandhu, Jonathan Shi
In Preparation
Polynomial Time Sparsification of the Boolean Hypercube
Juspreet Singh Sandhu, Jonathan Shi, Luca Trevisan
In Preparation