o i OB

Jonathan Shi

theory of computer science
cornell university
Ph.D. candidate.
Advised by David Steurer.
Graduating Dec. 2018.
Brown Bag


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

. p. .


. pp. .



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.


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

Contact Information

Office: 324 Gates Hall