You are cordially invited to attend the TCS for All 2026 Meeting, taking place on Friday June 26, 2026, from 8:30AM to 11AM in the Alpine Ballroom B at the conference hotel. This workshop is part of the 58th Symposium on Theory of Computing (STOC) and will feature some fantastic Rising Star speakers. The event is open to all attendees. To attend the workshop in person, just show up!
8:30am Anay Mehrotra
8:54am Elena Gribelyuk
9:18am Rhea Jain
9:42am Shivam Nadimpalli
10:06am Yifan Wu
10:30am -11 Ask Me Anything: Sepehr Assadi, Kamesh Mungala and Rocco Servedio.
Abstracts and speakers info
Elena Gribelyuk
Title: Adversarial Robustness for Small Frequency Moments
Abstract: We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. While recent work achieved a robust $(1+\varepsilon)$-approximation for the second moment $F_2$ in polylogarithmic space, achieving high accuracy for other frequency moments remained a major open question; for $p \in [0, 2)$, including the fundamental distinct elements problem ($F_0$), only constant-factor approximations were known in sublinear space. We close this gap, showing that $(1+\varepsilon)$-approximate robustness can be achieved in polylogarithmic space for all $p \in [0, 2]$. Our approach generalizes the estimator-corrector-learner framework to non-Hilbert spaces by dynamically maintaining implicit isometric embeddings into $L_2$ and performing regularized kernel ridge regression over adaptively discovered hard queries, yielding the first insertion-deletion algorithms that approximate: (1) the $p$-th frequency moment $F_p$ up to a $(1+\varepsilon)$-factor in $\text{poly}(1/\varepsilon, \log n)$ space for all $p \in [0, 2]$, including the support size $F_0$, (2) metric and information-theoretic quantities, including the Earth Mover Distance (EMD) and $k$-median clustering cost over $[\Delta]^d$ up to an $\mathcal{O}(d \log \Delta)$-factor, and the Shannon entropy up to an $\varepsilon$-additive error, and (3) non-normed symmetric losses defined by Bernstein functions up to a $(1+\varepsilon)$-factor. For the $F_p$ moments, our algorithm is optimal up to $\text{poly}(1/\varepsilon, \log n)$ factors. Furthermore, we establish a weak equivalence between classical oblivious sketching and adversarial robustness. We prove that for any sub-multiplicative norm, the existence of an efficient classical linear sketch is equivalent to the existence of an efficient adversarially robust turnstile algorithm, up to polynomial factors, formalizing $L_1$ embeddability as the fundamental mechanism governing both models.
Bio: Elena is a fourth-year PhD student in Theoretical Computer Science at Princeton University. She is primarily interested in sketching and sublinear algorithms, communication complexity, and differential privacy. Her recent work studies the power and limitations of streaming algorithms under adaptive inputs for various fundamental problems.
Rhea Jain
Title: Fault-Tolerance in Length-Constrained Network Design
Abstract: Length-constraints in network design have been classically studied and have a wide range of practical applications. In these problems, one is given as input a graph with demand pairs, and the goal is to connect demand pairs via short-length paths. Recent work on length-constrained tree embeddings have led to advancements in length-constrained network design. We are interested in fault-tolerant problems, which aim to protect against node or edge failures by connecting demand pairs via disjoint paths. Despite substantial work on special cases and related problems, there has been limited progress in fault-tolerant length-constrained network design. We obtain the first polylogarithmic approximations for several problems in this area. In this talk, I will provide an overview of these results and highlight interesting resulting open problems.
Bio: Rhea Jain will be a postdoc at CMU Tepper working with Professor R Ravi starting this summer. She completed her PhD in computer science at the University of Illinois Urbana–Champaign, advised by Prof. Chandra Chekuri. Before that, she received her undergraduate degree in Computer Science and Mathematics from Carnegie Mellon University, where she was advised by Prof. Anupam Gupta. Her research focus is the development of approximation algorithms for a wide variety of network design problems.
Anay Mehrotra
Title: Learning Theory in the Wild: Foundations of Missing Data and Language Generation
Abstract. What can be learned from data? Traditional answers to this question assume an idealized data-generating process (e.g., satisfying i.i.d.-ness) and objectives that fit neatly into loss minimization. In this talk, I will present results for settings where these assumptions fail.
We will focus on learning from positive samples alone—a challenge arising in many domains—and show how a smoothed analysis bypasses classic impossibility results. This analysis also enables faster and more general algorithms for other foundational statistical tasks including, truncated statistics and causal inference. Time permitting, we will also briefly mention a line of work on the foundations of language generation.
Bio: Anay Mehrotra is a Motwani Postdoctoral Fellow at Stanford working with Amin Saberi. He recently completed his PhD at Yale, advised by Amin Karbasi and Manolis Zampetakis. His work has received the Best Paper Award at COLT and the Sir Binay Kumar Sinha Award from IIT Kanpur, and has been featured in WIRED.
Shivam Nadimpalli
Title: Optimal Sparsification of Gaussian Suprema
Abstract: Suprema of Gaussian processes are fundamental objects in probability theory, with influential applications throughout theoretical computer science. This talk is about *sparsifying* Gaussian suprema: replacing a large Gaussian process with a much smaller one while approximately preserving its supremum. I will describe a recent optimal sparsification theorem that exponentially improves previous bounds, along with some of the ideas behind the result. The talk will be self-contained and will assume no prior background on Gaussian processes.
Bio: Shivam Nadimpalli is a postdoctoral researcher at MIT. He completed his PhD at Columbia University under the supervision of Rocco Servedio and Mihalis Yannakakis. His research interests lie broadly in high-dimensional geometry and theoretical computer science, with an emphasis on convex geometry, learning theory, and property testing.
Yifan Wu
Title: A Perfectly Truthful Calibration Measure
Abstract: Calibration requires that predictions are conditionally unbiased and, therefore, reliably interpretable as probabilities. A calibration measure quantifies how far a predictor is from perfect calibration. As introduced by Haghtalab et al. (2024), a calibration measure is truthful if it is minimized in expectation when a predictor outputs the ground-truth probabilities. Predicting the true probabilities guarantees perfect calibration, but in reality, when calibration is evaluated on a random sample, all known calibration measures incentivize predictors to lie in order to appear more calibrated. Such lack of truthfulness motivated Haghtalab et al. (2024) and Qiao and Zhao (2025) to construct approximately truthful calibration measures in the sequential prediction setting, but no perfectly truthful calibration measure was known to exist even in the more basic batch setting.
We design a simple, perfectly and strictly truthful, sound and complete calibration measure in the batch setting: averaged two-bin calibration error (ATB). ATB is quadratically related to two existing calibration measures: the smooth calibration error smCal and the lower distance to calibration distCal. The simplicity in our definition of ATB makes it efficient and straightforward to compute, allowing us to give the first linear-time calibration testing algorithm, improving a result of Hu et al. (2024). We also introduce a general recipe for constructing truthful measures based on the variance additivity of independent random variables, which proves the truthfulness of ATB as a special case and allows us to construct other truthful calibration measures such as adaptive l2-ECE. Our empirical evaluations show that truthfulness of a calibration measure improves the robustness of the measure to hyper parameter selection of estimation method.
The talk will be based on two recent papers: https://arxiv.org/abs/2508.13100 and https://arxiv.org/abs/2510.06388
Bio: Yifan is a postdoctoral researcher with the EconCS group at Microsoft Research New England. She received her Ph.D. from Northwestern University, advised by Prof. Jason Hartline, and her B.S. in Computer Science from Peking University. Her research sits at the intersection of theoretical computer science, AI, and economics, with a recent focus on the theory of AI trustworthiness.