Almost Chor--Goldreich Sources and Adversarial Random Walks.

Dean Doron (Ben Gurion University); Dana Moshkovitz, Justin Oh, David Zuckerman (University of Texas at Austin)

On Regularity Lemma and Barriers in Streaming and Dynamic Matching.

Sepehr Assadi (Rutgers University); Soheil Behnezhad (Northeastern University); Sanjeev Khanna, Huan Li (University of Pennsylvania)

Almost-Optimal Sublinear Additive Spanners.

Zihan Tan (DIMACS, Rutgers University); Tianyi Zhang (Tel Aviv University)

A New Berry-Esseen Theorem for Expander Walks.

Louis Golowich (UC Berkeley)

Streaming Euclidean MST to a Constant Factor.

Xi Chen (Columbia University); Vincent Cohen-Addad, Rajesh Jayaram (Google Research); Amit Levi (University of Waterloo); Erik Waingarten (Stanford / University of Pennsylvania)

A Unified Framework for Light Spanners.

Hung Le (University of Massachusetts); Shay Solomon (Tel Aviv University)

Near-Optimal Derandomization of Medium-Width Branching Programs.

Aaron (Louie) Putterman (Harvard University); Edward Pyne (MIT)

Optimal Eigenvalue Approximation via Sketching.

William Swartworth (University of California Los Angeles); David P. Woodruff (Carnegie Mellon University)

New algorithms for all pairs approximate shortest paths.

Liam Roditty (Bar Ilan University)

Extractors for Images of Varieties.

Zeyu Guo (Ohio State University); Ben Lee Volk (Reichman University); Akhil Jalan, David Zuckerman (University of Texas at Austin)

Streaming Euclidean Max-Cut: Dimension vs Data Reduction.

Xiaoyu Chen, Shaofeng H.-C. Jiang (Peking University); Robert Krauthgamer (Weizmann Institute of Science)

Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances.

Vaclav Rozhon (ETH Zurich); Bernhard Haeupler (ETHZ & Carnegie Mellon University); Anders Martinsson, Christoph Grunau, Goran Zuzic (ETH Zurich)

When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems.

Lijie Chen (Miller Institute for Basic Research in Science, UC Berkeley); Roei Tell (The Institute for Advanced Study at Princeton NJ and the DIMACS Center at Rutgers University)

(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond.

Sepehr Assadi, Janani Sundaresan (Rutgers University)

A New Approach to Learning Linear Dynamical Systems.

Morris Yau, Ainesh Bakshi, Allen Liu (MIT); Ankur Moitra (Math & CSAIL, MIT)

Hardness Self-Amplification: Simplified, Optimized, and Unified.

Shuichi Hirahara (National Institute of Informatics); Nobutaka Shimizu (Tokyo Institute of Technology)

Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification.

Arun Jambulapati (University of Washington); Yang P. Liu, Aaron Sidford (Stanford University).

Joint talk with

Spectral hypergraph sparsification via chaining.

James R. Lee (University of Washington)

Planning and Learning in Partially Observable Systems via Filter Stability.

Noah Golowich (MIT); Ankur Moitra (Math & CSAIL, MIT); Dhruv Rohatgi (MIT)

Sum-of-Squares Lower Bounds for Densest k-Subgraph.

Chris Jones (Bocconi University); Aaron Potechin (University of Chicago); Goutham Rajendran, Jeff Xu (Carnegie Mellon University)

Locally consistent decomposition of strings with applications to edit distance sketching.

Sudatta Bhattacharya, Michal Koucký (Charles University)

Optimistic MLE---A Generic Model-based Algorithm for Partially Observable Sequential Decision Making.

Qinghua Liu (Princeton University); Praneeth Netrapalli (Google Research India); Csaba Szepesv ́ari (DeepMind and University of Alberta); Chi Jin (Princeton University)

Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees.

Elchanan Mossel (MIT); Allan Sly (Princeton); Youngtak Sohn (MIT)

Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $\tilde{O}(n \sqrt{d})$ Monotonicity Tester.

Hadley Black (UC Los Angeles); Deeparnab Chakrabarty (Dartmouth); C. Seshadhri (UC Santa Cruz)

Weighted Edit Distance Computation: Strings, Trees, and Dyck.

Debarati Das (Pennsylvania State University); Jacob Gilbert, MohammadTaghi Hajiaghayi (University of Maryland); Tomasz Kociumaka (Max Planck Institute for Informatics); Barna Saha (University of California San Diego)

Parallel Discrete Sampling via Continuous Walks.

Nima Anari (Stanford University); Yizhi Huang (Tsinghua University); Tianyu Liu, Thuy-Duong Vuong, Brian Xu, Katherine Yu (Stanford University)

Stochastic Minimum Vertex Cover in General Graphs: a 3/2-Approximation.

Mahsa Derakhshan (Northeastern University); Naveen Durvasula, Nika Haghtalab (University of California, Berkeley)

Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics.

Amir Abboud (Weizmann Institute of Science); Karl Bringmann, Nick Fischer (Saarland University and Max-Planck-Institute for Informatics).

Joint talk with

Removing Additive Structure in 3SUM-Based Reductions.

Ce Jin, Yinzhan Xu (MIT)

Sampling from convex sets with a cold start using multiscale decompositions.

Hariharan Narayanan (TIFR, Mumbai); Amit Rajaraman (Indian Institute of Technology Bombay); Piyush Srivastava (TIFR, Mumbai)

Sublinear Algorithms for (1.5+ϵ)-Approximate Matching.

Sayan Bhattacharya, Peter Kiss (University of Warwick); Thatchaphol Saranurak (University of Michigan).

Joint talk with

Sublinear Time Algorithms and Complexity of Approximate Maximum Matching.

Soheil Behnezhad (Northeastern University); Mohammad Roghani, Aviad Rubinstein (Stanford University)

Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More.

Timothy M. Chan (UIUC); Virginia Vassilevska Williams (Massachusetts Institute of Technology); Yinzhan Xu (MIT)

Taking on the World's Challenges: The Role of Computing Research and Innovation.
Margaret Martonosi (US National Science Foundation)

Reflecting on 50 Years of Computing Research, and Future Outlook.
Hagit Attiya (Technion); Jack Dongarra (University of Tennessee at Knoxville); Mary Hall (University of Utah); Lizy Kurian John (University of Texas at Austin); Huan Liu (Arizona State University); Guy L. Steele Jr. (Oracle Labs)

Faster Isomorphism for p-Groups of Class 2 and Exponent p.

Xiaorui Sun (University of Illinois at Chicago)

Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization.

Edith Cohen (Google Research and Tel Aviv University); Xin Lyu (UC Berkeley); Jelani Nelson (UC Berkeley and Google Research); Tamás Sarlós (Google Research); Uri Stemmer (Tel Aviv University and Google Research)

An Improved Parameterized Algorithm for Treewidth.

Tuukka Korhonen (University of Bergen, Norway); Daniel Lokshtanov (University of California Santa Barbara, USA)

Linear Independence, Alternants and Applications.

Vishwas Bhargava (University of Waterloo); Shubhangi Saraf (University of Toronto); Ilya Volkovich (Boston College)

Privately Estimating a Gaussian: Efficient, Robust and Optimal.

Daniel Alabi (Columbia University); Pravesh K Kothari (Carnegie Mellon University); Pranay Tankala, Prayaag Venkat (Harvard University); Fred Zhang (UC Berkeley).

Joint talk with

Robustness Implies Privacy in Statistical Estimation.

Sam Hopkins (Massachusetts Institute of Technology); Gautam Kamath, Mahbod Majid (University of Waterloo); Shyam Narayanan (Massachusetts Institute of Technology)

The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree.

Marco Bressan (University of Milan); Matthias Lanzinger, Marc Roth (University of Oxford)

Faster Walsh-Hadamard and Discrete Fourier Transforms From Matrix Non-Rigidity.

Josh Alman, Kevin Rao (Columbia University)

Concurrent Composition Theorems for Differential Privacy.

Salil Vadhan, Wanrong Zhang (Harvard University)

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓp​ Norms.

Huck Bennett (Oregon State University); Mahdi Cheraghchi (University of Michigan); Venkatesan Guruswami (UC Berkeley); João Ribeiro (New University of Lisbon)

A Borsuk-Ulam lower bound for sign-rank and its applications.

Hamed Hatami (McGill University); Kaave Hosseini (University of Rochester); Xiang Meng (McGill University)

Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization.

Mark Bun, Marco Gaboardi (Boston University); Max Hopkins, Russell Impagliazzo, Rex Lei (University of California, San Diego); Toniann Pitassi (Columbia University); Satchit Sivakumar (Boston University); Jessica Sorrell (University of Pennsylvania)

First-Order Model Checking on Structurally Sparse Graph Classes.

Jan Dreier (TU Wien); Nikolas Mählmann, Sebastian Siebertz (University of Bremen)

The Randomized k-Server Conjecture is False!.
Sebastien Bubeck (Microsoft Research); Christian Coester (University of Oxford); Yuval Rabani (Hebrew University)

Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE.
Wei-Kai Lin, Ethan Mook (Northeastern); Daniel Wichs (Northeastern & NTT Research)

SDPs and Robust Satisfiability of Promise CSP.

Joshua Brakensiek (Stanford); Venkatesan Guruswami, Sai Sandeep (UC Berkeley)

A proof of the Nisan-Ronen conjecture.

George Christodoulou (Aristotle University of Thessaloniki); Elias Koutsoupias (University of Oxford); Annamaria Kovacs (Goethe University, Frankfurt M.)

Improved and Deterministic Online Service with Deadlines or Delay.

Noam Touitou (Amazon)

Approximate Graph Colouring and the Hollow Shadow.

Lorenzo Ciardo, Stanislav Zivny (University of Oxford)

A Constant Factor Prophet Inequality for Online Combinatorial Auctions.

Jose Correa, Andres Cristi (Universidad de Chile)

Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse.

Ravishankar Krishnaswamy (Microsoft Research India); Shi Li (University at Buffalo); Varun Suriyanarayana (Cornell University)

On Approximability of Satisfiable k-CSPs: II.

Amey Bhangale (UC Riverside); Subhash Khot (NYU); Dor Minzer (MIT)

Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules.

Binghui Peng, Xi Chen (Columbia University)

Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme.

Hu Fu (Shanghai University of Finance and Economics); Jiawei Li (University of Texas at Austin); Daogao Liu (University of Washington).

Joint talk with

Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS.

Hedyeh Beyhaghi (Carnegie Mellon University); Linda Cai (Princeton University)

On Approximability of Satisfiable k-CSPs: III.

Amey Bhangale (UC Riverside); Subhash Khot (NYU); Dor Minzer (MIT)

Computing better approximate pure Nash equilibria in cut games via semidefinite programming.

Ioannis Caragiannis, Zhile Jiang (Aarhus University)

Local and global expansion in random geometric graphs.

Siqi Liu, Sidhanth Mohanty (UC Berkeley); Tselil Schramm (Stanford); Elizabeth Yang (UC Berkeley)

An Analogue of Bonami's Lemma for Functions on Spaces of Linear Maps, and 2-2 Games.

Guy Kindler (The Hebrew University of Jerusalem); David Ellis (Bristol University); Noam Lifshitz (Hebrew University of Jerusalem)

Credible Decentralized Exchange Design via Verifiable Sequencing Rules.

Matheus Venturyne Xavier Ferreira, David C. Parkes (Harvard University)

New High Dimensional Expanders from Covers.

Yotam Dikstein (Weizmann Institute of Science)

Noise stability on the Boolean hypercube via a renormalized Brownian motion.

Ronen Eldan (Microsoft Research); Dan Mikulincer (MIT); Prasad Raghavendra (U.C. Berkeley)

On the Optimal Fixed-Price Mechanism in Bilateral Trade.

Yang Cai, Jinzhao Wu (Yale University).

Joint talk with

Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades.

Zhengyang Liu (Beijing Institute of Technology); Zeyu Ren, Zihe Wang (Renmin University of China)

Towards the Erdős-Gallai Cycle Decomposition Conjecture.

Matija Bucic (Institute for Advanced Study and Princeton University); Richard Montgomery (University of Warwick)

Constructing and Deconstructing Trust: Employing Cryptographic Recipe in the ML Domain.
Shafi Goldwasser (Director, Simons Institute for the Theory of Computing, University of California Berkeley C. Lester Hogan Professor of Electrical Engineering and Computer Sciences, University of California Berkeley)

An Optimal "It Ain't Over Till It's Over" Theorem.

Pei Wu, Avi Wigderson (Institute for Advanced Study); Ronen Eldan (Microsoft Research)

Good Quantum LDPC Codes with Linear Time Decoders.

Irit Dinur (Weizmann); Min-Hsiu Hsieh (Hon Hai Quantum Computing Research Centre); Ting-Chun Lin (UC San Diego, Hon Hai Research Institute); Thomas Vidick (California Institute Of Technology)

Nearly all k-SAT functions are unate.

J\'ozsef Balogh (University of Illinois at Urbana-Champaign); Dingding Dong (Harvard); Bernard Lidick\'y (Iowa State University); Nitya Mani, Yufei Zhao (Massachusetts Institute of Technology)

Randomized versus Deterministic Decision Tree Size.

Arkadev Chattopadhyay (STCS, TIFR, Mumbai); Yogesh Dahiya (IMSc, Chennai); Nikhil Mande (QuSoft and CWI, Amsterdam); Jaikumar Radhakrishnan (STCS, TIFR, Mumbai, and ICTS, Bengaluru); Swagato Sanyal (IIT Kharagpur)

An efficient decoder for a linear distance quantum LDPC code.

Shouzhen Gu, Christopher A. Pattison (California Institute of Technology); Eugene Tang (Massachusetts Institute of Technology)

Kneser graphs are Hamiltonian.

Arturo Merino (TU Berlin); Torsten Mütze, Namrata (University of Warwick)

Optimal Explicit Small-Depth Formulas for the Coin Problem.

Srikanth Srinivasan (Aarhus University); Utkarsh Tripathi (IIT Bombay)

Certified Randomness from Quantum Supremacy.

Scott Aaronson, Shih-Han Hung (UT Austin)

Random Walks on Rotating Expanders.

Gil Cohen, Gal Maor (Tel Aviv University)

Depth-d Threshold Circuits vs.Depth-(d + 1) AND-OR Trees.

Pooya Hatami (Ohio State University); William Hoza (Simons Institute for the Theory of Computing); Avishay Tal (UC Berkeley); Roei Tell (IAS & DIMACS)

A polynomial-time classical algorithm for noisy random circuit sampling.

Dorit Aharonov (Hebrew University); Xun Gao (Harvard University); Zeph Landau, Yunchao Liu, Umesh Vazirani (UC Berkeley)

Algorithmic Applications of Hypergraph and Partition Containers.

Or Zamir (Princeton University)

Subsampling Suffices for Adaptive Data Analysis.
Guy Blanc (Stanford University)

The Power of Multi-Step Vizing chains.
Aleksander Bjørn Grodt Christiansen (Technical University of Denmark, DTU)

Capturing One-Way Functions via NP-Hardness of Meta-Complexity.

Shuichi Hirahara (National Institute of Informatics)

NLTS Hamiltonians from good quantum codes.

Anurag Anshu (Harvard University); Nikolas P. Breuckmann (University College London); Chinmay Nirkhe (IBM Quantum, MIT-IBM Watson AI Lab)

A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths.

Julia Chuzhoy (Toyota Technological Institute at Chicago); Ruimin Zhang (University of Chicago)

A Duality Between One-Way Functions and Average-Case Symmetry of Information.

Shuichi Hirahara (National Institute of Informatics); Rahul Ilango (MIT); Zhenjian Lu (University of Oxford); Mikito Nanashima (Tokyo Institute of Technology); Igor C. Oliveira (University of Warwick)

Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory.

Qipeng Liu (Simons Institute); Ran Raz, Wei Zhan (Princeton University)

Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch.

Sebastian Forster, Yasamin Nazari (University of Salzburg); Maximilian Probst Gutenberg (ETH Zurich)

Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic.

Jiatu Li (Tsinghua University); Igor C. Oliveira (University of Warwick)

Quantum Depth in the Random Oracle Model.

Atul Singh ARORA (California Institute of Technology); Andrea Coladangelo (Simons Institute); Matthew Coudron (NIST/University of Maryland); Alexandru Gheorghiu (Chalmers University of Technology); Uttam Singh (Centre for Theoretical Physics, Warsaw); Hendrik Waldner (University of Maryland, College Park and Max Planck Institute for Security and Privacy)

Dynamic ((1+ϵ)lnn)-Approximation Algorithms for Minimum Set Cover and Dominating Set.

Shay Solomon, Amitai Uzrad (Tel Aviv University)

Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms.

Yeyuan Chen (Xi'an Jiaotong University); Yizhi Huang, Jiatu Li (Tsinghua University); Hanlin Ren (University of Oxford)

Multidimensional Quantum Walks.

Stacey Jeffery, Sebastian Zur (CWI & QuSoft)

Improved Dynamic Colouring of Sparse Graphs.

Aleksander Bjørn Grodt Christiansen (Technical University of Denmark, DTU); Krzysztof Nowicki (University of Copenhagen; pathway.com); Eva Rotenberg (Technical University of Denmark, DTU)

NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach.

Yizhi Huang (Tsinghua University); Rahul Ilango (Massachusetts Institute of Technology); Hanlin Ren (University of Oxford)

Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end.

Alexander Dalzell, Nicola Pancotti (Amazon Web Services (AWS) Center for Quantum Computing); Earl T. Campbell (Riverlane); Fernando G.S.L. Brandao (Caltech)

Dynamic Maxflow via Dynamic Interior Point Methods.

Jan van den Brand (Georgia Tech); Yang P. Liu, Aaron Sidford (Stanford University)

Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic.

Rahul Ilango (MIT); Jiatu Li (Tsinghua University); Ryan Williams (MIT)

Approximating binary longest common subsequence in almost-linear time.

Xiaoyu He (Princeton University); Ray Li (UC Berkeley)

Fast Algorithms via Dynamic-Oracle Matroids.

Joakim Blikstad (KTH Royal Institute of Technology); Sagnik Mukhopadhyay (University of Sheffield); Danupon Nanongkai (Max Planck Institute for Informatics & KTH); Ta-Wei Tu (Max Planck Institute for Informatics)

The Quantum Internet: Recent Advantages and Challenges.
Don Towsley (University of Massachusetts)

Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness.

Riddhi Ghosal (UCLA); Yuval Ishai (Technion); Alexis Korb (UCLA); Eyal Kushilevitz (Technion); Paul Lou, Amit Sahai (UCLA)

Approximating Nash Social Welfare by Matching and Local Search.

Jugal Garg (University of Illinois at Urbana-Champaign); Edin Husić (IDSIA, USI-SUPSI); Wenzheng Li (Stanford); László A. Végh (Department of Mathematics, London School of Economics); Jan Vondrák (Stanford)

Random graph matching at Otter's threshold via counting chandeliers.

Cheng Mao (Georgia Institute of Technology); Yihong Wu (Yale University); Jiaming Xu, Sophie Yu (Duke University)

On the consistency of circuit lower bounds for non-deterministic time.

Albert Atserias (Universitat Politècnica de Catalunya); Sam Buss (Univ. of California, San Diego); Moritz Müller (Universität Passau)

Multi-Agent Contracts.

Paul Duetting (Google Research); Tomer Ezra (Sapienza University of Rome); Michal Feldman (Tel Aviv University and Microsoft Research); Thomas Kesselheim (University of Bonn)

Uniformly Random Colourings of Sparse Graphs.

Eoin Hurley (Universität Heidelberg); François Pirot (Université Paris-Saclay)

Shellability is hard even for balls.

Pavel Paták (Department of Applied Mathematics, Charles University and Faculty of Information Technology, Czech Technical University, Prague, Czech Republic); Martin Tancer (Department of Applied Mathematics, Charles University, Prague, Czech Republic)

Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth.

Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, Ziena Zeif (Hasso Plattner Institute Potsdam)

Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic and Fast.

Bernhard Haeupler (Carnegie Mellon University and ETH Zürich); D Ellis Hershkowitz (ETH Zürich); Thatchaphol Saranurak (University of Michigan)

The complexity of counting planar graph homomorphisms of domain size 3.

Jin-Yi Cai, Ashwin Maran (University of Wisconsin-Madison)

A PTAS for Minimizing Weighted Flow Time on a Single Machine.

Alexander Armbruster (Technical University of Munich); Lars Rohwedder (Maastricht University); Andreas Wiese (Technical University of Munich)

Tight Conditional Lower Bounds for Vertex Connectivity Problems.

Zhiyi Huang (Tsinghua University); Yaowei Long, Thatchaphol Saranurak (University of Michigan); Benyu Wang (Tsinghua University)

Approximate Distance Sensitivity Oracles in Subquadratic Space.

Davide Bilò (University of L'Aquila, Italy); Shiri Chechik (Tel-Aviv University); Keerti Choudhary (Indian Institute of Technology); Sarel Cohen (The Academic College of Tel Aviv-Yaffo, Israel); Tobias Friedrich (Hasso Plattner Institute); Simon Krogmann (Hasso Plattner Institute, Germany); Martin Schirneck (University of Vienna, Austria)

The Round Complexity of Statistical MPC with Optimal Resiliency.

Benny Applebaum, Eliran Kachlon (Tel Aviv University); Arpita Patra (IISc Bangalore)

Testing distributional assumptions of learning algorithms.

Ronitt Rubinfeld, Arsen Vasilyan (MIT)

External Memory Fully Persistent Search Trees.

Gerth Stølting Brodal, Casper Moldrup Rysgaard, Rolf Svenning (Aarhus University)

Constant-Round Arguments from One-Way Functions.

Noga Amit (Weizmann Institute of Science); Guy Rothblum (Apple)

A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity.

Aravind Gollakota, Adam R. Klivans (University of Texas at Austin); Pravesh K. Kothari (CMU)

The Rate of Interactive Codes is Bounded Away from 1.

Klim Efremenko (Ben-Gurion University); Gillat Kol, Dmitry Paramonov (Princeton University); Raghuvansh R. Saxena (Microsoft Research)

Boosting Batch Arguments and RAM Delegation.

Yael Kalai (Microsoft Research and MIT); Alex Lombardi (Simons Institute and UC Berkeley); Vinod Vaikuntanathan (MIT); Daniel Wichs (Northeastern and NTT Research)

Learning Polynomial Transformations via Generalized Tensor Decompositions.

Sitan Chen (UC Berkeley); Jerry Li, Yuanzhi Li (Microsoft Research); Anru Zhang (Duke)

A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation.

Omar Alrabiah, Venkatesan Guruswami (UC Berkeley); Pravesh K. Kothari, Peter Manohar (Carnegie Mellon University)

Succinct Computational Secret Sharing.

Benny Applebaum (Tel Aviv University); Amos Beimel (Ben Gurion University); Yuval Ishai, Eyal Kushilevitz (Technion); Tianren Liu (Peking University); Vinod Vaikuntanathan (MIT)

Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials.

Alexander S. Wein (UC Davis)

Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel.

Meghal Gupta (Microsoft Research); Rachel Yun Zhang (MIT)

Obfuscation of Pseudo-Deterministic Quantum Circuits.

James Bartusek (UC Berkeley); Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa (NTT Social Informatics Laboratories)

What Makes a Good Fisherman? Linear Regression under Self-Selection Bias.

Yeshwanth Cherapanamjeri (UC Berkeley); Constantinos Daskalakis (Massachusetts Institute of Technology); Andrew Ilyas (MIT); Manolis Zampetakis (UC Berkeley)

A High Dimensional Goldreich-Levin Theorem.

Parker Newton, Silas Richelson, Chase Wilson (University of California, Riverside)

Commitments to Quantum States.

Sam Gunn, Nathan Ju (UC Berkeley); Fermi Ma (Simons Institute and UC Berkeley); Mark Zhandry (NTT Research and Princeton University)

A Characterization of List Learnability.

Moses Charikar, Chirag Pabbaraju (Stanford University)

Binary Error-Correcting Codes with Minimal Noiseless Feedback.

Meghal Gupta, Venkatesan Guruswami (UC Berkeley); Rachel Yun Zhang (MIT)

Quantum Cryptography in Algorithmica.

William Kretschmer (UT Austin); Luowen Qian (Boston University); Makrand Sinha (Simons Institute and UC Berkeley); Avishay Tal (UC Berkeley)

A Unifying Theory of Distance from Calibration.

Jarosław Błasiok (Columbia University); Parikshit Gopalan (Apple); Lunjia Hu (Stanford University); Preetum Nakkiran (Apple)

Generic Reed-Solomon codes achieve list-decoding capacity.

Joshua Brakensiek (Stanford University); Sivakanth Gopi (Microsoft Research); Visu Makam (Radix Trading Europe B. V.)

Quantum free games.

Anand Natarajan, Tina Zhang (MIT)

A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning.

Ilias Diakonikolas, Christos Tzamos (UW Madison); Daniel Kane (UCSD)

Optimal Bounds for Noisy Sorting.

Yuzhou Gu, Yinzhan Xu (MIT)

Quantum Advantage from Any Non-Local Game.

Yael Kalai (Microsoft Research and MIT); Alex Lombardi (Simons Institute and UC Berkeley); Vinod Vaikuntanathan, Lisa Yang (MIT)

Lifting uniform learners via distributional decomposition.

Guy Blanc (Stanford University); Jane Lange (MIT); Ali Malik, Li-Yang Tan (Stanford University)

Lattice Problems Beyond Polynomial Time.

Divesh Aggarwal (National University of Singapore); Huck Bennett (Oregon State University); Zvika Brakerski (Weizmann Institute of Science); Alexander Golovnev (Georgetown University); Rajendra Kumar (Weizmann Institute of Science); Zeyong Li (National University of Singapore); Spencer Peters, Noah Stephens-Davidowitz (Cornell University); Vinod Vaikuntanathan (MIT)

The Power of Unentangled Quantum Proofs with Non-negative Amplitudes.

Fernando Granha Jeronimo, Pei Wu (IAS)

Hausdorff and Gromov-Hausdorff stable subsets of the medial axis.

André Lieutier (None); Mathijs Wintraecken (IST Austria and Inria Sophia-Antipolis)

Scalable and Efficient AI: From Supercomputers to Smartphones.
Torsten Hoefler (ETH Zurich)

New Subset Selection Algorithms for Low Rank Approximation: Offline and Online.

David P. Woodruff, Taisuke Yasuda (Carnegie Mellon University)

A (1.5+epsilon)-Approximation Algorithm for Weighted Connectivity Augmentation.

Vera Traub (University of Bonn); Rico Zenklusen (ETH Zurich)

Interior Point Methods with a Gradient Oracle.

Adrian Vladu (CNRS, IRIF, Université Paris Cité)

Finding a Small Vertex Cut on Distributed Networks.

Yonggang Jiang (Max Planck Institute for Informatics and Saarland University); Sagnik Mukhopadhyay (University of Sheffield

Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues.

Lap Chi Lau, Kam Chuen Tung, Robert Wang (University of Waterloo)

The Smoothed Complexity of Policy Iteration for Markov Decision Processes.

Miranda Christ, Mihalis Yannakakis (Columbia University)

Faster Deterministic Distributed MIS and Approximate Matching.

Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich)

An improved approximation guarantee for Prize-Collecting TSP.

Jannis Blauth, Martin Nägele (University of Bonn)

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method.

Sophie Huiberts (Columbia University); Yin Tat Lee (University Washington); Xinzhi Zhang (University of Washington)

Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank.

Nikhil Bansal (University of Michigan, Ann Arbor); Haotian Jiang (University of Washington, Seattle); Raghu Meka (University of California, Los Angeles)

Better Trees for Santa Claus.

Etienne Bamas (EPFL); Lars Rohwedder (Maastricht University)

Algorithms approaching the threshold for semi-random planted clique.

Rares-Darius Buhai (ETH Zurich); Pravesh K. Kothari (CMU); David Steurer (ETH Zurich)