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
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.
(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs
SOS lower bounds with hard constraints: think global, act local
to appear in ITCS 2019.
The threshold for SDP-refutation of random regular NAE-3SAT
to appear 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).