**Coded trace reconstruction in a constant number of traces**

Joshua Brakensiek; Ray Li; Bruce Spang**Affiliations:** Stanford University; Stanford University; Stanford University

**Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation**

Ainesh Bakshi; Nadiia Chepurko; David P. Woodruff**Affiliations:** CMU; MIT; CMU

**Small Covers for Near-zero Sets of Polynomials and Learning Latent Variable Models**

Ilias Diakonikolas; Daniel Kane**Affiliations:** UW Madison; UCSD

*Local Proofs Approaching the Witness Length*

Noga Ron-Zewi; Ron Rothblum**Affiliations:** University of Haifa; Technion

*Towards a Proof of the Fourier Entropy Conjecture?*

Esty Kelman; Guy Kindler; Noam Lifshitz; Dor Minzer; Muli Safra**Affiliations:** Tel Aviv University; Hebrew University of Jerusalem; Hebrew University of Jerusalem; Institute for Advanced Study; Tel Aviv University

*Subexponential LPs Approximate Max-Cut*

Samuel B. Hopkins; Tselil Schramm; Luca Trevisan**Affiliations:** UC Berkeley; Stanford University; Bocconi University

*Beyond Tree Embeddings – a Deterministic Framework for Network Design with Deadlines or Delay*

Yossi Azar; Noam Touitou** Affiliations:** Tel Aviv University; Tel Aviv University

*Collaborative Top Distribution Identifications with Limited Interaction*

Nikolai Karpov; Qin Zhang; Yuan Zhou**Affiliations:** Indiana University at Bloomington; Indiana University at Bloomington; University of Illinois at Urbana-Champaign

*An Equivalence Between Private Classification and Online Prediction*

Mark Bun; Roi Livni; Shay Moran**Affiliations:** Boston University; Tel-Aviv University; Google AI Princeton

** Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving**Simon Apers; Ronald de Wolf

**Affiliations:**National Institute for Research in Digital Science and Technology (Inria); QuIC (ULB) + CWI; QuSoft, CWI and University of Amsterdam, the Netherlands

*Twin-width I: tractable FO model checking*

Idouard Bonnet; Eun Jung Kim; Stiphan Thomassi; Rimi Watrigant**Affiliations:** LIP, ENS Lyon; LAMSADE, Paris-Dauphine University; LIP, ENS Lyon; LIP, ENS Lyon

*Fully-Dynamic Submodular Cover with Bounded Recourse*

Anupam Gupta; Roie Levin**Affiliations:** Carnegie Mellon University; Carnegie Mellon University

*Towards Better Approximation of Graph Crossing Number*

Julia Chuzhoy; Sepideh Mahabadi; Zihan Tan**Affiliations:** Toyota Technological Institute at Chicago; Toyota Technological Institute at Chicago; University of Chicago

*Lazy Search Trees*

Bryce Sandlund; Sebastian Wild**Affiliations:** University of Waterloo; University of Liverpool

*Nearly Optimal Pseudorandomness From Hardness*

Dean Doron; Dana Moshkovitz; Justin Oh; David Zuckerman**Affiliations:** Stanford University; University of Texas at Austin; University of Texas at Austin; University of Texas at Austin

*Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time*

Mahdi Cheraghchi; Vasileios Nakos**Affiliations:** University of Michigan-Ann Arbor; Saarland University

*On the Existence of Algebraically Natural Proofs*

Prerona Chatterjee; Mrinal Kumar; C. Ramya; Ramprasad Saptharishi; Anamay Tengse**Affiliations:** Tata Institute of Fundamental Research, Mumbai, India; Indian Institute of Technology Bombay, Mumbai, India; Tata Institute of Fundamental Research, Mumbai, India; Tata Institute of Fundamental Research, Mumbai, India; Tata Institute of Fundamental Research, Mumbai, India

*Optimal Streaming Approximations for all Boolean Max 2-CSPs and Max k-SAT*

Chi-Ning Chou; Alexander Golovnev; Santhoshini Velusamy**Affiliations:** Harvard University; Harvard University; Harvard University

*Testing Positive Semi-Definiteness via Random Submatrices*

Ainesh Bakshi; Nadiia Chepurko; Rajesh Jayaram**Affiliations:** Carnegie Mellon University; Massachusetts Institute of Technology; Carnegie Mellon University

*On One-way Functions and Kolmogorov Complexity*

Yanyi Liu; Rafael Pass**Affiliations:** Cornell University; Cornell Tech

*Is it Easier to Prove Statements that are Guaranteed to be True?*

Rafael Pass; Muthuramakrishnan Venkitasubramaniam**Affiliations:** Cornell Tech; U. Rochester

*Scheduling with Communication Delays via LP Hierarchies and Clustering*

Sami Davies; Janardhan Kulkarni; Thomas Rothvoss; Jakub Tarnawski; Yihao Zhang**Affiliations:** University of Washington; Microsoft Research; University of Washington; Microsoft Research; University of Washington

*Deterministic Min-cut in Poly-logarithmic Max-flows*

Jason Li; Debmalya Panigrahi**Affiliations:** Carnegie Mellon University; Duke University

*Proximity gaps for Reed-Solomon Codes*

Eli Ben-Sasson; Dan Carmon; Yuval Ishai; Swastik Kopparty; Shubhangi Saraf**Affiliations:** StarkWare; StarkWare; Technion; Rutgers; Rutgers

*Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay*

Biswaroop Maiti; Rajmohan Rajaraman; David Stalfa; Zoya Svitkina; Aravindan Vijayaraghavan**Affiliations:** Northeastern University; Northeastern University; Northeastern University; Google; Northwestern University

*Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization*

Lijie Chen; Xin Lyu; R. Ryan Williams**Affiliations:** MIT; Tsinghua University; MIT

*Explicit near-fully X-Ramanujan graphs*

Ryan O’Donnell; Xinyu Wu**Affiliations:** Carnegie Mellon University; Carnegie Mellon University

*Near-linear Size Hypergraph Cut Sparsifiers*

Yu Chen; Sanjeev Khanna; Ansh Nagda**Affiliations:** University of Pennsylvania; University of Pennsylvania; University of Washington

*Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs*

Jin-Yi Cai; Artsiom Hovarau**Affiliations:** University of Wisconsin-Madison; University of Wisconsin-Madison

*AdWords in a Panorama*

Zhiyi Huang; Qiankun Zhang; Yuhao Zhang**Affiliations:** The University of Hong Kong; The University of Hong Kong; The University of Hong Kong

*Near-Optimal Decremental SSSP in Dense Weighted Digraphs*

Aaron Bernstein; Maximilian P. Gutenberg; Christian Wulff-Nilsen**Affiliations:** Rutgers University New Brunswick, Department of Computer Science; University of Copenhagen; University of Copenhagen

*Communication complexity of Nash equilibrium in potential games*

Yakov Babichenko; Aviad Rubinstein**Affiliations:** Technion, Israel institute of Technology; Stanford University

*Learning sums of powers of low-degree polynomials in the non-degenerate case*

Ankit Garg; Neeraj Kayal; Chandan Saha**Affiliations:** Microsoft Research India; Microsoft Research India; Indian Institute of Science

*Point Location and Active Learning: Learning Halfspaces Almost Optimally*

Max Hopkins; Daniel Kane; Shachar Lovett; Gaurav Mahajan**Affiliations:** University of California, San Diego; University of California, San Diego; University of California, San Diego; University of California, San Diego

*Framework for $\exists\mathbb R$-Completeness of Two-Dimensional Packing Problems*

Mikkel Abrahamsen; Tillmann Miltzow; Nadja Seiferth**Affiliations:** University of Copenhagen; Utrecht University; Freie Universitdt Berlin

*An Adaptive Step Toward the Multiphase Conjecture and Lower Bounds on Nonlinear Networks*

Young Kun Ko; Omri Weinstein**Affiliations:** New York University; Columbia University

*2D Fractional Cascading on Axis-aligned Planar Subdivisions*

Peyman Afshani; Pingan Cheng**Affiliations:** Aarhus University; Aarhus University

*Maximizing Determinants under Matroid Constraints*

Vivek Madan; Aleksandar Nikolov; Mohit Singh; Uthaipon Tantipongpipat**Affiliations:** Amazon; University of Toronto; Georgia Institute of Technology; Twitter

*Stochastic Weighted Matching: $(1-\epsilon)$ Approximation*

Soheil Behnezhad; Mahsa Derakhshan**Affiliations:** University of Maryland; University of Maryland

*Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations*

Ariel Kulik; Hadas Shachnai**Affiliations:** Technion; Technion

*Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization*

Yi-Jun Chang; Thatchaphol Saranurak**Affiliations:** ETH Zurich; Toyota Technological Institute at Chicago

*Counting Small Induced Subgraphs Satisfying Monotone Properties*

Marc Roth; Johannes Schmitt; Philip Wellnitz**Affiliations:** Merton College, University of Oxford, United Kingdom; Mathematical Institute, University of Bonn, Germany; Max Planck Institute for Informatics, Saarland Informatics Campus (SIC), Saarbr|cken, Germany

*A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond*

Julia Chuzhoy; Yu Gao; Jason Li; Danupon Nanongkai; Richard Peng; Thatchaphol Saranurak**Affiliations:** Toyota Technological Institute of Chicago; Georgia Tech; Carnegie Mellon University; KTH Royal Institute of Technology; Georgia Tech; Toyota Technological Institute of Chicago

**Optimal anytime regret with two experts**

Nicholas J. A. Harvey; Christopher Liaw; Edwin Perkins; Sikander Randhawa**Affiliations:** University of British Columbia; University of British Columbia; University of British Columbia; University of British Columbia

*Edit Distance in Near-Linear Time: it’s a Constant Factor*

Alexandr Andoni; Negev Shekel Nosatzki**Affiliations:** Columbia University; Columbia University

*High-precision Estimation of Random Walks in Small Space*

AmirMahdi Ahmadinejad; Jonathan Kelner; Jack Murtagh; John Peebles; Aaron Sidford; Salil Vadhan**Affiliations:** Stanford University; Massachusetts Institute of Technology; Harvard University; Yale University; Stanford University; Harvard University

*A Faster Interior Point Method for Semidefinite Programming*

Haotian Jiang; Tarun Kathuria; Yin Tat Lee; Swati Padmanabhan; Zhao Song**Affiliations:** University of Washington; UC Berkeley; University of Washington; University of Washington; Princeton University and Institute for Advanced Study

*Subsets and Supermajorities: Optimal Hashing-based Set Similarity Search*

Thomas D. Ahle; Jakob B. T. Knudsen**Affiliations:** BARC, IT University of Copenhagen; BARC, University of Copenhagen

*The complexity of approximating averages on bounded-degree graphs*

Andreas Galanis; Daniel Stefankovic; Eric Vigoda**Affiliations:** University of Oxford; University of Rochester; Georgia Institute of Technology

*Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms*

Sepehr Assadi; Ran Raz**Affiliations:** Rutgers University; Princeton Universitty

*Symbolic determinant identity testing (SDIT) is not a null cone problem; and the symmetries of algebraic varieties*

Visu Makam; Avi Wigderson**Affiliations:** Institute for Advanced Study; Institute for Advanced Study

*Polynomial Data Structure Lower Bounds in the Group Model*

Alexander Golovnev; Gleb Posobin; Oded Regev; Omri Weinstein**Affiliations:** Harvard University; Columbia University; New York University; Columbia University

*Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing*

Aaron Bernstein; Maximilian Probst Gutenberg; Thatchaphol Saranurak**Affiliations:** Rutgers University; University of Copenhagen; TTIC

*Distributed Lower Bounds for Ruling Sets*

Alkida Balliu; Sebastian Brandt; Dennis Olivetti**Affiliations:** University of Freiburg; ETH Zurich; University of Freiburg

*Tree-depth and the Formula Complexity of Subgraph Isomorphism*

Deepanshu Kush; Benjamin Rossman**Affiliations:** University of Toronto; Duke University

*Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs*

Kyriakos Axiotis; Aleksander Madry; Adrian Vladu**Affiliations:** MIT; MIT; Boston University

*LDPC Codes Achieve List Decoding Capacity*

Jonathan Mosheiff; Nicolas Resch; Noga Ron-Zewi; Shashwat Silas; Mary Wootters**Affiliations:** Carnegie Mellon University; Carnegie Mellon University; University of Haifa; Stanford University; Stanford University

*Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction*

Zongchen Chen; Kuikui Liu; Eric Vigoda**Affiliations:** Georgia Institute of Technology; University of Washington; Georgia Institute of Technology

*A Parameterized Approximation Scheme for Min k-Cut*

Daniel Lokshtanov; Saket Saurabh; Vaishali Surianarayanan**Affiliations:** University of California Santa Barbara, USA; The Institute of Mathematical Sciences, HBNI, Chennai, India; University of California Santa Barbara, USA

*Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise*

Noah Shutty; Mary Wootters; Patrick Hayden**Affiliations:** Stanford University; Stanford University; Stanford University

*Independent Set on P_k-Free Graphs in Quasi-Polynomial Time*

Peter Gartland; Daniel Lokshtanov**Affiliations:** University of California Santa Barbara; University of California Santa Barbara

*List Decodable Mean Estimation in Nearly Linear Time*

Yeshwanth Cherapanamjeri; Sidhanth Mohanty; Morris Yau**Affiliations:** University of California Berkeley; University of California Berkeley; University of California Berkeley

*Monochromatic Triangles, Triangle Listing and APSP*

Virginia V. Williams; Yinzhan Xu**Affiliations:** MIT; MIT

*Hypergraph k-cut for fixed k in deterministic polynomial time*

Karthekeyan Chandrasekaran; Chandra Chekuri**Affiliations:** UIUC; UIUC

*Symmetries, graph properties, and quantum speedups*

Shalev Ben-David; Andrew M. Childs; Andras Gilyin; William Kretschmer; Supartha Podder; Daochen Wang**Affiliations:** University of Waterloo; University of Maryland; California Institute of Technology; University of Texas at Austin; University of Ottawa; University of Maryland

*New Techniques for Proving Fine-Grained Average-Case Hardness*

Mina Dalirrooyfard; Andrea Lincoln; Virginia Vassilevska Williams**Affiliations:** MIT; MIT; MIT

*Algorithms and Hardness for Linear Algebra on Geometric Graphs*

Josh Alman; Timothy Chu; Aaron Schild; Zhao Song

*Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity*

Shuichi Hirahara**Affiliations:** National Institute of Informatics

*Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model*

Nima Anari; Kuikui Liu; Shayan Oveis Gharan**Affiliations:** Stanford University; University of Washington; University of Washington

*Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases*

Nima Anari; Michal Derezinski**Affiliations:** Stanford University; University of California, Berkeley

*A constant rate non-malleable code in the split-state model*

Divesh Aggarwal; Maciej Obremski**Affiliations:** National University of Singapore; National University of Singapore

*Fully Online Matching II: Beating Ranking and Water-filling*

Zhiyi Huang; Zhihao Gavin Tang; Xiaowei Wu; Yuhao Zhang**Affiliations:** The University of Hong Kong; ITCS, Shanghai University of Finance and Economics; IOTSC, University of Macau; The University of Hong Kong

*QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge*

Anne Broadbent; Alex B. Grilo**Affiliations:** University of Ottawa; CWI and QuSoft

*Adjacency Labelling for Planar Graphs (and Beyond)*

Vida Dujmovic; Louis Esperet; Cyril Gavoille; Gwenakl Joret; Piotr Micek; Pat Morin**Affiliations:** University of Ottawa; CNRS, Universiti Grenoble Alpes; University of Bordeaux; Universiti Libre de Bruxelles; Jagiellonian University; Carleton University

*Smoothing the gap between NP and ER*

Jeff Erickson; Ivor van der Hoog; Tillmann Miltzow**Affiliations:** University of Illinois; Utrecht University; Utrecht University

*Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance*

Tomasz Kociumaka; Barna Saha**Affiliations:** Bar-Ilan University; University of California, Berkeley

*Kernel Density Estimation through Density Constrained Near Neighbor Search*

Moses Charikar; Michael Kapralov; Navid Nouri; Paris Siminelakis**Affiliations: **Stanford University; EPFL; EPFL; UC Berkeley

*Resolution of the Burrows-Wheeler Transform Conjecture*

Dominik Kempa; Tomasz Kociumaka** Affiliations:** UC Berkeley; Bar-Ilan University

*The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency*

Benny Applebaum; Eliran Kachlon; Arpita Patra**Affiliations:** Tel-Aviv University, Israel; Tel-Aviv University, Israel; Indian Institute of Science, Bangalore, India

*Isomorphism Testing for Graphs Excluding Small Minors*

Martin Grohe; Daniel Neuen; Daniel Wiebking**Affiliations:** RWTH Aachen University; CISPA Helmholtz Center for Information Security; RWTH Aachen University

*Faster Approximate Pattern Matching: A Unified Approach*

Panagiotis Charalampopoulos; Tomasz Kociumaka; Philip Wellnitz**Affiliations:** Department of Informatics, Kings College London, United Kingdom; Bar-Ilan University, Ramat Gan, Israel and University of Warsaw, Poland; Max Planck Institute for Informatics, Saarland Informatics Campus (SIC), Saarbr|cken, Germany

*On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs*

Vincent Cohen-Addad; Arnold Filtser; Philip N. Klein; Hung Le**Affiliations:** Google Research; Columbia University; Brown University; University of Victoria and University of Massachusetts at Amherst

*Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity*

Susanna F. de Rezende; Or Meir; Jakob Nordstrvm; Toniann Pitassi; Robert Robere; Marc Vinyals**Affiliations:** Institute of Mathematics of the Czech Academy of Sciences; University of Haifa; University of Copenhagen and Lund University; University of Toronto and Institute for Advanced Study; DIMACS and Institute for Advanced Study; Technion

*Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders*

Shai Evra; Tali Kaufman; Gilles Zemor**Affiliations:** IAS; Bar Ilan University; Bordeaux University

*Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs*

Jan van den Brand; Yin Tat Lee; Danupon Nanongkai; Richard Peng; Thatchaphol Saranurak; Aaron Sidford; Zhao Song; Di Wang**Affiliations:** KTH Royal Institute of Technology; University of Washington and Microsoft Research Redmond; KTH Royal Institute of Technology; Georgia Institute of Technology; Toyota Technological Institute at Chicago; Stanford University; Princeton University and Institute for Advanced Study; Google Research

*Network Coding Gaps for Completion Times of Multiple Unicasts*

Bernhard Haeupler; David Wajc; Goran Zuzic**Affiliations:** CMU; CMU; CMU

*On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds*

Lijie Chen; Ron D. Rothblum; Roei Tell; Eylon Yogev**Affiliations: **Massachusetts Institute of Technology; Technion; Weizmann Institute of Science; Boston University and Tel Aviv University

*Revisiting Tardos’s Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers*

Daniel Dadush; Bento Natura; Laszlo A. Vegh**Affiliations:** CWI Amsterdam; London School of Economics and Political Science; London School of Economics and Political Science

*An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions*

Paul Duetting; Thomas Kesselheim; Brendan Lucier**Affiliations:** Google Research and London School of Economics; University of Bonn; Microsoft Research

*A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip*

Iftach Haitner; Yonatan Karidi-Heller**Affiliations:** Tel Aviv University; Tel Aviv University

*Near Optimal Linear Algebra in the Online and Sliding Window Models*

Vladimir Braverman; Petros Drineas; Cameron Musco; Christopher Musco; Jalaj Upadhyay; David P. Woodruff; Samson Zhou**Affiliations:** Johns Hopkins University; Purdue University; University of Massachusetts Amherst; New York University; Apple, Inc.; Carnegie Mellon University; Carnegie Mellon University

*Testing linear-invariant properties*

