Accepted Papers

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 Barverman; 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