STOC 2023 – Proceedings

Frontmatter

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 Info

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 Info

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 Info

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 Info

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 Video

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 Info

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 Info

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 Info

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 Info

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: 46.71