STOC 2023 Accepted Papers

• Planning and Learning in Partially Observable Systems via Filter Stability
  Noah Golowich (MIT); Ankur Moitra (Math & CSAIL, MIT); Dhruv Rohatgi (MIT)


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


• Good Quantum LDPC Codes with Linear Time Decoders
  Irit Dinur (Weizmann); Min-Hsiu Hsieh (Hon Hai Quantum Computing Research Centre); Ting-Chun Lin (UC San Diego, Hon Hai Research Institute); Thomas Vidick (California Institute Of Technology)


• Optimal Eigenvalue Approximation via Sketching
  William Swartworth (University of California Los Angeles); David P. Woodruff (Carnegie Mellon University)


• Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank
  Nikhil Bansal (University of Michigan, Ann Arbor); Haotian Jiang (University of Washington, Seattle); Raghu Meka (University of California, Los Angeles)


• Approximating binary longest common subsequence in almost-linear time
  Xiaoyu He (Princeton University); Ray Li (UC Berkeley)


• The Power of Multi-Step Vizing chains
  Aleksander Bjørn Grodt Christiansen (Technical University of Denmark, DTU)


• Local and global expansion in random geometric graphs
  Siqi Liu, Sidhanth Mohanty (UC Berkeley); Tselil Schramm (Stanford); Elizabeth Yang (UC Berkeley)


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


• Near-Optimal Derandomization of Medium-Width Branching Programs
  Aaron (Louie) Putterman (Harvard University); Edward Pyne (MIT)


• Extractors for Images of Varieties
  Zeyu Guo (Ohio State University); Ben Lee Volk (Reichman University); Akhil Jalan, David Zuckerman (University of Texas at Austin)


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


• Improved Dynamic Colouring of Sparse Graphs
  Aleksander Bjørn Grodt Christiansen (Technical University of Denmark, DTU); Krzysztof Nowicki (University of Copenhagen; pathway.com); Eva Rotenberg (Technical University of Denmark, DTU)


• Approximate Graph Colouring and the Hollow Shadow
  Lorenzo Ciardo, Stanislav Zivny (University of Oxford)


• Hausdorff and Gromov-Hausdorff stable subsets of the medial axis
  André Lieutier (None); Mathijs Wintraecken (IST Austria and Inria Sophia-Antipolis)


• NLTS Hamiltonians from good quantum codes
  Anurag Anshu (Harvard University); Nikolas P. Breuckmann (University College London); Chinmay Nirkhe (IBM Quantum, MIT-IBM Watson AI Lab)


• Robustness Implies Privacy in Statistical Estimation
  Sam Hopkins (Massachusetts Institute of Technology); Gautam Kamath, Mahbod Majid (University of Waterloo); Shyam Narayanan (Massachusetts Institute of Technology)


• AN ANALOGUE OF BONAMI’S LEMMA FOR FUNCTIONS ON SPACES OF LINEAR MAPS, AND 2-2 GAMES
  Guy Kindler (The Hebrew University of Jerusalem); David Ellis (Bristol University); Noam Lifshitz (Hebrew University of Jerusalem)


• Testing distributional assumptions of learning algorithms
  Ronitt Rubinfeld, Arsen Vasilyan (MIT)


• Noise stability on the Boolean hypercube via a renormalized Brownian motion
  Ronen Eldan (Microsoft Research); Dan Mikulincer (MIT); Prasad Raghavendra (U.C. Berkeley)


• Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness
  Riddhi Ghosal (UCLA); Yuval Ishai (Technion); Alexis Korb (UCLA); Eyal Kushilevitz (Technion); Paul Lou, Amit Sahai (UCLA)


• On Approximability of Satisfiable k-CSPs: II
  Amey Bhangale (UC Riverside); Subhash Khot (NYU); Dor Minzer (MIT)


• On Approximability of Satisfiable k-CSPs: III Linearity Testing over the Biased Cube, and More
  Amey Bhangale (UC Riverside); Subhash Khot (NYU); Dor Minzer (MIT)


