| Accepted Paper | Authors |
| Parallel Repetition for the GHZ Game: Exponential Decay | Mark Braverman (Princeton University); Subhash Khot (NYU); Dor Minzer (MIT) |
| Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets | Zeyu Guo and Zihan Zhang (The Ohio State University) |
| Streaming Lower Bounds and Asymmetric Set-Disjointness | Shachar Lovett (UC San Diego); Jiapeng Zhang (University of Southern California) |
| Traversing combinatorial 0/1-polytopes via optimization | Arturo Merino (TU Berlin); Torsten Mutze (University of Warwick) |
| Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries | Dor Minzer and Kai Zhe Zheng (MIT) |
| Strongly History Independent Storage Allocation: New Upper and Lower bounds | William Kuszmaul (MIT) |
| Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon | Reilly Browne (Department of Computer Science, Stony Brook University); Prahlad Narasimham Kasthurirangan and Joseph S. B. Mitchell (Stony Brook University); Valentin Polishchuk (Linköping University, Sweden) |
| A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs | Ran Duan and Jiayi Mao (Tsinghua University); Xinkai Shu (The University of Hong Kong); Longhui Yin (Tsinghua University) |
| Directed Acyclic Outerplanar Graphs Have Constant Stack Number | Paul Jungeblut, Laura Merker, and Torsten Ueckerdt (Karlsruhe Institute of Technology) |
| Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification | Anand Natarajan and Tina Zhang (MIT) |
| Distribution of the threshold for the symmetric perceptron | Mehtaab Sawhney and Ashwin Sah (MIT) |
| Faster high-accuracy log-concave sampling via algorithmic warm starts | Jason M. Altschuler (New York University); Sinho Chewi (Massachusetts Institute of Technology) |
| Separating MAX 2-AND, MAX DI-CUT and MAX CUT | Joshua Brakensiek (Stanford University); Neng Huang and Aaron Potechin (University of Chicago); Uri Zwick (Tel Aviv University) |
| Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications | Zongchen Chen, Kuikui Liu, and Nitya Mani (MIT); Ankur Moitra (Math & CSAIL, MIT) |
| Slicing all Edges of an $n$-cube Requires $n^{2/3}$ Hyperplanes | Ohad Klein (Hebrew University) |
| A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids | Hadley Black (University of California, Los Angeles); Deeparnab Chakrabarty (Dartmouth College); C. Seshadhri (University of California, Santa Cruz) |
| On small-depth Frege proofs for PHP | Johan Håstad (KTH Royal Institute of Technology, Stockholm) |
| Fast Numerical Multivariate Multipoint Evaluation | Sumanta Ghosh (Caltech); Prahladh Harsha (TIFR); Simao Herdade (Yahoo Research); Mrinal Kumar and Ramprasad Saptharishi (TIFR) |
| Towards derandomising Markov chain Monte Carlo | Weiming Feng and Heng Guo (University of Edinburgh); Chunyang Wang (Nanjing University); Jiaheng Wang (University of Edinburgh); Yitong Yin (Nanjing University) |
| Dynamic (1+ε)-Approximate Matching Size in Truly Sublinear Update Time | Sayan Bhattacharya and Peter Kiss (University of Warwick); Thatchaphol Saranurak (University of Michigan) |
| Parameterized Approximation Schemes for Clustering with General Norm Objectives | Fateme Abbasi, Sandip Banerjee, and Jaroslaw Byrka (University of Wrocław, Poland); Parinya Chalermsook and Ameet Gadekar (Aalto University, Espoo, Finland); Kamyar Khodamoradi (University of British Columbia); Daniel Marx (CISPA Helmholtz Center for Information Security, Saarbrucken, Germany); Roohani Sharma (Max Planck Institute for Informatics, Saarbrucken, Germany); Joachim Spoerhase (University of Sheffield, United Kingdom) |
| Sparsifying Sums of Norms | Arun Jambulapati and James R. Lee (University of Washington); Yang P. Liu and Aaron Sidford (Stanford University) |
| stateQIP = statePSPACE | Tony Metger (ETH Zurich); Henry Yuen (Columbia University) |
| Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant | Vaggos Chatziafratis (UC Santa Cruz); Konstantin Makarychev (Northwestern University) |
| Constant Approximation for Private Interdependent Valuations | Alon Eden (The Hebrew University of Jerusalem); Michal Feldman (Tel Aviv University); Kira Goldner (Boston University); Simon Mauras and Divyarthi Mohan (Tel Aviv University) |
| Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More | Xin Li (Johns Hopkins University) |
| Agnostic proper learning of monotone functions: beyond black-box correction barrier | Jane Lange and Arsen Vasilyan (MIT) |
| Quartic Samples Suffice for Fourier Interpolation | Zhao Song (Adobe Research); Baocheng Sun (Weizmann Institute of Science); Omri Weinstein (The Hebrew University and Columbia University.); Ruizhe Zhang (The University of Texas at Austin) |
| All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time | Amir Abboud (Weizmann Institute of Science); Jason Li (UC Berkeley); Debmalya Panigrahi (Duke University); Thatchaphol Saranurak (University of Michigan) |
| Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries | Tianxiao Li and Jingxun Liang (IIIS, Tsinghua University); Huacheng Yu (Princeton University); Renfei Zhou (IIIS, Tsinghua University) |
| Thin trees for laminar families | Nathan Klein (University of Washington); Neil Olver (London School of Economics and Political Science) |
| Extracting Randomness from Samplable Distributions, Revisited | Marshall Ball (NYU); Dana Dachman-Soled (University of Maryland, College Park); Eli Goldin (NYU); Saachi Mutreja (University Of California, Berkeley) |
| From Grassmannian to Simplicial High-Dimensional Expanders | Louis Golowich (UC Berkeley) |
| Super-Logarithmic Lower Bounds for Dynamic Graph Problems | Kasper Green Larsen (Aarhus University); Huacheng Yu (Princeton University) |
| Certified Hardness vs. Randomness for Log-Space | Edward Pyne (MIT); Ran Raz and Wei Zhan (Princeton) |
| A deterministic near-linear time approximation scheme for geometric transportation | Emily Fox and Jiashuai Lu (The University of Texas at Dallas) |
| Lipschitz Continuous Algorithms for Graph Problems | Soh Kumabe (The University of Tokyo); Yuichi Yoshida (National Institute of Informatics) |
| The Vector Balancing Constant for Zonotopes | Rainie Bozzai, Victor Reis, and Thomas Rothvoss (University of Washington) |
| The Complexity of Dynamic Least-Squares Regression | Shunhua Jiang, Binghui Peng, and Omri Weinstein (Columbia University) |
| The Subspace Flatness Conjecture and Faster Integer Programming | Victor Reis and Thomas Rothvoss (University of Washington) |
| Improved Hardness of Approximating k-Clique under ETH | Bingkai Lin (Nanjing University); Xuandi Ren (University of California, Berkeley); Yican Sun (Peking University); Xiuhan Wang (Tsinghua University) |
| Explicit orthogonal and unitary designs | Ryan O'Donnell (Carnegie Mellon University); Rocco A. Servedio (Columbia University); Pedro Paredes (Princeton University) |
| Canonical decompositions of 3-connected graphs | Johannes Carmesin and Jan Kurkofka (University of Birmingham) |
| Uniqueness and Rapid Mixing in the Bipartite Hardcore Model | Xiaoyu Chen, Jingcheng Liu, and Yitong Yin (Nanjing University) |
| HDX Condensers | Itay Cohen, Roy Roth, and Amnon Ta-Shma (Tel Aviv University) |
| Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold | Venkatesan Guruswami (UC Berkeley); Jun-Ting Hsieh, Pravesh K. Kothari, and Peter Manohar (Carnegie Mellon University) |
| Chasing Positive Bodies | Sayan Bhattacharya (University of Warwick); Niv Buchbinder and Roie Levin (Tel Aviv University); Thatchaphol Saranurak (University of Michigan) |
| Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1 | Vincent Cohen-Addad (Google Research, France); Hung Le (University of Massachusetts); Marcin Pilipczuk (University of Warsaw and IT University of Copenhagen); Michał Pilipczuk (University of Warsaw) |
| Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering | Vincent Cohen-Addad (Google Research, France); Euiwoong Lee (University of Michigan); Shi Li (University at Buffalo); Alantha Newman (Université Grenoble Alpes) |
| Approximating Edit Distance in the Fully Dynamic Model | Tomasz Kociumaka (Max Planck Institute for Informatics); Anish Mukherjee (University of Warwick); Barna Saha (University of California San Diego) |
| Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques | Jan van den Brand and Daniel Zhang (Georgia Institute of Technology) |
| Generalizations of Matrix Multiplication can solve the Light Bulb Problem | Josh Alman and Hengjie Zhang (Columbia University) |
| Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity | Nick Gravin (Shanghai University of Finance and Economics); Enze Sun (The University of Hong Kong); Zhihao Gavin Tang (Shanghai University of Finance and Economics) |
| Near Optimal Memory-Regret Tradeoff for Online Learning | Binghui Peng (Columbia University); Aviad Rubinstein (Stanford University) |
| Bridge Girth: A Unifying Notion in Network Design | Greg Bodwin and Gary Hoppenworth (University of Michigan); Ohad Trabelsi (Toyota Technological Institute at Chicago) |
| Polynomial-Time Pseudodeterministic Construction of Primes | Lijie Chen (UC Berkeley); Zhenjian Lu (University of Oxford); Igor C. Oliveira (University of Warwick); Hanlin Ren and Rahul Santhanam (University of Oxford) |
| On Symmetric Factorizations of Hankel Matrices | Mehrdad Ghadiri (Georgia Institute of Technology) |
| Locally Uniform Hashing | Ioana-Oriana Bercea (IT University of Copenhagen); Lorenzo Beretta, Jonas Klausen, Jakob Bæk Tejs Houen, and Mikkel Thorup (University of Copenhagen) |
| Query-optimal estimation of unitary channels in diamond distance | Jeongwan Haah (Microsoft Research); Robin Kothari (Google); Ryan O'Donnell (Carnegie Mellon University); Ewin Tang (University of Washington) |
| Planar Disjoint Paths, Treewidth, and Kernels | Michal Wlodarczyk and Meirav Zehavi (Ben-Gurion University) |
| A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow | Maximilian Probst Gutenberg (ETH Zürich); Jan van den Brand and Li Chen (Georgia Institute of Technology); Rasmus Kyng (ETH Zurich); Yang P. Liu (Stanford University); Richard Peng (University of Waterloo); Sushant Sachdeva (University of Toronto); Aaron Sidford (Stanford University) |
| Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation | Vincent Cohen-Addad (Google Research, France); David Saulpic (IST Austria); Chris Schwiegelshohn (Aarhus University) |
| Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond | Nathaniel Johnston (Mount Allison University); Benjamin Lovitz (Northeastern University); Aravindan Vijayaraghavan (Northwestern University) |
| Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming | Praneeth Kacham (Carnegie Mellon University); Rasmus Pagh and Mikkel Thorup (University of Copenhagen); David P. Woodruff (Carnegie Mellon University) |
| Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms! | Divesh Aggarwal (National University of Singapore); Rajendra Kumar (Weizmann Institute of Science) |
| Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster! | Alejandro Cassis and Karl Bringmann (Saarland University and Max-Planck-Institute for Informatics); Nick Fischer (Weizmann Institute of Science) |
| Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements | Martin Grohe (RWTH Aachen University); Moritz Lichter (TU Darmstadt); Daniel Neuen (University of Bremen); Pascal Schweitzer (TU Darmstadt) |
| The minimal canonical form of a tensor network | Arturo Acuaviva (unaffiliated); Visu Makam (Radix trading); Harold Nieuwboer (University of Amsterdam); David Pérez-García (Universidad Complutense de Madrid); Friedrich Sittner (unaffiliated); Michael Walter (Ruhr-Universität Bochum); Freek Witteveen (University of Copenhagen) |
| Krylov Methods are (nearly) Optimal for Low-Rank Approximation | Ainesh Bakshi and Shyam Narayanan (Massachusetts Institute of Technology) |
| Query lower bounds for log-concave sampling | Sinho Chewi (MIT); Jaume de Dios Pont (University of California, Los Angeles); Jerry Li (Microsoft Research); Chen Lu (MIT); Shyam Narayanan (Massachusetts Institute of Technology) |
| One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree | Costas Busch (Augusta University); Da Qi Chen (University of Virginia); Arnold Filtser (Bar-Ilan University); Daniel Hathcock (Carnegie Mellon University); D Ellis Hershkowitz (ETH Zurich); Rajmohan Rajaraman (Northeastern University) |
| Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n) | Michael Elkin and Idan Shabat (Ben-Gurion University) |
| Sub-quadratic $(1+\eps)$-approximate Euclidean Spanner, with Applications | Hengjie Zhang and Alexandr Andoni (Columbia University) |
| A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels | Emmanuel Abbe and Colin Sandon (EPFL) |
| Properly Learning Decision Trees with Queries is NP-Hard | Caleb Koch, Carmen Strassle, and Li-Yang Tan (Stanford University) |
| Streaming Euclidean $k$-median and $k$-means with $o(\log n)$ Space | Vincent Cohen-Addad (Google Research, France); David P. Woodruff (Carnegie Mellon University); Samson Zhou (UC Berkeley and Rice University) |
| Testing Graph Properties with the Container Method | Eric Blais and Cameron Seth (University of Waterloo) |
| Interior-point methods on manifolds: theory and applications | Hiroshi Hirai (Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, Japan); Harold Nieuwboer (Korteweg-de Vries Institute for Mathematics and QuSoft, University of Amsterdam, The Netherlands and Faculty of Computer Science, Ruhr University Bochum, Germany); Michael Walter (Faculty of Computer Science, Ruhr University Bochum, Germany) |
| Fourier Growth of Communication Protocols for XOR Functions | Uma Girish (Princeton University); Makrand Sinha (Simons Institute and UC Berkeley); Avishay Tal and Kewen Wu (University of California Berkeley) |
| Optimal Algorithms for Bounded Weighted Edit Distance | Alejandro Cassis (Saarland University, Saarland Informatics Campus, Max Planck Institute for Informatics); Tomasz Kociumaka and Philip Wellnitz (Max Planck Institute for Informatics; Saarland Informatics Campus) |
| On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs | Suprovat Ghoshal (Northwestern University, TTIC); Euiwoong Lee (University of Michigan) |
| Envy-Free Cake-Cutting for Four Agents | Alexandros Hollender (EPFL); Aviad Rubinstein (Stanford University) |
| New Lower Bounds for Adaptive Tolerant Junta Testing | Xi Chen and Shyamal Patel (Columbia University) |
| Optimal mixing of the down-up walk on independent sets of a given size | Vishesh Jain and Marcus Michelen (University of Illinois Chicago); Huy Tuan Pham and Thuy-Duong Vuong (Stanford University) |
| A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers | Guy Blanc, Caleb Koch, Carmen Strassle, and Li-Yang Tan (Stanford University) |
| Top-Down Lower Bounds for Depth-Four Circuits | Mika Göös, Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov (EPFL) |
| ReSQueing Parallel and Private Stochastic Convex Optimization | Yair Carmon (Tel Aviv University); Arun Jambulapati (University of Washington); Yujia Jin (Stanford University); Yin Tat Lee (Microsoft Research); Daogao Liu (University of Washington); Aaron Sidford (Stanford University); Kevin Tian (Microsoft Research) |
| Matrix Completion in Almost-Verification Time | Jonathan Kelner (MIT); Jerry Li (Microsoft Research); Allen Liu (MIT); Aaron Sidford (Stanford University); Kevin Tian (Microsoft Research) |
| Dynamic ``Succincter'' | Tianxiao Li and Jingxun Liang (IIIS, Tsinghua University); Huacheng Yu (Princeton University); Renfei Zhou (IIIS, Tsinghua University) |
| Dynamic treewidth | Tuukka Korhonen (University of Bergen); Konrad Majewski, Wojciech Nadara, Michał Pilipczuk, and Marek Sokołowski (University of Warsaw) |
| The Bit Complexity of Efficient Continuous Optimization | Mehrdad Ghadiri (Georgia Institute of Technology); Richard Peng (University of Waterloo); Santosh Vempala (Georgia Institute of Technology) |
| Faster Matrix Multiplication via Asymmetric Hashing | Ran Duan (IIIS, Tsinghua University); Hongxun Wu (University of California at Berkeley); Renfei Zhou (IIIS, Tsinghua University) |
| Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization | 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, NJ); Ryan Williams (MIT) |
| Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier | Greg Bodwin and Gary Hoppenworth (University of Michigan) |
| The Price of Explainability for Clustering | Anupam Gupta and Madhusudhan Pittu (Carnegie Mellon University); Ola Svensson (EPFL); Rachel Yuan (Carnegie Mellon University) |
| Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space | Dominik Kempa (Stony Brook University); Tomasz Kociumaka (Max Planck Institute for Informatics) |
| Deterministic Fully Dynamic SSSP and More | Jan van den Brand (Georgia Institute of Technology); Adam Karczmarz (University of Warsaw and IDEAS NCBR) |
| Faster Algorithms for Text-to-Pattern Hamming Distances | Timothy M. Chan (UIUC); Ce Jin (MIT); Virginia Vassilevska Williams (Massachusetts Institute of Technology); Yinzhan Xu (MIT) |
| Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error | He Jia (Georgia Tech); Pravesh Kothari (CMU); Santosh Vempala (Georgia Tech) |
| On the tractability of sampling from the Potts model at low-temperatures via Swendsen--Wang dynamics | Antonio Blanca (Pennsylvania State University); Reza Gheissari (Northwestern University) |
| Tight Time-Space Lower Bounds for Constant-Pass Learning | Xin Lyu, Avishay Tal, and Hongxun Wu (UC Berkeley); Junzhao Yang (Tsinghua Univesity) |
| Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles | Guy Bresler, Chenghao Guo, and Yury Polyanskiy (MIT) |
| Sparse Submodular Function Minimization | Andrei Graur (Stanford University); Haotian Jiang (Microsoft Research); Aaron Sidford (Stanford University) |
| Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting | Lijie Chen (University of California at Berkeley); William Hoza (University of Chicago); Xin Lyu, Avishay Tal, and Hongxun Wu (University of California at Berkeley) |
| When Does Adaptivity Help for Quantum State Learning? | Sitan Chen (UC Berkeley, Harvard); Brice Huang (MIT); Jerry Li (Microsoft Research); Allen Liu (MIT); Mark Sellke (Amazon, Harvard) |
| Learning in Pessiland via Inductive Inference | Shuichi Hirahara (National Institute of Informatics); Mikito Nanashima (Tokyo Institute of Technology) |
| Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form | Adam Karczmarz and Piotr Sankowski (University of Warsaw and IDEAS NCBR) |
| Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition | Or Meir (University of Haifa) |
| SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle | Rahul Ilango (MIT) |
| Secure Computation Meets Distributed Universal Optimality | Merav Parter (Weizmann IS) |
| The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination | Clément Canonne (University of Sydney); Samuel B Hopkins (Massachusetts Institute of Technology); Jerry Li (Microsoft Research); Allen Liu and Shyam Narayanan (Massachusetts Institute of Technology) |
| Proof of the Clustered Hadwiger Conjecture | Vida Dujmović (University of Ottawa); Louis Esperet (Laboratoire G-SCOP, Grenoble); Pat Morin (Carleton University); David Wood (Monash University) |
| Doubly-Efficient Interactive Proofs for Distribution Properties | Tal Herman (Weizmann Institute of Science); Guy N. Rothblum (Apple) |
| IOPs with Inverse Polynomial Soundness Error | Gal Arnon (Weizmann Institute); Alessandro Chiesa (EPFL); Eylon Yogev (Bar-Ilan University) |
| Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time | Neil Olver (London School of Economics and Political Science); Leon Sering and Laura Vargas Koch (ETH Zurich) |
| Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding | Ariel Kulik (CISPA); Matthias Mnich (TU Hamburg); Hadas Shachnai (Technion) |
| Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the $\Omega(\log n)$ Lightness Barrier | Cuong Than (University of Massachusetts at Amherst); Shay Solomon (Tel Aviv University); Hung Le (University of Massachusettsat Amherst) |
| Flip-width: Cops and Robber on dense graphs | Szymon Toruńczyk (University of Warsaw) |
| Stability and replicability in learning | Zachary Chase (Oxford); Shay Moran (Technion-IIT and Google Research); Amir Yehudayoff (Technion-IIT) |
| Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography | Oded Nir and Benny Applebaum (Tel Aviv University) |
| Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots | Raghuvansh Saxena (Microsoft Research); Noah Singer (Carnegie Mellon University); Santhoshini Velusamy and Madhu Sudan (Harvard University) |
| Gilbert and Varshamov Meet Johnson: List-Decoding Explicit Nearly-Optimal Binary Codes | Silas Richelson and Sourya Roy (University of California, Riverside) |
| Covering Planar Metrics (and Beyond): O(1) Trees Suffice | Hsien-Chih Chang and Jonathan Conroy (Dartmouth College); Hung Le (University of Massachusetts); Lazar Milenković and Shay Solomon (Tel Aviv University); Cuong Than (College of Information and Computer Sciences, University of Massachusetts Amherst) |
| Strong Bounds for 3-Progressions | Zander Kelley (UIUC); Raghu Meka (UCLA) |
| Singular Value Approximation and Sparsifying Random Walks on Directed Graphs | AmirMahdi Ahmadinejad (Amazon); John Peebles (Apple); Edward Pyne (MIT); Aaron Sidford (Stanford University); Salil Vadhan (Harvard University) |
| On Pseudolinear Codes for Correcting Adversarial Errors | Eric Ruzomberka and Homa Nikbakht (Princeton University); Christopher G. Brinton (Purdue University); H. Vincent Poor (Princeton University) |
| List Decoding of Tanner and Expander Amplified Codes from Distance Certificates | Fernando Granha Jeronimo (Institute for Advanced Study); Shashank Srivastava and Madhur Tulsiani (TTIC) |
| Memory-Query Tradeoffs for Randomized Convex Optimization | Xi Chen and Binghui Peng (Columbia University) |
| Optimal PAC Bounds Without Uniform Convergence | Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy (UC Berkeley) |
| Exponential quantum speedup in simulating coupled classical oscillators | Ryan Babbush (Google); Dominic Berry (Macquarie University); Robin Kothari and Rolando Somma (Google); Nathan Wiebe (University of Toronto) |
| Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting | Ofer Grossman (MIT); Meghal Gupta (UC Berkeley); Mark Sellke (Harvard) |
| Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence | Mohsen Ghaffari (MIT); Christoph Grunau and Vaclav Rozhon (ETH Zurich) |
| Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement | Marshall Ball (NYU); Yanyi Liu (Cornell University); Noam Mazor (Cornell Tech); Rafael Pass (Tel-Aviv University & Cornell Tech) |
| Graph Colouring is Hard on Average for Polynomial Calculus and Nullstellensatz | Jonas Conneryd (Lund University and University of Copenhagen); Susanna F. de Rezende (Lund University); Jakob Nordström and Shuo Pang (University of Copenhagen and Lund University); Kilian Risse (EPFL) |
| Clique is Hard on Average for Unary Sherali-Adams | Susanna de Rezende (Lund University); Aaron Potechin (University of Chicago); Kilian Risse (EPFL) |
| Hidden Permutations to the Rescue: Multi-Pass Semi-Streaming Lower Bounds for Approximate Matchings | Sepehr Assadi (Rutgers University and University of Waterloo); Janani Sundaresan (Rutgers University) |
| A New Approach to Post-Quantum Non-Malleability | Xiao Liang (NTT Research); Omkant Pandey (Stony Brook University); Takashi Yamakawa (NTT Social Informatics Laboratories) |
| ABE for Circuits with poly(λ)-sized Keys from LWE | Valerio Cini (AIT, Austria); Hoeteck Wee (NTT Research, USA) |
| Self-Improving Output-Sensitive Convex Hull Algorithm | Siu-Wing Cheng (HKUST) |
| Simultaneous Auctions are Approximately Revenue-Optimal for Subadditive Bidders | Yang Cai (Yale University); Ziyun Chen (Tsinghua University); Jinzhao Wu (Yale University) |
| Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices | Yao-Ching Hsieh, Huijia (Rachel) Lin, and Ji Luo (University of Washington) |
| Separating Computational and Statistical Differential Privacy Under Plausible Assumptions | Badih Ghazi (Google); Rahul Ilango (Massachusetts Institute of Technology); Pritish Kamath (Google Research); Ravi Kumar (Google); Pasin Manurangsi (Google Research) |
| Local Computation Algorithms for Maximum Matching: New Lower Bounds | Soheil Behnezhad (Northeastern University); Mohammad Roghani and Aviad Rubinstein (Stanford University) |