tselil AT mit DOT edu
I am a theoretical computer scientist.
My research is in algorithms, and my interests include optimization via convex programs (especially the sum-of-squares hierarchy), and statistical and average-case problems, with a focus on understanding the tradeoff between information and computation.
In January 2021, I will be joining Stanford Statistics as an assistant professor.
Right now, I am visiting Ronen Eldan at the Weizmann Institute.
I received my PhD from U.C. Berkeley, where I was advised by
Prasad Raghavendra and
I was a postdoc at Harvard and MIT, hosted by the wonderful quadrumvirate of Boaz Barak, Jon Kelner, Ankur Moitra, and Pablo Parrilo.
I spent Fall 2017 as a Google Research Fellow in the Simons Institute program on Optimization.
Here is a tutorial for pronouncing my name.
Check out my thesis, "Random Matrices and the Sum-of-Squares Hierarchy".
Also, my (likely outdated) CV.
Here is a survey on High-dimensional estimation via sum-of-squares proofs that I co-wrote with Prasad Raghavendra and David Steurer, for their ICM 2018 invited lecture.
Subexponential LPs Approximate Max-Cut
Sam Hopkins and
(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs
in NeurIPS 2020.
Sherali-Adams Strikes Back
in CCC 2019.
Invited to the CCC 2019 special issue of Theory of Computing.
SOS lower bounds with hard constraints: think global, act local
in ITCS 2019.
The threshold for SDP-refutation of random regular NAE-3SAT
in SODA 2019.
Computing exact minimum cuts without knowing the graph
Aviad Rubinstein and
in ITCS 2018.
On the power of sum-of-squares for detecting hidden structures
Prasad Raghavendra, and
in FOCS 2017.
Fast and robust tensor decomposition with applications to dictionary learning
in COLT 2017.
Strongly refuting random CSPs below the spectral threshold
in STOC 2017.
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
with Sam Hopkins, Jonathan Shi, and David Steurer,
in STOC 2016.
On the integrality gap of degree-4 sum-of-squares for planted clique
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
with Ronen Eldan and
in Random Structures & Algorithms (2016).
Near optimal LP rounding algorithms for correlation clustering in complete and complete k-partite graphs
with Shuchi Chawla,
and Grigory Yaroslavtsev,
in STOC 2015.
Gap amplification for small-set expansion via random walks
with Prasad Raghavendra,
in APPROX 2014.
Global and local information in clustering labeled block models
in RANDOM 2014, and in IEEE Transactions on Information Theory (2016).