Tselil Schramm

tselil AT seas DOT harv
tselil AT mit

I am a postdoc in theoretical computer science at Harvard and MIT. My hosts are Boaz Barak, Jon Kelner, Ankur Moitra, and Pablo Parrilo.

During Fall 2017, I was the Google Research Fellow in the Simons Institute program on Discrete and Continuous Optimization.

I received my PhD from U.C. Berkeley, where I was advised by Prasad Raghavendra and Satish Rao. I got my B.S. in CS/Math from Harvey Mudd College, where Ran Libeskind-Hadas kept me out of trouble.

My research interests include optimization via convex programs (especially the sum-of-squares hierarchy), statistical inference, spectral algorithms, spectral graph theory, and more.

Here is a tutorial for pronouncing my name.


Check out my thesis, "Random Matrices and the Sum-of-Squares Hierarchy".
Also, my CV.



I recently co-wrote a survey on High-dimensional estimation via sum-of-squares proofs with Prasad Raghavendra and David Steurer, for their ICM 2018 invited lecture.

Papers:
(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs [arXiv]
with Boaz Barak, Chi-Ning Chou, Zhixian Lei, and Yueqi Sheng, in submission.

SOS lower bounds with hard constraints: think global, act local [arXiv]
with Pravesh Kothari, and Ryan O'Donnell, to appear in ITCS 2019.

The threshold for SDP-refutation of random regular NAE-3SAT [arXiv]
with Yash Deshpande, Andrea Montanari, Ryan O'Donnell, and Subhabrata Sen, to appear in SODA 2019.

Computing exact minimum cuts without knowing the graph [arXiv]
with Aviad Rubinstein and Matt Weinberg, in ITCS 2018.

On the power of sum-of-squares for detecting hidden structures [arXiv]
with Sam Hopkins, Pravesh Kothari, Aaron Potechin, Prasad Raghavendra, and David Steurer, in FOCS 2017.

Fast and robust tensor decomposition with applications to dictionary learning [arXiv]
with David Steurer, in COLT 2017.

Strongly refuting random CSPs below the spectral threshold [arXiv]
with Prasad Raghavendra and Satish Rao, in STOC 2017.

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors [arXiv]
with Sam Hopkins, Jonathan Shi, and David Steurer, in STOC 2016.

On the integrality gap of degree-4 sum-of-squares for planted clique
with Sam Hopkins, Pravesh Kothari, Aaron Potechin, and Prasad Raghavendra, in SODA 2016 (merge of [this] paper and [this] paper)
Invited to the SODA 2016 special issue of ACM Transactions on Algorithms.

Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors [arXiv]
with Ronen Eldan and Miklos Racz, in Random Structures & Algorithms (2016).

Near optimal LP rounding algorithms for correlation clustering in complete and complete k-partite graphs [arXiv]
with Shuchi Chawla, Konstantin Makarychev, and Grigory Yaroslavtsev, in STOC 2015.

Gap amplification for small-set expansion via random walks [arXiv]
with Prasad Raghavendra, in APPROX 2014.

Global and local information in clustering labeled block models [arXiv]
with Varun Kanade and Elchanan Mossel , in RANDOM 2014, and in IEEE Transactions on Information Theory (2016).