November 6-9, 2023

Santa Cruz, CA, USA

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)