STOC 2026 – Author Index

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

	Abawonse, Olakunle Sunday	STOC '26: "Generalized Samorodnitsky ..." Generalized Samorodnitsky Noisy Function Inequalities, with Applications to Error-Correcting Codes Olakunle Sunday Abawonse, Jan Hązła, and Ryan O'Donnell (AIMS, Rwanda; Carnegie Mellon University, USA) Article Search Article: stoc26main-p175-p
	Ahunbay, Mete Şeref	STOC '26: "First-Order (Coarse) Correlated ..." First-Order (Coarse) Correlated Equilibria in Non-concave Games Mete Şeref Ahunbay (CNRS - Université Grenoble Alpes - INRIA - LIG, France) Article Search Article: stoc26main-p1080-p
	Al-Dhalaan, Bandar	STOC '26: "Monte Carlo to Las Vegas for ..." Monte Carlo to Las Vegas for Recursively Composed Functions Bandar Al-Dhalaan and Shalev Ben David (University of Waterloo, Canada) Article Search Article: stoc26main-p1245-p
	Alekseev, Yaroslav	STOC '26: "Sampling Permutations with ..." Sampling Permutations with Cell Probes Is Hard Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, and Dmitry Sokolov (Technion, Israel; EPFL, Switzerland; Université de Montréal, Canada) Article Search Article: stoc26main-p108-p
	Alman, Josh	STOC '26: "Learning Functions of Halfspaces ..." Learning Functions of Halfspaces Josh Alman, Shyamal Patel, and Rocco A. Servedio (Columbia University, USA) Article Search Article: stoc26main-p827-p
	Altschuler, Jason M.	STOC '26: "Shifted Composition IV: Toward ..." Shifted Composition IV: Toward Ballistic Acceleration for Log-Concave Sampling Jason M. Altschuler, Sinho Chewi, and Matthew (Shunshi) Zhang (University of Pennsylvania, USA; Yale University, USA; University of Toronto, Canada) Article Search Article: stoc26main-p984-p
	Amireddy, Prashanth	STOC '26: "Ideals, Macaulay Bases, and ..." Ideals, Macaulay Bases, and PCPs Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, and Sophus Valentin Willumsgaard (Harvard University, USA; University of Copenhagen, Denmark) Article Search Article: stoc26main-p505-p
	Anari, Nima	STOC '26: "Parallel Sampling via Autospeculation ..." Parallel Sampling via Autospeculation Nima Anari, Carlo Baronio, CJ Chen, Alireza Haqi, Frederic Koehler, Anqi Li, and Thuy-Duong Vuong (Stanford University, USA; University of Arizona, USA; University of Chicago, USA; University of California at San Diego, USA) Article Search Article: stoc26main-p524-p
	Andoni, Alexandr	STOC '26: "Approximate Orthogonal Vectors ..." Approximate Orthogonal Vectors and Diameter via Regularity Lemma Alexandr Andoni, Shunhua Jiang, and Stepan Zharkov (Columbia University, USA; Hebrew University of Jerusalem, Israel) Article Search Article: stoc26main-p734-p
	Aravind, Abhiram	STOC '26: "Learning Read-Once Determinants ..." Learning Read-Once Determinants and the Principal Minor Assignment Problem Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, and Chandan Saha (IISc Bangalore, India; IIT Kanpur, India; ISI Kolkata, India; IIT Bombay, India; Tata Institute of Fundamental Research, Mumbai, India) Article Search Article: stoc26main-p909-p
	Armbruster, Alexander	STOC '26: "Improved Approximation Algorithms ..." Improved Approximation Algorithms for Non-preemptive Throughput Maximization Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, and Andreas Wiese (TU Munich, Germany; IDSIA at USI-SUPSI, Switzerland) Article Search Article: stoc26main-p1425-p
	Arunachalam, Srinivasan	STOC '26: "Learning Stabilizer Structure ..." Learning Stabilizer Structure of Quantum States Srinivasan Arunachalam and Arkopal Dutt (IBM Research, USA) Article Search Article: stoc26main-p1268-p
	Arvanitakis, Dionysis	STOC '26: "Optimal Phylogenetic Reconstruction ..." Optimal Phylogenetic Reconstruction from Sampled Quartets Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo, and Konstantin Makarychev (Northwestern University, USA; University of California at Santa Cruz, USA) Article Search Article: stoc26main-p1059-p
	Arvind, V.	STOC '26: "Reach Unambiguous Logspace ..." Reach Unambiguous Logspace Is Almost in Logspace V. Arvind and Samir Datta (Institute of Mathematical Sciences, Chennai, India; Chennai Mathematical Institute, India) Article Search Article: stoc26main-p905-p
	Assadi, Sepehr	STOC '26: "Semi-streaming Matching in ..." Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints Sepehr Assadi, Max Jiang, and Mars Xiang (University of Waterloo, Canada) Article Search Article: stoc26main-p429-p STOC '26: "Settling the Pass Complexity ..." Settling the Pass Complexity of Streaming Set Cover Sepehr Assadi and Janani Sundaresan (University of Waterloo, Canada) Article Search Article: stoc26main-p871-p
	Azarmehr, Amir	STOC '26: "Half-Approximating Maximum ..." Half-Approximating Maximum Dicut in the Streaming Setting Amir Azarmehr, Soheil Behnezhad, Shane Ferrante, and Mohammad Saneian (Northeastern University, USA) Article Search Article: stoc26main-p1536-p
	Babaioff, Moshe	STOC '26: "Approximating Gains-from-Trade ..." Approximating Gains-from-Trade in Matching Markets Moshe Babaioff, Aviad Rubinstein, Xizhi Tan, and Kangning Wang (Hebrew University of Jerusalem, Israel; Stanford University, USA; Rutgers University, USA) Article Search Article: stoc26main-p305-p
	Bach, Eleon	STOC '26: "Beyond Smoothed Analysis: ..." Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book Eleon Bach, Alexander E. Black, Sophie Huiberts, and Sean Kafer (TU Munich, Germany; Bowdoin College, USA; LIMOS - CNRS - University Clermont Auvergne, France; Illinois State University, USA) Article Search Article: stoc26main-p103-p
	Bakaev, Egor	STOC '26: "Better Neural Network Expressivity: ..." Better Neural Network Expressivity: Subdividing the Simplex Egor Bakaev, Florestan Brunck, Christoph Hertrich, Jack Stade, and Amir Yehudayoff (University of Copenhagen, Denmark; University of Technology Nuremberg, Germany; Technion, Israel) Article Search Article: stoc26main-p234-p
	Bakshi, Ainesh	STOC '26: "A Dobrushin Condition for ..." A Dobrushin Condition for Quantum Markov Chains: Rapid Mixing and Conditional Mutual Information at High Temperature Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang (New York University, USA; University of California at Berkeley, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p776-p
	Bamas, Étienne	STOC '26: "Randomized Rounding over Dynamic ..." Randomized Rounding over Dynamic Programs Étienne Bamas, Shi Li, and Lars Rohwedder (EPFL, Switzerland; Nanjing University, China; University of Southern Denmark, Denmark) Article Search Article: stoc26main-p1143-p
	Banerjee, Sid	STOC '26: "The Price of Competitive Information ..." The Price of Competitive Information Disclosure Sid Banerjee, Kamesh Munagala, Yiheng Shen, and Kangning Wang (Cornell University, USA; Duke University, USA; Rutgers University, USA) Article Search Article: stoc26main-p601-p
	Bansal, Nikhil	STOC '26: "Decoupling via Affine Spectral-Independence: ..." Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds beyond Banaszczyk Nikhil Bansal and Haotian Jiang (University of Michigan, USA; University of Chicago, USA) Article Search Article: stoc26main-p206-p
	Bao, Ning	STOC '26: "Efficient Quantum Hermite ..." Efficient Quantum Hermite Transform Siddhartha Jain, Vishnu Iyer, Rolando D. Somma, Ning Bao, and Stephen Jordan (University of Texas at Austin, USA; Google, USA; Northeastern University, USA; Brookhaven National Laboratory, USA) Article Search Article: stoc26main-p255-p
	Bao, Yiqiao	STOC '26: "Testing Noisy Low-Degree Polynomials ..." Testing Noisy Low-Degree Polynomials for Sparsity Yiqiao Bao, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, and Nathan White (University of Pennsylvania, USA; Massachusetts Institute of Technology, USA; Columbia University, USA) Article Search Article: stoc26main-p348-p
	Bao, Zongbo	STOC '26: "Clifford Testing: Algorithms ..." Clifford Testing: Algorithms and Lower Bounds Marcel Hinsche, Zongbo Bao, Phillipe van Dordrecht, Jens Eisert, Jop Briet, and Jonas Helsen (FU Berlin, Germany; CWI, Netherlands; QuSoft, Netherlands) Article Search Article: stoc26main-p379-p
	Baronio, Carlo	STOC '26: "Parallel Sampling via Autospeculation ..." Parallel Sampling via Autospeculation Nima Anari, Carlo Baronio, CJ Chen, Alireza Haqi, Frederic Koehler, Anqi Li, and Thuy-Duong Vuong (Stanford University, USA; University of Arizona, USA; University of Chicago, USA; University of California at San Diego, USA) Article Search Article: stoc26main-p524-p
	Behera, Amik Raj	STOC '26: "Ideals, Macaulay Bases, and ..." Ideals, Macaulay Bases, and PCPs Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, and Sophus Valentin Willumsgaard (Harvard University, USA; University of Copenhagen, Denmark) Article Search Article: stoc26main-p505-p
	Behnezhad, Soheil	STOC '26: "Half-Approximating Maximum ..." Half-Approximating Maximum Dicut in the Streaming Setting Amir Azarmehr, Soheil Behnezhad, Shane Ferrante, and Mohammad Saneian (Northeastern University, USA) Article Search Article: stoc26main-p1536-p
	Bei, Xiaohui	STOC '26: "Nash Social Welfare with Submodular ..." Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps Xiaohui Bei, Yuda Feng, Yang Hu, Shi Li, and Ruilong Zhang (Nanyang Technological University, Singapore; Nanjing University, China; Tsinghua University, China; TU Munich, Germany) Article Search Article: stoc26main-p1408-p
	Bencs, Ferenc	STOC '26: "On Zeros and Algorithms for ..." On Zeros and Algorithms for Disordered Systems: Mean-Field Spin Glasses Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, and Guus Regts (CWI, Netherlands; Stanford University, USA; Massachusetts Institute of Technology, USA; University of Amsterdam, Netherlands) Article Search Article: stoc26main-p245-p
	Ben David, Shalev	STOC '26: "Monte Carlo to Las Vegas for ..." Monte Carlo to Las Vegas for Recursively Composed Functions Bandar Al-Dhalaan and Shalev Ben David (University of Waterloo, Canada) Article Search Article: stoc26main-p1245-p
	Ben-Sasson, Eli	STOC '26: "On Proximity Gaps of Reed-Solomon ..." On Proximity Gaps of Reed-Solomon Codes Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, and Shubhangi Saraf (StarkWare Industries, Israel; StarkWare Industries, Poland; University of Toronto, Canada) Article Search Article: stoc26main-p523-p
	Bentert, Matthias	STOC '26: "Perfect Network Resilience ..." Perfect Network Resilience in Polynomial Time Matthias Bentert and Stefan Schmid (TU Berlin, Germany; Fraunhofer SIT, Germany) Modern communication networks support local fast rerouting mechanisms to quickly react to link failures: nodes store a set of conditional rerouting rules which define how to forward an incoming packet in case of incident link failures. Ideally, such rerouting mechanisms provide perfect resilience: any packet is routed from its source s to its target t as long as s and t are still connected in the underlying graph after the link failures. However, ensuring perfect resilience is algorithmically challenging as the rerouting decisions at any node v must rely solely on the local information available at v: the link from which a packet arrived at v (known as the in-port), the target of the packet, and the incident link failures at v. Already in their seminal paper at ACM PODC’12, Feigenbaum, Godfrey, Panda, Schapira, Shenker, and Singla showed that there are instances in which perfect resilience cannot be achieved. While the design of local rerouting algorithms has received much attention since then, we still lack a detailed understanding of when perfect resilience is achievable. This paper closes this gap and presents a complete characterization of when perfect resilience can be achieved. This characterization also allows us to design an O(n)-time algorithm to decide whether a given instance is perfectly resilient and an O(nm)-time algorithm to compute perfectly resilient rerouting rules whenever it is. Our algorithm is also attractive for the simple structure of the rerouting rules it uses, known as skipping in the literature: alternative links are chosen according to an ordered priority list (per in-port), where failed links are simply skipped. This is also naturally supported in hardware. The size of such an encoding is in Θ(nm) and therefore the running time of our algorithm is optimal when considering skipping rerouting rules. Intriguingly, our result also implies that in the context of perfect resilience, skipping rerouting rules are as powerful as more general rerouting rules that define the out-port for each set of incident failed links explicitly. This partially answers a long-standing open question by Chiesa, Nikolaevskiy, Mitrovic, Gurtov, Madry, Schapira, and Shenker [IEEE/ACM Transactions on Networking, 2017] in the affirmative. While our algorithm is simple, its analysis is intricate. A key concept in the analysis are links whose two endpoints also form a node separator. We prove that removing those links does not change whether a given instance is perfectly resilient or not. We also show that once all such links are removed, any instance either contains one of four specific rooted minors or belongs to one of three classes. If one of the four rooted minors is contained, then we are dealing with a no-instance (this was previously known for only two of them). Lastly, we show that any instance in any of the three remaining classes is a yes-instance, completing the characterization of perfectly resilient graphs. We do this by showing that simply following a particular face of a planar embedding of the reduced instance using the right-hand rule until a link directly to the target is found is sufficient. Article Search Article: stoc26main-p277-p
	Bergamaschi, Thiago	STOC '26: "Fast Mixing of Quantum Spin ..." Fast Mixing of Quantum Spin Chains at All Temperatures Thiago Bergamaschi and Chi-Fang Chen (University of California at Berkeley, USA) Article Search Article: stoc26main-p363-p
	Bernasconi, Martino	STOC '26: "The Complexity of Min-Max ..." The Complexity of Min-Max Optimization with Product Constraints Martino Bernasconi and Matteo Castiglioni (Bocconi University, Italy; Politecnico di Milano, Italy) Article Search Article: stoc26main-p227-p
	Bernstein, Aaron	STOC '26: "Reviving Thorup’s Shortcut ..." Reviving Thorup’s Shortcut Conjecture Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, and Leon Schiller (New York University, USA; Carnegie Mellon University, USA; ETH Zurich, Switzerland; INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; University of Michigan, USA; MPI-INF, Germany; Saarland University, Germany; Hasso Plattner Institute - University of Potsdam, Germany) Article Search Article: stoc26main-p292-p
	Bertram, Christian	STOC '26: "Dynamic Meta-Kernelization ..." Dynamic Meta-Kernelization Christian Bertram, Deborah Haun, Mads Vestergaard Jensen, and Tuukka Korhonen (University of Copenhagen, Denmark; KIT, Germany) Article Search Article: stoc26main-p269-p
	Bhangale, Amey	STOC '26: "An Analytical Approach to ..." An Analytical Approach to Parallel Repetition via CSP Inverse Theorems Amey Bhangale, Mark Braverman, Subhash Khot, Yang Liu, Dor Minzer, and Kunal Mittal (University of California at Riverside, USA; Princeton University, USA; New York University, USA; Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p148-p
	Bhattacharjee, Somnath	STOC '26: "Closure under Factorization ..." Closure under Factorization from a Result of Furstenberg Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, and Shubhangi Saraf (University of Toronto, Canada; Tata Institute of Fundamental Research, Mumbai, India) Article Search Article: stoc26main-p81-p
	Bhattacharya, Sayan	STOC '26: "Fully Dynamic Set Cover: Worst-Case ..." Fully Dynamic Set Cover: Worst-Case Recourse and Update Time Sayan Bhattacharya, Ruoxu Cen, and Debmalya Panigrahi (University of Warwick, UK; Duke University, USA) Article Search Article: stoc26main-p395-p STOC '26: "Additive One Approximation ..." Additive One Approximation for Minimum Degree Spanning Tree: Breaking the O(mn) Time Barrier Sayan Bhattacharya, Ermiya Farokhnejad, and Haoze Wang (University of Warwick, UK; Peking University, China) Article Search Article: stoc26main-p548-p
	Bhattacharya, Sreejata Kishor	STOC '26: "Lower Bounds for Near-Quadratic-Depth ..." Lower Bounds for Near-Quadratic-Depth Resolution over Parities Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, and Russell Impagliazzo (Tata Institute of Fundamental Research, Mumbai, India; University of California at San Diego, USA) Article Search Article: stoc26main-p416-p
	Bibbens, Jackson	STOC '26: "Space-Efficient Dictionary ..." Space-Efficient Dictionary Matching with Mismatches using Function Inversion Jackson Bibbens, Levi Borevitz, and Samuel McCauley (University of Massachusetts at Amherst, USA; Northwestern University, USA; Williams College, USA) Article Search Article: stoc26main-p480-p
	Bitansky, Nir	STOC '26: "Shuffling Is Universal: Statistical ..." Shuffling Is Universal: Statistical Additive Randomized Encodings for All Functions Nir Bitansky, Saroja Erabelli, Rachit Garg, and Yuval Ishai (New York University, USA; Technion, Israel; AWS, USA) Article Search Article: stoc26main-p1125-p
	Black, Alexander E.	STOC '26: "Beyond Smoothed Analysis: ..." Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book Eleon Bach, Alexander E. Black, Sophie Huiberts, and Sean Kafer (TU Munich, Germany; Bowdoin College, USA; LIMOS - CNRS - University Clermont Auvergne, France; Illinois State University, USA) Article Search Article: stoc26main-p103-p
	Blanchard, Justin	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Blank, Lotte	STOC '26: "Fine-Grained Complexity of ..." Fine-Grained Complexity of Continuous Euclidean k-Center Lotte Blank, Karl Bringmann, Parinya Chalermsook, Karthik C. S., Benedikt Kolbe, Hung Le, and Geert van Wordragen (University of Bonn, Germany; Saarland University, Germany; MPI-INF, Germany; University of Sheffield, UK; Rutgers University, USA; University of Massachusetts at Amherst, USA; Aalto University, Finland) Article Search Article: stoc26main-p171-p
	Blauth, Jannis	STOC '26: "Toward Optimal Approximations ..." Toward Optimal Approximations for Resource-Minimization for Fire Containment on Trees and Non-uniform k-Center Jannis Blauth, Christian Nöbel, and Rico Zenklusen (ETH Zurich, Switzerland) Article Search Article: stoc26main-p1150-p STOC '26: "A Constant-Factor Approximation ..." A Constant-Factor Approximation for Directed Latency Jannis Blauth and Ramin Mousavi (ETH Zurich, Switzerland; IDSIA at USI-SUPSI, Switzerland) Article Search Article: stoc26main-p221-p
	Blin, Lelia	STOC '26: "What Can Be Computed Locally ..." What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing Lelia Blin, Fedor V. Fomin, Pierre Fraigniaud, Sylvain Gay, Petr A. Golovach, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca (Université Paris Cité - IRIF - CNRS, France; University of Bergen, Norway; CNRS - Université de Paris, France; École Normale Supérieure, France; Universidad Adolfo Ibáñez, Chile; Universidad de Chile, Chile; Université d'Orléans, France) Article Search Article: stoc26main-p673-p
	Blondal, Ari	STOC '26: "Borsuk-Ulam and Replicable ..." Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, and Sivan Tretiak (McGill University, Canada; Ohio State University, USA) Article Search Article: stoc26main-p250-p
	Bogdanov, Andrej	STOC '26: "Adaptive Robustness of Hypergrid ..." Adaptive Robustness of Hypergrid Johnson-Lindenstrauss Andrej Bogdanov, Alon Rosen, Neekon Vafa, and Vinod Vaikuntanathan (University of Ottawa, Canada; Bocconi University, Italy; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p98-p
	Bonnet, Édouard	STOC '26: "Separator Theorem for Minor-Free ..." Separator Theorem for Minor-Free Graphs in Linear Time Édouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, and Tomáš Masařík (CNRS, France; University of Copenhagen, Denmark; University of Massachusetts at Amherst, USA; Carnegie Mellon University, USA; University of Warsaw, Poland) Article Search Article: stoc26main-p31-p
	Borevitz, Levi	STOC '26: "Space-Efficient Dictionary ..." Space-Efficient Dictionary Matching with Mismatches using Function Inversion Jackson Bibbens, Levi Borevitz, and Samuel McCauley (University of Massachusetts at Amherst, USA; Northwestern University, USA; Williams College, USA) Article Search Article: stoc26main-p480-p
	Bostanci, John	STOC '26: "Separating QMA from QCMA with ..." Separating QMA from QCMA with a Classical Oracle John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, and Mark Zhandry (Columbia University, USA; Saarland University, Germany; University of Washington, USA; NTT Research, USA; Stanford University, USA) Article Search Article: stoc26main-p275-p
	Bowers, Robin	STOC '26: "Combinatorial Markov Search ..." Combinatorial Markov Search Robin Bowers, Elias Lindgren, and Bo Waggoner (University of Colorado Boulder, USA) Article Search Article: stoc26main-p2089-p
	Brakensiek, Joshua	STOC '26: "Improved Approximation Algorithms ..." Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes Joshua Brakensiek, Neng Huang, Aaron Potechin, and Uri Zwick (University of California at Berkeley, USA; University of Michigan, USA; University of Chicago, USA; Tel Aviv University, Israel) Article Search Article: stoc26main-p713-p STOC '26: "Combinatorial Bounds for List ..." Combinatorial Bounds for List Recovery via Discrete Brascamp-Lieb Inequalities Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang (University of California at Berkeley, USA; University of Michigan, USA; Massachusetts Institute of Technology, USA; Ohio State University, USA) Article Search Article: stoc26main-p178-p STOC '26: "From Random to Explicit via ..." From Random to Explicit via Subspace Designs with Applications to Local Properties and Matroids Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang (University of California at Berkeley, USA; University of Michigan, USA; Massachusetts Institute of Technology, USA; Ohio State University, USA) Article Search Article: stoc26main-p281-p
	Braverman, Mark	STOC '26: "An Analytical Approach to ..." An Analytical Approach to Parallel Repetition via CSP Inverse Theorems Amey Bhangale, Mark Braverman, Subhash Khot, Yang Liu, Dor Minzer, and Kunal Mittal (University of California at Riverside, USA; Princeton University, USA; New York University, USA; Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p148-p
	Briet, Jop	STOC '26: "Clifford Testing: Algorithms ..." Clifford Testing: Algorithms and Lower Bounds Marcel Hinsche, Zongbo Bao, Phillipe van Dordrecht, Jens Eisert, Jop Briet, and Jonas Helsen (FU Berlin, Germany; CWI, Netherlands; QuSoft, Netherlands) Article Search Article: stoc26main-p379-p
	Briggs, Daniel	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Bringmann, Karl	STOC '26: "Tight (S)ETH-Based Lower Bounds ..." Tight (S)ETH-Based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-machine Scheduling Karl Bringmann, Anita Durr, and Karol Węgrzycki (Saarland University, Germany; MPI-INF, Germany) Article Search Article: stoc26main-p1518-p STOC '26: "Fine-Grained Complexity of ..." Fine-Grained Complexity of Continuous Euclidean k-Center Lotte Blank, Karl Bringmann, Parinya Chalermsook, Karthik C. S., Benedikt Kolbe, Hung Le, and Geert van Wordragen (University of Bonn, Germany; Saarland University, Germany; MPI-INF, Germany; University of Sheffield, UK; Rutgers University, USA; University of Massachusetts at Amherst, USA; Aalto University, Finland) Article Search Article: stoc26main-p171-p
	Brunck, Florestan	STOC '26: "Better Neural Network Expressivity: ..." Better Neural Network Expressivity: Subdividing the Simplex Egor Bakaev, Florestan Brunck, Christoph Hertrich, Jack Stade, and Amir Yehudayoff (University of Copenhagen, Denmark; University of Technology Nuremberg, Germany; Technion, Israel) Article Search Article: stoc26main-p234-p
	Bun, Mark	STOC '26: "Testing Distributions against ..." Testing Distributions against Bounded Distinguishers Mark Bun, Rathin Desai, and Renato Ferreira Pinto Jr. (Boston University, USA; Columbia University, USA) Article Search Article: stoc26main-p1134-p
	Byramji, Farzan	STOC '26: "Lower Bounds for Near-Quadratic-Depth ..." Lower Bounds for Near-Quadratic-Depth Resolution over Parities Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, and Russell Impagliazzo (Tata Institute of Fundamental Research, Mumbai, India; University of California at San Diego, USA) Article Search Article: stoc26main-p416-p
	Cai, Jin-Yi	STOC '26: "New Planar Algorithms and ..." New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model Jin-Yi Cai, Austen Fan, Shuai Shao, and Zhuxiao Tang (University of Wisconsin-Madison, USA; University of Science and Technology of China, China) Article Search Article: stoc26main-p428-p
	Cai, Yang	STOC '26: "Proximal Regret and Proximal ..." Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng (Yale University, USA; Massachusetts Institute of Technology, USA; University of Southern California, USA; University of Virginia, USA) Article Search Article: stoc26main-p859-p
	Cai, Zixi	STOC '26: "Contention Resolution, with ..." Contention Resolution, with and without a Global Clock Zixi Cai, Kuowen Chen, Shengquan Du, Tsvi Kopelowitz, Seth Pettie, and Ben Plosk (Tsinghua University, China; Bar-Ilan University, Israel; University of Michigan, USA) Article Search Article: stoc26main-p360-p
	Cao, Xinyuan	STOC '26: "Provable Long-Range Benefits ..." Provable Long-Range Benefits of Next-Token Prediction Xinyuan Cao and Santosh S. Vempala (Georgia Institute of Technology, USA) Article Search Article: stoc26main-p1520-p
	Carmesin, Johannes	STOC '26: "A Graph Minors Approach to ..." A Graph Minors Approach to Temporal Sequences Johannes Carmesin and William Turner (TU Bergakademie Freiberg, Germany) Article Search Article: stoc26main-p668-p
	Carmon, Dan	STOC '26: "On Proximity Gaps of Reed-Solomon ..." On Proximity Gaps of Reed-Solomon Codes Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, and Shubhangi Saraf (StarkWare Industries, Israel; StarkWare Industries, Poland; University of Toronto, Canada) Article Search Article: stoc26main-p523-p
	Carolan, Joseph	STOC '26: "Compressed Permutation Oracles ..." Compressed Permutation Oracles Joseph Carolan (University of Maryland at College Park, USA) Article Search Article: stoc26main-p68-p
	Castiglioni, Matteo	STOC '26: "The Sample Complexity of Uniform ..." The Sample Complexity of Uniform Approximation for Multi-dimensional CDFs and Fixed-Price Mechanisms Matteo Castiglioni, Anna Lunghi, and Alberto Marchesi (Politecnico di Milano, Italy) Article Search Article: stoc26main-p634-p STOC '26: "The Complexity of Min-Max ..." The Complexity of Min-Max Optimization with Product Constraints Martino Bernasconi and Matteo Castiglioni (Bocconi University, Italy; Politecnico di Milano, Italy) Article Search Article: stoc26main-p227-p
	Cavalar, Bruno	STOC '26: "Monotone Circuit Complexity ..." Monotone Circuit Complexity of Matching Bruno Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov (University of Oxford, UK; EPFL, Switzerland; Université de Montréal, Canada) Article Search Article: stoc26main-p518-p STOC '26: "Negations Are Powerful Even ..." Negations Are Powerful Even in Small Depth Bruno Cavalar, Théo Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, and Amir Yehudayoff (University of Oxford, UK; University of Copenhagen, Denmark; Chennai Mathematical Institute, India) Article Search Article: stoc26main-p1423-p STOC '26: "A Meta-complexity Characterization ..." A Meta-complexity Characterization of Minimal Quantum Cryptography Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, and Xingjian Li (University of Oxford, UK; Tsinghua University, China; University of Washington, USA; EPFL, Switzerland) Article Search Article: stoc26main-p298-p
	Cen, Ruoxu	STOC '26: "Fully Dynamic Set Cover: Worst-Case ..." Fully Dynamic Set Cover: Worst-Case Recourse and Update Time Sayan Bhattacharya, Ruoxu Cen, and Debmalya Panigrahi (University of Warwick, UK; Duke University, USA) Article Search Article: stoc26main-p395-p
	Chakraborty, Ishan	STOC '26: "Oracle Subset Problems: A ..." Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks Ishan Chakraborty, Tanmay Inamdar, Ariel Kulik, Madhumita Kundu, and Saket Saurabh (Institute of Mathematical Sciences, Chennai, India; IIT Jodhpur, India; Ben-Gurion University of the Negev, Israel; University of Bergen, Norway; Institute of Mathematical Sciences, India) Article Search Article: stoc26main-p443-p
	Chalermsook, Parinya	STOC '26: "Fine-Grained Complexity of ..." Fine-Grained Complexity of Continuous Euclidean k-Center Lotte Blank, Karl Bringmann, Parinya Chalermsook, Karthik C. S., Benedikt Kolbe, Hung Le, and Geert van Wordragen (University of Bonn, Germany; Saarland University, Germany; MPI-INF, Germany; University of Sheffield, UK; Rutgers University, USA; University of Massachusetts at Amherst, USA; Aalto University, Finland) Article Search Article: stoc26main-p171-p
	Chandrasekaran, Gautam	STOC '26: "A Fully Polynomial-Time Algorithm ..." A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube Gautam Chandrasekaran, Adam R. Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan (University of Texas at Austin, USA) Article Search Article: stoc26main-p1095-p STOC '26: "Sparse Linear Regression Is ..." Sparse Linear Regression Is Easy on Random Supports Gautam Chandrasekaran, Raghu Meka, and Konstantinos Stavropoulos (University of Texas at Austin, USA; University of California at Los Angeles, USA) Article Search Article: stoc26main-p1875-p
	Chang, Hsien-Chih	STOC '26: "Cutting Planarians: Planar ..." Cutting Planarians: Planar Emulators for String Graphs Hsien-Chih Chang, Jonathan Conroy, Zihan Tan, and Da Wei Zheng (Dartmouth College, USA; University of Minnesota, USA; IST Austria, Austria) Article Search Article: stoc26main-p1565-p
	Charikar, Moses	STOC '26: "A (4+ϵ)-Approximation for ..." A (4+ϵ)-Approximation for Euclidean 𝑘-Means via Non-monotone Dual-Fitting Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, and Ernest van Wijland (Stanford University, USA; Google Research, France; IDSIA at USI-SUPSI, Switzerland; University of Michigan, USA; Université Paris-Cité - CNRS, France) Article Search Article: stoc26main-p1152-p
	Chatterjee, Abhranil	STOC '26: "Learning Read-Once Determinants ..." Learning Read-Once Determinants and the Principal Minor Assignment Problem Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, and Chandan Saha (IISc Bangalore, India; IIT Kanpur, India; ISI Kolkata, India; IIT Bombay, India; Tata Institute of Fundamental Research, Mumbai, India) Article Search Article: stoc26main-p909-p
	Chatterjee, Soham	STOC '26: "Deterministic List Decoding ..." Deterministic List Decoding of Reed-Solomon Codes Soham Chatterjee, Mrinal Kumar, and Prahladh Harsha (Tata Institute of Fundamental Research, Mumbai, India) Article Search Article: stoc26main-p1402-p
	Chattopadhyay, Arkadev	STOC '26: "Lower Bounds for Near-Quadratic-Depth ..." Lower Bounds for Near-Quadratic-Depth Resolution over Parities Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, and Russell Impagliazzo (Tata Institute of Fundamental Research, Mumbai, India; University of California at San Diego, USA) Article Search Article: stoc26main-p416-p STOC '26: "Restriction Trees for Sparsity ..." Restriction Trees for Sparsity and Applications Arkadev Chattopadhyay, Yogesh Dahiya, and Shachar Lovett (Tata Institute of Fundamental Research, Mumbai, India; University of California at San Diego, USA) Article Search Article: stoc26main-p1195-p
	Chattopadhyay, Eshan	STOC '26: "Improved Bounds for Coin Flipping, ..." Improved Bounds for Coin Flipping, Leader Election, and Random Selection Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, and Rocco A. Servedio (Cornell University, USA; Columbia University, USA) Article Search Article: stoc26main-p777-p
	Chatziafratis, Vaggos	STOC '26: "Optimal Phylogenetic Reconstruction ..." Optimal Phylogenetic Reconstruction from Sampled Quartets Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo, and Konstantin Makarychev (Northwestern University, USA; University of California at Santa Cruz, USA) Article Search Article: stoc26main-p1059-p
	Chaudhury, Bhaskar Ray	STOC '26: "Tâtonnement Dynamics for ..." Tâtonnement Dynamics for Fisher Markets with Chores Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta, and Tianlong Nan (University of Illinois at Urbana-Champaign, USA; Columbia University, USA) Article Search Article: stoc26main-p183-p
	Chekuri, Chandra	STOC '26: "A Polylogarithmic Approximation ..." A Polylogarithmic Approximation for Buy-at-Bulk Network Design with Protection Chandra Chekuri and Rhea Jain (University of Illinois at Urbana-Champaign, USA) Article Search Article: stoc26main-p1857-p
	Chen, Boyang	STOC '26: "A Meta-complexity Characterization ..." A Meta-complexity Characterization of Minimal Quantum Cryptography Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, and Xingjian Li (University of Oxford, UK; Tsinghua University, China; University of Washington, USA; EPFL, Switzerland) Article Search Article: stoc26main-p298-p
	Chen, Caicai	STOC '26: "Secret-Key PIR from Random ..." Secret-Key PIR from Random Linear Codes Caicai Chen, Yuval Ishai, Tamer Mour, and Alon Rosen (Bocconi University, Italy; Technion, Israel; AWS, USA) Article Search Article: stoc26main-p1368-p
	Chen, Charles R.	STOC '26: "Quantum Precomputation: Parallelizing ..." Quantum Precomputation: Parallelizing Cascade Circuits and the Moore–Nilsson Conjecture Is False Adam Bene Watts, Charles R. Chen, J. William Helton, and Joseph Slote (University of Calgary, Canada; University of California at San Diego, USA; University of Washington, USA) Article Search Article: stoc26main-p487-p
	Chen, Chi-Fang	STOC '26: "Fast Mixing of Quantum Spin ..." Fast Mixing of Quantum Spin Chains at All Temperatures Thiago Bergamaschi and Chi-Fang Chen (University of California at Berkeley, USA) Article Search Article: stoc26main-p363-p
	Chen, CJ	STOC '26: "Parallel Sampling via Autospeculation ..." Parallel Sampling via Autospeculation Nima Anari, Carlo Baronio, CJ Chen, Alireza Haqi, Frederic Koehler, Anqi Li, and Thuy-Duong Vuong (Stanford University, USA; University of Arizona, USA; University of Chicago, USA; University of California at San Diego, USA) Article Search Article: stoc26main-p524-p
	Chen, Kean	STOC '26: "Approximation Does Not Help ..." Approximation Does Not Help in Quantum Unitary Time-Reversal Kean Chen, Nengkun Yu, and Zhicheng Zhang (University of Pennsylvania, USA; Stony Brook University, USA; University of Technology Sydney, Australia) Article Search Article: stoc26main-p656-p
	Chen, Kuowen	STOC '26: "Contention Resolution, with ..." Contention Resolution, with and without a Global Clock Zixi Cai, Kuowen Chen, Shengquan Du, Tsvi Kopelowitz, Seth Pettie, and Ben Plosk (Tsinghua University, China; Bar-Ilan University, Israel; University of Michigan, USA) Article Search Article: stoc26main-p360-p
	Chen, Lijie	STOC '26: "A Theory for Probabilistic ..." A Theory for Probabilistic Polynomial-Time Reasoning Lijie Chen, Jiatu Li, Igor C. Oliveira, and Ryan Williams (University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; University of Warwick, UK) Article Search Article: stoc26main-p624-p STOC '26: "Superquadratic Lower Bounds ..." Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits Lijie Chen, Avishay Tal, and Yichuan Wang (University of California at Berkeley, USA) Article Search Article: stoc26main-p385-p
	Chen, Mark	STOC '26: "Boolean Function Monotonicity ..." Boolean Function Monotonicity Testing Requires (Almost) n1/2 Queries Mark Chen, Xi Chen, Hao Cui, William Pires, and Jonah Stockwell (Columbia University, USA) Article Search Article: stoc26main-p270-p
	Chen, Sitan	STOC '26: "Computation-Utility-Privacy ..." Computation-Utility-Privacy Tradeoffs in Bayesian Estimation Sitan Chen, Jingqiu Ding, Mahbod Majid, and Walt McKelvie (Harvard University, USA; ETH Zurich, Switzerland; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p850-p
	Chen, Xi	STOC '26: "A Mysterious Connection between ..." A Mysterious Connection between Tolerant Junta Testing and Agnostically Learning Conjunctions Xi Chen, Shyamal Patel, and Rocco A. Servedio (Columbia University, USA) Article Search Article: stoc26main-p48-p STOC '26: "Boolean Function Monotonicity ..." Boolean Function Monotonicity Testing Requires (Almost) n1/2 Queries Mark Chen, Xi Chen, Hao Cui, William Pires, and Jonah Stockwell (Columbia University, USA) Article Search Article: stoc26main-p270-p
	Chen, Yeyuan	STOC '26: "Combinatorial Bounds for List ..." Combinatorial Bounds for List Recovery via Discrete Brascamp-Lieb Inequalities Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang (University of California at Berkeley, USA; University of Michigan, USA; Massachusetts Institute of Technology, USA; Ohio State University, USA) Article Search Article: stoc26main-p178-p STOC '26: "From Random to Explicit via ..." From Random to Explicit via Subspace Designs with Applications to Local Properties and Matroids Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang (University of California at Berkeley, USA; University of Michigan, USA; Massachusetts Institute of Technology, USA; Ohio State University, USA) Article Search Article: stoc26main-p281-p
	Chen, Yu	STOC '26: "Lower Bounds on Flow Sparsifiers ..." Lower Bounds on Flow Sparsifiers with Steiner Nodes Yu Chen, Zihan Tan, and Mingyang Yang (National University of Singapore, Singapore; University of Minnesota, USA) Article Search Article: stoc26main-p636-p
	Chen, Ziyun	STOC '26: "High-Accuracy List-Decodable ..." High-Accuracy List-Decodable Mean Estimation Ziyun Chen, Spencer Compton, Daniel M. Kane, and Jerry Li (University of Washington, USA; Stanford University, USA; University of California at San Diego, USA) Article Search Article: stoc26main-p335-p
	Chewi, Sinho	STOC '26: "Shifted Composition IV: Toward ..." Shifted Composition IV: Toward Ballistic Acceleration for Log-Concave Sampling Jason M. Altschuler, Sinho Chewi, and Matthew (Shunshi) Zhang (University of Pennsylvania, USA; Yale University, USA; University of Toronto, Canada) Article Search Article: stoc26main-p984-p
	Christ, Miranda	STOC '26: "Improved Pseudorandom Codes ..." Improved Pseudorandom Codes from Permuted Puzzles Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, and Daniel Wichs (Columbia University, USA; Microsoft Research, USA; University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; Northeastern University, USA) Article Search Article: stoc26main-p1557-p
	Chudnovsky, Maria	STOC '26: "Forbidden Subgraphs of Graphs ..." Forbidden Subgraphs of Graphs with Low Bandwidth Maria Chudnovsky, Daniel Lokshtanov, and Eran Nevo (Princeton University, USA; University of California at Santa Barbara, USA; Hebrew University of Jerusalem, Israel) Article Search Article: stoc26main-p21-p
	Chuzhoy, Julia	STOC '26: "A Faster Deterministic Algorithm ..." A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching Julia Chuzhoy, Sanjeev Khanna, and Junkai Song (Toyota Technological Institute at Chicago, USA; University of Pennsylvania, USA) Article Search Article: stoc26main-p840-p
	Cohen, Alon	STOC '26: "Sample Complexity of Agnostic ..." Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, and Qian Zhang (Tel Aviv University, Israel; Google Research, Israel; Purdue University, USA; Technion, Israel) Article Search Article: stoc26main-p308-p
	Cohen-Addad, Vincent	STOC '26: "A (4+ϵ)-Approximation for ..." A (4+ϵ)-Approximation for Euclidean 𝑘-Means via Non-monotone Dual-Fitting Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, and Ernest van Wijland (Stanford University, USA; Google Research, France; IDSIA at USI-SUPSI, Switzerland; University of Michigan, USA; Université Paris-Cité - CNRS, France) Article Search Article: stoc26main-p1152-p STOC '26: "Combinatorial Optimization ..." Combinatorial Optimization using Comparison Oracles Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Pittu, Jon Schneider, and David P. Woodruff (Google Research, New-York, USA; Bocconi University, Italy; New York University, USA; Google Research, USA; University of Michigan, USA; Duke University, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p1341-p STOC '26: "A Strong Linear Programming ..." A Strong Linear Programming Relaxation for Weighted Tree Augmentation Vincent Cohen-Addad, Marina Drygala, Nathan Klein, and Ola Svensson (Google Research, France; EPFL, Switzerland; Boston University, USA) Article Search Article: stoc26main-p1669-p
	Coladangelo, Andrea	STOC '26: "The Power of Two Bases: Nearly ..." The Power of Two Bases: Nearly Robust and Copy-Optimal Certification of Nearly All Quantum States with Single-Qubit Measurements Andrea Coladangelo, Jerry Li, Joseph Slote, and Ellen Wu (University of Washington, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p999-p STOC '26: "A Meta-complexity Characterization ..." A Meta-complexity Characterization of Minimal Quantum Cryptography Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, and Xingjian Li (University of Oxford, UK; Tsinghua University, China; University of Washington, USA; EPFL, Switzerland) Article Search Article: stoc26main-p298-p
	Collaboration, The bbchallenge	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Compton, Spencer	STOC '26: "High-Accuracy List-Decodable ..." High-Accuracy List-Decodable Mean Estimation Ziyun Chen, Spencer Compton, Daniel M. Kane, and Jerry Li (University of Washington, USA; Stanford University, USA; University of California at San Diego, USA) Article Search Article: stoc26main-p335-p
	Conroy, Jonathan	STOC '26: "Cutting Planarians: Planar ..." Cutting Planarians: Planar Emulators for String Graphs Hsien-Chih Chang, Jonathan Conroy, Zihan Tan, and Da Wei Zheng (Dartmouth College, USA; University of Minnesota, USA; IST Austria, Austria) Article Search Article: stoc26main-p1565-p
	Correa, José	STOC '26: "On the Informativeness of ..." On the Informativeness of Moments in Optimal Stopping José Correa, Andrés Cristi, Vasilis Livanos, Victor Verdugo, and Jiechen Zhang (Universidad de Chile, Chile; EPFL, Switzerland; Center for Mathematical Modeling, Chile; Pontificia Universidad Católica de Chile, Chile) Article Search Article: stoc26main-p342-p
	Cristi, Andrés	STOC '26: "On the Informativeness of ..." On the Informativeness of Moments in Optimal Stopping José Correa, Andrés Cristi, Vasilis Livanos, Victor Verdugo, and Jiechen Zhang (Universidad de Chile, Chile; EPFL, Switzerland; Center for Mathematical Modeling, Chile; Pontificia Universidad Católica de Chile, Chile) Article Search Article: stoc26main-p342-p
	Cui, Hao	STOC '26: "Boolean Function Monotonicity ..." Boolean Function Monotonicity Testing Requires (Almost) n1/2 Queries Mark Chen, Xi Chen, Hao Cui, William Pires, and Jonah Stockwell (Columbia University, USA) Article Search Article: stoc26main-p270-p
	Dadush, Daniel	STOC '26: "Trust Region Interior Point ..." Trust Region Interior Point Methods: Optimal L2- and Faster Wide-Neighborhood Path Following Daniel Dadush, Haoyuan Ma, Bento Natura, and László A. Végh (CWI, Netherlands; University of Bonn, Germany; Columbia University, USA) Article Search Article: stoc26main-p331-p
	Dahiya, Yogesh	STOC '26: "Restriction Trees for Sparsity ..." Restriction Trees for Sparsity and Applications Arkadev Chattopadhyay, Yogesh Dahiya, and Shachar Lovett (Tata Institute of Fundamental Research, Mumbai, India; University of California at San Diego, USA) Article Search Article: stoc26main-p1195-p
	Daskalakis, Constantinos	STOC '26: "Proximal Regret and Proximal ..." Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng (Yale University, USA; Massachusetts Institute of Technology, USA; University of Southern California, USA; University of Virginia, USA) Article Search Article: stoc26main-p859-p
	Datta, Samir	STOC '26: "Reach Unambiguous Logspace ..." Reach Unambiguous Logspace Is Almost in Logspace V. Arvind and Samir Datta (Institute of Mathematical Sciences, Chennai, India; Chennai Mathematical Institute, India) Article Search Article: stoc26main-p905-p
	De, Anindya	STOC '26: "Sparsifying Suprema of Gaussian ..." Sparsifying Suprema of Gaussian Processes Anindya De, Shivam Nadimpalli, Ryan O'Donnell, and Rocco A. Servedio (University of Pennsylvania, USA; Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; Columbia University, USA) We give a dimension-independent sparsification result for suprema of centered Gaussian processes: Let T be any (possibly infinite) bounded set of vectors in n, and let {t := t · g }t∈ T be the canonical Gaussian process on T, where g∼ N(0, In). We show that there is an Oε(1)-size subset S ⊆ T and a set of real values {cs}s ∈ S such that the random variable sups ∈ S {Xs + cs} is an ε-approximator (in L1) of the random variable supt ∈ T Xt. Notably, the size of the sparsifier S is completely independent of both |T| and the ambient dimension n. We give two applications of this sparsification theorem: <ul> <li><strong>A “Junta Theorem” for Norms:</strong> We show that given any norm ν(x) on n, there is another norm ψ(x) depending only on the projection of x onto Oε(1) directions, for which ψ(g) is a multiplicative (1 ± ε)-approximation of ν(g) with probability 1−ε for g ∼ N(0,In). </li> <li><strong>Sparsification of Convex Sets:</strong> We show that any intersection of (possibly infinitely many) halfspaces in n that are at distance r from the origin is ε-close (under N(0,In)) to an intersection of only Or,ε(1) halfspaces. This yields new polynomial-time agnostic learning and tolerant property testing algorithms for intersections of halfspaces. </li> </ul> Article Search Article: stoc26main-p202-p STOC '26: "Testing Noisy Low-Degree Polynomials ..." Testing Noisy Low-Degree Polynomials for Sparsity Yiqiao Bao, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, and Nathan White (University of Pennsylvania, USA; Massachusetts Institute of Technology, USA; Columbia University, USA) Article Search Article: stoc26main-p348-p
	De, Debsurya	STOC '26: "Computational and Statistical ..." Computational and Statistical Lower Bounds for Low-Rank Estimation under General Inhomogeneous Noise Debsurya De and Dmitriy Kunisky (Johns Hopkins University, USA) Article Search Article: stoc26main-p1352-p
	De Boer, Koen	STOC '26: "Average Hardness of SIVP for ..." Average Hardness of SIVP for Module Lattices of Fixed Rank Koen de Boer, Aurel Page, Radu Toma, and Benjamin Wesolowski (Unaffiliated, France; Inria - Univ. Bordeaux - CNRS - Bordeaux INP - IMB - UMR 5251, France; Sorbonne Univ. - Univ. Paris Cité - CNRS - IMJ-PRG, France; ENS de Lyon - CNRS - UMPA - UMR 5669, France) Article Search Article: stoc26main-p353-p
	Deka, Konrad	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Deligkas, Argyrios	STOC '26: "Fisher Markets with Approximately ..." Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos (Royal Holloway University of London, UK; University of Liverpool, UK; University of Oxford, UK; University of Essex, UK) Article Search Article: stoc26main-p474-p
	Derakhshan, Mahsa	STOC '26: "A Unified Framework for Analysis ..." A Unified Framework for Analysis of Randomized Greedy Matching Algorithms Mahsa Derakhshan and Tao Yu (Northeastern University, USA) Article Search Article: stoc26main-p1274-p
	Desai, Rathin	STOC '26: "Testing Distributions against ..." Testing Distributions against Bounded Distinguishers Mark Bun, Rathin Desai, and Renato Ferreira Pinto Jr. (Boston University, USA; Columbia University, USA) Article Search Article: stoc26main-p1134-p
	Devadas, Lalita	STOC '26: "SNARGs for NP and Non-signaling ..." SNARGs for NP and Non-signaling PCPs, Revisited Lalita Devadas, Samuel B. Hopkins, Yael Kalai, Pravesh K. Kothari, Alex Lombardi, and Surya Mathialagan (Massachusetts Institute of Technology, USA; Princeton University, USA; NTT Research, USA) Article Search Article: stoc26main-p297-p
	Devismes, Stéphane	STOC '26: "Can Like Attract Like? A Study ..." Can Like Attract Like? A Study of Homonymous Gathering in Networks Yoann Dieudonné, Stéphane Devismes, and Arnaud Labourel (MIS - Université de Picardie Jules Verne, France; LIS - Aix-Marseille University, France) Article Search Article: stoc26main-p403-p
	Dhar, Manik	STOC '26: "Combinatorial Bounds for List ..." Combinatorial Bounds for List Recovery via Discrete Brascamp-Lieb Inequalities Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang (University of California at Berkeley, USA; University of Michigan, USA; Massachusetts Institute of Technology, USA; Ohio State University, USA) Article Search Article: stoc26main-p178-p STOC '26: "From Random to Explicit via ..." From Random to Explicit via Subspace Designs with Applications to Local Properties and Matroids Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang (University of California at Berkeley, USA; University of Michigan, USA; Massachusetts Institute of Technology, USA; Ohio State University, USA) Article Search Article: stoc26main-p281-p
	Dieudonné, Yoann	STOC '26: "Can Like Attract Like? A Study ..." Can Like Attract Like? A Study of Homonymous Gathering in Networks Yoann Dieudonné, Stéphane Devismes, and Arnaud Labourel (MIS - Université de Picardie Jules Verne, France; LIS - Aix-Marseille University, France) Article Search Article: stoc26main-p403-p
	Dikstein, Yotam	STOC '26: "High Rate Efficient Local ..." High Rate Efficient Local List Decoding from HDX Yotam Dikstein, Max Hopkins, Toniann Pitassi, and Russell Impagliazzo (Institute for Advanced Study at Princeton, USA; Princeton University, USA; Columbia University, USA; University of California at San Diego, USA) Article Search Article: stoc26main-p1064-p
	Ding, Jingqiu	STOC '26: "Computation-Utility-Privacy ..." Computation-Utility-Privacy Tradeoffs in Bayesian Estimation Sitan Chen, Jingqiu Ding, Mahbod Majid, and Walt McKelvie (Harvard University, USA; ETH Zurich, Switzerland; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p850-p
	Dinur, Itai	STOC '26: "Non-adaptive Cryptanalytic ..." Non-adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-Like Inequality for Permutations Itai Dinur, Nathan Keller, and Avichai Marmor (Ben-Gurion University of the Negev, Israel; Georgetown University, USA; Bar-Ilan University, Israel) Article Search Article: stoc26main-p879-p
	Dodis, Yevgeniy	STOC '26: "Locally Computable High Independence ..." Locally Computable High Independence Hashing Yevgeniy Dodis, Shachar Lovett, and Daniel Wichs (New York University, USA; University of California at San Diego, USA; Northeastern University, USA; NTT Research, USA) Article Search Article: stoc26main-p718-p
	Domingues, Gabriel Marques	STOC '26: "Compressing Dynamic Fully ..." Compressing Dynamic Fully Indexable Dictionaries in Word-RAM Gabriel Marques Domingues (Tel Aviv University, Israel) Article Search Article: stoc26main-p594-p
	Dong, Ruiwen	STOC '26: "S-Unit Equations in Modules ..." S-Unit Equations in Modules and Linear-Exponential Diophantine Equations Ruiwen Dong and Doron Shafrir (University of Oxford, UK; Ben-Gurion University of the Negev, Israel) Let T be a positive integer and M be a finitely presented module over the Laurent polynomial ring ℤ/T[X1±, …, XN±]. We consider S-unit equations over M: these are equations of the form x1 m1 + ⋯ + xK mK = m0, where the variables x1, …, xK range over the set of monomials (with coefficient 1) of ℤ/T[X1±, …, XN±]. When T is a power of a prime number p, we show that the solution set of an S-unit equation over M is effectively p-normal in the sense of Derksen and Masser (2015). This generalizes their result on S-unit equations in fields of prime characteristic. When T is an arbitrary positive integer, we show that deciding whether an S-unit equation over M admits a solution is Turing equivalent to solving a system of linear-exponential Diophantine equations, whose base contains the prime divisors of T. Combined with a recent result of Karimov, Luca, Nieuwveld, Ouaknine and Worrell (2025), this yields decidability when T has at most two distinct prime divisors. This also shows that proving either decidability or undecidability in the case of arbitrary T would entail major breakthroughs in number theory. S-unit equations in modules have direct connections to many problems in computational algebra such as finding sparse polynomials in ideals, identifying zeros of linear recurrence sequences, and deciding membership problems in metabelian groups. In particular, a direct consequence of our result is the decidability Submonoid Membership in wreath products of the form ℤ/pa qb ≀ ℤd. Article Search Article: stoc26main-p56-p STOC '26: "The Skolem Problem in Rings ..." The Skolem Problem in Rings of Positive Characteristic Ruiwen Dong and Doron Shafrir (University of Oxford, UK; Ben-Gurion University of the Negev, Israel) We show that the Skolem Problem is decidable in finitely generated commutative rings of positive characteristic. More precisely, we show that there exists an algorithm which, given a finite presentation of a (unitary) commutative ring R = ℤ/T[X1, …, Xn]/I of characteristic T > 0, and a linear recurrence sequence (γn)n ∈ ℕ ∈ Rℕ, determines whether (γn)n ∈ ℕ contains a zero term. Our proof is based on two recent results: Dong and Shafrir (2026) on the solution set of S-unit equations over pe-torsion modules, and Karimov, Luca, Nieuwveld, Ouaknine, and Worrell (2025) on solving linear equations over powers of two multiplicatively independent numbers. Our result implies, moreover, that the zero set of a linear recurrence sequence over a ring of characteristic T = p1e1 ⋯ pkek is effectively a finite union of pi-normal sets in the sense of Derksen (2007). Article Search Article: stoc26main-p169-p
	D'Orsi, Tommaso	STOC '26: "Combinatorial Optimization ..." Combinatorial Optimization using Comparison Oracles Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Pittu, Jon Schneider, and David P. Woodruff (Google Research, New-York, USA; Bocconi University, Italy; New York University, USA; Google Research, USA; University of Michigan, USA; Duke University, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p1341-p
	Dreier, Jan	STOC '26: "Efficient Reversal of Transductions ..." Efficient Reversal of Transductions of Sparse Graph Classes Jakub Gajarský, Michał Pilipczuk, and Jan Dreier (University of Warsaw, Poland; TU Wien, Austria) Article Search Article: stoc26main-p530-p
	Drygala, Marina	STOC '26: "A Strong Linear Programming ..." A Strong Linear Programming Relaxation for Weighted Tree Augmentation Vincent Cohen-Addad, Marina Drygala, Nathan Klein, and Ola Svensson (Google Research, France; EPFL, Switzerland; Boston University, USA) Article Search Article: stoc26main-p1669-p
	Du, Shengquan	STOC '26: "Contention Resolution, with ..." Contention Resolution, with and without a Global Clock Zixi Cai, Kuowen Chen, Shengquan Du, Tsvi Kopelowitz, Seth Pettie, and Ben Plosk (Tsinghua University, China; Bar-Ilan University, Israel; University of Michigan, USA) Article Search Article: stoc26main-p360-p
	Dudek, Bartłomiej	STOC '26: "Classifying Identities: Subcubic ..." Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection Bartłomiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin, Marvin Künnemann, Xiao Mao, and Mirza Redžić (University of Wrocław, Poland; MPI-INF, Germany; KIT, Germany; University of California at Berkeley, USA; Stanford University, USA) Article Search Article: stoc26main-p715-p
	Durr, Anita	STOC '26: "Tight (S)ETH-Based Lower Bounds ..." Tight (S)ETH-Based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-machine Scheduling Karl Bringmann, Anita Durr, and Karol Węgrzycki (Saarland University, Germany; MPI-INF, Germany) Article Search Article: stoc26main-p1518-p
	Dutt, Arkopal	STOC '26: "Learning Stabilizer Structure ..." Learning Stabilizer Structure of Quantum States Srinivasan Arunachalam and Arkopal Dutt (IBM Research, USA) Article Search Article: stoc26main-p1268-p
	Dwivedi, Prateek	STOC '26: "Lower Bounds in Algebraic ..." Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials Prateek Dwivedi, Benedikt Pago, and Tim Seppelt (IT University of Copenhagen, Denmark; University of Cambridge, UK) Article Search Article: stoc26main-p286-p
	Efremenko, Klim	STOC '26: "Strong ETH Holds for Bounded-Depth ..." Strong ETH Holds for Bounded-Depth Resolution over Parities Klim Efremenko and Dmitry Itsykson (Ben-Gurion University of the Negev, Israel) Article Search Article: stoc26main-p393-p
	Eisert, Jens	STOC '26: "Clifford Testing: Algorithms ..." Clifford Testing: Algorithms and Lower Bounds Marcel Hinsche, Zongbo Bao, Phillipe van Dordrecht, Jens Eisert, Jop Briet, and Jonas Helsen (FU Berlin, Germany; CWI, Netherlands; QuSoft, Netherlands) Article Search Article: stoc26main-p379-p
	Elbaz, Tal	STOC '26: "Lower Bounds against the Ideal ..." Lower Bounds against the Ideal Proof System in Finite Fields Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu, and Iddo Tzameret (Imperial College London, UK) Article Search Article: stoc26main-p4-p
	Erabelli, Saroja	STOC '26: "Shuffling Is Universal: Statistical ..." Shuffling Is Universal: Statistical Additive Randomized Encodings for All Functions Nir Bitansky, Saroja Erabelli, Rachit Garg, and Yuval Ishai (New York University, USA; Technion, Israel; AWS, USA) Article Search Article: stoc26main-p1125-p
	Erez, Liad	STOC '26: "Sample Complexity of Agnostic ..." Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, and Qian Zhang (Tel Aviv University, Israel; Google Research, Israel; Purdue University, USA; Technion, Israel) Article Search Article: stoc26main-p308-p
	Fabris, Théo	STOC '26: "Negations Are Powerful Even ..." Negations Are Powerful Even in Small Depth Bruno Cavalar, Théo Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, and Amir Yehudayoff (University of Oxford, UK; University of Copenhagen, Denmark; Chennai Mathematical Institute, India) Article Search Article: stoc26main-p1423-p
	Fan, Austen	STOC '26: "New Planar Algorithms and ..." New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model Jin-Yi Cai, Austen Fan, Shuai Shao, and Zhuxiao Tang (University of Wisconsin-Madison, USA; University of Science and Technology of China, China) Article Search Article: stoc26main-p428-p
	Farach-Colton, Martín	STOC '26: "Greedy Open Addressing Revisited: ..." Greedy Open Addressing Revisited: Beyond Yao’s Lower Bound Martín Farach-Colton, Andrew Krapivin, and William Kuszmaul (New York University, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p516-p
	Farfan, Angelo	STOC '26: "Entrywise Approximate Solutions ..." Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time Mehrdad Ghadiri, Junzhao Yang, and Angelo Farfan (Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p247-p
	Farokhnejad, Ermiya	STOC '26: "Additive One Approximation ..." Additive One Approximation for Minimum Degree Spanning Tree: Breaking the O(mn) Time Barrier Sayan Bhattacharya, Ermiya Farokhnejad, and Haoze Wang (University of Warwick, UK; Peking University, China) Article Search Article: stoc26main-p548-p
	Fearnley, John	STOC '26: "Fisher Markets with Approximately ..." Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos (Royal Holloway University of London, UK; University of Liverpool, UK; University of Oxford, UK; University of Essex, UK) Article Search Article: stoc26main-p474-p
	Fei, Yumou	STOC '26: "A Dichotomy Theorem for Multi-pass ..." A Dichotomy Theorem for Multi-pass Streaming CSPs Yumou Fei, Dor Minzer, and Shuo Wang (Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p111-p
	Feng, Weiming	STOC '26: "Learning CNF Formulas from ..." Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime Weiming Feng, Xiongxin Yang, Yixiao Yu, and Yiyao Zhang (University of Hong Kong, Hong Kong; University of California at Santa Barbara, USA; Nanjing University, China) Article Search Article: stoc26main-p226-p
	Feng, Ying	STOC '26: "Fast and Compact Random Mappings ..." Fast and Compact Random Mappings with Uniform Guarantees and Applications Ying Feng and Piotr Indyk (Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p303-p
	Feng, Yuda	STOC '26: "Nash Social Welfare with Submodular ..." Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps Xiaohui Bei, Yuda Feng, Yang Hu, Shi Li, and Ruilong Zhang (Nanyang Technological University, Singapore; Nanjing University, China; Tsinghua University, China; TU Munich, Germany) Article Search Article: stoc26main-p1408-p
	Fenner, Nathan	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Ferrante, Shane	STOC '26: "Half-Approximating Maximum ..." Half-Approximating Maximum Dicut in the Streaming Setting Amir Azarmehr, Soheil Behnezhad, Shane Ferrante, and Mohammad Saneian (Northeastern University, USA) Article Search Article: stoc26main-p1536-p
	Ferreira Pinto Jr., Renato	STOC '26: "Testing Distributions against ..." Testing Distributions against Bounded Distinguishers Mark Bun, Rathin Desai, and Renato Ferreira Pinto Jr. (Boston University, USA; Columbia University, USA) Article Search Article: stoc26main-p1134-p
	Fischer, Nick	STOC '26: "Universe Reduction for APSP: ..." Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses Nick Fischer (MPI-INF, Germany) Article Search Article: stoc26main-p396-p STOC '26: "Classifying Identities: Subcubic ..." Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection Bartłomiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin, Marvin Künnemann, Xiao Mao, and Mirza Redžić (University of Wrocław, Poland; MPI-INF, Germany; KIT, Germany; University of California at Berkeley, USA; Stanford University, USA) Article Search Article: stoc26main-p715-p
	Fleischmann, Henry	STOC '26: "Reviving Thorup’s Shortcut ..." Reviving Thorup’s Shortcut Conjecture Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, and Leon Schiller (New York University, USA; Carnegie Mellon University, USA; ETH Zurich, Switzerland; INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; University of Michigan, USA; MPI-INF, Germany; Saarland University, Germany; Hasso Plattner Institute - University of Potsdam, Germany) Article Search Article: stoc26main-p292-p
	Flin, Maxime	STOC '26: "Sublogarithmic Distributed ..." Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors Maxime Flin, Magnús Halldórsson, Manuel Jakob, and Yannic Maus (Aalto University, Finland; Reykjavik University, Iceland; TU Graz, Austria) Article Search Article: stoc26main-p1266-p
	Fomin, Fedor V.	STOC '26: "What Can Be Computed Locally ..." What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing Lelia Blin, Fedor V. Fomin, Pierre Fraigniaud, Sylvain Gay, Petr A. Golovach, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca (Université Paris Cité - IRIF - CNRS, France; University of Bergen, Norway; CNRS - Université de Paris, France; École Normale Supérieure, France; Universidad Adolfo Ibáñez, Chile; Universidad de Chile, Chile; Université d'Orléans, France) Article Search Article: stoc26main-p673-p STOC '26: "Path Cover, Hamiltonicity, ..." Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective Fedor V. Fomin, Petr A. Golovach, Nikola Jedličková, Jan Kratochvíl, Danil Sagunov, and Kirill Simonov (University of Bergen, Norway; Charles University, Czech Republic; Saint Petersburg State University, Russian Federation) Article Search Article: stoc26main-p127-p
	Forster, Yannick	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Fraigniaud, Pierre	STOC '26: "What Can Be Computed Locally ..." What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing Lelia Blin, Fedor V. Fomin, Pierre Fraigniaud, Sylvain Gay, Petr A. Golovach, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca (Université Paris Cité - IRIF - CNRS, France; University of Bergen, Norway; CNRS - Université de Paris, France; École Normale Supérieure, France; Universidad Adolfo Ibáñez, Chile; Universidad de Chile, Chile; Université d'Orléans, France) Article Search Article: stoc26main-p673-p
	Gajarský, Jakub	STOC '26: "Efficient Reversal of Transductions ..." Efficient Reversal of Transductions of Sparse Graph Classes Jakub Gajarský, Michał Pilipczuk, and Jan Dreier (University of Warsaw, Poland; TU Wien, Austria) Article Search Article: stoc26main-p530-p
	Ganz, Amit	STOC '26: "A Poisson Process for Submodular ..." A Poisson Process for Submodular Maximization Amit Ganz, Ariel Kulik, Roy Schwartz, and Mohit Singh (Technion, Israel; Ben-Gurion University of the Negev, Israel; Georgia Institute of Technology, USA) Article Search Article: stoc26main-p1663-p
	Gao, Ruiquan	STOC '26: "A (4+ϵ)-Approximation for ..." A (4+ϵ)-Approximation for Euclidean 𝑘-Means via Non-monotone Dual-Fitting Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, and Ernest van Wijland (Stanford University, USA; Google Research, France; IDSIA at USI-SUPSI, Switzerland; University of Michigan, USA; Université Paris-Cité - CNRS, France) Article Search Article: stoc26main-p1152-p
	Gao, Zhimeng	STOC '26: "Online Combinatorial Optimization ..." Online Combinatorial Optimization with Graphical Dependencies Zhimeng Gao, Evangelia Gergatsouli, Kalen Patton, and Sahil Singla (Georgia Institute of Technology, USA) Article Search Article: stoc26main-p545-p
	Garg, Rachit	STOC '26: "Shuffling Is Universal: Statistical ..." Shuffling Is Universal: Statistical Additive Randomized Encodings for All Functions Nir Bitansky, Saroja Erabelli, Rachit Garg, and Yuval Ishai (New York University, USA; Technion, Israel; AWS, USA) Article Search Article: stoc26main-p1125-p
	Garg, Sumegha	STOC '26: "A Unified Approach to Memory-Sample ..." A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures Sumegha Garg, Jabari Hastings, Chirag Pabbaraju, and Vatsal Sharan (Rutgers University, USA; Stanford University, USA; University of Southern California, USA) Article Search Article: stoc26main-p85-p
	Garlík, Michal	STOC '26: "The Weak Rank Principle: Lower ..." The Weak Rank Principle: Lower Bounds and Applications Michal Garlík, Svyatoslav Gryaznov, Hanlin Ren, and Iddo Tzameret (Imperial College London, UK; Institute for Advanced Study at Princeton, USA) Article Search Article: stoc26main-p65-p
	Gartland, Chris	STOC '26: "Lower Estimates for 𝐿₁-Distortion ..." Lower Estimates for 𝐿₁-Distortion of Transportation Cost Spaces Chris Gartland and Mikhail Ostrovskii (University of North Carolina at Charlotte, USA; St. John's University, USA) Article Search Article: stoc26main-p304-p
	Gay, Sylvain	STOC '26: "What Can Be Computed Locally ..." What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing Lelia Blin, Fedor V. Fomin, Pierre Fraigniaud, Sylvain Gay, Petr A. Golovach, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca (Université Paris Cité - IRIF - CNRS, France; University of Bergen, Norway; CNRS - Université de Paris, France; École Normale Supérieure, France; Universidad Adolfo Ibáñez, Chile; Universidad de Chile, Chile; Université d'Orléans, France) Article Search Article: stoc26main-p673-p
	Gelles, Yuval	STOC '26: "Sub-linear Secure Broadcast ..." Sub-linear Secure Broadcast and Applications Yuval Gelles, Ilan Komargodski, and Merav Parter (Hebrew University of Jerusalem, Israel; Weizmann Institute of Science, Israel) Article Search Article: stoc26main-p851-p
	Georgiev (Skelet), Georgi	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Gergatsouli, Evangelia	STOC '26: "Online Combinatorial Optimization ..." Online Combinatorial Optimization with Graphical Dependencies Zhimeng Gao, Evangelia Gergatsouli, Kalen Patton, and Sahil Singla (Georgia Institute of Technology, USA) Article Search Article: stoc26main-p545-p
	Ghadiri, Mehrdad	STOC '26: "Entrywise Approximate Solutions ..." Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time Mehrdad Ghadiri, Junzhao Yang, and Angelo Farfan (Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p247-p
	Gheissari, Reza	STOC '26: "Mixing of General Biased Adjacent ..." Mixing of General Biased Adjacent Transposition Chains Reza Gheissari, Holden Lee, and Eric Vigoda (Northwestern University, USA; Johns Hopkins University, USA; University of California at Santa Barbara, USA) Article Search Article: stoc26main-p565-p
	Ghentiyala, Surendra	STOC '26: "Range Avoidance, Arthur-Merlin, ..." Range Avoidance, Arthur-Merlin, and TFNP Surendra Ghentiyala, Zeyong Li, and Noah Stephens-Davidowitz (Cornell University, USA; National University of Singapore, Singapore) Article Search Article: stoc26main-p1260-p
	Ghosh, Sumanta	STOC '26: "Learning Read-Once Determinants ..." Learning Read-Once Determinants and the Principal Minor Assignment Problem Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, and Chandan Saha (IISc Bangalore, India; IIT Kanpur, India; ISI Kolkata, India; IIT Bombay, India; Tata Institute of Fundamental Research, Mumbai, India) Article Search Article: stoc26main-p909-p
	Girish, Uma	STOC '26: "Fourier Spectrum of Noisy ..." Fourier Spectrum of Noisy Quantum Algorithms Uma Girish (Columbia University, USA) Article Search Article: stoc26main-p157-p STOC '26: "Magic and Communication Complexity ..." Magic and Communication Complexity Uma Girish, Alex May, Natalie Parham, and Henry Yuen (Columbia University, USA; Perimeter Institute for Theoretical Physics, Canada) Article Search Article: stoc26main-p364-p
	Gørtz, Inge Li	STOC '26: "An Optimal Algorithm for Stochastic ..." An Optimal Algorithm for Stochastic Vertex Cover Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Cliff Stein, Miltiadis Stouras, Ola Svensson, and Ali Vakilian (Georgia Institute of Technology, USA; DTU, Denmark; Stanford University, USA; Duke University, USA; Columbia University, USA; EPFL, Switzerland; Virginia Tech, USA) Article Search Article: stoc26main-p798-p
	Gokaj, Geri	STOC '26: "Classifying Identities: Subcubic ..." Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection Bartłomiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin, Marvin Künnemann, Xiao Mao, and Mirza Redžić (University of Wrocław, Poland; MPI-INF, Germany; KIT, Germany; University of California at Berkeley, USA; Stanford University, USA) Article Search Article: stoc26main-p715-p
	Goldberg, Guy	STOC '26: "Nearly Tight Lower Bounds ..." Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies Guy Goldberg, Tom Gur, and Sidhant Saraogi (Weizmann Institute of Science, Israel; University of Cambridge, UK; Georgetown University, USA) Article Search Article: stoc26main-p1782-p
	Golovach, Petr A.	STOC '26: "What Can Be Computed Locally ..." What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing Lelia Blin, Fedor V. Fomin, Pierre Fraigniaud, Sylvain Gay, Petr A. Golovach, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca (Université Paris Cité - IRIF - CNRS, France; University of Bergen, Norway; CNRS - Université de Paris, France; École Normale Supérieure, France; Universidad Adolfo Ibáñez, Chile; Universidad de Chile, Chile; Université d'Orléans, France) Article Search Article: stoc26main-p673-p STOC '26: "Path Cover, Hamiltonicity, ..." Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective Fedor V. Fomin, Petr A. Golovach, Nikola Jedličková, Jan Kratochvíl, Danil Sagunov, and Kirill Simonov (University of Bergen, Norway; Charles University, Czech Republic; Saint Petersburg State University, Russian Federation) Article Search Article: stoc26main-p127-p
	Golowich, Noah	STOC '26: "Improved Pseudorandom Codes ..." Improved Pseudorandom Codes from Permuted Puzzles Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, and Daniel Wichs (Columbia University, USA; Microsoft Research, USA; University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; Northeastern University, USA) Article Search Article: stoc26main-p1557-p
	Golrezaei, Negin	STOC '26: "Optimal Contest beyond Convexity ..." Optimal Contest beyond Convexity Negin Golrezaei, MohammadTaghi Hajiaghayi, and Suho Shin (Massachusetts Institute of Technology, USA; University of Maryland, USA) Article Search Article: stoc26main-p69-p
	Göös, Mika	STOC '26: "Monotone Circuit Complexity ..." Monotone Circuit Complexity of Matching Bruno Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov (University of Oxford, UK; EPFL, Switzerland; Université de Montréal, Canada) Article Search Article: stoc26main-p518-p STOC '26: "Pseudodeterministic Communication ..." Pseudodeterministic Communication Complexity Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, and Weiqiang Yuan (EPFL, Switzerland; University of British Columbia, Canada; Université de Montréal, Canada) Article Search Article: stoc26main-p1390-p STOC '26: "Sampling Permutations with ..." Sampling Permutations with Cell Probes Is Hard Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, and Dmitry Sokolov (Technion, Israel; EPFL, Switzerland; Université de Montréal, Canada) Article Search Article: stoc26main-p108-p
	Gopalan, Parikshit	STOC '26: "Efficient Calibration for ..." Efficient Calibration for Decision Making Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar, and Pranay Tankala (Apple, USA; University of Texas at Austin, USA; Harvard University, USA) Article Search Article: stoc26main-p1666-p
	Govindasamy, Nashlen	STOC '26: "Lower Bounds against the Ideal ..." Lower Bounds against the Ideal Proof System in Finite Fields Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu, and Iddo Tzameret (Imperial College London, UK) Article Search Article: stoc26main-p4-p
	Goyal, Rohan	STOC '26: "Optimal Proximity Gaps for ..." Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes Rohan Goyal and Venkatesan Guruswami (Massachusetts Institute of Technology, USA; University of California at Berkeley, USA) Article Search Article: stoc26main-p809-p
	Grandoni, Fabrizio	STOC '26: "A (4+ϵ)-Approximation for ..." A (4+ϵ)-Approximation for Euclidean 𝑘-Means via Non-monotone Dual-Fitting Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, and Ernest van Wijland (Stanford University, USA; Google Research, France; IDSIA at USI-SUPSI, Switzerland; University of Michigan, USA; Université Paris-Cité - CNRS, France) Article Search Article: stoc26main-p1152-p STOC '26: "Improved Approximation Algorithms ..." Improved Approximation Algorithms for Non-preemptive Throughput Maximization Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, and Andreas Wiese (TU Munich, Germany; IDSIA at USI-SUPSI, Switzerland) Article Search Article: stoc26main-p1425-p
	Gray, Matthew	STOC '26: "A Meta-complexity Characterization ..." A Meta-complexity Characterization of Minimal Quantum Cryptography Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, and Xingjian Li (University of Oxford, UK; Tsinghua University, China; University of Washington, USA; EPFL, Switzerland) Article Search Article: stoc26main-p298-p
	Gribelyuk, Elena	STOC '26: "Adversarial Robustness on ..." Adversarial Robustness on Insertion-Deletion Streams Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou (Princeton University, USA; Carnegie Mellon University, USA; Texas A&M University, USA) Article Search Article: stoc26main-p2045-p
	Grigorescu, Elena	STOC '26: "Relaxed vs. Full Local Decodability ..." Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes Elena Grigorescu, Vinayak M. Kumar, Peter Manohar, and Geoffrey Mon (University of Waterloo, Canada; University of Texas at Austin, USA; Institute for Advanced Study at Princeton, USA) Article Search Article: stoc26main-p674-p
	Grochow, Joshua A.	STOC '26: "Polynomial Identity Testing ..." Polynomial Identity Testing and the Ideal Proof System: PIT Is in NP If and Only If IPS Can Be p-Simulated by a Cook-Reckhow Proof System Joshua A. Grochow (University of Colorado Boulder, USA) Article Search Article: stoc26main-p813-p
	Gryaznov, Svyatoslav	STOC '26: "The Weak Rank Principle: Lower ..." The Weak Rank Principle: Lower Bounds and Applications Michal Garlík, Svyatoslav Gryaznov, Hanlin Ren, and Iddo Tzameret (Imperial College London, UK; Institute for Advanced Study at Princeton, USA) Article Search Article: stoc26main-p65-p
	Gunn, Sam	STOC '26: "Improved Pseudorandom Codes ..." Improved Pseudorandom Codes from Permuted Puzzles Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, and Daniel Wichs (Columbia University, USA; Microsoft Research, USA; University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; Northeastern University, USA) Article Search Article: stoc26main-p1557-p
	Gupta, Anupam	STOC '26: "Steiner Forest: A Simplified ..." Steiner Forest: A Simplified Better-Than-2 Approximation Anupam Gupta and Vera Traub (New York University, USA; ETH Zurich, Switzerland) Article Search Article: stoc26main-p404-p STOC '26: "Combinatorial Optimization ..." Combinatorial Optimization using Comparison Oracles Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Pittu, Jon Schneider, and David P. Woodruff (Google Research, New-York, USA; Bocconi University, Italy; New York University, USA; Google Research, USA; University of Michigan, USA; Duke University, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p1341-p
	Gupta, Meghal	STOC '26: "Few Single-Qubit Measurements ..." Few Single-Qubit Measurements Suffice to Certify Any Quantum State Meghal Gupta, William He, and Ryan O'Donnell (University of California at Berkeley, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p26-p
	Gur, Tom	STOC '26: "3-Query RLDCs Are Strictly ..." 3-Query RLDCs Are Strictly Stronger Than 3-Query LDCs Tom Gur, Dor Minzer, Guy Weissenberg, and Kai Zhe Zheng (University of Cambridge, UK; Massachusetts Institute of Technology, USA; EPFL, Switzerland) Article Search Article: stoc26main-p741-p STOC '26: "Nearly Tight Lower Bounds ..." Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies Guy Goldberg, Tom Gur, and Sidhant Saraogi (Weizmann Institute of Science, Israel; University of Cambridge, UK; Georgetown University, USA) Article Search Article: stoc26main-p1782-p
	Gurjar, Rohit	STOC '26: "Learning Read-Once Determinants ..." Learning Read-Once Determinants and the Principal Minor Assignment Problem Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, and Chandan Saha (IISc Bangalore, India; IIT Kanpur, India; ISI Kolkata, India; IIT Bombay, India; Tata Institute of Fundamental Research, Mumbai, India) Article Search Article: stoc26main-p909-p
	Guruganesh, Guru	STOC '26: "Combinatorial Optimization ..." Combinatorial Optimization using Comparison Oracles Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Pittu, Jon Schneider, and David P. Woodruff (Google Research, New-York, USA; Bocconi University, Italy; New York University, USA; Google Research, USA; University of Michigan, USA; Duke University, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p1341-p
	Gurumukhani, Mohit	STOC '26: "Improved Bounds for Coin Flipping, ..." Improved Bounds for Coin Flipping, Leader Election, and Random Selection Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, and Rocco A. Servedio (Cornell University, USA; Columbia University, USA) Article Search Article: stoc26main-p777-p
	Guruswami, Venkatesan	STOC '26: "Optimal Proximity Gaps for ..." Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes Rohan Goyal and Venkatesan Guruswami (Massachusetts Institute of Technology, USA; University of California at Berkeley, USA) Article Search Article: stoc26main-p809-p
	Gutenberg, Maximilian Probst	STOC '26: "Reviving Thorup’s Shortcut ..." Reviving Thorup’s Shortcut Conjecture Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, and Leon Schiller (New York University, USA; Carnegie Mellon University, USA; ETH Zurich, Switzerland; INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; University of Michigan, USA; MPI-INF, Germany; Saarland University, Germany; Hasso Plattner Institute - University of Potsdam, Germany) Article Search Article: stoc26main-p292-p
	Haböck, Ulrich	STOC '26: "On Proximity Gaps of Reed-Solomon ..." On Proximity Gaps of Reed-Solomon Codes Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, and Shubhangi Saraf (StarkWare Industries, Israel; StarkWare Industries, Poland; University of Toronto, Canada) Article Search Article: stoc26main-p523-p
	Haeupler, Bernhard	STOC '26: "A Constant-Approximation Distance ..." A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures Bernhard Haeupler, Yaowei Long, Antti Roeyskoe, and Thatchaphol Saranurak (INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; ETH Zurich, Switzerland; University of Michigan, USA) Article Search Article: stoc26main-p454-p STOC '26: "Deterministic Negative-Weight ..." Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers Bernhard Haeupler, Yonggang Jiang, and Thatchaphol Saranurak (INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; ETH Zurich, Switzerland; MPI-INF, Germany; Saarland University, Germany; University of Michigan, USA) Article Search Article: stoc26main-p87-p STOC '26: "DAG Projections: Reducing ..." DAG Projections: Reducing Distance and Flow Problems to DAGs Bernhard Haeupler, Yonggang Jiang, and Thatchaphol Saranurak (INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; ETH Zurich, Switzerland; MPI-INF, Germany; Saarland University, Germany; University of Michigan, USA) Article Search Article: stoc26main-p1972-p STOC '26: "Reviving Thorup’s Shortcut ..." Reviving Thorup’s Shortcut Conjecture Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, and Leon Schiller (New York University, USA; Carnegie Mellon University, USA; ETH Zurich, Switzerland; INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; University of Michigan, USA; MPI-INF, Germany; Saarland University, Germany; Hasso Plattner Institute - University of Potsdam, Germany) Article Search Article: stoc26main-p292-p
	Haferkamp, Jonas	STOC '26: "Separating QMA from QCMA with ..." Separating QMA from QCMA with a Classical Oracle John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, and Mark Zhandry (Columbia University, USA; Saarland University, Germany; University of Washington, USA; NTT Research, USA; Stanford University, USA) Article Search Article: stoc26main-p275-p
	Hair, Isaac M.	STOC '26: "SVPp Is ..." SVPp Is NP-Hard for All p > 2, Even to Approximate within a Factor of 2log1-εn Isaac M. Hair and Amit Sahai (University of California at Santa Barbara, USA; University of California at Los Angeles, USA) Article Search Article: stoc26main-p958-p
	Hajiaghayi, MohammadTaghi	STOC '26: "Optimal Contest beyond Convexity ..." Optimal Contest beyond Convexity Negin Golrezaei, MohammadTaghi Hajiaghayi, and Suho Shin (Massachusetts Institute of Technology, USA; University of Maryland, USA) Article Search Article: stoc26main-p69-p
	Halldórsson, Magnús	STOC '26: "Sublogarithmic Distributed ..." Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors Maxime Flin, Magnús Halldórsson, Manuel Jakob, and Yannic Maus (Aalto University, Finland; Reykjavik University, Iceland; TU Graz, Austria) Article Search Article: stoc26main-p1266-p
	Hanneke, Steve	STOC '26: "Sample Complexity of Agnostic ..." Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, and Qian Zhang (Tel Aviv University, Israel; Google Research, Israel; Purdue University, USA; Technion, Israel) Article Search Article: stoc26main-p308-p STOC '26: "On the Learning Curves of ..." On the Learning Curves of Revenue Maximization Steve Hanneke, Alkis Kalavasis, Shay Moran, and Grigoris Velegkas (Purdue University, USA; Yale University, USA; Technion, Israel; Google Research, USA) Article Search Article: stoc26main-p38-p
	Hao, Zihan	STOC '26: "On the Need for (Quantum) ..." On the Need for (Quantum) Memory with Short Outputs Zihan Hao, Qipeng Liu, and Zikuan Huang (University of California at San Diego, USA; Tsinghua University, China) Article Search Article: stoc26main-p1237-p
	Haqi, Alireza	STOC '26: "Parallel Sampling via Autospeculation ..." Parallel Sampling via Autospeculation Nima Anari, Carlo Baronio, CJ Chen, Alireza Haqi, Frederic Koehler, Anqi Li, and Thuy-Duong Vuong (Stanford University, USA; University of Arizona, USA; University of Chicago, USA; University of California at San Diego, USA) Article Search Article: stoc26main-p524-p
	Harms, Nathaniel	STOC '26: "Pseudodeterministic Communication ..." Pseudodeterministic Communication Complexity Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, and Weiqiang Yuan (EPFL, Switzerland; University of British Columbia, Canada; Université de Montréal, Canada) Article Search Article: stoc26main-p1390-p
	Harsha, Prahladh	STOC '26: "Deterministic List Decoding ..." Deterministic List Decoding of Reed-Solomon Codes Soham Chatterjee, Mrinal Kumar, and Prahladh Harsha (Tata Institute of Fundamental Research, Mumbai, India) Article Search Article: stoc26main-p1402-p
	Hastings, Jabari	STOC '26: "A Unified Approach to Memory-Sample ..." A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures Sumegha Garg, Jabari Hastings, Chirag Pabbaraju, and Vatsal Sharan (Rutgers University, USA; Stanford University, USA; University of Southern California, USA) Article Search Article: stoc26main-p85-p
	Hatami, Hamed	STOC '26: "Borsuk-Ulam and Replicable ..." Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, and Sivan Tretiak (McGill University, Canada; Ohio State University, USA) Article Search Article: stoc26main-p250-p
	Hatami, Pooya	STOC '26: "Borsuk-Ulam and Replicable ..." Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, and Sivan Tretiak (McGill University, Canada; Ohio State University, USA) Article Search Article: stoc26main-p250-p
	Haun, Deborah	STOC '26: "Dynamic Meta-Kernelization ..." Dynamic Meta-Kernelization Christian Bertram, Deborah Haun, Mads Vestergaard Jensen, and Tuukka Korhonen (University of Copenhagen, Denmark; KIT, Germany) Article Search Article: stoc26main-p269-p
	Hązła, Jan	STOC '26: "Generalized Samorodnitsky ..." Generalized Samorodnitsky Noisy Function Inequalities, with Applications to Error-Correcting Codes Olakunle Sunday Abawonse, Jan Hązła, and Ryan O'Donnell (AIMS, Rwanda; Carnegie Mellon University, USA) Article Search Article: stoc26main-p175-p
	He, William	STOC '26: "Few Single-Qubit Measurements ..." Few Single-Qubit Measurements Suffice to Certify Any Quantum State Meghal Gupta, William He, and Ryan O'Donnell (University of California at Berkeley, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p26-p
	Hecht, Yahli	STOC '26: "Deterministic Hardness of ..." Deterministic Hardness of Approximation of Unique-SVP and GapSVP in ℓp Norms for p<2 Yahli Hecht and Muli Safra (Tel Aviv University, Israel) Article Search Article: stoc26main-p388-p
	Helsen, Jonas	STOC '26: "Clifford Testing: Algorithms ..." Clifford Testing: Algorithms and Lower Bounds Marcel Hinsche, Zongbo Bao, Phillipe van Dordrecht, Jens Eisert, Jop Briet, and Jonas Helsen (FU Berlin, Germany; CWI, Netherlands; QuSoft, Netherlands) Article Search Article: stoc26main-p379-p
	Helton, J. William	STOC '26: "Quantum Precomputation: Parallelizing ..." Quantum Precomputation: Parallelizing Cascade Circuits and the Moore–Nilsson Conjecture Is False Adam Bene Watts, Charles R. Chen, J. William Helton, and Joseph Slote (University of Calgary, Canada; University of California at San Diego, USA; University of Washington, USA) Article Search Article: stoc26main-p487-p
	Henzinger, Monika	STOC '26: "An Improved Quality Hierarchical ..." An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time Monika Henzinger, Robin Münk, and Harald Räcke (IST Austria, Austria; TU Munich, Germany) Article Search Article: stoc26main-p678-p
	Hershkowitz, D. Ellis	STOC '26: "Planar Length-Constrained ..." Planar Length-Constrained Minimum Spanning Trees D. Ellis Hershkowitz and Richard Z. Huang (Brown University, USA) In length-constrained minimum spanning tree (MST) we are given an n-node graph G = (V,E) with edge weights w : E → ℤ≥ 0 and edge lengths l: E → ℤ≥ 0 along with a root node r ∈ V and a length constraint h ∈ ℤ≥ 0. Our goal is to output a spanning tree of minimum weight according to w in which every node is at distance at most h from r according to l. We give a polynomial-time algorithm for planar graphs which, for any constant є > 0, outputs an O(log1+є n)-approximate solution with every node at distance at most (1+є)h from r. Our algorithm is based on new length-constrained versions of classic planar separators and divisions which may be of independent interest. Additionally, our algorithm works for length-constrained Steiner tree and bounds the integrality gap of the natural linear program as O(log2 n /є), again with (1+є) slack in the length constraint. Complementing this, we show that any algorithm on general graphs for length-constrained MST in which nodes are at most 2h from r cannot achieve an approximation of O(log2−є n) for any constant є > 0 under standard complexity assumptions; as such, our results separate the approximability of length-constrained MST in planar and general graphs. Article Search Article: stoc26main-p778-p
	Hertrich, Christoph	STOC '26: "Better Neural Network Expressivity: ..." Better Neural Network Expressivity: Subdividing the Simplex Egor Bakaev, Florestan Brunck, Christoph Hertrich, Jack Stade, and Amir Yehudayoff (University of Copenhagen, Denmark; University of Technology Nuremberg, Germany; Technion, Israel) Article Search Article: stoc26main-p234-p
	Hinsche, Marcel	STOC '26: "Clifford Testing: Algorithms ..." Clifford Testing: Algorithms and Lower Bounds Marcel Hinsche, Zongbo Bao, Phillipe van Dordrecht, Jens Eisert, Jop Briet, and Jonas Helsen (FU Berlin, Germany; CWI, Netherlands; QuSoft, Netherlands) Article Search Article: stoc26main-p379-p
	Hirahara, Shuichi	STOC '26: "A Sharp Characterization of ..." A Sharp Characterization of Pessiland Shuichi Hirahara and Mikito Nanashima (National Institute of Informatics, Tokyo, Japan; Institute of Science Tokyo, Japan) Article Search Article: stoc26main-p177-p STOC '26: "Complexity-Theoretic Universal ..." Complexity-Theoretic Universal Inductive Inference Shuichi Hirahara and Mikito Nanashima (National Institute of Informatics, Tokyo, Japan; Institute of Science Tokyo, Japan) Article Search Article: stoc26main-p181-p STOC '26: "Optimal Random Self-Reductions ..." Optimal Random Self-Reductions for All Linear Problems Shuichi Hirahara and Nobutaka Shimizu (National Institute of Informatics, Tokyo, Japan; Institute of Science Tokyo, Japan) Article Search Article: stoc26main-p264-p
	Hollender, Alexandros	STOC '26: "Fisher Markets with Approximately ..." Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos (Royal Holloway University of London, UK; University of Liverpool, UK; University of Oxford, UK; University of Essex, UK) Article Search Article: stoc26main-p474-p
	Hopkins, Max	STOC '26: "High Rate Efficient Local ..." High Rate Efficient Local List Decoding from HDX Yotam Dikstein, Max Hopkins, Toniann Pitassi, and Russell Impagliazzo (Institute for Advanced Study at Princeton, USA; Princeton University, USA; Columbia University, USA; University of California at San Diego, USA) Article Search Article: stoc26main-p1064-p
	Hopkins, Samuel B.	STOC '26: "SNARGs for NP and Non-signaling ..." SNARGs for NP and Non-signaling PCPs, Revisited Lalita Devadas, Samuel B. Hopkins, Yael Kalai, Pravesh K. Kothari, Alex Lombardi, and Surya Mathialagan (Massachusetts Institute of Technology, USA; Princeton University, USA; NTT Research, USA) Article Search Article: stoc26main-p297-p
	Hoppenworth, Gary	STOC '26: "Reviving Thorup’s Shortcut ..." Reviving Thorup’s Shortcut Conjecture Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, and Leon Schiller (New York University, USA; Carnegie Mellon University, USA; ETH Zurich, Switzerland; INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; University of Michigan, USA; MPI-INF, Germany; Saarland University, Germany; Hasso Plattner Institute - University of Potsdam, Germany) Article Search Article: stoc26main-p292-p
	House, Matthew L.	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Hsieh, Jun-Ting	STOC '26: "Rigorous Implications of the ..." Rigorous Implications of the Low-Degree Heuristic Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari, Jerry Li, Sidhanth Mohanty, and Stefan Tiegel (Massachusetts Institute of Technology, USA; University of California at San Diego, USA; Princeton University, USA; University of Washington, USA; Northwestern University, USA) Article Search Article: stoc26main-p995-p
	Hsieh, Yao-Ching	STOC '26: "SNARGs for NP from Unprovability ..." SNARGs for NP from Unprovability of Mathematical Theorems (Or: How to Use the Simplicity of Cryptographic Reasoning) Yao-Ching Hsieh, Abhishek Jain, Jiatu Li, and Surya Mathialagan (University of Washington, USA; NTT Research, USA; Johns Hopkins University, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p24-p
	Hu, Jinqiao	STOC '26: "Failure of Symmetry of Information ..." Failure of Symmetry of Information for Randomized Computations Jinqiao Hu, Yahel Manor, and Igor C. Oliveira (University of Warwick, UK; University of Haifa, Israel) Article Search Article: stoc26main-p834-p
	Hu, Yang	STOC '26: "Nash Social Welfare with Submodular ..." Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps Xiaohui Bei, Yuda Feng, Yang Hu, Shi Li, and Ruilong Zhang (Nanyang Technological University, Singapore; Nanjing University, China; Tsinghua University, China; TU Munich, Germany) Article Search Article: stoc26main-p1408-p
	Hu, Zihan	STOC '26: "A Meta-complexity Characterization ..." A Meta-complexity Characterization of Minimal Quantum Cryptography Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, and Xingjian Li (University of Oxford, UK; Tsinghua University, China; University of Washington, USA; EPFL, Switzerland) Article Search Article: stoc26main-p298-p
	Huang, Brice	STOC '26: "On Zeros and Algorithms for ..." On Zeros and Algorithms for Disordered Systems: Mean-Field Spin Glasses Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, and Guus Regts (CWI, Netherlands; Stanford University, USA; Massachusetts Institute of Technology, USA; University of Amsterdam, Netherlands) Article Search Article: stoc26main-p245-p
	Huang, Neng	STOC '26: "Improved Approximation Algorithms ..." Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes Joshua Brakensiek, Neng Huang, Aaron Potechin, and Uri Zwick (University of California at Berkeley, USA; University of Michigan, USA; University of Chicago, USA; Tel Aviv University, Israel) Article Search Article: stoc26main-p713-p
	Huang, Richard Z.	STOC '26: "Planar Length-Constrained ..." Planar Length-Constrained Minimum Spanning Trees D. Ellis Hershkowitz and Richard Z. Huang (Brown University, USA) In length-constrained minimum spanning tree (MST) we are given an n-node graph G = (V,E) with edge weights w : E → ℤ≥ 0 and edge lengths l: E → ℤ≥ 0 along with a root node r ∈ V and a length constraint h ∈ ℤ≥ 0. Our goal is to output a spanning tree of minimum weight according to w in which every node is at distance at most h from r according to l. We give a polynomial-time algorithm for planar graphs which, for any constant є > 0, outputs an O(log1+є n)-approximate solution with every node at distance at most (1+є)h from r. Our algorithm is based on new length-constrained versions of classic planar separators and divisions which may be of independent interest. Additionally, our algorithm works for length-constrained Steiner tree and bounds the integrality gap of the natural linear program as O(log2 n /є), again with (1+є) slack in the length constraint. Complementing this, we show that any algorithm on general graphs for length-constrained MST in which nodes are at most 2h from r cannot achieve an approximation of O(log2−є n) for any constant є > 0 under standard complexity assumptions; as such, our results separate the approximability of length-constrained MST in planar and general graphs. Article Search Article: stoc26main-p778-p
	Huang, Zikuan	STOC '26: "On the Need for (Quantum) ..." On the Need for (Quantum) Memory with Short Outputs Zihan Hao, Qipeng Liu, and Zikuan Huang (University of California at San Diego, USA; Tsinghua University, China) Article Search Article: stoc26main-p1237-p
	Huiberts, Sophie	STOC '26: "Beyond Smoothed Analysis: ..." Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book Eleon Bach, Alexander E. Black, Sophie Huiberts, and Sean Kafer (TU Munich, Germany; Bowdoin College, USA; LIMOS - CNRS - University Clermont Auvergne, France; Illinois State University, USA) Article Search Article: stoc26main-p103-p
	Hunter, Rachel	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Iijil	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Impagliazzo, Russell	STOC '26: "Lower Bounds for Near-Quadratic-Depth ..." Lower Bounds for Near-Quadratic-Depth Resolution over Parities Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, and Russell Impagliazzo (Tata Institute of Fundamental Research, Mumbai, India; University of California at San Diego, USA) Article Search Article: stoc26main-p416-p STOC '26: "High Rate Efficient Local ..." High Rate Efficient Local List Decoding from HDX Yotam Dikstein, Max Hopkins, Toniann Pitassi, and Russell Impagliazzo (Institute for Advanced Study at Princeton, USA; Princeton University, USA; Columbia University, USA; University of California at San Diego, USA) Article Search Article: stoc26main-p1064-p
	Inamdar, Tanmay	STOC '26: "Oracle Subset Problems: A ..." Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks Ishan Chakraborty, Tanmay Inamdar, Ariel Kulik, Madhumita Kundu, and Saket Saurabh (Institute of Mathematical Sciences, Chennai, India; IIT Jodhpur, India; Ben-Gurion University of the Negev, Israel; University of Bergen, Norway; Institute of Mathematical Sciences, India) Article Search Article: stoc26main-p443-p
	Indyk, Piotr	STOC '26: "Fast and Compact Random Mappings ..." Fast and Compact Random Mappings with Uniform Guarantees and Applications Ying Feng and Piotr Indyk (Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p303-p
	Ishai, Yuval	STOC '26: "Shuffling Is Universal: Statistical ..." Shuffling Is Universal: Statistical Additive Randomized Encodings for All Functions Nir Bitansky, Saroja Erabelli, Rachit Garg, and Yuval Ishai (New York University, USA; Technion, Israel; AWS, USA) Article Search Article: stoc26main-p1125-p STOC '26: "Secret-Key PIR from Random ..." Secret-Key PIR from Random Linear Codes Caicai Chen, Yuval Ishai, Tamer Mour, and Alon Rosen (Bocconi University, Italy; Technion, Israel; AWS, USA) Article Search Article: stoc26main-p1368-p
	Itsykson, Dmitry	STOC '26: "Strong ETH Holds for Bounded-Depth ..." Strong ETH Holds for Bounded-Depth Resolution over Parities Klim Efremenko and Dmitry Itsykson (Ben-Gurion University of the Negev, Israel) Article Search Article: stoc26main-p393-p
	Iyer, Vishnu	STOC '26: "Efficient Quantum Hermite ..." Efficient Quantum Hermite Transform Siddhartha Jain, Vishnu Iyer, Rolando D. Somma, Ning Bao, and Stephen Jordan (University of Texas at Austin, USA; Google, USA; Northeastern University, USA; Brookhaven National Laboratory, USA) Article Search Article: stoc26main-p255-p
	Jain, Abhishek	STOC '26: "SNARGs for NP from Unprovability ..." SNARGs for NP from Unprovability of Mathematical Theorems (Or: How to Use the Simplicity of Cryptographic Reasoning) Yao-Ching Hsieh, Abhishek Jain, Jiatu Li, and Surya Mathialagan (University of Washington, USA; NTT Research, USA; Johns Hopkins University, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p24-p
	Jain, Rhea	STOC '26: "A Polylogarithmic Approximation ..." A Polylogarithmic Approximation for Buy-at-Bulk Network Design with Protection Chandra Chekuri and Rhea Jain (University of Illinois at Urbana-Champaign, USA) Article Search Article: stoc26main-p1857-p
	Jain, Siddhartha	STOC '26: "Efficient Quantum Hermite ..." Efficient Quantum Hermite Transform Siddhartha Jain, Vishnu Iyer, Rolando D. Somma, Ning Bao, and Stephen Jordan (University of Texas at Austin, USA; Google, USA; Northeastern University, USA; Brookhaven National Laboratory, USA) Article Search Article: stoc26main-p255-p
	Jakob, Manuel	STOC '26: "Sublogarithmic Distributed ..." Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors Maxime Flin, Magnús Halldórsson, Manuel Jakob, and Yannic Maus (Aalto University, Finland; Reykjavik University, Iceland; TU Graz, Austria) Article Search Article: stoc26main-p1266-p
	Jayaram, Rajesh	STOC '26: "Near-Optimal Directed Euclidean ..." Near-Optimal Directed Euclidean Spanners in High Dimensions Rajesh Jayaram, Shyamal Patel, Cliff Stein, Erik Waingarten, and Tian Zhang (Google Research, USA; Columbia University, USA; University of Pennsylvania, USA) Article Search Article: stoc26main-p703-p
	Jedličková, Nikola	STOC '26: "Path Cover, Hamiltonicity, ..." Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective Fedor V. Fomin, Petr A. Golovach, Nikola Jedličková, Jan Kratochvíl, Danil Sagunov, and Kirill Simonov (University of Bergen, Norway; Charles University, Czech Republic; Saint Petersburg State University, Russian Federation) Article Search Article: stoc26main-p127-p
	Jensen, Mads Vestergaard	STOC '26: "Dynamic Meta-Kernelization ..." Dynamic Meta-Kernelization Christian Bertram, Deborah Haun, Mads Vestergaard Jensen, and Tuukka Korhonen (University of Copenhagen, Denmark; KIT, Germany) Article Search Article: stoc26main-p269-p
	Jeronimo, Fernando Granha	STOC '26: "Probabilistic Guarantees to ..." Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes Fernando Granha Jeronimo and Nikhil Shagrithaya (University of Illinois at Urbana-Champaign, USA; University of Michigan at Ann Arbor, USA) Article Search Article: stoc26main-p352-p
	Ji, Zhengfeng	STOC '26: "A Meta-complexity Characterization ..." A Meta-complexity Characterization of Minimal Quantum Cryptography Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, and Xingjian Li (University of Oxford, UK; Tsinghua University, China; University of Washington, USA; EPFL, Switzerland) Article Search Article: stoc26main-p298-p
	Jiang, Haotian	STOC '26: "Decoupling via Affine Spectral-Independence: ..." Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds beyond Banaszczyk Nikhil Bansal and Haotian Jiang (University of Michigan, USA; University of Chicago, USA) Article Search Article: stoc26main-p206-p
	Jiang, Max	STOC '26: "Semi-streaming Matching in ..." Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints Sepehr Assadi, Max Jiang, and Mars Xiang (University of Waterloo, Canada) Article Search Article: stoc26main-p429-p
	Jiang, Shunhua	STOC '26: "Approximate Orthogonal Vectors ..." Approximate Orthogonal Vectors and Diameter via Regularity Lemma Alexandr Andoni, Shunhua Jiang, and Stepan Zharkov (Columbia University, USA; Hebrew University of Jerusalem, Israel) Article Search Article: stoc26main-p734-p
	Jiang, Yonggang	STOC '26: "Deterministic Negative-Weight ..." Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers Bernhard Haeupler, Yonggang Jiang, and Thatchaphol Saranurak (INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; ETH Zurich, Switzerland; MPI-INF, Germany; Saarland University, Germany; University of Michigan, USA) Article Search Article: stoc26main-p87-p STOC '26: "DAG Projections: Reducing ..." DAG Projections: Reducing Distance and Flow Problems to DAGs Bernhard Haeupler, Yonggang Jiang, and Thatchaphol Saranurak (INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; ETH Zurich, Switzerland; MPI-INF, Germany; Saarland University, Germany; University of Michigan, USA) Article Search Article: stoc26main-p1972-p STOC '26: "Reviving Thorup’s Shortcut ..." Reviving Thorup’s Shortcut Conjecture Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, and Leon Schiller (New York University, USA; Carnegie Mellon University, USA; ETH Zurich, Switzerland; INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; University of Michigan, USA; MPI-INF, Germany; Saarland University, Germany; Hasso Plattner Institute - University of Potsdam, Germany) Article Search Article: stoc26main-p292-p
	Jin, Ce	STOC '26: "Memory Reallocation with Polylogarithmic ..." Memory Reallocation with Polylogarithmic Overhead Ce Jin (University of California at Berkeley, USA) The Memory Reallocation problem asks to dynamically maintain an assignment of given objects of various sizes to non-overlapping contiguous chunks of memory, while supporting updates (insertions/deletions) in an online fashion. The total size of live objects at any time is guaranteed to be at most a 1−є fraction of the total memory. To handle an online update, the allocator may rearrange the objects in memory to make space, and the overhead for this update is defined as the total size of moved objects divided by the size of the object being inserted/deleted. Our main result is an allocator with worst-case expected overhead polylog(є−1). This exponentially improves the previous worst-case expected overhead O(є−1/2) achieved by Farach-Colton, Kuszmaul, Sheffield, and Westover (2024), narrowing the gap towards the Ω(logє−1) lower bound. Our improvement is based on an application of the sunflower lemma previously used by Erdős and Sárk'ozy (1992) in the context of subset sums. Our allocator achieves polylogarithmic overhead only in expectation, and sometimes performs expensive rebuilds. Our second technical result shows that this is necessary: it is impossible to achieve subpolynomial overhead with high probability. Preprint Article: stoc26main-p510-p STOC '26: "Classifying Identities: Subcubic ..." Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection Bartłomiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin, Marvin Künnemann, Xiao Mao, and Mirza Redžić (University of Wrocław, Poland; MPI-INF, Germany; KIT, Germany; University of California at Berkeley, USA; Stanford University, USA) Article Search Article: stoc26main-p715-p
	Jin, Zhengzhong	STOC '26: "SNARKs from LWE via Non-black-Box ..." SNARKs from LWE via Non-black-Box Reductions Zhengzhong Jin, Mingqi Lu, and Bo Peng (Northeastern University, USA; Peking University, China) Article Search Article: stoc26main-p1088-p
	Jordan, Stephen	STOC '26: "Efficient Quantum Hermite ..." Efficient Quantum Hermite Transform Siddhartha Jain, Vishnu Iyer, Rolando D. Somma, Ning Bao, and Stephen Jordan (University of Texas at Austin, USA; Google, USA; Northeastern University, USA; Brookhaven National Laboratory, USA) Article Search Article: stoc26main-p255-p
	Joshi, Malvika Raj	STOC '26: "Improved Lower Bounds for ..." Improved Lower Bounds for QAC0 Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, and John Wright (University of California at Berkeley, USA) Article Search Article: stoc26main-p1703-p
	Kabanets, Valentine	STOC '26: "Kolmogorov’s Approach to ..." Kolmogorov’s Approach to P vs. NP: Chain Rules for Time-Bounded Kolmogorov Complexity Valentine Kabanets and Antonina Kolokolova (Simon Fraser University, Canada; Memorial University of Newfoundland, Canada) Article Search Article: stoc26main-p288-p
	Kądziołka, Maja	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Kafer, Sean	STOC '26: "Beyond Smoothed Analysis: ..." Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book Eleon Bach, Alexander E. Black, Sophie Huiberts, and Sean Kafer (TU Munich, Germany; Bowdoin College, USA; LIMOS - CNRS - University Clermont Auvergne, France; Illinois State University, USA) Article Search Article: stoc26main-p103-p
	Kalai, Yael	STOC '26: "SNARGs for NP and Non-signaling ..." SNARGs for NP and Non-signaling PCPs, Revisited Lalita Devadas, Samuel B. Hopkins, Yael Kalai, Pravesh K. Kothari, Alex Lombardi, and Surya Mathialagan (Massachusetts Institute of Technology, USA; Princeton University, USA; NTT Research, USA) Article Search Article: stoc26main-p297-p
	Kalavasis, Alkis	STOC '26: "Learning Mixture Models via ..." Learning Mixture Models via Efficient High-Dimensional Sparse Fourier Transforms Alkis Kalavasis, Pravesh K. Kothari, Shuchen Li, and Manolis Zampetakis (Yale University, USA; Princeton University, USA) Article Search Article: stoc26main-p1321-p STOC '26: "On the Learning Curves of ..." On the Learning Curves of Revenue Maximization Steve Hanneke, Alkis Kalavasis, Shay Moran, and Grigoris Velegkas (Purdue University, USA; Yale University, USA; Technion, Israel; Google Research, USA) Article Search Article: stoc26main-p38-p
	Kane, Daniel M.	STOC '26: "Rigorous Implications of the ..." Rigorous Implications of the Low-Degree Heuristic Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari, Jerry Li, Sidhanth Mohanty, and Stefan Tiegel (Massachusetts Institute of Technology, USA; University of California at San Diego, USA; Princeton University, USA; University of Washington, USA; Northwestern University, USA) Article Search Article: stoc26main-p995-p STOC '26: "High-Accuracy List-Decodable ..." High-Accuracy List-Decodable Mean Estimation Ziyun Chen, Spencer Compton, Daniel M. Kane, and Jerry Li (University of Washington, USA; Stanford University, USA; University of California at San Diego, USA) Article Search Article: stoc26main-p335-p
	Kar, Debajyoti	STOC '26: "Approximation Schemes and ..." Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations Debajyoti Kar, Arindam Khan, and Andreas Wiese (IISc Bengaluru, India; TU Munich, Germany) Article Search Article: stoc26main-p522-p
	Karmarkar, Ishani	STOC '26: "Solving Matrix Games with ..." Solving Matrix Games with Near-Optimal Matvec Complexity Ishani Karmarkar, Liam O'Carroll, and Aaron Sidford (Stanford University, USA) Article Search Article: stoc26main-p975-p
	Keller, Nathan	STOC '26: "Non-adaptive Cryptanalytic ..." Non-adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-Like Inequality for Permutations Itai Dinur, Nathan Keller, and Avichai Marmor (Ben-Gurion University of the Negev, Israel; Georgetown University, USA; Bar-Ilan University, Israel) Article Search Article: stoc26main-p879-p
	Kenneth-Mordoch, Yotam	STOC '26: "Faster All-Pairs Minimum Cut: ..." Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow Yotam Kenneth-Mordoch and Robert Krauthgamer (Weizmann Institute of Science, Israel) Article Search Article: stoc26main-p571-p
	Khan, Arindam	STOC '26: "Approximation Schemes and ..." Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations Debajyoti Kar, Arindam Khan, and Andreas Wiese (IISc Bengaluru, India; TU Munich, Germany) Article Search Article: stoc26main-p522-p
	Khanna, Sanjeev	STOC '26: "A Faster Deterministic Algorithm ..." A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching Julia Chuzhoy, Sanjeev Khanna, and Junkai Song (Toyota Technological Institute at Chicago, USA; University of Pennsylvania, USA) Article Search Article: stoc26main-p840-p
	Khesin, Andrey Boris	STOC '26: "Average-Case Complexity of ..." Average-Case Complexity of Quantum Stabilizer Decoding Andrey Boris Khesin, Jonathan Lu, Alexander Poremba, Akshar Ramkumar, and Vinod Vaikuntanathan (University of Oxford, UK; Massachusetts Institute of Technology, USA; Boston University, USA; California Institute of Technology, USA) Article Search Article: stoc26main-p373-p
	Khot, Subhash	STOC '26: "An Analytical Approach to ..." An Analytical Approach to Parallel Repetition via CSP Inverse Theorems Amey Bhangale, Mark Braverman, Subhash Khot, Yang Liu, Dor Minzer, and Kunal Mittal (University of California at Riverside, USA; Princeton University, USA; New York University, USA; Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p148-p
	Khoury, Seri	STOC '26: "Breaking Barriers for Distributed ..." Breaking Barriers for Distributed MIS by Faster Degree Reduction Seri Khoury and Aaron Schild (INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; Google Research, USA) Article Search Article: stoc26main-p470-p
	Kisfaludi-Bak, Sándor	STOC '26: "Approximation Schemes for ..." Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs Sándor Kisfaludi-Bak and Dániel Marx (Aalto University, Espoo, Finland; CISPA Helmholtz Center for Information Security, Germany) Article Search Article: stoc26main-p460-p
	Klein, Nathan	STOC '26: "A Strong Linear Programming ..." A Strong Linear Programming Relaxation for Weighted Tree Augmentation Vincent Cohen-Addad, Marina Drygala, Nathan Klein, and Ola Svensson (Google Research, France; EPFL, Switzerland; Boston University, USA) Article Search Article: stoc26main-p1669-p
	Kleinberg, Jon	STOC '26: "Language Generation and Identification ..." Language Generation and Identification from Partial Enumeration: Tight Density Bounds and Topological Characterizations Jon Kleinberg and Fan Wei (Cornell University, USA; Duke University, USA) Article Search Article: stoc26main-p926-p
	Klivans, Adam R.	STOC '26: "A Fully Polynomial-Time Algorithm ..." A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube Gautam Chandrasekaran, Adam R. Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan (University of Texas at Austin, USA) Article Search Article: stoc26main-p1095-p
	Koehler, Frederic	STOC '26: "Constructive Approximation ..." Constructive Approximation under Carleman’s Condition, with Applications to Smoothed Analysis Frederic Koehler and Beining Wu (University of Chicago, USA) Article Search Article: stoc26main-p521-p STOC '26: "Parallel Sampling via Autospeculation ..." Parallel Sampling via Autospeculation Nima Anari, Carlo Baronio, CJ Chen, Alireza Haqi, Frederic Koehler, Anqi Li, and Thuy-Duong Vuong (Stanford University, USA; University of Arizona, USA; University of Chicago, USA; University of California at San Diego, USA) Article Search Article: stoc26main-p524-p
	Kolbe, Benedikt	STOC '26: "Fine-Grained Complexity of ..." Fine-Grained Complexity of Continuous Euclidean k-Center Lotte Blank, Karl Bringmann, Parinya Chalermsook, Karthik C. S., Benedikt Kolbe, Hung Le, and Geert van Wordragen (University of Bonn, Germany; Saarland University, Germany; MPI-INF, Germany; University of Sheffield, UK; Rutgers University, USA; University of Massachusetts at Amherst, USA; Aalto University, Finland) Article Search Article: stoc26main-p171-p
	Kolokolova, Antonina	STOC '26: "Kolmogorov’s Approach to ..." Kolmogorov’s Approach to P vs. NP: Chain Rules for Time-Bounded Kolmogorov Complexity Valentine Kabanets and Antonina Kolokolova (Simon Fraser University, Canada; Memorial University of Newfoundland, Canada) Article Search Article: stoc26main-p288-p
	Komargodski, Ilan	STOC '26: "Sub-linear Secure Broadcast ..." Sub-linear Secure Broadcast and Applications Yuval Gelles, Ilan Komargodski, and Merav Parter (Hebrew University of Jerusalem, Israel; Weizmann Institute of Science, Israel) Article Search Article: stoc26main-p851-p
	Kopelowitz, Tsvi	STOC '26: "Contention Resolution, with ..." Contention Resolution, with and without a Global Clock Zixi Cai, Kuowen Chen, Shengquan Du, Tsvi Kopelowitz, Seth Pettie, and Ben Plosk (Tsinghua University, China; Bar-Ilan University, Israel; University of Michigan, USA) Article Search Article: stoc26main-p360-p
	Kopparty, Swastik	STOC '26: "On Proximity Gaps of Reed-Solomon ..." On Proximity Gaps of Reed-Solomon Codes Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, and Shubhangi Saraf (StarkWare Industries, Israel; StarkWare Industries, Poland; University of Toronto, Canada) Article Search Article: stoc26main-p523-p
	Koren, Tomer	STOC '26: "Sample Complexity of Agnostic ..." Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, and Qian Zhang (Tel Aviv University, Israel; Google Research, Israel; Purdue University, USA; Technion, Israel) Article Search Article: stoc26main-p308-p
	Korhonen, Tuukka	STOC '26: "Dynamic Meta-Kernelization ..." Dynamic Meta-Kernelization Christian Bertram, Deborah Haun, Mads Vestergaard Jensen, and Tuukka Korhonen (University of Copenhagen, Denmark; KIT, Germany) Article Search Article: stoc26main-p269-p STOC '26: "Separator Theorem for Minor-Free ..." Separator Theorem for Minor-Free Graphs in Linear Time Édouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, and Tomáš Masařík (CNRS, France; University of Copenhagen, Denmark; University of Massachusetts at Amherst, USA; Carnegie Mellon University, USA; University of Warsaw, Poland) Article Search Article: stoc26main-p31-p
	Kothari, Pravesh K.	STOC '26: "Rigorous Implications of the ..." Rigorous Implications of the Low-Degree Heuristic Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari, Jerry Li, Sidhanth Mohanty, and Stefan Tiegel (Massachusetts Institute of Technology, USA; University of California at San Diego, USA; Princeton University, USA; University of Washington, USA; Northwestern University, USA) Article Search Article: stoc26main-p995-p STOC '26: "Learning Mixture Models via ..." Learning Mixture Models via Efficient High-Dimensional Sparse Fourier Transforms Alkis Kalavasis, Pravesh K. Kothari, Shuchen Li, and Manolis Zampetakis (Yale University, USA; Princeton University, USA) Article Search Article: stoc26main-p1321-p STOC '26: "SNARGs for NP and Non-signaling ..." SNARGs for NP and Non-signaling PCPs, Revisited Lalita Devadas, Samuel B. Hopkins, Yael Kalai, Pravesh K. Kothari, Alex Lombardi, and Surya Mathialagan (Massachusetts Institute of Technology, USA; Princeton University, USA; NTT Research, USA) Article Search Article: stoc26main-p297-p
	Kothari, Robin	STOC '26: "No Exponential Quantum Speedup ..." No Exponential Quantum Speedup for SIS∞ Anymore Robin Kothari, Ryan O'Donnell, and Kewen Wu (Google Quantum AI, USA; Carnegie Mellon University, USA; Institute for Advanced Study at Princeton, USA) In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case ℓ∞-Short Integer Solution (SIS∞) problem, in a parameter range outside the normal range of cryptographic interest, but still with no known efficient classical algorithm. This was particularly exciting since SIS∞ is a simple problem without structure, and their algorithmic techniques were different from those used in prior exponential quantum speedups. We present efficient classical algorithms for all of the SIS∞ and (more general) Constrained Integer Solution problems studied in their paper, showing there is no exponential quantum speedup anymore. Article Search Article: stoc26main-p52-p
	Koucký, Michal	STOC '26: "The Natural Proofs Barrier ..." The Natural Proofs Barrier against Data-Structure Lower-Bounds Bruno Loff, Michal Koucký, Tulasimohan Molli, and Michael E. Saks (LASIGE, Portugal; University of Lisbon, Portugal; Charles University, Czech Republic; Rutgers University, USA) Article Search Article: stoc26main-p628-p
	Krapivin, Andrew	STOC '26: "Greedy Open Addressing Revisited: ..." Greedy Open Addressing Revisited: Beyond Yao’s Lower Bound Martín Farach-Colton, Andrew Krapivin, and William Kuszmaul (New York University, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p516-p STOC '26: "Optimal and Efficient Partite ..." Optimal and Efficient Partite Decompositions of Hypergraphs Andrew Krapivin, Benjamin Przybocki, Nicolás Sanhueza-Matamala, and Bernardo Subercaseaux (Carnegie Mellon University, USA; Universidad de Concepción, Chile) Article Search Article: stoc26main-p1693-p
	Kratochvíl, Jan	STOC '26: "Path Cover, Hamiltonicity, ..." Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective Fedor V. Fomin, Petr A. Golovach, Nikola Jedličková, Jan Kratochvíl, Danil Sagunov, and Kirill Simonov (University of Bergen, Norway; Charles University, Czech Republic; Saint Petersburg State University, Russian Federation) Article Search Article: stoc26main-p127-p
	Krauthgamer, Robert	STOC '26: "Faster All-Pairs Minimum Cut: ..." Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow Yotam Kenneth-Mordoch and Robert Krauthgamer (Weizmann Institute of Science, Israel) Article Search Article: stoc26main-p571-p
	Kroer, Christian	STOC '26: "Tâtonnement Dynamics for ..." Tâtonnement Dynamics for Fisher Markets with Chores Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta, and Tianlong Nan (University of Illinois at Urbana-Champaign, USA; Columbia University, USA) Article Search Article: stoc26main-p183-p
	Kropitz, Pavel	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Kulik, Ariel	STOC '26: "Oracle Subset Problems: A ..." Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks Ishan Chakraborty, Tanmay Inamdar, Ariel Kulik, Madhumita Kundu, and Saket Saurabh (Institute of Mathematical Sciences, Chennai, India; IIT Jodhpur, India; Ben-Gurion University of the Negev, Israel; University of Bergen, Norway; Institute of Mathematical Sciences, India) Article Search Article: stoc26main-p443-p STOC '26: "A Poisson Process for Submodular ..." A Poisson Process for Submodular Maximization Amit Ganz, Ariel Kulik, Roy Schwartz, and Mohit Singh (Technion, Israel; Ben-Gurion University of the Negev, Israel; Georgia Institute of Technology, USA) Article Search Article: stoc26main-p1663-p
	Kumar, Mrinal	STOC '26: "Closure under Factorization ..." Closure under Factorization from a Result of Furstenberg Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, and Shubhangi Saraf (University of Toronto, Canada; Tata Institute of Fundamental Research, Mumbai, India) Article Search Article: stoc26main-p81-p STOC '26: "Deterministic List Decoding ..." Deterministic List Decoding of Reed-Solomon Codes Soham Chatterjee, Mrinal Kumar, and Prahladh Harsha (Tata Institute of Fundamental Research, Mumbai, India) Article Search Article: stoc26main-p1402-p
	Kumar, Vinayak M.	STOC '26: "Relaxed vs. Full Local Decodability ..." Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes Elena Grigorescu, Vinayak M. Kumar, Peter Manohar, and Geoffrey Mon (University of Waterloo, Canada; University of Texas at Austin, USA; Institute for Advanced Study at Princeton, USA) Article Search Article: stoc26main-p674-p
	Kundu, Madhumita	STOC '26: "Oracle Subset Problems: A ..." Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks Ishan Chakraborty, Tanmay Inamdar, Ariel Kulik, Madhumita Kundu, and Saket Saurabh (Institute of Mathematical Sciences, Chennai, India; IIT Jodhpur, India; Ben-Gurion University of the Negev, Israel; University of Bergen, Norway; Institute of Mathematical Sciences, India) Article Search Article: stoc26main-p443-p
	Kunisky, Dmitriy	STOC '26: "Computational and Statistical ..." Computational and Statistical Lower Bounds for Low-Rank Estimation under General Inhomogeneous Noise Debsurya De and Dmitriy Kunisky (Johns Hopkins University, USA) Article Search Article: stoc26main-p1352-p
	Künnemann, Marvin	STOC '26: "Classifying Identities: Subcubic ..." Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection Bartłomiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin, Marvin Künnemann, Xiao Mao, and Mirza Redžić (University of Wrocław, Poland; MPI-INF, Germany; KIT, Germany; University of California at Berkeley, USA; Stanford University, USA) Article Search Article: stoc26main-p715-p
	Kuszmaul, William	STOC '26: "Greedy Open Addressing Revisited: ..." Greedy Open Addressing Revisited: Beyond Yao’s Lower Bound Martín Farach-Colton, Andrew Krapivin, and William Kuszmaul (New York University, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p516-p
	Labourel, Arnaud	STOC '26: "Can Like Attract Like? A Study ..." Can Like Attract Like? A Study of Homonymous Gathering in Networks Yoann Dieudonné, Stéphane Devismes, and Arnaud Labourel (MIS - Université de Picardie Jules Verne, France; LIS - Aix-Marseille University, France) Article Search Article: stoc26main-p403-p
	Lalov, Chavdar	STOC '26: "Borsuk-Ulam and Replicable ..." Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, and Sivan Tretiak (McGill University, Canada; Ohio State University, USA) Article Search Article: stoc26main-p250-p
	Larsen, Kasper Green	STOC '26: "The Sample Complexity of Replicable ..." The Sample Complexity of Replicable Realizable PAC Learning Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju, and Clement Svendsen (Aarhus University, Denmark; Stanford University, USA) Article Search Article: stoc26main-p1419-p
	Lau, Lap Chi	STOC '26: "Derandomizing Matrix Concentration ..." Derandomizing Matrix Concentration Inequalities from Free Probability Robert Wang, Lap Chi Lau, and Hong Zhou (University of Waterloo, Canada; Fuzhou University, China) Article Search Article: stoc26main-p209-p
	Le, Hung	STOC '26: "Fine-Grained Complexity of ..." Fine-Grained Complexity of Continuous Euclidean k-Center Lotte Blank, Karl Bringmann, Parinya Chalermsook, Karthik C. S., Benedikt Kolbe, Hung Le, and Geert van Wordragen (University of Bonn, Germany; Saarland University, Germany; MPI-INF, Germany; University of Sheffield, UK; Rutgers University, USA; University of Massachusetts at Amherst, USA; Aalto University, Finland) Article Search Article: stoc26main-p171-p STOC '26: "Separator Theorem for Minor-Free ..." Separator Theorem for Minor-Free Graphs in Linear Time Édouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, and Tomáš Masařík (CNRS, France; University of Copenhagen, Denmark; University of Massachusetts at Amherst, USA; Carnegie Mellon University, USA; University of Warsaw, Poland) Article Search Article: stoc26main-p31-p
	Lee, Daniel Z.	STOC '26: "On Zeros and Algorithms for ..." On Zeros and Algorithms for Disordered Systems: Mean-Field Spin Glasses Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, and Guus Regts (CWI, Netherlands; Stanford University, USA; Massachusetts Institute of Technology, USA; University of Amsterdam, Netherlands) Article Search Article: stoc26main-p245-p
	Lee, Euiwoong	STOC '26: "A (4+ϵ)-Approximation for ..." A (4+ϵ)-Approximation for Euclidean 𝑘-Means via Non-monotone Dual-Fitting Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, and Ernest van Wijland (Stanford University, USA; Google Research, France; IDSIA at USI-SUPSI, Switzerland; University of Michigan, USA; Université Paris-Cité - CNRS, France) Article Search Article: stoc26main-p1152-p STOC '26: "Combinatorial Optimization ..." Combinatorial Optimization using Comparison Oracles Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Pittu, Jon Schneider, and David P. Woodruff (Google Research, New-York, USA; Bocconi University, Italy; New York University, USA; Google Research, USA; University of Michigan, USA; Duke University, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p1341-p
	Lee, Holden	STOC '26: "Mixing of General Biased Adjacent ..." Mixing of General Biased Adjacent Transposition Chains Reza Gheissari, Holden Lee, and Eric Vigoda (Northwestern University, USA; Johns Hopkins University, USA; University of California at Santa Barbara, USA) Article Search Article: stoc26main-p565-p
	Lee, Jane	STOC '26: "Smoothed Analysis of Learning ..." Smoothed Analysis of Learning from Positive Samples Jane Lee, Anay Mehrotra, and Manolis Zampetakis (Yale University, USA) Article Search Article: stoc26main-p25-p
	Leme, Renato Paes	STOC '26: "Combinatorial Optimization ..." Combinatorial Optimization using Comparison Oracles Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Pittu, Jon Schneider, and David P. Woodruff (Google Research, New-York, USA; Bocconi University, Italy; New York University, USA; Google Research, USA; University of Michigan, USA; Duke University, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p1341-p
	Li, Anqi	STOC '26: "Parallel Sampling via Autospeculation ..." Parallel Sampling via Autospeculation Nima Anari, Carlo Baronio, CJ Chen, Alireza Haqi, Frederic Koehler, Anqi Li, and Thuy-Duong Vuong (Stanford University, USA; University of Arizona, USA; University of Chicago, USA; University of California at San Diego, USA) Article Search Article: stoc26main-p524-p
	Li, George Z.	STOC '26: "Shortcutting for Negative-Weight ..." Shortcutting for Negative-Weight Shortest Paths George Z. Li, Jason Li, Satish Rao, and Junkai Zhang (Carnegie Mellon University, USA; University of California at Berkeley, USA; Tsinghua University, China) Article Search Article: stoc26main-p125-p STOC '26: "Reviving Thorup’s Shortcut ..." Reviving Thorup’s Shortcut Conjecture Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, and Leon Schiller (New York University, USA; Carnegie Mellon University, USA; ETH Zurich, Switzerland; INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; University of Michigan, USA; MPI-INF, Germany; Saarland University, Germany; Hasso Plattner Institute - University of Potsdam, Germany) Article Search Article: stoc26main-p292-p
	Li, Jason	STOC '26: "Deterministic Padded Decompositions ..." Deterministic Padded Decompositions and Negative-Weight Shortest Paths Jason Li (Carnegie Mellon University, USA) Article Search Article: stoc26main-p8-p STOC '26: "Shortcutting for Negative-Weight ..." Shortcutting for Negative-Weight Shortest Paths George Z. Li, Jason Li, Satish Rao, and Junkai Zhang (Carnegie Mellon University, USA; University of California at Berkeley, USA; Tsinghua University, China) Article Search Article: stoc26main-p125-p STOC '26: "Separator Theorem for Minor-Free ..." Separator Theorem for Minor-Free Graphs in Linear Time Édouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, and Tomáš Masařík (CNRS, France; University of Copenhagen, Denmark; University of Massachusetts at Amherst, USA; Carnegie Mellon University, USA; University of Warsaw, Poland) Article Search Article: stoc26main-p31-p
	Li, Jerry	STOC '26: "Rigorous Implications of the ..." Rigorous Implications of the Low-Degree Heuristic Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari, Jerry Li, Sidhanth Mohanty, and Stefan Tiegel (Massachusetts Institute of Technology, USA; University of California at San Diego, USA; Princeton University, USA; University of Washington, USA; Northwestern University, USA) Article Search Article: stoc26main-p995-p STOC '26: "The Power of Two Bases: Nearly ..." The Power of Two Bases: Nearly Robust and Copy-Optimal Certification of Nearly All Quantum States with Single-Qubit Measurements Andrea Coladangelo, Jerry Li, Joseph Slote, and Ellen Wu (University of Washington, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p999-p STOC '26: "High-Accuracy List-Decodable ..." High-Accuracy List-Decodable Mean Estimation Ziyun Chen, Spencer Compton, Daniel M. Kane, and Jerry Li (University of Washington, USA; Stanford University, USA; University of California at San Diego, USA) Article Search Article: stoc26main-p335-p
	Li, Jiatu	STOC '26: "A Theory for Probabilistic ..." A Theory for Probabilistic Polynomial-Time Reasoning Lijie Chen, Jiatu Li, Igor C. Oliveira, and Ryan Williams (University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; University of Warwick, UK) Article Search Article: stoc26main-p624-p STOC '26: "SNARGs for NP from Unprovability ..." SNARGs for NP from Unprovability of Mathematical Theorems (Or: How to Use the Simplicity of Cryptographic Reasoning) Yao-Ching Hsieh, Abhishek Jain, Jiatu Li, and Surya Mathialagan (University of Washington, USA; NTT Research, USA; Johns Hopkins University, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p24-p
	Li, Jiawei	STOC '26: "Finding Bugs in Short Proofs: ..." Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds Jiawei Li, Yuhao Li, and Hanlin Ren (University of Texas at Austin, USA; Columbia University, USA; Institute for Advanced Study at Princeton, USA) Article Search Article: stoc26main-p343-p
	Li, Shi	STOC '26: "Randomized Rounding over Dynamic ..." Randomized Rounding over Dynamic Programs Étienne Bamas, Shi Li, and Lars Rohwedder (EPFL, Switzerland; Nanjing University, China; University of Southern Denmark, Denmark) Article Search Article: stoc26main-p1143-p STOC '26: "Nash Social Welfare with Submodular ..." Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps Xiaohui Bei, Yuda Feng, Yang Hu, Shi Li, and Ruilong Zhang (Nanyang Technological University, Singapore; Nanjing University, China; Tsinghua University, China; TU Munich, Germany) Article Search Article: stoc26main-p1408-p
	Li, Shuchen	STOC '26: "Learning Mixture Models via ..." Learning Mixture Models via Efficient High-Dimensional Sparse Fourier Transforms Alkis Kalavasis, Pravesh K. Kothari, Shuchen Li, and Manolis Zampetakis (Yale University, USA; Princeton University, USA) Article Search Article: stoc26main-p1321-p
	Li, Xingjian	STOC '26: "A Meta-complexity Characterization ..." A Meta-complexity Characterization of Minimal Quantum Cryptography Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, and Xingjian Li (University of Oxford, UK; Tsinghua University, China; University of Washington, USA; EPFL, Switzerland) Article Search Article: stoc26main-p298-p
	Li, Yuhao	STOC '26: "Finding Bugs in Short Proofs: ..." Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds Jiawei Li, Yuhao Li, and Hanlin Ren (University of Texas at Austin, USA; Columbia University, USA; Institute for Advanced Study at Princeton, USA) Article Search Article: stoc26main-p343-p
	Li, Zeyong	STOC '26: "Range Avoidance, Arthur-Merlin, ..." Range Avoidance, Arthur-Merlin, and TFNP Surendra Ghentiyala, Zeyong Li, and Noah Stephens-Davidowitz (Cornell University, USA; National University of Singapore, Singapore) Article Search Article: stoc26main-p1260-p
	Ligocki, Shawn	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Lin, Honghao	STOC '26: "Adversarial Robustness on ..." Adversarial Robustness on Insertion-Deletion Streams Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou (Princeton University, USA; Carnegie Mellon University, USA; Texas A&M University, USA) Article Search Article: stoc26main-p2045-p
	Lin, Junqiao (Randy)	STOC '26: "MIPco=coRE ..." MIPco=coRE Junqiao (Randy) Lin (CWI, Netherlands; QuSoft, Netherlands) Article Search Article: stoc26main-p163-p
	Lindgren, Elias	STOC '26: "Combinatorial Markov Search ..." Combinatorial Markov Search Robin Bowers, Elias Lindgren, and Bo Waggoner (University of Colorado Boulder, USA) Article Search Article: stoc26main-p2089-p
	Liu, Allen	STOC '26: "A Dobrushin Condition for ..." A Dobrushin Condition for Quantum Markov Chains: Rapid Mixing and Conditional Mutual Information at High Temperature Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang (New York University, USA; University of California at Berkeley, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p776-p
	Liu, Jingcheng	STOC '26: "Zero-Free Regions and Concentration ..." Zero-Free Regions and Concentration Inequalities for Hypergraph Colorings in the Local Lemma Regime Jingcheng Liu and Yixiao Yu (Nanjing University, China) Article Search Article: stoc26main-p435-p
	Liu, Kuikui	STOC '26: "On Zeros and Algorithms for ..." On Zeros and Algorithms for Disordered Systems: Mean-Field Spin Glasses Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, and Guus Regts (CWI, Netherlands; Stanford University, USA; Massachusetts Institute of Technology, USA; University of Amsterdam, Netherlands) Article Search Article: stoc26main-p245-p
	Liu, Qipeng	STOC '26: "On the Need for (Quantum) ..." On the Need for (Quantum) Memory with Short Outputs Zihan Hao, Qipeng Liu, and Zikuan Huang (University of California at San Diego, USA; Tsinghua University, China) Article Search Article: stoc26main-p1237-p
	Liu, Yang	STOC '26: "Incremental Shortest Paths ..." Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method Yang Liu (Carnegie Mellon University, USA) We give an algorithm that takes a directed graph G undergoing m edge insertions with lengths in [1, W], and maintains (1+є)-approximate shortest path distances from a fixed source s to all other vertices. The algorithm is deterministic and runs in total time m1+o(1)logW, for any є > exp(−(logm)0.99). This is achieved by designing a nonstandard interior point method to crudely detect when the distances from s to other vertices v have decreased by a (1+є) factor, and implementing it using the deterministic min-ratio cycle data structure of [Chen-Kyng-Liu-Meierhans-Probst, STOC 2024]. Preprint Info Article: stoc26main-p55-p STOC '26: "An Analytical Approach to ..." An Analytical Approach to Parallel Repetition via CSP Inverse Theorems Amey Bhangale, Mark Braverman, Subhash Khot, Yang Liu, Dor Minzer, and Kunal Mittal (University of California at Riverside, USA; Princeton University, USA; New York University, USA; Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p148-p
	Livanos, Vasilis	STOC '26: "On the Informativeness of ..." On the Informativeness of Moments in Optimal Stopping José Correa, Andrés Cristi, Vasilis Livanos, Victor Verdugo, and Jiechen Zhang (Universidad de Chile, Chile; EPFL, Switzerland; Center for Mathematical Modeling, Chile; Pontificia Universidad Católica de Chile, Chile) Article Search Article: stoc26main-p342-p
	Loff, Bruno	STOC '26: "The Natural Proofs Barrier ..." The Natural Proofs Barrier against Data-Structure Lower-Bounds Bruno Loff, Michal Koucký, Tulasimohan Molli, and Michael E. Saks (LASIGE, Portugal; University of Lisbon, Portugal; Charles University, Czech Republic; Rutgers University, USA) Article Search Article: stoc26main-p628-p
	Lokshtanov, Daniel	STOC '26: "Fine-Grained Bounds for Courcelle’s ..." Fine-Grained Bounds for Courcelle’s Theorem Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi (University of California Santa Barbara, USA; University of Leeds, UK; Institute of Mathematical Sciences, India; New York University Shanghai, China; Ben-Gurion University of the Negev, Israel) Article Search Article: stoc26main-p1957-p STOC '26: "Forbidden Subgraphs of Graphs ..." Forbidden Subgraphs of Graphs with Low Bandwidth Maria Chudnovsky, Daniel Lokshtanov, and Eran Nevo (Princeton University, USA; University of California at Santa Barbara, USA; Hebrew University of Jerusalem, Israel) Article Search Article: stoc26main-p21-p
	Lombardi, Alex	STOC '26: "SNARGs for NP and Non-signaling ..." SNARGs for NP and Non-signaling PCPs, Revisited Lalita Devadas, Samuel B. Hopkins, Yael Kalai, Pravesh K. Kothari, Alex Lombardi, and Surya Mathialagan (Massachusetts Institute of Technology, USA; Princeton University, USA; NTT Research, USA) Article Search Article: stoc26main-p297-p
	Long, Yaowei	STOC '26: "A Constant-Approximation Distance ..." A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures Bernhard Haeupler, Yaowei Long, Antti Roeyskoe, and Thatchaphol Saranurak (INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; ETH Zurich, Switzerland; University of Michigan, USA) Article Search Article: stoc26main-p454-p
	Lovett, Shachar	STOC '26: "Locally Computable High Independence ..." Locally Computable High Independence Hashing Yevgeniy Dodis, Shachar Lovett, and Daniel Wichs (New York University, USA; University of California at San Diego, USA; Northeastern University, USA; NTT Research, USA) Article Search Article: stoc26main-p718-p STOC '26: "Restriction Trees for Sparsity ..." Restriction Trees for Sparsity and Applications Arkadev Chattopadhyay, Yogesh Dahiya, and Shachar Lovett (Tata Institute of Fundamental Research, Mumbai, India; University of California at San Diego, USA) Article Search Article: stoc26main-p1195-p
	Lu, Jiaqi	STOC '26: "Lower Bounds against the Ideal ..." Lower Bounds against the Ideal Proof System in Finite Fields Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu, and Iddo Tzameret (Imperial College London, UK) Article Search Article: stoc26main-p4-p
	Lu, Jonathan	STOC '26: "Average-Case Complexity of ..." Average-Case Complexity of Quantum Stabilizer Decoding Andrey Boris Khesin, Jonathan Lu, Alexander Poremba, Akshar Ramkumar, and Vinod Vaikuntanathan (University of Oxford, UK; Massachusetts Institute of Technology, USA; Boston University, USA; California Institute of Technology, USA) Article Search Article: stoc26main-p373-p
	Lu, Mingqi	STOC '26: "SNARKs from LWE via Non-black-Box ..." SNARKs from LWE via Non-black-Box Reductions Zhengzhong Jin, Mingqi Lu, and Bo Peng (Northeastern University, USA; Peking University, China) Article Search Article: stoc26main-p1088-p
	Lunghi, Anna	STOC '26: "The Sample Complexity of Uniform ..." The Sample Complexity of Uniform Approximation for Multi-dimensional CDFs and Fixed-Price Mechanisms Matteo Castiglioni, Anna Lunghi, and Alberto Marchesi (Politecnico di Milano, Italy) Article Search Article: stoc26main-p634-p
	Luo, Haipeng	STOC '26: "Proximal Regret and Proximal ..." Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng (Yale University, USA; Massachusetts Institute of Technology, USA; University of Southern California, USA; University of Virginia, USA) Article Search Article: stoc26main-p859-p
	Luo, Yiyuan	STOC '26: "Optimal Phylogenetic Reconstruction ..." Optimal Phylogenetic Reconstruction from Sampled Quartets Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo, and Konstantin Makarychev (Northwestern University, USA; University of California at Santa Cruz, USA) Article Search Article: stoc26main-p1059-p
	Lyu, Xin	STOC '26: "Private Learning of Littlestone ..." Private Learning of Littlestone Classes, Revisited Xin Lyu (University of California at Berkeley, USA) Article Search Article: stoc26main-p1801-p
	Ma, Haoyuan	STOC '26: "Trust Region Interior Point ..." Trust Region Interior Point Methods: Optimal L2- and Faster Wide-Neighborhood Path Following Daniel Dadush, Haoyuan Ma, Bento Natura, and László A. Végh (CWI, Netherlands; University of Bonn, Germany; Columbia University, USA) Article Search Article: stoc26main-p331-p
	Majid, Mahbod	STOC '26: "Computation-Utility-Privacy ..." Computation-Utility-Privacy Tradeoffs in Bayesian Estimation Sitan Chen, Jingqiu Ding, Mahbod Majid, and Walt McKelvie (Harvard University, USA; ETH Zurich, Switzerland; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p850-p
	Makarychev, Konstantin	STOC '26: "Optimal Phylogenetic Reconstruction ..." Optimal Phylogenetic Reconstruction from Sampled Quartets Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo, and Konstantin Makarychev (Northwestern University, USA; University of California at Santa Cruz, USA) Article Search Article: stoc26main-p1059-p
	Makarychev, Yury	STOC '26: "Approximation Algorithms for ..." Approximation Algorithms for Satisfiable and Nearly Satisfiable Ordering CSPs Yury Makarychev (Toyota Technological Institute at Chicago, USA) Article Search Article: stoc26main-p928-p
	Manohar, Peter	STOC '26: "Relaxed vs. Full Local Decodability ..." Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes Elena Grigorescu, Vinayak M. Kumar, Peter Manohar, and Geoffrey Mon (University of Waterloo, Canada; University of Texas at Austin, USA; Institute for Advanced Study at Princeton, USA) Article Search Article: stoc26main-p674-p
	Manor, Yahel	STOC '26: "Failure of Symmetry of Information ..." Failure of Symmetry of Information for Randomized Computations Jinqiao Hu, Yahel Manor, and Igor C. Oliveira (University of Warwick, UK; University of Haifa, Israel) Article Search Article: stoc26main-p834-p
	Mansour, Yishay	STOC '26: "Sample Complexity of Agnostic ..." Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, and Qian Zhang (Tel Aviv University, Israel; Google Research, Israel; Purdue University, USA; Technion, Israel) Article Search Article: stoc26main-p308-p
	Mao, Xiao	STOC '26: "Classifying Identities: Subcubic ..." Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection Bartłomiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin, Marvin Künnemann, Xiao Mao, and Mirza Redžić (University of Wrocław, Poland; MPI-INF, Germany; KIT, Germany; University of California at Berkeley, USA; Stanford University, USA) Article Search Article: stoc26main-p715-p STOC '26: "Approximation Schemes for ..." Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time Xiao Mao and Aviad Rubinstein (Stanford University, USA) Article Search Article: stoc26main-p322-p
	Marchesi, Alberto	STOC '26: "The Sample Complexity of Uniform ..." The Sample Complexity of Uniform Approximation for Multi-dimensional CDFs and Fixed-Price Mechanisms Matteo Castiglioni, Anna Lunghi, and Alberto Marchesi (Politecnico di Milano, Italy) Article Search Article: stoc26main-p634-p
	Marmor, Avichai	STOC '26: "Non-adaptive Cryptanalytic ..." Non-adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-Like Inequality for Permutations Itai Dinur, Nathan Keller, and Avichai Marmor (Ben-Gurion University of the Negev, Israel; Georgetown University, USA; Bar-Ilan University, Israel) Article Search Article: stoc26main-p879-p
	Marx, Dániel	STOC '26: "Approximation Schemes for ..." Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs Sándor Kisfaludi-Bak and Dániel Marx (Aalto University, Espoo, Finland; CISPA Helmholtz Center for Information Security, Germany) Article Search Article: stoc26main-p460-p STOC '26: "Pattern-Sparse Tree Decompositions ..." Pattern-Sparse Tree Decompositions in H-Minor-Free Graphs Dániel Marx, Marcin Pilipczuk, and Michał Pilipczuk (CISPA Helmholtz Center for Information Security, Germany; University of Warsaw, Poland) Article Search Article: stoc26main-p775-p
	Masařík, Tomáš	STOC '26: "Separator Theorem for Minor-Free ..." Separator Theorem for Minor-Free Graphs in Linear Time Édouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, and Tomáš Masařík (CNRS, France; University of Copenhagen, Denmark; University of Massachusetts at Amherst, USA; Carnegie Mellon University, USA; University of Warsaw, Poland) Article Search Article: stoc26main-p31-p
	Mathialagan, Surya	STOC '26: "SNARGs for NP from Unprovability ..." SNARGs for NP from Unprovability of Mathematical Theorems (Or: How to Use the Simplicity of Cryptographic Reasoning) Yao-Ching Hsieh, Abhishek Jain, Jiatu Li, and Surya Mathialagan (University of Washington, USA; NTT Research, USA; Johns Hopkins University, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p24-p STOC '26: "SNARGs for NP and Non-signaling ..." SNARGs for NP and Non-signaling PCPs, Revisited Lalita Devadas, Samuel B. Hopkins, Yael Kalai, Pravesh K. Kothari, Alex Lombardi, and Surya Mathialagan (Massachusetts Institute of Technology, USA; Princeton University, USA; NTT Research, USA) Article Search Article: stoc26main-p297-p
	Mathiasen, Markus Engelund	STOC '26: "The Sample Complexity of Replicable ..." The Sample Complexity of Replicable Realizable PAC Learning Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju, and Clement Svendsen (Aarhus University, Denmark; Stanford University, USA) Article Search Article: stoc26main-p1419-p
	Maus, Yannic	STOC '26: "Sublogarithmic Distributed ..." Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors Maxime Flin, Magnús Halldórsson, Manuel Jakob, and Yannic Maus (Aalto University, Finland; Reykjavik University, Iceland; TU Graz, Austria) Article Search Article: stoc26main-p1266-p
	May, Alex	STOC '26: "Magic and Communication Complexity ..." Magic and Communication Complexity Uma Girish, Alex May, Natalie Parham, and Henry Yuen (Columbia University, USA; Perimeter Institute for Theoretical Physics, Canada) Article Search Article: stoc26main-p364-p
	McCauley, Samuel	STOC '26: "Space-Efficient Dictionary ..." Space-Efficient Dictionary Matching with Mismatches using Function Inversion Jackson Bibbens, Levi Borevitz, and Samuel McCauley (University of Massachusetts at Amherst, USA; Northwestern University, USA; Williams College, USA) Article Search Article: stoc26main-p480-p
	McKelvie, Walt	STOC '26: "Computation-Utility-Privacy ..." Computation-Utility-Privacy Tradeoffs in Bayesian Estimation Sitan Chen, Jingqiu Ding, Mahbod Majid, and Walt McKelvie (Harvard University, USA; ETH Zurich, Switzerland; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p850-p
	Mehrotra, Anay	STOC '26: "Smoothed Analysis of Learning ..." Smoothed Analysis of Learning from Positive Samples Jane Lee, Anay Mehrotra, and Manolis Zampetakis (Yale University, USA) Article Search Article: stoc26main-p25-p
	Mehta, Ruta	STOC '26: "Tâtonnement Dynamics for ..." Tâtonnement Dynamics for Fisher Markets with Chores Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta, and Tianlong Nan (University of Illinois at Urbana-Champaign, USA; Columbia University, USA) Article Search Article: stoc26main-p183-p
	Meka, Raghu	STOC '26: "Sparse Linear Regression Is ..." Sparse Linear Regression Is Easy on Random Supports Gautam Chandrasekaran, Raghu Meka, and Konstantinos Stavropoulos (University of Texas at Austin, USA; University of California at Los Angeles, USA) Article Search Article: stoc26main-p1875-p
	Melissourgos, Themistoklis	STOC '26: "Fisher Markets with Approximately ..." Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos (Royal Holloway University of London, UK; University of Liverpool, UK; University of Oxford, UK; University of Essex, UK) Article Search Article: stoc26main-p474-p
	Minzer, Dor	STOC '26: "3-Query RLDCs Are Strictly ..." 3-Query RLDCs Are Strictly Stronger Than 3-Query LDCs Tom Gur, Dor Minzer, Guy Weissenberg, and Kai Zhe Zheng (University of Cambridge, UK; Massachusetts Institute of Technology, USA; EPFL, Switzerland) Article Search Article: stoc26main-p741-p STOC '26: "A Dichotomy Theorem for Multi-pass ..." A Dichotomy Theorem for Multi-pass Streaming CSPs Yumou Fei, Dor Minzer, and Shuo Wang (Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p111-p STOC '26: "An Analytical Approach to ..." An Analytical Approach to Parallel Repetition via CSP Inverse Theorems Amey Bhangale, Mark Braverman, Subhash Khot, Yang Liu, Dor Minzer, and Kunal Mittal (University of California at Riverside, USA; Princeton University, USA; New York University, USA; Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p148-p STOC '26: "Near Optimal Hardness of Approximating ..." Near Optimal Hardness of Approximating 𝑘-CSP Dor Minzer and Kai Zhe Zheng (Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p34-p
	Mitrović, Slobodan	STOC '26: "Improved Local Computation ..." Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates Slobodan Mitrović, Srikkanth Ramachandran, Ronitt Rubinfeld, and Mihir Singhal (University of California at Davis, USA; University of Novi Sad, Serbia; Massachusetts Institute of Technology, USA; University of California at Berkeley, USA) Article Search Article: stoc26main-p551-p
	Mittal, Kunal	STOC '26: "An Analytical Approach to ..." An Analytical Approach to Parallel Repetition via CSP Inverse Theorems Amey Bhangale, Mark Braverman, Subhash Khot, Yang Liu, Dor Minzer, and Kunal Mittal (University of California at Riverside, USA; Princeton University, USA; New York University, USA; Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p148-p
	Mohanty, Sidhanth	STOC '26: "Rigorous Implications of the ..." Rigorous Implications of the Low-Degree Heuristic Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari, Jerry Li, Sidhanth Mohanty, and Stefan Tiegel (Massachusetts Institute of Technology, USA; University of California at San Diego, USA; Princeton University, USA; University of Washington, USA; Northwestern University, USA) Article Search Article: stoc26main-p995-p
	Moitra, Ankur	STOC '26: "A Dobrushin Condition for ..." A Dobrushin Condition for Quantum Markov Chains: Rapid Mixing and Conditional Mutual Information at High Temperature Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang (New York University, USA; University of California at Berkeley, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p776-p STOC '26: "Improved Pseudorandom Codes ..." Improved Pseudorandom Codes from Permuted Puzzles Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, and Daniel Wichs (Columbia University, USA; Microsoft Research, USA; University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; Northeastern University, USA) Article Search Article: stoc26main-p1557-p
	Molli, Tulasimohan	STOC '26: "The Natural Proofs Barrier ..." The Natural Proofs Barrier against Data-Structure Lower-Bounds Bruno Loff, Michal Koucký, Tulasimohan Molli, and Michael E. Saks (LASIGE, Portugal; University of Lisbon, Portugal; Charles University, Czech Republic; Rutgers University, USA) Article Search Article: stoc26main-p628-p
	Mon, Geoffrey	STOC '26: "Relaxed vs. Full Local Decodability ..." Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes Elena Grigorescu, Vinayak M. Kumar, Peter Manohar, and Geoffrey Mon (University of Waterloo, Canada; University of Texas at Austin, USA; Institute for Advanced Study at Princeton, USA) Article Search Article: stoc26main-p674-p
	Montealegre, Pedro	STOC '26: "What Can Be Computed Locally ..." What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing Lelia Blin, Fedor V. Fomin, Pierre Fraigniaud, Sylvain Gay, Petr A. Golovach, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca (Université Paris Cité - IRIF - CNRS, France; University of Bergen, Norway; CNRS - Université de Paris, France; École Normale Supérieure, France; Universidad Adolfo Ibáñez, Chile; Universidad de Chile, Chile; Université d'Orléans, France) Article Search Article: stoc26main-p673-p
	Moran, Shay	STOC '26: "Sample Complexity of Agnostic ..." Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, and Qian Zhang (Tel Aviv University, Israel; Google Research, Israel; Purdue University, USA; Technion, Israel) Article Search Article: stoc26main-p308-p STOC '26: "On the Learning Curves of ..." On the Learning Curves of Revenue Maximization Steve Hanneke, Alkis Kalavasis, Shay Moran, and Grigoris Velegkas (Purdue University, USA; Yale University, USA; Technion, Israel; Google Research, USA) Article Search Article: stoc26main-p38-p
	Mosenzon, Ron	STOC '26: "Almost-Optimal Approximation ..." Almost-Optimal Approximation Algorithm for Global Minimum Cut in Directed Graphs Ron Mosenzon (Toyota Technological Institute at Chicago, USA) Article Search Article: stoc26main-p53-p
	Mour, Tamer	STOC '26: "Secret-Key PIR from Random ..." Secret-Key PIR from Random Linear Codes Caicai Chen, Yuval Ishai, Tamer Mour, and Alon Rosen (Bocconi University, Italy; Technion, Israel; AWS, USA) Article Search Article: stoc26main-p1368-p
	Mousavi, Ramin	STOC '26: "A Constant-Factor Approximation ..." A Constant-Factor Approximation for Directed Latency Jannis Blauth and Ramin Mousavi (ETH Zurich, Switzerland; IDSIA at USI-SUPSI, Switzerland) Article Search Article: stoc26main-p221-p
	Mukhopadhyay, Partha	STOC '26: "Negations Are Powerful Even ..." Negations Are Powerful Even in Small Depth Bruno Cavalar, Théo Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, and Amir Yehudayoff (University of Oxford, UK; University of Copenhagen, Denmark; Chennai Mathematical Institute, India) Article Search Article: stoc26main-p1423-p
	Munagala, Kamesh	STOC '26: "The Price of Competitive Information ..." The Price of Competitive Information Disclosure Sid Banerjee, Kamesh Munagala, Yiheng Shen, and Kangning Wang (Cornell University, USA; Duke University, USA; Rutgers University, USA) Article Search Article: stoc26main-p601-p
	Münk, Robin	STOC '26: "An Improved Quality Hierarchical ..." An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time Monika Henzinger, Robin Münk, and Harald Räcke (IST Austria, Austria; TU Munich, Germany) Article Search Article: stoc26main-p678-p
	Mxdys	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Myasnikov, Konstantin	STOC '26: "Sampling Permutations with ..." Sampling Permutations with Cell Probes Is Hard Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, and Dmitry Sokolov (Technion, Israel; EPFL, Switzerland; Université de Montréal, Canada) Article Search Article: stoc26main-p108-p
	Nadimpalli, Shivam	STOC '26: "Sparsifying Suprema of Gaussian ..." Sparsifying Suprema of Gaussian Processes Anindya De, Shivam Nadimpalli, Ryan O'Donnell, and Rocco A. Servedio (University of Pennsylvania, USA; Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; Columbia University, USA) We give a dimension-independent sparsification result for suprema of centered Gaussian processes: Let T be any (possibly infinite) bounded set of vectors in n, and let {t := t · g }t∈ T be the canonical Gaussian process on T, where g∼ N(0, In). We show that there is an Oε(1)-size subset S ⊆ T and a set of real values {cs}s ∈ S such that the random variable sups ∈ S {Xs + cs} is an ε-approximator (in L1) of the random variable supt ∈ T Xt. Notably, the size of the sparsifier S is completely independent of both |T| and the ambient dimension n. We give two applications of this sparsification theorem: <ul> <li><strong>A “Junta Theorem” for Norms:</strong> We show that given any norm ν(x) on n, there is another norm ψ(x) depending only on the projection of x onto Oε(1) directions, for which ψ(g) is a multiplicative (1 ± ε)-approximation of ν(g) with probability 1−ε for g ∼ N(0,In). </li> <li><strong>Sparsification of Convex Sets:</strong> We show that any intersection of (possibly infinitely many) halfspaces in n that are at distance r from the origin is ε-close (under N(0,In)) to an intersection of only Or,ε(1) halfspaces. This yields new polynomial-time agnostic learning and tolerant property testing algorithms for intersections of halfspaces. </li> </ul> Article Search Article: stoc26main-p202-p STOC '26: "Testing Noisy Low-Degree Polynomials ..." Testing Noisy Low-Degree Polynomials for Sparsity Yiqiao Bao, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, and Nathan White (University of Pennsylvania, USA; Massachusetts Institute of Technology, USA; Columbia University, USA) Article Search Article: stoc26main-p348-p
	Nan, Tianlong	STOC '26: "Tâtonnement Dynamics for ..." Tâtonnement Dynamics for Fisher Markets with Chores Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta, and Tianlong Nan (University of Illinois at Urbana-Champaign, USA; Columbia University, USA) Article Search Article: stoc26main-p183-p
	Nanashima, Mikito	STOC '26: "A Sharp Characterization of ..." A Sharp Characterization of Pessiland Shuichi Hirahara and Mikito Nanashima (National Institute of Informatics, Tokyo, Japan; Institute of Science Tokyo, Japan) Article Search Article: stoc26main-p177-p STOC '26: "Complexity-Theoretic Universal ..." Complexity-Theoretic Universal Inductive Inference Shuichi Hirahara and Mikito Nanashima (National Institute of Informatics, Tokyo, Japan; Institute of Science Tokyo, Japan) Article Search Article: stoc26main-p181-p
	Naściszewski, Mateusz	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Natura, Bento	STOC '26: "Trust Region Interior Point ..." Trust Region Interior Point Methods: Optimal L2- and Faster Wide-Neighborhood Path Following Daniel Dadush, Haoyuan Ma, Bento Natura, and László A. Végh (CWI, Netherlands; University of Bonn, Germany; Columbia University, USA) Article Search Article: stoc26main-p331-p
	Nevo, Eran	STOC '26: "Forbidden Subgraphs of Graphs ..." Forbidden Subgraphs of Graphs with Low Bandwidth Maria Chudnovsky, Daniel Lokshtanov, and Eran Nevo (Princeton University, USA; University of California at Santa Barbara, USA; Hebrew University of Jerusalem, Israel) Article Search Article: stoc26main-p21-p
	Nikolov, Aleksandar	STOC '26: "Online Matrix Factorization, ..." Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization Aleksandar Nikolov, Haohua Tang, and Jonathan Ullman (University of Toronto, Canada; Northeastern University, USA) Article Search Article: stoc26main-p2157-p
	Nirkhe, Chinmay	STOC '26: "Separating QMA from QCMA with ..." Separating QMA from QCMA with a Classical Oracle John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, and Mark Zhandry (Columbia University, USA; Saarland University, Germany; University of Washington, USA; NTT Research, USA; Stanford University, USA) Article Search Article: stoc26main-p275-p
	Nöbel, Christian	STOC '26: "Toward Optimal Approximations ..." Toward Optimal Approximations for Resource-Minimization for Fire Containment on Trees and Non-uniform k-Center Jannis Blauth, Christian Nöbel, and Rico Zenklusen (ETH Zurich, Switzerland) Article Search Article: stoc26main-p1150-p
	O'Carroll, Liam	STOC '26: "Solving Matrix Games with ..." Solving Matrix Games with Near-Optimal Matvec Complexity Ishani Karmarkar, Liam O'Carroll, and Aaron Sidford (Stanford University, USA) Article Search Article: stoc26main-p975-p
	O'Donnell, Ryan	STOC '26: "No Exponential Quantum Speedup ..." No Exponential Quantum Speedup for SIS∞ Anymore Robin Kothari, Ryan O'Donnell, and Kewen Wu (Google Quantum AI, USA; Carnegie Mellon University, USA; Institute for Advanced Study at Princeton, USA) In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case ℓ∞-Short Integer Solution (SIS∞) problem, in a parameter range outside the normal range of cryptographic interest, but still with no known efficient classical algorithm. This was particularly exciting since SIS∞ is a simple problem without structure, and their algorithmic techniques were different from those used in prior exponential quantum speedups. We present efficient classical algorithms for all of the SIS∞ and (more general) Constrained Integer Solution problems studied in their paper, showing there is no exponential quantum speedup anymore. Article Search Article: stoc26main-p52-p STOC '26: "Generalized Samorodnitsky ..." Generalized Samorodnitsky Noisy Function Inequalities, with Applications to Error-Correcting Codes Olakunle Sunday Abawonse, Jan Hązła, and Ryan O'Donnell (AIMS, Rwanda; Carnegie Mellon University, USA) Article Search Article: stoc26main-p175-p STOC '26: "Instance-Optimal Quantum State ..." Instance-Optimal Quantum State Certification with Entangled Measurements Ryan O'Donnell and Chirag Wadhwa (Carnegie Mellon University, USA; University of Edinburgh, UK) Article Search Article: stoc26main-p187-p STOC '26: "Sparsifying Suprema of Gaussian ..." Sparsifying Suprema of Gaussian Processes Anindya De, Shivam Nadimpalli, Ryan O'Donnell, and Rocco A. Servedio (University of Pennsylvania, USA; Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; Columbia University, USA) We give a dimension-independent sparsification result for suprema of centered Gaussian processes: Let T be any (possibly infinite) bounded set of vectors in n, and let {t := t · g }t∈ T be the canonical Gaussian process on T, where g∼ N(0, In). We show that there is an Oε(1)-size subset S ⊆ T and a set of real values {cs}s ∈ S such that the random variable sups ∈ S {Xs + cs} is an ε-approximator (in L1) of the random variable supt ∈ T Xt. Notably, the size of the sparsifier S is completely independent of both |T| and the ambient dimension n. We give two applications of this sparsification theorem: <ul> <li><strong>A “Junta Theorem” for Norms:</strong> We show that given any norm ν(x) on n, there is another norm ψ(x) depending only on the projection of x onto Oε(1) directions, for which ψ(g) is a multiplicative (1 ± ε)-approximation of ν(g) with probability 1−ε for g ∼ N(0,In). </li> <li><strong>Sparsification of Convex Sets:</strong> We show that any intersection of (possibly infinitely many) halfspaces in n that are at distance r from the origin is ε-close (under N(0,In)) to an intersection of only Or,ε(1) halfspaces. This yields new polynomial-time agnostic learning and tolerant property testing algorithms for intersections of halfspaces. </li> </ul> Article Search Article: stoc26main-p202-p STOC '26: "Few Single-Qubit Measurements ..." Few Single-Qubit Measurements Suffice to Certify Any Quantum State Meghal Gupta, William He, and Ryan O'Donnell (University of California at Berkeley, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p26-p
	Oh, Justin	STOC '26: "Extractors for Samplable Distributions ..." Extractors for Samplable Distributions from the Two-Source Extractor Recipe Justin Oh and Ronen Shaltiel (University of Haifa, Israel) Article Search Article: stoc26main-p633-p
	Oliveira, Igor C.	STOC '26: "A Theory for Probabilistic ..." A Theory for Probabilistic Polynomial-Time Reasoning Lijie Chen, Jiatu Li, Igor C. Oliveira, and Ryan Williams (University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; University of Warwick, UK) Article Search Article: stoc26main-p624-p STOC '26: "Failure of Symmetry of Information ..." Failure of Symmetry of Information for Randomized Computations Jinqiao Hu, Yahel Manor, and Igor C. Oliveira (University of Warwick, UK; University of Haifa, Israel) Article Search Article: stoc26main-p834-p
	Olver, Neil	STOC '26: "Nonuniform Graph Partitioning ..." Nonuniform Graph Partitioning with Just a Little Flex Neil Olver, Harald Räcke, and Stefan Schmid (London School of Economics and Political Science, UK; TU Munich, Germany; TU Berlin, Germany; Fraunhofer SIT, Germany) Article Search Article: stoc26main-p989-p
	Ostrovskii, Mikhail	STOC '26: "Lower Estimates for 𝐿₁-Distortion ..." Lower Estimates for 𝐿₁-Distortion of Transportation Cost Spaces Chris Gartland and Mikhail Ostrovskii (University of North Carolina at Charlotte, USA; St. John's University, USA) Article Search Article: stoc26main-p304-p
	Pabbaraju, Chirag	STOC '26: "An Optimal Algorithm for Stochastic ..." An Optimal Algorithm for Stochastic Vertex Cover Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Cliff Stein, Miltiadis Stouras, Ola Svensson, and Ali Vakilian (Georgia Institute of Technology, USA; DTU, Denmark; Stanford University, USA; Duke University, USA; Columbia University, USA; EPFL, Switzerland; Virginia Tech, USA) Article Search Article: stoc26main-p798-p STOC '26: "A Unified Approach to Memory-Sample ..." A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures Sumegha Garg, Jabari Hastings, Chirag Pabbaraju, and Vatsal Sharan (Rutgers University, USA; Stanford University, USA; University of Southern California, USA) Article Search Article: stoc26main-p85-p STOC '26: "The Sample Complexity of Replicable ..." The Sample Complexity of Replicable Realizable PAC Learning Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju, and Clement Svendsen (Aarhus University, Denmark; Stanford University, USA) Article Search Article: stoc26main-p1419-p
	Page, Aurel	STOC '26: "Average Hardness of SIVP for ..." Average Hardness of SIVP for Module Lattices of Fixed Rank Koen de Boer, Aurel Page, Radu Toma, and Benjamin Wesolowski (Unaffiliated, France; Inria - Univ. Bordeaux - CNRS - Bordeaux INP - IMB - UMR 5251, France; Sorbonne Univ. - Univ. Paris Cité - CNRS - IMJ-PRG, France; ENS de Lyon - CNRS - UMPA - UMR 5669, France) Article Search Article: stoc26main-p353-p
	Pago, Benedikt	STOC '26: "Lower Bounds in Algebraic ..." Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials Prateek Dwivedi, Benedikt Pago, and Tim Seppelt (IT University of Copenhagen, Denmark; University of Cambridge, UK) Article Search Article: stoc26main-p286-p
	Panigrahi, Debmalya	STOC '26: "Fully Dynamic Set Cover: Worst-Case ..." Fully Dynamic Set Cover: Worst-Case Recourse and Update Time Sayan Bhattacharya, Ruoxu Cen, and Debmalya Panigrahi (University of Warwick, UK; Duke University, USA) Article Search Article: stoc26main-p395-p STOC '26: "An Optimal Algorithm for Stochastic ..." An Optimal Algorithm for Stochastic Vertex Cover Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Cliff Stein, Miltiadis Stouras, Ola Svensson, and Ali Vakilian (Georgia Institute of Technology, USA; DTU, Denmark; Stanford University, USA; Duke University, USA; Columbia University, USA; EPFL, Switzerland; Virginia Tech, USA) Article Search Article: stoc26main-p798-p STOC '26: "Combinatorial Optimization ..." Combinatorial Optimization using Comparison Oracles Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Pittu, Jon Schneider, and David P. Woodruff (Google Research, New-York, USA; Bocconi University, Italy; New York University, USA; Google Research, USA; University of Michigan, USA; Duke University, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p1341-p
	Panolan, Fahad	STOC '26: "Fine-Grained Bounds for Courcelle’s ..." Fine-Grained Bounds for Courcelle’s Theorem Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi (University of California Santa Barbara, USA; University of Leeds, UK; Institute of Mathematical Sciences, India; New York University Shanghai, China; Ben-Gurion University of the Negev, Israel) Article Search Article: stoc26main-p1957-p
	Parham, Natalie	STOC '26: "Quantum Circuit Lower Bounds ..." Quantum Circuit Lower Bounds in the Magic Hierarchy Natalie Parham (Columbia University, USA) Article Search Article: stoc26main-p310-p STOC '26: "Magic and Communication Complexity ..." Magic and Communication Complexity Uma Girish, Alex May, Natalie Parham, and Henry Yuen (Columbia University, USA; Perimeter Institute for Theoretical Physics, Canada) Article Search Article: stoc26main-p364-p
	Parter, Merav	STOC '26: "Sub-linear Secure Broadcast ..." Sub-linear Secure Broadcast and Applications Yuval Gelles, Ilan Komargodski, and Merav Parter (Hebrew University of Jerusalem, Israel; Weizmann Institute of Science, Israel) Article Search Article: stoc26main-p851-p
	Patel, Shyamal	STOC '26: "A Mysterious Connection between ..." A Mysterious Connection between Tolerant Junta Testing and Agnostically Learning Conjunctions Xi Chen, Shyamal Patel, and Rocco A. Servedio (Columbia University, USA) Article Search Article: stoc26main-p48-p STOC '26: "Near-Optimal Directed Euclidean ..." Near-Optimal Directed Euclidean Spanners in High Dimensions Rajesh Jayaram, Shyamal Patel, Cliff Stein, Erik Waingarten, and Tian Zhang (Google Research, USA; Columbia University, USA; University of Pennsylvania, USA) Article Search Article: stoc26main-p703-p STOC '26: "Learning Functions of Halfspaces ..." Learning Functions of Halfspaces Josh Alman, Shyamal Patel, and Rocco A. Servedio (Columbia University, USA) Article Search Article: stoc26main-p827-p
	Patton, Kalen	STOC '26: "Online Combinatorial Optimization ..." Online Combinatorial Optimization with Graphical Dependencies Zhimeng Gao, Evangelia Gergatsouli, Kalen Patton, and Sahil Singla (Georgia Institute of Technology, USA) Article Search Article: stoc26main-p545-p
	Pelecanos, Angelos	STOC '26: "The Debiased Keyl’s Algorithm: ..." The Debiased Keyl’s Algorithm: A New Unbiased Estimator for Full State Tomography Angelos Pelecanos, Jack Spilecki, and John Wright (University of California at Berkeley, USA) Article Search Article: stoc26main-p589-p
	Peng, Bo	STOC '26: "SNARKs from LWE via Non-black-Box ..." SNARKs from LWE via Non-black-Box Reductions Zhengzhong Jin, Mingqi Lu, and Bo Peng (Northeastern University, USA; Peking University, China) Article Search Article: stoc26main-p1088-p
	Pettie, Seth	STOC '26: "Reviving Thorup’s Shortcut ..." Reviving Thorup’s Shortcut Conjecture Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, and Leon Schiller (New York University, USA; Carnegie Mellon University, USA; ETH Zurich, Switzerland; INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; University of Michigan, USA; MPI-INF, Germany; Saarland University, Germany; Hasso Plattner Institute - University of Potsdam, Germany) Article Search Article: stoc26main-p292-p STOC '26: "Contention Resolution, with ..." Contention Resolution, with and without a Global Clock Zixi Cai, Kuowen Chen, Shengquan Du, Tsvi Kopelowitz, Seth Pettie, and Ben Plosk (Tsinghua University, China; Bar-Ilan University, Israel; University of Michigan, USA) Article Search Article: stoc26main-p360-p
	Pilipczuk, Marcin	STOC '26: "Pattern-Sparse Tree Decompositions ..." Pattern-Sparse Tree Decompositions in H-Minor-Free Graphs Dániel Marx, Marcin Pilipczuk, and Michał Pilipczuk (CISPA Helmholtz Center for Information Security, Germany; University of Warsaw, Poland) Article Search Article: stoc26main-p775-p
	Pilipczuk, Michał	STOC '26: "Efficient Reversal of Transductions ..." Efficient Reversal of Transductions of Sparse Graph Classes Jakub Gajarský, Michał Pilipczuk, and Jan Dreier (University of Warsaw, Poland; TU Wien, Austria) Article Search Article: stoc26main-p530-p STOC '26: "Pattern-Sparse Tree Decompositions ..." Pattern-Sparse Tree Decompositions in H-Minor-Free Graphs Dániel Marx, Marcin Pilipczuk, and Michał Pilipczuk (CISPA Helmholtz Center for Information Security, Germany; University of Warsaw, Poland) Article Search Article: stoc26main-p775-p
	Pires, William	STOC '26: "Boolean Function Monotonicity ..." Boolean Function Monotonicity Testing Requires (Almost) n1/2 Queries Mark Chen, Xi Chen, Hao Cui, William Pires, and Jonah Stockwell (Columbia University, USA) Article Search Article: stoc26main-p270-p
	Pitassi, Toniann	STOC '26: "High Rate Efficient Local ..." High Rate Efficient Local List Decoding from HDX Yotam Dikstein, Max Hopkins, Toniann Pitassi, and Russell Impagliazzo (Institute for Advanced Study at Princeton, USA; Princeton University, USA; Columbia University, USA; University of California at San Diego, USA) Article Search Article: stoc26main-p1064-p
	Pittu, Madhusudhan	STOC '26: "Combinatorial Optimization ..." Combinatorial Optimization using Comparison Oracles Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Pittu, Jon Schneider, and David P. Woodruff (Google Research, New-York, USA; Bocconi University, Italy; New York University, USA; Google Research, USA; University of Michigan, USA; Duke University, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p1341-p
	Plosk, Ben	STOC '26: "Contention Resolution, with ..." Contention Resolution, with and without a Global Clock Zixi Cai, Kuowen Chen, Shengquan Du, Tsvi Kopelowitz, Seth Pettie, and Ben Plosk (Tsinghua University, China; Bar-Ilan University, Israel; University of Michigan, USA) Article Search Article: stoc26main-p360-p
	Poremba, Alexander	STOC '26: "Average-Case Complexity of ..." Average-Case Complexity of Quantum Stabilizer Decoding Andrey Boris Khesin, Jonathan Lu, Alexander Poremba, Akshar Ramkumar, and Vinod Vaikuntanathan (University of Oxford, UK; Massachusetts Institute of Technology, USA; Boston University, USA; California Institute of Technology, USA) Article Search Article: stoc26main-p373-p
	Potechin, Aaron	STOC '26: "Improved Approximation Algorithms ..." Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes Joshua Brakensiek, Neng Huang, Aaron Potechin, and Uri Zwick (University of California at Berkeley, USA; University of Michigan, USA; University of Chicago, USA; Tel Aviv University, Israel) Article Search Article: stoc26main-p713-p
	Przybocki, Benjamin	STOC '26: "Optimal and Efficient Partite ..." Optimal and Efficient Partite Decompositions of Hypergraphs Andrew Krapivin, Benjamin Przybocki, Nicolás Sanhueza-Matamala, and Bernardo Subercaseaux (Carnegie Mellon University, USA; Universidad de Concepción, Chile) Article Search Article: stoc26main-p1693-p
	Quanrud, Kent	STOC '26: "Approximating Directed Connectivity ..." Approximating Directed Connectivity in Almost-Linear Time Kent Quanrud (Purdue University, USA) Article Search Article: stoc26main-p791-p STOC '26: "From Hop Reduction to Sparsification ..." From Hop Reduction to Sparsification for Negative Length Shortest Paths Kent Quanrud and Navid Tajkhorshid (Purdue University, USA; University of Illinois at Urbana-Champaign, USA) Article Search Article: stoc26main-p1292-p
	Räcke, Harald	STOC '26: "An Improved Quality Hierarchical ..." An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time Monika Henzinger, Robin Münk, and Harald Räcke (IST Austria, Austria; TU Munich, Germany) Article Search Article: stoc26main-p678-p STOC '26: "Nonuniform Graph Partitioning ..." Nonuniform Graph Partitioning with Just a Little Flex Neil Olver, Harald Räcke, and Stefan Schmid (London School of Economics and Political Science, UK; TU Munich, Germany; TU Berlin, Germany; Fraunhofer SIT, Germany) Article Search Article: stoc26main-p989-p
	Rai, Shanthanu S.	STOC '26: "Closure under Factorization ..." Closure under Factorization from a Result of Furstenberg Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, and Shubhangi Saraf (University of Toronto, Canada; Tata Institute of Fundamental Research, Mumbai, India) Article Search Article: stoc26main-p81-p
	Raj, Roshan	STOC '26: "Learning Read-Once Determinants ..." Learning Read-Once Determinants and the Principal Minor Assignment Problem Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, and Chandan Saha (IISc Bangalore, India; IIT Kanpur, India; ISI Kolkata, India; IIT Bombay, India; Tata Institute of Fundamental Research, Mumbai, India) Article Search Article: stoc26main-p909-p
	Rajaraman, Amit	STOC '26: "Markov Chains Approximate ..." Markov Chains Approximate Message Passing Amit Rajaraman and David X. Wu (Massachusetts Institute of Technology, USA; University of California at Berkeley, USA) Article Search Article: stoc26main-p535-p
	Ramachandran, Srikkanth	STOC '26: "Improved Local Computation ..." Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates Slobodan Mitrović, Srikkanth Ramachandran, Ronitt Rubinfeld, and Mihir Singhal (University of California at Davis, USA; University of Novi Sad, Serbia; Massachusetts Institute of Technology, USA; University of California at Berkeley, USA) Article Search Article: stoc26main-p551-p
	Ramanathan, Varun	STOC '26: "Closure under Factorization ..." Closure under Factorization from a Result of Furstenberg Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, and Shubhangi Saraf (University of Toronto, Canada; Tata Institute of Fundamental Research, Mumbai, India) Article Search Article: stoc26main-p81-p
	Ramkumar, Akshar	STOC '26: "Average-Case Complexity of ..." Average-Case Complexity of Quantum Stabilizer Decoding Andrey Boris Khesin, Jonathan Lu, Alexander Poremba, Akshar Ramkumar, and Vinod Vaikuntanathan (University of Oxford, UK; Massachusetts Institute of Technology, USA; Boston University, USA; California Institute of Technology, USA) Article Search Article: stoc26main-p373-p
	Randolph, Tim	STOC '26: "Beating Meet-in-the-Middle ..." Beating Meet-in-the-Middle for Subset Balancing Problems Tim Randolph and Karol Węgrzycki (Harvey Mudd College, USA; MPI-INF, Germany) Article Search Article: stoc26main-p606-p
	Rao, Satish	STOC '26: "Shortcutting for Negative-Weight ..." Shortcutting for Negative-Weight Shortest Paths George Z. Li, Jason Li, Satish Rao, and Junkai Zhang (Carnegie Mellon University, USA; University of California at Berkeley, USA; Tsinghua University, China) Article Search Article: stoc26main-p125-p
	Rapaport, Ivan	STOC '26: "What Can Be Computed Locally ..." What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing Lelia Blin, Fedor V. Fomin, Pierre Fraigniaud, Sylvain Gay, Petr A. Golovach, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca (Université Paris Cité - IRIF - CNRS, France; University of Bergen, Norway; CNRS - Université de Paris, France; École Normale Supérieure, France; Universidad Adolfo Ibáñez, Chile; Universidad de Chile, Chile; Université d'Orléans, France) Article Search Article: stoc26main-p673-p
	Redžić, Mirza	STOC '26: "Classifying Identities: Subcubic ..." Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection Bartłomiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin, Marvin Künnemann, Xiao Mao, and Mirza Redžić (University of Wrocław, Poland; MPI-INF, Germany; KIT, Germany; University of California at Berkeley, USA; Stanford University, USA) Article Search Article: stoc26main-p715-p
	Regts, Guus	STOC '26: "On Zeros and Algorithms for ..." On Zeros and Algorithms for Disordered Systems: Mean-Field Spin Glasses Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, and Guus Regts (CWI, Netherlands; Stanford University, USA; Massachusetts Institute of Technology, USA; University of Amsterdam, Netherlands) Article Search Article: stoc26main-p245-p
	Ren, Hanlin	STOC '26: "The Weak Rank Principle: Lower ..." The Weak Rank Principle: Lower Bounds and Applications Michal Garlík, Svyatoslav Gryaznov, Hanlin Ren, and Iddo Tzameret (Imperial College London, UK; Institute for Advanced Study at Princeton, USA) Article Search Article: stoc26main-p65-p STOC '26: "Finding Bugs in Short Proofs: ..." Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds Jiawei Li, Yuhao Li, and Hanlin Ren (University of Texas at Austin, USA; Columbia University, USA; Institute for Advanced Study at Princeton, USA) Article Search Article: stoc26main-p343-p
	Riazanov, Artur	STOC '26: "Monotone Circuit Complexity ..." Monotone Circuit Complexity of Matching Bruno Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov (University of Oxford, UK; EPFL, Switzerland; Université de Montréal, Canada) Article Search Article: stoc26main-p518-p STOC '26: "Pseudodeterministic Communication ..." Pseudodeterministic Communication Complexity Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, and Weiqiang Yuan (EPFL, Switzerland; University of British Columbia, Canada; Université de Montréal, Canada) Article Search Article: stoc26main-p1390-p STOC '26: "Sampling Permutations with ..." Sampling Permutations with Cell Probes Is Hard Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, and Dmitry Sokolov (Technion, Israel; EPFL, Switzerland; Université de Montréal, Canada) Article Search Article: stoc26main-p108-p
	Ringach, Noam	STOC '26: "Improved Bounds for Coin Flipping, ..." Improved Bounds for Coin Flipping, Leader Election, and Random Selection Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, and Rocco A. Servedio (Cornell University, USA; Columbia University, USA) Article Search Article: stoc26main-p777-p
	Roeyskoe, Antti	STOC '26: "A Constant-Approximation Distance ..." A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures Bernhard Haeupler, Yaowei Long, Antti Roeyskoe, and Thatchaphol Saranurak (INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; ETH Zurich, Switzerland; University of Michigan, USA) Article Search Article: stoc26main-p454-p
	Rohwedder, Lars	STOC '26: "Randomized Rounding over Dynamic ..." Randomized Rounding over Dynamic Programs Étienne Bamas, Shi Li, and Lars Rohwedder (EPFL, Switzerland; Nanjing University, China; University of Southern Denmark, Denmark) Article Search Article: stoc26main-p1143-p
	Rosen, Alon	STOC '26: "Secret-Key PIR from Random ..." Secret-Key PIR from Random Linear Codes Caicai Chen, Yuval Ishai, Tamer Mour, and Alon Rosen (Bocconi University, Italy; Technion, Israel; AWS, USA) Article Search Article: stoc26main-p1368-p STOC '26: "Adaptive Robustness of Hypergrid ..." Adaptive Robustness of Hypergrid Johnson-Lindenstrauss Andrej Bogdanov, Alon Rosen, Neekon Vafa, and Vinod Vaikuntanathan (University of Ottawa, Canada; Bocconi University, Italy; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p98-p
	Rubinfeld, Ronitt	STOC '26: "Improved Local Computation ..." Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates Slobodan Mitrović, Srikkanth Ramachandran, Ronitt Rubinfeld, and Mihir Singhal (University of California at Davis, USA; University of Novi Sad, Serbia; Massachusetts Institute of Technology, USA; University of California at Berkeley, USA) Article Search Article: stoc26main-p551-p
	Rubinstein, Aviad	STOC '26: "Secretary, Prophet, and Stochastic ..." Secretary, Prophet, and Stochastic Probing via Big-Decisions-First Aviad Rubinstein and Sahil Singla (Stanford University, USA; Georgia Institute of Technology, USA) Article Search Article: stoc26main-p569-p STOC '26: "Approximating Gains-from-Trade ..." Approximating Gains-from-Trade in Matching Markets Moshe Babaioff, Aviad Rubinstein, Xizhi Tan, and Kangning Wang (Hebrew University of Jerusalem, Israel; Stanford University, USA; Rutgers University, USA) Article Search Article: stoc26main-p305-p STOC '26: "Approximation Schemes for ..." Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time Xiao Mao and Aviad Rubinstein (Stanford University, USA) Article Search Article: stoc26main-p322-p
	S., Karthik C.	STOC '26: "Fine-Grained Complexity of ..." Fine-Grained Complexity of Continuous Euclidean k-Center Lotte Blank, Karl Bringmann, Parinya Chalermsook, Karthik C. S., Benedikt Kolbe, Hung Le, and Geert van Wordragen (University of Bonn, Germany; Saarland University, Germany; MPI-INF, Germany; University of Sheffield, UK; Rutgers University, USA; University of Massachusetts at Amherst, USA; Aalto University, Finland) Article Search Article: stoc26main-p171-p
	Safra, Muli	STOC '26: "Deterministic Hardness of ..." Deterministic Hardness of Approximation of Unique-SVP and GapSVP in ℓp Norms for p<2 Yahli Hecht and Muli Safra (Tel Aviv University, Israel) Article Search Article: stoc26main-p388-p
	Sagunov, Danil	STOC '26: "Path Cover, Hamiltonicity, ..." Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective Fedor V. Fomin, Petr A. Golovach, Nikola Jedličková, Jan Kratochvíl, Danil Sagunov, and Kirill Simonov (University of Bergen, Norway; Charles University, Czech Republic; Saint Petersburg State University, Russian Federation) Article Search Article: stoc26main-p127-p
	Saha, Barna	STOC '26: "On the Computational Hardness ..." On the Computational Hardness of Transformers Barna Saha, Yinzhan Xu, Christopher Ye, and Hantao Yu (University of California at San Diego, USA; Columbia University, USA) Article Search Article: stoc26main-p482-p
	Saha, Chandan	STOC '26: "Learning Read-Once Determinants ..." Learning Read-Once Determinants and the Principal Minor Assignment Problem Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, and Chandan Saha (IISc Bangalore, India; IIT Kanpur, India; ISI Kolkata, India; IIT Bombay, India; Tata Institute of Fundamental Research, Mumbai, India) Article Search Article: stoc26main-p909-p
	Sahai, Amit	STOC '26: "SVPp Is ..." SVPp Is NP-Hard for All p > 2, Even to Approximate within a Factor of 2log1-εn Isaac M. Hair and Amit Sahai (University of California at Santa Barbara, USA; University of California at Los Angeles, USA) Article Search Article: stoc26main-p958-p
	Saks, Michael E.	STOC '26: "The Natural Proofs Barrier ..." The Natural Proofs Barrier against Data-Structure Lower-Bounds Bruno Loff, Michal Koucký, Tulasimohan Molli, and Michael E. Saks (LASIGE, Portugal; University of Lisbon, Portugal; Charles University, Czech Republic; Rutgers University, USA) Article Search Article: stoc26main-p628-p
	Saneian, Mohammad	STOC '26: "Half-Approximating Maximum ..." Half-Approximating Maximum Dicut in the Streaming Setting Amir Azarmehr, Soheil Behnezhad, Shane Ferrante, and Mohammad Saneian (Northeastern University, USA) Article Search Article: stoc26main-p1536-p
	Sanhueza-Matamala, Nicolás	STOC '26: "Optimal and Efficient Partite ..." Optimal and Efficient Partite Decompositions of Hypergraphs Andrew Krapivin, Benjamin Przybocki, Nicolás Sanhueza-Matamala, and Bernardo Subercaseaux (Carnegie Mellon University, USA; Universidad de Concepción, Chile) Article Search Article: stoc26main-p1693-p
	Saptharishi, Ramprasad	STOC '26: "Closure under Factorization ..." Closure under Factorization from a Result of Furstenberg Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, and Shubhangi Saraf (University of Toronto, Canada; Tata Institute of Fundamental Research, Mumbai, India) Article Search Article: stoc26main-p81-p
	Saraf, Shubhangi	STOC '26: "On Proximity Gaps of Reed-Solomon ..." On Proximity Gaps of Reed-Solomon Codes Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, and Shubhangi Saraf (StarkWare Industries, Israel; StarkWare Industries, Poland; University of Toronto, Canada) Article Search Article: stoc26main-p523-p STOC '26: "Reconstruction of Depth-3 ..." Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-In Shubhangi Saraf, Devansh Shringi, and Narmada Varadarajan (University of Toronto, Canada) Article Search Article: stoc26main-p954-p STOC '26: "Closure under Factorization ..." Closure under Factorization from a Result of Furstenberg Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, and Shubhangi Saraf (University of Toronto, Canada; Tata Institute of Fundamental Research, Mumbai, India) Article Search Article: stoc26main-p81-p
	Saranurak, Thatchaphol	STOC '26: "A Constant-Approximation Distance ..." A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures Bernhard Haeupler, Yaowei Long, Antti Roeyskoe, and Thatchaphol Saranurak (INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; ETH Zurich, Switzerland; University of Michigan, USA) Article Search Article: stoc26main-p454-p STOC '26: "Deterministic Negative-Weight ..." Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers Bernhard Haeupler, Yonggang Jiang, and Thatchaphol Saranurak (INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; ETH Zurich, Switzerland; MPI-INF, Germany; Saarland University, Germany; University of Michigan, USA) Article Search Article: stoc26main-p87-p STOC '26: "DAG Projections: Reducing ..." DAG Projections: Reducing Distance and Flow Problems to DAGs Bernhard Haeupler, Yonggang Jiang, and Thatchaphol Saranurak (INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; ETH Zurich, Switzerland; MPI-INF, Germany; Saarland University, Germany; University of Michigan, USA) Article Search Article: stoc26main-p1972-p STOC '26: "Reviving Thorup’s Shortcut ..." Reviving Thorup’s Shortcut Conjecture Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, and Leon Schiller (New York University, USA; Carnegie Mellon University, USA; ETH Zurich, Switzerland; INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; University of Michigan, USA; MPI-INF, Germany; Saarland University, Germany; Hasso Plattner Institute - University of Potsdam, Germany) Article Search Article: stoc26main-p292-p
	Saraogi, Sidhant	STOC '26: "Nearly Tight Lower Bounds ..." Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies Guy Goldberg, Tom Gur, and Sidhant Saraogi (Weizmann Institute of Science, Israel; University of Cambridge, UK; Georgetown University, USA) Article Search Article: stoc26main-p1782-p
	Saurabh, Saket	STOC '26: "Oracle Subset Problems: A ..." Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks Ishan Chakraborty, Tanmay Inamdar, Ariel Kulik, Madhumita Kundu, and Saket Saurabh (Institute of Mathematical Sciences, Chennai, India; IIT Jodhpur, India; Ben-Gurion University of the Negev, Israel; University of Bergen, Norway; Institute of Mathematical Sciences, India) Article Search Article: stoc26main-p443-p STOC '26: "Fine-Grained Bounds for Courcelle’s ..." Fine-Grained Bounds for Courcelle’s Theorem Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi (University of California Santa Barbara, USA; University of Leeds, UK; Institute of Mathematical Sciences, India; New York University Shanghai, China; Ben-Gurion University of the Negev, Israel) Article Search Article: stoc26main-p1957-p
	Savask	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Schild, Aaron	STOC '26: "Breaking Barriers for Distributed ..." Breaking Barriers for Distributed MIS by Faster Degree Reduction Seri Khoury and Aaron Schild (INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; Google Research, USA) Article Search Article: stoc26main-p470-p
	Schiller, Leon	STOC '26: "Reviving Thorup’s Shortcut ..." Reviving Thorup’s Shortcut Conjecture Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, and Leon Schiller (New York University, USA; Carnegie Mellon University, USA; ETH Zurich, Switzerland; INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; University of Michigan, USA; MPI-INF, Germany; Saarland University, Germany; Hasso Plattner Institute - University of Potsdam, Germany) Article Search Article: stoc26main-p292-p
	Schmid, Stefan	STOC '26: "Nonuniform Graph Partitioning ..." Nonuniform Graph Partitioning with Just a Little Flex Neil Olver, Harald Räcke, and Stefan Schmid (London School of Economics and Political Science, UK; TU Munich, Germany; TU Berlin, Germany; Fraunhofer SIT, Germany) Article Search Article: stoc26main-p989-p STOC '26: "Perfect Network Resilience ..." Perfect Network Resilience in Polynomial Time Matthias Bentert and Stefan Schmid (TU Berlin, Germany; Fraunhofer SIT, Germany) Modern communication networks support local fast rerouting mechanisms to quickly react to link failures: nodes store a set of conditional rerouting rules which define how to forward an incoming packet in case of incident link failures. Ideally, such rerouting mechanisms provide perfect resilience: any packet is routed from its source s to its target t as long as s and t are still connected in the underlying graph after the link failures. However, ensuring perfect resilience is algorithmically challenging as the rerouting decisions at any node v must rely solely on the local information available at v: the link from which a packet arrived at v (known as the in-port), the target of the packet, and the incident link failures at v. Already in their seminal paper at ACM PODC’12, Feigenbaum, Godfrey, Panda, Schapira, Shenker, and Singla showed that there are instances in which perfect resilience cannot be achieved. While the design of local rerouting algorithms has received much attention since then, we still lack a detailed understanding of when perfect resilience is achievable. This paper closes this gap and presents a complete characterization of when perfect resilience can be achieved. This characterization also allows us to design an O(n)-time algorithm to decide whether a given instance is perfectly resilient and an O(nm)-time algorithm to compute perfectly resilient rerouting rules whenever it is. Our algorithm is also attractive for the simple structure of the rerouting rules it uses, known as skipping in the literature: alternative links are chosen according to an ordered priority list (per in-port), where failed links are simply skipped. This is also naturally supported in hardware. The size of such an encoding is in Θ(nm) and therefore the running time of our algorithm is optimal when considering skipping rerouting rules. Intriguingly, our result also implies that in the context of perfect resilience, skipping rerouting rules are as powerful as more general rerouting rules that define the out-port for each set of incident failed links explicitly. This partially answers a long-standing open question by Chiesa, Nikolaevskiy, Mitrovic, Gurtov, Madry, Schapira, and Shenker [IEEE/ACM Transactions on Networking, 2017] in the affirmative. While our algorithm is simple, its analysis is intricate. A key concept in the analysis are links whose two endpoints also form a node separator. We prove that removing those links does not change whether a given instance is perfectly resilient or not. We also show that once all such links are removed, any instance either contains one of four specific rooted minors or belongs to one of three classes. If one of the four rooted minors is contained, then we are dealing with a no-instance (this was previously known for only two of them). Lastly, we show that any instance in any of the three remaining classes is a yes-instance, completing the characterization of perfectly resilient graphs. We do this by showing that simply following a particular face of a planar embedding of the reduced instance using the right-hand rule until a link directly to the target is found is sufficient. Article Search Article: stoc26main-p277-p
	Schneider, Jon	STOC '26: "Combinatorial Optimization ..." Combinatorial Optimization using Comparison Oracles Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Pittu, Jon Schneider, and David P. Woodruff (Google Research, New-York, USA; Bocconi University, Italy; New York University, USA; Google Research, USA; University of Michigan, USA; Duke University, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p1341-p
	Schwartz, Roy	STOC '26: "A Poisson Process for Submodular ..." A Poisson Process for Submodular Maximization Amit Ganz, Ariel Kulik, Roy Schwartz, and Mohit Singh (Technion, Israel; Ben-Gurion University of the Negev, Israel; Georgia Institute of Technology, USA) Article Search Article: stoc26main-p1663-p
	Seppelt, Tim	STOC '26: "Lower Bounds in Algebraic ..." Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials Prateek Dwivedi, Benedikt Pago, and Tim Seppelt (IT University of Copenhagen, Denmark; University of Cambridge, UK) Article Search Article: stoc26main-p286-p
	Servedio, Rocco A.	STOC '26: "A Mysterious Connection between ..." A Mysterious Connection between Tolerant Junta Testing and Agnostically Learning Conjunctions Xi Chen, Shyamal Patel, and Rocco A. Servedio (Columbia University, USA) Article Search Article: stoc26main-p48-p STOC '26: "Improved Bounds for Coin Flipping, ..." Improved Bounds for Coin Flipping, Leader Election, and Random Selection Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, and Rocco A. Servedio (Cornell University, USA; Columbia University, USA) Article Search Article: stoc26main-p777-p STOC '26: "Learning Functions of Halfspaces ..." Learning Functions of Halfspaces Josh Alman, Shyamal Patel, and Rocco A. Servedio (Columbia University, USA) Article Search Article: stoc26main-p827-p STOC '26: "Sparsifying Suprema of Gaussian ..." Sparsifying Suprema of Gaussian Processes Anindya De, Shivam Nadimpalli, Ryan O'Donnell, and Rocco A. Servedio (University of Pennsylvania, USA; Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; Columbia University, USA) We give a dimension-independent sparsification result for suprema of centered Gaussian processes: Let T be any (possibly infinite) bounded set of vectors in n, and let {t := t · g }t∈ T be the canonical Gaussian process on T, where g∼ N(0, In). We show that there is an Oε(1)-size subset S ⊆ T and a set of real values {cs}s ∈ S such that the random variable sups ∈ S {Xs + cs} is an ε-approximator (in L1) of the random variable supt ∈ T Xt. Notably, the size of the sparsifier S is completely independent of both |T| and the ambient dimension n. We give two applications of this sparsification theorem: <ul> <li><strong>A “Junta Theorem” for Norms:</strong> We show that given any norm ν(x) on n, there is another norm ψ(x) depending only on the projection of x onto Oε(1) directions, for which ψ(g) is a multiplicative (1 ± ε)-approximation of ν(g) with probability 1−ε for g ∼ N(0,In). </li> <li><strong>Sparsification of Convex Sets:</strong> We show that any intersection of (possibly infinitely many) halfspaces in n that are at distance r from the origin is ε-close (under N(0,In)) to an intersection of only Or,ε(1) halfspaces. This yields new polynomial-time agnostic learning and tolerant property testing algorithms for intersections of halfspaces. </li> </ul> Article Search Article: stoc26main-p202-p STOC '26: "Testing Noisy Low-Degree Polynomials ..." Testing Noisy Low-Degree Polynomials for Sparsity Yiqiao Bao, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, and Nathan White (University of Pennsylvania, USA; Massachusetts Institute of Technology, USA; Columbia University, USA) Article Search Article: stoc26main-p348-p
	Shafrir, Doron	STOC '26: "S-Unit Equations in Modules ..." S-Unit Equations in Modules and Linear-Exponential Diophantine Equations Ruiwen Dong and Doron Shafrir (University of Oxford, UK; Ben-Gurion University of the Negev, Israel) Let T be a positive integer and M be a finitely presented module over the Laurent polynomial ring ℤ/T[X1±, …, XN±]. We consider S-unit equations over M: these are equations of the form x1 m1 + ⋯ + xK mK = m0, where the variables x1, …, xK range over the set of monomials (with coefficient 1) of ℤ/T[X1±, …, XN±]. When T is a power of a prime number p, we show that the solution set of an S-unit equation over M is effectively p-normal in the sense of Derksen and Masser (2015). This generalizes their result on S-unit equations in fields of prime characteristic. When T is an arbitrary positive integer, we show that deciding whether an S-unit equation over M admits a solution is Turing equivalent to solving a system of linear-exponential Diophantine equations, whose base contains the prime divisors of T. Combined with a recent result of Karimov, Luca, Nieuwveld, Ouaknine and Worrell (2025), this yields decidability when T has at most two distinct prime divisors. This also shows that proving either decidability or undecidability in the case of arbitrary T would entail major breakthroughs in number theory. S-unit equations in modules have direct connections to many problems in computational algebra such as finding sparse polynomials in ideals, identifying zeros of linear recurrence sequences, and deciding membership problems in metabelian groups. In particular, a direct consequence of our result is the decidability Submonoid Membership in wreath products of the form ℤ/pa qb ≀ ℤd. Article Search Article: stoc26main-p56-p STOC '26: "The Skolem Problem in Rings ..." The Skolem Problem in Rings of Positive Characteristic Ruiwen Dong and Doron Shafrir (University of Oxford, UK; Ben-Gurion University of the Negev, Israel) We show that the Skolem Problem is decidable in finitely generated commutative rings of positive characteristic. More precisely, we show that there exists an algorithm which, given a finite presentation of a (unitary) commutative ring R = ℤ/T[X1, …, Xn]/I of characteristic T > 0, and a linear recurrence sequence (γn)n ∈ ℕ ∈ Rℕ, determines whether (γn)n ∈ ℕ contains a zero term. Our proof is based on two recent results: Dong and Shafrir (2026) on the solution set of S-unit equations over pe-torsion modules, and Karimov, Luca, Nieuwveld, Ouaknine, and Worrell (2025) on solving linear equations over powers of two multiplicatively independent numbers. Our result implies, moreover, that the zero set of a linear recurrence sequence over a ring of characteristic T = p1e1 ⋯ pkek is effectively a finite union of pi-normal sets in the sense of Derksen (2007). Article Search Article: stoc26main-p169-p
	Shagrithaya, Nikhil	STOC '26: "Probabilistic Guarantees to ..." Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes Fernando Granha Jeronimo and Nikhil Shagrithaya (University of Illinois at Urbana-Champaign, USA; University of Michigan at Ann Arbor, USA) Article Search Article: stoc26main-p352-p
	Shaltiel, Ronen	STOC '26: "Extractors for Samplable Distributions ..." Extractors for Samplable Distributions from the Two-Source Extractor Recipe Justin Oh and Ronen Shaltiel (University of Haifa, Israel) Article Search Article: stoc26main-p633-p
	Shao, Shuai	STOC '26: "New Planar Algorithms and ..." New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model Jin-Yi Cai, Austen Fan, Shuai Shao, and Zhuxiao Tang (University of Wisconsin-Madison, USA; University of Science and Technology of China, China) Article Search Article: stoc26main-p428-p
	Sharan, Vatsal	STOC '26: "A Unified Approach to Memory-Sample ..." A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures Sumegha Garg, Jabari Hastings, Chirag Pabbaraju, and Vatsal Sharan (Rutgers University, USA; Stanford University, USA; University of Southern California, USA) Article Search Article: stoc26main-p85-p
	Shen, Yiheng	STOC '26: "The Price of Competitive Information ..." The Price of Competitive Information Disclosure Sid Banerjee, Kamesh Munagala, Yiheng Shen, and Kangning Wang (Cornell University, USA; Duke University, USA; Rutgers University, USA) Article Search Article: stoc26main-p601-p
	Shimizu, Nobutaka	STOC '26: "Hardness Amplification beyond ..." Hardness Amplification beyond Boolean Functions Nobutaka Shimizu and Kenji Yasunaga (Institute of Science Tokyo, Japan) Article Search Article: stoc26main-p590-p STOC '26: "Optimal Random Self-Reductions ..." Optimal Random Self-Reductions for All Linear Problems Shuichi Hirahara and Nobutaka Shimizu (National Institute of Informatics, Tokyo, Japan; Institute of Science Tokyo, Japan) Article Search Article: stoc26main-p264-p
	Shin, Suho	STOC '26: "Optimal Contest beyond Convexity ..." Optimal Contest beyond Convexity Negin Golrezaei, MohammadTaghi Hajiaghayi, and Suho Shin (Massachusetts Institute of Technology, USA; University of Maryland, USA) Article Search Article: stoc26main-p69-p
	Shringi, Devansh	STOC '26: "Reconstruction of Depth-3 ..." Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-In Shubhangi Saraf, Devansh Shringi, and Narmada Varadarajan (University of Toronto, Canada) Article Search Article: stoc26main-p954-p
	Sidford, Aaron	STOC '26: "Solving Matrix Games with ..." Solving Matrix Games with Near-Optimal Matvec Complexity Ishani Karmarkar, Liam O'Carroll, and Aaron Sidford (Stanford University, USA) Article Search Article: stoc26main-p975-p
	Simonov, Kirill	STOC '26: "Path Cover, Hamiltonicity, ..." Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective Fedor V. Fomin, Petr A. Golovach, Nikola Jedličková, Jan Kratochvíl, Danil Sagunov, and Kirill Simonov (University of Bergen, Norway; Charles University, Czech Republic; Saint Petersburg State University, Russian Federation) Article Search Article: stoc26main-p127-p
	Singh, Mohit	STOC '26: "A Poisson Process for Submodular ..." A Poisson Process for Submodular Maximization Amit Ganz, Ariel Kulik, Roy Schwartz, and Mohit Singh (Technion, Israel; Ben-Gurion University of the Negev, Israel; Georgia Institute of Technology, USA) Article Search Article: stoc26main-p1663-p
	Singhal, Mihir	STOC '26: "Improved Local Computation ..." Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates Slobodan Mitrović, Srikkanth Ramachandran, Ronitt Rubinfeld, and Mihir Singhal (University of California at Davis, USA; University of Novi Sad, Serbia; Massachusetts Institute of Technology, USA; University of California at Berkeley, USA) Article Search Article: stoc26main-p551-p
	Singla, Sahil	STOC '26: "Online Combinatorial Optimization ..." Online Combinatorial Optimization with Graphical Dependencies Zhimeng Gao, Evangelia Gergatsouli, Kalen Patton, and Sahil Singla (Georgia Institute of Technology, USA) Article Search Article: stoc26main-p545-p STOC '26: "Secretary, Prophet, and Stochastic ..." Secretary, Prophet, and Stochastic Probing via Big-Decisions-First Aviad Rubinstein and Sahil Singla (Stanford University, USA; Georgia Institute of Technology, USA) Article Search Article: stoc26main-p569-p
	Slot, Lucas	STOC '26: "Hesse’s Redemption: Efficient ..." Hesse’s Redemption: Efficient Convex Polynomial Programming Lucas Slot, David Steurer, and Manuel Wiedmer (ETH Zurich, Switzerland) Article Search Article: stoc26main-p193-p
	Slote, Joseph	STOC '26: "Quantum Precomputation: Parallelizing ..." Quantum Precomputation: Parallelizing Cascade Circuits and the Moore–Nilsson Conjecture Is False Adam Bene Watts, Charles R. Chen, J. William Helton, and Joseph Slote (University of Calgary, Canada; University of California at San Diego, USA; University of Washington, USA) Article Search Article: stoc26main-p487-p STOC '26: "The Power of Two Bases: Nearly ..." The Power of Two Bases: Nearly Robust and Copy-Optimal Certification of Nearly All Quantum States with Single-Qubit Measurements Andrea Coladangelo, Jerry Li, Joseph Slote, and Ellen Wu (University of Washington, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p999-p
	Sofronova, Anastasia	STOC '26: "Monotone Circuit Complexity ..." Monotone Circuit Complexity of Matching Bruno Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov (University of Oxford, UK; EPFL, Switzerland; Université de Montréal, Canada) Article Search Article: stoc26main-p518-p STOC '26: "Pseudodeterministic Communication ..." Pseudodeterministic Communication Complexity Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, and Weiqiang Yuan (EPFL, Switzerland; University of British Columbia, Canada; Université de Montréal, Canada) Article Search Article: stoc26main-p1390-p
	Sokolov, Dmitry	STOC '26: "Monotone Circuit Complexity ..." Monotone Circuit Complexity of Matching Bruno Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov (University of Oxford, UK; EPFL, Switzerland; Université de Montréal, Canada) Article Search Article: stoc26main-p518-p STOC '26: "Pseudodeterministic Communication ..." Pseudodeterministic Communication Complexity Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, and Weiqiang Yuan (EPFL, Switzerland; University of British Columbia, Canada; Université de Montréal, Canada) Article Search Article: stoc26main-p1390-p STOC '26: "Sampling Permutations with ..." Sampling Permutations with Cell Probes Is Hard Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, and Dmitry Sokolov (Technion, Israel; EPFL, Switzerland; Université de Montréal, Canada) Article Search Article: stoc26main-p108-p
	Somma, Rolando D.	STOC '26: "Efficient Quantum Hermite ..." Efficient Quantum Hermite Transform Siddhartha Jain, Vishnu Iyer, Rolando D. Somma, Ning Bao, and Stephen Jordan (University of Texas at Austin, USA; Google, USA; Northeastern University, USA; Brookhaven National Laboratory, USA) Article Search Article: stoc26main-p255-p
	Song, Junkai	STOC '26: "A Faster Deterministic Algorithm ..." A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching Julia Chuzhoy, Sanjeev Khanna, and Junkai Song (Toyota Technological Institute at Chicago, USA; University of Pennsylvania, USA) Article Search Article: stoc26main-p840-p
	Spilecki, Jack	STOC '26: "The Debiased Keyl’s Algorithm: ..." The Debiased Keyl’s Algorithm: A New Unbiased Estimator for Full State Tomography Angelos Pelecanos, Jack Spilecki, and John Wright (University of California at Berkeley, USA) Article Search Article: stoc26main-p589-p
	Srinivasan, Srikanth	STOC '26: "Ideals, Macaulay Bases, and ..." Ideals, Macaulay Bases, and PCPs Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, and Sophus Valentin Willumsgaard (Harvard University, USA; University of Copenhagen, Denmark) Article Search Article: stoc26main-p505-p STOC '26: "Negations Are Powerful Even ..." Negations Are Powerful Even in Small Depth Bruno Cavalar, Théo Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, and Amir Yehudayoff (University of Oxford, UK; University of Copenhagen, Denmark; Chennai Mathematical Institute, India) Article Search Article: stoc26main-p1423-p
	Stade, Jack	STOC '26: "NP-Membership for the Boundary-Boundary ..." NP-Membership for the Boundary-Boundary Art-Gallery Problem Jack Stade (University of Copenhagen, Denmark) Article Search Article: stoc26main-p120-p STOC '26: "Better Neural Network Expressivity: ..." Better Neural Network Expressivity: Subdividing the Simplex Egor Bakaev, Florestan Brunck, Christoph Hertrich, Jack Stade, and Amir Yehudayoff (University of Copenhagen, Denmark; University of Technology Nuremberg, Germany; Technion, Israel) Article Search Article: stoc26main-p234-p
	Stavropoulos, Konstantinos	STOC '26: "A Fully Polynomial-Time Algorithm ..." A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube Gautam Chandrasekaran, Adam R. Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan (University of Texas at Austin, USA) Article Search Article: stoc26main-p1095-p STOC '26: "Efficient Calibration for ..." Efficient Calibration for Decision Making Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar, and Pranay Tankala (Apple, USA; University of Texas at Austin, USA; Harvard University, USA) Article Search Article: stoc26main-p1666-p STOC '26: "Sparse Linear Regression Is ..." Sparse Linear Regression Is Easy on Random Supports Gautam Chandrasekaran, Raghu Meka, and Konstantinos Stavropoulos (University of Texas at Austin, USA; University of California at Los Angeles, USA) Article Search Article: stoc26main-p1875-p
	Stein, Cliff	STOC '26: "Near-Optimal Directed Euclidean ..." Near-Optimal Directed Euclidean Spanners in High Dimensions Rajesh Jayaram, Shyamal Patel, Cliff Stein, Erik Waingarten, and Tian Zhang (Google Research, USA; Columbia University, USA; University of Pennsylvania, USA) Article Search Article: stoc26main-p703-p STOC '26: "An Optimal Algorithm for Stochastic ..." An Optimal Algorithm for Stochastic Vertex Cover Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Cliff Stein, Miltiadis Stouras, Ola Svensson, and Ali Vakilian (Georgia Institute of Technology, USA; DTU, Denmark; Stanford University, USA; Duke University, USA; Columbia University, USA; EPFL, Switzerland; Virginia Tech, USA) Article Search Article: stoc26main-p798-p
	Stephens-Davidowitz, Noah	STOC '26: "Range Avoidance, Arthur-Merlin, ..." Range Avoidance, Arthur-Merlin, and TFNP Surendra Ghentiyala, Zeyong Li, and Noah Stephens-Davidowitz (Cornell University, USA; National University of Singapore, Singapore) Article Search Article: stoc26main-p1260-p
	Stérin, Tristan	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Steurer, David	STOC '26: "Hesse’s Redemption: Efficient ..." Hesse’s Redemption: Efficient Convex Polynomial Programming Lucas Slot, David Steurer, and Manuel Wiedmer (ETH Zurich, Switzerland) Article Search Article: stoc26main-p193-p
	Stockwell, Jonah	STOC '26: "Boolean Function Monotonicity ..." Boolean Function Monotonicity Testing Requires (Almost) n1/2 Queries Mark Chen, Xi Chen, Hao Cui, William Pires, and Jonah Stockwell (Columbia University, USA) Article Search Article: stoc26main-p270-p
	Stouras, Miltiadis	STOC '26: "An Optimal Algorithm for Stochastic ..." An Optimal Algorithm for Stochastic Vertex Cover Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Cliff Stein, Miltiadis Stouras, Ola Svensson, and Ali Vakilian (Georgia Institute of Technology, USA; DTU, Denmark; Stanford University, USA; Duke University, USA; Columbia University, USA; EPFL, Switzerland; Virginia Tech, USA) Article Search Article: stoc26main-p798-p
	Subercaseaux, Bernardo	STOC '26: "Optimal and Efficient Partite ..." Optimal and Efficient Partite Decompositions of Hypergraphs Andrew Krapivin, Benjamin Przybocki, Nicolás Sanhueza-Matamala, and Bernardo Subercaseaux (Carnegie Mellon University, USA; Universidad de Concepción, Chile) Article Search Article: stoc26main-p1693-p
	Sudan, Madhu	STOC '26: "Ideals, Macaulay Bases, and ..." Ideals, Macaulay Bases, and PCPs Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, and Sophus Valentin Willumsgaard (Harvard University, USA; University of Copenhagen, Denmark) Article Search Article: stoc26main-p505-p
	Sundaresan, Janani	STOC '26: "Settling the Pass Complexity ..." Settling the Pass Complexity of Streaming Set Cover Sepehr Assadi and Janani Sundaresan (University of Waterloo, Canada) Article Search Article: stoc26main-p871-p
	Svendsen, Clement	STOC '26: "The Sample Complexity of Replicable ..." The Sample Complexity of Replicable Realizable PAC Learning Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju, and Clement Svendsen (Aarhus University, Denmark; Stanford University, USA) Article Search Article: stoc26main-p1419-p
	Svensson, Ola	STOC '26: "An Optimal Algorithm for Stochastic ..." An Optimal Algorithm for Stochastic Vertex Cover Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Cliff Stein, Miltiadis Stouras, Ola Svensson, and Ali Vakilian (Georgia Institute of Technology, USA; DTU, Denmark; Stanford University, USA; Duke University, USA; Columbia University, USA; EPFL, Switzerland; Virginia Tech, USA) Article Search Article: stoc26main-p798-p STOC '26: "A Strong Linear Programming ..." A Strong Linear Programming Relaxation for Weighted Tree Augmentation Vincent Cohen-Addad, Marina Drygala, Nathan Klein, and Ola Svensson (Google Research, France; EPFL, Switzerland; Boston University, USA) Article Search Article: stoc26main-p1669-p
	Tajkhorshid, Navid	STOC '26: "From Hop Reduction to Sparsification ..." From Hop Reduction to Sparsification for Negative Length Shortest Paths Kent Quanrud and Navid Tajkhorshid (Purdue University, USA; University of Illinois at Urbana-Champaign, USA) Article Search Article: stoc26main-p1292-p
	Tal, Avishay	STOC '26: "Improved Lower Bounds for ..." Improved Lower Bounds for QAC0 Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, and John Wright (University of California at Berkeley, USA) Article Search Article: stoc26main-p1703-p STOC '26: "Superquadratic Lower Bounds ..." Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits Lijie Chen, Avishay Tal, and Yichuan Wang (University of California at Berkeley, USA) Article Search Article: stoc26main-p385-p
	Talwar, Kunal	STOC '26: "Efficient Calibration for ..." Efficient Calibration for Decision Making Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar, and Pranay Tankala (Apple, USA; University of Texas at Austin, USA; Harvard University, USA) Article Search Article: stoc26main-p1666-p
	Tan, Xizhi	STOC '26: "Approximating Gains-from-Trade ..." Approximating Gains-from-Trade in Matching Markets Moshe Babaioff, Aviad Rubinstein, Xizhi Tan, and Kangning Wang (Hebrew University of Jerusalem, Israel; Stanford University, USA; Rutgers University, USA) Article Search Article: stoc26main-p305-p
	Tan, Zihan	STOC '26: "Lower Bounds on Flow Sparsifiers ..." Lower Bounds on Flow Sparsifiers with Steiner Nodes Yu Chen, Zihan Tan, and Mingyang Yang (National University of Singapore, Singapore; University of Minnesota, USA) Article Search Article: stoc26main-p636-p STOC '26: "Cutting Planarians: Planar ..." Cutting Planarians: Planar Emulators for String Graphs Hsien-Chih Chang, Jonathan Conroy, Zihan Tan, and Da Wei Zheng (Dartmouth College, USA; University of Minnesota, USA; IST Austria, Austria) Article Search Article: stoc26main-p1565-p
	Tang, Ewin	STOC '26: "A Dobrushin Condition for ..." A Dobrushin Condition for Quantum Markov Chains: Rapid Mixing and Conditional Mutual Information at High Temperature Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang (New York University, USA; University of California at Berkeley, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p776-p
	Tang, Haohua	STOC '26: "Online Matrix Factorization, ..." Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization Aleksandar Nikolov, Haohua Tang, and Jonathan Ullman (University of Toronto, Canada; Northeastern University, USA) Article Search Article: stoc26main-p2157-p
	Tang, Zhuxiao	STOC '26: "New Planar Algorithms and ..." New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model Jin-Yi Cai, Austen Fan, Shuai Shao, and Zhuxiao Tang (University of Wisconsin-Madison, USA; University of Science and Technology of China, China) Article Search Article: stoc26main-p428-p
	Tankala, Pranay	STOC '26: "Efficient Calibration for ..." Efficient Calibration for Decision Making Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar, and Pranay Tankala (Apple, USA; University of Texas at Austin, USA; Harvard University, USA) Article Search Article: stoc26main-p1666-p
	Tao, Yixin	STOC '26: "Fisher Meets Lindahl: A Unified ..." Fisher Meets Lindahl: A Unified Duality Framework for Market Equilibrium Yixin Tao and Weiqiang Zheng (Shanghai University of Finance and Economics, China; Yale University, USA) Article Search Article: stoc26main-p138-p
	Tiegel, Stefan	STOC '26: "Rigorous Implications of the ..." Rigorous Implications of the Low-Degree Heuristic Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari, Jerry Li, Sidhanth Mohanty, and Stefan Tiegel (Massachusetts Institute of Technology, USA; University of California at San Diego, USA; Princeton University, USA; University of Washington, USA; Northwestern University, USA) Article Search Article: stoc26main-p995-p
	Tinguely, Antoine	STOC '26: "Improved Approximation Algorithms ..." Improved Approximation Algorithms for Non-preemptive Throughput Maximization Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, and Andreas Wiese (TU Munich, Germany; IDSIA at USI-SUPSI, Switzerland) Article Search Article: stoc26main-p1425-p
	Todinca, Ioan	STOC '26: "What Can Be Computed Locally ..." What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing Lelia Blin, Fedor V. Fomin, Pierre Fraigniaud, Sylvain Gay, Petr A. Golovach, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca (Université Paris Cité - IRIF - CNRS, France; University of Bergen, Norway; CNRS - Université de Paris, France; École Normale Supérieure, France; Universidad Adolfo Ibáñez, Chile; Universidad de Chile, Chile; Université d'Orléans, France) Article Search Article: stoc26main-p673-p
	Toma, Radu	STOC '26: "Average Hardness of SIVP for ..." Average Hardness of SIVP for Module Lattices of Fixed Rank Koen de Boer, Aurel Page, Radu Toma, and Benjamin Wesolowski (Unaffiliated, France; Inria - Univ. Bordeaux - CNRS - Bordeaux INP - IMB - UMR 5251, France; Sorbonne Univ. - Univ. Paris Cité - CNRS - IMJ-PRG, France; ENS de Lyon - CNRS - UMPA - UMR 5669, France) Article Search Article: stoc26main-p353-p
	Tomer, Kabir	STOC '26: "On the Cryptographic Foundations ..." On the Cryptographic Foundations of Interactive Quantum Advantage Kabir Tomer and Mark Zhandry (University of Illinois at Urbana-Champaign, USA; Stanford University, USA; NTT Research, USA) Article Search Article: stoc26main-p217-p
	Traub, Vera	STOC '26: "Steiner Forest: A Simplified ..." Steiner Forest: A Simplified Better-Than-2 Approximation Anupam Gupta and Vera Traub (New York University, USA; ETH Zurich, Switzerland) Article Search Article: stoc26main-p404-p
	Tretiak, Sivan	STOC '26: "Borsuk-Ulam and Replicable ..." Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, and Sivan Tretiak (McGill University, Canada; Ohio State University, USA) Article Search Article: stoc26main-p250-p
	Turner, William	STOC '26: "A Graph Minors Approach to ..." A Graph Minors Approach to Temporal Sequences Johannes Carmesin and William Turner (TU Bergakademie Freiberg, Germany) Article Search Article: stoc26main-p668-p
	Tzameret, Iddo	STOC '26: "The Weak Rank Principle: Lower ..." The Weak Rank Principle: Lower Bounds and Applications Michal Garlík, Svyatoslav Gryaznov, Hanlin Ren, and Iddo Tzameret (Imperial College London, UK; Institute for Advanced Study at Princeton, USA) Article Search Article: stoc26main-p65-p STOC '26: "Lower Bounds against the Ideal ..." Lower Bounds against the Ideal Proof System in Finite Fields Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu, and Iddo Tzameret (Imperial College London, UK) Article Search Article: stoc26main-p4-p
	Ullman, Jonathan	STOC '26: "Online Matrix Factorization, ..." Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization Aleksandar Nikolov, Haohua Tang, and Jonathan Ullman (University of Toronto, Canada; Northeastern University, USA) Article Search Article: stoc26main-p2157-p
	Vafa, Neekon	STOC '26: "Adaptive Robustness of Hypergrid ..." Adaptive Robustness of Hypergrid Johnson-Lindenstrauss Andrej Bogdanov, Alon Rosen, Neekon Vafa, and Vinod Vaikuntanathan (University of Ottawa, Canada; Bocconi University, Italy; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p98-p
	Vaikuntanathan, Vinod	STOC '26: "Adaptive Robustness of Hypergrid ..." Adaptive Robustness of Hypergrid Johnson-Lindenstrauss Andrej Bogdanov, Alon Rosen, Neekon Vafa, and Vinod Vaikuntanathan (University of Ottawa, Canada; Bocconi University, Italy; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p98-p STOC '26: "Average-Case Complexity of ..." Average-Case Complexity of Quantum Stabilizer Decoding Andrey Boris Khesin, Jonathan Lu, Alexander Poremba, Akshar Ramkumar, and Vinod Vaikuntanathan (University of Oxford, UK; Massachusetts Institute of Technology, USA; Boston University, USA; California Institute of Technology, USA) Article Search Article: stoc26main-p373-p
	Vakilian, Ali	STOC '26: "An Optimal Algorithm for Stochastic ..." An Optimal Algorithm for Stochastic Vertex Cover Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Cliff Stein, Miltiadis Stouras, Ola Svensson, and Ali Vakilian (Georgia Institute of Technology, USA; DTU, Denmark; Stanford University, USA; Duke University, USA; Columbia University, USA; EPFL, Switzerland; Virginia Tech, USA) Article Search Article: stoc26main-p798-p
	Van den Brand, Jan	STOC '26: "An Optimal Algorithm for Stochastic ..." An Optimal Algorithm for Stochastic Vertex Cover Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Cliff Stein, Miltiadis Stouras, Ola Svensson, and Ali Vakilian (Georgia Institute of Technology, USA; DTU, Denmark; Stanford University, USA; Duke University, USA; Columbia University, USA; EPFL, Switzerland; Virginia Tech, USA) Article Search Article: stoc26main-p798-p
	Van Dordrecht, Phillipe	STOC '26: "Clifford Testing: Algorithms ..." Clifford Testing: Algorithms and Lower Bounds Marcel Hinsche, Zongbo Bao, Phillipe van Dordrecht, Jens Eisert, Jop Briet, and Jonas Helsen (FU Berlin, Germany; CWI, Netherlands; QuSoft, Netherlands) Article Search Article: stoc26main-p379-p
	Van Wijland, Ernest	STOC '26: "A (4+ϵ)-Approximation for ..." A (4+ϵ)-Approximation for Euclidean 𝑘-Means via Non-monotone Dual-Fitting Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, and Ernest van Wijland (Stanford University, USA; Google Research, France; IDSIA at USI-SUPSI, Switzerland; University of Michigan, USA; Université Paris-Cité - CNRS, France) Article Search Article: stoc26main-p1152-p
	Van Wordragen, Geert	STOC '26: "Fine-Grained Complexity of ..." Fine-Grained Complexity of Continuous Euclidean k-Center Lotte Blank, Karl Bringmann, Parinya Chalermsook, Karthik C. S., Benedikt Kolbe, Hung Le, and Geert van Wordragen (University of Bonn, Germany; Saarland University, Germany; MPI-INF, Germany; University of Sheffield, UK; Rutgers University, USA; University of Massachusetts at Amherst, USA; Aalto University, Finland) Article Search Article: stoc26main-p171-p
	Varadarajan, Narmada	STOC '26: "Reconstruction of Depth-3 ..." Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-In Shubhangi Saraf, Devansh Shringi, and Narmada Varadarajan (University of Toronto, Canada) Article Search Article: stoc26main-p954-p
	Vasconcelos, Francisca	STOC '26: "Improved Lower Bounds for ..." Improved Lower Bounds for QAC0 Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, and John Wright (University of California at Berkeley, USA) Article Search Article: stoc26main-p1703-p
	Vasilyan, Arsen	STOC '26: "A Fully Polynomial-Time Algorithm ..." A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube Gautam Chandrasekaran, Adam R. Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan (University of Texas at Austin, USA) Article Search Article: stoc26main-p1095-p
	Végh, László A.	STOC '26: "Trust Region Interior Point ..." Trust Region Interior Point Methods: Optimal L2- and Faster Wide-Neighborhood Path Following Daniel Dadush, Haoyuan Ma, Bento Natura, and László A. Végh (CWI, Netherlands; University of Bonn, Germany; Columbia University, USA) Article Search Article: stoc26main-p331-p
	Velegkas, Grigoris	STOC '26: "On the Learning Curves of ..." On the Learning Curves of Revenue Maximization Steve Hanneke, Alkis Kalavasis, Shay Moran, and Grigoris Velegkas (Purdue University, USA; Yale University, USA; Technion, Israel; Google Research, USA) Article Search Article: stoc26main-p38-p
	Vempala, Santosh S.	STOC '26: "Provable Long-Range Benefits ..." Provable Long-Range Benefits of Next-Token Prediction Xinyuan Cao and Santosh S. Vempala (Georgia Institute of Technology, USA) Article Search Article: stoc26main-p1520-p
	Verdugo, Victor	STOC '26: "On the Informativeness of ..." On the Informativeness of Moments in Optimal Stopping José Correa, Andrés Cristi, Vasilis Livanos, Victor Verdugo, and Jiechen Zhang (Universidad de Chile, Chile; EPFL, Switzerland; Center for Mathematical Modeling, Chile; Pontificia Universidad Católica de Chile, Chile) Article Search Article: stoc26main-p342-p
	Vigoda, Eric	STOC '26: "Mixing of General Biased Adjacent ..." Mixing of General Biased Adjacent Transposition Chains Reza Gheissari, Holden Lee, and Eric Vigoda (Northwestern University, USA; Johns Hopkins University, USA; University of California at Santa Barbara, USA) Article Search Article: stoc26main-p565-p
	Vuong, Thuy-Duong	STOC '26: "Parallel Sampling via Autospeculation ..." Parallel Sampling via Autospeculation Nima Anari, Carlo Baronio, CJ Chen, Alireza Haqi, Frederic Koehler, Anqi Li, and Thuy-Duong Vuong (Stanford University, USA; University of Arizona, USA; University of Chicago, USA; University of California at San Diego, USA) Article Search Article: stoc26main-p524-p
	Wadhwa, Chirag	STOC '26: "Instance-Optimal Quantum State ..." Instance-Optimal Quantum State Certification with Entangled Measurements Ryan O'Donnell and Chirag Wadhwa (Carnegie Mellon University, USA; University of Edinburgh, UK) Article Search Article: stoc26main-p187-p
	Waggoner, Bo	STOC '26: "Combinatorial Markov Search ..." Combinatorial Markov Search Robin Bowers, Elias Lindgren, and Bo Waggoner (University of Colorado Boulder, USA) Article Search Article: stoc26main-p2089-p
	Waingarten, Erik	STOC '26: "Near-Optimal Directed Euclidean ..." Near-Optimal Directed Euclidean Spanners in High Dimensions Rajesh Jayaram, Shyamal Patel, Cliff Stein, Erik Waingarten, and Tian Zhang (Google Research, USA; Columbia University, USA; University of Pennsylvania, USA) Article Search Article: stoc26main-p703-p
	Wang, Haoze	STOC '26: "Additive One Approximation ..." Additive One Approximation for Minimum Degree Spanning Tree: Breaking the O(mn) Time Barrier Sayan Bhattacharya, Ermiya Farokhnejad, and Haoze Wang (University of Warwick, UK; Peking University, China) Article Search Article: stoc26main-p548-p
	Wang, Kangning	STOC '26: "The Price of Competitive Information ..." The Price of Competitive Information Disclosure Sid Banerjee, Kamesh Munagala, Yiheng Shen, and Kangning Wang (Cornell University, USA; Duke University, USA; Rutgers University, USA) Article Search Article: stoc26main-p601-p STOC '26: "Approximating Gains-from-Trade ..." Approximating Gains-from-Trade in Matching Markets Moshe Babaioff, Aviad Rubinstein, Xizhi Tan, and Kangning Wang (Hebrew University of Jerusalem, Israel; Stanford University, USA; Rutgers University, USA) Article Search Article: stoc26main-p305-p
	Wang, Robert	STOC '26: "Derandomizing Matrix Concentration ..." Derandomizing Matrix Concentration Inequalities from Free Probability Robert Wang, Lap Chi Lau, and Hong Zhou (University of Waterloo, Canada; Fuzhou University, China) Article Search Article: stoc26main-p209-p
	Wang, Shuo	STOC '26: "A Dichotomy Theorem for Multi-pass ..." A Dichotomy Theorem for Multi-pass Streaming CSPs Yumou Fei, Dor Minzer, and Shuo Wang (Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p111-p
	Wang, Yichuan	STOC '26: "Superquadratic Lower Bounds ..." Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits Lijie Chen, Avishay Tal, and Yichuan Wang (University of California at Berkeley, USA) Article Search Article: stoc26main-p385-p
	Watts, Adam Bene	STOC '26: "Quantum Precomputation: Parallelizing ..." Quantum Precomputation: Parallelizing Cascade Circuits and the Moore–Nilsson Conjecture Is False Adam Bene Watts, Charles R. Chen, J. William Helton, and Joseph Slote (University of Calgary, Canada; University of California at San Diego, USA; University of Washington, USA) Article Search Article: stoc26main-p487-p
	Węgrzycki, Karol	STOC '26: "Beating Meet-in-the-Middle ..." Beating Meet-in-the-Middle for Subset Balancing Problems Tim Randolph and Karol Węgrzycki (Harvey Mudd College, USA; MPI-INF, Germany) Article Search Article: stoc26main-p606-p STOC '26: "Tight (S)ETH-Based Lower Bounds ..." Tight (S)ETH-Based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-machine Scheduling Karl Bringmann, Anita Durr, and Karol Węgrzycki (Saarland University, Germany; MPI-INF, Germany) Article Search Article: stoc26main-p1518-p
	Wei, Chen-Yu	STOC '26: "Proximal Regret and Proximal ..." Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng (Yale University, USA; Massachusetts Institute of Technology, USA; University of Southern California, USA; University of Virginia, USA) Article Search Article: stoc26main-p859-p
	Wei, Fan	STOC '26: "Language Generation and Identification ..." Language Generation and Identification from Partial Enumeration: Tight Density Bounds and Topological Characterizations Jon Kleinberg and Fan Wei (Cornell University, USA; Duke University, USA) Article Search Article: stoc26main-p926-p
	Weissenberg, Guy	STOC '26: "3-Query RLDCs Are Strictly ..." 3-Query RLDCs Are Strictly Stronger Than 3-Query LDCs Tom Gur, Dor Minzer, Guy Weissenberg, and Kai Zhe Zheng (University of Cambridge, UK; Massachusetts Institute of Technology, USA; EPFL, Switzerland) Article Search Article: stoc26main-p741-p
	Wesolowski, Benjamin	STOC '26: "Average Hardness of SIVP for ..." Average Hardness of SIVP for Module Lattices of Fixed Rank Koen de Boer, Aurel Page, Radu Toma, and Benjamin Wesolowski (Unaffiliated, France; Inria - Univ. Bordeaux - CNRS - Bordeaux INP - IMB - UMR 5251, France; Sorbonne Univ. - Univ. Paris Cité - CNRS - IMJ-PRG, France; ENS de Lyon - CNRS - UMPA - UMR 5669, France) Article Search Article: stoc26main-p353-p
	White, Nathan	STOC '26: "Testing Noisy Low-Degree Polynomials ..." Testing Noisy Low-Degree Polynomials for Sparsity Yiqiao Bao, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, and Nathan White (University of Pennsylvania, USA; Massachusetts Institute of Technology, USA; Columbia University, USA) Article Search Article: stoc26main-p348-p
	Wichs, Daniel	STOC '26: "Locally Computable High Independence ..." Locally Computable High Independence Hashing Yevgeniy Dodis, Shachar Lovett, and Daniel Wichs (New York University, USA; University of California at San Diego, USA; Northeastern University, USA; NTT Research, USA) Article Search Article: stoc26main-p718-p STOC '26: "Improved Pseudorandom Codes ..." Improved Pseudorandom Codes from Permuted Puzzles Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, and Daniel Wichs (Columbia University, USA; Microsoft Research, USA; University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; Northeastern University, USA) Article Search Article: stoc26main-p1557-p
	Wiedmer, Manuel	STOC '26: "Hesse’s Redemption: Efficient ..." Hesse’s Redemption: Efficient Convex Polynomial Programming Lucas Slot, David Steurer, and Manuel Wiedmer (ETH Zurich, Switzerland) Article Search Article: stoc26main-p193-p
	Wiese, Andreas	STOC '26: "Approximation Schemes and ..." Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations Debajyoti Kar, Arindam Khan, and Andreas Wiese (IISc Bengaluru, India; TU Munich, Germany) Article Search Article: stoc26main-p522-p STOC '26: "Improved Approximation Algorithms ..." Improved Approximation Algorithms for Non-preemptive Throughput Maximization Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, and Andreas Wiese (TU Munich, Germany; IDSIA at USI-SUPSI, Switzerland) Article Search Article: stoc26main-p1425-p
	Williams, Ryan	STOC '26: "A Theory for Probabilistic ..." A Theory for Probabilistic Polynomial-Time Reasoning Lijie Chen, Jiatu Li, Igor C. Oliveira, and Ryan Williams (University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; University of Warwick, UK) Article Search Article: stoc26main-p624-p
	Willumsgaard, Sophus Valentin	STOC '26: "Ideals, Macaulay Bases, and ..." Ideals, Macaulay Bases, and PCPs Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, and Sophus Valentin Willumsgaard (Harvard University, USA; University of Copenhagen, Denmark) Article Search Article: stoc26main-p505-p
	Woodruff, David P.	STOC '26: "Combinatorial Optimization ..." Combinatorial Optimization using Comparison Oracles Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Pittu, Jon Schneider, and David P. Woodruff (Google Research, New-York, USA; Bocconi University, Italy; New York University, USA; Google Research, USA; University of Michigan, USA; Duke University, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p1341-p STOC '26: "Adversarial Robustness on ..." Adversarial Robustness on Insertion-Deletion Streams Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou (Princeton University, USA; Carnegie Mellon University, USA; Texas A&M University, USA) Article Search Article: stoc26main-p2045-p
	Wright, John	STOC '26: "The Debiased Keyl’s Algorithm: ..." The Debiased Keyl’s Algorithm: A New Unbiased Estimator for Full State Tomography Angelos Pelecanos, Jack Spilecki, and John Wright (University of California at Berkeley, USA) Article Search Article: stoc26main-p589-p STOC '26: "Improved Lower Bounds for ..." Improved Lower Bounds for QAC0 Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, and John Wright (University of California at Berkeley, USA) Article Search Article: stoc26main-p1703-p
	Wu, Beining	STOC '26: "Constructive Approximation ..." Constructive Approximation under Carleman’s Condition, with Applications to Smoothed Analysis Frederic Koehler and Beining Wu (University of Chicago, USA) Article Search Article: stoc26main-p521-p
	Wu, David X.	STOC '26: "Markov Chains Approximate ..." Markov Chains Approximate Message Passing Amit Rajaraman and David X. Wu (Massachusetts Institute of Technology, USA; University of California at Berkeley, USA) Article Search Article: stoc26main-p535-p
	Wu, Ellen	STOC '26: "The Power of Two Bases: Nearly ..." The Power of Two Bases: Nearly Robust and Copy-Optimal Certification of Nearly All Quantum States with Single-Qubit Measurements Andrea Coladangelo, Jerry Li, Joseph Slote, and Ellen Wu (University of Washington, USA; Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p999-p
	Wu, Kewen	STOC '26: "No Exponential Quantum Speedup ..." No Exponential Quantum Speedup for SIS∞ Anymore Robin Kothari, Ryan O'Donnell, and Kewen Wu (Google Quantum AI, USA; Carnegie Mellon University, USA; Institute for Advanced Study at Princeton, USA) In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case ℓ∞-Short Integer Solution (SIS∞) problem, in a parameter range outside the normal range of cryptographic interest, but still with no known efficient classical algorithm. This was particularly exciting since SIS∞ is a simple problem without structure, and their algorithmic techniques were different from those used in prior exponential quantum speedups. We present efficient classical algorithms for all of the SIS∞ and (more general) Constrained Integer Solution problems studied in their paper, showing there is no exponential quantum speedup anymore. Article Search Article: stoc26main-p52-p
	Xiang, Mars	STOC '26: "Semi-streaming Matching in ..." Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints Sepehr Assadi, Max Jiang, and Mars Xiang (University of Waterloo, Canada) Article Search Article: stoc26main-p429-p
	Xu, Chris	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Xu, Yinzhan	STOC '26: "On the Computational Hardness ..." On the Computational Hardness of Transformers Barna Saha, Yinzhan Xu, Christopher Ye, and Hantao Yu (University of California at San Diego, USA; Columbia University, USA) Article Search Article: stoc26main-p482-p
	Xue, Jie	STOC '26: "Fine-Grained Bounds for Courcelle’s ..." Fine-Grained Bounds for Courcelle’s Theorem Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi (University of California Santa Barbara, USA; University of Leeds, UK; Institute of Mathematical Sciences, India; New York University Shanghai, China; Ben-Gurion University of the Negev, Israel) Article Search Article: stoc26main-p1957-p
	Yang, Junzhao	STOC '26: "Entrywise Approximate Solutions ..." Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time Mehrdad Ghadiri, Junzhao Yang, and Angelo Farfan (Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA) Article Search Article: stoc26main-p247-p
	Yang, Mingyang	STOC '26: "Lower Bounds on Flow Sparsifiers ..." Lower Bounds on Flow Sparsifiers with Steiner Nodes Yu Chen, Zihan Tan, and Mingyang Yang (National University of Singapore, Singapore; University of Minnesota, USA) Article Search Article: stoc26main-p636-p
	Yang, Xiongxin	STOC '26: "Learning CNF Formulas from ..." Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime Weiming Feng, Xiongxin Yang, Yixiao Yu, and Yiyao Zhang (University of Hong Kong, Hong Kong; University of California at Santa Barbara, USA; Nanjing University, China) Article Search Article: stoc26main-p226-p
	Yasunaga, Kenji	STOC '26: "Hardness Amplification beyond ..." Hardness Amplification beyond Boolean Functions Nobutaka Shimizu and Kenji Yasunaga (Institute of Science Tokyo, Japan) Article Search Article: stoc26main-p590-p
	Ye, Christopher	STOC '26: "On the Computational Hardness ..." On the Computational Hardness of Transformers Barna Saha, Yinzhan Xu, Christopher Ye, and Hantao Yu (University of California at San Diego, USA; Columbia University, USA) Article Search Article: stoc26main-p482-p
	Yehudayoff, Amir	STOC '26: "Negations Are Powerful Even ..." Negations Are Powerful Even in Small Depth Bruno Cavalar, Théo Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, and Amir Yehudayoff (University of Oxford, UK; University of Copenhagen, Denmark; Chennai Mathematical Institute, India) Article Search Article: stoc26main-p1423-p STOC '26: "Better Neural Network Expressivity: ..." Better Neural Network Expressivity: Subdividing the Simplex Egor Bakaev, Florestan Brunck, Christoph Hertrich, Jack Stade, and Amir Yehudayoff (University of Copenhagen, Denmark; University of Technology Nuremberg, Germany; Technion, Israel) Article Search Article: stoc26main-p234-p
	Yu, Hantao	STOC '26: "On the Computational Hardness ..." On the Computational Hardness of Transformers Barna Saha, Yinzhan Xu, Christopher Ye, and Hantao Yu (University of California at San Diego, USA; Columbia University, USA) Article Search Article: stoc26main-p482-p
	Yu, Huacheng	STOC '26: "Adversarial Robustness on ..." Adversarial Robustness on Insertion-Deletion Streams Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou (Princeton University, USA; Carnegie Mellon University, USA; Texas A&M University, USA) Article Search Article: stoc26main-p2045-p
	Yu, Nengkun	STOC '26: "Approximation Does Not Help ..." Approximation Does Not Help in Quantum Unitary Time-Reversal Kean Chen, Nengkun Yu, and Zhicheng Zhang (University of Pennsylvania, USA; Stony Brook University, USA; University of Technology Sydney, Australia) Article Search Article: stoc26main-p656-p
	Yu, Tao	STOC '26: "A Unified Framework for Analysis ..." A Unified Framework for Analysis of Randomized Greedy Matching Algorithms Mahsa Derakhshan and Tao Yu (Northeastern University, USA) Article Search Article: stoc26main-p1274-p
	Yu, Yixiao	STOC '26: "Zero-Free Regions and Concentration ..." Zero-Free Regions and Concentration Inequalities for Hypergraph Colorings in the Local Lemma Regime Jingcheng Liu and Yixiao Yu (Nanjing University, China) Article Search Article: stoc26main-p435-p STOC '26: "Learning CNF Formulas from ..." Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime Weiming Feng, Xiongxin Yang, Yixiao Yu, and Yiyao Zhang (University of Hong Kong, Hong Kong; University of California at Santa Barbara, USA; Nanjing University, China) Article Search Article: stoc26main-p226-p
	Yuan, Weiqiang	STOC '26: "Pseudodeterministic Communication ..." Pseudodeterministic Communication Complexity Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, and Weiqiang Yuan (EPFL, Switzerland; University of British Columbia, Canada; Université de Montréal, Canada) Article Search Article: stoc26main-p1390-p
	Yuen, Henry	STOC '26: "Magic and Communication Complexity ..." Magic and Communication Complexity Uma Girish, Alex May, Natalie Parham, and Henry Yuen (Columbia University, USA; Perimeter Institute for Theoretical Physics, Canada) Article Search Article: stoc26main-p364-p
	Yuen, Jason	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Zampetakis, Manolis	STOC '26: "Learning Mixture Models via ..." Learning Mixture Models via Efficient High-Dimensional Sparse Fourier Transforms Alkis Kalavasis, Pravesh K. Kothari, Shuchen Li, and Manolis Zampetakis (Yale University, USA; Princeton University, USA) Article Search Article: stoc26main-p1321-p STOC '26: "Smoothed Analysis of Learning ..." Smoothed Analysis of Learning from Positive Samples Jane Lee, Anay Mehrotra, and Manolis Zampetakis (Yale University, USA) Article Search Article: stoc26main-p25-p
	Zehavi, Meirav	STOC '26: "Fine-Grained Bounds for Courcelle’s ..." Fine-Grained Bounds for Courcelle’s Theorem Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi (University of California Santa Barbara, USA; University of Leeds, UK; Institute of Mathematical Sciences, India; New York University Shanghai, China; Ben-Gurion University of the Negev, Israel) Article Search Article: stoc26main-p1957-p
	Zenklusen, Rico	STOC '26: "Toward Optimal Approximations ..." Toward Optimal Approximations for Resource-Minimization for Fire Containment on Trees and Non-uniform k-Center Jannis Blauth, Christian Nöbel, and Rico Zenklusen (ETH Zurich, Switzerland) Article Search Article: stoc26main-p1150-p
	Zhandry, Mark	STOC '26: "On the Cryptographic Foundations ..." On the Cryptographic Foundations of Interactive Quantum Advantage Kabir Tomer and Mark Zhandry (University of Illinois at Urbana-Champaign, USA; Stanford University, USA; NTT Research, USA) Article Search Article: stoc26main-p217-p STOC '26: "Separating QMA from QCMA with ..." Separating QMA from QCMA with a Classical Oracle John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, and Mark Zhandry (Columbia University, USA; Saarland University, Germany; University of Washington, USA; NTT Research, USA; Stanford University, USA) Article Search Article: stoc26main-p275-p
	Zhang, Jiechen	STOC '26: "On the Informativeness of ..." On the Informativeness of Moments in Optimal Stopping José Correa, Andrés Cristi, Vasilis Livanos, Victor Verdugo, and Jiechen Zhang (Universidad de Chile, Chile; EPFL, Switzerland; Center for Mathematical Modeling, Chile; Pontificia Universidad Católica de Chile, Chile) Article Search Article: stoc26main-p342-p
	Zhang, Junkai	STOC '26: "Shortcutting for Negative-Weight ..." Shortcutting for Negative-Weight Shortest Paths George Z. Li, Jason Li, Satish Rao, and Junkai Zhang (Carnegie Mellon University, USA; University of California at Berkeley, USA; Tsinghua University, China) Article Search Article: stoc26main-p125-p
	Zhang, Matthew (Shunshi)	STOC '26: "Shifted Composition IV: Toward ..." Shifted Composition IV: Toward Ballistic Acceleration for Log-Concave Sampling Jason M. Altschuler, Sinho Chewi, and Matthew (Shunshi) Zhang (University of Pennsylvania, USA; Yale University, USA; University of Toronto, Canada) Article Search Article: stoc26main-p984-p
	Zhang, Qian	STOC '26: "Sample Complexity of Agnostic ..." Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, and Qian Zhang (Tel Aviv University, Israel; Google Research, Israel; Purdue University, USA; Technion, Israel) Article Search Article: stoc26main-p308-p
	Zhang, Ruilong	STOC '26: "Nash Social Welfare with Submodular ..." Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps Xiaohui Bei, Yuda Feng, Yang Hu, Shi Li, and Ruilong Zhang (Nanyang Technological University, Singapore; Nanjing University, China; Tsinghua University, China; TU Munich, Germany) Article Search Article: stoc26main-p1408-p
	Zhang, Tian	STOC '26: "Near-Optimal Directed Euclidean ..." Near-Optimal Directed Euclidean Spanners in High Dimensions Rajesh Jayaram, Shyamal Patel, Cliff Stein, Erik Waingarten, and Tian Zhang (Google Research, USA; Columbia University, USA; University of Pennsylvania, USA) Article Search Article: stoc26main-p703-p
	Zhang, Yiyao	STOC '26: "Learning CNF Formulas from ..." Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime Weiming Feng, Xiongxin Yang, Yixiao Yu, and Yiyao Zhang (University of Hong Kong, Hong Kong; University of California at Santa Barbara, USA; Nanjing University, China) Article Search Article: stoc26main-p226-p
	Zhang, Zhicheng	STOC '26: "Approximation Does Not Help ..." Approximation Does Not Help in Quantum Unitary Time-Reversal Kean Chen, Nengkun Yu, and Zhicheng Zhang (University of Pennsylvania, USA; Stony Brook University, USA; University of Technology Sydney, Australia) Article Search Article: stoc26main-p656-p
	Zhang, Zihan	STOC '26: "Combinatorial Bounds for List ..." Combinatorial Bounds for List Recovery via Discrete Brascamp-Lieb Inequalities Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang (University of California at Berkeley, USA; University of Michigan, USA; Massachusetts Institute of Technology, USA; Ohio State University, USA) Article Search Article: stoc26main-p178-p STOC '26: "From Random to Explicit via ..." From Random to Explicit via Subspace Designs with Applications to Local Properties and Matroids Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang (University of California at Berkeley, USA; University of Michigan, USA; Massachusetts Institute of Technology, USA; Ohio State University, USA) Article Search Article: stoc26main-p281-p
	Zharkov, Stepan	STOC '26: "Approximate Orthogonal Vectors ..." Approximate Orthogonal Vectors and Diameter via Regularity Lemma Alexandr Andoni, Shunhua Jiang, and Stepan Zharkov (Columbia University, USA; Hebrew University of Jerusalem, Israel) Article Search Article: stoc26main-p734-p
	Zheng, Da Wei	STOC '26: "Cutting Planarians: Planar ..." Cutting Planarians: Planar Emulators for String Graphs Hsien-Chih Chang, Jonathan Conroy, Zihan Tan, and Da Wei Zheng (Dartmouth College, USA; University of Minnesota, USA; IST Austria, Austria) Article Search Article: stoc26main-p1565-p
	Zheng, Kai Zhe	STOC '26: "3-Query RLDCs Are Strictly ..." 3-Query RLDCs Are Strictly Stronger Than 3-Query LDCs Tom Gur, Dor Minzer, Guy Weissenberg, and Kai Zhe Zheng (University of Cambridge, UK; Massachusetts Institute of Technology, USA; EPFL, Switzerland) Article Search Article: stoc26main-p741-p STOC '26: "Near Optimal Hardness of Approximating ..." Near Optimal Hardness of Approximating 𝑘-CSP Dor Minzer and Kai Zhe Zheng (Massachusetts Institute of Technology, USA) Article Search Article: stoc26main-p34-p
	Zheng, Weiqiang	STOC '26: "Proximal Regret and Proximal ..." Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng (Yale University, USA; Massachusetts Institute of Technology, USA; University of Southern California, USA; University of Virginia, USA) Article Search Article: stoc26main-p859-p STOC '26: "Fisher Meets Lindahl: A Unified ..." Fisher Meets Lindahl: A Unified Duality Framework for Market Equilibrium Yixin Tao and Weiqiang Zheng (Shanghai University of Finance and Economics, China; Yale University, USA) Article Search Article: stoc26main-p138-p
	Zhou, Hong	STOC '26: "Derandomizing Matrix Concentration ..." Derandomizing Matrix Concentration Inequalities from Free Probability Robert Wang, Lap Chi Lau, and Hong Zhou (University of Waterloo, Canada; Fuzhou University, China) Article Search Article: stoc26main-p209-p
	Zhou, Samson	STOC '26: "Adversarial Robustness on ..." Adversarial Robustness on Insertion-Deletion Streams Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou (Princeton University, USA; Carnegie Mellon University, USA; Texas A&M University, USA) Article Search Article: stoc26main-p2045-p
	Zimmermann, Théo	STOC '26: "Determination of the Fifth ..." Determination of the Fifth Busy Beaver Value The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann (bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France) Article Search Article: stoc26main-p268-p
	Zwick, Uri	STOC '26: "Improved Approximation Algorithms ..." Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes Joshua Brakensiek, Neng Huang, Aaron Potechin, and Uri Zwick (University of California at Berkeley, USA; University of Michigan, USA; University of Chicago, USA; Tel Aviv University, Israel) Article Search Article: stoc26main-p713-p