# 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.

I received my PhD from U.C. Berkeley, where I was advised by
Prasad Raghavendra and
Satish Rao.

After that, I spent Fall 2017 as a Google Research Fellow in the Simons Institute program on Discrete and Continuous Optimization.

My research is in algorithms, and my interests include optimization via convex programs (especially the sum-of-squares hierarchy), statistical inference and average-case problems, 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).