Jonathan Tidor; Yufei Zhao**Affiliations: **MIT; MIT

*Rigid Matrices from Rectangular PCPs*

Amey Bhangale; Prahladh Harsha; Orr Paradise; Avishay Tal**Affiliations:** UC Riverside; Tata Institute of Fundamental research; UC Berkeley; UC Berkeley

*Benchmark Design and Prior-independent Optimization*

Jason Hartline; Aleck Johnsen; Yingkai Li**Affiliations:** Northwestern University; Northwestern University; Northwestern University

*Correlated Pseudorandom Functions from Variable-Density LPN*

Elette Boyle; Geoffroy Couteau; Niv Gilboa; Yuval Ishai; Lisa Kohl; Peter Scholl**Affiliations: **IDC Herzliya; IRIF; Ben-Gurion University; Technion; Technion; Aarhus University

*Edge-Weighted Online Bipartite Matching*

Matthew Fahrbach; Zhiyi Huang; Runzhou Tao; Morteza Zadimoghaddam**Affiliations:** Google Research; The University of Hong Kong; Columbia University; Google Research

*Approximation Algorithms for Stochastic Minimum Norm Combinatorial Optimization*

Sharat Ibrahimpur; Chaitanya Swamy**Affiliations: **University of Waterloo; University of Waterloo

*KRW Composition Theorems via Lifting*

Susanna F. de Rezende; Or Meir; Jakob Nordstrvm; Toniann Pitassi; Robert Robere**Affiliations:** Mathematical Institute of the Czech Academy of Sciences.; University of Haifa; University of Copenhagen and Lund University; University of Toronto; DIMACS and University of Toronto and Institute for Advanced Study

*Towards Optimal Separations between Quantum and Randomized Query Complexities*

Avishay Tal**Affiliations:** UC Berkeley

*Cut-Equivalent Trees are Optimal for Min-Cut Queries*

Amir Abboud; Robert Krauthgamer; Ohad Trabelsi**Affiliations:** IBM Almaden, US; Weizmann Institute of Science, Israel; Weizmann Institute of Science, Israel

*The Constant Depth Formula and Partial Function Versions of MCSP are Hard*

Rahul Ilango**Affiliations: **MIT

*Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems*

Sepehr Assadi; Gillat Kol; Raghuvansh Saxena; Huacheng Yu**Affiliations:** Rutgers University; Princeton University; Princeton University; Princeton University

*Fast Dynamic Cuts, Distances and Effective Resistance via Vertex Sparsifier*

Li Chen; Gramoz Goranci; Monika Henzinger; Richard Peng; Thatchaphol Saranurak**Affiliations:** Georgia Institute of Technology; University of Toronto; University of Vienna; Georgia Institute of Technology; Toyota Technological Institute at Chicago

*Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$)*

Klim Efremenko; Gillat Kol; Raghuvansh R. Saxena**Affiliations:** Ben-Gurion University; Princeton University; Princeton University

*Low-Degree Hardness of Random Optimization Problems*

David Gamarnik; Aukosh Jagannath; Alexander S. Wein**Affiliations:** MIT; University of Waterloo; NYU Courant

*Unique Decoding of Explicit $\epsilon$-balanced Codes Near the Gilbert–Varshamov Bound*

Fernando Granha Jeronimo; Dylan Quintana; Shashank Srivastava; Madhur Tulsiani**Affiliations:** University of Chicago; University of Chicago; TTIC; TTIC

*Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes*

Zvika Brakerski; Yael Tauman Kalai; Raghuvansh R. Saxena**Affiliations:** Weizmann Institute; Microsoft and MIT; Princeton University

*Sample-efficient learning of quantum many-body systems*

Anurag Anshu; Srinivasan Arunachalam; Tomotaka Kuwahara; Mehdi Soleimanifar**Affiliations:** Institute for Quantum Computing and Perimeter Institute, Waterloo; IBM Research; RIKEN Center for Advanced Intelligence Project, Japan; MIT

*A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions*

Shalev Ben-David; Eric Blais**Affiliations:** University of Waterloo; University of Waterloo

*A New Minimax Theorem for Randomized Algorithms*

