{"id":1452,"date":"2025-04-25T04:15:11","date_gmt":"2025-04-25T04:15:11","guid":{"rendered":"https:\/\/sigact.org\/tcsforall\/?page_id=1452"},"modified":"2026-06-24T14:01:20","modified_gmt":"2026-06-24T14:01:20","slug":"8th-tcs-for-all-meeting-2","status":"publish","type":"page","link":"https:\/\/sigact.org\/tcsforall\/","title":{"rendered":"9th TCS for All Meeting"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">You are cordially invited to attend the TCS for All 2026 Meeting, taking place on <strong>Friday June 26, <\/strong>2026, from <strong>8:30AM to 11AM in the Alpine Ballroom B at the conference hotel.<\/strong> 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!<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<div class=\"wp-block-jetpack-slideshow aligncenter\" data-autoplay=\"true\" data-delay=\"3\" data-effect=\"slide\" style=\"--aspect-ratio:calc(620 \/ 264)\"><div class=\"wp-block-jetpack-slideshow_container swiper\"><ul class=\"wp-block-jetpack-slideshow_swiper-wrapper swiper-wrapper\"><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img loading=\"lazy\" decoding=\"async\" width=\"620\" height=\"264\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-509\" data-id=\"509\" data-aspect-ratio=\"620 \/ 264\" src=\"https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2020\/06\/image-1-1.png\" srcset=\"https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2020\/06\/image-1-1.png 620w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2020\/06\/image-1-1-300x128.png 300w\" sizes=\"(max-width: 620px) 100vw, 620px\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img loading=\"lazy\" decoding=\"async\" width=\"3787\" height=\"1107\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-63\" data-id=\"63\" data-aspect-ratio=\"3787 \/ 1107\" src=\"https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2019\/03\/54728656_10157078432907889_8434244402636914688_o-1.jpg\" srcset=\"https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2019\/03\/54728656_10157078432907889_8434244402636914688_o-1.jpg 3787w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2019\/03\/54728656_10157078432907889_8434244402636914688_o-1-300x88.jpg 300w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2019\/03\/54728656_10157078432907889_8434244402636914688_o-1-768x224.jpg 768w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2019\/03\/54728656_10157078432907889_8434244402636914688_o-1-1024x299.jpg 1024w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2019\/03\/54728656_10157078432907889_8434244402636914688_o-1-1200x351.jpg 1200w\" sizes=\"(max-width: 3787px) 100vw, 3787px\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img loading=\"lazy\" decoding=\"async\" width=\"2560\" height=\"922\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-1585\" data-id=\"1585\" data-aspect-ratio=\"2560 \/ 922\" src=\"https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/rising_stars_talks_2026_collage_compact-1-scaled.jpg\" srcset=\"https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/rising_stars_talks_2026_collage_compact-1-scaled.jpg 2560w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/rising_stars_talks_2026_collage_compact-1-300x108.jpg 300w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/rising_stars_talks_2026_collage_compact-1-1024x369.jpg 1024w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/rising_stars_talks_2026_collage_compact-1-768x276.jpg 768w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/rising_stars_talks_2026_collage_compact-1-1536x553.jpg 1536w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/rising_stars_talks_2026_collage_compact-1-2048x737.jpg 2048w\" sizes=\"(max-width: 2560px) 100vw, 2560px\" \/><\/figure><\/li><\/ul><a class=\"wp-block-jetpack-slideshow_button-prev swiper-button-prev swiper-button-white\" role=\"button\"><\/a><a class=\"wp-block-jetpack-slideshow_button-next swiper-button-next swiper-button-white\" role=\"button\"><\/a><a aria-label=\"Pause Slideshow\" class=\"wp-block-jetpack-slideshow_button-pause\" role=\"button\"><\/a><div class=\"wp-block-jetpack-slideshow_pagination swiper-pagination swiper-pagination-white\"><\/div><\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Program: Friday June 26th, 2026, 8:30-11am<\/h2>\n<\/div><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">8:30am Anay Mehrotra<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">8:54am  Elena Gribelyuk<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">9:18am Rhea Jain<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">9:42am Shivam Nadimpalli<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">10:06am Yifan Wu <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">10:30am -11 Ask Me Anything: Sepehr Assadi, Kamesh Mungala and Rocco Servedio.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Abstracts and speakers info<\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1007\" height=\"1024\" src=\"https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/Elena-1007x1024.jpg\" alt=\"\" class=\"wp-image-1569\" srcset=\"https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/Elena-1007x1024.jpg 1007w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/Elena-295x300.jpg 295w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/Elena-768x781.jpg 768w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/Elena.jpg 1176w\" sizes=\"auto, (max-width: 1007px) 100vw, 1007px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Elena Gribelyuk<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Title:<\/strong> Adversarial Robustness for Small Frequency Moments<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Abstract:<\/strong> 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.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Bio:<\/strong> 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.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Rhea Jain<\/h3>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"800\" height=\"800\" src=\"https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/RheaJain.jpg\" alt=\"\" class=\"wp-image-1565\" srcset=\"https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/RheaJain.jpg 800w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/RheaJain-300x300.jpg 300w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/RheaJain-150x150.jpg 150w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/RheaJain-768x768.jpg 768w\" sizes=\"auto, (max-width: 800px) 100vw, 800px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Title<\/strong>: Fault-Tolerance in Length-Constrained Network Design<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Abstract<\/strong>: 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.&nbsp;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Bio:&nbsp;<\/strong>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\u2013Champaign, 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.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\" id=\"block-1133373f-0fdd-4fa5-88a7-d064230e8fcb\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"1024\" src=\"https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/anay_mehrotra_2023_square-1024x1024.jpg\" alt=\"\" class=\"wp-image-1559\" srcset=\"https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/anay_mehrotra_2023_square-1024x1024.jpg 1024w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/anay_mehrotra_2023_square-300x300.jpg 300w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/anay_mehrotra_2023_square-150x150.jpg 150w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/anay_mehrotra_2023_square-768x768.jpg 768w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/anay_mehrotra_2023_square-1536x1536.jpg 1536w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/anay_mehrotra_2023_square-2048x2048.jpg 2048w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Anay Mehrotra<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Title: <\/strong>Learning Theory in the Wild: Foundations of Missing Data and Language Generation<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Abstract. <\/strong>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.&nbsp;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">We will focus on learning from positive samples alone\u2014a challenge arising in many domains\u2014and 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.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Bio: <\/strong>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.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><\/h3>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"480\" height=\"480\" src=\"https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/Shivam.jpg\" alt=\"\" class=\"wp-image-1568\" srcset=\"https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/Shivam.jpg 480w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/Shivam-300x300.jpg 300w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/Shivam-150x150.jpg 150w\" sizes=\"auto, (max-width: 480px) 100vw, 480px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Shivam Nadimpalli<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Title:<\/strong>&nbsp;Optimal Sparsification of Gaussian Suprema<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Abstract:<\/strong>&nbsp;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.&nbsp;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Bio:<\/strong>&nbsp;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.&nbsp;<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1018\" height=\"1024\" src=\"https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/Yifan-1018x1024.jpg\" alt=\"\" class=\"wp-image-1570\" srcset=\"https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/Yifan-1018x1024.jpg 1018w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/Yifan-298x300.jpg 298w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/Yifan-150x150.jpg 150w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/Yifan-768x773.jpg 768w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/Yifan-1526x1536.jpg 1526w, https:\/\/sigact.org\/tcsforall\/wp-content\/uploads\/2026\/06\/Yifan.jpg 1590w\" sizes=\"auto, (max-width: 1018px) 100vw, 1018px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Yifan Wu<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Title<\/strong>: A Perfectly Truthful Calibration Measure<br><br><strong>Abstract:<\/strong> 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&nbsp;Haghtalab et al.&nbsp;(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&nbsp;Haghtalab et al.&nbsp;(2024) and&nbsp;Qiao and Zhao&nbsp;(2025) to construct&nbsp;approximately&nbsp;truthful calibration measures in the sequential prediction setting, but no&nbsp;perfectly&nbsp;truthful calibration measure was known to exist even in the more basic batch setting.<br>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&nbsp;smCal&nbsp;and the lower distance to calibration&nbsp;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&nbsp;Hu et al.&nbsp;(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&nbsp;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.&nbsp;<br><br>The talk will be based on two recent papers:&nbsp;<a href=\"https:\/\/arxiv.org\/abs\/2508.13100\" target=\"_blank\" rel=\"noreferrer noopener\">https:\/\/arxiv.org\/abs\/2508.13100<\/a>&nbsp;and&nbsp;<a href=\"https:\/\/arxiv.org\/abs\/2510.06388\" target=\"_blank\" rel=\"noreferrer noopener\">https:\/\/arxiv.org\/abs\/2510.06388<\/a><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><br><strong>Bio:<\/strong> 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.&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 &hellip; <a href=\"https:\/\/sigact.org\/tcsforall\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">9th TCS for All Meeting<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":7,"comment_status":"open","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1452","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/PaR09L-nq","_links":{"self":[{"href":"https:\/\/sigact.org\/tcsforall\/wp-json\/wp\/v2\/pages\/1452","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sigact.org\/tcsforall\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/sigact.org\/tcsforall\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/sigact.org\/tcsforall\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sigact.org\/tcsforall\/wp-json\/wp\/v2\/comments?post=1452"}],"version-history":[{"count":28,"href":"https:\/\/sigact.org\/tcsforall\/wp-json\/wp\/v2\/pages\/1452\/revisions"}],"predecessor-version":[{"id":1588,"href":"https:\/\/sigact.org\/tcsforall\/wp-json\/wp\/v2\/pages\/1452\/revisions\/1588"}],"wp:attachment":[{"href":"https:\/\/sigact.org\/tcsforall\/wp-json\/wp\/v2\/media?parent=1452"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}