Jonathan Shi, Academic Homepage

Research

What I do:

My broad interests:

Current projects (as of 2021):

spin glass methods for average-case constraint-satisfaction problems (CSPs),
certifying far-from-satisfiability for average-case CSPs,
explicit unweighted sparsifiers of edge-transitive graphs,
proper scoring/aggregation algorithms for expert predictions weighted by specializations,
etiology of emergent properties of neural network models.

Selected publications

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

@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 $0$) tensors over $(\mathbb{R}^d)^{\otimes 4}$ with rank $n \le 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 $\tilde O(n^2d^3) \le \tilde 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

@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 $0$) tensors over $(\mathbb{R}^d)^{\otimes 4}$ with rank $n \le 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 $\tilde O(n^2d^3) \le \tilde 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]

Poster Presentations

Miscellaneous

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 concepts of sociolinguistics, emphasizing elements of bias/prejudice embedded in 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

Office: Via Röntgen, 1, Room 3-C3-04

Email: