STOC 2023
55th Annual ACM Symposium on Theory of Computing (STOC 2023)
Powered by
Conference Publishing Consulting

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

STOC 2023 – Preliminary Table of Contents

Contents - Abstracts - Authors

Frontmatter

Title Page
Message from the Chairs
Committees
Sponsors

Papers

Planning and Learning in Partially Observable Systems via Filter Stability
Noah GolowichORCID logo, Ankur Moitra ORCID logo, and Dhruv Rohatgi ORCID logo
(Massachusetts Institute of Technology, USA)
Article Search
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online
David P. Woodruff ORCID logo and Taisuke Yasuda ORCID logo
(Carnegie Mellon University, USA)
Article Search
Good Quantum LDPC Codes with Linear Time Decoders
Irit Dinur ORCID logo, Min-Hsiu Hsieh ORCID logo, Ting-Chun Lin ORCID logo, and Thomas Vidick ORCID logo
(Weizmann Institute of Science, Israel; Hon Hai Research Institute, Taiwan; University of California at San Diego, San Diego, USA)
Preprint
Optimal Eigenvalue Approximation via Sketching
William Swartworth ORCID logo and David P. Woodruff ORCID logo
(University of California at Los Angeles, Los Angeles, USA; Carnegie Mellon University, USA)
Article Search
Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank
Nikhil Bansal, Haotian Jiang, and Raghu Meka
(University of Michigan, Ann Arbor, USA; University of Washington, Seattle, USA; University of California at Los Angeles, Los Angeles, USA)
Article Search
Approximating Binary Longest Common Subsequence in Almost-Linear Time
Xiaoyu He ORCID logo and Ray Li ORCID logo
(Princeton University, USA; University of California at Berkeley, Berkeley, USA)
Article Search
The Power of Multi-step Vizing Chains
Aleksander Bjørn Grodt Christiansen ORCID logo
(DTU, Denmark)
Article Search
Local and Global Expansion in Random Geometric Graphs
Siqi Liu ORCID logo, Sidhanth Mohanty ORCID logo, Tselil Schramm ORCID logo, and Elizabeth Yang ORCID logo
(University of California at Berkeley, Berkeley, USA; Stanford University, USA)
Article Search Info
Improved and Deterministic Online Service with Deadlines or Delay
Noam Touitou ORCID logo
(Amazon, Israel)
Article Search
Near-Optimal Derandomization of Medium-Width Branching Programs
Aaron (Louie) Putterman ORCID logo and Edward Pyne ORCID logo
(Harvard University, USA; Massachusetts Institute of Technology, USA)
Article Search
Extractors for Images of Varieties
Zeyu Guo ORCID logo, Ben Lee VolkORCID logo, Akhil Jalan ORCID logo, and David Zuckerman ORCID logo
(Ohio State University, USA; Reichman University, Israel; University of Texas at Austin, USA)
Article Search
On Regularity Lemma and Barriers in Streaming and Dynamic Matching
Sepehr Assadi ORCID logo, Soheil Behnezhad ORCID logo, Sanjeev Khanna ORCID logo, and Huan Li ORCID logo
(Rutgers University, USA; Northeastern University, USA; University of Pennsylvania, USA)
Preprint
Improved Dynamic Colouring of Sparse Graphs
Aleksander Bjørn Grodt Christiansen ORCID logo, Krzysztof Nowicki ORCID logo, and Eva Rotenberg ORCID logo
(DTU, Denmark; University of Copenhagen, Denmark; pathway.com, Poland)
Article Search
Approximate Graph Colouring and the Hollow Shadow
Lorenzo Ciardo ORCID logo and Stanislav Zivny ORCID logo
(University of Oxford, UK)
Preprint
Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis
André Lieutier ORCID logo and Mathijs Wintraecken ORCID logo
(No affiliation, France; Inria, France; IST Austria, Austria)
Article Search
NLTS Hamiltonians from Good Quantum Codes
Anurag Anshu ORCID logo, Nikolas P. Breuckmann ORCID logo, and Chinmay Nirkhe ORCID logo
(Harvard University, USA; University College London, UK; IBM, USA)
Article Search
Robustness Implies Privacy in Statistical Estimation
Samuel B. HopkinsORCID logo, Gautam KamathORCID logo, Mahbod MajidORCID logo, and Shyam NarayananORCID logo
(Massachusetts Institute of Technology, USA; University of Waterloo, Canada; Carnegie Mellon University, USA)
Article Search
An Analogue of Bonami’s Lemma for Functions on Spaces of Linear Maps, and 2-2 Games
Guy Kindler ORCID logo, David Ellis ORCID logo, and Noam Lifshitz ORCID logo
(Hebrew University of Jerusalem, Israel; Bristol University, UK)
Article Search
Testing Distributional Assumptions of Learning Algorithms
Ronitt Rubinfeld ORCID logo and Arsen Vasilyan ORCID logo
(Massachusetts Institute of Technology, USA)
Article Search Info
Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion
Ronen Eldan ORCID logo, Dan Mikulincer ORCID logo, and Prasad RaghavendraORCID logo
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; University of California at Berkeley, Berkeley, USA)
Preprint
Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness
Riddhi Ghosal ORCID logo, Yuval Ishai ORCID logo, Alexis Korb ORCID logo, Eyal Kushilevitz ORCID logo, Paul Lou ORCID logo, and Amit Sahai ORCID logo
(University of California at Los Angeles, Los Angeles, USA; Technion, Israel)
Article Search
On Approximability of Satisfiable k-CSPs: II
Amey Bhangale ORCID logo, Subhash Khot ORCID logo, and Dor Minzer ORCID logo
(University of California at Riverside, Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA)
Article Search
On Approximability of Satisfiable k-CSPs: III
Amey Bhangale ORCID logo, Subhash Khot ORCID logo, and Dor Minzer ORCID logo
(University of California at Riverside, Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA)
Article Search
A (1.5+epsilon)-Approximation Algorithm for Weighted Connectivity Augmentation
Vera Traub ORCID logo and Rico Zenklusen ORCID logo
(University of Bonn, Germany; ETH Zurich, Switzerland)
Article Search
Nearly All k-SAT Functions Are Unate
József Balogh ORCID logo, Dingding Dong ORCID logo, Bernard Lidický ORCID logo, Nitya Mani ORCID logo, and Yufei Zhao ORCID logo
(University of Illinois at Urbana-Champaign, USA; Harvard University, USA; Iowa State University, USA; Massachusetts Institute of Technology, USA)
Article Search Info
Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
Sophie Huiberts ORCID logo, Yin Tat Lee ORCID logo, and Xinzhi Zhang ORCID logo
(Columbia University, USA; University of Washington, USA)
Article Search
Almost-Optimal Sublinear Additive Spanners
Zihan Tan ORCID logo and Tianyi Zhang ORCID logo
(Rutgers University, USA; Tel Aviv University, Israel)
Preprint
Binary Error-Correcting Codes with Minimal Noiseless Feedback
Meghal GuptaORCID logo, Venkatesan Guruswami ORCID logo, and Rachel Yun Zhang ORCID logo
(University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA)
Article Search
Succinct Computational Secret Sharing
Benny Applebaum ORCID logo, Amos Beimel ORCID logo, Yuval Ishai ORCID logo, Eyal Kushilevitz ORCID logo, Tianren Liu ORCID logo, and Vinod VaikuntanathanORCID logo
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel; Technion, Israel; Peking University, China; Massachusetts Institute of Technology, USA)
Article Search
Generic Reed-Solomon Codes Achieve List-Decoding Capacity
Joshua Brakensiek ORCID logo, Sivakanth Gopi ORCID logo, and Visu Makam ORCID logo
(Stanford University, USA; Microsoft Research, USA; Radix Trading Europe, Netherlands)
Article Search
Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory
Qipeng Liu ORCID logo, Ran Raz ORCID logo, and Wei Zhan ORCID logo
(Simons Institute for the Theory of Computing, Berkeley, USA; Princeton University, USA)
Preprint
Capturing One-Way Functions via NP-Hardness of Meta-Complexity
Shuichi Hirahara ORCID logo
(National Institute of Informatics, Japan)
Article Search
Optimal Bounds for Noisy Sorting
Yuzhou Gu ORCID logo and Yinzhan Xu ORCID logo
(Massachusetts Institute of Technology, USA)
Preprint
The Randomized k-Server Conjecture Is False!
Sébastien BubeckORCID logo, Christian Coester ORCID logo, and Yuval Rabani ORCID logo
(Microsoft Research, USA; University of Oxford, UK; Hebrew University of Jerusalem, Israel)
Article Search
Random Walks on Rotating Expanders
Gil Cohen ORCID logo and Gal Maor ORCID logo
(Tel Aviv University, Israel)
Article Search
Almost Chor-Goldreich Sources and Adversarial Random Walks
Dean Doron ORCID logo, Dana Moshkovitz ORCID logo, Justin Oh ORCID logo, and David Zuckerman ORCID logo
(Ben-Gurion University of the Negev, Israel; University of Texas at Austin, USA)
Article Search
Dynamic Maxflow via Dynamic Interior Point Methods
Jan van den Brand ORCID logo, Yang P. LiuORCID logo, and Aaron Sidford ORCID logo
(Georgia Institute of Technology, USA; Stanford University, USA)
Preprint
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification
Arun Jambulapati ORCID logo, Yang P. LiuORCID logo, and Aaron Sidford ORCID logo
(University of Washington, USA; Stanford University, USA)
Article Search
Kneser Graphs Are Hamiltonian
Arturo Merino ORCID logo, Torsten Mütze ORCID logo, and Namrata ORCID logo
(TU Berlin, Germany; University of Warwick, UK)
Article Search
A Duality between One-Way Functions and Average-Case Symmetry of Information
Shuichi Hirahara ORCID logo, Rahul IlangoORCID logo, Zhenjian Lu ORCID logo, Mikito Nanashima ORCID logo, and Igor C. OliveiraORCID logo
(National Institute of Informatics, Japan; Massachusetts Institute of Technology, USA; University of Oxford, UK; Tokyo Institute of Technology, Japan; University of Warwick, UK)
Article Search
Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues
Lap Chi Lau ORCID logo, Kam Chuen Tung ORCID logo, and Robert Wang ORCID logo
(University of Waterloo, Canada)
Article Search
External Memory Fully Persistent Search Trees
Gerth Stølting Brodal ORCID logo, Casper Moldrup Rysgaard ORCID logo, and Rolf Svenning ORCID logo
(Aarhus University, Denmark)
Article Search
A New Berry-Esseen Theorem for Expander Walks
Louis Golowich ORCID logo
(University of California at Berkeley, Berkeley, USA)
Article Search
Interior Point Methods with a Gradient Oracle
Adrian Vladu ORCID logo
(CNRS, France; IRIF, France; Université Paris Cité, France)
Article Search
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
Omar Alrabiah ORCID logo, Venkatesan Guruswami ORCID logo, Pravesh K. Kothari ORCID logo, and Peter Manohar ORCID logo
(University of California at Berkeley, Berkeley, USA; Carnegie Mellon University, USA)
Article Search
Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
Jiatu LiORCID logo and Igor C. OliveiraORCID logo
(Tsinghua University, China; University of Warwick, UK)
Article Search
Certified Randomness from Quantum Supremacy
Scott Aaronson ORCID logo and Shih-Han Hung ORCID logo
(University of Texas at Austin, USA)
Article Search
A PTAS for Minimizing Weighted Flow Time on a Single Machine
Alexander Armbruster ORCID logo, Lars Rohwedder ORCID logo, and Andreas Wiese ORCID logo
(TU Munich, Germany; Maastricht University, Netherlands)
Article Search
Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms
Yeyuan Chen ORCID logo, Yizhi Huang ORCID logo, Jiatu Li ORCID logo, and Hanlin RenORCID logo
(Xi’an Jiaotong University, China; Tsinghua University, China; University of Oxford, UK)
Article Search
Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
Edith Cohen ORCID logo, Xin Lyu ORCID logo, Jelani Nelson ORCID logo, Tamás Sarlós ORCID logo, and Uri Stemmer ORCID logo
(Google Research, USA; Tel Aviv University, Israel; University of California at Berkeley, Berkeley, USA; Google Research, Israel)
Article Search Info
Linear Independence, Alternants, and Applications
Vishwas Bhargava ORCID logo, Shubhangi Saraf ORCID logo, and Ilya Volkovich ORCID logo
(University of Waterloo, Canada; University of Toronto, Canada; Boston College, USA)
Article Search Info
Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
Tobias Friedrich ORCID logo, Davis Issac ORCID logo, Nikhil Kumar ORCID logo, Nadym Mallek ORCID logo, and Ziena Zeif ORCID logo
(Hasso Plattner Institute, Potsdam, Germany)
Article Search
A Constant Factor Prophet Inequality for Online Combinatorial Auctions
Jose Correa ORCID logo and Andres Cristi ORCID logo
(Universidad de Chile, Chile)
Article Search
Shellability Is Hard Even for Balls
Pavel Paták ORCID logo and Martin Tancer ORCID logo
(Charles University, Prague, Czechia; Czech Technical University, Prague, Czechia)
Article Search
Quantum Depth in the Random Oracle Model
Atul Singh Arora ORCID logo, Andrea ColadangeloORCID logo, Matthew Coudron ORCID logo, Alexandru Gheorghiu ORCID logo, Uttam Singh ORCID logo, and Hendrik Waldner ORCID logo
(California Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; National Institute of Standards and Technology, USA; University of Maryland, USA; Chalmers University of Technology, Sweden; Centre for Theoretical Physics, Warsaw, Poland; IIIT Hyderabad, India; University of Maryland, College Park, USA; MPI-SP, Germany)
Article Search
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
Yizhi Huang ORCID logo, Rahul IlangoORCID logo, and Hanlin RenORCID logo
(Tsinghua University, China; Massachusetts Institute of Technology, USA; University of Oxford, UK)
Article Search
Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees
Elchanan Mossel ORCID logo, Allan Sly ORCID logo, and Youngtak Sohn ORCID logo
(Massachusetts Institute of Technology, USA; Princeton University, USA)
Preprint
Random Graph Matching at Otter’s Threshold via Counting Chandeliers
Cheng MaoORCID logo, Yihong WuORCID logo, Jiaming XuORCID logo, and Sophie H. YuORCID logo
(Georgia Institute of Technology, USA; Yale University, USA; Duke University, USA)
Article Search
Removing Additive Structure in 3SUM-Based Reductions
Ce JinORCID logo and Yinzhan Xu ORCID logo
(Massachusetts Institute of Technology, USA)
Preprint
Multidimensional Quantum Walks
Stacey Jeffery ORCID logo and Sebastian Zur ORCID logo
(CWI, Amsterdam, Netherlands; QuSoft, Netherlands)
Preprint
An Improved Approximation Guarantee for Prize-Collecting TSP
Jannis Blauth ORCID logo and Martin Nägele ORCID logo
(University of Bonn, Germany)
Preprint
Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades
Zhengyang Liu ORCID logo, Zeyu Ren ORCID logo, and Zihe Wang ORCID logo
(Beijing Institute of Technology, China; Renmin University of China, China)
Article Search
Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making
Qinghua Liu ORCID logo, Praneeth Netrapalli ORCID logo, Csaba Szepesvari ORCID logo, and Chi Jin ORCID logo
(Princeton University, USA; Google Research, India; DeepMind, UK; University of Alberta, Canada)
Article Search Info
Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary Channel
Meghal Gupta ORCID logo and Rachel Yun Zhang ORCID logo
(Microsoft Research, USA; Massachusetts Institute of Technology, USA)
Article Search
Algorithmic Applications of Hypergraph and Partition Containers
Or Zamir ORCID logo
(Princeton University, USA)
Article Search
Quantum Advantage from Any Non-local Game
Yael KalaiORCID logo, Alex LombardiORCID logo, Vinod VaikuntanathanORCID logo, and Lisa Yang ORCID logo
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA)
Preprint
Spectral Hypergraph Sparsification via Chaining
James R. Lee ORCID logo
(University of Washington, USA)
Article Search
Approximating Nash Social Welfare by Matching and Local Search
Jugal GargORCID logo, Edin HusicORCID logo, Wenzheng Li ORCID logo, László A. VéghORCID logo, and Jan Vondrák ORCID logo
(University of Illinois at Urbana-Champaign, USA; USI Lugano, Switzerland; Stanford University, USA; London School of Economics, UK)
Article Search
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $\Widetilde{O}(n\sqrt{d})$ Monotonicity Tester
Hadley Black ORCID logo, Deeparnab Chakrabarty ORCID logo, and C. Seshadhri ORCID logo
(University of California at Los Angeles, Los Angeles, USA; Dartmouth College, USA; University of California at Santa Cruz, Santa Cruz, USA)
Preprint
Streaming Euclidean MST to a Constant Factor
Xi ChenORCID logo, Vincent Cohen-Addad ORCID logo, Rajesh Jayaram ORCID logo, Amit Levi ORCID logo, and Erik Waingarten ORCID logo
(Columbia University, USA; Google Research, France; Google Research, USA; University of Waterloo, Canada; Stanford University, USA; University of Pennsylvania, USA)
Article Search
An Efficient Decoder for a Linear Distance Quantum LDPC Code
Shouzhen Gu ORCID logo, Christopher A. Pattison ORCID logo, and Eugene Tang ORCID logo
(California Institute of Technology, USA; Massachusetts Institute of Technology, USA)
Preprint
Streaming Euclidean Max-Cut: Dimension vs Data Reduction
Xiaoyu Chen ORCID logo, Shaofeng H.-C. Jiang ORCID logo, and Robert Krauthgamer ORCID logo
(Peking University, China; Weizmann Institute of Science, Israel)
Preprint
On the Optimal Fixed-Price Mechanism in Bilateral Trade
Yang Cai ORCID logo and Jinzhao Wu ORCID logo
(Yale University, USA)
Article Search
Sampling from Convex Sets with a Cold Start using Multiscale Decompositions
Hariharan Narayanan ORCID logo, Amit Rajaraman ORCID logo, and Piyush Srivastava ORCID logo
(TIFR, Mumbai, India; IIT Bombay, India)
Article Search
The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3
Jin-Yi Cai ORCID logo and Ashwin Maran ORCID logo
(University of Wisconsin-Madison, USA)
Preprint
Better Trees for Santa Claus
Etienne Bamas ORCID logo and Lars Rohwedder ORCID logo
(EPFL, Switzerland; Maastricht University, Netherland)
Preprint
Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
Wei-Kai Lin ORCID logo, Ethan Mook ORCID logo, and Daniel WichsORCID logo
(Northeastern University, USA; NTT Research, USA)
Preprint
A Proof of the Nisan-Ronen Conjecture
George Christodoulou ORCID logo, Elias Koutsoupias ORCID logo, and Annamária Kovács ORCID logo
(Aristotle University of Thessaloniki, Greece; RC Athena, Greece; University of Oxford, UK; Goethe University, Frankfurt am Main, Germany)
Article Search
What Makes a Good Fisherman? Linear Regression under Self-Selection Bias
Yeshwanth Cherapanamjeri ORCID logo, Constantinos Daskalakis ORCID logo, Andrew IlyasORCID logo, and Manolis Zampetakis ORCID logo
(University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA)
Article Search
Weighted Edit Distance Computation: Strings, Trees, and Dyck
Debarati Das ORCID logo, Jacob Gilbert ORCID logo, MohammadTaghi Hajiaghayi ORCID logo, Tomasz Kociumaka ORCID logo, and Barna Saha ORCID logo
(Pennsylvania State University, USA; University of Maryland, USA; MPI-INF, Germany; University of California at San Diego, San Diego, USA)
Preprint
Obfuscation of Pseudo-Deterministic Quantum Circuits
James Bartusek ORCID logo, Fuyuki Kitagawa ORCID logo, Ryo Nishimaki ORCID logo, and Takashi Yamakawa ORCID logo
(University of California at Berkeley, Berkeley, USA; NTT Social Informatics Laboratories, Japan)
Article Search
SDPs and Robust Satisfiability of Promise CSP
Joshua Brakensiek ORCID logo, Venkatesan Guruswami ORCID logo, and Sai Sandeep ORCID logo
(Stanford University, USA; University of California at Berkeley, Berkeley, USA)
Preprint
Approximating Iterated Multiplication of Stochastic Matrices in Small Space
Gil Cohen ORCID logo, Dean Doron ORCID logo, Ori Sberlo ORCID logo, and Amnon Ta-Shma ORCID logo
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel)
Article Search
A Unifying Theory of Distance from Calibration
Jarosław Błasiok ORCID logo, Parikshit Gopalan ORCID logo, Lunjia Hu ORCID logo, and Preetum Nakkiran ORCID logo
(Columbia University, USA; Apple, USA; Stanford University, USA)
Article Search
New High Dimensional Expanders from Covers
Yotam Dikstein ORCID logo
(Weizmann Institute of Science, Israel)
Article Search
Algorithms Approaching the Threshold for Semi-random Planted Clique
Rares-Darius Buhai ORCID logo, Pravesh K. Kothari ORCID logo, and David Steurer ORCID logo
(ETH Zurich, Switzerland; Carnegie Mellon University, USA)
Article Search
A Unified Framework for Light Spanners
Hung LeORCID logo and Shay Solomon ORCID logo
(University of Massachusetts, USA; Tel Aviv University, Israel)
Preprint
First-Order Model Checking on Structurally Sparse Graph Classes
Jan Dreier ORCID logo, Nikolas Mählmann ORCID logo, and Sebastian Siebertz ORCID logo
(TU Wien, Austria; University of Bremen, Germany)
Article Search
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
Rahul IlangoORCID logo, Jiatu LiORCID logo, and R. Ryan Williams ORCID logo
(Massachusetts Institute of Technology, USA; Tsinghua University, China)
Article Search
Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity
Josh Alman ORCID logo and Kevin Rao ORCID logo
(Columbia University, USA)
Article Search
Hardness Self-Amplification: Simplified, Optimized, and Unified
Shuichi Hirahara ORCID logo and Nobutaka Shimizu ORCID logo
(National Institute of Informatics, Japan; Tokyo Institute of Technology, Japan)
Article Search
A Characterization of List Learnability
Moses Charikar ORCID logo and Chirag Pabbaraju ORCID logo
(Stanford University, USA)
Article Search
A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning
Ilias Diakonikolas ORCID logo, Christos Tzamos ORCID logo, and Daniel M. Kane ORCID logo
(University of Wisconsin-Madison, USA; University of Athens, Greece; University of California at San Diego, San Diego, USA)
Article Search
(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond
Sepehr Assadi ORCID logo and Janani Sundaresan ORCID logo
(Rutgers University, USA)
Article Search
Multi-agent Contracts
Paul Duetting ORCID logo, Tomer Ezra ORCID logo, Michal Feldman ORCID logo, and Thomas Kesselheim ORCID logo
(Google Research, Switzerland; Sapienza University of Rome, Italy; Tel Aviv University, Israel; Microsoft Research, Israel; University of Bonn, Germany)
Article Search
Privately Estimating a Gaussian: Efficient, Robust, and Optimal
Daniel Alabi ORCID logo, Pravesh K. Kothari ORCID logo, Pranay Tankala ORCID logo, Prayaag Venkat ORCID logo, and Fred Zhang ORCID logo
(Columbia University, USA; Carnegie Mellon University, USA; Harvard University, USA; University of California at Berkeley, Berkeley, USA)
Preprint
Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules
Binghui Peng ORCID logo and Xi ChenORCID logo
(Columbia University, USA)
Article Search
A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths
Julia Chuzhoy ORCID logo and Ruimin Zhang ORCID logo
(Toyota Technological Institute at Chicago, USA; University of Chicago, USA)
Article Search
New Algorithms for All Pairs Approximate Shortest Paths
Liam Roditty ORCID logo
(Bar-Ilan University, Israel)
Article Search
Commitments to Quantum States
Sam Gunn ORCID logo, Nathan Ju ORCID logo, Fermi Ma ORCID logo, and Mark Zhandry ORCID logo
(University of California at Berkeley, Berkeley, USA; Simons Institute for the Theory of Computing, Berkeley, USA; NTT Research, USA)
Article Search
Randomized versus Deterministic Decision Tree Size
Arkadev Chattopadhyay ORCID logo, Yogesh Dahiya ORCID logo, Nikhil S. Mande ORCID logo, Jaikumar Radhakrishnan ORCID logo, and Swagato Sanyal ORCID logo
(TIFR, Mumbai, India; IMSc, Chennai, India; QuSoft, Netherlands; CWI, Amsterdam, Netherlands; ICTS, Bengaluru, India; IIT Kharagpur, India)
Preprint
Boosting Batch Arguments and RAM Delegation
Yael KalaiORCID logo, Alex LombardiORCID logo, Vinod VaikuntanathanORCID logo, and Daniel WichsORCID logo
(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)
Preprint
Finding a Small Vertex Cut on Distributed Networks
Yonggang Jiang ORCID logo and Sagnik Mukhopadhyay ORCID logo
(MPI-INF, Germany; Saarland University, Germany; University of Sheffield, UK)
Article Search
Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast
Bernhard Haeupler ORCID logo, D. Ellis Hershkowitz ORCID logo, and Thatchaphol SaranurakORCID logo
(ETH Zurich, Switzerland; Carnegie Mellon University, USA; University of Michigan, USA)
Preprint
Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End
Alexander M. Dalzell ORCID logo, Nicola Pancotti ORCID logo, Earl T. Campbell ORCID logo, and Fernando G. S. L. Brandao ORCID logo
(AWS Center for Quantum Computing, USA; California Institute of Technology, USA; Riverlane, UK; University of Sheffield, UK)
Article Search
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
Marco Bressan ORCID logo, Matthias Lanzinger ORCID logo, and Marc Roth ORCID logo
(University of Milan, Italy; University of Oxford, UK)
Article Search
An Optimal “It Ain’t Over Till It’s Over” Theorem
Ronen Eldan ORCID logo, Avi Wigderson ORCID logo, and Pei Wu ORCID logo
(Microsoft Research, USA; Weizmann Institute of Science, Israel; Institute for Advanced Study, Princeton, USA)
Article Search
A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
Aravind Gollakota ORCID logo, Adam R. Klivans ORCID logo, and Pravesh K. Kothari ORCID logo
(University of Texas at Austin, USA; Carnegie Mellon University, USA)
Article Search
Parallel Discrete Sampling via Continuous Walks
Nima Anari ORCID logo, Yizhi Huang ORCID logo, Tianyu Liu ORCID logo, Thuy-Duong Vuong ORCID logo, Brian Xu ORCID logo, and Katherine Yu ORCID logo
(Stanford University, USA; Tsinghua University, China)
Article Search
Quantum Free Games
Anand Natarajan ORCID logo and Tina Zhang ORCID logo
(Massachusetts Institute of Technology, USA)
Article Search
Learning Polynomial Transformations via Generalized Tensor Decompositions
Sitan Chen ORCID logo, Jerry Li ORCID logo, Yuanzhi Li ORCID logo, and Anru Zhang ORCID logo
(University of California at Berkeley, Berkeley, USA; Harvard University, USA; Microsoft Research, USA; Duke University, USA)
Article Search
A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications
Hamed Hatami ORCID logo, Kaave Hosseini ORCID logo, and Xiang Meng ORCID logo
(McGill University, Canada; University of Rochester, USA)
Article Search
Dynamic $((1+\epsilon)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
Shay Solomon ORCID logo and Amitai Uzrad ORCID logo
(Tel Aviv University, Israel)
Article Search
Lifting Uniform Learners via Distributional Decomposition
Guy Blanc ORCID logo, Jane Lange ORCID logo, Ali Malik ORCID logo, and Li-Yang Tan ORCID logo
(Stanford University, USA; Massachusetts Institute of Technology, USA)
Article Search
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
Sebastian Forster ORCID logo, Yasamin Nazari ORCID logo, and Maximilian Probst Gutenberg ORCID logo
(University of Salzburg, Austria; ETH Zurich, Switzerland)
Preprint
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All $\ell_p$ Norms
Huck Bennett ORCID logo, Mahdi Cheraghchi ORCID logo, Venkatesan Guruswami ORCID logo, and João RibeiroORCID logo
(Oregon State University, USA; University of Michigan, USA; University of California at Berkeley, Berkeley, USA; NOVA-LINCS, Portugal; Universidade Nova de Lisboa, Portugal)
Article Search
When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems
Lijie Chen ORCID logo and Roei Tell ORCID logo
(University of California at Berkeley, Berkeley, USA; Institute for Advanced Study, Princeton, USA; Rutgers University, USA)
Article Search
Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees
Pooya Hatami ORCID logo, William M. Hoza ORCID logo, Avishay Tal ORCID logo, and Roei Tell ORCID logo
(Ohio State University, USA; University of California at Berkeley, Berkeley, USA; Institute for Advanced Study, Princeton, USA; Rutgers University, USA)
Article Search
Pandora’s Problem with Nonobligatory Inspection: Optimal Structure and a PTAS
Hedyeh Beyhaghi ORCID logo and Linda Cai ORCID logo
(Carnegie Mellon University, USA; Princeton University, USA)
Article Search
Towards the Erdős-Gallai Cycle Decomposition Conjecture
Matija Bucic ORCID logo and Richard Montgomery ORCID logo
(Institute for Advanced Study, Princeton, USA; Princeton University, USA; University of Warwick, UK)
Preprint Video
Fast Algorithms via Dynamic-Oracle Matroids
Joakim Blikstad ORCID logo, Sagnik Mukhopadhyay ORCID logo, Danupon NanongkaiORCID logo, and Ta-Wei Tu ORCID logo
(KTH Royal Institute of Technology, Sweden; University of Sheffield, UK; MPI-INF, Germany)
Article Search
The Smoothed Complexity of Policy Iteration for Markov Decision Processes
Miranda Christ ORCID logo and Mihalis Yannakakis ORCID logo
(Columbia University, USA)
Article Search
Sum-of-Squares Lower Bounds for Densest k-Subgraph
Chris Jones ORCID logo, Aaron Potechin ORCID logo, Goutham Rajendran ORCID logo, and Jeff Xu ORCID logo
(Bocconi University, Italy; University of Chicago, USA; Carnegie Mellon University, USA)
Article Search
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)
Article Search
Tight Conditional Lower Bounds for Vertex Connectivity Problems
Zhiyi Huang ORCID logo, Yaowei Long ORCID logo, Thatchaphol SaranurakORCID logo, and Benyu Wang ORCID logo
(Tsinghua University, China; University of Michigan, USA)
Article Search
A High Dimensional Goldreich-Levin Theorem
Parker Newton ORCID logo, Silas Richelson ORCID logo, and Chase Wilson ORCID logo
(University of California at Riverside, Riverside, USA)
Article Search
Quantum Cryptography in Algorithmica
William Kretschmer ORCID logo, Luowen Qian ORCID logo, Makrand Sinha ORCID logo, and Avishay Tal ORCID logo
(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)
Preprint
Subsampling Suffices for Adaptive Data Analysis
Guy Blanc ORCID logo
(Stanford University, USA)
Preprint Info
Lattice Problems beyond Polynomial Time
Divesh Aggarwal ORCID logo, Huck Bennett ORCID logo, Zvika Brakerski ORCID logo, Alexander Golovnev ORCID logo, Rajendra Kumar ORCID logo, Zeyong Li ORCID logo, Spencer Peters ORCID logo, Noah Stephens-Davidowitz ORCID logo, and Vinod Vaikuntanathan ORCID logo
(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)
Article Search
The Round Complexity of Statistical MPC with Optimal Resiliency
Benny Applebaum ORCID logo, Eliran Kachlon ORCID logo, and Arpita Patra ORCID logo
(Tel Aviv University, Israel; IISc Bangalore, India)
Article Search
Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme
Hu FuORCID logo, Jiawei Li ORCID logo, and Daogao LiuORCID logo
(Shanghai University of Finance and Economics, China; University of Texas at Austin, USA; University of Washington, USA)
Preprint
Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation
Mahsa Derakhshan ORCID logo, Naveen Durvasula ORCID logo, and Nika Haghtalab ORCID logo
(Northeastern University, USA; University of California at Berkeley, Berkeley, USA)
Article Search
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
Soheil Behnezhad ORCID logo, Mohammad Roghani ORCID logo, and Aviad Rubinstein ORCID logo
(Northeastern University, USA; Stanford University, USA)
Article Search
Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
Alexander S. Wein ORCID logo
(University of California at Davis, Davis, USA)
Article Search
Credible Decentralized Exchange Design via Verifiable Sequencing Rules
Matheus Venturyne Xavier FerreiraORCID logo and David C. Parkes ORCID logo
(Harvard University, USA)
Preprint
A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
Dorit Aharonov ORCID logo, Xun Gao ORCID logo, Zeph Landau ORCID logo, Yunchao Liu ORCID logo, and Umesh Vazirani ORCID logo
(Hebrew University of Jerusalem, Israel; Harvard University, USA; University of California at Berkeley, Berkeley, USA)
Preprint
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
Václav Rozhoň ORCID logo, Bernhard Haeupler ORCID logo, Anders Martinsson ORCID logo, Christoph Grunau ORCID logo, and Goran Zuzic ORCID logo
(ETH Zurich, Switzerland; Carnegie Mellon University, USA)
Article Search
Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming
Ioannis CaragiannisORCID logo and Zhile Jiang ORCID logo
(Aarhus University, Denmark)
Preprint
Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
Timothy M. Chan ORCID logo, Virginia Vassilevska Williams ORCID logo, and Yinzhan Xu ORCID logo
(University of Illinois at Urbana-Champaign, USA; Massachusetts Institute of Technology, USA)
Preprint
Optimal Explicit Small-Depth Formulas for the Coin Problem
Srikanth Srinivasan ORCID logo and Utkarsh Tripathi ORCID logo
(Aarhus University, Denmark; IIT Bombay, India)
Article Search
Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching
Sudatta Bhattacharya ORCID logo and Michal Koucký ORCID logo
(Charles University, Prague, Czechia)
Preprint
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics
Amir Abboud ORCID logo, Karl Bringmann ORCID logo, and Nick Fischer ORCID logo
(Weizmann Institute of Science, Israel; Saarland University, Germany; MPI-INF, Germany)
Article Search
Concurrent Composition Theorems for Differential Privacy
Salil Vadhan ORCID logo and Wanrong Zhang ORCID logo
(Harvard University, USA)
Article Search
Uniformly Random Colourings of Sparse Graphs
Eoin Hurley ORCID logo and François Pirot ORCID logo
(Unaffiliated, Heidelberg, Germany; Université Paris-Saclay, France)
Article Search
Faster Deterministic Distributed MIS and Approximate Matching
Mohsen Ghaffari ORCID logo and Christoph Grunau ORCID logo
(Massachusetts Institute of Technology, USA; ETH Zurich, Switzerland)
Article Search
Constant-Round Arguments from One-Way Functions
Noga Amit ORCID logo and Guy N. RothblumORCID logo
(Weizmann Institute of Science, Israel; Apple, USA)
Article Search
An Improved Parameterized Algorithm for Treewidth
Tuukka KorhonenORCID logo and Daniel Lokshtanov ORCID logo
(University of Bergen, Norway, Norway; University of California at Santa Barbara, Santa Barbara, USA)
Article Search
Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
Mark Bun ORCID logo, Marco Gaboardi ORCID logo, Max Hopkins ORCID logo, Russell Impagliazzo ORCID logo, Rex Lei ORCID logo, Toniann Pitassi ORCID logo, Satchit Sivakumar ORCID logo, and Jessica Sorrell ORCID logo
(Boston University, USA; University of California at San Diego, San Diego, USA; Columbia University, USA; University of Pennsylvania, USA)
Preprint
A New Approach to Learning Linear Dynamical Systems
Ainesh Bakshi ORCID logo, Allen Liu ORCID logo, Ankur Moitra ORCID logo, and Morris Yau ORCID logo
(Massachusetts Institute of Technology, USA)
Article Search
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
Fernando Granha Jeronimo ORCID logo and Pei Wu ORCID logo
(Institute for Advanced Study, Princeton, USA)
Article Search
The Rate of Interactive Codes Is Bounded Away from 1
Klim Efremenko ORCID logo, Gillat Kol ORCID logo, Dmitry Paramonov ORCID logo, and Raghuvansh R. Saxena ORCID logo
(Ben-Gurion University of the Negev, Israel; Princeton University, USA; Microsoft Research, USA)
Article Search
Faster Isomorphism for p-Groups of Class 2 and Exponent p
Xiaorui Sun ORCID logo
(University of Illinois at Chicago, USA)
Article Search
Approximate Distance Sensitivity Oracles in Subquadratic Space
Davide Bilò ORCID logo, Shiri Chechik ORCID logo, Keerti Choudhary ORCID logo, Sarel Cohen ORCID logo, Tobias Friedrich ORCID logo, Simon Krogmann ORCID logo, and Martin Schirneck ORCID logo
(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)
Article Search
Sublinear Algorithms for $(1.5+\epsilon)$-Approximate Matching
Sayan Bhattacharya ORCID logo, Peter Kiss ORCID logo, and Thatchaphol SaranurakORCID logo
(University of Warwick, UK; University of Michigan, USA)
Article Search
On the Consistency of Circuit Lower Bounds for Non-deterministic Time
Albert Atserias ORCID logo, Sam Buss ORCID logo, and Moritz Müller ORCID logo
(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)
Article Search

proc time: 0.26