The Role of TCS in Modern Machine Learning
2026-05-26..2026-05-29
Berkeley, United States
who it's for
theoretical computer scientists, machine learning researchers, language model researchers, algorithm designers, ai safety researchers, ml engineers, graduate students
topics
successor auxiliary tasks for transformers; recursive attention and erase workspace; one-run auditing for differential privacy; testable learning proof systems; constructive Komlós discrepancy algorithms; nowhere-zero flows and dijoins; adaptive resampling and panpredictors; astral space convex analysis; efficient reasoning in large models; disincentivizing hallucination in LLMs; theoretical models of consciousness; ocam's razor principles for transformers
| title | author | length |
|---|---|---|
| Talk by Pranjal Awasthi (Google) | Pranjal Awasthi | 38m |
Shows that adding an successor auxiliary task (multitask training with two heads, alternating gradient steps) makes decoder-only transformers trained on… | ||
| Talk by Katrina Ligett (Hebrew University of Jerusalem) | Katrina Ligett | 37m |
Presents two concrete TCS approaches: a principal–agent model where an agent holds a cost-correlated signal X that the principal neither models nor knows… | ||
| Efficient Algorithms for Reliable Machine Learning | Adam R. Klivans | 37m |
Introduces a concrete proof system called testable learning where an algorithm either returns a classifier with error at most opt + ε or abstains, and must… | ||
| Computational Thinking on Learning Models | Nati Srebro | 39m |
Argues that autoregressive chain-of-thought is the right computational model because a simple next-token function H iterated T times decouples runtime from… | ||
| On the Komlós Conjecture | Nikhil Bansal | 34m |
Proves an O((log n)^{1/4}) bound for Komlós, improving the prior Banaszczyk O((log n)^{1/2}) rate, via a polynomial‑time constructive method that repeatedly… | ||
| Multi-objective Learning: An Algorithmic Toolbox for Optimal Predictions Anytime Anywhere! | Nika Haghtalab | 38m |
Presents a concrete algorithmic toolbox that turns K-fold hard multi-distribution learning into an adaptively sampled problem where sample complexity adds… | ||
| Approximately Packing Dijoins Via Nowhere-Zero Flows | R. Ravi | 34m |
Proves a concrete packing bound: if the underlying undirected graph admits a nowhere-zero k-flow, then a digraph with minimum dicut size τ contains ⌊τ/k⌋… | ||
| Lightning Talks! | Anupam Gupta, Kevin Stangl, Kavya Ramachandran, Han Shao, Naren Manoj, Jamie Morgenstern, Xinyuan Cao, Lev Reyzin, Adam Tauman Kalai, Siddharth Prasad, Pravesh K. Kothari | 56m |
A rapid-fire set of concrete results: an online load‑balancing scheme learns from a 1% sample and achieves a 1+ε load guarantee (using fractional relaxations… | ||
| Venturing out into the world with AI | Jon Kleinberg | 45m |
Argues large language models often lack an elicitable internal map and shows concrete probes and numbers: using Myhill–Nerode extraction on transformers… | ||
| Unfamiliar Terrain | Prabhakar Raghavan | 30m |
Uses AlphaEvolve to evolve code that generates proof objects, produces a sub-ten-node asymmetric gadget that improves a TSP hardness ratio to 111/110, a… | ||
| Astral Space: Convex Analysis at Infinity | Robert Schapire | 44m |
Defines astral space as a compact extension of R^n that adds points at infinity so every linear functional extends continuously, and proves every convex… | ||
| AI and Safety | Ron Rivest | 29m |
Argues that Asimov's three laws don't fit today's AI, because fiction assumes a positronic brain that enforces rules and a near-perfect world model. Cites… | ||
| The Role of TCS in Understanding (AI) Consciousness | Lenore Blum | 43m |
A formal conscious Turing machine model combines a competition/up‑tree/down‑tree architecture, predictive learning (sleeping‑expert algorithms), homeostats and… | ||
| The Conscious Turing Machine (CTM), a formally defined Theoretical model of Consciousness | Manuel Blum | 45m |
A formally specified Conscious Turing Machine is given as a 7‑tuple with roughly 10 million processors, a 10‑Hz clock, STM/LTM, an up‑tree competition and… | ||
| Probably Approximately Precision and Recall Learning | Yishay Mansour | 35m |
Introduces a learning model where each training point is a user plus one liked item, shows that only positive samples make unbiased precision estimates… | ||
| Theory of Modern AI: Learning Theoretic, Game Theoretic, and Algorithmic Perspectives | Nina Balcan | 41m |
Claims a formal framework for learning verifiers for chain-of-thought reasoning with provable guarantees, using PAC and online learning tools, VC bounds (VC ·… | ||
| An Occam's Razor Principle for Transformers? | John Langford | 40m |
Claim: predicting the next hidden activation (not just the next token) produces a compact implicit world model that cuts extrapolation error about threefold on… | ||
| Red Points and Blue Points | Santosh Vempala | 38m |
Given independent n‑dimensional points labeled by an unknown intersection of k halfspaces with a soft margin ρ, the work gives an algorithm that PAC‑learns the… | ||
| Latent Variable models and Subset Smoothing | Ravi Kannan | 29m |
Defines Subset Smoothed polytope K' as the convex hull of averages over k‑subsets of the n noisy samples and proves K' ≈ K when many latent points lie near… | ||
| Enhanced and Efficient Reasoning in Large Language Models | Les Valiant | 36m |
Proposes a two-stage pipeline that first recodes text into a Unary Relational Integracode (expand each entity into ~4 local Boolean/embedding slots) and then… | ||
| Disincentivizing Hallucination | Adam Tauman Kalai | 34m |
Joint work with Santosh Vempala, Ofir Nachum and Edwin Zhang argues hallucinations arise because benchmarks reward guessing, not humility, and demonstrates… | ||
| Questions for Theory in the New Age of Machine Learning | Tom Mitchell | 42m |
Argues that LLMs become the learning substrate: using GPT-4 to generate justifications from 125 examples of CK-12 hints, distilling them into seven principles… | ||
| nothing matches | ||