default search action
55th STOC 2023: Orlando, FL, USA
- Barna Saha, Rocco A. Servedio:
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023. ACM 2023, ISBN 978-1-4503-9913-5
Session 1A
- Dean Doron
, Dana Moshkovitz, Justin Oh, David Zuckerman:
Almost Chor-Goldreich Sources and Adversarial Random Walks. 1-9 - Louis Golowich:
A New Berry-Esseen Theorem for Expander Walks. 10-22 - Aaron (Louie) Putterman, Edward Pyne:
Near-Optimal Derandomization of Medium-Width Branching Programs. 23-34 - Gil Cohen, Dean Doron
Approximating Iterated Multiplication of Stochastic Matrices in Small Space. 35-45 - Zeyu Guo
Extractors for Images of Varieties. 46-59 - Lijie Chen, Roei Tell:
When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems. 60-69 - Shuichi Hirahara, Nobutaka Shimizu
Hardness Self-Amplification: Simplified, Optimized, and Unified. 70-83 - Chris Jones, Aaron Potechin, Goutham Rajendran, Jeff Xu:
Sum-of-Squares Lower Bounds for Densest k-Subgraph. 84-95 - Elchanan Mossel, Allan Sly, Youngtak Sohn:
Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees. 96-102 - Nima Anari, Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu
Parallel Discrete Sampling via Continuous Walks. 103-116 - Hariharan Narayanan
Sampling from Convex Sets with a Cold Start using Multiscale Decompositions. 117-130
Session 1B
- Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna
On Regularity Lemma and Barriers in Streaming and Dynamic Matching. 131-144 - William Swartworth, David P. Woodruff:
Optimal Eigenvalue Approximation via Sketching. 145-155 - Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi
Streaming Euclidean MST to a Constant Factor. 156-169 - Xiaoyu Chen, Shaofeng H.-C. Jiang, Robert Krauthgamer:
Streaming Euclidean Max-Cut: Dimension vs Data Reduction. 170-182 - Sepehr Assadi, Janani Sundaresan:
(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond. 183-195 - Arun Jambulapati, Yang P. Liu, Aaron Sidford:
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification. 196-206 - James R. Lee:
Spectral Hypergraph Sparsification via Chaining. 207-218 - Sudatta Bhattacharya
Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching. 219-232 - Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester. 233-241 - Mahsa Derakhshan, Naveen Durvasula, Nika Haghtalab:
Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation. 242-253 - Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
Sublinear Algorithms for (1.5+ε)-Approximate Matching. 254-266 - Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein:
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. 267-280
Session 1C
- Zihan Tan, Tianyi Zhang:
Almost-Optimal Sublinear Additive Spanners. 281-294 - Hung Le, Shay Solomon:
A Unified Framework for Light Spanners. 295-308 - Liam Roditty:
New Algorithms for All Pairs Approximate Shortest Paths. 309-320 - Václav Rozhon, Bernhard Haeupler, Anders Martinsson, Christoph Grunau
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances. 321-334 - Ainesh Bakshi, Allen Liu, Ankur Moitra, Morris Yau:
A New Approach to Learning Linear Dynamical Systems. 335-348 - Noah Golowich, Ankur Moitra, Dhruv Rohatgi:
Planning and Learning in Partially Observable Systems via Filter Stability. 349-362 - Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvári, Chi Jin:
Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making. 363-376 - Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha:
Weighted Edit Distance Computation: Strings, Trees, and Dyck. 377-390 - Amir Abboud, Karl Bringmann, Nick Fischer:
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics. 391-404 - Ce Jin, Yinzhan Xu:
Removing Additive Structure in 3SUM-Based Reductions. 405-418 - Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu:
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More. 419-432
Session 2A
- Xiaorui Sun:
Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝. 433-440 - Vishwas Bhargava
Linear Independence, Alternants, and Applications. 441-454 - Josh Alman, Kevin Rao:
Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity. 455-462 - Hamed Hatami, Kaave Hosseini
A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications. 463-471
Session 2B
- Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer:
Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization. 472-482 - Daniel Alabi, Pravesh K. Kothari, Pranay Tankala, Prayaag Venkat, Fred Zhang:
Privately Estimating a Gaussian: Efficient, Robust, and Optimal. 483-496 - Samuel B. Hopkins, Gautam Kamath
Robustness Implies Privacy in Statistical Estimation. 497-506 - Salil P. Vadhan, Wanrong Zhang:
Concurrent Composition Theorems for Differential Privacy. 507-519 - Mark Bun, Marco Gaboardi
Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization. 520-527
Session 2C
- Tuukka Korhonen
An Improved Parameterized Algorithm for Treewidth. 528-541 - Marco Bressan, Matthias Lanzinger, Marc Roth
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree. 542-552 - Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms. 553-566 - Jan Dreier
First-Order Model Checking on Structurally Sparse Graph Classes. 567-580
Session 3: Best Papers
- Sébastien Bubeck, Christian Coester
The Randomized k-Server Conjecture Is False! 581-594 - Wei-Kai Lin, Ethan Mook, Daniel Wichs:
Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE. 595-608
Session 4A
- Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep:
SDPs and Robust Satisfiability of Promise CSP. 609-622 - Lorenzo Ciardo, Stanislav Zivný:
Approximate Graph Colouring and the Hollow Shadow. 623-631 - Amey Bhangale, Subhash Khot, Dor Minzer:
On Approximability of Satisfiable k-CSPs: II. 632-642 - Amey Bhangale, Subhash Khot, Dor Minzer:
On Approximability of Satisfiable k-CSPs: III. 643-655 - David Ellis, Guy Kindler, Noam Lifshitz
An Analogue of Bonami's Lemma for Functions on Spaces of Linear Maps, and 2-2 Games. 656-660 - Ronen Eldan, Dan Mikulincer
Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion. 661-671
Session 4B
- George Christodoulou, Elias Koutsoupias, Annamária Kovács:
A Proof of the Nisan-Ronen Conjecture. 672-685 - José Correa, Andrés Cristi:
A Constant Factor Prophet Inequality for Online Combinatorial Auctions. 686-697 - Xi Chen, Binghui Peng:
Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules. 698-709 - Ioannis Caragiannis, Zhile Jiang:
Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming. 710-722 - Matheus Venturyne Xavier Ferreira, David C. Parkes:
Credible Decentralized Exchange Design via Verifiable Sequencing Rules. 723-736 - Yang Cai
On the Optimal Fixed-Price Mechanism in Bilateral Trade. 737-750 - Zhengyang Liu, Zeyu Ren, Zihe Wang:
Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades. 751-760
Session 4C
- Noam Touitou:
Improved and Deterministic Online Service with Deadlines or Delay. 761-774 - Ravishankar Krishnaswamy, Shi Li, Varun Suriyanarayana:
Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse. 775-788 - Hu Fu, Jiawei Li, Daogao Liu:
Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme. 789-802 - Hedyeh Beyhaghi, Linda Cai:
Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS. 803-816 - Siqi Liu, Sidhanth Mohanty, Tselil Schramm, Elizabeth Yang:
Local and Global Expansion in Random Geometric Graphs. 817-825 - Yotam Dikstein:
New High Dimensional Expanders from Covers. 826-838 - Matija Bucic
Towards the Erdős-Gallai Cycle Decomposition Conjecture. 839-852
Session 5A
- Ronen Eldan, Avi Wigderson, Pei Wu:
An Optimal "It Ain't Over Till It's Over" Theorem. 853-866 - Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande
Randomized versus Deterministic Decision Tree Size. 867-880 - Srikanth Srinivasan
Optimal Explicit Small-Depth Formulas for the Coin Problem. 881-894 - Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell:
Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees. 895-904
Session 5B
- Irit Dinur
Good Quantum LDPC Codes with Linear Time Decoders. 905-918 - Shouzhen Gu
An Efficient Decoder for a Linear Distance Quantum LDPC Code. 919-932 - Scott Aaronson, Shih-Han Hung:
Certified Randomness from Quantum Supremacy. 933-944 - Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, Umesh V. Vazirani:
A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling. 945-957
Session 5C
- József Balogh, Dingding Dong
Nearly All k-SAT Functions Are Unate. 958-962 - Arturo Merino, Torsten Mütze, Namrata:
Kneser Graphs Are Hamiltonian. 963-970 - Gil Cohen, Gal Maor:
Random Walks on Rotating Expanders. 971-984 - Or Zamir:
Algorithmic Applications of Hypergraph and Partition Containers. 985-998
Session 6: Best Student Papers
- Guy Blanc:
Subsampling Suffices for Adaptive Data Analysis. 999-1012 - Aleksander Bjørn Grodt Christiansen:
The Power of Multi-step Vizing Chains. 1013-1026
Session 7A
- Shuichi Hirahara:
Capturing One-Way Functions via NP-Hardness of Meta-Complexity. 1027-1038 - Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira:
A Duality between One-Way Functions and Average-Case Symmetry of Information. 1039-1050 - Jiatu Li, Igor C. Oliveira:
Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic. 1051-1057 - Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren
Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms. 1058-1066 - Yizhi Huang, Rahul Ilango, Hanlin Ren
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach. 1067-1075 - Rahul Ilango, Jiatu Li, R. Ryan Williams
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic. 1076-1089
Session 7B
- Anurag Anshu, Nikolas P. Breuckmann
NLTS Hamiltonians from Good Quantum Codes. 1090-1096 - Qipeng Liu, Ran Raz
Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory. 1097-1110 - Atul Singh Arora, Andrea Coladangelo
Quantum Depth in the Random Oracle Model. 1111-1124 - Stacey Jeffery
Multidimensional Quantum Walks. 1125-1130 - Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, Fernando G. S. L. Brandão:
Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End. 1131-1144 - Xiaoyu He
Approximating Binary Longest Common Subsequence in Almost-Linear Time. 1145-1158
Session 7C
- Julia Chuzhoy, Ruimin Zhang:
A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths. 1159-1172 - Sebastian Forster, Yasamin Nazari
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch. 1173-1186 - Shay Solomon, Amitai Uzrad:
Dynamic ((1+ε) ln n)-Approximation Algorithms for Minimum Set Cover and Dominating Set. 1187-1200 - Aleksander Bjørn Grodt Christiansen, Krzysztof Nowicki
Improved Dynamic Colouring of Sparse Graphs. 1201-1214 - Jan van den Brand
Dynamic Maxflow via Dynamic Interior Point Methods. 1215-1228 - Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, Ta-Wei Tu
Fast Algorithms via Dynamic-Oracle Matroids. 1229-1242
Session 8A
- Riddhi Ghosal, Yuval Ishai, Alexis Korb
Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness. 1243-1256 - Albert Atserias, Sam Buss, Moritz Müller:
On the Consistency of Circuit Lower Bounds for Non-deterministic Time. 1257-1270 - Pavel Paták
Shellability Is Hard Even for Balls. 1271-1284 - Jin-Yi Cai, Ashwin Maran:
The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3. 1285-1297
Session 8B
- Jugal Garg, Edin Husic
Approximating Nash Social Welfare by Matching and Local Search. 1298-1310 - Paul Dütting, Tomer Ezra
Multi-agent Contracts. 1311-1324 - Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, Ziena Zeif:
Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth. 1325-1334 - Alexander Armbruster, Lars Rohwedder
A PTAS for Minimizing Weighted Flow Time on a Single Machine. 1335-1344
Session 8C
- Cheng Mao, Yihong Wu, Jiaming Xu, Sophie H. Yu:
Random Graph Matching at Otter's Threshold via Counting Chandeliers. 1345-1356 - Eoin Hurley, François Pirot
Uniformly Random Colourings of Sparse Graphs. 1357-1370 - Bernhard Haeupler, D. Ellis Hershkowitz, Thatchaphol Saranurak
Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast. 1371-1383 - Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak
Tight Conditional Lower Bounds for Vertex Connectivity Problems. 1384-1395
Session 9A
- Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann
Approximate Distance Sensitivity Oracles in Subquadratic Space. 1396-1409 - Gerth Stølting Brodal
External Memory Fully Persistent Search Trees. 1410-1423 - Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena:
The Rate of Interactive Codes Is Bounded Away from 1. 1424-1437 - Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar:
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. 1438-1448 - Meghal Gupta, Rachel Yun Zhang:
Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary Channel. 1449-1462 - Parker Newton, Silas Richelson
A High Dimensional Goldreich-Levin Theorem. 1463-1474 - Meghal Gupta, Venkatesan Guruswami, Rachel Yun Zhang:
Binary Error-Correcting Codes with Minimal Noiseless Feedback. 1475-1487 - Joshua Brakensiek, Sivakanth Gopi, Visu Makam:
Generic Reed-Solomon Codes Achieve List-Decoding Capacity. 1488-1501 - Yuzhou Gu, Yinzhan Xu:
Optimal Bounds for Noisy Sorting. 1502-1515 - Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Rajendra Kumar, Zeyong Li, Spencer Peters, Noah Stephens-Davidowitz, Vinod Vaikuntanathan:
Lattice Problems beyond Polynomial Time. 1516-1526
Session 9B
- Benny Applebaum, Eliran Kachlon, Arpita Patra:
The Round Complexity of Statistical MPC with Optimal Resiliency. 1527-1536 - Noga Amit, Guy N. Rothblum:
Constant-Round Arguments from One-Way Functions. 1537-1544 - Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, Daniel Wichs:
Boosting Batch Arguments and RAM Delegation. 1545-1552 - Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu, Vinod Vaikuntanathan:
Succinct Computational Secret Sharing. 1553-1566 - James Bartusek
Obfuscation of Pseudo-Deterministic Quantum Circuits. 1567-1578 - Sam Gunn, Nathan Ju, Fermi Ma, Mark Zhandry:
Commitments to Quantum States. 1579-1588 - William Kretschmer, Luowen Qian
Quantum Cryptography in Algorithmica. 1589-1602 - Anand Natarajan, Tina Zhang:
Quantum Free Games. 1603-1616 - Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, Lisa Yang:
Quantum Advantage from Any Non-local Game. 1617-1628 - Fernando Granha Jeronimo, Pei Wu:
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes. 1629-1642
Session 9C
- Ronitt Rubinfeld, Arsen Vasilyan:
Testing Distributional Assumptions of Learning Algorithms. 1643-1656 - Aravind Gollakota, Adam R. Klivans, Pravesh K. Kothari:
A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity. 1657-1670 - Sitan Chen, Jerry Li, Yuanzhi Li, Anru R. Zhang:
Learning Polynomial Transformations via Generalized Tensor Decompositions. 1671-1684 - Alexander S. Wein:
Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials. 1685-1698 - Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Andrew Ilyas, Manolis Zampetakis
What Makes a Good Fisherman? Linear Regression under Self-Selection Bias. 1699-1712 - Moses Charikar
A Characterization of List Learnability. 1713-1726 - Jaroslaw Blasiok
A Unifying Theory of Distance from Calibration. 1727-1740 - Ilias Diakonikolas, Christos Tzamos, Daniel M. Kane:
A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning. 1741-1754 - Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan:
Lifting Uniform Learners via Distributional Decomposition. 1755-1767 - André Lieutier, Mathijs Wintraecken:
Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis. 1768-1776
Session 10A
- Mohsen Ghaffari, Christoph Grunau
Faster Deterministic Distributed MIS and Approximate Matching. 1777-1790 - Yonggang Jiang, Sagnik Mukhopadhyay:
Finding a Small Vertex Cut on Distributed Networks. 1791-1801 - David P. Woodruff, Taisuke Yasuda:
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online. 1802-1813 - Nikhil Bansal, Haotian Jiang, Raghu Meka:
Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank. 1814-1819
Session 10B
- Vera Traub, Rico Zenklusen:
A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation. 1820-1833 - Lap Chi Lau, Kam Chuen Tung, Robert Wang:
Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues. 1834-1847 - Jannis Blauth, Martin Nägele
An Improved Approximation Guarantee for Prize-Collecting TSP. 1848-1861 - Étienne Bamas, Lars Rohwedder
Better Trees for Santa Claus. 1862-1875
Session 10C
- Adrian Vladu:
Interior Point Methods with a Gradient Oracle. 1876-1889 - Miranda Christ, Mihalis Yannakakis:
The Smoothed Complexity of Policy Iteration for Markov Decision Processes. 1890-1903 - Sophie Huiberts, Yin Tat Lee, Xinzhi Zhang:
Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method. 1904-1917 - Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
Algorithms Approaching the Threshold for Semi-random Planted Clique. 1918-1926
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-26 00:57 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: