Jonathan Shi, Academic Homepage

Research

I work on bringing ideas from the study of approximation algorithms to statistical inference problems.

In particular, the analysis of the sum-of-squares hierarchy of semidefinite programs gives us new ways to look at latent variable and unknown statistical mixture models.

General themes in my work include: tensor/multilinear algebra, random matrix theory, and polynomial/operator analysis.

I am broadly interested in the physical and social sciences, and I think about how science can serve the public good.

Selected publications

@unpublished{HSS18,
	author = {Samuel B. Hopkins and
		Tselil Schramm and
		Jonathan Shi},
	title = {A Robust Spectral Algorithm for Overcomplete Tensor Decomposition},
  note = {Work in progress.},
  year = {2018},
  booktitle = {Work in progress.}
}

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

@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

@unpublished{HSS18,
  author = {Samuel B. Hopkins and
    Tselil Schramm and
    Jonathan Shi},
  title = {A Robust Spectral Algorithm for Overcomplete Tensor Decomposition},
  note = {Work in progress.},
  year = {2018},
  booktitle = {Work in progress.}
}

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

. pp. .
[bibtex]

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

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

Contact Information

Office: 324 Gates Hall

Email: