default search action
52nd STOC 2020: Chicago, IL, USA
- Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy:
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020. ACM 2020, ISBN 978-1-4503-6979-4
Session 1A: TSP
- Vera Traub
, Jens Vygen:
An improved approximation algorithm for ATSP. 1-13 - Vera Traub
Reducing path TSP to TSP. 14-27 - Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan:
An improved approximation algorithm for TSP in the half integral case. 28-39 - Jesper Nederlof:
Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication. 40-53
Session 1B: Proof Complexity and Applications of Logics
- Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret
Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative? 54-67 - Mika Göös, Sajin Koroth, Ian Mertz
Automating cutting planes is NP-hard. 68-77 - Dmitry Sokolov
(Semi)Algebraic proofs over ±1 variables. 78-90 - Dmitriy Zhuk, Barnaby Martin
QCSP monsters and the demise of the chen conjecture. 91-104
Session 1C: Distributed and Parallel Algorithms I
- Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Seth Pettie:
Contention resolution without collision detection. 105-118 - Petra Berenbrink, George Giakkoupis
Optimal time and space leader election in population protocols. 119-129 - Eric Balkanski, Yaron Singer:
A lower bound for parallel submodular minimization. 130-139 - Wenzheng Li, Paul Liu
A polynomial lower bound on adaptive complexity of submodular maximization. 140-152
Session 2A: Dynamic Algorithms
- Maximilian Probst Gutenberg
New algorithms and hardness for incremental single-source shortest paths in directed graphs. 153-166 - Jacob Holm
Fully-dynamic planarity testing in polylogarithmic time. 167-180 - Saurabh Sawlani, Junxing Wang:
Near-optimal fully dynamic densest subgraph. 181-193 - David Wajc
Rounding dynamic matchings against an adaptive adversary. 194-207
Session 2B: Boolean Function Analysis and Algebraic Complexity
- Ronen Eldan, Renan Gross:
Concentration on the Boolean hypercube via pathwise stochastic analysis. 208-221 - Yuval Filmus, Noam Lifshitz
AND testing and robust judgement aggregation. 222-233 - Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini
XOR lemmas for resilient functions against polynomials. 234-246 - Shachar Lovett, Kewen Wu, Jiapeng Zhang:
Decision list compression by mild random restrictions. 247-254
Session 2C: Cryptography
- Ryan Amos, Marios Georgiou, Aggelos Kiayias, Mark Zhandry:
One-shot signatures and applications to hybrid quantum/classical authentication. 255-268 - Nir Bitansky, Omri Shmueli:
Post-quantum zero knowledge in constant rounds. 269-279 - Benny Applebaum, Amos Beimel
Better secret sharing via robust conditional disclosure of secrets. 280-293 - Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, Vinod Vaikuntanathan:
Data structures meet cryptography: 3SUM with preprocessing. 294-307
Session 3A: Distributed and Parallel Algorithms II
- Jason Li:
Faster parallel algorithm for approximate shortest path. 308-321 - Alexandr Andoni, Clifford Stein, Peilin Zhong:
Parallel approximate undirected shortest paths via low hop emulators. 322-335 - Nairen Cao, Jeremy T. Fineman, Katina Russell:
Efficient construction of directed hopsets and parallel approximate shortest paths. 336-349 - Václav Rozhon, Mohsen Ghaffari:
Polylogarithmic-time deterministic network decomposition and distributed derandomization. 350-363 - Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak
Walking randomly, massively, and efficiently. 364-377
Session 3B: Quantum (Inspired) Computation
- Aram W. Harrow
Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems. 378-386 - Nai-Hui Chia, András Gilyén, Tongyang Li
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. 387-400 - Dmitry Gavinsky:
Bare quantum simultaneity versus classical interactivity in communication complexity. 401-411 - Andris Ambainis, András Gilyén, Stacey Jeffery
Quadratic speedup for finding marked vertices by quantum walks. 412-424
Session 3C: Privacy and Fairness
- Alexander Edmonds, Aleksandar Nikolov, Jonathan R. Ullman:
The power of factorization mechanisms in local and central differential privacy. 425-438 - Vitaly Feldman, Tomer Koren, Kunal Talwar:
Private stochastic convex optimization: optimal rates in linear time. 439-449 - Yuval Dagan
Interaction is necessary for distributed learning with privacy or communication constraints. 450-462 - Zhihao Jiang, Kamesh Munagala
Approximately stable committee selection. 463-472
Session 4A: Graph Theory and Algorithms
- Anupam Gupta
The Karger-Stein algorithm is optimal for k-cut. 473-484 - David R. Karger
A phase transition and a quadratic time unbiased estimator for network reliability. 485-495 - Sagnik Mukhopadhyay
Weighted min-cut: sequential, cut-query, and streaming algorithms. 496-509 - Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
Explicit near-Ramanujan graphs of every degree. 510-523
Session 4B: Coding and Information Theory
- Venkatesan Guruswami, Bernhard Haeupler
Optimally resilient codes for list-decoding from insertions and deletions. 524-537 - Chong Shangguan, Itzhak Tamo:
Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius. 538-551 - Venkatesan Guruswami, Andrii Riazanov, Min Ye:
Arikan meets Shannon: polar codes with near-optimal convergence to channel capacity. 552-564 - Klim Efremenko
Interactive error resilience beyond 2/7. 565-578
Session 4C: Learning and Testing
- Rong Ge, Holden Lee, Jianfeng Lu
Estimating normalizing constants for log-concave distributions: algorithms and lower bounds. 579-586 - Sitan Chen, Jerry Li, Zhao Song:
Learning mixtures of linear regressions in subexponential time via Fourier moments. 587-600 - Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, Nilesh Tripuraneni:
Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond. 601-609 - Xue Chen, Anindya De, Rocco A. Servedio
Testing noisy linear functions for sparsity. 610-623
Session 5A: Best Paper
- Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang:
Improved bounds for the sunflower lemma. 624-630
Session 5B: Best Student Paper
- Siddharth Bhandari, Sayantan Chakraborty:
Improved bounds for perfect sampling of k-colorings in graphs. 631-642
Session 6A: Strings and Sequences
- Timothy M. Chan, Shay Golan, Tomasz Kociumaka
Approximating text-to-pattern Hamming distances. 643-656 - Elazar Goldenberg, Aviad Rubinstein, Barna Saha:
Does preprocessing help in fast sequence comparisons? 657-670 - Michael Mitzenmacher, Saeed Seddighin
Dynamic algorithms for LIS and distance to monotonicity. 671-684 - Joshua Brakensiek, Aviad Rubinstein:
Constant-factor approximation of near-linear edit distance in near-linear time. 685-698 - Michal Koucký
Constant factor approximations to edit distance on far input pairs in nearly linear time. 699-712
Session 6B: Complexity I
- Christian Ikenmeyer, Umangathan Kandasamy:
Implementing geometric complexity theory: on the separation of orbit closures via symmetries. 713-726 - Pierre-Étienne Meunier, Damien Regnault, Damien Woods
The program-size complexity of self-assembled paths. 727-737 - Christian Borgs
Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures. 738-751 - James Cook, Ian Mertz
Catalytic approaches to the tree evaluation problem. 752-760
Session 6C: Optimization
- Daniel Dadush, Sophie Huiberts, Bento Natura, László A. Végh
A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix. 761-774 - Jan van den Brand
Solving tall dense linear programs in nearly linear time. 775-788 - Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, Kevin Tian:
Positive semidefinite programming: mixed, parallel, and width-independent. 789-802 - Yang P. Liu, Aaron Sidford:
Faster energy maximization for faster maximum flow. 803-814
Session 7A: Approximation Algorithms
- Jaroslaw Byrka
Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. 815-825 - Lap Chi Lau, Hong Zhou:
A spectral approach to network design. 826-839 - Sidhanth Mohanty, Prasad Raghavendra, Jeff Xu:
Lifting sum-of-squares lower bounds: degree-2 to degree-4. 840-853 - Weiming Feng, Heng Guo, Yitong Yin, Chihao Zhang:
Fast sampling and counting k-SAT solutions in the local lemma regime. 854-867
Session 7B: Quantum Computation
- Anurag Anshu, Itai Arad, David Gosset:
Entanglement subvolume law for 2d frustration-free spin systems. 868-874 - Daniel Grier, Luke Schaeffer:
Interactive shallow Clifford circuits: quantum advantage against NC¹ and beyond. 875-888 - Matthew Coudron, Sanketh Menda:
Computations with greater quantum depth are strictly more powerful (relative to an oracle). 889-901 - Nai-Hui Chia, Kai-Min Chung
On the need for large quantum depth. 902-915 - Carl A. Miller:
The impossibility of efficient quantum weak coin flipping. 916-929
Session 7C: Continuous Optimization / Machine Learning
- Jonathan Leake, Nisheeth K. Vishnoi:
On the computability of continuous maximum entropy distributions with applications. 930-943 - Haotian Jiang, Yin Tat Lee, Zhao Song, Sam Chiu-wai Wong:
An improved cutting plane method for convex optimization, convex-concave games, and its applications. 944-953 - Vitaly Feldman:
Does learning require memorization? a short tale about a long tail. 954-959 - Sitan Chen, Jerry Li, Ankur Moitra:
Efficiently learning structured distributions from untrusted batches. 960-973
Session 8A: Fine-Grained Complexity
- Bartlomiej Dudek
All non-trivial variants of 3-LDT are equivalent. 974-981 - Karl Bringmann, Vasileios Nakos:
Top-k-convolution and the quest for near-linear output-sensitive subset sum. 982-995 - Amir Abboud, Vincent Cohen-Addad, Philip N. Klein:
New hardness results for planar graph problems in p and an algorithm for sparsest cut. 996-1009 - Shiri Chechik, Yang P. Liu, Omer Rotem, Aaron Sidford:
Constant girth approximation for directed graphs in subquadratic time. 1010-1023
Session 8B: Complexity Theory II
- Dhiraj Holden, Yael Tauman Kalai:
Non-signaling proofs with o(√ log n) provers are in PSPACE. 1024-1037 - Shuichi Hirahara:
Unexpected hardness results for Kolmogorov complexity under uniform reductions. 1038-1051 - Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis
Smoothed complexity of local max-cut and binary max-CSP. 1052-1065 - Cristobal Rojas
How to lose at Monte Carlo: a simple dynamical system whose typical statistical behavior is non-computable. 1066-1072
Session 8C: Algorithmic Game Theory and Matchings
- Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg
Separating the communication complexity of truthful and non-truthful combinatorial auctions. 1073-1085 - George Christodoulou
On the Nisan-Ronen conjecture for submodular valuations. 1086-1096 - Zhihao Gavin Tang, Xiaowei Wu
Towards a better understanding of randomized greedy matching. 1097-1110 - Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi:
Stochastic matching with few queries: (1-ε) approximation. 1111-1124
Session 9A: Online Algorithms
- Anupam Gupta
Caching with time windows. 1125-1138 - Nikhil Bansal, Haotian Jiang, Sahil Singla
Online vector balancing and geometric discrepancy. 1139-1152 - Zhiyi Huang
Online primal dual meets online matching with stochastic rewards: configuration LP to the rescue. 1153-1164 - Marcin Bienkowski
Unbounded lower bound for k-server against weak adversaries. 1165-1169
Session 9B: Randomness in Computing
- Ryan O'Donnell, Rocco A. Servedio
Fooling Gaussian PTFs via local hyperconcentration. 1170-1183 - Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li:
Extractors for adversarial sources via extremal hypergraphs. 1184-1197 - Vedat Levi Alev
Improved analysis of higher order random walks and applications. 1198-1211 - Aditi Laddha, Yin Tat Lee, Santosh S. Vempala:
Strong self-concordance and sampling. 1212-1222
Session 9C: Streaming, Sketching, and Big Data
- John Kallaugher, Eric Price:
Separations and equivalences between turnstile streaming and linear sketching. 1223-1236 - Sepehr Assadi, Chen Wang
Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits. 1237-1250 - Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, Samson Zhou:
Non-adaptive adaptive sampling on turnstile streams. 1251-1264 - Anders Aamand, Jakob Bæk Tejs Knudsen, Mathias Bæk Tejs Knudsen, Peter Michael Reichstein Rasmussen
Fast hashing with strong concentration bounds. 1265-1278
Session 10A: Graph Theory and Fixed-Parameter Tractability
- Kai-Yuan Lai, Hsueh-I Lu, Mikkel Thorup
Three-in-a-tree in near linear time. 1279-1292 - Jesper Nederlof:
Detecting and counting small patterns in planar graphs in subexponential parameterized time. 1293-1306 - Daniel Lokshtanov, Pranabendu Misra, Michal Pilipczuk, Saket Saurabh, Meirav Zehavi:
An exponential time parameterized algorithm for planar disjoint paths. 1307-1316 - Fedor V. Fomin
Hitting topological minors is FPT. 1317-1326
Session 10B: Complexity Theory III
- Lijie Chen, Hanlin Ren
Strong average-case lower bounds from non-trivial derandomization. 1327-1334 - Lijie Chen, Ce Jin, R. Ryan Williams:
Sharp threshold results for computational complexity. 1335-1348 - Srikanth Srinivasan
A robust version of Hegedus's lemma, with applications. 1349-1362 - Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, Rico Zenklusen:
The one-way communication complexity of submodular maximization with applications to streaming and robustness. 1363-1374
Session 10C: Data Structures / Big Data
- Shiri Chechik, Sarel Cohen:
Distance sensitivity oracles with subcubic preprocessing time and fast query time. 1375-1388 - Huacheng Yu:
Nearly optimal static Las Vegas succinct dictionary. 1389-1401 - Mingmou Liu
Lower bound for succinct range minimum query. 1402-1415 - Lingxiao Huang
Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal. 1416-1429
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-11-14 20:49 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: