Jonathan Shi, Academic Homepage

Research

I study simple models of highly non-convex functions in high dimensions—especially spin glasses—to find general principles for optimization and sampling. Some of this work helps delineate what quantum and classical algorithms can achieve.

In recent work, my collaborators and I identified a diffusion-model structure within classical spin-glass theory from the 1980s. We use this connection to make progress on open problems in sampling theory.

Earlier, during my Ph.D. at Cornell, I applied the Sum-of-Squares proof-to-algorithm framework to optimization problems in signal processing and unsupervised learning. I also developed a circuits-to-codes method for quantum error correction.

From 2024 to 2026, I was part of a small team that taught itself digital and analog nanoelectronics layout, reaching its first tapeout on Intel’s 3 nm process within six months. As an end-to-end contributor, I worked across layout, verification, debugging, and tapeout preparation for three integrated circuits implementing new universal protocols for inter-satellite communication.

Selected publications

@article{davies2026weak,
  title={Weak Poincaré Inequalities via Approximate Stochastic Localization: Application to Sampling the Sherrington-Kirkpatrick Model},
  author={Davies, Ewan and Lee, Holden and Sandhu, Juspreet Singh and Shi, Jonathan},
  year={2026},
  journal={arXiv preprint arXiv:2607.08160},
  url={https://arxiv.org/abs/2607.08160},
  pdf={https://arxiv.org/pdf/2607.08160}
}

@article{davies2026potentialhessianascentiii,
  title={Potential Hessian Ascent III: Sampling the Sherrington–Kirkpatrick Model at β < 1/2}, 
  author={Davies, Ewan and Lee, Holden and Sandhu, Juspreet Singh and Shi, Jonathan},
  year={2026},
  journal={arXiv preprint arXiv:2605.03718},
  url={https://arxiv.org/abs/2605.03718},
  pdf={https://arxiv.org/pdf/2605.03718}
}

@article{jekel2024potential,
  title={Potential Hessian Ascent: The Sherrington-Kirkpatrick Model},
  author={Jekel, David and Shi, Jonathan and Sandhu, Juspreet Singh},
  journal={Communications in Mathematical Physics (to appear)},
  year={2026},
  url ={https://arxiv.org/abs/2408.02360},
  pdf ={https://arxiv.org/pdf/2408.02360},
  comment={Conference version in SODA 2025}
}

@inproceedings{chou2022limitations,
  title={Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond},
  author={Chou, Chi-Ning and Love, Peter J and Sandhu, Juspreet Singh and Shi, Jonathan},
  booktitle={49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  year={2022},
  organization={Schloss Dagstuhl-Leibniz-Zentrum f{"u}r Informatik},
  url ={https://arxiv.org/abs/2108.06049},
  pdf ={https://arxiv.org/pdf/2108.06049}
}

@InProceedings{pmlr-v99-hopkins19b,
  title =        {A Robust Spectral Algorithm for Overcomplete Tensor Decomposition},
  author =       {Hopkins, Samuel B. and Schramm, Tselil and Shi, Jonathan},
  booktitle =    {Proceedings of the Thirty-Second Conference on Learning Theory (COLT)},
  pages =        {1683--1722},
  year =         {2019},
  editor =       {Beygelzimer, Alina and Hsu, Daniel},
  volume =       {99},
  series =       {Proceedings of Machine Learning Research},
  address =      {Phoenix, USA},
  month =        {25--28 Jun},
  publisher =    {PMLR},
  pdf =          {http://proceedings.mlr.press/v99/hopkins19b/hopkins19b.pdf},
  url =          {http://proceedings.mlr.press/v99/hopkins19b.html},
  abstract =     {We give a spectral algorithm for decomposing overcomplete order-4 tensors, so long as their components satisfy an algebraic non-degeneracy condition that holds for nearly all (all but an algebraic set of measure zero) tensors over (R^d)^{otimes 4} with rank n <= d^2. Our algorithm is robust to adversarial perturbations of bounded spectral norm. Our algorithm is inspired by one which uses the sum-of-squares semidefinite programming hierarchy (Ma, Shi, and Steurer STOC 16), and we achieve comparable robustness and overcompleteness guarantees under similar algebraic assumptions. However, our algorithm avoids semidefinite programming and may be implemented as a series of basic linear-algebraic operations. We consequently obtain a much faster running time than semidefinite programming methods: our algorithm runs in time O(n^2d^3) <= O(d^7), which is subquadratic in the input size d^4 (where we have suppressed factors related to the condition number of the input tensor).}
}

@article{DBLP:journals/tit/BaconFHS17,
        author = {Dave Bacon and
                Steven T. Flammia and
                Aram Wettroth Harrow and
                Jonathan Shi},
        title = {Sparse Quantum Codes From Quantum Circuits},
        journal = {{IEEE} Trans. Information Theory},
        volume = {63},
        number = {4},
        pages = {2464–2479},
        year = {2017},
  url = {https://arxiv.org/abs/1411.3334}
}

.
. . . p. . .

[bibtex]

Articles

@article{davies2026weak,
  title={Weak Poincaré Inequalities via Approximate Stochastic Localization: Application to Sampling the Sherrington-Kirkpatrick Model},
  author={Davies, Ewan and Lee, Holden and Sandhu, Juspreet Singh and Shi, Jonathan},
  year={2026},
  journal={arXiv preprint arXiv:2607.08160},
  url={https://arxiv.org/abs/2607.08160},
  pdf={https://arxiv.org/pdf/2607.08160}
}

@article{davies2026potentialhessianascentiii,
  title={Potential Hessian Ascent III: Sampling the Sherrington–Kirkpatrick Model at β < 1/2}, 
  author={Davies, Ewan and Lee, Holden and Sandhu, Juspreet Singh and Shi, Jonathan},
  year={2026},
  journal={arXiv preprint arXiv:2605.03718},
  url={https://arxiv.org/abs/2605.03718},
  pdf={https://arxiv.org/pdf/2605.03718}
}

@article{jekel2024potential,
  title={Potential Hessian Ascent: The Sherrington-Kirkpatrick Model},
  author={Jekel, David and Shi, Jonathan and Sandhu, Juspreet Singh},
  journal={Communications in Mathematical Physics (to appear)},
  year={2026},
  url ={https://arxiv.org/abs/2408.02360},
  pdf ={https://arxiv.org/pdf/2408.02360},
  comment={Conference version in SODA 2025}
}

@article{sandhu2024sum,
  title={Sum-of-Squares \& Gaussian Processes I: Certification},
  author={Sandhu, Juspreet Singh and Shi, Jonathan},
  journal={arXiv preprint arXiv:2401.14383},
  year={2024},
  url ={https://arxiv.org/abs/2401.14383},
  pdf ={https://arxiv.org/pdf/2401.14383}
}

@inproceedings{jones2023random,
  title={Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses},
  author={Jones, Chris and Marwaha, Kunal and Sandhu, Juspreet Singh and Shi, Jonathan},
  booktitle={14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  year={2023},
  organization={Schloss-Dagstuhl-Leibniz Zentrum f{"u}r Informatik},
  url ={https://arxiv.org/abs/2210.03006},
  pdf ={https://arxiv.org/pdf/2210.03006}
}

@inproceedings{chou2022limitations,
  title={Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond},
  author={Chou, Chi-Ning and Love, Peter J and Sandhu, Juspreet Singh and Shi, Jonathan},
  booktitle={49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  year={2022},
  organization={Schloss Dagstuhl-Leibniz-Zentrum f{"u}r Informatik},
  url ={https://arxiv.org/abs/2108.06049},
  pdf ={https://arxiv.org/pdf/2108.06049}
}

@InProceedings{chen2020cut,
  title={Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification},
  author={Chen, Antares and Shi, Jonathan and Trevisan, Luca},
  booktitle =    {Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms,
               {SODA} 2022, January 9 - 10, 2022},
  publisher = {{SIAM}},
  year      = {2022},
  url ={https://arxiv.org/abs/2008.05648},
  pdf ={https://arxiv.org/pdf/2008.05648}
}

@article{shi2021low,
  title={Low-Overhead Fault-Tolerant Error Correction for High-Rate Concatenated Codes: Measuring High-Weight Syndromes with Small Circuits},
  author={Shi, Jonathan},
  year={2021}
}

@InProceedings{pmlr-v99-hopkins19b,
  title =        {A Robust Spectral Algorithm for Overcomplete Tensor Decomposition},
  author =       {Hopkins, Samuel B. and Schramm, Tselil and Shi, Jonathan},
  booktitle =    {Proceedings of the Thirty-Second Conference on Learning Theory (COLT)},
  pages =        {1683--1722},
  year =         {2019},
  editor =       {Beygelzimer, Alina and Hsu, Daniel},
  volume =       {99},
  series =       {Proceedings of Machine Learning Research},
  address =      {Phoenix, USA},
  month =        {25--28 Jun},
  publisher =    {PMLR},
  pdf =          {http://proceedings.mlr.press/v99/hopkins19b/hopkins19b.pdf},
  url =          {http://proceedings.mlr.press/v99/hopkins19b.html},
  abstract =     {We give a spectral algorithm for decomposing overcomplete order-4 tensors, so long as their components satisfy an algebraic non-degeneracy condition that holds for nearly all (all but an algebraic set of measure zero) tensors over (R^d)^{otimes 4} with rank n <= d^2. Our algorithm is robust to adversarial perturbations of bounded spectral norm. Our algorithm is inspired by one which uses the sum-of-squares semidefinite programming hierarchy (Ma, Shi, and Steurer STOC 16), and we achieve comparable robustness and overcompleteness guarantees under similar algebraic assumptions. However, our algorithm avoids semidefinite programming and may be implemented as a series of basic linear-algebraic operations. We consequently obtain a much faster running time than semidefinite programming methods: our algorithm runs in time O(n^2d^3) <= O(d^7), which is subquadratic in the input size d^4 (where we have suppressed factors related to the condition number of the input tensor).}
}

@article{DBLP:journals/tit/BaconFHS17,
        author = {Dave Bacon and
                Steven T. Flammia and
                Aram Wettroth Harrow and
                Jonathan Shi},
        title = {Sparse Quantum Codes From Quantum Circuits},
        journal = {{IEEE} Trans. Information Theory},
        volume = {63},
        number = {4},
        pages = {2464–2479},
        year = {2017},
  url = {https://arxiv.org/abs/1411.3334}
}
@inproceedings{DBLP:conf/focs/MaSS16,
        author = {Tengyu Ma and
                Jonathan Shi and
                David Steurer},
        title = {Polynomial-Time Tensor Decompositions with Sum-of-Squares},
        booktitle = {{FOCS}},
        pages = {438–446},
        publisher = {{IEEE} Computer Society},
        year = {2016},
  url = {https://arxiv.org/abs/1610.01980}
}

@inproceedings{DBLP:conf/stoc/HopkinsSSS16,
        author = {Samuel B. Hopkins and
                Tselil Schramm and
                Jonathan Shi and
                David Steurer},
        title = {Fast spectral algorithms from sum-of-squares proofs: tensor decomposition
                and planted sparse vectors},
        booktitle = {{STOC}},
        pages = {178–191},
        publisher = {{ACM}},
        year = {2016},
  url = {https://arxiv.org/abs/1512.02337}
}

@inproceedings{DBLP:conf/colt/HopkinsSS15,
        author = {Samuel B. Hopkins and
                Jonathan Shi and
                David Steurer},
        title = {Tensor principal component analysis via sum-of-square proofs},
        booktitle = {{COLT}},
        series = {{JMLR} Workshop and Conference Proceedings},
        volume = {40},
        pages = {956–1006},
        publisher = {JMLR.org},
        year = {2015},
  url = {https://arxiv.org/abs/1507.03269}
}

@article{ellenberg2014efficient,
  title={Efficient computation of the Kauffman bracket},
  author={Ellenberg, Lauren and Newman, Gabriella and Sawin, Stephen and Shi, Jonathan},
  journal={Journal of Knot Theory and Its Ramifications},
  volume={23},
  number={05},
  pages={1450026},
  year={2014},
  publisher={World Scientific},
  url={https://arxiv.org/abs/1303.7179}
}

.
. . . p. . . .

[bibtex]

Tapeouts

Lecture notes

Lecture notes introducing semidefinite programming from a statistical method-of-moments/pseudo-distribution perspective.

Covers MAX-CUT, positive-semidefinite matrices, an analysis of the Goemans-Williamson algorithm for MAX-CUT via hyperplane cuts (equivalently, Gaussian sampling), and briefly duality and ties to hardness of approximation.

Non-research presentations

Slides discussing the thermodynamic arrow of time, especially as it relates to computation and/or cognition.

Slides introducing some basic concepts of sociolinguistics and debunking common assumptions about language.

Miscellaneous

Cognitive Behavioral Productivity: How you can use psychology to get unstuck

Article on Every/Superorganizers newsletter.

What’s Going On When Hard Work Seems Impossible?

Article on Every/Superorganizers newsletter.

Organization Is Key

Opinion article in Princeton campus newspaper.

Webpage generating mailing labels for all legislators serving a given a U.S. address/location.

Contact Information

Email: