Jonathan Shi, Academic Homepage

Research

I study simple models of highly non-convex functions in high dimensions (specifically, spin glass models) to find generalizable lessons for non-convex optimization and sampling. Some of the findings clarify the boundary between what quantum vs. classical computers are capable of.

My most recent work finds that diffusion models (the ones that are omnipresent today in generative AI) underlie the classic theory of spin glasses from the 1980s. We use this newfound connection to make progress on open questions in the theory of sampling.

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

In 2024-2025, I was among a small team of novices who, within a span of 6 months, learned and taught each other digital/analog nanoelectronics layout well enough to tape out on Intel's 3nm process. We produced integrated circuits supporting new universal protocols for data communication between satellites (e.g. for datacenters in space).

Selected publications

@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}
}

@inproceedings{jekel2024potential,
  title={Potential Hessian Ascent: The Sherrington-Kirkpatrick Model},
  author={Jekel, David and Shi, Jonathan and Sandhu, Juspreet Singh},
  booktitle={Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  pages={5307--5387},
  year={2025},
  organization={SIAM},
  url ={https://arxiv.org/abs/2408.02360},
  pdf ={https://arxiv.org/pdf/2408.02360}
}

@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},
  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}
}

.
. . . p. . .
[bibtex]

Articles

@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}
}

@inproceedings{jekel2024potential,
  title={Potential Hessian Ascent: The Sherrington-Kirkpatrick Model},
  author={Jekel, David and Shi, Jonathan and Sandhu, Juspreet Singh},
  booktitle={Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  pages={5307--5387},
  year={2025},
  organization={SIAM},
  url ={https://arxiv.org/abs/2408.02360},
  pdf ={https://arxiv.org/pdf/2408.02360}
}

@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}
}

@article{chou2021limitations,
  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},
  journal={arXiv preprint arXiv:2108.06049},
  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},
  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: