STOC 2023
55th Annual ACM Symposium on Theory of Computing (STOC 2023)
Powered by
Conference Publishing Consulting
55th Annual ACM Symposium on Theory of Computing (STOC 2023), June 20–23, 2023, Orlando, FL, USA

STOC 2023 – Proceedings

 Contents - Abstracts - Authors

Frontmatter

Title Page


Welcome from the Program Chair


STOC 2023 Conference Organization


Sponsors


Session 1A

Almost Chor-Goldreich Sources and Adversarial Random Walks
Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman
(Ben-Gurion University of the Negev, Israel; University of Texas at Austin, USA)


 Publisher's Version
A New Berry-Esseen Theorem for Expander Walks
Louis Golowich
(University of California at Berkeley, Berkeley, USA)


 Publisher's Version
Near-Optimal Derandomization of Medium-Width Branching Programs
Aaron (Louie) Putterman and Edward Pyne
(Harvard University, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version
Approximating Iterated Multiplication of Stochastic Matrices in Small Space
Gil Cohen, Dean Doron, Ori Sberlo, and Amnon Ta-Shma
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel)


 Publisher's Version
Extractors for Images of Varieties
Zeyu Guo, Ben Lee Volk, Akhil Jalan, and David Zuckerman
(Ohio State University, USA; Reichman University, Israel; University of Texas at Austin, USA)


 Publisher's Version
When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems
Lijie Chen and Roei Tell
(University of California at Berkeley, Berkeley, USA; Institute for Advanced Study, Princeton, USA; Rutgers University, USA)


 Publisher's Version
Hardness Self-Amplification: Simplified, Optimized, and Unified
Shuichi Hirahara and Nobutaka Shimizu
(National Institute of Informatics, Japan; Tokyo Institute of Technology, Japan)


 Publisher's Version
Sum-of-Squares Lower Bounds for Densest k-Subgraph
Chris Jones, Aaron Potechin, Goutham Rajendran, and Jeff Xu
(Bocconi University, Italy; University of Chicago, USA; Carnegie Mellon University, USA)


 Publisher's Version
Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees
Elchanan Mossel, Allan Sly, and Youngtak Sohn
(Massachusetts Institute of Technology, USA; Princeton University, USA)


 Publisher's Version
Parallel Discrete Sampling via Continuous Walks
Nima Anari, Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, and Katherine Yu
(Stanford University, USA; Tsinghua University, China)


 Publisher's Version
Sampling from Convex Sets with a Cold Start using Multiscale Decompositions
Hariharan Narayanan, Amit Rajaraman, and Piyush Srivastava
(TIFR, Mumbai, India; IIT Bombay, India)


 Publisher's Version

Session 1B

On Regularity Lemma and Barriers in Streaming and Dynamic Matching
Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, and Huan Li
(Rutgers University, USA; Northeastern University, USA; University of Pennsylvania, USA)


 Publisher's Version
Optimal Eigenvalue Approximation via Sketching
William Swartworth and David P. Woodruff
(University of California at Los Angeles, Los Angeles, USA; Carnegie Mellon University, USA)


 Publisher's Version
Streaming Euclidean MST to a Constant Factor
Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, and Erik Waingarten
(Columbia University, USA; Google Research, Switzerland; Google Research, USA; University of Waterloo, Canada; University of Pennsylvania, USA)


 Publisher's Version
Streaming Euclidean Max-Cut: Dimension vs Data Reduction
Xiaoyu Chen, Shaofeng H.-C. Jiang, and Robert Krauthgamer
(Peking University, China; Weizmann Institute of Science, Israel)


 Publisher's Version
(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond
Sepehr Assadi and Janani Sundaresan
(Rutgers University, USA)


 Publisher's Version
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification
Arun Jambulapati, Yang P. Liu, and Aaron Sidford
(University of Washington, USA; Stanford University, USA)


 Publisher's Version
Spectral Hypergraph Sparsification via Chaining
James R. Lee
(University of Washington, USA)


 Publisher's Version
Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching
Sudatta Bhattacharya and Michal Koucký
(Charles University, Prague, Czechia)


 Publisher's Version
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester
Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri
(University of California at Los Angeles, Los Angeles, USA; Dartmouth College, USA; University of California at Santa Cruz, Santa Cruz, USA)


 Publisher's Version
Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation
Mahsa Derakhshan, Naveen Durvasula, and Nika Haghtalab
(Northeastern University, USA; University of California at Berkeley, Berkeley, USA)


 Publisher's Version
Sublinear Algorithms for (1.5+𝜖)-Approximate Matching
Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak
(University of Warwick, UK; MPI-INF, Germany; University of Michigan, USA)


 Publisher's Version
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein
(Northeastern University, USA; Stanford University, USA)


 Publisher's Version

Session 1C

Almost-Optimal Sublinear Additive Spanners
Zihan Tan and Tianyi Zhang
(Rutgers University, USA; Tel Aviv University, Israel)


 Publisher's Version
A Unified Framework for Light Spanners
Hung Le and Shay Solomon
(University of Massachusetts, USA; Tel Aviv University, Israel)


 Publisher's Version
New Algorithms for All Pairs Approximate Shortest Paths
Liam Roditty
(Bar-Ilan University, Israel)


 Publisher's Version
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
Václav Rozhoň, Bernhard Haeupler, Anders Martinsson, Christoph Grunau, and Goran Zuzic
(ETH Zurich, Switzerland; Carnegie Mellon University, USA)


 Publisher's Version
A New Approach to Learning Linear Dynamical Systems
Ainesh Bakshi, Allen Liu, Ankur Moitra, and Morris Yau
(Massachusetts Institute of Technology, USA)


 Publisher's Version
Planning and Learning in Partially Observable Systems via Filter Stability
Noah Golowich, Ankur Moitra, and Dhruv Rohatgi
(Massachusetts Institute of Technology, USA)


 Publisher's Version
Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making
Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin
(Princeton University, USA; Google Research, India; DeepMind, UK; University of Alberta, Canada)


 Publisher's Version
Weighted Edit Distance Computation: Strings, Trees, and Dyck
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, and Barna Saha
(Pennsylvania State University, USA; University of Maryland, USA; MPI-INF, Germany; University of California at San Diego, San Diego, USA)


 Publisher's Version
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics
Amir Abboud, Karl Bringmann, and Nick Fischer
(Weizmann Institute of Science, Israel; Saarland University, Germany; MPI-INF, Germany)


 Publisher's Version
Removing Additive Structure in 3SUM-Based Reductions
Ce Jin and Yinzhan Xu
(Massachusetts Institute of Technology, USA)


 Publisher's Version
Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu
(University of Illinois at Urbana-Champaign, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version

Session 2A

Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝
Xiaorui Sun
(University of Illinois at Chicago, USA)


 Publisher's Version
Linear Independence, Alternants, and Applications
Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich
(University of Waterloo, Canada; University of Toronto, Canada; Boston College, USA)


 Publisher's Version
Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity
Josh Alman and Kevin Rao
(Columbia University, USA)


 Publisher's Version
A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications
Hamed Hatami, Kaave Hosseini, and Xiang Meng
(McGill University, Canada; University of Rochester, USA)


 Publisher's Version

Session 2B

Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer
(Google Research, USA; Tel Aviv University, Israel; University of California at Berkeley, Berkeley, USA; Google Research, Israel)


 Publisher's Version
Privately Estimating a Gaussian: Efficient, Robust, and Optimal
Daniel Alabi, Pravesh K. Kothari, Pranay Tankala, Prayaag Venkat, and Fred Zhang
(Columbia University, USA; Carnegie Mellon University, USA; Harvard University, USA; University of California at Berkeley, Berkeley, USA)


 Publisher's Version
Robustness Implies Privacy in Statistical Estimation
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan
(Massachusetts Institute of Technology, USA; University of Waterloo, Canada; Carnegie Mellon University, USA)


 Publisher's Version
Concurrent Composition Theorems for Differential Privacy
Salil Vadhan and Wanrong Zhang
(Harvard University, USA)


 Publisher's Version
Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell
(Boston University, USA; University of California at San Diego, San Diego, USA; Columbia University, USA; University of Pennsylvania, USA)


 Publisher's Version

Session 2C

An Improved Parameterized Algorithm for Treewidth
Tuukka Korhonen and Daniel Lokshtanov
(University of Bergen, Norway, Norway; University of California at Santa Barbara, Santa Barbara, USA)


 Publisher's Version
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
Marco Bressan, Matthias Lanzinger, and Marc Roth
(University of Milan, Italy; University of Oxford, UK)


 Publisher's Version
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms
Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, and João Ribeiro
(Oregon State University, USA; University of Michigan, USA; University of California at Berkeley, Berkeley, USA; NOVA-LINCS, Portugal; Universidade Nova de Lisboa, Portugal)


 Publisher's Version
First-Order Model Checking on Structurally Sparse Graph Classes
Jan Dreier, Nikolas Mählmann, and Sebastian Siebertz
(TU Wien, Austria; University of Bremen, Germany)


 Publisher's Version

Session 3: Best Papers

The Randomized 𝑘-Server Conjecture Is False!
Sébastien Bubeck, Christian Coester, and Yuval Rabani
(Microsoft Research, USA; University of Oxford, UK; Hebrew University of Jerusalem, Israel)


 Publisher's Version
Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
Wei-Kai Lin, Ethan Mook, and Daniel Wichs
(Northeastern University, USA; NTT Research, USA)


 Publisher's Version

Session 4A

SDPs and Robust Satisfiability of Promise CSP
Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep
(Stanford University, USA; University of California at Berkeley, Berkeley, USA)


 Publisher's Version
Approximate Graph Colouring and the Hollow Shadow
Lorenzo Ciardo and Stanislav Živný
(University of Oxford, UK)


 Publisher's Version
On Approximability of Satisfiable k-CSPs: II
Amey Bhangale, Subhash Khot, and Dor Minzer
(University of California at Riverside, Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version
On Approximability of Satisfiable k-CSPs: III
Amey Bhangale, Subhash Khot, and Dor Minzer
(University of California at Riverside, Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version
An Analogue of Bonami’s Lemma for Functions on Spaces of Linear Maps, and 2-2 Games
David Ellis, Guy Kindler, and Noam Lifshitz
(University of Bristol, UK; Hebrew University of Jerusalem, Israel)


 Publisher's Version
Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion
Ronen Eldan, Dan Mikulincer, and Prasad Raghavendra
(Microsoft Research, USA; Weizmann Institute of Science, Israel; Massachusetts Institute of Technology, USA; University of California at Berkeley, Berkeley, USA)


 Publisher's Version

Session 4B

A Proof of the Nisan-Ronen Conjecture
George Christodoulou, Elias Koutsoupias, and Annamária Kovács
(Aristotle University of Thessaloniki, Greece; RC Athena, Greece; University of Oxford, UK; Goethe University, Frankfurt am Main, Germany)


 Publisher's Version
A Constant Factor Prophet Inequality for Online Combinatorial Auctions
José Correa and Andrés Cristi
(University of Chile, Chile)


 Publisher's Version
Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules
Xi Chen and Binghui Peng
(Columbia University, USA)


 Publisher's Version
Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming
Ioannis Caragiannis and Zhile Jiang
(Aarhus University, Denmark)


 Publisher's Version
Credible Decentralized Exchange Design via Verifiable Sequencing Rules
Matheus Venturyne Xavier Ferreira and David C. Parkes
(Harvard University, USA)


 Publisher's Version
On the Optimal Fixed-Price Mechanism in Bilateral Trade
Yang Cai and Jinzhao Wu
(Yale University, USA)


 Publisher's Version
Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades
Zhengyang Liu, Zeyu Ren, and Zihe Wang
(Beijing Institute of Technology, China; Renmin University of China, China)


 Publisher's Version

Session 4C

Improved and Deterministic Online Service with Deadlines or Delay
Noam Touitou
(Amazon, Israel)


 Publisher's Version
Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse
Ravishankar Krishnaswamy, Shi Li, and Varun Suriyanarayana
(Microsoft Research, India; University at Buffalo, USA; Cornell University, USA)


 Publisher's Version
Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme
Hu Fu, Jiawei Li, and Daogao Liu
(Shanghai University of Finance and Economics, China; University of Texas at Austin, USA; University of Washington, USA)


 Publisher's Version
Pandora’s Problem with Nonobligatory Inspection: Optimal Structure and a PTAS
Hedyeh Beyhaghi and Linda Cai
(Carnegie Mellon University, USA; Princeton University, USA)


 Publisher's Version
Local and Global Expansion in Random Geometric Graphs
Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang
(University of California at Berkeley, Berkeley, USA; Stanford University, USA)


 Publisher's Version
New High Dimensional Expanders from Covers
Yotam Dikstein
(Weizmann Institute of Science, Israel)


 Publisher's Version
Towards the Erdős-Gallai Cycle Decomposition Conjecture
Matija Bucić and Richard Montgomery
(Institute for Advanced Study, Princeton, USA; Princeton University, USA; University of Warwick, UK)


 Publisher's Version

Session 5A

An Optimal “It Ain’t Over Till It’s Over” Theorem
Ronen Eldan, Avi Wigderson, and Pei Wu
(Microsoft Research, USA; Weizmann Institute of Science, Israel; Institute for Advanced Study, Princeton, USA)


 Publisher's Version
Randomized versus Deterministic Decision Tree Size
Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, and Swagato Sanyal
(TIFR, Mumbai, India; IMSc, Chennai, India; QuSoft, Netherlands; CWI, Amsterdam, Netherlands; ICTS, Bengaluru, India; IIT Kharagpur, India)


 Publisher's Version
Optimal Explicit Small-Depth Formulas for the Coin Problem
Srikanth Srinivasan and Utkarsh Tripathi
(Aarhus University, Denmark; IIT Bombay, India)


 Publisher's Version
Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees
Pooya Hatami, William M. Hoza, Avishay Tal, and Roei Tell
(Ohio State University, USA; University of California at Berkeley, Berkeley, USA; Simons Institute for the Theory of Computing, Berkeley, USA; Institute for Advanced Study, Princeton, USA; Rutgers University, USA)


 Publisher's Version

Session 5B

Good Quantum LDPC Codes with Linear Time Decoders
Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, and Thomas Vidick
(Weizmann Institute of Science, Israel; Hon Hai Research Institute, Taiwan; University of California at San Diego, San Diego, USA; California Institute of Technology, USA)


 Publisher's Version
An Efficient Decoder for a Linear Distance Quantum LDPC Code
Shouzhen Gu, Christopher A. Pattison, and Eugene Tang
(California Institute of Technology, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version
Certified Randomness from Quantum Supremacy
Scott Aaronson and Shih-Han Hung
(University of Texas at Austin, USA)


 Publisher's Version
A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani
(Hebrew University of Jerusalem, Israel; Harvard University, USA; University of California at Berkeley, Berkeley, USA)


 Publisher's Version

Session 5C

Nearly All 𝑘-SAT Functions Are Unate
József Balogh, Dingding Dong, Bernard Lidický, Nitya Mani, and Yufei Zhao
(University of Illinois at Urbana-Champaign, USA; Harvard University, USA; Iowa State University, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version
Kneser Graphs Are Hamiltonian
Arturo Merino, Torsten Mütze, and Namrata
(TU Berlin, Germany; University of Warwick, UK)


 Publisher's Version
Random Walks on Rotating Expanders
Gil Cohen and Gal Maor
(Tel Aviv University, Israel)


 Publisher's Version
Algorithmic Applications of Hypergraph and Partition Containers
Or Zamir
(Princeton University, USA)


 Publisher's Version

Session 6: Best Student Papers

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


 Publisher's Version
The Power of Multi-step Vizing Chains
Aleksander Bjørn Grodt Christiansen
(DTU, Denmark)


 Publisher's Version

Session 7A

Capturing One-Way Functions via NP-Hardness of Meta-Complexity
Shuichi Hirahara
(National Institute of Informatics, Japan)


 Publisher's Version
A Duality between One-Way Functions and Average-Case Symmetry of Information
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor C. Oliveira
(National Institute of Informatics, Japan; Massachusetts Institute of Technology, USA; University of Oxford, UK; Tokyo Institute of Technology, Japan; University of Warwick, UK)


 Publisher's Version
Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
Jiatu Li and Igor C. Oliveira
(Tsinghua University, China; University of Warwick, UK)


 Publisher's Version
Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms
Yeyuan Chen, Yizhi Huang, Jiatu Li, and Hanlin Ren
(Xi’an Jiaotong University, China; Tsinghua University, China; University of Oxford, UK)


 Publisher's Version
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
Yizhi Huang, Rahul Ilango, and Hanlin Ren
(Tsinghua University, China; Massachusetts Institute of Technology, USA; University of Oxford, UK)


 Publisher's Version
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
Rahul Ilango, Jiatu Li, and R. Ryan Williams
(Massachusetts Institute of Technology, USA; Tsinghua University, China)


 Publisher's Version

Session 7B

NLTS Hamiltonians from Good Quantum Codes
Anurag Anshu, Nikolas P. Breuckmann, and Chinmay Nirkhe
(Harvard University, USA; University of Bristol, UK; MIT-IBM Watson AI Lab, USA)


 Publisher's Version
Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory
Qipeng Liu, Ran Raz, and Wei Zhan
(Simons Institute for the Theory of Computing, Berkeley, USA; Princeton University, USA)


 Publisher's Version
Quantum Depth in the Random Oracle Model
Atul Singh Arora, Andrea Coladangelo, Matthew Coudron, Alexandru Gheorghiu, Uttam Singh, and Hendrik Waldner
(California Institute of Technology, USA; University of Washington, USA; National Institute of Standards and Technology, USA; University of Maryland, USA; Chalmers University of Technology, Sweden; ETH Zurich, Switzerland; Polish Academy of Sciences, Poland; IIIT Hyderabad, India; University of Maryland, College Park, USA; MPI-SP, Germany)


 Publisher's Version
Multidimensional Quantum Walks
Stacey Jeffery and Sebastian Zur
(CWI, Amsterdam, Netherlands; QuSoft, Netherlands)


 Publisher's Version
Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End
Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, and Fernando G.S.L. Brandão
(AWS Center for Quantum Computing, USA; California Institute of Technology, USA; Riverlane, UK; University of Sheffield, UK)


 Publisher's Version
Approximating Binary Longest Common Subsequence in Almost-Linear Time
Xiaoyu He and Ray Li
(Princeton University, USA; University of California at Berkeley, Berkeley, USA)


 Publisher's Version

Session 7C

A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths
Julia Chuzhoy and Ruimin Zhang
(Toyota Technological Institute at Chicago, USA; University of Chicago, USA)


 Publisher's Version
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
Sebastian Forster, Yasamin Nazari, and Maximilian Probst Gutenberg
(University of Salzburg, Austria; ETH Zurich, Switzerland)


 Publisher's Version
Dynamic ((1+𝜖) ln 𝑛)-Approximation Algorithms for Minimum Set Cover and Dominating Set
Shay Solomon and Amitai Uzrad
(Tel Aviv University, Israel)


 Publisher's Version
Improved Dynamic Colouring of Sparse Graphs
Aleksander Bjørn Grodt Christiansen, Krzysztof Nowicki, and Eva Rotenberg
(DTU, Denmark; University of Copenhagen, Denmark; pathway.com, Poland)


 Publisher's Version
Dynamic Maxflow via Dynamic Interior Point Methods
Jan van den Brand, Yang P. Liu, and Aaron Sidford
(Georgia Institute of Technology, USA; Stanford University, USA)


 Publisher's Version
Fast Algorithms via Dynamic-Oracle Matroids
Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, and Ta-Wei Tu
(KTH Royal Institute of Technology, Sweden; University of Sheffield, UK; MPI-INF, Germany)


 Publisher's Version

Session 8A

Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness
Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, and Amit Sahai
(University of California at Los Angeles, Los Angeles, USA; Technion, Israel)


 Publisher's Version
On the Consistency of Circuit Lower Bounds for Non-deterministic Time
Albert Atserias, Sam Buss, and Moritz Müller
(Universitat Politècnica de Catalunya, Spain; Centre de Recerca Matemàtica, Spain; University of California at San Diego, San Diego, USA; University of Passau, Germany)


 Publisher's Version
Shellability Is Hard Even for Balls
Pavel Paták and Martin Tancer
(Charles University, Prague, Czechia; Czech Technical University, Prague, Czechia)


 Publisher's Version
The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3
Jin-Yi Cai and Ashwin Maran
(University of Wisconsin-Madison, USA)


 Publisher's Version

Session 8B

Approximating Nash Social Welfare by Matching and Local Search
Jugal Garg, Edin Husić, Wenzheng Li, László A. Végh, and Jan Vondrák
(University of Illinois at Urbana-Champaign, USA; USI Lugano, Switzerland; Stanford University, USA; London School of Economics, UK)


 Publisher's Version
Multi-agent Contracts
Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim
(Google Research, Switzerland; Sapienza University of Rome, Italy; Tel Aviv University, Israel; Microsoft Research, Israel; University of Bonn, Germany)


 Publisher's Version
Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, and Ziena Zeif
(Hasso Plattner Institute, Potsdam, Germany)


 Publisher's Version
A PTAS for Minimizing Weighted Flow Time on a Single Machine
Alexander Armbruster, Lars Rohwedder, and Andreas Wiese
(TU Munich, Germany; Maastricht University, Netherlands)


 Publisher's Version

Session 8C

Random Graph Matching at Otter’s Threshold via Counting Chandeliers
Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu
(Georgia Institute of Technology, USA; Yale University, USA; Duke University, USA)


 Publisher's Version
Uniformly Random Colourings of Sparse Graphs
Eoin Hurley and François Pirot
(Unaffiliated, Heidelberg, Germany; Université Paris-Saclay, France)


 Publisher's Version
Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast
Bernhard Haeupler, D. Ellis Hershkowitz, and Thatchaphol Saranurak
(ETH Zurich, Switzerland; Carnegie Mellon University, USA; University of Michigan, USA)


 Publisher's Version
Tight Conditional Lower Bounds for Vertex Connectivity Problems
Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak, and Benyu Wang
(Tsinghua University, China; University of Michigan, USA)


 Publisher's Version

Session 9A

Approximate Distance Sensitivity Oracles in Subquadratic Space
Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, and Martin Schirneck
(University of L’Aquila, Italy; Tel Aviv University, Israel; IIT Delhi, India; Academic College of Tel Aviv-Yaffo, Israel; Hasso Plattner Institute, Potsdam, Germany; University of Vienna, Austria)


 Publisher's Version
External Memory Fully Persistent Search Trees
Gerth Stølting Brodal, Casper Moldrup Rysgaard, and Rolf Svenning
(Aarhus University, Denmark)


 Publisher's Version
The Rate of Interactive Codes Is Bounded Away from 1
Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena
(Ben-Gurion University of the Negev, Israel; Princeton University, USA; Microsoft Research, USA)


 Publisher's Version
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar
(University of California at Berkeley, Berkeley, USA; Carnegie Mellon University, USA)


 Publisher's Version
Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary Channel
Meghal Gupta and Rachel Yun Zhang
(University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version
A High Dimensional Goldreich-Levin Theorem
Parker Newton, Silas Richelson, and Chase Wilson
(University of California at Riverside, Riverside, USA; University of California at San Diego, San Diego, USA)


 Publisher's Version
Binary Error-Correcting Codes with Minimal Noiseless Feedback
Meghal Gupta, Venkatesan Guruswami, and Rachel Yun Zhang
(University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version
Generic Reed-Solomon Codes Achieve List-Decoding Capacity
Joshua Brakensiek, Sivakanth Gopi, and Visu Makam
(Stanford University, USA; Microsoft Research, USA; Radix Trading Europe, Netherlands)


 Publisher's Version
Optimal Bounds for Noisy Sorting
Yuzhou Gu and Yinzhan Xu
(Massachusetts Institute of Technology, USA)


 Publisher's Version
Lattice Problems beyond Polynomial Time
Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Rajendra Kumar, Zeyong Li, Spencer Peters, Noah Stephens-Davidowitz, and Vinod Vaikuntanathan
(National University of Singapore, Singapore; Oregon State University, USA; Weizmann Institute of Science, Israel; Georgetown University, USA; Cornell University, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version

Session 9B

The Round Complexity of Statistical MPC with Optimal Resiliency
Benny Applebaum, Eliran Kachlon, and Arpita Patra
(Tel Aviv University, Israel; IISc Bangalore, India)


 Publisher's Version
Constant-Round Arguments from One-Way Functions
Noga Amit and Guy N. Rothblum
(Weizmann Institute of Science, Israel; Apple, USA)


 Publisher's Version
Boosting Batch Arguments and RAM Delegation
Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Daniel Wichs
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA; Northeastern University, USA; NTT Research, USA)


 Publisher's Version
Succinct Computational Secret Sharing
Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu, and Vinod Vaikuntanathan
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel; Technion, Israel; Peking University, China; Massachusetts Institute of Technology, USA)


 Publisher's Version
Obfuscation of Pseudo-Deterministic Quantum Circuits
James Bartusek, Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa
(University of California at Berkeley, Berkeley, USA; NTT Social Informatics Laboratories, Japan)


 Publisher's Version
Commitments to Quantum States
Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry
(University of California at Berkeley, Berkeley, USA; Simons Institute for the Theory of Computing, Berkeley, USA; NTT Research, USA)


 Publisher's Version
Quantum Cryptography in Algorithmica
William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal
(University of Texas at Austin, USA; Boston University, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA)


 Publisher's Version
Quantum Free Games
Anand Natarajan and Tina Zhang
(Massachusetts Institute of Technology, USA)


 Publisher's Version
Quantum Advantage from Any Non-local Game
Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA)


 Publisher's Version
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
Fernando Granha Jeronimo and Pei Wu
(Institute for Advanced Study, Princeton, USA)


 Publisher's Version

Session 9C

Testing Distributional Assumptions of Learning Algorithms
Ronitt Rubinfeld and Arsen Vasilyan
(Massachusetts Institute of Technology, USA)


 Publisher's Version
A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
Aravind Gollakota, Adam R. Klivans, and Pravesh K. Kothari
(University of Texas at Austin, USA; Carnegie Mellon University, USA)


 Publisher's Version
Learning Polynomial Transformations via Generalized Tensor Decompositions
Sitan Chen, Jerry Li, Yuanzhi Li, and Anru R. Zhang
(University of California at Berkeley, Berkeley, USA; Harvard University, USA; Microsoft Research, USA; Carnegie Mellon University, USA; Duke University, USA)


 Publisher's Version
Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
Alexander S. Wein
(University of California at Davis, Davis, USA)


 Publisher's Version
What Makes a Good Fisherman? Linear Regression under Self-Selection Bias
Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Andrew Ilyas, and Manolis Zampetakis
(University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version
A Characterization of List Learnability
Moses Charikar and Chirag Pabbaraju
(Stanford University, USA)


 Publisher's Version
A Unifying Theory of Distance from Calibration
Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran
(Columbia University, USA; Apple, USA; Stanford University, USA)


 Publisher's Version
A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning
Ilias Diakonikolas, Christos Tzamos, and Daniel M. Kane
(University of Wisconsin-Madison, USA; University of Athens, Greece; University of California at San Diego, San Diego, USA)


 Publisher's Version
Lifting Uniform Learners via Distributional Decomposition
Guy Blanc, Jane Lange, Ali Malik, and Li-Yang Tan
(Stanford University, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version
Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis
André Lieutier and Mathijs Wintraecken
(No affiliation, France; Université Côte d’Azur, France; Inria, France; IST Austria, Austria)


 Publisher's Version

Session 10A

Faster Deterministic Distributed MIS and Approximate Matching
Mohsen Ghaffari and Christoph Grunau
(Massachusetts Institute of Technology, USA; ETH Zurich, Switzerland)


 Publisher's Version
Finding a Small Vertex Cut on Distributed Networks
Yonggang Jiang and Sagnik Mukhopadhyay
(MPI-INF, Germany; Saarland University, Germany; University of Sheffield, UK)


 Publisher's Version
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online
David P. Woodruff and Taisuke Yasuda
(Carnegie Mellon University, USA)


 Publisher's Version
Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank
Nikhil Bansal, Haotian Jiang, and Raghu Meka
(University of Michigan, Ann Arbor, USA; Microsoft Research, USA; University of California at Los Angeles, Los Angeles, USA)


 Publisher's Version

Session 10B

A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation
Vera Traub and Rico Zenklusen
(University of Bonn, Germany; ETH Zurich, Switzerland)


 Publisher's Version
Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues
Lap Chi Lau, Kam Chuen Tung, and Robert Wang
(University of Waterloo, Canada)


 Publisher's Version
An Improved Approximation Guarantee for Prize-Collecting TSP
Jannis Blauth and Martin Nägele
(University of Bonn, Germany)


 Publisher's Version
Better Trees for Santa Claus
Étienne Bamas and Lars Rohwedder
(EPFL, Switzerland; Maastricht University, Netherlands)


 Publisher's Version

Session 10C

Interior Point Methods with a Gradient Oracle
Adrian Vladu
(CNRS, France; IRIF, France; Université Paris Cité, France)


 Publisher's Version
The Smoothed Complexity of Policy Iteration for Markov Decision Processes
Miranda Christ and Mihalis Yannakakis
(Columbia University, USA)


 Publisher's Version
Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
Sophie Huiberts, Yin Tat Lee, and Xinzhi Zhang
(Columbia University, USA; Microsoft Research, USA; University of Washington, USA)


 Publisher's Version
Algorithms Approaching the Threshold for Semi-random Planted Clique
Rares-Darius Buhai, Pravesh K. Kothari, and David Steurer
(ETH Zurich, Switzerland; Carnegie Mellon University, USA)


 Publisher's Version

proc time: 0.95