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;; 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)

    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)