• A (1.5+epsilon)-Approximation Algorithm for Weighted Connectivity Augmentation
  Vera Traub (University of Bonn); Rico Zenklusen (ETH Zurich)


• Nearly all k-SAT functions are unate
  J\'ozsef Balogh (University of Illinois at Urbana-Champaign); Dingding Dong (Harvard); Bernard Lidick\'y (Iowa State University); Nitya Mani, Yufei Zhao (Massachusetts Institute of Technology)


• Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
  Sophie Huiberts (Columbia University); Yin Tat Lee (University Washington); Xinzhi Zhang (University of Washington)


• Almost-Optimal Sublinear Additive Spanners
  Zihan Tan (DIMACS, Rutgers University); Tianyi Zhang (Tel Aviv University)


• Binary Error-Correcting Codes with Minimal Noiseless Feedback
  Meghal Gupta, Venkatesan Guruswami (UC Berkeley); Rachel Yun Zhang (MIT)


• Succinct Computational Secret Sharing
  Benny Applebaum (Tel Aviv University); Amos Beimel (Ben Gurion University); Yuval Ishai, Eyal Kushilevitz (Technion); Tianren Liu (Peking University); Vinod Vaikuntanathan (MIT)


• Generic Reed-Solomon codes achieve list-decoding capacity
  Joshua Brakensiek (Stanford University); Sivakanth Gopi (Microsoft Research); Visu Makam (Radix Trading Europe B. V.)


• Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory
  Qipeng Liu (Simons Institute); Ran Raz, Wei Zhan (Princeton University)


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


• Optimal Bounds for Noisy Sorting
  Yuzhou Gu, Yinzhan Xu (MIT)


• The Randomized k-Server Conjecture is False!
  Sebastien Bubeck (Microsoft Research); Christian Coester (University of Oxford); Yuval Rabani (Hebrew University)


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


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


• Dynamic Maxflow via Dynamic Interior Point Methods
  Jan van den Brand (Georgia Tech); Yang P. Liu, Aaron Sidford (Stanford University)


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


• Kneser graphs are Hamiltonian
  Arturo Merino (TU Berlin); Torsten Mütze, Namrata (University of Warwick)


• A Duality Between One-Way Functions and Average-Case Symmetry of Information
  Shuichi Hirahara (National Institute of Informatics); Rahul Ilango (MIT); Zhenjian Lu (University of Oxford); Mikito Nanashima (Tokyo Institute of Technology); Igor C. Oliveira (University of Warwick)


• Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues
  Lap Chi Lau, Kam Chuen Tung, Robert Wang (University of Waterloo)


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


• A New Berry-Esseen Theorem for Expander Walks
  Louis Golowich (UC Berkeley)


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


• A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
  Omar Alrabiah, Venkatesan Guruswami (UC Berkeley); Pravesh K. Kothari, Peter Manohar (Carnegie Mellon University)


• Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
  Jiatu Li (Tsinghua University); Igor C. Oliveira (University of Warwick)


• Certified Randomness from Quantum Supremacy
  Scott Aaronson, Shih-Han Hung (UT Austin)


• A PTAS for Minimizing Weighted Flow Time on a Single Machine
  Alexander Armbruster (Technical University of Munich); Lars Rohwedder (Maastricht University); Andreas Wiese (Technical University of Munich)


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


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


• Linear Independence, Alternants and Applications
  Vishwas Bhargava (University of Waterloo); Shubhangi Saraf (University of Toronto); Ilya Volkovich (Boston College)


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


• A Constant Factor Prophet Inequality for Online Combinatorial Auctions
  Jose Correa, Andres Cristi (Universidad de Chile)


• Shellability is hard even for balls
  Pavel Paták (Department of Applied Mathematics, Charles University and Faculty of Information Technology, Czech Technical University, Prague, Czech Republic); Martin Tancer (Department of Applied Mathematics, Charles University, Prague, Czech Republic)


• Quantum Depth in the Random Oracle Model
  Atul Singh ARORA (California Institute of Technology); Andrea Coladangelo (Simons Institute); Matthew Coudron (NIST/University of Maryland); Alexandru Gheorghiu (Chalmers University of Technology); Uttam Singh (Centre for Theoretical Physics, Warsaw); Hendrik Waldner (University of Maryland, College Park and Max Planck Institute for Security and Privacy)


• NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
  Yizhi Huang (Tsinghua University); Rahul Ilango (Massachusetts Institute of Technology); Hanlin Ren (University of Oxford)


• Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees
  Elchanan Mossel (MIT); Allan Sly (Princeton); Youngtak Sohn (MIT)


• Random graph matching at Otter's threshold via counting chandeliers
  Cheng Mao (Georgia Institute of Technology); Yihong Wu (Yale University); Jiaming Xu, Sophie Yu (Duke University)


• Removing Additive Structure in 3SUM-Based Reductions
  Ce Jin, Yinzhan Xu (MIT)


• Multidimensional Quantum Walks, with Application to k-Distinctness
  Stacey Jeffery, Sebastian Zur (CWI & QuSoft)


• An improved approximation guarantee for Prize-Collecting TSP
  Jannis Blauth, Martin Nägele (University of Bonn)


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


• Optimistic MLE---A Generic Model-based Algorithm for Partially Observable Sequential Decision Making
  Qinghua Liu (Princeton University); Praneeth Netrapalli (Google Research India); Csaba Szepesv ́ari (DeepMind and University of Alberta); Chi Jin (Princeton University)


• Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel
  Meghal Gupta (Microsoft Research); Rachel Yun Zhang (MIT)


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


• Quantum Advantage from Any Non-Local Game
  Yael Kalai (Microsoft Research and MIT); Alex Lombardi (Simons Institute and UC Berkeley); Vinod Vaikuntanathan, Lisa Yang (MIT)


• Spectral hypergraph sparsification via chaining
  James R. Lee (University of Washington)


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


• Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $\tilde{O}(n \sqrt{d})$ Monotonicity Tester
  Hadley Black (UC Los Angeles); Deeparnab Chakrabarty (Dartmouth); C. Seshadhri (UC Santa Cruz)


• Streaming Euclidean MST to a Constant Factor
  Xi Chen (Columbia University); Vincent Cohen-Addad, Rajesh Jayaram (Google Research); Amit Levi (University of Waterloo); Erik Waingarten (Stanford / University of Pennsylvania)


• An efficient decoder for a linear distance quantum LDPC code
  Shouzhen Gu, Christopher A. Pattison (California Institute of Technology); Eugene Tang (Massachusetts Institute of Technology)


• Streaming Euclidean Max-Cut: Dimension vs Data Reduction
  Xiaoyu Chen, Shaofeng H.-C. Jiang (Peking University); Robert Krauthgamer (Weizmann Institute of Science)


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


• Sampling from convex sets with a cold start using multiscale decompositions
  Hariharan Narayanan (TIFR, Mumbai); Amit Rajaraman (Indian Institute of Technology Bombay); Piyush Srivastava (TIFR, Mumbai)


• The complexity of counting planar graph homomorphisms of domain size 3
  Jin-Yi Cai, Ashwin Maran (University of Wisconsin-Madison)


• Better Trees for Santa Claus
  Etienne Bamas (EPFL); Lars Rohwedder (Maastricht University)


• Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
  Wei-Kai Lin, Ethan Mook (Northeastern); Daniel Wichs (Northeastern & NTT Research)


• A proof of the Nisan-Ronen conjecture
  George Christodoulou (Aristotle University of Thessaloniki); Elias Koutsoupias (University of Oxford); Annamaria Kovacs (Goethe University, Frankfurt M.)


• What Makes a Good Fisherman? Linear Regression under Self-Selection Bias
  Yeshwanth Cherapanamjeri (UC Berkeley); Constantinos Daskalakis (Massachusetts Institute of Technology); Andrew Ilyas (MIT); Manolis Zampetakis (UC Berkeley)


• Weighted Edit Distance Computation: Strings, Trees, and Dyck
  Debarati Das (Pennsylvania State University); Jacob Gilbert, MohammadTaghi Hajiaghayi (University of Maryland); Tomasz Kociumaka (Max Planck Institute for Informatics); Barna Saha (University of California San Diego)


• Obfuscation of Pseudo-Deterministic Quantum Circuits
  James Bartusek (UC Berkeley); Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa (NTT Social Informatics Laboratories)


• SDPs and Robust Satisfiability of Promise CSP
  Joshua Brakensiek (Stanford); Venkatesan Guruswami, Sai Sandeep (UC Berkeley)


• Approximating Iterated Multiplication of Stochastic Matrices in Small Space
  Gil Cohen (Tel Aviv University); Dean Doron (Ben Gurion); Ori Sberlo, Amnon Ta-Shma (Tel Aviv University)


• A Unifying Theory of Distance from Calibration
  Jarosław Błasiok (Columbia University); Parikshit Gopalan (Apple); Lunjia Hu (Stanford University); Preetum Nakkiran (Apple)


• New High Dimensional Expanders from Covers
  Yotam Dikstein (Weizmann Institute of science)


• Algorithms approaching the threshold for semi-random planted clique
  Rares-Darius Buhai (ETH Zurich); Pravesh K. Kothari (CMU); David Steurer (ETH Zurich)


• A Unified Framework for Light Spanners
  Hung Le (University of Massachusetts); Shay Solomon (Tel Aviv University)


• First-Order Model Checking on Structurally Sparse Graph Classes
  Jan Dreier (TU Wien); Nikolas Mählmann, Sebastian Siebertz (University of Bremen)


• Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
  Rahul Ilango (MIT); Jiatu Li (Tsinghua University); Ryan Williams (MIT)


• Faster Walsh-Hadamard and Discrete Fourier Transforms From Matrix Non-Rigidity
  Josh Alman, Kevin Rao (Columbia University)


• Hardness Self-Amplification: Simplified, Optimized, and Unified
  Shuichi Hirahara (National Institute of Informatics); Nobutaka Shimizu (Tokyo Institute of Technology)


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


• A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning
  Ilias Diakonikolas, Christos Tzamos (UW Madison); Daniel Kane (UCSD)


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


• Multi-Agent Contracts
  Paul Duetting (Google Research); Tomer Ezra (Sapienza University of Rome); Michal Feldman (Tel Aviv University and Microsoft Research); Thomas Kesselheim (University of Bonn)


• Privately Estimating a Gaussian: Efficient, Robust and Optimal
  Daniel Alabi (Columbia University); Pravesh K Kothari (Carnegie Mellon University); Pranay Tankala, Prayaag Venkat (Harvard University); Fred Zhang (UC Berkeley)


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


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


• New algorithms for all pairs approximate shortest paths
  Liam Roditty (Bar Ilan University)


• Commitments to Quantum States
  Sam Gunn, Nathan Ju (UC Berkeley); Fermi Ma (Simons Institute and UC Berkeley); Mark Zhandry (NTT Research and Princeton University)


• Randomized versus Deterministic Decision Tree Size
  Arkadev Chattopadhyay (STCS, TIFR, Mumbai); Yogesh Dahiya (IMSc, Chennai); Nikhil Mande (QuSoft and CWI, Amsterdam); Jaikumar Radhakrishnan (STCS, TIFR, Mumbai, and ICTS, Bengaluru); Swagato Sanyal (IIT Kharagpur)


• Boosting Batch Arguments and RAM Delegation
  Yael Kalai (Microsoft Research and MIT); Alex Lombardi (Simons Institute and UC Berkeley); Vinod Vaikuntanathan (MIT); Daniel Wichs (Northeastern and NTT Research)


• Finding a Small Vertex Cut on Distributed Networks
  Yonggang Jiang (Max Planck Institute for Informatics and Saarland University); Sagnik Mukhopadhyay (University of Sheffield


• Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic and Fast
  Bernhard Haeupler (Carnegie Mellon University and ETH Zürich); D Ellis Hershkowitz (ETH Zürich); Thatchaphol Saranurak (University of Michigan)


• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
  Alexander Dalzell, Nicola Pancotti (Amazon Web Services (AWS) Center for Quantum Computing); Earl T. Campbell (Riverlane); Fernando G.S.L. Brandao (Caltech)


• The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
  Marco Bressan (University of Milan); Matthias Lanzinger, Marc Roth (University of Oxford)


• An Optimal "It Ain't Over Till It's Over" Theorem
  Pei Wu, Avi Wigderson (Institute for Advanced Study); Ronen Eldan (Microsoft Research)


• A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
  Aravind Gollakota, Adam R. Klivans (University of Texas at Austin); Pravesh K. Kothari (CMU)


• Parallel Discrete Sampling via Continuous Walks
  Nima Anari (Stanford University); Yizhi Huang (Tsinghua University); Tianyu Liu, Thuy-Duong Vuong, Brian Xu, Katherine Yu (Stanford University)


• Quantum free games
  Anand Natarajan, Tina Zhang (MIT)


• Learning Polynomial Transformations via Generalized Tensor Decompositions
  Sitan Chen (UC Berkeley); Jerry Li, Yuanzhi Li (Microsoft Research); Anru Zhang (Duke)


• A Borsuk-Ulam lower bound for sign-rank and its applications
  Hamed Hatami (McGill University); Kaave Hosseini (University of Rochester); Xiang Meng (McGill University)


• Dynamic ((1+ϵ)lnn)-Approximation Algorithms for Minimum Set Cover and Dominating Set
  Shay Solomon, Amitai Uzrad (Tel Aviv University)


• Lifting uniform learners via distributional decomposition
  Guy Blanc (Stanford University); Jane Lange (MIT); Ali Malik, Li-Yang Tan (Stanford University)


• Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
  Sebastian Forster, Yasamin Nazari (University of Salzburg); Maximilian Probst Gutenberg (ETH Zurich)


• Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓp​ Norms
  Huck Bennett (Oregon State University); Mahdi Cheraghchi (University of Michigan); Venkatesan Guruswami (UC Berkeley); João Ribeiro (New University of Lisbon)


• When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems
  Lijie Chen (Miller Institute for Basic Research in Science, UC Berkeley); Roei Tell (The Institute for Advanced Study at Princeton NJ and the DIMACS Center at Rutgers University)


• Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees
  Pooya Hatami (Ohio State University); William Hoza (Simons Institute for the Theory of Computing); Avishay Tal (UC Berkeley); Roei Tell (IAS & DIMACS)


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


• Towards the Erdős-Gallai Cycle Decomposition Conjecture
  Matija Bucic (Institute for Advanced Study and Princeton University); Richard Montgomery (University of Warwick)


• Fast Algorithms via Dynamic-Oracle Matroids
  Joakim Blikstad (KTH Royal Institute of Technology); Sagnik Mukhopadhyay (University of Sheffield); Danupon Nanongkai (Max Planck Institute for Informatics & KTH); Ta-Wei Tu (Max Planck Institute for Informatics)


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


• Sum-of-Squares Lower Bounds for Densest k-Subgraph
  Chris Jones (Bocconi University); Aaron Potechin (University of Chicago); Goutham Rajendran, Jeff Xu (Carnegie Mellon University)


• Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse
  Ravishankar Krishnaswamy (Microsoft Research India); Shi Li (University at Buffalo); Varun Suriyanarayana (Cornell University


• Tight Conditional Lower Bounds for Vertex Connectivity Problems
  Zhiyi Huang (Tsinghua University); Yaowei Long, Thatchaphol Saranurak (University of Michigan); Benyu Wang (Tsinghua University)


• A High Dimensional Goldreich-Levin Theorem
  Parker Newton, Silas Richelson, Chase Wilson (University of California, Riverside)


• Quantum Cryptography in Algorithmica
  William Kretschmer (UT Austin); Luowen Qian (Boston University); Makrand Sinha (Simons Institute and UC Berkeley); Avishay Tal (UC Berkeley)


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


• Lattice Problems Beyond Polynomial Time
  Divesh Aggarwal (National University of Singapore); Huck Bennett (Oregon State University); Zvika Brakerski (Weizmann Institute of Science); Alexander Golovnev (Georgetown University); Rajendra Kumar (Weizmann Institute of Science); Zeyong Li (National University of Singapore); Spencer Peters, Noah Stephens-Davidowitz (Cornell University); Vinod Vaikuntanathan (MIT)


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


• Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme
  Hu Fu (Shanghai University of Finance and Economics); Jiawei Li (University of Texas at Austin); Daogao Liu (University of Washington)


• Stochastic Minimum Vertex Cover in General Graphs: a 3/2-Approximation
  Mahsa Derakhshan (Northeastern University); Naveen Durvasula, Nika Haghtalab (University of California, Berkeley)


• Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
  Soheil Behnezhad (Northeastern University); Mohammad Roghani, Aviad Rubinstein (Stanford University)


• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
  Alexander S. Wein (UC Davis)


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


• A polynomial-time classical algorithm for noisy random circuit sampling
  Dorit Aharonov (Hebrew University); Xun Gao (Harvard University); Zeph Landau, Yunchao Liu, Umesh Vazirani (UC Berkeley)


• Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
  Vaclav Rozhon (ETH Zurich); Bernhard Haeupler (ETHZ & Carnegie Mellon University); Anders Martinsson, Christoph Grunau, Goran Zuzic (ETH Zurich)


• Computing better approximate pure Nash equilibria in cut games via semidefinite programming
  Ioannis Caragiannis, Zhile Jiang (Aarhus University)


• Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
  Timothy M. Chan (UIUC); Virginia Vassilevska Williams (Massachusetts Institute of Technology); Yinzhan Xu (MIT)


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


• Locally consistent decomposition of strings with applications to edit distance sketching
  Sudatta Bhattacharya, Michal Koucký (Charles University)


• Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics
  Amir Abboud (Weizmann Institute of Science); Karl Bringmann, Nick Fischer (Saarland University and Max-Planck-Institute for Informatics)


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


• Uniformly Random Colourings of Sparse Graphs
  Eoin Hurley (Universität Heidelberg); François Pirot (Université Paris-Saclay)


• Faster Deterministic Distributed MIS and Approximate Matching
  Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich)


• Constant-Round Arguments from One-Way Functions
  Noga Amit (Weizmann Institute of Science); Guy Rothblum (Apple)


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


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


• A New Approach to Learning Linear Dynamical Systems
  Morris Yau, Ainesh Bakshi, Allen Liu (MIT); Ankur Moitra (Math & CSAIL, MIT)


• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
  Fernando Granha Jeronimo, Pei Wu (IAS)


• The Rate of Interactive Codes is Bounded Away from 1
  Klim Efremenko (Ben-Gurion University); Gillat Kol, Dmitry Paramonov (Princeton University); Raghuvansh R. Saxena (Microsoft Research)


• Faster Isomorphism for p-Groups of Class 2 and Exponent p
  Xiaorui Sun (University of Illinois at Chicago)


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


• Sublinear Algorithms for (1.5+ϵ)-Approximate Matching
  Sayan Bhattacharya, Peter Kiss (University of Warwick); Thatchaphol Saranurak (University of Michigan)


• On the consistency of circuit lower bounds for non-deterministic time
  Albert Atserias (Universitat Politècnica de Catalunya); Sam Buss (Univ. of California, San Diego); Moritz Müller (Universität Passau)