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 Article: stoc23main-p133-p doi:10.1145/3564246.3585134

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

Publisher's Version Article: stoc23main-p168-p doi:10.1145/3564246.3585141

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 Article: stoc23main-p43-p doi:10.1145/3564246.3585108

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 Article: stoc23main-p434-p doi:10.1145/3564246.3585181

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 Article: stoc23main-p45-p doi:10.1145/3564246.3585109

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 Article: stoc23main-p739-p doi:10.1145/3564246.3585215

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 Article: stoc23main-p506-p doi:10.1145/3564246.3585189

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 Article: stoc23main-p786-p doi:10.1145/3564246.3585221

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 Article: stoc23main-p247-p doi:10.1145/3564246.3585155

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 Article: stoc23main-p655-p doi:10.1145/3564246.3585207

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 Article: stoc23main-p401-p doi:10.1145/3564246.3585172

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 Article: stoc23main-p46-p doi:10.1145/3564246.3585110

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 Article: stoc23main-p9-p doi:10.1145/3564246.3585102

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 Article: stoc23main-p369-p doi:10.1145/3564246.3585168

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 Article: stoc23main-p395-p doi:10.1145/3564246.3585170

(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 Article: stoc23main-p532-p doi:10.1145/3564246.3585192

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 Article: stoc23main-p145-p doi:10.1145/3564246.3585136

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

Publisher's Version Article: stoc23main-p348-p doi:10.1145/3564246.3585165

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

Publisher's Version Article: stoc23main-p1051-p doi:10.1145/3564246.3585239

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 Article: stoc23main-p365-p doi:10.1145/3564246.3585167

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 Article: stoc23main-p911-p doi:10.1145/3564246.3585230

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 Article: stoc23main-p1412-p doi:10.1145/3564246.3585252

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 Article: stoc23main-p925-p doi:10.1145/3564246.3585231

Session 1C

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

Publisher's Version Article: stoc23main-p99-p doi:10.1145/3564246.3585125

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

Publisher's Version Article: stoc23main-p487-p doi:10.1145/3564246.3585185

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

Publisher's Version Article: stoc23main-p567-p doi:10.1145/3564246.3585197

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 Article: stoc23main-p970-p doi:10.1145/3564246.3585235

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 Article: stoc23main-p1224-p doi:10.1145/3564246.3585247

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 Article: stoc23main-p2-p doi:10.1145/3564246.3585099

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 Article: stoc23main-p311-p doi:10.1145/3564246.3585161

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 Article: stoc23main-p423-p doi:10.1145/3564246.3585178

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 Article: stoc23main-p1070-p doi:10.1145/3564246.3585240

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

Publisher's Version Article: stoc23main-p277-p doi:10.1145/3564246.3585157

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 Article: stoc23main-p1027-p doi:10.1145/3564246.3585237

Session 2A

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

Publisher's Version Article: stoc23main-p1350-p doi:10.1145/3564246.3585250

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 Article: stoc23main-p219-p doi:10.1145/3564246.3585149

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

Publisher's Version Article: stoc23main-p501-p doi:10.1145/3564246.3585188

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 Article: stoc23main-p673-p doi:10.1145/3564246.3585210

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 Article: stoc23main-p214-p doi:10.1145/3564246.3585148

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 Article: stoc23main-p546-p doi:10.1145/3564246.3585194

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 Article: stoc23main-p62-p doi:10.1145/3564246.3585115

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

Publisher's Version Article: stoc23main-p1079-p doi:10.1145/3564246.3585241

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 Article: stoc23main-p1219-p doi:10.1145/3564246.3585246

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 Article: stoc23main-p1146-p doi:10.1145/3564246.3585245

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 Article: stoc23main-p633-p doi:10.1145/3564246.3585204

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 Article: stoc23main-p737-p doi:10.1145/3564246.3585214

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 Article: stoc23main-p491-p doi:10.1145/3564246.3585186

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 Article: stoc23main-p130-p doi:10.1145/3564246.3585132

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 Article: stoc23main-p408-p doi:10.1145/3564246.3585175

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 Article: stoc23main-p431-p doi:10.1145/3564246.3585180

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

Publisher's Version Article: stoc23main-p55-p doi:10.1145/3564246.3585112

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 Article: stoc23main-p86-p doi:10.1145/3564246.3585120

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 Article: stoc23main-p90-p doi:10.1145/3564246.3585121

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 Article: stoc23main-p65-p doi:10.1145/3564246.3585116

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 Article: stoc23main-p74-p doi:10.1145/3564246.3585118

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 Article: stoc23main-p409-p doi:10.1145/3564246.3585176

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

Publisher's Version Article: stoc23main-p231-p doi:10.1145/3564246.3585151

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

Publisher's Version Article: stoc23main-p548-p doi:10.1145/3564246.3585195

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

Publisher's Version Article: stoc23main-p1016-p doi:10.1145/3564246.3585236

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

Publisher's Version Article: stoc23main-p952-p doi:10.1145/3564246.3585233

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

Publisher's Version Article: stoc23main-p399-p doi:10.1145/3564246.3585171

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 Article: stoc23main-p304-p doi:10.1145/3564246.3585160

Session 4C

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

Publisher's Version Article: stoc23main-p40-p doi:10.1145/3564246.3585107

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 Article: stoc23main-p788-p doi:10.1145/3564246.3585222

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 Article: stoc23main-p888-p doi:10.1145/3564246.3585229

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 Article: stoc23main-p763-p doi:10.1145/3564246.3585217

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 Article: stoc23main-p38-p doi:10.1145/3564246.3585106

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

Publisher's Version Article: stoc23main-p467-p doi:10.1145/3564246.3585183

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 Article: stoc23main-p767-p doi:10.1145/3564246.3585218

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 Article: stoc23main-p635-p doi:10.1145/3564246.3585205

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 Article: stoc23main-p592-p doi:10.1145/3564246.3585199

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

Publisher's Version Article: stoc23main-p1039-p doi:10.1145/3564246.3585238

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 Article: stoc23main-p758-p doi:10.1145/3564246.3585216

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 Article: stoc23main-p6-p doi:10.1145/3564246.3585101

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 Article: stoc23main-p386-p doi:10.1145/3564246.3585169

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

Publisher's Version Article: stoc23main-p191-p doi:10.1145/3564246.3585145

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 Article: stoc23main-p955-p doi:10.1145/3564246.3585234

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 Article: stoc23main-p92-p doi:10.1145/3564246.3585123

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

Publisher's Version Article: stoc23main-p149-p doi:10.1145/3564246.3585137

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

Publisher's Version Article: stoc23main-p131-p doi:10.1145/3564246.3585133

Algorithmic Applications of Hypergraph and Partition Containers
Or Zamir
(Princeton University, USA)

Publisher's Version Article: stoc23main-p339-p doi:10.1145/3564246.3585163

Session 6: Best Student Papers

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

Publisher's Version Article: stoc23main-p825-p doi:10.1145/3564246.3585226

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

Publisher's Version Article: stoc23main-p26-p doi:10.1145/3564246.3585105

Session 7A

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

Publisher's Version Article: stoc23main-p116-p doi:10.1145/3564246.3585130

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 Article: stoc23main-p150-p doi:10.1145/3564246.3585138

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 Article: stoc23main-p175-p doi:10.1145/3564246.3585144

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 Article: stoc23main-p203-p doi:10.1145/3564246.3585147

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 Article: stoc23main-p245-p doi:10.1145/3564246.3585154

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 Article: stoc23main-p498-p doi:10.1145/3564246.3585187

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 Article: stoc23main-p58-p doi:10.1145/3564246.3585114

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 Article: stoc23main-p114-p doi:10.1145/3564246.3585129

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 Article: stoc23main-p237-p doi:10.1145/3564246.3585153

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

Publisher's Version Article: stoc23main-p279-p doi:10.1145/3564246.3585158

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 Article: stoc23main-p625-p doi:10.1145/3564246.3585203

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 Article: stoc23main-p18-p doi:10.1145/3564246.3585104

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 Article: stoc23main-p550-p doi:10.1145/3564246.3585196

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 Article: stoc23main-p719-p doi:10.1145/3564246.3585213

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

Publisher's Version Article: stoc23main-p684-p doi:10.1145/3564246.3585211

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 Article: stoc23main-p52-p doi:10.1145/3564246.3585111

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 Article: stoc23main-p139-p doi:10.1145/3564246.3585135

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 Article: stoc23main-p777-p doi:10.1145/3564246.3585219

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 Article: stoc23main-p84-p doi:10.1145/3564246.3585119

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 Article: stoc23main-p1578-p doi:10.1145/3564246.3585253

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

Publisher's Version Article: stoc23main-p232-p doi:10.1145/3564246.3585152

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 Article: stoc23main-p402-p doi:10.1145/3564246.3585173

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 Article: stoc23main-p355-p doi:10.1145/3564246.3585255

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 Article: stoc23main-p542-p doi:10.1145/3564246.3585193

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 Article: stoc23main-p221-p doi:10.1145/3564246.3585150

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 Article: stoc23main-p192-p doi:10.1145/3564246.3585146

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 Article: stoc23main-p254-p doi:10.1145/3564246.3585156

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

Publisher's Version Article: stoc23main-p1084-p doi:10.1145/3564246.3585242

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 Article: stoc23main-p621-p doi:10.1145/3564246.3585202

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 Article: stoc23main-p794-p doi:10.1145/3564246.3585223

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 Article: stoc23main-p1406-p doi:10.1145/3564246.3585251

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

Publisher's Version Article: stoc23main-p162-p doi:10.1145/3564246.3585140

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 Article: stoc23main-p1332-p doi:10.1145/3564246.3585249

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 Article: stoc23main-p174-p doi:10.1145/3564246.3585143

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 Article: stoc23main-p330-p doi:10.1145/3564246.3585162

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 Article: stoc23main-p811-p doi:10.1145/3564246.3585224

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 Article: stoc23main-p103-p doi:10.1145/3564246.3585126

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 Article: stoc23main-p111-p doi:10.1145/3564246.3585128

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

Publisher's Version Article: stoc23main-p125-p doi:10.1145/3564246.3585131

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 Article: stoc23main-p829-p doi:10.1145/3564246.3585227

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 Article: stoc23main-p856-p doi:10.1145/3564246.3585228

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

Publisher's Version Article: stoc23main-p1110-p doi:10.1145/3564246.3585244

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 Article: stoc23main-p600-p doi:10.1145/3564246.3585200

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 Article: stoc23main-p106-p doi:10.1145/3564246.3585127

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 Article: stoc23main-p429-p doi:10.1145/3564246.3585179

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 Article: stoc23main-p591-p doi:10.1145/3564246.3585198

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 Article: stoc23main-p813-p doi:10.1145/3564246.3585225

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

Publisher's Version Article: stoc23main-p669-p doi:10.1145/3564246.3585208

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 Article: stoc23main-p342-p doi:10.1145/3564246.3585164

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 Article: stoc23main-p1328-p doi:10.1145/3564246.3585248

Session 9C

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

Publisher's Version Article: stoc23main-p68-p doi:10.1145/3564246.3585117

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 Article: stoc23main-p651-p doi:10.1145/3564246.3585206

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 Article: stoc23main-p671-p doi:10.1145/3564246.3585209

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

Publisher's Version Article: stoc23main-p951-p doi:10.1145/3564246.3585232

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 Article: stoc23main-p410-p doi:10.1145/3564246.3585177

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

Publisher's Version Article: stoc23main-p507-p doi:10.1145/3564246.3585190

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 Article: stoc23main-p464-p doi:10.1145/3564246.3585182

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 Article: stoc23main-p522-p doi:10.1145/3564246.3585191

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 Article: stoc23main-p687-p doi:10.1145/3564246.3585212

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 Article: stoc23main-p56-p doi:10.1145/3564246.3585113

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 Article: stoc23main-p1106-p doi:10.1145/3564246.3585243

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 Article: stoc23main-p618-p doi:10.1145/3564246.3585201

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

Publisher's Version Article: stoc23main-p3-p doi:10.1145/3564246.3585100

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 Article: stoc23main-p16-p doi:10.1145/3564246.3585103

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 Article: stoc23main-p91-p doi:10.1145/3564246.3585122

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 Article: stoc23main-p160-p doi:10.1145/3564246.3585139

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

Publisher's Version Article: stoc23main-p303-p doi:10.1145/3564246.3585159

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

Publisher's Version Article: stoc23main-p407-p doi:10.1145/3564246.3585174

Session 10C

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

Publisher's Version Article: stoc23main-p169-p doi:10.1145/3564246.3585142

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

Publisher's Version Article: stoc23main-p780-p doi:10.1145/3564246.3585220

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 Article: stoc23main-p96-p doi:10.1145/3564246.3585124

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 Article: stoc23main-p479-p doi:10.1145/3564246.3585184

proc time: 0.4