Tselil Schramm

tselil AT stanford DOT edu

I am an assistant professor at Stanford in the Department of Statistics (and in Computer Science, by courtesy).

My research is at the intersection of theoretical computer science and statistics. My work aims to develop algorithmic tools for high-dimensional estimation problems and to characterize and explain information-computation tradeoffs.

Before joining Stanford, I received my PhD from U.C. Berkeley, where I was lucky to be advised by Prasad Raghavendra and Satish Rao. After that I was a postdoc at Harvard and MIT, hosted by the wonderful quadrumvirate of Boaz Barak, Jon Kelner, Ankur Moitra, and Pablo Parrilo.

Here is a tutorial for pronouncing my name.


Teaching:
Winter 2024: Theory of Statistics II (STATS 300B)
Fall 2023: Machine Learning Theory (STATS 214 / CS 228M)
Spring 2023: Probability Theory (STATS 116)
Winter 2023: Intro to Stochastic Processes 1 (STATS 217)
Fall 2022: Machine Learning Theory (STATS 214 / CS 228M)
Spring 2022: The Sum-of-Squares Algorithmic Paradigm in Statistics (STATS 314a)
Winter 2022: Random Processes on Graphs and Lattices (STATS 221)
Spring 2021: Probability Theory (STATS 116)
Winter 2021: The Sum-of-Squares Algorithmic Paradigm in Statistics (STATS 319)


Selected and Recent Papers [all papers]:

Some easy optimization problems have the overlap-gap property [arXiv]
with Shuangping Li , in submission.

Fast, robust approximate message passing [arXiv]
with Misha Ivkov, in submission.

Semidefinite programs simulate approximate message passing robustly [arXiv]
with Misha Ivkov, in STOC 2024.

Spectral clustering in the Gaussian mixture block model [arXiv]
with Shuangping Li , in submission.

Local and global expansion in random geometric graphs [arXiv]
with Siqi Liu, Sidhanth Mohanty, and Elizabeth Yang, in STOC 2023.

Testing thresholds for high-dimensional sparse random geometric graphs [arXiv]
with Siqi Liu, Sidhanth Mohanty, and Elizabeth Yang, in STOC 2022.
Invited to the STOC 2022 special issue of SICOMP.

Statistical query algorithms and low-degree tests are almost equivalent [arXiv]
with Matthew Brennan, Guy Bresler, Sam Hopkins and Jerry Li, in COLT 2021, runner up to the Best Paper.

Computational barriers to estimation from low-degree polynomials [arXiv]
with Alex Wein, in The Annals of Statistics, 2022.

Subexponential LPs approximate max-cut [arXiv]
with Sam Hopkins and Luca Trevisan, in FOCS 2020.

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.

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.