Tselil Schramm

tschramm AT cs DOT berk

I am a fifth-year graduate student in the U.C. Berkeley Theory Group. I am advised by Prasad Raghavendra and Satish Rao, and am generously supported by a Chancellor's Fellowship and an NSF Graduate Research Fellowship. 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 Spectral Algorithms, Spectral Graph Theory, Approximation Algorithms, Semidefinite Programming (especially the Sum-of-Squares Hierarchy), Random Matrices, and more.

Here is a tutorial for pronouncing my name.


Check out the "Intro to sum-of-squares" blog post I wrote for Learning With Errors, Preetum Nakkiran's new student blog.


Papers:
Strongly Refuting Random CSPs Below the Spectral Threshold [arXiv]
with Prasad Raghavendra and Satish Rao, to appear 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.

Symmetric Tensor Completion from Multilinear Entries and Learning Product Mixtures over the Hypercube [arXiv]
with Benjamin Weitz, in submission.

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