STOC '20: "Fast Hashing with Strong Concentration ..."
Fast Hashing with Strong Concentration Bounds
Anders Aamand, Jakob Bæk Tejs Knudsen, Mathias Bæk Tejs Knudsen, Peter Michael Reichstein Rasmussen, and Mikkel Thorup
(University of Copenhagen, Denmark; SupWiz, Denmark)
@InProceedings{STOC20p1401,
author = {Anders Aamand and Jakob Bæk Tejs Knudsen and Mathias Bæk Tejs Knudsen and Peter Michael Reichstein Rasmussen and Mikkel Thorup},
title = {Fast Hashing with Strong Concentration Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1401-1400},
doi = {10.1145/3357713.3384259},
year = {2020},
}
Publisher's Version
STOC '20: "New Hardness Results for Planar ..."
New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut
Amir Abboud, Vincent Cohen-Addad, and Philip N. Klein
(IBM, USA; CNRS, France; UPMC, France; Brown University, USA)
@InProceedings{STOC20p1107,
author = {Amir Abboud and Vincent Cohen-Addad and Philip N. Klein},
title = {New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1107-1106},
doi = {10.1145/3357713.3384310},
year = {2020},
}
Publisher's Version
STOC '20: "Semi-algebraic Proofs, IPS ..."
Semi-algebraic Proofs, IPS Lower Bounds, and the τ-Conjecture: Can a Natural Number Be Negative?
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, and Iddo Tzameret
(Steklov Institute of Mathematics at St. Petersburg, Russia; St. Petersburg State University, Russia; CNRS, France; University of Lille, France; Royal Holloway University of London, UK)
@InProceedings{STOC20p57,
author = {Yaroslav Alekseev and Dima Grigoriev and Edward A. Hirsch and Iddo Tzameret},
title = {Semi-algebraic Proofs, IPS Lower Bounds, and the τ-Conjecture: Can a Natural Number Be Negative?},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {57-56},
doi = {10.1145/3357713.3384245},
year = {2020},
}
Publisher's Version
STOC '20: "Improved Analysis of Higher ..."
Improved Analysis of Higher Order Random Walks and Applications
Vedat Levi Alev and Lap Chi Lau
(University of Waterloo, Canada)
@InProceedings{STOC20p1331,
author = {Vedat Levi Alev and Lap Chi Lau},
title = {Improved Analysis of Higher Order Random Walks and Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1331-1330},
doi = {10.1145/3357713.3384317},
year = {2020},
}
Publisher's Version
STOC '20: "Improved Bounds for the Sunflower ..."
Improved Bounds for the Sunflower Lemma
Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang
(Princeton University, USA; University of California at San Diego, USA; Peking University, China; Harvard University, USA)
@InProceedings{STOC20p687,
author = {Ryan Alweiss and Shachar Lovett and Kewen Wu and Jiapeng Zhang},
title = {Improved Bounds for the Sunflower Lemma},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {687-686},
doi = {10.1145/3357713.3384234},
year = {2020},
}
Publisher's Version
STOC '20: "Quadratic Speedup for Finding ..."
Quadratic Speedup for Finding Marked Vertices by Quantum Walks
Andris Ambainis, András Gilyén, Stacey Jeffery, and Martins Kokainis
(University of Latvia, Latvia; QuSoft, Netherlands; CWI, Netherlands; University of Amsterdam, Netherlands)
@InProceedings{STOC20p449,
author = {Andris Ambainis and András Gilyén and Stacey Jeffery and Martins Kokainis},
title = {Quadratic Speedup for Finding Marked Vertices by Quantum Walks},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {449-448},
doi = {10.1145/3357713.3384252},
year = {2020},
}
Publisher's Version
STOC '20: "Breaching the 2-Approximation ..."
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
Jarosław Byrka, Fabrizio Grandoni, and Afrouz Jabal Ameli
(University of Wrocław, Poland; IDSIA, Switzerland)
@InProceedings{STOC20p897,
author = {Jarosław Byrka and Fabrizio Grandoni and Afrouz Jabal Ameli},
title = {Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {897-896},
doi = {10.1145/3357713.3384301},
year = {2020},
}
Publisher's Version
STOC '20: "One-Shot Signatures and Applications ..."
One-Shot Signatures and Applications to Hybrid Quantum/Classical Authentication
Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry
(Princeton University, USA; City University of New York, USA; University of Edinburgh, UK)
@InProceedings{STOC20p281,
author = {Ryan Amos and Marios Georgiou and Aggelos Kiayias and Mark Zhandry},
title = {One-Shot Signatures and Applications to Hybrid Quantum/Classical Authentication},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {281-280},
doi = {10.1145/3357713.3384304},
year = {2020},
}
Publisher's Version
STOC '20: "Parallel Approximate Undirected ..."
Parallel Approximate Undirected Shortest Paths via Low Hop Emulators
Alexandr Andoni, Clifford Stein, and Peilin Zhong
(Columbia University, USA)
@InProceedings{STOC20p351,
author = {Alexandr Andoni and Clifford Stein and Peilin Zhong},
title = {Parallel Approximate Undirected Shortest Paths via Low Hop Emulators},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {351-350},
doi = {10.1145/3357713.3384321},
year = {2020},
}
Publisher's Version
STOC '20: "Entanglement Subvolume Law ..."
Entanglement Subvolume Law for 2D Frustration-Free Spin Systems
Anurag Anshu, Itai Arad, and David Gosset
(University of Waterloo, Canada; Perimeter Institute for Theoretical Physics, Canada; Technion, Israel)
@InProceedings{STOC20p953,
author = {Anurag Anshu and Itai Arad and David Gosset},
title = {Entanglement Subvolume Law for 2D Frustration-Free Spin Systems},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {953-952},
doi = {10.1145/3357713.3384292},
year = {2020},
}
Publisher's Version
STOC '20: "Better Secret Sharing via ..."
Better Secret Sharing via Robust Conditional Disclosure of Secrets
Benny Applebaum, Amos Beimel, Oded Nir, and Naty Peter
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel)
@InProceedings{STOC20p309,
author = {Benny Applebaum and Amos Beimel and Oded Nir and Naty Peter},
title = {Better Secret Sharing via Robust Conditional Disclosure of Secrets},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {309-308},
doi = {10.1145/3357713.3384293},
year = {2020},
}
Publisher's Version
STOC '20: "Entanglement Subvolume Law ..."
Entanglement Subvolume Law for 2D Frustration-Free Spin Systems
Anurag Anshu, Itai Arad, and David Gosset
(University of Waterloo, Canada; Perimeter Institute for Theoretical Physics, Canada; Technion, Israel)
@InProceedings{STOC20p953,
author = {Anurag Anshu and Itai Arad and David Gosset},
title = {Entanglement Subvolume Law for 2D Frustration-Free Spin Systems},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {953-952},
doi = {10.1145/3357713.3384292},
year = {2020},
}
Publisher's Version
STOC '20: "Separating the Communication ..."
Separating the Communication Complexity of Truthful and Non-truthful Combinatorial Auctions
Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, and S. Matthew Weinberg
(Rutgers University, USA; Princeton University, USA)
@InProceedings{STOC20p1191,
author = {Sepehr Assadi and Hrishikesh Khandeparkar and Raghuvansh R. Saxena and S. Matthew Weinberg},
title = {Separating the Communication Complexity of Truthful and Non-truthful Combinatorial Auctions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1191-1190},
doi = {10.1145/3357713.3384267},
year = {2020},
}
Publisher's Version
STOC '20: "Exploration with Limited Memory: ..."
Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-armed Bandits
Sepehr Assadi and Chen Wang
(Rutgers University, USA)
@InProceedings{STOC20p1373,
author = {Sepehr Assadi and Chen Wang},
title = {Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-armed Bandits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1373-1372},
doi = {10.1145/3357713.3384341},
year = {2020},
}
Publisher's Version
STOC '20: "A Lower Bound for Parallel ..."
A Lower Bound for Parallel Submodular Minimization
Eric Balkanski and Yaron Singer
(Harvard University, USA)
@InProceedings{STOC20p141,
author = {Eric Balkanski and Yaron Singer},
title = {A Lower Bound for Parallel Submodular Minimization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {141-140},
doi = {10.1145/3357713.3384287},
year = {2020},
}
Publisher's Version
STOC '20: "Online Vector Balancing and ..."
Online Vector Balancing and Geometric Discrepancy
Nikhil Bansal, Haotian Jiang, Sahil Singla, and Makrand Sinha
(Eindhoven University of Technology, Netherlands; CWI, Netherlands; University of Washington, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC20p1261,
author = {Nikhil Bansal and Haotian Jiang and Sahil Singla and Makrand Sinha},
title = {Online Vector Balancing and Geometric Discrepancy},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1261-1260},
doi = {10.1145/3357713.3384280},
year = {2020},
}
Publisher's Version
STOC '20: "Stochastic Matching with Few ..."
Stochastic Matching with Few Queries: (1-ε) Approximation
Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi
(University of Maryland, USA)
@InProceedings{STOC20p1233,
author = {Soheil Behnezhad and Mahsa Derakhshan and MohammadTaghi Hajiaghayi},
title = {Stochastic Matching with Few Queries: (1-ε) Approximation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1233-1232},
doi = {10.1145/3357713.3384340},
year = {2020},
}
Publisher's Version
STOC '20: "Better Secret Sharing via ..."
Better Secret Sharing via Robust Conditional Disclosure of Secrets
Benny Applebaum, Amos Beimel, Oded Nir, and Naty Peter
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel)
@InProceedings{STOC20p309,
author = {Benny Applebaum and Amos Beimel and Oded Nir and Naty Peter},
title = {Better Secret Sharing via Robust Conditional Disclosure of Secrets},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {309-308},
doi = {10.1145/3357713.3384293},
year = {2020},
}
Publisher's Version
STOC '20: "Contention Resolution without ..."
Contention Resolution without Collision Detection
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, and Seth Pettie
(Stony Brook University, USA; Bar-Ilan University, Israel; Massachusetts Institute of Technology, USA; University of Michigan, USA)
@InProceedings{STOC20p113,
author = {Michael A. Bender and Tsvi Kopelowitz and William Kuszmaul and Seth Pettie},
title = {Contention Resolution without Collision Detection},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {113-112},
doi = {10.1145/3357713.3384305},
year = {2020},
}
Publisher's Version
STOC '20: "Optimal Time and Space Leader ..."
Optimal Time and Space Leader Election in Population Protocols
Petra Berenbrink, George Giakkoupis, and Peter Kling
(University of Hamburg, Germany; Inria, France; University of Rennes, France; CNRS, France; IRISA, France)
@InProceedings{STOC20p127,
author = {Petra Berenbrink and George Giakkoupis and Peter Kling},
title = {Optimal Time and Space Leader Election in Population Protocols},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {127-126},
doi = {10.1145/3357713.3384312},
year = {2020},
}
Publisher's Version
STOC '20: "Improved Bounds for Perfect ..."
Improved Bounds for Perfect Sampling of k-Colorings in Graphs
Siddharth Bhandari and Sayantan Chakraborty
(Tata Institute of Fundamental Research, India)
@InProceedings{STOC20p701,
author = {Siddharth Bhandari and Sayantan Chakraborty},
title = {Improved Bounds for Perfect Sampling of k-Colorings in Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {701-700},
doi = {10.1145/3357713.3384244},
year = {2020},
}
Publisher's Version
STOC '20: "Unbounded Lower Bound for ..."
Unbounded Lower Bound for k-Server against Weak Adversaries
Marcin Bienkowski, Jarosław Byrka, Christian Coester, and Łukasz Jeż
(University of Wrocław, Poland; CWI, Netherlands)
@InProceedings{STOC20p1289,
author = {Marcin Bienkowski and Jarosław Byrka and Christian Coester and Łukasz Jeż},
title = {Unbounded Lower Bound for k-Server against Weak Adversaries},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1289-1288},
doi = {10.1145/3357713.3384306},
year = {2020},
}
Publisher's Version
STOC '20: "Post-quantum Zero Knowledge ..."
Post-quantum Zero Knowledge in Constant Rounds
Nir Bitansky and Omri Shmueli
(Tel Aviv University, Israel)
@InProceedings{STOC20p295,
author = {Nir Bitansky and Omri Shmueli},
title = {Post-quantum Zero Knowledge in Constant Rounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {295-294},
doi = {10.1145/3357713.3384324},
year = {2020},
}
Publisher's Version
STOC '20: "Efficient Sampling and Counting ..."
Efficient Sampling and Counting Algorithms for the Potts Model on ℤᵈ at All Temperatures
Christian Borgs, Jennifer Chayes, Tyler Helmuth, Will Perkins, and Prasad Tetali
(University of California at Berkeley, USA; University of Bristol, UK; University of Illinois at Chicago, USA; Georgia Institute of Technology, USA)
@InProceedings{STOC20p813,
author = {Christian Borgs and Jennifer Chayes and Tyler Helmuth and Will Perkins and Prasad Tetali},
title = {Efficient Sampling and Counting Algorithms for the Potts Model on ℤᵈ at All Temperatures},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {813-812},
doi = {10.1145/3357713.3384271},
year = {2020},
}
Publisher's Version
STOC '20: "Constant-Factor Approximation ..."
Constant-Factor Approximation of Near-Linear Edit Distance in Near-Linear Time
Joshua Brakensiek and Aviad Rubinstein
(Stanford University, USA)
@InProceedings{STOC20p757,
author = {Joshua Brakensiek and Aviad Rubinstein},
title = {Constant-Factor Approximation of Near-Linear Edit Distance in Near-Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {757-756},
doi = {10.1145/3357713.3384282},
year = {2020},
}
Publisher's Version
STOC '20: "Top-𝑘-Convolution and the ..."
Top-𝑘-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum
Karl Bringmann and Vasileios Nakos
(Saarland University, Germany; MPI-INF, Germany)
@InProceedings{STOC20p1093,
author = {Karl Bringmann and Vasileios Nakos},
title = {Top-𝑘-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1093-1092},
doi = {10.1145/3357713.3384308},
year = {2020},
}
Publisher's Version
STOC '20: "Unbounded Lower Bound for ..."
Unbounded Lower Bound for k-Server against Weak Adversaries
Marcin Bienkowski, Jarosław Byrka, Christian Coester, and Łukasz Jeż
(University of Wrocław, Poland; CWI, Netherlands)
@InProceedings{STOC20p1289,
author = {Marcin Bienkowski and Jarosław Byrka and Christian Coester and Łukasz Jeż},
title = {Unbounded Lower Bound for k-Server against Weak Adversaries},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1289-1288},
doi = {10.1145/3357713.3384306},
year = {2020},
}
Publisher's Version
STOC '20: "Breaching the 2-Approximation ..."
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
Jarosław Byrka, Fabrizio Grandoni, and Afrouz Jabal Ameli
(University of Wrocław, Poland; IDSIA, Switzerland)
@InProceedings{STOC20p897,
author = {Jarosław Byrka and Fabrizio Grandoni and Afrouz Jabal Ameli},
title = {Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {897-896},
doi = {10.1145/3357713.3384301},
year = {2020},
}
Publisher's Version
STOC '20: "Efficient Construction of ..."
Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths
Nairen Cao, Jeremy T. Fineman, and Katina Russell
(Georgetown University, USA)
@InProceedings{STOC20p365,
author = {Nairen Cao and Jeremy T. Fineman and Katina Russell},
title = {Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {365-364},
doi = {10.1145/3357713.3384270},
year = {2020},
}
Publisher's Version
STOC '20: "Improved Bounds for Perfect ..."
Improved Bounds for Perfect Sampling of k-Colorings in Graphs
Siddharth Bhandari and Sayantan Chakraborty
(Tata Institute of Fundamental Research, India)
@InProceedings{STOC20p701,
author = {Siddharth Bhandari and Sayantan Chakraborty},
title = {Improved Bounds for Perfect Sampling of k-Colorings in Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {701-700},
doi = {10.1145/3357713.3384244},
year = {2020},
}
Publisher's Version
STOC '20: "Approximating Text-to-Pattern ..."
Approximating Text-to-Pattern Hamming Distances
Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat
(University of Illinois at Urbana-Champaign, USA; Bar-Ilan University, Israel)
@InProceedings{STOC20p715,
author = {Timothy M. Chan and Shay Golan and Tomasz Kociumaka and Tsvi Kopelowitz and Ely Porat},
title = {Approximating Text-to-Pattern Hamming Distances},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {715-714},
doi = {10.1145/3357713.3384266},
year = {2020},
}
Publisher's Version
STOC '20: "Extractors for Adversarial ..."
Extractors for Adversarial Sources via Extremal Hypergraphs
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, and Xin Li
(Cornell University, USA; Carnegie Mellon University, USA; Johns Hopkins University, USA)
@InProceedings{STOC20p1317,
author = {Eshan Chattopadhyay and Jesse Goodman and Vipul Goyal and Xin Li},
title = {Extractors for Adversarial Sources via Extremal Hypergraphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1317-1316},
doi = {10.1145/3357713.3384339},
year = {2020},
}
Publisher's Version
STOC '20: "XOR Lemmas for Resilient Functions ..."
XOR Lemmas for Resilient Functions against Polynomials
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, and David Zuckerman
(Cornell University, USA; Ohio State University, USA; Carnegie Mellon University, USA; University of California at San Diego, USA; University of Texas at Austin, USA)
@InProceedings{STOC20p253,
author = {Eshan Chattopadhyay and Pooya Hatami and Kaave Hosseini and Shachar Lovett and David Zuckerman},
title = {XOR Lemmas for Resilient Functions against Polynomials},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {253-252},
doi = {10.1145/3357713.3384242},
year = {2020},
}
Publisher's Version
STOC '20: "Efficient Sampling and Counting ..."
Efficient Sampling and Counting Algorithms for the Potts Model on ℤᵈ at All Temperatures
Christian Borgs, Jennifer Chayes, Tyler Helmuth, Will Perkins, and Prasad Tetali
(University of California at Berkeley, USA; University of Bristol, UK; University of Illinois at Chicago, USA; Georgia Institute of Technology, USA)
@InProceedings{STOC20p813,
author = {Christian Borgs and Jennifer Chayes and Tyler Helmuth and Will Perkins and Prasad Tetali},
title = {Efficient Sampling and Counting Algorithms for the Potts Model on ℤᵈ at All Temperatures},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {813-812},
doi = {10.1145/3357713.3384271},
year = {2020},
}
Publisher's Version
STOC '20: "Constant Girth Approximation ..."
Constant Girth Approximation for Directed Graphs in Subquadratic Time
Shiri Chechik, Yang P. Liu, Omer Rotem, and Aaron Sidford
(Tel Aviv University, Israel; Stanford University, USA)
@InProceedings{STOC20p1121,
author = {Shiri Chechik and Yang P. Liu and Omer Rotem and Aaron Sidford},
title = {Constant Girth Approximation for Directed Graphs in Subquadratic Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1121-1120},
doi = {10.1145/3357713.3384330},
year = {2020},
}
Publisher's Version
STOC '20: "Distance Sensitivity Oracles ..."
Distance Sensitivity Oracles with Subcubic Preprocessing Time and Fast Query Time
Shiri Chechik and Sarel Cohen
(Tel Aviv University, Israel)
@InProceedings{STOC20p1527,
author = {Shiri Chechik and Sarel Cohen},
title = {Distance Sensitivity Oracles with Subcubic Preprocessing Time and Fast Query Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1527-1526},
doi = {10.1145/3357713.3384253},
year = {2020},
}
Publisher's Version
STOC '20: "Strong Average-Case Lower ..."
Strong Average-Case Lower Bounds from Non-trivial Derandomization
Lijie Chen and Hanlin Ren
(Massachusetts Institute of Technology, USA; Tsinghua University, China)
@InProceedings{STOC20p1471,
author = {Lijie Chen and Hanlin Ren},
title = {Strong Average-Case Lower Bounds from Non-trivial Derandomization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1471-1470},
doi = {10.1145/3357713.3384279},
year = {2020},
}
Publisher's Version
STOC '20: "Sharp Threshold Results for ..."
Sharp Threshold Results for Computational Complexity
Lijie Chen, Ce Jin, and R. Ryan Williams
(Massachusetts Institute of Technology, USA; Tsinghua University, China)
@InProceedings{STOC20p1485,
author = {Lijie Chen and Ce Jin and R. Ryan Williams},
title = {Sharp Threshold Results for Computational Complexity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1485-1484},
doi = {10.1145/3357713.3384283},
year = {2020},
}
Publisher's Version
STOC '20: "Efficiently Learning Structured ..."
Efficiently Learning Structured Distributions from Untrusted Batches
Sitan Chen, Jerry Li, and Ankur Moitra
(Massachusetts Institute of Technology, USA; Microsoft Research, USA)
@InProceedings{STOC20p1065,
author = {Sitan Chen and Jerry Li and Ankur Moitra},
title = {Efficiently Learning Structured Distributions from Untrusted Batches},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1065-1064},
doi = {10.1145/3357713.3384337},
year = {2020},
}
Publisher's Version
STOC '20: "Learning Mixtures of Linear ..."
Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
Sitan Chen, Jerry Li, and Zhao Song
(Massachusetts Institute of Technology, USA; Microsoft Research, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC20p645,
author = {Sitan Chen and Jerry Li and Zhao Song},
title = {Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {645-644},
doi = {10.1145/3357713.3384333},
year = {2020},
}
Publisher's Version
STOC '20: "Smoothed Complexity of Local ..."
Smoothed Complexity of Local Max-Cut and Binary Max-CSP
Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, and Xinzhi Zhang
(Columbia University, USA; Tsinghua University, China)
@InProceedings{STOC20p1163,
author = {Xi Chen and Chenghao Guo and Emmanouil V. Vlatakis-Gkaragkounis and Mihalis Yannakakis and Xinzhi Zhang},
title = {Smoothed Complexity of Local Max-Cut and Binary Max-CSP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1163-1162},
doi = {10.1145/3357713.3384325},
year = {2020},
}
Publisher's Version
STOC '20: "Testing Noisy Linear Functions ..."
Testing Noisy Linear Functions for Sparsity
Xue Chen, Anindya De, and Rocco A. Servedio
(Northwestern University, USA; University of Pennsylvania, USA; Columbia University, USA)
@InProceedings{STOC20p673,
author = {Xue Chen and Anindya De and Rocco A. Servedio},
title = {Testing Noisy Linear Functions for Sparsity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {673-672},
doi = {10.1145/3357713.3384239},
year = {2020},
}
Publisher's Version
STOC '20: "Algorithms for Heavy-Tailed ..."
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, and Nilesh Tripuraneni
(University of California at Berkeley, USA)
@InProceedings{STOC20p659,
author = {Yeshwanth Cherapanamjeri and Samuel B. Hopkins and Tarun Kathuria and Prasad Raghavendra and Nilesh Tripuraneni},
title = {Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {659-658},
doi = {10.1145/3357713.3384329},
year = {2020},
}
Publisher's Version
STOC '20: "Sampling-Based Sublinear Low-Rank ..."
Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang
(University of Texas at Austin, USA; California Institute of Technology, USA; University of Maryland, USA; University of Washington, USA)
@InProceedings{STOC20p421,
author = {Nai-Hui Chia and András Gilyén and Tongyang Li and Han-Hsuan Lin and Ewin Tang and Chunhao Wang},
title = {Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {421-420},
doi = {10.1145/3357713.3384314},
year = {2020},
}
Publisher's Version
STOC '20: "On the Need for Large Quantum ..."
On the Need for Large Quantum Depth
Nai-Hui Chia, Kai-Min Chung, and Ching-Yi Lai
(University of Texas at Austin, USA; Academia Sinica, Taiwan; National Chiao Tung University, Taiwan)
@InProceedings{STOC20p995,
author = {Nai-Hui Chia and Kai-Min Chung and Ching-Yi Lai},
title = {On the Need for Large Quantum Depth},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {995-994},
doi = {10.1145/3357713.3384291},
year = {2020},
}
Publisher's Version
STOC '20: "On the Nisan-Ronen Conjecture ..."
On the Nisan-Ronen Conjecture for Submodular Valuations
George Christodoulou, Elias Koutsoupias, and Annamária Kovács
(University of Liverpool, UK; University of Oxford, UK; Goethe University Frankfurt, Germany)
@InProceedings{STOC20p1205,
author = {George Christodoulou and Elias Koutsoupias and Annamária Kovács},
title = {On the Nisan-Ronen Conjecture for Submodular Valuations},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1205-1204},
doi = {10.1145/3357713.3384299},
year = {2020},
}
Publisher's Version
STOC '20: "On the Need for Large Quantum ..."
On the Need for Large Quantum Depth
Nai-Hui Chia, Kai-Min Chung, and Ching-Yi Lai
(University of Texas at Austin, USA; Academia Sinica, Taiwan; National Chiao Tung University, Taiwan)
@InProceedings{STOC20p995,
author = {Nai-Hui Chia and Kai-Min Chung and Ching-Yi Lai},
title = {On the Need for Large Quantum Depth},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {995-994},
doi = {10.1145/3357713.3384291},
year = {2020},
}
Publisher's Version
STOC '20: "Unbounded Lower Bound for ..."
Unbounded Lower Bound for k-Server against Weak Adversaries
Marcin Bienkowski, Jarosław Byrka, Christian Coester, and Łukasz Jeż
(University of Wrocław, Poland; CWI, Netherlands)
@InProceedings{STOC20p1289,
author = {Marcin Bienkowski and Jarosław Byrka and Christian Coester and Łukasz Jeż},
title = {Unbounded Lower Bound for k-Server against Weak Adversaries},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1289-1288},
doi = {10.1145/3357713.3384306},
year = {2020},
}
Publisher's Version
STOC '20: "Distance Sensitivity Oracles ..."
Distance Sensitivity Oracles with Subcubic Preprocessing Time and Fast Query Time
Shiri Chechik and Sarel Cohen
(Tel Aviv University, Israel)
@InProceedings{STOC20p1527,
author = {Shiri Chechik and Sarel Cohen},
title = {Distance Sensitivity Oracles with Subcubic Preprocessing Time and Fast Query Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1527-1526},
doi = {10.1145/3357713.3384253},
year = {2020},
}
Publisher's Version
STOC '20: "New Hardness Results for Planar ..."
New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut
Amir Abboud, Vincent Cohen-Addad, and Philip N. Klein
(IBM, USA; CNRS, France; UPMC, France; Brown University, USA)
@InProceedings{STOC20p1107,
author = {Amir Abboud and Vincent Cohen-Addad and Philip N. Klein},
title = {New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1107-1106},
doi = {10.1145/3357713.3384310},
year = {2020},
}
Publisher's Version
STOC '20: "Catalytic Approaches to the ..."
Catalytic Approaches to the Tree Evaluation Problem
James Cook and Ian Mertz
(University of Toronto, Canada)
@InProceedings{STOC20p827,
author = {James Cook and Ian Mertz},
title = {Catalytic Approaches to the Tree Evaluation Problem},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {827-826},
doi = {10.1145/3357713.3384316},
year = {2020},
}
Publisher's Version
STOC '20: "Computations with Greater ..."
Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
Matthew Coudron and Sanketh Menda
(University of Waterloo, Canada; University of Maryland, USA; NIST, USA)
@InProceedings{STOC20p981,
author = {Matthew Coudron and Sanketh Menda},
title = {Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {981-980},
doi = {10.1145/3357713.3384269},
year = {2020},
}
Publisher's Version
STOC '20: "A Scaling-Invariant Algorithm ..."
A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix
Daniel Dadush, Sophie Huiberts, Bento Natura, and László A. Végh
(CWI, Netherlands; London School of Economics and Political Science, UK)
@InProceedings{STOC20p841,
author = {Daniel Dadush and Sophie Huiberts and Bento Natura and László A. Végh},
title = {A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {841-840},
doi = {10.1145/3357713.3384326},
year = {2020},
}
Publisher's Version
STOC '20: "Interaction Is Necessary for ..."
Interaction Is Necessary for Distributed Learning with Privacy or Communication Constraints
Yuval Dagan and Vitaly Feldman
(Massachusetts Institute of Technology, USA; Google Research, USA)
@InProceedings{STOC20p491,
author = {Yuval Dagan and Vitaly Feldman},
title = {Interaction Is Necessary for Distributed Learning with Privacy or Communication Constraints},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {491-490},
doi = {10.1145/3357713.3384315},
year = {2020},
}
Publisher's Version
STOC '20: "Testing Noisy Linear Functions ..."
Testing Noisy Linear Functions for Sparsity
Xue Chen, Anindya De, and Rocco A. Servedio
(Northwestern University, USA; University of Pennsylvania, USA; Columbia University, USA)
@InProceedings{STOC20p673,
author = {Xue Chen and Anindya De and Rocco A. Servedio},
title = {Testing Noisy Linear Functions for Sparsity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {673-672},
doi = {10.1145/3357713.3384239},
year = {2020},
}
Publisher's Version
STOC '20: "Stochastic Matching with Few ..."
Stochastic Matching with Few Queries: (1-ε) Approximation
Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi
(University of Maryland, USA)
@InProceedings{STOC20p1233,
author = {Soheil Behnezhad and Mahsa Derakhshan and MohammadTaghi Hajiaghayi},
title = {Stochastic Matching with Few Queries: (1-ε) Approximation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1233-1232},
doi = {10.1145/3357713.3384340},
year = {2020},
}
Publisher's Version
STOC '20: "All Non-trivial Variants of ..."
All Non-trivial Variants of 3-LDT Are Equivalent
Bartłomiej Dudek, Paweł Gawrychowski, and Tatiana Starikovskaya
(University of Wrocław, Poland; PSL University, France)
@InProceedings{STOC20p1079,
author = {Bartłomiej Dudek and Paweł Gawrychowski and Tatiana Starikovskaya},
title = {All Non-trivial Variants of 3-LDT Are Equivalent},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1079-1078},
doi = {10.1145/3357713.3384275},
year = {2020},
}
Publisher's Version
STOC '20: "The Power of Factorization ..."
The Power of Factorization Mechanisms in Local and Central Differential Privacy
Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman
(University of Toronto, Canada; Northeastern University, USA)
@InProceedings{STOC20p463,
author = {Alexander Edmonds and Aleksandar Nikolov and Jonathan Ullman},
title = {The Power of Factorization Mechanisms in Local and Central Differential Privacy},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {463-462},
doi = {10.1145/3357713.3384297},
year = {2020},
}
Publisher's Version
STOC '20: "Interactive Error Resilience ..."
Interactive Error Resilience beyond 2/7
Klim Efremenko, Gillat Kol, and Raghuvansh R. Saxena
(Ben-Gurion University of the Negev, Israel; Princeton University, USA)
@InProceedings{STOC20p617,
author = {Klim Efremenko and Gillat Kol and Raghuvansh R. Saxena},
title = {Interactive Error Resilience beyond 2/7},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {617-616},
doi = {10.1145/3357713.3384320},
year = {2020},
}
Publisher's Version
STOC '20: "Concentration on the Boolean ..."
Concentration on the Boolean Hypercube via Pathwise Stochastic Analysis
Ronen Eldan and Renan Gross
(Weizmann Institute of Science, Israel)
@InProceedings{STOC20p225,
author = {Ronen Eldan and Renan Gross},
title = {Concentration on the Boolean Hypercube via Pathwise Stochastic Analysis},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {225-224},
doi = {10.1145/3357713.3384230},
year = {2020},
}
Publisher's Version
STOC '20: "The One-Way Communication ..."
The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen
(University of Haifa, Israel; Google Research, Switzerland; EPFL, Switzerland; ETH Zurich, Switzerland)
@InProceedings{STOC20p1513,
author = {Moran Feldman and Ashkan Norouzi-Fard and Ola Svensson and Rico Zenklusen},
title = {The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1513-1512},
doi = {10.1145/3357713.3384286},
year = {2020},
}
Publisher's Version
STOC '20: "Does Learning Require Memorization? ..."
Does Learning Require Memorization? A Short Tale about a Long Tail
Vitaly Feldman
(Google Research, USA)
@InProceedings{STOC20p1051,
author = {Vitaly Feldman},
title = {Does Learning Require Memorization? A Short Tale about a Long Tail},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1051-1050},
doi = {10.1145/3357713.3384290},
year = {2020},
}
Publisher's Version
STOC '20: "Private Stochastic Convex ..."
Private Stochastic Convex Optimization: Optimal Rates in Linear Time
Vitaly Feldman, Tomer Koren, and Kunal Talwar
(Google Research, USA; Tel Aviv University, Israel; Google, Israel)
@InProceedings{STOC20p477,
author = {Vitaly Feldman and Tomer Koren and Kunal Talwar},
title = {Private Stochastic Convex Optimization: Optimal Rates in Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {477-476},
doi = {10.1145/3357713.3384335},
year = {2020},
}
Publisher's Version
STOC '20: "Interaction Is Necessary for ..."
Interaction Is Necessary for Distributed Learning with Privacy or Communication Constraints
Yuval Dagan and Vitaly Feldman
(Massachusetts Institute of Technology, USA; Google Research, USA)
@InProceedings{STOC20p491,
author = {Yuval Dagan and Vitaly Feldman},
title = {Interaction Is Necessary for Distributed Learning with Privacy or Communication Constraints},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {491-490},
doi = {10.1145/3357713.3384315},
year = {2020},
}
Publisher's Version
STOC '20: "Fast Sampling and Counting ..."
Fast Sampling and Counting 𝑘-SAT Solutions in the Local Lemma Regime
Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang
(Nanjing University, China; University of Edinburgh, UK; Shanghai Jiao Tong University, China)
@InProceedings{STOC20p939,
author = {Weiming Feng and Heng Guo and Yitong Yin and Chihao Zhang},
title = {Fast Sampling and Counting 𝑘-SAT Solutions in the Local Lemma Regime},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {939-938},
doi = {10.1145/3357713.3384255},
year = {2020},
}
Publisher's Version
STOC '20: "AND Testing and Robust Judgement ..."
AND Testing and Robust Judgement Aggregation
Yuval Filmus, Noam Lifshitz, Dor Minzer, and Elchanan Mossel
(Technion, Israel; Hebrew University of Jerusalem, Israel; Institute for Advanced Study at Princeton, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC20p239,
author = {Yuval Filmus and Noam Lifshitz and Dor Minzer and Elchanan Mossel},
title = {AND Testing and Robust Judgement Aggregation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {239-238},
doi = {10.1145/3357713.3384254},
year = {2020},
}
Publisher's Version
STOC '20: "Efficient Construction of ..."
Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths
Nairen Cao, Jeremy T. Fineman, and Katina Russell
(Georgetown University, USA)
@InProceedings{STOC20p365,
author = {Nairen Cao and Jeremy T. Fineman and Katina Russell},
title = {Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {365-364},
doi = {10.1145/3357713.3384270},
year = {2020},
}
Publisher's Version
STOC '20: "Hitting Topological Minors ..."
Hitting Topological Minors Is FPT
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi
(University of Bergen, Norway; University of California at Santa Barbara, USA; IIT Hyderabad, India; IMSc, India; Ben-Gurion University of the Negev, Israel)
@InProceedings{STOC20p1457,
author = {Fedor V. Fomin and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh and Meirav Zehavi},
title = {Hitting Topological Minors Is FPT},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1457-1456},
doi = {10.1145/3357713.3384318},
year = {2020},
}
Publisher's Version
STOC '20: "Bare Quantum Simultaneity ..."
Bare Quantum Simultaneity versus Classical Interactivity in Communication Complexity
Dmitry Gavinsky
(Czech Academy of Sciences, Czechia)
@InProceedings{STOC20p435,
author = {Dmitry Gavinsky},
title = {Bare Quantum Simultaneity versus Classical Interactivity in Communication Complexity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {435-434},
doi = {10.1145/3357713.3384243},
year = {2020},
}
Publisher's Version
STOC '20: "All Non-trivial Variants of ..."
All Non-trivial Variants of 3-LDT Are Equivalent
Bartłomiej Dudek, Paweł Gawrychowski, and Tatiana Starikovskaya
(University of Wrocław, Poland; PSL University, France)
@InProceedings{STOC20p1079,
author = {Bartłomiej Dudek and Paweł Gawrychowski and Tatiana Starikovskaya},
title = {All Non-trivial Variants of 3-LDT Are Equivalent},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1079-1078},
doi = {10.1145/3357713.3384275},
year = {2020},
}
Publisher's Version
STOC '20: "Estimating Normalizing Constants ..."
Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds
Rong Ge, Holden Lee, and Jianfeng Lu
(Duke University, USA)
@InProceedings{STOC20p631,
author = {Rong Ge and Holden Lee and Jianfeng Lu},
title = {Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {631-630},
doi = {10.1145/3357713.3384289},
year = {2020},
}
Publisher's Version
STOC '20: "One-Shot Signatures and Applications ..."
One-Shot Signatures and Applications to Hybrid Quantum/Classical Authentication
Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry
(Princeton University, USA; City University of New York, USA; University of Edinburgh, UK)
@InProceedings{STOC20p281,
author = {Ryan Amos and Marios Georgiou and Aggelos Kiayias and Mark Zhandry},
title = {One-Shot Signatures and Applications to Hybrid Quantum/Classical Authentication},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {281-280},
doi = {10.1145/3357713.3384304},
year = {2020},
}
Publisher's Version
STOC '20: "Polylogarithmic-Time Deterministic ..."
Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
Václav Rozhoň and Mohsen Ghaffari
(ETH Zurich, Switzerland)
@InProceedings{STOC20p379,
author = {Václav Rozhoň and Mohsen Ghaffari},
title = {Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {379-378},
doi = {10.1145/3357713.3384298},
year = {2020},
}
Publisher's Version
STOC '20: "An Improved Approximation ..."
An Improved Approximation Algorithm for TSP in the Half Integral Case
Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan
(University of Washington, USA)
@InProceedings{STOC20p29,
author = {Anna R. Karlin and Nathan Klein and Shayan Oveis Gharan},
title = {An Improved Approximation Algorithm for TSP in the Half Integral Case},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {29-28},
doi = {10.1145/3357713.3384273},
year = {2020},
}
Publisher's Version
STOC '20: "Optimal Time and Space Leader ..."
Optimal Time and Space Leader Election in Population Protocols
Petra Berenbrink, George Giakkoupis, and Peter Kling
(University of Hamburg, Germany; Inria, France; University of Rennes, France; CNRS, France; IRISA, France)
@InProceedings{STOC20p127,
author = {Petra Berenbrink and George Giakkoupis and Peter Kling},
title = {Optimal Time and Space Leader Election in Population Protocols},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {127-126},
doi = {10.1145/3357713.3384312},
year = {2020},
}
Publisher's Version
STOC '20: "Sampling-Based Sublinear Low-Rank ..."
Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang
(University of Texas at Austin, USA; California Institute of Technology, USA; University of Maryland, USA; University of Washington, USA)
@InProceedings{STOC20p421,
author = {Nai-Hui Chia and András Gilyén and Tongyang Li and Han-Hsuan Lin and Ewin Tang and Chunhao Wang},
title = {Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {421-420},
doi = {10.1145/3357713.3384314},
year = {2020},
}
Publisher's Version
STOC '20: "Quadratic Speedup for Finding ..."
Quadratic Speedup for Finding Marked Vertices by Quantum Walks
Andris Ambainis, András Gilyén, Stacey Jeffery, and Martins Kokainis
(University of Latvia, Latvia; QuSoft, Netherlands; CWI, Netherlands; University of Amsterdam, Netherlands)
@InProceedings{STOC20p449,
author = {Andris Ambainis and András Gilyén and Stacey Jeffery and Martins Kokainis},
title = {Quadratic Speedup for Finding Marked Vertices by Quantum Walks},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {449-448},
doi = {10.1145/3357713.3384252},
year = {2020},
}
Publisher's Version
STOC '20: "Approximating Text-to-Pattern ..."
Approximating Text-to-Pattern Hamming Distances
Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat
(University of Illinois at Urbana-Champaign, USA; Bar-Ilan University, Israel)
@InProceedings{STOC20p715,
author = {Timothy M. Chan and Shay Golan and Tomasz Kociumaka and Tsvi Kopelowitz and Ely Porat},
title = {Approximating Text-to-Pattern Hamming Distances},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {715-714},
doi = {10.1145/3357713.3384266},
year = {2020},
}
Publisher's Version
STOC '20: "Does Preprocessing Help in ..."
Does Preprocessing Help in Fast Sequence Comparisons?
Elazar Goldenberg, Aviad Rubinstein, and Barna Saha
(Academic College of Tel Aviv-Yaffo, Israel; Stanford University, USA; University of California at Berkeley, USA)
@InProceedings{STOC20p729,
author = {Elazar Goldenberg and Aviad Rubinstein and Barna Saha},
title = {Does Preprocessing Help in Fast Sequence Comparisons?},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {729-728},
doi = {10.1145/3357713.3384300},
year = {2020},
}
Publisher's Version
STOC '20: "Data Structures Meet Cryptography: ..."
Data Structures Meet Cryptography: 3SUM with Preprocessing
Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, and Vinod Vaikuntanathan
(Harvard University, USA; New York University Shanghai, China; Massachusetts Institute of Technology, USA)
@InProceedings{STOC20p323,
author = {Alexander Golovnev and Siyao Guo and Thibaut Horel and Sunoo Park and Vinod Vaikuntanathan},
title = {Data Structures Meet Cryptography: 3SUM with Preprocessing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {323-322},
doi = {10.1145/3357713.3384342},
year = {2020},
}
Publisher's Version
STOC '20: "Extractors for Adversarial ..."
Extractors for Adversarial Sources via Extremal Hypergraphs
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, and Xin Li
(Cornell University, USA; Carnegie Mellon University, USA; Johns Hopkins University, USA)
@InProceedings{STOC20p1317,
author = {Eshan Chattopadhyay and Jesse Goodman and Vipul Goyal and Xin Li},
title = {Extractors for Adversarial Sources via Extremal Hypergraphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1317-1316},
doi = {10.1145/3357713.3384339},
year = {2020},
}
Publisher's Version
STOC '20: "Automating Cutting Planes ..."
Automating Cutting Planes Is NP-Hard
Mika Göös, Sajin Koroth, Ian Mertz, and Toniann Pitassi
(Stanford University, USA; Simon Fraser University, Canada; University of Toronto, Canada; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC20p71,
author = {Mika Göös and Sajin Koroth and Ian Mertz and Toniann Pitassi},
title = {Automating Cutting Planes Is NP-Hard},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {71-70},
doi = {10.1145/3357713.3384248},
year = {2020},
}
Publisher's Version
STOC '20: "Entanglement Subvolume Law ..."
Entanglement Subvolume Law for 2D Frustration-Free Spin Systems
Anurag Anshu, Itai Arad, and David Gosset
(University of Waterloo, Canada; Perimeter Institute for Theoretical Physics, Canada; Technion, Israel)
@InProceedings{STOC20p953,
author = {Anurag Anshu and Itai Arad and David Gosset},
title = {Entanglement Subvolume Law for 2D Frustration-Free Spin Systems},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {953-952},
doi = {10.1145/3357713.3384292},
year = {2020},
}
Publisher's Version
STOC '20: "Extractors for Adversarial ..."
Extractors for Adversarial Sources via Extremal Hypergraphs
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, and Xin Li
(Cornell University, USA; Carnegie Mellon University, USA; Johns Hopkins University, USA)
@InProceedings{STOC20p1317,
author = {Eshan Chattopadhyay and Jesse Goodman and Vipul Goyal and Xin Li},
title = {Extractors for Adversarial Sources via Extremal Hypergraphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1317-1316},
doi = {10.1145/3357713.3384339},
year = {2020},
}
Publisher's Version
STOC '20: "Breaching the 2-Approximation ..."
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
Jarosław Byrka, Fabrizio Grandoni, and Afrouz Jabal Ameli
(University of Wrocław, Poland; IDSIA, Switzerland)
@InProceedings{STOC20p897,
author = {Jarosław Byrka and Fabrizio Grandoni and Afrouz Jabal Ameli},
title = {Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {897-896},
doi = {10.1145/3357713.3384301},
year = {2020},
}
Publisher's Version
STOC '20: "Interactive Shallow Clifford ..."
Interactive Shallow Clifford Circuits: Quantum Advantage against NC¹ and Beyond
Daniel Grier and Luke Schaeffer
(University of Waterloo, Canada)
@InProceedings{STOC20p967,
author = {Daniel Grier and Luke Schaeffer},
title = {Interactive Shallow Clifford Circuits: Quantum Advantage against NC¹ and Beyond},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {967-966},
doi = {10.1145/3357713.3384332},
year = {2020},
}
Publisher's Version
STOC '20: "Semi-algebraic Proofs, IPS ..."
Semi-algebraic Proofs, IPS Lower Bounds, and the τ-Conjecture: Can a Natural Number Be Negative?
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, and Iddo Tzameret
(Steklov Institute of Mathematics at St. Petersburg, Russia; St. Petersburg State University, Russia; CNRS, France; University of Lille, France; Royal Holloway University of London, UK)
@InProceedings{STOC20p57,
author = {Yaroslav Alekseev and Dima Grigoriev and Edward A. Hirsch and Iddo Tzameret},
title = {Semi-algebraic Proofs, IPS Lower Bounds, and the τ-Conjecture: Can a Natural Number Be Negative?},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {57-56},
doi = {10.1145/3357713.3384245},
year = {2020},
}
Publisher's Version
STOC '20: "Concentration on the Boolean ..."
Concentration on the Boolean Hypercube via Pathwise Stochastic Analysis
Ronen Eldan and Renan Gross
(Weizmann Institute of Science, Israel)
@InProceedings{STOC20p225,
author = {Ronen Eldan and Renan Gross},
title = {Concentration on the Boolean Hypercube via Pathwise Stochastic Analysis},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {225-224},
doi = {10.1145/3357713.3384230},
year = {2020},
}
Publisher's Version
STOC '20: "Smoothed Complexity of Local ..."
Smoothed Complexity of Local Max-Cut and Binary Max-CSP
Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, and Xinzhi Zhang
(Columbia University, USA; Tsinghua University, China)
@InProceedings{STOC20p1163,
author = {Xi Chen and Chenghao Guo and Emmanouil V. Vlatakis-Gkaragkounis and Mihalis Yannakakis and Xinzhi Zhang},
title = {Smoothed Complexity of Local Max-Cut and Binary Max-CSP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1163-1162},
doi = {10.1145/3357713.3384325},
year = {2020},
}
Publisher's Version
STOC '20: "Fast Sampling and Counting ..."
Fast Sampling and Counting 𝑘-SAT Solutions in the Local Lemma Regime
Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang
(Nanjing University, China; University of Edinburgh, UK; Shanghai Jiao Tong University, China)
@InProceedings{STOC20p939,
author = {Weiming Feng and Heng Guo and Yitong Yin and Chihao Zhang},
title = {Fast Sampling and Counting 𝑘-SAT Solutions in the Local Lemma Regime},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {939-938},
doi = {10.1145/3357713.3384255},
year = {2020},
}
Publisher's Version
STOC '20: "Data Structures Meet Cryptography: ..."
Data Structures Meet Cryptography: 3SUM with Preprocessing
Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, and Vinod Vaikuntanathan
(Harvard University, USA; New York University Shanghai, China; Massachusetts Institute of Technology, USA)
@InProceedings{STOC20p323,
author = {Alexander Golovnev and Siyao Guo and Thibaut Horel and Sunoo Park and Vinod Vaikuntanathan},
title = {Data Structures Meet Cryptography: 3SUM with Preprocessing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {323-322},
doi = {10.1145/3357713.3384342},
year = {2020},
}
Publisher's Version
STOC '20: "Caching with Time Windows ..."
Caching with Time Windows
Anupam Gupta, Amit Kumar, and Debmalya Panigrahi
(Carnegie Mellon University, USA; IIT Delhi, India; Duke University, USA)
@InProceedings{STOC20p1247,
author = {Anupam Gupta and Amit Kumar and Debmalya Panigrahi},
title = {Caching with Time Windows},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1247-1246},
doi = {10.1145/3357713.3384277},
year = {2020},
}
Publisher's Version
STOC '20: "The Karger-Stein Algorithm ..."
The Karger-Stein Algorithm Is Optimal for k-Cut
Anupam Gupta, Euiwoong Lee, and Jason Li
(Carnegie Mellon University, USA; New York University, USA)
@InProceedings{STOC20p519,
author = {Anupam Gupta and Euiwoong Lee and Jason Li},
title = {The Karger-Stein Algorithm Is Optimal for k-Cut},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {519-518},
doi = {10.1145/3357713.3384285},
year = {2020},
}
Publisher's Version
STOC '20: "Optimally Resilient Codes ..."
Optimally Resilient Codes for List-Decoding from Insertions and Deletions
Venkatesan Guruswami, Bernhard Haeupler, and Amirbehshad Shahrasbi
(Carnegie Mellon University, USA)
@InProceedings{STOC20p575,
author = {Venkatesan Guruswami and Bernhard Haeupler and Amirbehshad Shahrasbi},
title = {Optimally Resilient Codes for List-Decoding from Insertions and Deletions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {575-574},
doi = {10.1145/3357713.3384262},
year = {2020},
}
Publisher's Version
STOC '20: "Arikan Meets Shannon: Polar ..."
Arikan Meets Shannon: Polar Codes with Near-Optimal Convergence to Channel Capacity
Venkatesan Guruswami, Andrii Riazanov, and Min Ye
(Carnegie Mellon University, USA; Tsinghua-Berkeley Shenzhen Institute, China)
@InProceedings{STOC20p603,
author = {Venkatesan Guruswami and Andrii Riazanov and Min Ye},
title = {Arikan Meets Shannon: Polar Codes with Near-Optimal Convergence to Channel Capacity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {603-602},
doi = {10.1145/3357713.3384323},
year = {2020},
}
Publisher's Version
STOC '20: "Optimally Resilient Codes ..."
Optimally Resilient Codes for List-Decoding from Insertions and Deletions
Venkatesan Guruswami, Bernhard Haeupler, and Amirbehshad Shahrasbi
(Carnegie Mellon University, USA)
@InProceedings{STOC20p575,
author = {Venkatesan Guruswami and Bernhard Haeupler and Amirbehshad Shahrasbi},
title = {Optimally Resilient Codes for List-Decoding from Insertions and Deletions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {575-574},
doi = {10.1145/3357713.3384262},
year = {2020},
}
Publisher's Version
STOC '20: "Stochastic Matching with Few ..."
Stochastic Matching with Few Queries: (1-ε) Approximation
Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi
(University of Maryland, USA)
@InProceedings{STOC20p1233,
author = {Soheil Behnezhad and Mahsa Derakhshan and MohammadTaghi Hajiaghayi},
title = {Stochastic Matching with Few Queries: (1-ε) Approximation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1233-1232},
doi = {10.1145/3357713.3384340},
year = {2020},
}
Publisher's Version
STOC '20: "Classical Algorithms, Correlation ..."
Classical Algorithms, Correlation Decay, and Complex Zeros of Partition Functions of Quantum Many-Body Systems
Aram W. Harrow, Saeed Mehraban, and Mehdi Soleimanifar
(Massachusetts Institute of Technology, USA; California Institute of Technology, USA)
@InProceedings{STOC20p407,
author = {Aram W. Harrow and Saeed Mehraban and Mehdi Soleimanifar},
title = {Classical Algorithms, Correlation Decay, and Complex Zeros of Partition Functions of Quantum Many-Body Systems},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {407-406},
doi = {10.1145/3357713.3384322},
year = {2020},
}
Publisher's Version
STOC '20: "XOR Lemmas for Resilient Functions ..."
XOR Lemmas for Resilient Functions against Polynomials
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, and David Zuckerman
(Cornell University, USA; Ohio State University, USA; Carnegie Mellon University, USA; University of California at San Diego, USA; University of Texas at Austin, USA)
@InProceedings{STOC20p253,
author = {Eshan Chattopadhyay and Pooya Hatami and Kaave Hosseini and Shachar Lovett and David Zuckerman},
title = {XOR Lemmas for Resilient Functions against Polynomials},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {253-252},
doi = {10.1145/3357713.3384242},
year = {2020},
}
Publisher's Version
STOC '20: "Efficient Sampling and Counting ..."
Efficient Sampling and Counting Algorithms for the Potts Model on ℤᵈ at All Temperatures
Christian Borgs, Jennifer Chayes, Tyler Helmuth, Will Perkins, and Prasad Tetali
(University of California at Berkeley, USA; University of Bristol, UK; University of Illinois at Chicago, USA; Georgia Institute of Technology, USA)
@InProceedings{STOC20p813,
author = {Christian Borgs and Jennifer Chayes and Tyler Helmuth and Will Perkins and Prasad Tetali},
title = {Efficient Sampling and Counting Algorithms for the Potts Model on ℤᵈ at All Temperatures},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {813-812},
doi = {10.1145/3357713.3384271},
year = {2020},
}
Publisher's Version
STOC '20: "Unexpected Hardness Results ..."
Unexpected Hardness Results for Kolmogorov Complexity under Uniform Reductions
Shuichi Hirahara
(National Institute of Informatics, Japan)
@InProceedings{STOC20p1149,
author = {Shuichi Hirahara},
title = {Unexpected Hardness Results for Kolmogorov Complexity under Uniform Reductions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1149-1148},
doi = {10.1145/3357713.3384251},
year = {2020},
}
Publisher's Version
STOC '20: "Semi-algebraic Proofs, IPS ..."
Semi-algebraic Proofs, IPS Lower Bounds, and the τ-Conjecture: Can a Natural Number Be Negative?
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, and Iddo Tzameret
(Steklov Institute of Mathematics at St. Petersburg, Russia; St. Petersburg State University, Russia; CNRS, France; University of Lille, France; Royal Holloway University of London, UK)
@InProceedings{STOC20p57,
author = {Yaroslav Alekseev and Dima Grigoriev and Edward A. Hirsch and Iddo Tzameret},
title = {Semi-algebraic Proofs, IPS Lower Bounds, and the τ-Conjecture: Can a Natural Number Be Negative?},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {57-56},
doi = {10.1145/3357713.3384245},
year = {2020},
}
Publisher's Version
STOC '20: "Non-signaling Proofs with ..."
Non-signaling Proofs with O(√ log n) Provers Are in PSPACE
Dhiraj Holden and Yael Tauman Kalai
(Massachusetts Institute of Technology, USA; Microsoft Research, USA)
@InProceedings{STOC20p1135,
author = {Dhiraj Holden and Yael Tauman Kalai},
title = {Non-signaling Proofs with O(√ log n) Provers Are in PSPACE},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1135-1134},
doi = {10.1145/3357713.3384246},
year = {2020},
}
Publisher's Version
STOC '20: "Fully-Dynamic Planarity Testing ..."
Fully-Dynamic Planarity Testing in Polylogarithmic Time
Jacob Holm and Eva Rotenberg
(University of Copenhagen, Denmark; DTU, Denmark)
@InProceedings{STOC20p183,
author = {Jacob Holm and Eva Rotenberg},
title = {Fully-Dynamic Planarity Testing in Polylogarithmic Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {183-182},
doi = {10.1145/3357713.3384249},
year = {2020},
}
Publisher's Version
STOC '20: "Algorithms for Heavy-Tailed ..."
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, and Nilesh Tripuraneni
(University of California at Berkeley, USA)
@InProceedings{STOC20p659,
author = {Yeshwanth Cherapanamjeri and Samuel B. Hopkins and Tarun Kathuria and Prasad Raghavendra and Nilesh Tripuraneni},
title = {Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {659-658},
doi = {10.1145/3357713.3384329},
year = {2020},
}
Publisher's Version
STOC '20: "Data Structures Meet Cryptography: ..."
Data Structures Meet Cryptography: 3SUM with Preprocessing
Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, and Vinod Vaikuntanathan
(Harvard University, USA; New York University Shanghai, China; Massachusetts Institute of Technology, USA)
@InProceedings{STOC20p323,
author = {Alexander Golovnev and Siyao Guo and Thibaut Horel and Sunoo Park and Vinod Vaikuntanathan},
title = {Data Structures Meet Cryptography: 3SUM with Preprocessing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {323-322},
doi = {10.1145/3357713.3384342},
year = {2020},
}
Publisher's Version
STOC '20: "XOR Lemmas for Resilient Functions ..."
XOR Lemmas for Resilient Functions against Polynomials
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, and David Zuckerman
(Cornell University, USA; Ohio State University, USA; Carnegie Mellon University, USA; University of California at San Diego, USA; University of Texas at Austin, USA)
@InProceedings{STOC20p253,
author = {Eshan Chattopadhyay and Pooya Hatami and Kaave Hosseini and Shachar Lovett and David Zuckerman},
title = {XOR Lemmas for Resilient Functions against Polynomials},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {253-252},
doi = {10.1145/3357713.3384242},
year = {2020},
}
Publisher's Version
STOC '20: "Coresets for Clustering in ..."
Coresets for Clustering in Euclidean Spaces: Importance Sampling Is Nearly Optimal
Lingxiao Huang and Nisheeth K. Vishnoi
(Yale University, USA)
@InProceedings{STOC20p1569,
author = {Lingxiao Huang and Nisheeth K. Vishnoi},
title = {Coresets for Clustering in Euclidean Spaces: Importance Sampling Is Nearly Optimal},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1569-1568},
doi = {10.1145/3357713.3384296},
year = {2020},
}
Publisher's Version
STOC '20: "Online Primal Dual Meets Online ..."
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue
Zhiyi Huang and Qiankun Zhang
(University of Hong Kong, China)
@InProceedings{STOC20p1275,
author = {Zhiyi Huang and Qiankun Zhang},
title = {Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1275-1274},
doi = {10.1145/3357713.3384294},
year = {2020},
}
Publisher's Version
STOC '20: "A Scaling-Invariant Algorithm ..."
A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix
Daniel Dadush, Sophie Huiberts, Bento Natura, and László A. Végh
(CWI, Netherlands; London School of Economics and Political Science, UK)
@InProceedings{STOC20p841,
author = {Daniel Dadush and Sophie Huiberts and Bento Natura and László A. Végh},
title = {A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {841-840},
doi = {10.1145/3357713.3384326},
year = {2020},
}
Publisher's Version
STOC '20: "Implementing Geometric Complexity ..."
Implementing Geometric Complexity Theory: On the Separation of Orbit Closures via Symmetries
Christian Ikenmeyer and Umangathan Kandasamy
(University of Liverpool, UK; Saarland University, Germany)
@InProceedings{STOC20p785,
author = {Christian Ikenmeyer and Umangathan Kandasamy},
title = {Implementing Geometric Complexity Theory: On the Separation of Orbit Closures via Symmetries},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {785-784},
doi = {10.1145/3357713.3384257},
year = {2020},
}
Publisher's Version
STOC '20: "Positive Semidefinite Programming: ..."
Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, and Kevin Tian
(Stanford University, USA; University of Washington, USA; Microsoft Research, USA)
@InProceedings{STOC20p869,
author = {Arun Jambulapati and Yin Tat Lee and Jerry Li and Swati Padmanabhan and Kevin Tian},
title = {Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {869-868},
doi = {10.1145/3357713.3384338},
year = {2020},
}
Publisher's Version
STOC '20: "Quadratic Speedup for Finding ..."
Quadratic Speedup for Finding Marked Vertices by Quantum Walks
Andris Ambainis, András Gilyén, Stacey Jeffery, and Martins Kokainis
(University of Latvia, Latvia; QuSoft, Netherlands; CWI, Netherlands; University of Amsterdam, Netherlands)
@InProceedings{STOC20p449,
author = {Andris Ambainis and András Gilyén and Stacey Jeffery and Martins Kokainis},
title = {Quadratic Speedup for Finding Marked Vertices by Quantum Walks},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {449-448},
doi = {10.1145/3357713.3384252},
year = {2020},
}
Publisher's Version
STOC '20: "Unbounded Lower Bound for ..."
Unbounded Lower Bound for k-Server against Weak Adversaries
Marcin Bienkowski, Jarosław Byrka, Christian Coester, and Łukasz Jeż
(University of Wrocław, Poland; CWI, Netherlands)
@InProceedings{STOC20p1289,
author = {Marcin Bienkowski and Jarosław Byrka and Christian Coester and Łukasz Jeż},
title = {Unbounded Lower Bound for k-Server against Weak Adversaries},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1289-1288},
doi = {10.1145/3357713.3384306},
year = {2020},
}
Publisher's Version
STOC '20: "An Improved Cutting Plane ..."
An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games, and Its Applications
Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong
(University of Washington, USA; Microsoft Research, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA)
@InProceedings{STOC20p1037,
author = {Haotian Jiang and Yin Tat Lee and Zhao Song and Sam Chiu-wai Wong},
title = {An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games, and Its Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1037-1036},
doi = {10.1145/3357713.3384284},
year = {2020},
}
Publisher's Version
STOC '20: "Online Vector Balancing and ..."
Online Vector Balancing and Geometric Discrepancy
Nikhil Bansal, Haotian Jiang, Sahil Singla, and Makrand Sinha
(Eindhoven University of Technology, Netherlands; CWI, Netherlands; University of Washington, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC20p1261,
author = {Nikhil Bansal and Haotian Jiang and Sahil Singla and Makrand Sinha},
title = {Online Vector Balancing and Geometric Discrepancy},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1261-1260},
doi = {10.1145/3357713.3384280},
year = {2020},
}
Publisher's Version
STOC '20: "Approximately Stable Committee ..."
Approximately Stable Committee Selection
Zhihao Jiang, Kamesh Munagala, and Kangning Wang
(Tsinghua University, China; Duke University, USA)
@InProceedings{STOC20p505,
author = {Zhihao Jiang and Kamesh Munagala and Kangning Wang},
title = {Approximately Stable Committee Selection},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {505-504},
doi = {10.1145/3357713.3384238},
year = {2020},
}
Publisher's Version
STOC '20: "Sharp Threshold Results for ..."
Sharp Threshold Results for Computational Complexity
Lijie Chen, Ce Jin, and R. Ryan Williams
(Massachusetts Institute of Technology, USA; Tsinghua University, China)
@InProceedings{STOC20p1485,
author = {Lijie Chen and Ce Jin and R. Ryan Williams},
title = {Sharp Threshold Results for Computational Complexity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1485-1484},
doi = {10.1145/3357713.3384283},
year = {2020},
}
Publisher's Version
STOC '20: "Non-signaling Proofs with ..."
Non-signaling Proofs with O(√ log n) Provers Are in PSPACE
Dhiraj Holden and Yael Tauman Kalai
(Massachusetts Institute of Technology, USA; Microsoft Research, USA)
@InProceedings{STOC20p1135,
author = {Dhiraj Holden and Yael Tauman Kalai},
title = {Non-signaling Proofs with O(√ log n) Provers Are in PSPACE},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1135-1134},
doi = {10.1145/3357713.3384246},
year = {2020},
}
Publisher's Version
STOC '20: "Separations and Equivalences ..."
Separations and Equivalences between Turnstile Streaming and Linear Sketching
John Kallaugher and Eric Price
(University of Texas at Austin, USA)
@InProceedings{STOC20p1359,
author = {John Kallaugher and Eric Price},
title = {Separations and Equivalences between Turnstile Streaming and Linear Sketching},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1359-1358},
doi = {10.1145/3357713.3384278},
year = {2020},
}
Publisher's Version
STOC '20: "Implementing Geometric Complexity ..."
Implementing Geometric Complexity Theory: On the Separation of Orbit Closures via Symmetries
Christian Ikenmeyer and Umangathan Kandasamy
(University of Liverpool, UK; Saarland University, Germany)
@InProceedings{STOC20p785,
author = {Christian Ikenmeyer and Umangathan Kandasamy},
title = {Implementing Geometric Complexity Theory: On the Separation of Orbit Closures via Symmetries},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {785-784},
doi = {10.1145/3357713.3384257},
year = {2020},
}
Publisher's Version
STOC '20: "A Phase Transition and a Quadratic ..."
A Phase Transition and a Quadratic Time Unbiased Estimator for Network Reliability
David R. Karger
(Massachusetts Institute of Technology, USA)
@InProceedings{STOC20p533,
author = {David R. Karger},
title = {A Phase Transition and a Quadratic Time Unbiased Estimator for Network Reliability},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {533-532},
doi = {10.1145/3357713.3384336},
year = {2020},
}
Publisher's Version
STOC '20: "An Improved Approximation ..."
An Improved Approximation Algorithm for TSP in the Half Integral Case
Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan
(University of Washington, USA)
@InProceedings{STOC20p29,
author = {Anna R. Karlin and Nathan Klein and Shayan Oveis Gharan},
title = {An Improved Approximation Algorithm for TSP in the Half Integral Case},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {29-28},
doi = {10.1145/3357713.3384273},
year = {2020},
}
Publisher's Version
STOC '20: "Algorithms for Heavy-Tailed ..."
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, and Nilesh Tripuraneni
(University of California at Berkeley, USA)
@InProceedings{STOC20p659,
author = {Yeshwanth Cherapanamjeri and Samuel B. Hopkins and Tarun Kathuria and Prasad Raghavendra and Nilesh Tripuraneni},
title = {Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {659-658},
doi = {10.1145/3357713.3384329},
year = {2020},
}
Publisher's Version
STOC '20: "Separating the Communication ..."
Separating the Communication Complexity of Truthful and Non-truthful Combinatorial Auctions
Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, and S. Matthew Weinberg
(Rutgers University, USA; Princeton University, USA)
@InProceedings{STOC20p1191,
author = {Sepehr Assadi and Hrishikesh Khandeparkar and Raghuvansh R. Saxena and S. Matthew Weinberg},
title = {Separating the Communication Complexity of Truthful and Non-truthful Combinatorial Auctions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1191-1190},
doi = {10.1145/3357713.3384267},
year = {2020},
}
Publisher's Version
STOC '20: "One-Shot Signatures and Applications ..."
One-Shot Signatures and Applications to Hybrid Quantum/Classical Authentication
Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry
(Princeton University, USA; City University of New York, USA; University of Edinburgh, UK)
@InProceedings{STOC20p281,
author = {Ryan Amos and Marios Georgiou and Aggelos Kiayias and Mark Zhandry},
title = {One-Shot Signatures and Applications to Hybrid Quantum/Classical Authentication},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {281-280},
doi = {10.1145/3357713.3384304},
year = {2020},
}
Publisher's Version
STOC '20: "An Improved Approximation ..."
An Improved Approximation Algorithm for TSP in the Half Integral Case
Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan
(University of Washington, USA)
@InProceedings{STOC20p29,
author = {Anna R. Karlin and Nathan Klein and Shayan Oveis Gharan},
title = {An Improved Approximation Algorithm for TSP in the Half Integral Case},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {29-28},
doi = {10.1145/3357713.3384273},
year = {2020},
}
Publisher's Version
STOC '20: "New Hardness Results for Planar ..."
New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut
Amir Abboud, Vincent Cohen-Addad, and Philip N. Klein
(IBM, USA; CNRS, France; UPMC, France; Brown University, USA)
@InProceedings{STOC20p1107,
author = {Amir Abboud and Vincent Cohen-Addad and Philip N. Klein},
title = {New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1107-1106},
doi = {10.1145/3357713.3384310},
year = {2020},
}
Publisher's Version
STOC '20: "Optimal Time and Space Leader ..."
Optimal Time and Space Leader Election in Population Protocols
Petra Berenbrink, George Giakkoupis, and Peter Kling
(University of Hamburg, Germany; Inria, France; University of Rennes, France; CNRS, France; IRISA, France)
@InProceedings{STOC20p127,
author = {Petra Berenbrink and George Giakkoupis and Peter Kling},
title = {Optimal Time and Space Leader Election in Population Protocols},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {127-126},
doi = {10.1145/3357713.3384312},
year = {2020},
}
Publisher's Version
STOC '20: "Fast Hashing with Strong Concentration ..."
Fast Hashing with Strong Concentration Bounds
Anders Aamand, Jakob Bæk Tejs Knudsen, Mathias Bæk Tejs Knudsen, Peter Michael Reichstein Rasmussen, and Mikkel Thorup
(University of Copenhagen, Denmark; SupWiz, Denmark)
@InProceedings{STOC20p1401,
author = {Anders Aamand and Jakob Bæk Tejs Knudsen and Mathias Bæk Tejs Knudsen and Peter Michael Reichstein Rasmussen and Mikkel Thorup},
title = {Fast Hashing with Strong Concentration Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1401-1400},
doi = {10.1145/3357713.3384259},
year = {2020},
}
Publisher's Version
STOC '20: "Fast Hashing with Strong Concentration ..."
Fast Hashing with Strong Concentration Bounds
Anders Aamand, Jakob Bæk Tejs Knudsen, Mathias Bæk Tejs Knudsen, Peter Michael Reichstein Rasmussen, and Mikkel Thorup
(University of Copenhagen, Denmark; SupWiz, Denmark)
@InProceedings{STOC20p1401,
author = {Anders Aamand and Jakob Bæk Tejs Knudsen and Mathias Bæk Tejs Knudsen and Peter Michael Reichstein Rasmussen and Mikkel Thorup},
title = {Fast Hashing with Strong Concentration Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1401-1400},
doi = {10.1145/3357713.3384259},
year = {2020},
}
Publisher's Version
STOC '20: "Approximating Text-to-Pattern ..."
Approximating Text-to-Pattern Hamming Distances
Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat
(University of Illinois at Urbana-Champaign, USA; Bar-Ilan University, Israel)
@InProceedings{STOC20p715,
author = {Timothy M. Chan and Shay Golan and Tomasz Kociumaka and Tsvi Kopelowitz and Ely Porat},
title = {Approximating Text-to-Pattern Hamming Distances},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {715-714},
doi = {10.1145/3357713.3384266},
year = {2020},
}
Publisher's Version
STOC '20: "Quadratic Speedup for Finding ..."
Quadratic Speedup for Finding Marked Vertices by Quantum Walks
Andris Ambainis, András Gilyén, Stacey Jeffery, and Martins Kokainis
(University of Latvia, Latvia; QuSoft, Netherlands; CWI, Netherlands; University of Amsterdam, Netherlands)
@InProceedings{STOC20p449,
author = {Andris Ambainis and András Gilyén and Stacey Jeffery and Martins Kokainis},
title = {Quadratic Speedup for Finding Marked Vertices by Quantum Walks},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {449-448},
doi = {10.1145/3357713.3384252},
year = {2020},
}
Publisher's Version
STOC '20: "Interactive Error Resilience ..."
Interactive Error Resilience beyond 2/7
Klim Efremenko, Gillat Kol, and Raghuvansh R. Saxena
(Ben-Gurion University of the Negev, Israel; Princeton University, USA)
@InProceedings{STOC20p617,
author = {Klim Efremenko and Gillat Kol and Raghuvansh R. Saxena},
title = {Interactive Error Resilience beyond 2/7},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {617-616},
doi = {10.1145/3357713.3384320},
year = {2020},
}
Publisher's Version
STOC '20: "Contention Resolution without ..."
Contention Resolution without Collision Detection
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, and Seth Pettie
(Stony Brook University, USA; Bar-Ilan University, Israel; Massachusetts Institute of Technology, USA; University of Michigan, USA)
@InProceedings{STOC20p113,
author = {Michael A. Bender and Tsvi Kopelowitz and William Kuszmaul and Seth Pettie},
title = {Contention Resolution without Collision Detection},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {113-112},
doi = {10.1145/3357713.3384305},
year = {2020},
}
Publisher's Version
STOC '20: "Approximating Text-to-Pattern ..."
Approximating Text-to-Pattern Hamming Distances
Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat
(University of Illinois at Urbana-Champaign, USA; Bar-Ilan University, Israel)
@InProceedings{STOC20p715,
author = {Timothy M. Chan and Shay Golan and Tomasz Kociumaka and Tsvi Kopelowitz and Ely Porat},
title = {Approximating Text-to-Pattern Hamming Distances},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {715-714},
doi = {10.1145/3357713.3384266},
year = {2020},
}
Publisher's Version
STOC '20: "Private Stochastic Convex ..."
Private Stochastic Convex Optimization: Optimal Rates in Linear Time
Vitaly Feldman, Tomer Koren, and Kunal Talwar
(Google Research, USA; Tel Aviv University, Israel; Google, Israel)
@InProceedings{STOC20p477,
author = {Vitaly Feldman and Tomer Koren and Kunal Talwar},
title = {Private Stochastic Convex Optimization: Optimal Rates in Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {477-476},
doi = {10.1145/3357713.3384335},
year = {2020},
}
Publisher's Version
STOC '20: "Automating Cutting Planes ..."
Automating Cutting Planes Is NP-Hard
Mika Göös, Sajin Koroth, Ian Mertz, and Toniann Pitassi
(Stanford University, USA; Simon Fraser University, Canada; University of Toronto, Canada; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC20p71,
author = {Mika Göös and Sajin Koroth and Ian Mertz and Toniann Pitassi},
title = {Automating Cutting Planes Is NP-Hard},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {71-70},
doi = {10.1145/3357713.3384248},
year = {2020},
}
Publisher's Version
STOC '20: "Constant Factor Approximations ..."
Constant Factor Approximations to Edit Distance on Far Input Pairs in Nearly Linear Time
Michal Koucký and Michael Saks
(Charles University in Prague, Czechia; Rutgers University, USA)
@InProceedings{STOC20p771,
author = {Michal Koucký and Michael Saks},
title = {Constant Factor Approximations to Edit Distance on Far Input Pairs in Nearly Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {771-770},
doi = {10.1145/3357713.3384307},
year = {2020},
}
Publisher's Version
STOC '20: "On the Nisan-Ronen Conjecture ..."
On the Nisan-Ronen Conjecture for Submodular Valuations
George Christodoulou, Elias Koutsoupias, and Annamária Kovács
(University of Liverpool, UK; University of Oxford, UK; Goethe University Frankfurt, Germany)
@InProceedings{STOC20p1205,
author = {George Christodoulou and Elias Koutsoupias and Annamária Kovács},
title = {On the Nisan-Ronen Conjecture for Submodular Valuations},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1205-1204},
doi = {10.1145/3357713.3384299},
year = {2020},
}
Publisher's Version
STOC '20: "On the Nisan-Ronen Conjecture ..."
On the Nisan-Ronen Conjecture for Submodular Valuations
George Christodoulou, Elias Koutsoupias, and Annamária Kovács
(University of Liverpool, UK; University of Oxford, UK; Goethe University Frankfurt, Germany)
@InProceedings{STOC20p1205,
author = {George Christodoulou and Elias Koutsoupias and Annamária Kovács},
title = {On the Nisan-Ronen Conjecture for Submodular Valuations},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1205-1204},
doi = {10.1145/3357713.3384299},
year = {2020},
}
Publisher's Version
STOC '20: "Caching with Time Windows ..."
Caching with Time Windows
Anupam Gupta, Amit Kumar, and Debmalya Panigrahi
(Carnegie Mellon University, USA; IIT Delhi, India; Duke University, USA)
@InProceedings{STOC20p1247,
author = {Anupam Gupta and Amit Kumar and Debmalya Panigrahi},
title = {Caching with Time Windows},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1247-1246},
doi = {10.1145/3357713.3384277},
year = {2020},
}
Publisher's Version
STOC '20: "Contention Resolution without ..."
Contention Resolution without Collision Detection
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, and Seth Pettie
(Stony Brook University, USA; Bar-Ilan University, Israel; Massachusetts Institute of Technology, USA; University of Michigan, USA)
@InProceedings{STOC20p113,
author = {Michael A. Bender and Tsvi Kopelowitz and William Kuszmaul and Seth Pettie},
title = {Contention Resolution without Collision Detection},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {113-112},
doi = {10.1145/3357713.3384305},
year = {2020},
}
Publisher's Version
STOC '20: "Walking Randomly, Massively, ..."
Walking Randomly, Massively, and Efficiently
Jakub Łącki, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski
(Google Research, USA; Massachusetts Institute of Technology, USA; IBM Research, USA; University of Warsaw, Poland)
@InProceedings{STOC20p393,
author = {Jakub Łącki and Slobodan Mitrović and Krzysztof Onak and Piotr Sankowski},
title = {Walking Randomly, Massively, and Efficiently},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {393-392},
doi = {10.1145/3357713.3384303},
year = {2020},
}
Publisher's Version
STOC '20: "Strong Self-Concordance and ..."
Strong Self-Concordance and Sampling
Aditi Laddha, Yin Tat Lee, and Santosh Vempala
(Georgia Institute of Technology, USA; University of Washington, USA; Microsoft Research, USA)
@InProceedings{STOC20p1345,
author = {Aditi Laddha and Yin Tat Lee and Santosh Vempala},
title = {Strong Self-Concordance and Sampling},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1345-1344},
doi = {10.1145/3357713.3384272},
year = {2020},
}
Publisher's Version
STOC '20: "On the Need for Large Quantum ..."
On the Need for Large Quantum Depth
Nai-Hui Chia, Kai-Min Chung, and Ching-Yi Lai
(University of Texas at Austin, USA; Academia Sinica, Taiwan; National Chiao Tung University, Taiwan)
@InProceedings{STOC20p995,
author = {Nai-Hui Chia and Kai-Min Chung and Ching-Yi Lai},
title = {On the Need for Large Quantum Depth},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {995-994},
doi = {10.1145/3357713.3384291},
year = {2020},
}
Publisher's Version
STOC '20: "Three-in-a-Tree in Near Linear ..."
Three-in-a-Tree in Near Linear Time
Kai-Yuan Lai, Hsueh-I Lu, and Mikkel Thorup
(National Taiwan University, Taiwan; University of Copenhagen, Denmark)
@InProceedings{STOC20p1415,
author = {Kai-Yuan Lai and Hsueh-I Lu and Mikkel Thorup},
title = {Three-in-a-Tree in Near Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1415-1414},
doi = {10.1145/3357713.3384235},
year = {2020},
}
Publisher's Version
STOC '20: "Improved Analysis of Higher ..."
Improved Analysis of Higher Order Random Walks and Applications
Vedat Levi Alev and Lap Chi Lau
(University of Waterloo, Canada)
@InProceedings{STOC20p1331,
author = {Vedat Levi Alev and Lap Chi Lau},
title = {Improved Analysis of Higher Order Random Walks and Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1331-1330},
doi = {10.1145/3357713.3384317},
year = {2020},
}
Publisher's Version
STOC '20: "A Spectral Approach to Network ..."
A Spectral Approach to Network Design
Lap Chi Lau and Hong Zhou
(University of Waterloo, Canada)
@InProceedings{STOC20p911,
author = {Lap Chi Lau and Hong Zhou},
title = {A Spectral Approach to Network Design},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {911-910},
doi = {10.1145/3357713.3384313},
year = {2020},
}
Publisher's Version
STOC '20: "On the Computability of Continuous ..."
On the Computability of Continuous Maximum Entropy Distributions with Applications
Jonathan Leake and Nisheeth K. Vishnoi
(KTH, Sweden; Yale University, USA)
@InProceedings{STOC20p1023,
author = {Jonathan Leake and Nisheeth K. Vishnoi},
title = {On the Computability of Continuous Maximum Entropy Distributions with Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1023-1022},
doi = {10.1145/3357713.3384302},
year = {2020},
}
Publisher's Version
STOC '20: "The Karger-Stein Algorithm ..."
The Karger-Stein Algorithm Is Optimal for k-Cut
Anupam Gupta, Euiwoong Lee, and Jason Li
(Carnegie Mellon University, USA; New York University, USA)
@InProceedings{STOC20p519,
author = {Anupam Gupta and Euiwoong Lee and Jason Li},
title = {The Karger-Stein Algorithm Is Optimal for k-Cut},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {519-518},
doi = {10.1145/3357713.3384285},
year = {2020},
}
Publisher's Version
STOC '20: "Estimating Normalizing Constants ..."
Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds
Rong Ge, Holden Lee, and Jianfeng Lu
(Duke University, USA)
@InProceedings{STOC20p631,
author = {Rong Ge and Holden Lee and Jianfeng Lu},
title = {Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {631-630},
doi = {10.1145/3357713.3384289},
year = {2020},
}
Publisher's Version
STOC '20: "An Improved Cutting Plane ..."
An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games, and Its Applications
Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong
(University of Washington, USA; Microsoft Research, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA)
@InProceedings{STOC20p1037,
author = {Haotian Jiang and Yin Tat Lee and Zhao Song and Sam Chiu-wai Wong},
title = {An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games, and Its Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1037-1036},
doi = {10.1145/3357713.3384284},
year = {2020},
}
Publisher's Version
STOC '20: "Strong Self-Concordance and ..."
Strong Self-Concordance and Sampling
Aditi Laddha, Yin Tat Lee, and Santosh Vempala
(Georgia Institute of Technology, USA; University of Washington, USA; Microsoft Research, USA)
@InProceedings{STOC20p1345,
author = {Aditi Laddha and Yin Tat Lee and Santosh Vempala},
title = {Strong Self-Concordance and Sampling},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1345-1344},
doi = {10.1145/3357713.3384272},
year = {2020},
}
Publisher's Version
STOC '20: "Solving Tall Dense Linear ..."
Solving Tall Dense Linear Programs in Nearly Linear Time
Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song
(KTH, Sweden; University of Washington, USA; Microsoft Research, USA; Stanford University, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA)
@InProceedings{STOC20p855,
author = {Jan van den Brand and Yin Tat Lee and Aaron Sidford and Zhao Song},
title = {Solving Tall Dense Linear Programs in Nearly Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {855-854},
doi = {10.1145/3357713.3384309},
year = {2020},
}
Publisher's Version
STOC '20: "Positive Semidefinite Programming: ..."
Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, and Kevin Tian
(Stanford University, USA; University of Washington, USA; Microsoft Research, USA)
@InProceedings{STOC20p869,
author = {Arun Jambulapati and Yin Tat Lee and Jerry Li and Swati Padmanabhan and Kevin Tian},
title = {Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {869-868},
doi = {10.1145/3357713.3384338},
year = {2020},
}
Publisher's Version
STOC '20: "Faster Parallel Algorithm ..."
Faster Parallel Algorithm for Approximate Shortest Path
Jason Li
(Carnegie Mellon University, USA)
@InProceedings{STOC20p337,
author = {Jason Li},
title = {Faster Parallel Algorithm for Approximate Shortest Path},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {337-336},
doi = {10.1145/3357713.3384268},
year = {2020},
}
Publisher's Version
STOC '20: "The Karger-Stein Algorithm ..."
The Karger-Stein Algorithm Is Optimal for k-Cut
Anupam Gupta, Euiwoong Lee, and Jason Li
(Carnegie Mellon University, USA; New York University, USA)
@InProceedings{STOC20p519,
author = {Anupam Gupta and Euiwoong Lee and Jason Li},
title = {The Karger-Stein Algorithm Is Optimal for k-Cut},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {519-518},
doi = {10.1145/3357713.3384285},
year = {2020},
}
Publisher's Version
STOC '20: "Efficiently Learning Structured ..."
Efficiently Learning Structured Distributions from Untrusted Batches
Sitan Chen, Jerry Li, and Ankur Moitra
(Massachusetts Institute of Technology, USA; Microsoft Research, USA)
@InProceedings{STOC20p1065,
author = {Sitan Chen and Jerry Li and Ankur Moitra},
title = {Efficiently Learning Structured Distributions from Untrusted Batches},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1065-1064},
doi = {10.1145/3357713.3384337},
year = {2020},
}
Publisher's Version
STOC '20: "Learning Mixtures of Linear ..."
Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
Sitan Chen, Jerry Li, and Zhao Song
(Massachusetts Institute of Technology, USA; Microsoft Research, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC20p645,
author = {Sitan Chen and Jerry Li and Zhao Song},
title = {Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {645-644},
doi = {10.1145/3357713.3384333},
year = {2020},
}
Publisher's Version
STOC '20: "Positive Semidefinite Programming: ..."
Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, and Kevin Tian
(Stanford University, USA; University of Washington, USA; Microsoft Research, USA)
@InProceedings{STOC20p869,
author = {Arun Jambulapati and Yin Tat Lee and Jerry Li and Swati Padmanabhan and Kevin Tian},
title = {Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {869-868},
doi = {10.1145/3357713.3384338},
year = {2020},
}
Publisher's Version
STOC '20: "Sampling-Based Sublinear Low-Rank ..."
Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang
(University of Texas at Austin, USA; California Institute of Technology, USA; University of Maryland, USA; University of Washington, USA)
@InProceedings{STOC20p421,
author = {Nai-Hui Chia and András Gilyén and Tongyang Li and Han-Hsuan Lin and Ewin Tang and Chunhao Wang},
title = {Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {421-420},
doi = {10.1145/3357713.3384314},
year = {2020},
}
Publisher's Version
STOC '20: "A Polynomial Lower Bound on ..."
A Polynomial Lower Bound on Adaptive Complexity of Submodular Maximization
Wenzheng Li, Paul Liu, and Jan Vondrák
(Stanford University, USA)
@InProceedings{STOC20p155,
author = {Wenzheng Li and Paul Liu and Jan Vondrák},
title = {A Polynomial Lower Bound on Adaptive Complexity of Submodular Maximization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {155-154},
doi = {10.1145/3357713.3384311},
year = {2020},
}
Publisher's Version
STOC '20: "Extractors for Adversarial ..."
Extractors for Adversarial Sources via Extremal Hypergraphs
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, and Xin Li
(Cornell University, USA; Carnegie Mellon University, USA; Johns Hopkins University, USA)
@InProceedings{STOC20p1317,
author = {Eshan Chattopadhyay and Jesse Goodman and Vipul Goyal and Xin Li},
title = {Extractors for Adversarial Sources via Extremal Hypergraphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1317-1316},
doi = {10.1145/3357713.3384339},
year = {2020},
}
Publisher's Version
STOC '20: "AND Testing and Robust Judgement ..."
AND Testing and Robust Judgement Aggregation
Yuval Filmus, Noam Lifshitz, Dor Minzer, and Elchanan Mossel
(Technion, Israel; Hebrew University of Jerusalem, Israel; Institute for Advanced Study at Princeton, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC20p239,
author = {Yuval Filmus and Noam Lifshitz and Dor Minzer and Elchanan Mossel},
title = {AND Testing and Robust Judgement Aggregation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {239-238},
doi = {10.1145/3357713.3384254},
year = {2020},
}
Publisher's Version
STOC '20: "Sampling-Based Sublinear Low-Rank ..."
Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang
(University of Texas at Austin, USA; California Institute of Technology, USA; University of Maryland, USA; University of Washington, USA)
@InProceedings{STOC20p421,
author = {Nai-Hui Chia and András Gilyén and Tongyang Li and Han-Hsuan Lin and Ewin Tang and Chunhao Wang},
title = {Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {421-420},
doi = {10.1145/3357713.3384314},
year = {2020},
}
Publisher's Version
STOC '20: "Lower Bound for Succinct Range ..."
Lower Bound for Succinct Range Minimum Query
Mingmou Liu and Huacheng Yu
(Nanjing University, China; Princeton University, USA)
@InProceedings{STOC20p1555,
author = {Mingmou Liu and Huacheng Yu},
title = {Lower Bound for Succinct Range Minimum Query},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1555-1554},
doi = {10.1145/3357713.3384260},
year = {2020},
}
Publisher's Version
STOC '20: "A Polynomial Lower Bound on ..."
A Polynomial Lower Bound on Adaptive Complexity of Submodular Maximization
Wenzheng Li, Paul Liu, and Jan Vondrák
(Stanford University, USA)
@InProceedings{STOC20p155,
author = {Wenzheng Li and Paul Liu and Jan Vondrák},
title = {A Polynomial Lower Bound on Adaptive Complexity of Submodular Maximization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {155-154},
doi = {10.1145/3357713.3384311},
year = {2020},
}
Publisher's Version
STOC '20: "Constant Girth Approximation ..."
Constant Girth Approximation for Directed Graphs in Subquadratic Time
Shiri Chechik, Yang P. Liu, Omer Rotem, and Aaron Sidford
(Tel Aviv University, Israel; Stanford University, USA)
@InProceedings{STOC20p1121,
author = {Shiri Chechik and Yang P. Liu and Omer Rotem and Aaron Sidford},
title = {Constant Girth Approximation for Directed Graphs in Subquadratic Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1121-1120},
doi = {10.1145/3357713.3384330},
year = {2020},
}
Publisher's Version
STOC '20: "Faster Energy Maximization ..."
Faster Energy Maximization for Faster Maximum Flow
Yang P. Liu and Aaron Sidford
(Stanford University, USA)
@InProceedings{STOC20p883,
author = {Yang P. Liu and Aaron Sidford},
title = {Faster Energy Maximization for Faster Maximum Flow},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {883-882},
doi = {10.1145/3357713.3384247},
year = {2020},
}
Publisher's Version
STOC '20: "An Exponential Time Parameterized ..."
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
Daniel Lokshtanov, Pranabendu Misra, Michał Pilipczuk, Saket Saurabh, and Meirav Zehavi
(University of California at Santa Barbara, USA; MPI-INF, Germany; University of Warsaw, Poland; IMSc, India; Ben-Gurion University of the Negev, Israel)
@InProceedings{STOC20p1443,
author = {Daniel Lokshtanov and Pranabendu Misra and Michał Pilipczuk and Saket Saurabh and Meirav Zehavi},
title = {An Exponential Time Parameterized Algorithm for Planar Disjoint Paths},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1443-1442},
doi = {10.1145/3357713.3384250},
year = {2020},
}
Publisher's Version
STOC '20: "Hitting Topological Minors ..."
Hitting Topological Minors Is FPT
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi
(University of Bergen, Norway; University of California at Santa Barbara, USA; IIT Hyderabad, India; IMSc, India; Ben-Gurion University of the Negev, Israel)
@InProceedings{STOC20p1457,
author = {Fedor V. Fomin and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh and Meirav Zehavi},
title = {Hitting Topological Minors Is FPT},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1457-1456},
doi = {10.1145/3357713.3384318},
year = {2020},
}
Publisher's Version
STOC '20: "XOR Lemmas for Resilient Functions ..."
XOR Lemmas for Resilient Functions against Polynomials
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, and David Zuckerman
(Cornell University, USA; Ohio State University, USA; Carnegie Mellon University, USA; University of California at San Diego, USA; University of Texas at Austin, USA)
@InProceedings{STOC20p253,
author = {Eshan Chattopadhyay and Pooya Hatami and Kaave Hosseini and Shachar Lovett and David Zuckerman},
title = {XOR Lemmas for Resilient Functions against Polynomials},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {253-252},
doi = {10.1145/3357713.3384242},
year = {2020},
}
Publisher's Version
STOC '20: "Decision List Compression ..."
Decision List Compression by Mild Random Restrictions
Shachar Lovett, Kewen Wu, and Jiapeng Zhang
(University of California at San Diego, USA; Peking University, China; Harvard University, USA)
@InProceedings{STOC20p267,
author = {Shachar Lovett and Kewen Wu and Jiapeng Zhang},
title = {Decision List Compression by Mild Random Restrictions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {267-266},
doi = {10.1145/3357713.3384241},
year = {2020},
}
Publisher's Version
STOC '20: "Improved Bounds for the Sunflower ..."
Improved Bounds for the Sunflower Lemma
Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang
(Princeton University, USA; University of California at San Diego, USA; Peking University, China; Harvard University, USA)
@InProceedings{STOC20p687,
author = {Ryan Alweiss and Shachar Lovett and Kewen Wu and Jiapeng Zhang},
title = {Improved Bounds for the Sunflower Lemma},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {687-686},
doi = {10.1145/3357713.3384234},
year = {2020},
}
Publisher's Version
STOC '20: "Three-in-a-Tree in Near Linear ..."
Three-in-a-Tree in Near Linear Time
Kai-Yuan Lai, Hsueh-I Lu, and Mikkel Thorup
(National Taiwan University, Taiwan; University of Copenhagen, Denmark)
@InProceedings{STOC20p1415,
author = {Kai-Yuan Lai and Hsueh-I Lu and Mikkel Thorup},
title = {Three-in-a-Tree in Near Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1415-1414},
doi = {10.1145/3357713.3384235},
year = {2020},
}
Publisher's Version
STOC '20: "Estimating Normalizing Constants ..."
Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds
Rong Ge, Holden Lee, and Jianfeng Lu
(Duke University, USA)
@InProceedings{STOC20p631,
author = {Rong Ge and Holden Lee and Jianfeng Lu},
title = {Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {631-630},
doi = {10.1145/3357713.3384289},
year = {2020},
}
Publisher's Version
STOC '20: "Non-adaptive Adaptive Sampling ..."
Non-adaptive Adaptive Sampling on Turnstile Streams
Sepideh Mahabadi, Ilya Razenshteyn, David P. Woodruff, and Samson Zhou
(Toyota Technological Institute at Chicago, USA; Microsoft Research, USA; Carnegie Mellon University, USA)
@InProceedings{STOC20p1387,
author = {Sepideh Mahabadi and Ilya Razenshteyn and David P. Woodruff and Samson Zhou},
title = {Non-adaptive Adaptive Sampling on Turnstile Streams},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1387-1386},
doi = {10.1145/3357713.3384331},
year = {2020},
}
Publisher's Version
STOC '20: "QCSP Monsters and the Demise ..."
QCSP Monsters and the Demise of the Chen Conjecture
Dmitriy Zhuk and Barnaby Martin
(Moscow State University, Russia; Durham University, UK)
@InProceedings{STOC20p99,
author = {Dmitriy Zhuk and Barnaby Martin},
title = {QCSP Monsters and the Demise of the Chen Conjecture},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {99-98},
doi = {10.1145/3357713.3384232},
year = {2020},
}
Publisher's Version
STOC '20: "Classical Algorithms, Correlation ..."
Classical Algorithms, Correlation Decay, and Complex Zeros of Partition Functions of Quantum Many-Body Systems
Aram W. Harrow, Saeed Mehraban, and Mehdi Soleimanifar
(Massachusetts Institute of Technology, USA; California Institute of Technology, USA)
@InProceedings{STOC20p407,
author = {Aram W. Harrow and Saeed Mehraban and Mehdi Soleimanifar},
title = {Classical Algorithms, Correlation Decay, and Complex Zeros of Partition Functions of Quantum Many-Body Systems},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {407-406},
doi = {10.1145/3357713.3384322},
year = {2020},
}
Publisher's Version
STOC '20: "Computations with Greater ..."
Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
Matthew Coudron and Sanketh Menda
(University of Waterloo, Canada; University of Maryland, USA; NIST, USA)
@InProceedings{STOC20p981,
author = {Matthew Coudron and Sanketh Menda},
title = {Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {981-980},
doi = {10.1145/3357713.3384269},
year = {2020},
}
Publisher's Version
STOC '20: "Automating Cutting Planes ..."
Automating Cutting Planes Is NP-Hard
Mika Göös, Sajin Koroth, Ian Mertz, and Toniann Pitassi
(Stanford University, USA; Simon Fraser University, Canada; University of Toronto, Canada; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC20p71,
author = {Mika Göös and Sajin Koroth and Ian Mertz and Toniann Pitassi},
title = {Automating Cutting Planes Is NP-Hard},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {71-70},
doi = {10.1145/3357713.3384248},
year = {2020},
}
Publisher's Version
STOC '20: "Catalytic Approaches to the ..."
Catalytic Approaches to the Tree Evaluation Problem
James Cook and Ian Mertz
(University of Toronto, Canada)
@InProceedings{STOC20p827,
author = {James Cook and Ian Mertz},
title = {Catalytic Approaches to the Tree Evaluation Problem},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {827-826},
doi = {10.1145/3357713.3384316},
year = {2020},
}
Publisher's Version
STOC '20: "The Program-Size Complexity ..."
The Program-Size Complexity of Self-Assembled Paths
Pierre-Étienne Meunier, Damien Regnault, and Damien Woods
(Maynooth University, Ireland; University of Évry, France; University of Paris-Saclay, France)
@InProceedings{STOC20p799,
author = {Pierre-Étienne Meunier and Damien Regnault and Damien Woods},
title = {The Program-Size Complexity of Self-Assembled Paths},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {799-798},
doi = {10.1145/3357713.3384263},
year = {2020},
}
Publisher's Version
STOC '20: "The Impossibility of Efficient ..."
The Impossibility of Efficient Quantum Weak Coin Flipping
Carl A. Miller
(NIST, USA; University of Maryland, USA)
@InProceedings{STOC20p1009,
author = {Carl A. Miller},
title = {The Impossibility of Efficient Quantum Weak Coin Flipping},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1009-1008},
doi = {10.1145/3357713.3384276},
year = {2020},
}
Publisher's Version
STOC '20: "AND Testing and Robust Judgement ..."
AND Testing and Robust Judgement Aggregation
Yuval Filmus, Noam Lifshitz, Dor Minzer, and Elchanan Mossel
(Technion, Israel; Hebrew University of Jerusalem, Israel; Institute for Advanced Study at Princeton, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC20p239,
author = {Yuval Filmus and Noam Lifshitz and Dor Minzer and Elchanan Mossel},
title = {AND Testing and Robust Judgement Aggregation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {239-238},
doi = {10.1145/3357713.3384254},
year = {2020},
}
Publisher's Version
STOC '20: "An Exponential Time Parameterized ..."
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
Daniel Lokshtanov, Pranabendu Misra, Michał Pilipczuk, Saket Saurabh, and Meirav Zehavi
(University of California at Santa Barbara, USA; MPI-INF, Germany; University of Warsaw, Poland; IMSc, India; Ben-Gurion University of the Negev, Israel)
@InProceedings{STOC20p1443,
author = {Daniel Lokshtanov and Pranabendu Misra and Michał Pilipczuk and Saket Saurabh and Meirav Zehavi},
title = {An Exponential Time Parameterized Algorithm for Planar Disjoint Paths},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1443-1442},
doi = {10.1145/3357713.3384250},
year = {2020},
}
Publisher's Version
STOC '20: "Walking Randomly, Massively, ..."
Walking Randomly, Massively, and Efficiently
Jakub Łącki, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski
(Google Research, USA; Massachusetts Institute of Technology, USA; IBM Research, USA; University of Warsaw, Poland)
@InProceedings{STOC20p393,
author = {Jakub Łącki and Slobodan Mitrović and Krzysztof Onak and Piotr Sankowski},
title = {Walking Randomly, Massively, and Efficiently},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {393-392},
doi = {10.1145/3357713.3384303},
year = {2020},
}
Publisher's Version
STOC '20: "Dynamic Algorithms for LIS ..."
Dynamic Algorithms for LIS and Distance to Monotonicity
Michael Mitzenmacher and Saeed Seddighin
(Harvard University, USA)
@InProceedings{STOC20p743,
author = {Michael Mitzenmacher and Saeed Seddighin},
title = {Dynamic Algorithms for LIS and Distance to Monotonicity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {743-742},
doi = {10.1145/3357713.3384240},
year = {2020},
}
Publisher's Version
STOC '20: "Explicit Near-Ramanujan Graphs ..."
Explicit Near-Ramanujan Graphs of Every Degree
Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes
(University of California at Berkeley, USA; Carnegie Mellon University, USA)
@InProceedings{STOC20p561,
author = {Sidhanth Mohanty and Ryan O'Donnell and Pedro Paredes},
title = {Explicit Near-Ramanujan Graphs of Every Degree},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {561-560},
doi = {10.1145/3357713.3384231},
year = {2020},
}
Publisher's Version
STOC '20: "Lifting Sum-of-Squares Lower ..."
Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4
Sidhanth Mohanty, Prasad Raghavendra, and Jeff Xu
(University of California at Berkeley, USA)
@InProceedings{STOC20p925,
author = {Sidhanth Mohanty and Prasad Raghavendra and Jeff Xu},
title = {Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {925-924},
doi = {10.1145/3357713.3384319},
year = {2020},
}
Publisher's Version
STOC '20: "Efficiently Learning Structured ..."
Efficiently Learning Structured Distributions from Untrusted Batches
Sitan Chen, Jerry Li, and Ankur Moitra
(Massachusetts Institute of Technology, USA; Microsoft Research, USA)
@InProceedings{STOC20p1065,
author = {Sitan Chen and Jerry Li and Ankur Moitra},
title = {Efficiently Learning Structured Distributions from Untrusted Batches},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1065-1064},
doi = {10.1145/3357713.3384337},
year = {2020},
}
Publisher's Version
STOC '20: "AND Testing and Robust Judgement ..."
AND Testing and Robust Judgement Aggregation
Yuval Filmus, Noam Lifshitz, Dor Minzer, and Elchanan Mossel
(Technion, Israel; Hebrew University of Jerusalem, Israel; Institute for Advanced Study at Princeton, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC20p239,
author = {Yuval Filmus and Noam Lifshitz and Dor Minzer and Elchanan Mossel},
title = {AND Testing and Robust Judgement Aggregation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {239-238},
doi = {10.1145/3357713.3384254},
year = {2020},
}
Publisher's Version
STOC '20: "Weighted Min-Cut: Sequential, ..."
Weighted Min-Cut: Sequential, Cut-Query, and Streaming Algorithms
Sagnik Mukhopadhyay and Danupon Nanongkai
(KTH, Sweden)
@InProceedings{STOC20p547,
author = {Sagnik Mukhopadhyay and Danupon Nanongkai},
title = {Weighted Min-Cut: Sequential, Cut-Query, and Streaming Algorithms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {547-546},
doi = {10.1145/3357713.3384334},
year = {2020},
}
Publisher's Version
STOC '20: "Approximately Stable Committee ..."
Approximately Stable Committee Selection
Zhihao Jiang, Kamesh Munagala, and Kangning Wang
(Tsinghua University, China; Duke University, USA)
@InProceedings{STOC20p505,
author = {Zhihao Jiang and Kamesh Munagala and Kangning Wang},
title = {Approximately Stable Committee Selection},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {505-504},
doi = {10.1145/3357713.3384238},
year = {2020},
}
Publisher's Version
STOC '20: "Top-𝑘-Convolution and the ..."
Top-𝑘-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum
Karl Bringmann and Vasileios Nakos
(Saarland University, Germany; MPI-INF, Germany)
@InProceedings{STOC20p1093,
author = {Karl Bringmann and Vasileios Nakos},
title = {Top-𝑘-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1093-1092},
doi = {10.1145/3357713.3384308},
year = {2020},
}
Publisher's Version
STOC '20: "Weighted Min-Cut: Sequential, ..."
Weighted Min-Cut: Sequential, Cut-Query, and Streaming Algorithms
Sagnik Mukhopadhyay and Danupon Nanongkai
(KTH, Sweden)
@InProceedings{STOC20p547,
author = {Sagnik Mukhopadhyay and Danupon Nanongkai},
title = {Weighted Min-Cut: Sequential, Cut-Query, and Streaming Algorithms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {547-546},
doi = {10.1145/3357713.3384334},
year = {2020},
}
Publisher's Version
STOC '20: "A Scaling-Invariant Algorithm ..."
A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix
Daniel Dadush, Sophie Huiberts, Bento Natura, and László A. Végh
(CWI, Netherlands; London School of Economics and Political Science, UK)
@InProceedings{STOC20p841,
author = {Daniel Dadush and Sophie Huiberts and Bento Natura and László A. Végh},
title = {A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {841-840},
doi = {10.1145/3357713.3384326},
year = {2020},
}
Publisher's Version
STOC '20: "Detecting and Counting Small ..."
Detecting and Counting Small Patterns in Planar Graphs in Subexponential Parameterized Time
Jesper Nederlof
(Utrecht University, Netherlands)
@InProceedings{STOC20p1429,
author = {Jesper Nederlof},
title = {Detecting and Counting Small Patterns in Planar Graphs in Subexponential Parameterized Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1429-1428},
doi = {10.1145/3357713.3384261},
year = {2020},
}
Publisher's Version
STOC '20: "Bipartite TSP in O(1.9999ⁿ) ..."
Bipartite TSP in O(1.9999ⁿ) Time, Assuming Quadratic Time Matrix Multiplication
Jesper Nederlof
(Utrecht University, Netherlands)
@InProceedings{STOC20p43,
author = {Jesper Nederlof},
title = {Bipartite TSP in O(1.9999ⁿ) Time, Assuming Quadratic Time Matrix Multiplication},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {43-42},
doi = {10.1145/3357713.3384264},
year = {2020},
}
Publisher's Version
STOC '20: "The Power of Factorization ..."
The Power of Factorization Mechanisms in Local and Central Differential Privacy
Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman
(University of Toronto, Canada; Northeastern University, USA)
@InProceedings{STOC20p463,
author = {Alexander Edmonds and Aleksandar Nikolov and Jonathan Ullman},
title = {The Power of Factorization Mechanisms in Local and Central Differential Privacy},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {463-462},
doi = {10.1145/3357713.3384297},
year = {2020},
}
Publisher's Version
STOC '20: "Better Secret Sharing via ..."
Better Secret Sharing via Robust Conditional Disclosure of Secrets
Benny Applebaum, Amos Beimel, Oded Nir, and Naty Peter
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel)
@InProceedings{STOC20p309,
author = {Benny Applebaum and Amos Beimel and Oded Nir and Naty Peter},
title = {Better Secret Sharing via Robust Conditional Disclosure of Secrets},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {309-308},
doi = {10.1145/3357713.3384293},
year = {2020},
}
Publisher's Version
STOC '20: "The One-Way Communication ..."
The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen
(University of Haifa, Israel; Google Research, Switzerland; EPFL, Switzerland; ETH Zurich, Switzerland)
@InProceedings{STOC20p1513,
author = {Moran Feldman and Ashkan Norouzi-Fard and Ola Svensson and Rico Zenklusen},
title = {The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1513-1512},
doi = {10.1145/3357713.3384286},
year = {2020},
}
Publisher's Version
STOC '20: "Fooling Gaussian PTFs via ..."
Fooling Gaussian PTFs via Local Hyperconcentration
Ryan O'Donnell, Rocco A. Servedio, and Li-Yang Tan
(Carnegie Mellon University, USA; Columbia University, USA; Stanford University, USA)
@InProceedings{STOC20p1303,
author = {Ryan O'Donnell and Rocco A. Servedio and Li-Yang Tan},
title = {Fooling Gaussian PTFs via Local Hyperconcentration},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1303-1302},
doi = {10.1145/3357713.3384281},
year = {2020},
}
Publisher's Version
STOC '20: "Explicit Near-Ramanujan Graphs ..."
Explicit Near-Ramanujan Graphs of Every Degree
Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes
(University of California at Berkeley, USA; Carnegie Mellon University, USA)
@InProceedings{STOC20p561,
author = {Sidhanth Mohanty and Ryan O'Donnell and Pedro Paredes},
title = {Explicit Near-Ramanujan Graphs of Every Degree},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {561-560},
doi = {10.1145/3357713.3384231},
year = {2020},
}
Publisher's Version
STOC '20: "Walking Randomly, Massively, ..."
Walking Randomly, Massively, and Efficiently
Jakub Łącki, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski
(Google Research, USA; Massachusetts Institute of Technology, USA; IBM Research, USA; University of Warsaw, Poland)
@InProceedings{STOC20p393,
author = {Jakub Łącki and Slobodan Mitrović and Krzysztof Onak and Piotr Sankowski},
title = {Walking Randomly, Massively, and Efficiently},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {393-392},
doi = {10.1145/3357713.3384303},
year = {2020},
}
Publisher's Version
STOC '20: "Positive Semidefinite Programming: ..."
Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, and Kevin Tian
(Stanford University, USA; University of Washington, USA; Microsoft Research, USA)
@InProceedings{STOC20p869,
author = {Arun Jambulapati and Yin Tat Lee and Jerry Li and Swati Padmanabhan and Kevin Tian},
title = {Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {869-868},
doi = {10.1145/3357713.3384338},
year = {2020},
}
Publisher's Version
STOC '20: "Caching with Time Windows ..."
Caching with Time Windows
Anupam Gupta, Amit Kumar, and Debmalya Panigrahi
(Carnegie Mellon University, USA; IIT Delhi, India; Duke University, USA)
@InProceedings{STOC20p1247,
author = {Anupam Gupta and Amit Kumar and Debmalya Panigrahi},
title = {Caching with Time Windows},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1247-1246},
doi = {10.1145/3357713.3384277},
year = {2020},
}
Publisher's Version
STOC '20: "Hitting Topological Minors ..."
Hitting Topological Minors Is FPT
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi
(University of Bergen, Norway; University of California at Santa Barbara, USA; IIT Hyderabad, India; IMSc, India; Ben-Gurion University of the Negev, Israel)
@InProceedings{STOC20p1457,
author = {Fedor V. Fomin and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh and Meirav Zehavi},
title = {Hitting Topological Minors Is FPT},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1457-1456},
doi = {10.1145/3357713.3384318},
year = {2020},
}
Publisher's Version
STOC '20: "Explicit Near-Ramanujan Graphs ..."
Explicit Near-Ramanujan Graphs of Every Degree
Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes
(University of California at Berkeley, USA; Carnegie Mellon University, USA)
@InProceedings{STOC20p561,
author = {Sidhanth Mohanty and Ryan O'Donnell and Pedro Paredes},
title = {Explicit Near-Ramanujan Graphs of Every Degree},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {561-560},
doi = {10.1145/3357713.3384231},
year = {2020},
}
Publisher's Version
STOC '20: "Data Structures Meet Cryptography: ..."
Data Structures Meet Cryptography: 3SUM with Preprocessing
Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, and Vinod Vaikuntanathan
(Harvard University, USA; New York University Shanghai, China; Massachusetts Institute of Technology, USA)
@InProceedings{STOC20p323,
author = {Alexander Golovnev and Siyao Guo and Thibaut Horel and Sunoo Park and Vinod Vaikuntanathan},
title = {Data Structures Meet Cryptography: 3SUM with Preprocessing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {323-322},
doi = {10.1145/3357713.3384342},
year = {2020},
}
Publisher's Version
STOC '20: "Efficient Sampling and Counting ..."
Efficient Sampling and Counting Algorithms for the Potts Model on ℤᵈ at All Temperatures
Christian Borgs, Jennifer Chayes, Tyler Helmuth, Will Perkins, and Prasad Tetali
(University of California at Berkeley, USA; University of Bristol, UK; University of Illinois at Chicago, USA; Georgia Institute of Technology, USA)
@InProceedings{STOC20p813,
author = {Christian Borgs and Jennifer Chayes and Tyler Helmuth and Will Perkins and Prasad Tetali},
title = {Efficient Sampling and Counting Algorithms for the Potts Model on ℤᵈ at All Temperatures},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {813-812},
doi = {10.1145/3357713.3384271},
year = {2020},
}
Publisher's Version
STOC '20: "Better Secret Sharing via ..."
Better Secret Sharing via Robust Conditional Disclosure of Secrets
Benny Applebaum, Amos Beimel, Oded Nir, and Naty Peter
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel)
@InProceedings{STOC20p309,
author = {Benny Applebaum and Amos Beimel and Oded Nir and Naty Peter},
title = {Better Secret Sharing via Robust Conditional Disclosure of Secrets},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {309-308},
doi = {10.1145/3357713.3384293},
year = {2020},
}
Publisher's Version
STOC '20: "Contention Resolution without ..."
Contention Resolution without Collision Detection
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, and Seth Pettie
(Stony Brook University, USA; Bar-Ilan University, Israel; Massachusetts Institute of Technology, USA; University of Michigan, USA)
@InProceedings{STOC20p113,
author = {Michael A. Bender and Tsvi Kopelowitz and William Kuszmaul and Seth Pettie},
title = {Contention Resolution without Collision Detection},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {113-112},
doi = {10.1145/3357713.3384305},
year = {2020},
}
Publisher's Version
STOC '20: "An Exponential Time Parameterized ..."
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
Daniel Lokshtanov, Pranabendu Misra, Michał Pilipczuk, Saket Saurabh, and Meirav Zehavi
(University of California at Santa Barbara, USA; MPI-INF, Germany; University of Warsaw, Poland; IMSc, India; Ben-Gurion University of the Negev, Israel)
@InProceedings{STOC20p1443,
author = {Daniel Lokshtanov and Pranabendu Misra and Michał Pilipczuk and Saket Saurabh and Meirav Zehavi},
title = {An Exponential Time Parameterized Algorithm for Planar Disjoint Paths},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1443-1442},
doi = {10.1145/3357713.3384250},
year = {2020},
}
Publisher's Version
STOC '20: "Automating Cutting Planes ..."
Automating Cutting Planes Is NP-Hard
Mika Göös, Sajin Koroth, Ian Mertz, and Toniann Pitassi
(Stanford University, USA; Simon Fraser University, Canada; University of Toronto, Canada; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC20p71,
author = {Mika Göös and Sajin Koroth and Ian Mertz and Toniann Pitassi},
title = {Automating Cutting Planes Is NP-Hard},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {71-70},
doi = {10.1145/3357713.3384248},
year = {2020},
}
Publisher's Version
STOC '20: "Approximating Text-to-Pattern ..."
Approximating Text-to-Pattern Hamming Distances
Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat
(University of Illinois at Urbana-Champaign, USA; Bar-Ilan University, Israel)
@InProceedings{STOC20p715,
author = {Timothy M. Chan and Shay Golan and Tomasz Kociumaka and Tsvi Kopelowitz and Ely Porat},
title = {Approximating Text-to-Pattern Hamming Distances},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {715-714},
doi = {10.1145/3357713.3384266},
year = {2020},
}
Publisher's Version
STOC '20: "Separations and Equivalences ..."
Separations and Equivalences between Turnstile Streaming and Linear Sketching
John Kallaugher and Eric Price
(University of Texas at Austin, USA)
@InProceedings{STOC20p1359,
author = {John Kallaugher and Eric Price},
title = {Separations and Equivalences between Turnstile Streaming and Linear Sketching},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1359-1358},
doi = {10.1145/3357713.3384278},
year = {2020},
}
Publisher's Version
STOC '20: "New Algorithms and Hardness ..."
New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein
(University of Copenhagen, Denmark; Massachusetts Institute of Technology, USA)
@InProceedings{STOC20p169,
author = {Maximilian Probst Gutenberg and Virginia Vassilevska Williams and Nicole Wein},
title = {New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {169-168},
doi = {10.1145/3357713.3384236},
year = {2020},
}
Publisher's Version
STOC '20: "Algorithms for Heavy-Tailed ..."
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, and Nilesh Tripuraneni
(University of California at Berkeley, USA)
@InProceedings{STOC20p659,
author = {Yeshwanth Cherapanamjeri and Samuel B. Hopkins and Tarun Kathuria and Prasad Raghavendra and Nilesh Tripuraneni},
title = {Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {659-658},
doi = {10.1145/3357713.3384329},
year = {2020},
}
Publisher's Version
STOC '20: "Lifting Sum-of-Squares Lower ..."
Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4
Sidhanth Mohanty, Prasad Raghavendra, and Jeff Xu
(University of California at Berkeley, USA)
@InProceedings{STOC20p925,
author = {Sidhanth Mohanty and Prasad Raghavendra and Jeff Xu},
title = {Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {925-924},
doi = {10.1145/3357713.3384319},
year = {2020},
}
Publisher's Version
STOC '20: "Fast Hashing with Strong Concentration ..."
Fast Hashing with Strong Concentration Bounds
Anders Aamand, Jakob Bæk Tejs Knudsen, Mathias Bæk Tejs Knudsen, Peter Michael Reichstein Rasmussen, and Mikkel Thorup
(University of Copenhagen, Denmark; SupWiz, Denmark)
@InProceedings{STOC20p1401,
author = {Anders Aamand and Jakob Bæk Tejs Knudsen and Mathias Bæk Tejs Knudsen and Peter Michael Reichstein Rasmussen and Mikkel Thorup},
title = {Fast Hashing with Strong Concentration Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1401-1400},
doi = {10.1145/3357713.3384259},
year = {2020},
}
Publisher's Version
STOC '20: "Non-adaptive Adaptive Sampling ..."
Non-adaptive Adaptive Sampling on Turnstile Streams
Sepideh Mahabadi, Ilya Razenshteyn, David P. Woodruff, and Samson Zhou
(Toyota Technological Institute at Chicago, USA; Microsoft Research, USA; Carnegie Mellon University, USA)
@InProceedings{STOC20p1387,
author = {Sepideh Mahabadi and Ilya Razenshteyn and David P. Woodruff and Samson Zhou},
title = {Non-adaptive Adaptive Sampling on Turnstile Streams},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1387-1386},
doi = {10.1145/3357713.3384331},
year = {2020},
}
Publisher's Version
STOC '20: "The Program-Size Complexity ..."
The Program-Size Complexity of Self-Assembled Paths
Pierre-Étienne Meunier, Damien Regnault, and Damien Woods
(Maynooth University, Ireland; University of Évry, France; University of Paris-Saclay, France)
@InProceedings{STOC20p799,
author = {Pierre-Étienne Meunier and Damien Regnault and Damien Woods},
title = {The Program-Size Complexity of Self-Assembled Paths},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {799-798},
doi = {10.1145/3357713.3384263},
year = {2020},
}
Publisher's Version
STOC '20: "Strong Average-Case Lower ..."
Strong Average-Case Lower Bounds from Non-trivial Derandomization
Lijie Chen and Hanlin Ren
(Massachusetts Institute of Technology, USA; Tsinghua University, China)
@InProceedings{STOC20p1471,
author = {Lijie Chen and Hanlin Ren},
title = {Strong Average-Case Lower Bounds from Non-trivial Derandomization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1471-1470},
doi = {10.1145/3357713.3384279},
year = {2020},
}
Publisher's Version
STOC '20: "Arikan Meets Shannon: Polar ..."
Arikan Meets Shannon: Polar Codes with Near-Optimal Convergence to Channel Capacity
Venkatesan Guruswami, Andrii Riazanov, and Min Ye
(Carnegie Mellon University, USA; Tsinghua-Berkeley Shenzhen Institute, China)
@InProceedings{STOC20p603,
author = {Venkatesan Guruswami and Andrii Riazanov and Min Ye},
title = {Arikan Meets Shannon: Polar Codes with Near-Optimal Convergence to Channel Capacity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {603-602},
doi = {10.1145/3357713.3384323},
year = {2020},
}
Publisher's Version
STOC '20: "How to Lose at Monte Carlo: ..."
How to Lose at Monte Carlo: A Simple Dynamical System Whose Typical Statistical Behavior Is Non-computable
Cristobal Rojas and Michael Yampolsky
(Andrés Bello National University, Chile; University of Toronto, Canada)
@InProceedings{STOC20p1177,
author = {Cristobal Rojas and Michael Yampolsky},
title = {How to Lose at Monte Carlo: A Simple Dynamical System Whose Typical Statistical Behavior Is Non-computable},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1177-1176},
doi = {10.1145/3357713.3384237},
year = {2020},
}
Publisher's Version
STOC '20: "Constant Girth Approximation ..."
Constant Girth Approximation for Directed Graphs in Subquadratic Time
Shiri Chechik, Yang P. Liu, Omer Rotem, and Aaron Sidford
(Tel Aviv University, Israel; Stanford University, USA)
@InProceedings{STOC20p1121,
author = {Shiri Chechik and Yang P. Liu and Omer Rotem and Aaron Sidford},
title = {Constant Girth Approximation for Directed Graphs in Subquadratic Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1121-1120},
doi = {10.1145/3357713.3384330},
year = {2020},
}
Publisher's Version
STOC '20: "Fully-Dynamic Planarity Testing ..."
Fully-Dynamic Planarity Testing in Polylogarithmic Time
Jacob Holm and Eva Rotenberg
(University of Copenhagen, Denmark; DTU, Denmark)
@InProceedings{STOC20p183,
author = {Jacob Holm and Eva Rotenberg},
title = {Fully-Dynamic Planarity Testing in Polylogarithmic Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {183-182},
doi = {10.1145/3357713.3384249},
year = {2020},
}
Publisher's Version
STOC '20: "Polylogarithmic-Time Deterministic ..."
Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
Václav Rozhoň and Mohsen Ghaffari
(ETH Zurich, Switzerland)
@InProceedings{STOC20p379,
author = {Václav Rozhoň and Mohsen Ghaffari},
title = {Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {379-378},
doi = {10.1145/3357713.3384298},
year = {2020},
}
Publisher's Version
STOC '20: "Does Preprocessing Help in ..."
Does Preprocessing Help in Fast Sequence Comparisons?
Elazar Goldenberg, Aviad Rubinstein, and Barna Saha
(Academic College of Tel Aviv-Yaffo, Israel; Stanford University, USA; University of California at Berkeley, USA)
@InProceedings{STOC20p729,
author = {Elazar Goldenberg and Aviad Rubinstein and Barna Saha},
title = {Does Preprocessing Help in Fast Sequence Comparisons?},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {729-728},
doi = {10.1145/3357713.3384300},
year = {2020},
}
Publisher's Version
STOC '20: "Constant-Factor Approximation ..."
Constant-Factor Approximation of Near-Linear Edit Distance in Near-Linear Time
Joshua Brakensiek and Aviad Rubinstein
(Stanford University, USA)
@InProceedings{STOC20p757,
author = {Joshua Brakensiek and Aviad Rubinstein},
title = {Constant-Factor Approximation of Near-Linear Edit Distance in Near-Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {757-756},
doi = {10.1145/3357713.3384282},
year = {2020},
}
Publisher's Version
STOC '20: "Efficient Construction of ..."
Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths
Nairen Cao, Jeremy T. Fineman, and Katina Russell
(Georgetown University, USA)
@InProceedings{STOC20p365,
author = {Nairen Cao and Jeremy T. Fineman and Katina Russell},
title = {Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {365-364},
doi = {10.1145/3357713.3384270},
year = {2020},
}
Publisher's Version
STOC '20: "Does Preprocessing Help in ..."
Does Preprocessing Help in Fast Sequence Comparisons?
Elazar Goldenberg, Aviad Rubinstein, and Barna Saha
(Academic College of Tel Aviv-Yaffo, Israel; Stanford University, USA; University of California at Berkeley, USA)
@InProceedings{STOC20p729,
author = {Elazar Goldenberg and Aviad Rubinstein and Barna Saha},
title = {Does Preprocessing Help in Fast Sequence Comparisons?},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {729-728},
doi = {10.1145/3357713.3384300},
year = {2020},
}
Publisher's Version
STOC '20: "Constant Factor Approximations ..."
Constant Factor Approximations to Edit Distance on Far Input Pairs in Nearly Linear Time
Michal Koucký and Michael Saks
(Charles University in Prague, Czechia; Rutgers University, USA)
@InProceedings{STOC20p771,
author = {Michal Koucký and Michael Saks},
title = {Constant Factor Approximations to Edit Distance on Far Input Pairs in Nearly Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {771-770},
doi = {10.1145/3357713.3384307},
year = {2020},
}
Publisher's Version
STOC '20: "Walking Randomly, Massively, ..."
Walking Randomly, Massively, and Efficiently
Jakub Łącki, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski
(Google Research, USA; Massachusetts Institute of Technology, USA; IBM Research, USA; University of Warsaw, Poland)
@InProceedings{STOC20p393,
author = {Jakub Łącki and Slobodan Mitrović and Krzysztof Onak and Piotr Sankowski},
title = {Walking Randomly, Massively, and Efficiently},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {393-392},
doi = {10.1145/3357713.3384303},
year = {2020},
}
Publisher's Version
STOC '20: "An Exponential Time Parameterized ..."
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
Daniel Lokshtanov, Pranabendu Misra, Michał Pilipczuk, Saket Saurabh, and Meirav Zehavi
(University of California at Santa Barbara, USA; MPI-INF, Germany; University of Warsaw, Poland; IMSc, India; Ben-Gurion University of the Negev, Israel)
@InProceedings{STOC20p1443,
author = {Daniel Lokshtanov and Pranabendu Misra and Michał Pilipczuk and Saket Saurabh and Meirav Zehavi},
title = {An Exponential Time Parameterized Algorithm for Planar Disjoint Paths},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1443-1442},
doi = {10.1145/3357713.3384250},
year = {2020},
}
Publisher's Version
STOC '20: "Hitting Topological Minors ..."
Hitting Topological Minors Is FPT
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi
(University of Bergen, Norway; University of California at Santa Barbara, USA; IIT Hyderabad, India; IMSc, India; Ben-Gurion University of the Negev, Israel)
@InProceedings{STOC20p1457,
author = {Fedor V. Fomin and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh and Meirav Zehavi},
title = {Hitting Topological Minors Is FPT},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1457-1456},
doi = {10.1145/3357713.3384318},
year = {2020},
}
Publisher's Version
STOC '20: "Near-Optimal Fully Dynamic ..."
Near-Optimal Fully Dynamic Densest Subgraph
Saurabh Sawlani and Junxing Wang
(Georgia Institute of Technology, USA; Carnegie Mellon University, USA)
@InProceedings{STOC20p197,
author = {Saurabh Sawlani and Junxing Wang},
title = {Near-Optimal Fully Dynamic Densest Subgraph},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {197-196},
doi = {10.1145/3357713.3384327},
year = {2020},
}
Publisher's Version
STOC '20: "Separating the Communication ..."
Separating the Communication Complexity of Truthful and Non-truthful Combinatorial Auctions
Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, and S. Matthew Weinberg
(Rutgers University, USA; Princeton University, USA)
@InProceedings{STOC20p1191,
author = {Sepehr Assadi and Hrishikesh Khandeparkar and Raghuvansh R. Saxena and S. Matthew Weinberg},
title = {Separating the Communication Complexity of Truthful and Non-truthful Combinatorial Auctions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1191-1190},
doi = {10.1145/3357713.3384267},
year = {2020},
}
Publisher's Version
STOC '20: "Interactive Error Resilience ..."
Interactive Error Resilience beyond 2/7
Klim Efremenko, Gillat Kol, and Raghuvansh R. Saxena
(Ben-Gurion University of the Negev, Israel; Princeton University, USA)
@InProceedings{STOC20p617,
author = {Klim Efremenko and Gillat Kol and Raghuvansh R. Saxena},
title = {Interactive Error Resilience beyond 2/7},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {617-616},
doi = {10.1145/3357713.3384320},
year = {2020},
}
Publisher's Version
STOC '20: "Interactive Shallow Clifford ..."
Interactive Shallow Clifford Circuits: Quantum Advantage against NC¹ and Beyond
Daniel Grier and Luke Schaeffer
(University of Waterloo, Canada)
@InProceedings{STOC20p967,
author = {Daniel Grier and Luke Schaeffer},
title = {Interactive Shallow Clifford Circuits: Quantum Advantage against NC¹ and Beyond},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {967-966},
doi = {10.1145/3357713.3384332},
year = {2020},
}
Publisher's Version
STOC '20: "Dynamic Algorithms for LIS ..."
Dynamic Algorithms for LIS and Distance to Monotonicity
Michael Mitzenmacher and Saeed Seddighin
(Harvard University, USA)
@InProceedings{STOC20p743,
author = {Michael Mitzenmacher and Saeed Seddighin},
title = {Dynamic Algorithms for LIS and Distance to Monotonicity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {743-742},
doi = {10.1145/3357713.3384240},
year = {2020},
}
Publisher's Version
STOC '20: "Fooling Gaussian PTFs via ..."
Fooling Gaussian PTFs via Local Hyperconcentration
Ryan O'Donnell, Rocco A. Servedio, and Li-Yang Tan
(Carnegie Mellon University, USA; Columbia University, USA; Stanford University, USA)
@InProceedings{STOC20p1303,
author = {Ryan O'Donnell and Rocco A. Servedio and Li-Yang Tan},
title = {Fooling Gaussian PTFs via Local Hyperconcentration},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1303-1302},
doi = {10.1145/3357713.3384281},
year = {2020},
}
Publisher's Version
STOC '20: "Testing Noisy Linear Functions ..."
Testing Noisy Linear Functions for Sparsity
Xue Chen, Anindya De, and Rocco A. Servedio
(Northwestern University, USA; University of Pennsylvania, USA; Columbia University, USA)
@InProceedings{STOC20p673,
author = {Xue Chen and Anindya De and Rocco A. Servedio},
title = {Testing Noisy Linear Functions for Sparsity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {673-672},
doi = {10.1145/3357713.3384239},
year = {2020},
}
Publisher's Version
STOC '20: "Optimally Resilient Codes ..."
Optimally Resilient Codes for List-Decoding from Insertions and Deletions
Venkatesan Guruswami, Bernhard Haeupler, and Amirbehshad Shahrasbi
(Carnegie Mellon University, USA)
@InProceedings{STOC20p575,
author = {Venkatesan Guruswami and Bernhard Haeupler and Amirbehshad Shahrasbi},
title = {Optimally Resilient Codes for List-Decoding from Insertions and Deletions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {575-574},
doi = {10.1145/3357713.3384262},
year = {2020},
}
Publisher's Version
STOC '20: "Combinatorial List-Decoding ..."
Combinatorial List-Decoding of Reed-Solomon Codes beyond the Johnson Radius
Chong Shangguan and Itzhak Tamo
(Tel Aviv University, Israel)
@InProceedings{STOC20p589,
author = {Chong Shangguan and Itzhak Tamo},
title = {Combinatorial List-Decoding of Reed-Solomon Codes beyond the Johnson Radius},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {589-588},
doi = {10.1145/3357713.3384295},
year = {2020},
}
Publisher's Version
STOC '20: "Post-quantum Zero Knowledge ..."
Post-quantum Zero Knowledge in Constant Rounds
Nir Bitansky and Omri Shmueli
(Tel Aviv University, Israel)
@InProceedings{STOC20p295,
author = {Nir Bitansky and Omri Shmueli},
title = {Post-quantum Zero Knowledge in Constant Rounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {295-294},
doi = {10.1145/3357713.3384324},
year = {2020},
}
Publisher's Version
STOC '20: "Constant Girth Approximation ..."
Constant Girth Approximation for Directed Graphs in Subquadratic Time
Shiri Chechik, Yang P. Liu, Omer Rotem, and Aaron Sidford
(Tel Aviv University, Israel; Stanford University, USA)
@InProceedings{STOC20p1121,
author = {Shiri Chechik and Yang P. Liu and Omer Rotem and Aaron Sidford},
title = {Constant Girth Approximation for Directed Graphs in Subquadratic Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1121-1120},
doi = {10.1145/3357713.3384330},
year = {2020},
}
Publisher's Version
STOC '20: "Solving Tall Dense Linear ..."
Solving Tall Dense Linear Programs in Nearly Linear Time
Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song
(KTH, Sweden; University of Washington, USA; Microsoft Research, USA; Stanford University, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA)
@InProceedings{STOC20p855,
author = {Jan van den Brand and Yin Tat Lee and Aaron Sidford and Zhao Song},
title = {Solving Tall Dense Linear Programs in Nearly Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {855-854},
doi = {10.1145/3357713.3384309},
year = {2020},
}
Publisher's Version
STOC '20: "Faster Energy Maximization ..."
Faster Energy Maximization for Faster Maximum Flow
Yang P. Liu and Aaron Sidford
(Stanford University, USA)
@InProceedings{STOC20p883,
author = {Yang P. Liu and Aaron Sidford},
title = {Faster Energy Maximization for Faster Maximum Flow},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {883-882},
doi = {10.1145/3357713.3384247},
year = {2020},
}
Publisher's Version
STOC '20: "A Lower Bound for Parallel ..."
A Lower Bound for Parallel Submodular Minimization
Eric Balkanski and Yaron Singer
(Harvard University, USA)
@InProceedings{STOC20p141,
author = {Eric Balkanski and Yaron Singer},
title = {A Lower Bound for Parallel Submodular Minimization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {141-140},
doi = {10.1145/3357713.3384287},
year = {2020},
}
Publisher's Version
STOC '20: "Online Vector Balancing and ..."
Online Vector Balancing and Geometric Discrepancy
Nikhil Bansal, Haotian Jiang, Sahil Singla, and Makrand Sinha
(Eindhoven University of Technology, Netherlands; CWI, Netherlands; University of Washington, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC20p1261,
author = {Nikhil Bansal and Haotian Jiang and Sahil Singla and Makrand Sinha},
title = {Online Vector Balancing and Geometric Discrepancy},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1261-1260},
doi = {10.1145/3357713.3384280},
year = {2020},
}
Publisher's Version
STOC '20: "Online Vector Balancing and ..."
Online Vector Balancing and Geometric Discrepancy
Nikhil Bansal, Haotian Jiang, Sahil Singla, and Makrand Sinha
(Eindhoven University of Technology, Netherlands; CWI, Netherlands; University of Washington, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC20p1261,
author = {Nikhil Bansal and Haotian Jiang and Sahil Singla and Makrand Sinha},
title = {Online Vector Balancing and Geometric Discrepancy},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1261-1260},
doi = {10.1145/3357713.3384280},
year = {2020},
}
Publisher's Version
STOC '20: "(Semi)Algebraic Proofs over ..."
(Semi)Algebraic Proofs over {±1} Variables
Dmitry Sokolov
(St. Petersburg State University, Russia; Steklov Institute of Mathematics at St. Petersburg, Russia)
@InProceedings{STOC20p85,
author = {Dmitry Sokolov},
title = {(Semi)Algebraic Proofs over {±1} Variables},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {85-84},
doi = {10.1145/3357713.3384288},
year = {2020},
}
Publisher's Version
STOC '20: "Classical Algorithms, Correlation ..."
Classical Algorithms, Correlation Decay, and Complex Zeros of Partition Functions of Quantum Many-Body Systems
Aram W. Harrow, Saeed Mehraban, and Mehdi Soleimanifar
(Massachusetts Institute of Technology, USA; California Institute of Technology, USA)
@InProceedings{STOC20p407,
author = {Aram W. Harrow and Saeed Mehraban and Mehdi Soleimanifar},
title = {Classical Algorithms, Correlation Decay, and Complex Zeros of Partition Functions of Quantum Many-Body Systems},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {407-406},
doi = {10.1145/3357713.3384322},
year = {2020},
}
Publisher's Version
STOC '20: "An Improved Cutting Plane ..."
An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games, and Its Applications
Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong
(University of Washington, USA; Microsoft Research, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA)
@InProceedings{STOC20p1037,
author = {Haotian Jiang and Yin Tat Lee and Zhao Song and Sam Chiu-wai Wong},
title = {An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games, and Its Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1037-1036},
doi = {10.1145/3357713.3384284},
year = {2020},
}
Publisher's Version
STOC '20: "Learning Mixtures of Linear ..."
Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
Sitan Chen, Jerry Li, and Zhao Song
(Massachusetts Institute of Technology, USA; Microsoft Research, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC20p645,
author = {Sitan Chen and Jerry Li and Zhao Song},
title = {Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {645-644},
doi = {10.1145/3357713.3384333},
year = {2020},
}
Publisher's Version
STOC '20: "Solving Tall Dense Linear ..."
Solving Tall Dense Linear Programs in Nearly Linear Time
Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song
(KTH, Sweden; University of Washington, USA; Microsoft Research, USA; Stanford University, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA)
@InProceedings{STOC20p855,
author = {Jan van den Brand and Yin Tat Lee and Aaron Sidford and Zhao Song},
title = {Solving Tall Dense Linear Programs in Nearly Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {855-854},
doi = {10.1145/3357713.3384309},
year = {2020},
}
Publisher's Version
STOC '20: "A Robust Version of Hegedus’s ..."
A Robust Version of Hegedus’s Lemma, with Applications
Srikanth Srinivasan
(IIT Bombay, India)
@InProceedings{STOC20p1499,
author = {Srikanth Srinivasan},
title = {A Robust Version of Hegedus’s Lemma, with Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1499-1498},
doi = {10.1145/3357713.3384328},
year = {2020},
}
Publisher's Version
STOC '20: "All Non-trivial Variants of ..."
All Non-trivial Variants of 3-LDT Are Equivalent
Bartłomiej Dudek, Paweł Gawrychowski, and Tatiana Starikovskaya
(University of Wrocław, Poland; PSL University, France)
@InProceedings{STOC20p1079,
author = {Bartłomiej Dudek and Paweł Gawrychowski and Tatiana Starikovskaya},
title = {All Non-trivial Variants of 3-LDT Are Equivalent},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1079-1078},
doi = {10.1145/3357713.3384275},
year = {2020},
}
Publisher's Version
STOC '20: "Parallel Approximate Undirected ..."
Parallel Approximate Undirected Shortest Paths via Low Hop Emulators
Alexandr Andoni, Clifford Stein, and Peilin Zhong
(Columbia University, USA)
@InProceedings{STOC20p351,
author = {Alexandr Andoni and Clifford Stein and Peilin Zhong},
title = {Parallel Approximate Undirected Shortest Paths via Low Hop Emulators},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {351-350},
doi = {10.1145/3357713.3384321},
year = {2020},
}
Publisher's Version
STOC '20: "The One-Way Communication ..."
The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen
(University of Haifa, Israel; Google Research, Switzerland; EPFL, Switzerland; ETH Zurich, Switzerland)
@InProceedings{STOC20p1513,
author = {Moran Feldman and Ashkan Norouzi-Fard and Ola Svensson and Rico Zenklusen},
title = {The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1513-1512},
doi = {10.1145/3357713.3384286},
year = {2020},
}
Publisher's Version
STOC '20: "Private Stochastic Convex ..."
Private Stochastic Convex Optimization: Optimal Rates in Linear Time
Vitaly Feldman, Tomer Koren, and Kunal Talwar
(Google Research, USA; Tel Aviv University, Israel; Google, Israel)
@InProceedings{STOC20p477,
author = {Vitaly Feldman and Tomer Koren and Kunal Talwar},
title = {Private Stochastic Convex Optimization: Optimal Rates in Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {477-476},
doi = {10.1145/3357713.3384335},
year = {2020},
}
Publisher's Version
STOC '20: "Combinatorial List-Decoding ..."
Combinatorial List-Decoding of Reed-Solomon Codes beyond the Johnson Radius
Chong Shangguan and Itzhak Tamo
(Tel Aviv University, Israel)
@InProceedings{STOC20p589,
author = {Chong Shangguan and Itzhak Tamo},
title = {Combinatorial List-Decoding of Reed-Solomon Codes beyond the Johnson Radius},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {589-588},
doi = {10.1145/3357713.3384295},
year = {2020},
}
Publisher's Version
STOC '20: "Fooling Gaussian PTFs via ..."
Fooling Gaussian PTFs via Local Hyperconcentration
Ryan O'Donnell, Rocco A. Servedio, and Li-Yang Tan
(Carnegie Mellon University, USA; Columbia University, USA; Stanford University, USA)
@InProceedings{STOC20p1303,
author = {Ryan O'Donnell and Rocco A. Servedio and Li-Yang Tan},
title = {Fooling Gaussian PTFs via Local Hyperconcentration},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1303-1302},
doi = {10.1145/3357713.3384281},
year = {2020},
}
Publisher's Version
STOC '20: "Sampling-Based Sublinear Low-Rank ..."
Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang
(University of Texas at Austin, USA; California Institute of Technology, USA; University of Maryland, USA; University of Washington, USA)
@InProceedings{STOC20p421,
author = {Nai-Hui Chia and András Gilyén and Tongyang Li and Han-Hsuan Lin and Ewin Tang and Chunhao Wang},
title = {Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {421-420},
doi = {10.1145/3357713.3384314},
year = {2020},
}
Publisher's Version
STOC '20: "Towards a Better Understanding ..."
Towards a Better Understanding of Randomized Greedy Matching
Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang
(Shanghai University of Finance and Economics, China; University of Macau, China; University of Hong Kong, China)
@InProceedings{STOC20p1219,
author = {Zhihao Gavin Tang and Xiaowei Wu and Yuhao Zhang},
title = {Towards a Better Understanding of Randomized Greedy Matching},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1219-1218},
doi = {10.1145/3357713.3384265},
year = {2020},
}
Publisher's Version
STOC '20: "Efficient Sampling and Counting ..."
Efficient Sampling and Counting Algorithms for the Potts Model on ℤᵈ at All Temperatures
Christian Borgs, Jennifer Chayes, Tyler Helmuth, Will Perkins, and Prasad Tetali
(University of California at Berkeley, USA; University of Bristol, UK; University of Illinois at Chicago, USA; Georgia Institute of Technology, USA)
@InProceedings{STOC20p813,
author = {Christian Borgs and Jennifer Chayes and Tyler Helmuth and Will Perkins and Prasad Tetali},
title = {Efficient Sampling and Counting Algorithms for the Potts Model on ℤᵈ at All Temperatures},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {813-812},
doi = {10.1145/3357713.3384271},
year = {2020},
}
Publisher's Version
STOC '20: "Fast Hashing with Strong Concentration ..."
Fast Hashing with Strong Concentration Bounds
Anders Aamand, Jakob Bæk Tejs Knudsen, Mathias Bæk Tejs Knudsen, Peter Michael Reichstein Rasmussen, and Mikkel Thorup
(University of Copenhagen, Denmark; SupWiz, Denmark)
@InProceedings{STOC20p1401,
author = {Anders Aamand and Jakob Bæk Tejs Knudsen and Mathias Bæk Tejs Knudsen and Peter Michael Reichstein Rasmussen and Mikkel Thorup},
title = {Fast Hashing with Strong Concentration Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1401-1400},
doi = {10.1145/3357713.3384259},
year = {2020},
}
Publisher's Version
STOC '20: "Three-in-a-Tree in Near Linear ..."
Three-in-a-Tree in Near Linear Time
Kai-Yuan Lai, Hsueh-I Lu, and Mikkel Thorup
(National Taiwan University, Taiwan; University of Copenhagen, Denmark)
@InProceedings{STOC20p1415,
author = {Kai-Yuan Lai and Hsueh-I Lu and Mikkel Thorup},
title = {Three-in-a-Tree in Near Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1415-1414},
doi = {10.1145/3357713.3384235},
year = {2020},
}
Publisher's Version
STOC '20: "Positive Semidefinite Programming: ..."
Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, and Kevin Tian
(Stanford University, USA; University of Washington, USA; Microsoft Research, USA)
@InProceedings{STOC20p869,
author = {Arun Jambulapati and Yin Tat Lee and Jerry Li and Swati Padmanabhan and Kevin Tian},
title = {Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {869-868},
doi = {10.1145/3357713.3384338},
year = {2020},
}
Publisher's Version
STOC '20: "An Improved Approximation ..."
An Improved Approximation Algorithm for ATSP
Vera Traub and Jens Vygen
(University of Bonn, Germany)
@InProceedings{STOC20p1,
author = {Vera Traub and Jens Vygen},
title = {An Improved Approximation Algorithm for ATSP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1-0},
doi = {10.1145/3357713.3384233},
year = {2020},
}
Publisher's Version
STOC '20: "Reducing Path TSP to TSP ..."
Reducing Path TSP to TSP
Vera Traub, Jens Vygen, and Rico Zenklusen
(University of Bonn, Germany; ETH Zurich, Switzerland)
@InProceedings{STOC20p15,
author = {Vera Traub and Jens Vygen and Rico Zenklusen},
title = {Reducing Path TSP to TSP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {15-14},
doi = {10.1145/3357713.3384256},
year = {2020},
}
Publisher's Version
STOC '20: "Algorithms for Heavy-Tailed ..."
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, and Nilesh Tripuraneni
(University of California at Berkeley, USA)
@InProceedings{STOC20p659,
author = {Yeshwanth Cherapanamjeri and Samuel B. Hopkins and Tarun Kathuria and Prasad Raghavendra and Nilesh Tripuraneni},
title = {Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {659-658},
doi = {10.1145/3357713.3384329},
year = {2020},
}
Publisher's Version
STOC '20: "Semi-algebraic Proofs, IPS ..."
Semi-algebraic Proofs, IPS Lower Bounds, and the τ-Conjecture: Can a Natural Number Be Negative?
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, and Iddo Tzameret
(Steklov Institute of Mathematics at St. Petersburg, Russia; St. Petersburg State University, Russia; CNRS, France; University of Lille, France; Royal Holloway University of London, UK)
@InProceedings{STOC20p57,
author = {Yaroslav Alekseev and Dima Grigoriev and Edward A. Hirsch and Iddo Tzameret},
title = {Semi-algebraic Proofs, IPS Lower Bounds, and the τ-Conjecture: Can a Natural Number Be Negative?},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {57-56},
doi = {10.1145/3357713.3384245},
year = {2020},
}
Publisher's Version
STOC '20: "The Power of Factorization ..."
The Power of Factorization Mechanisms in Local and Central Differential Privacy
Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman
(University of Toronto, Canada; Northeastern University, USA)
@InProceedings{STOC20p463,
author = {Alexander Edmonds and Aleksandar Nikolov and Jonathan Ullman},
title = {The Power of Factorization Mechanisms in Local and Central Differential Privacy},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {463-462},
doi = {10.1145/3357713.3384297},
year = {2020},
}
Publisher's Version
STOC '20: "Data Structures Meet Cryptography: ..."
Data Structures Meet Cryptography: 3SUM with Preprocessing
Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, and Vinod Vaikuntanathan
(Harvard University, USA; New York University Shanghai, China; Massachusetts Institute of Technology, USA)
@InProceedings{STOC20p323,
author = {Alexander Golovnev and Siyao Guo and Thibaut Horel and Sunoo Park and Vinod Vaikuntanathan},
title = {Data Structures Meet Cryptography: 3SUM with Preprocessing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {323-322},
doi = {10.1145/3357713.3384342},
year = {2020},
}
Publisher's Version
STOC '20: "Solving Tall Dense Linear ..."
Solving Tall Dense Linear Programs in Nearly Linear Time
Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song
(KTH, Sweden; University of Washington, USA; Microsoft Research, USA; Stanford University, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA)
@InProceedings{STOC20p855,
author = {Jan van den Brand and Yin Tat Lee and Aaron Sidford and Zhao Song},
title = {Solving Tall Dense Linear Programs in Nearly Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {855-854},
doi = {10.1145/3357713.3384309},
year = {2020},
}
Publisher's Version
STOC '20: "New Algorithms and Hardness ..."
New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein
(University of Copenhagen, Denmark; Massachusetts Institute of Technology, USA)
@InProceedings{STOC20p169,
author = {Maximilian Probst Gutenberg and Virginia Vassilevska Williams and Nicole Wein},
title = {New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {169-168},
doi = {10.1145/3357713.3384236},
year = {2020},
}
Publisher's Version
STOC '20: "A Scaling-Invariant Algorithm ..."
A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix
Daniel Dadush, Sophie Huiberts, Bento Natura, and László A. Végh
(CWI, Netherlands; London School of Economics and Political Science, UK)
@InProceedings{STOC20p841,
author = {Daniel Dadush and Sophie Huiberts and Bento Natura and László A. Végh},
title = {A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {841-840},
doi = {10.1145/3357713.3384326},
year = {2020},
}
Publisher's Version
STOC '20: "Strong Self-Concordance and ..."
Strong Self-Concordance and Sampling
Aditi Laddha, Yin Tat Lee, and Santosh Vempala
(Georgia Institute of Technology, USA; University of Washington, USA; Microsoft Research, USA)
@InProceedings{STOC20p1345,
author = {Aditi Laddha and Yin Tat Lee and Santosh Vempala},
title = {Strong Self-Concordance and Sampling},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1345-1344},
doi = {10.1145/3357713.3384272},
year = {2020},
}
Publisher's Version
STOC '20: "On the Computability of Continuous ..."
On the Computability of Continuous Maximum Entropy Distributions with Applications
Jonathan Leake and Nisheeth K. Vishnoi
(KTH, Sweden; Yale University, USA)
@InProceedings{STOC20p1023,
author = {Jonathan Leake and Nisheeth K. Vishnoi},
title = {On the Computability of Continuous Maximum Entropy Distributions with Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1023-1022},
doi = {10.1145/3357713.3384302},
year = {2020},
}
Publisher's Version
STOC '20: "Coresets for Clustering in ..."
Coresets for Clustering in Euclidean Spaces: Importance Sampling Is Nearly Optimal
Lingxiao Huang and Nisheeth K. Vishnoi
(Yale University, USA)
@InProceedings{STOC20p1569,
author = {Lingxiao Huang and Nisheeth K. Vishnoi},
title = {Coresets for Clustering in Euclidean Spaces: Importance Sampling Is Nearly Optimal},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1569-1568},
doi = {10.1145/3357713.3384296},
year = {2020},
}
Publisher's Version
STOC '20: "Smoothed Complexity of Local ..."
Smoothed Complexity of Local Max-Cut and Binary Max-CSP
Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, and Xinzhi Zhang
(Columbia University, USA; Tsinghua University, China)
@InProceedings{STOC20p1163,
author = {Xi Chen and Chenghao Guo and Emmanouil V. Vlatakis-Gkaragkounis and Mihalis Yannakakis and Xinzhi Zhang},
title = {Smoothed Complexity of Local Max-Cut and Binary Max-CSP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1163-1162},
doi = {10.1145/3357713.3384325},
year = {2020},
}
Publisher's Version
STOC '20: "A Polynomial Lower Bound on ..."
A Polynomial Lower Bound on Adaptive Complexity of Submodular Maximization
Wenzheng Li, Paul Liu, and Jan Vondrák
(Stanford University, USA)
@InProceedings{STOC20p155,
author = {Wenzheng Li and Paul Liu and Jan Vondrák},
title = {A Polynomial Lower Bound on Adaptive Complexity of Submodular Maximization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {155-154},
doi = {10.1145/3357713.3384311},
year = {2020},
}
Publisher's Version
STOC '20: "An Improved Approximation ..."
An Improved Approximation Algorithm for ATSP
Vera Traub and Jens Vygen
(University of Bonn, Germany)
@InProceedings{STOC20p1,
author = {Vera Traub and Jens Vygen},
title = {An Improved Approximation Algorithm for ATSP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1-0},
doi = {10.1145/3357713.3384233},
year = {2020},
}
Publisher's Version
STOC '20: "Reducing Path TSP to TSP ..."
Reducing Path TSP to TSP
Vera Traub, Jens Vygen, and Rico Zenklusen
(University of Bonn, Germany; ETH Zurich, Switzerland)
@InProceedings{STOC20p15,
author = {Vera Traub and Jens Vygen and Rico Zenklusen},
title = {Reducing Path TSP to TSP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {15-14},
doi = {10.1145/3357713.3384256},
year = {2020},
}
Publisher's Version
STOC '20: "Rounding Dynamic Matchings ..."
Rounding Dynamic Matchings against an Adaptive Adversary
David Wajc
(Carnegie Mellon University, USA)
@InProceedings{STOC20p211,
author = {David Wajc},
title = {Rounding Dynamic Matchings against an Adaptive Adversary},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {211-210},
doi = {10.1145/3357713.3384258},
year = {2020},
}
Publisher's Version
STOC '20: "Exploration with Limited Memory: ..."
Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-armed Bandits
Sepehr Assadi and Chen Wang
(Rutgers University, USA)
@InProceedings{STOC20p1373,
author = {Sepehr Assadi and Chen Wang},
title = {Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-armed Bandits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1373-1372},
doi = {10.1145/3357713.3384341},
year = {2020},
}
Publisher's Version
STOC '20: "Sampling-Based Sublinear Low-Rank ..."
Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang
(University of Texas at Austin, USA; California Institute of Technology, USA; University of Maryland, USA; University of Washington, USA)
@InProceedings{STOC20p421,
author = {Nai-Hui Chia and András Gilyén and Tongyang Li and Han-Hsuan Lin and Ewin Tang and Chunhao Wang},
title = {Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {421-420},
doi = {10.1145/3357713.3384314},
year = {2020},
}
Publisher's Version
STOC '20: "Near-Optimal Fully Dynamic ..."
Near-Optimal Fully Dynamic Densest Subgraph
Saurabh Sawlani and Junxing Wang
(Georgia Institute of Technology, USA; Carnegie Mellon University, USA)
@InProceedings{STOC20p197,
author = {Saurabh Sawlani and Junxing Wang},
title = {Near-Optimal Fully Dynamic Densest Subgraph},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {197-196},
doi = {10.1145/3357713.3384327},
year = {2020},
}
Publisher's Version
STOC '20: "Approximately Stable Committee ..."
Approximately Stable Committee Selection
Zhihao Jiang, Kamesh Munagala, and Kangning Wang
(Tsinghua University, China; Duke University, USA)
@InProceedings{STOC20p505,
author = {Zhihao Jiang and Kamesh Munagala and Kangning Wang},
title = {Approximately Stable Committee Selection},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {505-504},
doi = {10.1145/3357713.3384238},
year = {2020},
}
Publisher's Version
STOC '20: "New Algorithms and Hardness ..."
New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein
(University of Copenhagen, Denmark; Massachusetts Institute of Technology, USA)
@InProceedings{STOC20p169,
author = {Maximilian Probst Gutenberg and Virginia Vassilevska Williams and Nicole Wein},
title = {New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {169-168},
doi = {10.1145/3357713.3384236},
year = {2020},
}
Publisher's Version
STOC '20: "Separating the Communication ..."
Separating the Communication Complexity of Truthful and Non-truthful Combinatorial Auctions
Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, and S. Matthew Weinberg
(Rutgers University, USA; Princeton University, USA)
@InProceedings{STOC20p1191,
author = {Sepehr Assadi and Hrishikesh Khandeparkar and Raghuvansh R. Saxena and S. Matthew Weinberg},
title = {Separating the Communication Complexity of Truthful and Non-truthful Combinatorial Auctions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1191-1190},
doi = {10.1145/3357713.3384267},
year = {2020},
}
Publisher's Version
STOC '20: "Sharp Threshold Results for ..."
Sharp Threshold Results for Computational Complexity
Lijie Chen, Ce Jin, and R. Ryan Williams
(Massachusetts Institute of Technology, USA; Tsinghua University, China)
@InProceedings{STOC20p1485,
author = {Lijie Chen and Ce Jin and R. Ryan Williams},
title = {Sharp Threshold Results for Computational Complexity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1485-1484},
doi = {10.1145/3357713.3384283},
year = {2020},
}
Publisher's Version
STOC '20: "An Improved Cutting Plane ..."
An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games, and Its Applications
Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong
(University of Washington, USA; Microsoft Research, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA)
@InProceedings{STOC20p1037,
author = {Haotian Jiang and Yin Tat Lee and Zhao Song and Sam Chiu-wai Wong},
title = {An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games, and Its Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1037-1036},
doi = {10.1145/3357713.3384284},
year = {2020},
}
Publisher's Version
STOC '20: "Non-adaptive Adaptive Sampling ..."
Non-adaptive Adaptive Sampling on Turnstile Streams
Sepideh Mahabadi, Ilya Razenshteyn, David P. Woodruff, and Samson Zhou
(Toyota Technological Institute at Chicago, USA; Microsoft Research, USA; Carnegie Mellon University, USA)
@InProceedings{STOC20p1387,
author = {Sepideh Mahabadi and Ilya Razenshteyn and David P. Woodruff and Samson Zhou},
title = {Non-adaptive Adaptive Sampling on Turnstile Streams},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1387-1386},
doi = {10.1145/3357713.3384331},
year = {2020},
}
Publisher's Version
STOC '20: "The Program-Size Complexity ..."
The Program-Size Complexity of Self-Assembled Paths
Pierre-Étienne Meunier, Damien Regnault, and Damien Woods
(Maynooth University, Ireland; University of Évry, France; University of Paris-Saclay, France)
@InProceedings{STOC20p799,
author = {Pierre-Étienne Meunier and Damien Regnault and Damien Woods},
title = {The Program-Size Complexity of Self-Assembled Paths},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {799-798},
doi = {10.1145/3357713.3384263},
year = {2020},
}
Publisher's Version
STOC '20: "Decision List Compression ..."
Decision List Compression by Mild Random Restrictions
Shachar Lovett, Kewen Wu, and Jiapeng Zhang
(University of California at San Diego, USA; Peking University, China; Harvard University, USA)
@InProceedings{STOC20p267,
author = {Shachar Lovett and Kewen Wu and Jiapeng Zhang},
title = {Decision List Compression by Mild Random Restrictions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {267-266},
doi = {10.1145/3357713.3384241},
year = {2020},
}
Publisher's Version
STOC '20: "Improved Bounds for the Sunflower ..."
Improved Bounds for the Sunflower Lemma
Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang
(Princeton University, USA; University of California at San Diego, USA; Peking University, China; Harvard University, USA)
@InProceedings{STOC20p687,
author = {Ryan Alweiss and Shachar Lovett and Kewen Wu and Jiapeng Zhang},
title = {Improved Bounds for the Sunflower Lemma},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {687-686},
doi = {10.1145/3357713.3384234},
year = {2020},
}
Publisher's Version
STOC '20: "Towards a Better Understanding ..."
Towards a Better Understanding of Randomized Greedy Matching
Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang
(Shanghai University of Finance and Economics, China; University of Macau, China; University of Hong Kong, China)
@InProceedings{STOC20p1219,
author = {Zhihao Gavin Tang and Xiaowei Wu and Yuhao Zhang},
title = {Towards a Better Understanding of Randomized Greedy Matching},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1219-1218},
doi = {10.1145/3357713.3384265},
year = {2020},
}
Publisher's Version
STOC '20: "Lifting Sum-of-Squares Lower ..."
Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4
Sidhanth Mohanty, Prasad Raghavendra, and Jeff Xu
(University of California at Berkeley, USA)
@InProceedings{STOC20p925,
author = {Sidhanth Mohanty and Prasad Raghavendra and Jeff Xu},
title = {Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {925-924},
doi = {10.1145/3357713.3384319},
year = {2020},
}
Publisher's Version
STOC '20: "How to Lose at Monte Carlo: ..."
How to Lose at Monte Carlo: A Simple Dynamical System Whose Typical Statistical Behavior Is Non-computable
Cristobal Rojas and Michael Yampolsky
(Andrés Bello National University, Chile; University of Toronto, Canada)
@InProceedings{STOC20p1177,
author = {Cristobal Rojas and Michael Yampolsky},
title = {How to Lose at Monte Carlo: A Simple Dynamical System Whose Typical Statistical Behavior Is Non-computable},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1177-1176},
doi = {10.1145/3357713.3384237},
year = {2020},
}
Publisher's Version
STOC '20: "Smoothed Complexity of Local ..."
Smoothed Complexity of Local Max-Cut and Binary Max-CSP
Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, and Xinzhi Zhang
(Columbia University, USA; Tsinghua University, China)
@InProceedings{STOC20p1163,
author = {Xi Chen and Chenghao Guo and Emmanouil V. Vlatakis-Gkaragkounis and Mihalis Yannakakis and Xinzhi Zhang},
title = {Smoothed Complexity of Local Max-Cut and Binary Max-CSP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1163-1162},
doi = {10.1145/3357713.3384325},
year = {2020},
}
Publisher's Version
STOC '20: "Arikan Meets Shannon: Polar ..."
Arikan Meets Shannon: Polar Codes with Near-Optimal Convergence to Channel Capacity
Venkatesan Guruswami, Andrii Riazanov, and Min Ye
(Carnegie Mellon University, USA; Tsinghua-Berkeley Shenzhen Institute, China)
@InProceedings{STOC20p603,
author = {Venkatesan Guruswami and Andrii Riazanov and Min Ye},
title = {Arikan Meets Shannon: Polar Codes with Near-Optimal Convergence to Channel Capacity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {603-602},
doi = {10.1145/3357713.3384323},
year = {2020},
}
Publisher's Version
STOC '20: "Fast Sampling and Counting ..."
Fast Sampling and Counting 𝑘-SAT Solutions in the Local Lemma Regime
Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang
(Nanjing University, China; University of Edinburgh, UK; Shanghai Jiao Tong University, China)
@InProceedings{STOC20p939,
author = {Weiming Feng and Heng Guo and Yitong Yin and Chihao Zhang},
title = {Fast Sampling and Counting 𝑘-SAT Solutions in the Local Lemma Regime},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {939-938},
doi = {10.1145/3357713.3384255},
year = {2020},
}
Publisher's Version
STOC '20: "Nearly Optimal Static Las ..."
Nearly Optimal Static Las Vegas Succinct Dictionary
Huacheng Yu
(Princeton University, USA)
@InProceedings{STOC20p1541,
author = {Huacheng Yu},
title = {Nearly Optimal Static Las Vegas Succinct Dictionary},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1541-1540},
doi = {10.1145/3357713.3384274},
year = {2020},
}
Publisher's Version
STOC '20: "Lower Bound for Succinct Range ..."
Lower Bound for Succinct Range Minimum Query
Mingmou Liu and Huacheng Yu
(Nanjing University, China; Princeton University, USA)
@InProceedings{STOC20p1555,
author = {Mingmou Liu and Huacheng Yu},
title = {Lower Bound for Succinct Range Minimum Query},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1555-1554},
doi = {10.1145/3357713.3384260},
year = {2020},
}
Publisher's Version
STOC '20: "An Exponential Time Parameterized ..."
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
Daniel Lokshtanov, Pranabendu Misra, Michał Pilipczuk, Saket Saurabh, and Meirav Zehavi
(University of California at Santa Barbara, USA; MPI-INF, Germany; University of Warsaw, Poland; IMSc, India; Ben-Gurion University of the Negev, Israel)
@InProceedings{STOC20p1443,
author = {Daniel Lokshtanov and Pranabendu Misra and Michał Pilipczuk and Saket Saurabh and Meirav Zehavi},
title = {An Exponential Time Parameterized Algorithm for Planar Disjoint Paths},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1443-1442},
doi = {10.1145/3357713.3384250},
year = {2020},
}
Publisher's Version
STOC '20: "Hitting Topological Minors ..."
Hitting Topological Minors Is FPT
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi
(University of Bergen, Norway; University of California at Santa Barbara, USA; IIT Hyderabad, India; IMSc, India; Ben-Gurion University of the Negev, Israel)
@InProceedings{STOC20p1457,
author = {Fedor V. Fomin and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh and Meirav Zehavi},
title = {Hitting Topological Minors Is FPT},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1457-1456},
doi = {10.1145/3357713.3384318},
year = {2020},
}
Publisher's Version
STOC '20: "The One-Way Communication ..."
The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen
(University of Haifa, Israel; Google Research, Switzerland; EPFL, Switzerland; ETH Zurich, Switzerland)
@InProceedings{STOC20p1513,
author = {Moran Feldman and Ashkan Norouzi-Fard and Ola Svensson and Rico Zenklusen},
title = {The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1513-1512},
doi = {10.1145/3357713.3384286},
year = {2020},
}
Publisher's Version
STOC '20: "Reducing Path TSP to TSP ..."
Reducing Path TSP to TSP
Vera Traub, Jens Vygen, and Rico Zenklusen
(University of Bonn, Germany; ETH Zurich, Switzerland)
@InProceedings{STOC20p15,
author = {Vera Traub and Jens Vygen and Rico Zenklusen},
title = {Reducing Path TSP to TSP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {15-14},
doi = {10.1145/3357713.3384256},
year = {2020},
}
Publisher's Version
STOC '20: "One-Shot Signatures and Applications ..."
One-Shot Signatures and Applications to Hybrid Quantum/Classical Authentication
Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry
(Princeton University, USA; City University of New York, USA; University of Edinburgh, UK)
@InProceedings{STOC20p281,
author = {Ryan Amos and Marios Georgiou and Aggelos Kiayias and Mark Zhandry},
title = {One-Shot Signatures and Applications to Hybrid Quantum/Classical Authentication},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {281-280},
doi = {10.1145/3357713.3384304},
year = {2020},
}
Publisher's Version
STOC '20: "Fast Sampling and Counting ..."
Fast Sampling and Counting 𝑘-SAT Solutions in the Local Lemma Regime
Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang
(Nanjing University, China; University of Edinburgh, UK; Shanghai Jiao Tong University, China)
@InProceedings{STOC20p939,
author = {Weiming Feng and Heng Guo and Yitong Yin and Chihao Zhang},
title = {Fast Sampling and Counting 𝑘-SAT Solutions in the Local Lemma Regime},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {939-938},
doi = {10.1145/3357713.3384255},
year = {2020},
}
Publisher's Version
STOC '20: "Decision List Compression ..."
Decision List Compression by Mild Random Restrictions
Shachar Lovett, Kewen Wu, and Jiapeng Zhang
(University of California at San Diego, USA; Peking University, China; Harvard University, USA)
@InProceedings{STOC20p267,
author = {Shachar Lovett and Kewen Wu and Jiapeng Zhang},
title = {Decision List Compression by Mild Random Restrictions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {267-266},
doi = {10.1145/3357713.3384241},
year = {2020},
}
Publisher's Version
STOC '20: "Improved Bounds for the Sunflower ..."
Improved Bounds for the Sunflower Lemma
Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang
(Princeton University, USA; University of California at San Diego, USA; Peking University, China; Harvard University, USA)
@InProceedings{STOC20p687,
author = {Ryan Alweiss and Shachar Lovett and Kewen Wu and Jiapeng Zhang},
title = {Improved Bounds for the Sunflower Lemma},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {687-686},
doi = {10.1145/3357713.3384234},
year = {2020},
}
Publisher's Version
STOC '20: "Online Primal Dual Meets Online ..."
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue
Zhiyi Huang and Qiankun Zhang
(University of Hong Kong, China)
@InProceedings{STOC20p1275,
author = {Zhiyi Huang and Qiankun Zhang},
title = {Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1275-1274},
doi = {10.1145/3357713.3384294},
year = {2020},
}
Publisher's Version
STOC '20: "Smoothed Complexity of Local ..."
Smoothed Complexity of Local Max-Cut and Binary Max-CSP
Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, and Xinzhi Zhang
(Columbia University, USA; Tsinghua University, China)
@InProceedings{STOC20p1163,
author = {Xi Chen and Chenghao Guo and Emmanouil V. Vlatakis-Gkaragkounis and Mihalis Yannakakis and Xinzhi Zhang},
title = {Smoothed Complexity of Local Max-Cut and Binary Max-CSP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1163-1162},
doi = {10.1145/3357713.3384325},
year = {2020},
}
Publisher's Version
STOC '20: "Towards a Better Understanding ..."
Towards a Better Understanding of Randomized Greedy Matching
Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang
(Shanghai University of Finance and Economics, China; University of Macau, China; University of Hong Kong, China)
@InProceedings{STOC20p1219,
author = {Zhihao Gavin Tang and Xiaowei Wu and Yuhao Zhang},
title = {Towards a Better Understanding of Randomized Greedy Matching},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1219-1218},
doi = {10.1145/3357713.3384265},
year = {2020},
}
Publisher's Version
STOC '20: "Parallel Approximate Undirected ..."
Parallel Approximate Undirected Shortest Paths via Low Hop Emulators
Alexandr Andoni, Clifford Stein, and Peilin Zhong
(Columbia University, USA)
@InProceedings{STOC20p351,
author = {Alexandr Andoni and Clifford Stein and Peilin Zhong},
title = {Parallel Approximate Undirected Shortest Paths via Low Hop Emulators},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {351-350},
doi = {10.1145/3357713.3384321},
year = {2020},
}
Publisher's Version
STOC '20: "A Spectral Approach to Network ..."
A Spectral Approach to Network Design
Lap Chi Lau and Hong Zhou
(University of Waterloo, Canada)
@InProceedings{STOC20p911,
author = {Lap Chi Lau and Hong Zhou},
title = {A Spectral Approach to Network Design},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {911-910},
doi = {10.1145/3357713.3384313},
year = {2020},
}
Publisher's Version
STOC '20: "Non-adaptive Adaptive Sampling ..."
Non-adaptive Adaptive Sampling on Turnstile Streams
Sepideh Mahabadi, Ilya Razenshteyn, David P. Woodruff, and Samson Zhou
(Toyota Technological Institute at Chicago, USA; Microsoft Research, USA; Carnegie Mellon University, USA)
@InProceedings{STOC20p1387,
author = {Sepideh Mahabadi and Ilya Razenshteyn and David P. Woodruff and Samson Zhou},
title = {Non-adaptive Adaptive Sampling on Turnstile Streams},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1387-1386},
doi = {10.1145/3357713.3384331},
year = {2020},
}
Publisher's Version
STOC '20: "QCSP Monsters and the Demise ..."
QCSP Monsters and the Demise of the Chen Conjecture
Dmitriy Zhuk and Barnaby Martin
(Moscow State University, Russia; Durham University, UK)
@InProceedings{STOC20p99,
author = {Dmitriy Zhuk and Barnaby Martin},
title = {QCSP Monsters and the Demise of the Chen Conjecture},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {99-98},
doi = {10.1145/3357713.3384232},
year = {2020},
}
Publisher's Version
STOC '20: "XOR Lemmas for Resilient Functions ..."
XOR Lemmas for Resilient Functions against Polynomials
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, and David Zuckerman
(Cornell University, USA; Ohio State University, USA; Carnegie Mellon University, USA; University of California at San Diego, USA; University of Texas at Austin, USA)
@InProceedings{STOC20p253,
author = {Eshan Chattopadhyay and Pooya Hatami and Kaave Hosseini and Shachar Lovett and David Zuckerman},
title = {XOR Lemmas for Resilient Functions against Polynomials},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {253-252},
doi = {10.1145/3357713.3384242},
year = {2020},
}
Publisher's Version