All my papers can be found on DBLP or Google Scholar.

I work very closely with Jonathan Shi on obstructing algorithms (such as low-degree polynomials (LDPs), local quantum algorithms and diffusion dynamics) in the presence of ultrametric OGPs, and designing unifying sum-of-squares (SoS) algorithms for optimizing spin glasses and Max-CSPs under fRSB. The motivation for our work is to develop a unified theory of typical-instance complexity for optimization and understand its ramifications on quantum advantage, the small-set expansion hypothesis/unique-games conjecture and a possible SoS version of a proof of the Parisi formula.

Some 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.

Publications

Sum-of-Squares Optimization for Spherical Spin Glasses: The fRSB Regime
Tommaso D'Orsi, Juspreet Singh Sandhu, Jonathan Shi
In Submission
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
In Submission
PDF
A General Framework for Analyzing Stochastic Dynamics in Learning Algorithms
Chi-Ning Chou, Juspreet Singh Sandhu, Mien Brabeeba Wang, Tiancheng Yu
In Submission
PDF

Preprints

Modified Hessian Ascent for the Sherrington-Kirkpatrick Model: The fRSB Regime
Juspreet Singh Sandhu, Jonathan Shi
In Preparation
Sum-of-Squares optimization for Ising Mean-Field Spin Glasses: The fRSB Regime
Juspreet Singh Sandhu, Jonathan Shi
In Preparation
Polynomial Time Sparsification of the Boolean Hypercube
Juspreet Singh Sandhu, Jonathan Shi, Luca Trevisan
In Preparation