| Name of Paper | Authors | Presenter | Conference |
|---|---|---|---|
| Quantum One-Time Programs, Revisited | Aparna Gupte, Jiahui Liu, Justin Raizes, Bhaskar Roberts, Vinod Vaikuntanathan | Jiahui Liu | STOC 2025 |
| Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable | Sasank Mouli | Sasank Mouli | FOCS 2024 |
| Calibration Error for Decision Making | Lunjia Hu, Yifan Wu | Yifan Wu | FOCS 2024 |
| Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler–Leman | Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordström, Shuo Pang | Duri Andrea Janett | STOC 2025 |
| Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds | Yeyuan Chen, Zihan Zhang | One of the authors | STOC 2025 |
| The FP^NP versus #P Dichotomy for #EO | Boning Meng, Juqiu Wang, Mingji Xia | Juqiu Wang | STOC 2025 |
| Vizing’s Theorem in Near-Linear Time | Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang | Tianyi Zhang | STOC 2025 |
| Sampling and Integration of Logconcave Functions by Algorithmic Diffusion | Yunbum Kook, Santosh S. Vempala | Yunbum Kook | STOC 2025 |
| Positive bias makes tensor network contraction tractable | Jiaqing Jiang, Jielun Chen, Norbert Schuch, Dominik Hangleiter | Jiaqing Jiang | STOC 2025 |
| Constant-Factor EFX Exists for Chores | Jugal Garg, Aniket Murhekar, John Qin | Aniket Murhekar | STOC 2025 |
| Constant Approximation of Fréchet Distance in Strongly Subquadratic Time | Siu-Wing Cheng, Haoqiang Huang, Shuo Zhang | Haoqiang Huang | STOC 2025 |
| Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods | Ruichen Jiang, Aryan Mokhtari, Francisco Patitucci | Ruichen Jiang | STOC 2025 |
| An Optimal Algorithm for Sorting Pattern-Avoiding Sequences | Michal Opler | Michal Opler | FOCS 2024 |
| Monotone Contractions | Eleni Batziou, John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani | Eleni Batziou | STOC 2025 |
| Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence | Jakob Nogler, Adam Polak, Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu, Christopher Ye | Jakob Nogler | STOC 2025 |
| Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs | Soheil Behnezhad, Alma Ghafari | Alma Ghafari | FOCS 2024 |
| Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations | Yuda Feng, Yang Hu, Shi Li, Ruilong Zhang | Ruilong Zhang | STOC 2025 |
| The Online Submodular Assignment Problem | Daniel Hathcock, Billy Jin, Kalen Patton, Sherry Sarkar, Michael Zlatin | Kalen Patton | FOCS 2024 |
| Omnipredicting Single-Index Models with Multi-Index Models | Lunjia Hu, Kevin Tian, Chutong Yang | Chutong Yang | STOC 2025 |
| From signaling to interviews in random matching markets | Maxwell Allman, Itai Ashlagi, Amin Saberi, Sophie H. Yu | Sophie Yu | STOC 2025 |
| The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth | Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, Katherine Van Kirk | Seyoon Ragavan | STOC 2025 |
| A Tolerant Independent Set Tester | Cameron Seth | Cameron Seth | STOC 2025 |
| Solving the Correlation Cluster LP in Sublinear Time | Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, Hanwen Zhang | Lukas Vogl | STOC 2025 |
| Name of Paper | Authors | Presenter | Conference |
|---|---|---|---|
| Novel properties of hierarchical probabilistic partitions and their algorithmic applications | Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, Alon Hovav | Lee-Ad Gottlieb | FOCS 2024 |
| The Meta-complexity of Secret Sharing | Benny Applbaum, Oded Nir | Oded Nir | STOC 2025 |
| A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends | Karl Bringmann, Egor Gorbachev | Egor Gorbachev | STOC 2025 |
| Online Combinatorial Allocations and Auctions with Few Samples | Paul Dütting, Thomas Kesselheim, Brendan Lucier, Rebecca Reiffenhäuser, Sahil Singla | Rebecca Reiffenhäuser | FOCS 2024 |
| Six Candidates Suffice to Win a Voter Majority | Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta, Kangning Wang | Prasanna Ramakrishnan | STOC 2025 |
| Breaking the Barrier of Self-Concordant Barriers: Faster Interior Point Methods for M-Matrices | Adrian Vladu | Adrian Vladu | STOC 2025 |
| Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness | Elena Gribelyuk and/or Honghao Lin | Elena Gribelyuk and/or Honghao Lin | STOC 2025 |
| List Decoding Capacity Implies Capacity on the q-ary Symmetric Channel | Francisco Pernice, Oscar Sprumont, Mary Wootters | Francisco Pernice | STOC 2025 |
| Privately Evaluating Untrusted Black-Box Functions | Ephraim Linder, Sofya Raskhodnikova, Adam Smith, Thomas Steinke | Ephraim Linder | STOC 2025 |
| Computational Lower Bounds for No-Regret Learning in Normal-Form Games | Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm | Ioannis Anagnostides | STOC 2025 |
| Single-Sample and Robust Online Resource Allocation | Rohan Ghuge, Sahil Singla, Yifan Wang | Yifan Wang | STOC 2025 |
| Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians | Jane H. Lee; Anay Mehrotra; Manolis Zampetakis | Anay Mehrotra | FOCS 2024 |
| On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse | Alkis Kalavasis; Anay Mehrotra; Grigoris Velegkas | Anay Mehrotra | STOC 2025 |
| Discrepancy Algorithms for the Binary Perceptron | Shuangping Li, Tselil Schramm, Kangjie Zhou | Kangjie Zhou | STOC 2025 |
| Accelerated Approximate Optimization of Multi-commodity Flows on Directed Graphs | Li Chen, Andrei Graur, Aaron Sidford | Andrei Graur | STOC 2025 |
| Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from #𝖯-Hardness | Dakshita Khurana and Kabir Tomer | Kabir Tomer | STOC 2025 |
| Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut | Julia Chuzhoy and Ohad Trabelsi | Ohad Trabelsi | STOC 2025 |
| SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications | Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, Stefan Tiegel | Ankit Pensia | STOC 2025 |
| Stochastic Online Correlated Selection | Ziyun Chen, Zhiyi Huang, Enze Sun | Zhiyi Huang | FOCS 2024 |
| Constant-Cost Communication is Not Reducible to k-Hamming Distance | Yuting Fang, Mika Goos, Nathan Harms, Pooya Hatami | Nathan Harms | STOC 2025 |
| The Structure of Catalytic Space: Capturing Randomness and Time via Compression | James Cook, Jiatu Li, Ian Mertz, Edward Pyne | Ian Mertz | STOC 2025 |
| Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap | Marco Carmosino, Stefan Grosser | Stefan Grosser | STOC 2025 |
| Lifting to Bounded-Depth and Regular Resolutions over Parities via Games | Yaroslav Alekseev, Dmitry Itsykson | Yaroslav Alekseev | STOC 2025 |