Shalev Ben-David; Eric Blais**Affiliations:** University of Waterloo; University of Waterloo

*Entanglement Is Necessary for Optimal Quantum Property Testing*

Sebastien Bubeck; Sitan Chen; Jerry Li**Affiliations:** MSR; MIT; MSR

*Pandoras Box with Correlations: Learning and Approximation*

Shuchi Chawla; Evangelia Gergatsouli; Yifeng Teng; Christos Tzamos; Ruimin Zhang**Affiliations:** University of Wisconsin-Madison; University of Wisconsin-Madison; University of Wisconsin-Madison; University of Wisconsin-Madison; University of Wisconsin-Madison

*The Coin Problem with Applications to Data Streams*

Mark Braverman; Sumegha Garg; David P. Woodruff**Affiliations:** Princeton University; Princeton University; Carnegie Mellon University

*Sparse PCA: algorithms, adversarial perturbations and certificates*

Tommaso d’Orsi; Pravesh K. Kothari; Gleb Novikov; David Steurer**Affiliations:** ETH Zurich; Carnegie-Mellon University; ETH Zurich; ETH Zurich

*A Dichotomy for Real Boolean Holant Problems*

Shuai Shao; Jin-Yi Cai**Affiliations:** University of Wisconsin-Madison; University of Wisconsin-Madison

*Tight Quantum Time-Space Tradeoffs for Function Inversion*

Kai-Min Chung; Siyao Guo; Qipeng Liu; Luowen Qian**Affiliations:** Academia Sinica; New York University Shanghai; Princeton University and NTT Research; Boston University

*Coordinate Methods for Matrix Games*

Yair Carmon; Yujia Jin; Aaron Sidford; Kevin Tian**Affiliations:** Stanford University; Stanford University; Stanford University; Stanford University

*Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs*

ManÄ¨inska; David E. Roberson**Affiliations:** University of Copenhagen; Technical University of Denmark

*Smoothed Complexity of 2-player Nash Equilibria*

Shant Boodaghians; Joshua Brakensiek; Samuel B. Hopkins; Aviad Rubinstein**Affiliations:** University of Illinois at Urbana-Champaign; Stanford University; University of California, Berkeley.; Stanford University

*Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes*

Mrinalkanti Ghosh; Fernando Granha Jeronimo; Chris Jones; Aaron H. Potechin; Goutham Rajendran**Affiliations:** Toyota Technological Institute at Chicago; University of Chicago; University of Chicago; University of Chicago; University of Chicago

*Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time*

Jess Banks; Jorge Garza Vargas; Archit Kulkarni; Nikhil Srivastava**Affiliations:** UC Berkeley; UC Berkeley; UC Berkeley; UC Berkeley

*Resolving the Optimal Metric Distortion Conjecture*

Vasilis Gkatzelis; Daniel Halpern; Nisarg Shah**Affiliations:** Drexel University; University of Toronto; University of Toronto

*Mechanisms for a No-Regret Agent: Beyond the Common Prior*

Modibo K Camara; Jason D Hartline; Aleck Johnsen**Affiliations:** Northwestern University; Northwestern University; Northwestern University

*An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature*

Andrew Drucker**Affiliations:** University of Chicago

*Extractors and Secret Sharing Against Bounded Collusion Protocols*

Eshan Chattopadhyay; Jesse Goodman; Vipul Goyal; Ashutosh Kumar; Xin Li; Raghu Meka; David Zuckerman

Cornell University; Cornell University; Carnegie Mellon University; UCLA; Johns Hopkins University; UCLA; UT Austin

*Unit Capacity Maxflow in Almost m^{4/3} time*

Tarun Kathuria; Yang P. Liu; Aaron Sidford

UC Berkeley; Stanford University; Stanford University

*Outlier-Robust clustering of Gaussians and other non-spherical mixtures*

Ainesh Bakshi; Ilias Diakonikolas; Sam Hopkins; Daniel Kane; Sushrut Karmalkar; Pravesh K Kothari

CMU; UW Madison; Berkeley; UCSD; UT Austin; CMU