STOC '19: "Gentle Measurement of Quantum ..."
Gentle Measurement of Quantum States and Differential Privacy
Scott Aaronson and Guy N. Rothblum
(University of Texas at Austin, USA; Weizmann Institute of Science, Israel)
@InProceedings{STOC19p393,
author = {Scott Aaronson and Guy N. Rothblum},
title = {Gentle Measurement of Quantum States and Differential Privacy},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {393-392},
doi = {10.1145/3313276.3316378},
year = {2019},
}
Publisher's Version
STOC '19: "Dynamic Set Cover: Improved ..."
Dynamic Set Cover: Improved Algorithms and Lower Bounds
Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, and Barna Saha
(IBM Research, USA; University of Massachusetts at Amherst, USA; IDSIA, Switzerland; Duke University, USA)
@InProceedings{STOC19p141,
author = {Amir Abboud and Raghavendra Addanki and Fabrizio Grandoni and Debmalya Panigrahi and Barna Saha},
title = {Dynamic Set Cover: Improved Algorithms and Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {141-140},
doi = {10.1145/3313276.3316376},
year = {2019},
}
Publisher's Version
STOC '19: "Dynamic Set Cover: Improved ..."
Dynamic Set Cover: Improved Algorithms and Lower Bounds
Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, and Barna Saha
(IBM Research, USA; University of Massachusetts at Amherst, USA; IDSIA, Switzerland; Duke University, USA)
@InProceedings{STOC19p141,
author = {Amir Abboud and Raghavendra Addanki and Fabrizio Grandoni and Debmalya Panigrahi and Barna Saha},
title = {Dynamic Set Cover: Improved Algorithms and Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {141-140},
doi = {10.1145/3313276.3316376},
year = {2019},
}
Publisher's Version
STOC '19: "Why Extension-Based Proofs ..."
Why Extension-Based Proofs Fail
Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu
(IST Austria, Austria; Yale University, USA; University of Toronto, Canada)
@InProceedings{STOC19p1233,
author = {Dan Alistarh and James Aspnes and Faith Ellen and Rati Gelashvili and Leqi Zhu},
title = {Why Extension-Based Proofs Fail},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1233-1232},
doi = {10.1145/3313276.3316407},
year = {2019},
}
Publisher's Version
STOC '19: "Private PAC Learning Implies ..."
Private PAC Learning Implies Finite Littlestone Dimension
Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran
(Princeton University, USA; Tel Aviv University, Israel; University of Chicago, USA)
@InProceedings{STOC19p1051,
author = {Noga Alon and Roi Livni and Maryanthe Malliaris and Shay Moran},
title = {Private PAC Learning Implies Finite Littlestone Dimension},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1051-1050},
doi = {10.1145/3313276.3316312},
year = {2019},
}
Publisher's Version
STOC '19: "An Exponential Lower Bound ..."
An Exponential Lower Bound on the Sub-Packetization of MSR Codes
Omar Alrabiah and Venkatesan Guruswami
(Carnegie Mellon University, USA)
@InProceedings{STOC19p1219,
author = {Omar Alrabiah and Venkatesan Guruswami},
title = {An Exponential Lower Bound on the Sub-Packetization of MSR Codes},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1219-1218},
doi = {10.1145/3313276.3316387},
year = {2019},
}
Publisher's Version
STOC '19: "Log-Concave Polynomials II: ..."
Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant
(Stanford University, USA; University of Washington, USA; North Carolina State University, USA)
@InProceedings{STOC19p1,
author = {Nima Anari and Kuikui Liu and Shayan Oveis Gharan and Cynthia Vinzant},
title = {Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1-0},
doi = {10.1145/3313276.3316385},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum Weak Coin Flipping ..."
Quantum Weak Coin Flipping
Atul Singh Arora, Jérémie Roland, and Stephan Weis
(Université libre de Bruxelles, Belgium)
@InProceedings{STOC19p253,
author = {Atul Singh Arora and Jérémie Roland and Stephan Weis},
title = {Quantum Weak Coin Flipping},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {253-252},
doi = {10.1145/3313276.3316306},
year = {2019},
}
Publisher's Version
STOC '19: "Why Extension-Based Proofs ..."
Why Extension-Based Proofs Fail
Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu
(IST Austria, Austria; Yale University, USA; University of Toronto, Canada)
@InProceedings{STOC19p1233,
author = {Dan Alistarh and James Aspnes and Faith Ellen and Rati Gelashvili and Leqi Zhu},
title = {Why Extension-Based Proofs Fail},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1233-1232},
doi = {10.1145/3313276.3316407},
year = {2019},
}
Publisher's Version
STOC '19: "Polynomial Pass Lower Bounds ..."
Polynomial Pass Lower Bounds for Graph Streaming Algorithms
Sepehr Assadi, Yu Chen, and Sanjeev Khanna
(Princeton University, USA; University of Pennsylvania, USA)
@InProceedings{STOC19p323,
author = {Sepehr Assadi and Yu Chen and Sanjeev Khanna},
title = {Polynomial Pass Lower Bounds for Graph Streaming Algorithms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {323-322},
doi = {10.1145/3313276.3316361},
year = {2019},
}
Publisher's Version
STOC '19: "A Universal Sampling Method ..."
A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh
(Tel Aviv University, Israel; EPFL, Switzerland; Microsoft Research, USA; Princeton University, USA; Google Research, USA)
@InProceedings{STOC19p1317,
author = {Haim Avron and Michael Kapralov and Cameron Musco and Christopher Musco and Ameya Velingker and Amir Zandieh},
title = {A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1317-1316},
doi = {10.1145/3313276.3316363},
year = {2019},
}
Publisher's Version
STOC '19: "Canonical Form for Graphs ..."
Canonical Form for Graphs in Quasipolynomial Time: Preliminary Report
László Babai
(University of Chicago, USA)
@InProceedings{STOC19p1555,
author = {László Babai},
title = {Canonical Form for Graphs in Quasipolynomial Time: Preliminary Report},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1555-1554},
doi = {10.1145/3313276.3316356},
year = {2019},
}
Publisher's Version
STOC '19: "The Communication Complexity ..."
The Communication Complexity of Local Search
Yakov Babichenko, Shahar Dobzinski, and Noam Nisan
(Technion, Israel; Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel)
@InProceedings{STOC19p813,
author = {Yakov Babichenko and Shahar Dobzinski and Noam Nisan},
title = {The Communication Complexity of Local Search},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {813-812},
doi = {10.1145/3313276.3316354},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum State Certification ..."
Quantum State Certification
Costin Bădescu, Ryan O'Donnell, and John Wright
(Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p631,
author = {Costin Bădescu and Ryan O'Donnell and John Wright},
title = {Quantum State Certification},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {631-630},
doi = {10.1145/3313276.3316344},
year = {2019},
}
Publisher's Version
STOC '19: "An Optimal Approximation for ..."
An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model
Eric Balkanski, Aviad Rubinstein, and Yaron Singer
(Harvard University, USA; Stanford University, USA)
@InProceedings{STOC19p85,
author = {Eric Balkanski and Aviad Rubinstein and Yaron Singer},
title = {An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {85-84},
doi = {10.1145/3313276.3316304},
year = {2019},
}
Publisher's Version
STOC '19: "On a Generalization of Iterated ..."
On a Generalization of Iterated and Randomized Rounding
Nikhil Bansal
(CWI, Netherlands; Eindhoven University of Technology, Netherlands)
@InProceedings{STOC19p1415,
author = {Nikhil Bansal},
title = {On a Generalization of Iterated and Randomized Rounding},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1415-1414},
doi = {10.1145/3313276.3316313},
year = {2019},
}
Publisher's Version
STOC '19: "Oblivious Dimension Reduction ..."
Oblivious Dimension Reduction for k-Means: Beyond Subspaces and the Johnson-Lindenstrauss Lemma
Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn
(Sapienza University of Rome, Italy; Zalando, Switzerland; CNRS, France; IDSIA, Switzerland)
@InProceedings{STOC19p1303,
author = {Luca Becchetti and Marc Bury and Vincent Cohen-Addad and Fabrizio Grandoni and Chris Schwiegelshohn},
title = {Oblivious Dimension Reduction for <i>k</i>-Means: Beyond Subspaces and the Johnson-Lindenstrauss Lemma},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1303-1302},
doi = {10.1145/3313276.3316318},
year = {2019},
}
Publisher's Version
STOC '19: "Planar Graphs of Bounded Degree ..."
Planar Graphs of Bounded Degree Have Bounded Queue Number
Michael Bekos, Henry Förster, Martin Gronemann, Tamara Mchedlidze, Fabrizio Montecchiani, Chrysanthi Raftopoulou, and Torsten Ueckerdt
(University of Tübingen, Germany; University of Cologne, Germany; KIT, Germany; University of Perugia, Italy; National Technical University of Athens, Greece)
@InProceedings{STOC19p211,
author = {Michael Bekos and Henry Förster and Martin Gronemann and Tamara Mchedlidze and Fabrizio Montecchiani and Chrysanthi Raftopoulou and Torsten Ueckerdt},
title = {Planar Graphs of Bounded Degree Have Bounded Queue Number},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {211-210},
doi = {10.1145/3313276.3316324},
year = {2019},
}
Publisher's Version
STOC '19: "Achieving Optimal Backlog ..."
Achieving Optimal Backlog in Multi-processor Cup Games
Michael A. Bender, Martín Farach-Colton, and William Kuszmaul
(Stony Brook University, USA; Rutgers University, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1443,
author = {Michael A. Bender and Martín Farach-Colton and William Kuszmaul},
title = {Achieving Optimal Backlog in Multi-processor Cup Games},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1443-1442},
doi = {10.1145/3313276.3316342},
year = {2019},
}
Publisher's Version
STOC '19: "Distributed Exact Weighted ..."
Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time
Aaron Bernstein and Danupon Nanongkai
(Rutgers University, USA; KTH, Sweden)
@InProceedings{STOC19p407,
author = {Aaron Bernstein and Danupon Nanongkai},
title = {Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {407-406},
doi = {10.1145/3313276.3316326},
year = {2019},
}
Publisher's Version
STOC '19: "Decremental Strongly-Connected ..."
Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time
Aaron Bernstein, Maximilian Probst, and Christian Wulff-Nilsen
(Rutgers University, USA; University of Copenhagen, Denmark)
@InProceedings{STOC19p449,
author = {Aaron Bernstein and Maximilian Probst and Christian Wulff-Nilsen},
title = {Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {449-448},
doi = {10.1145/3313276.3316335},
year = {2019},
}
Publisher's Version
STOC '19: "Optimal (and Benchmark-Optimal) ..."
Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items
Hedyeh Beyhaghi and S. Matthew Weinberg
(Cornell University, USA; Princeton University, USA)
@InProceedings{STOC19p855,
author = {Hedyeh Beyhaghi and S. Matthew Weinberg},
title = {Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {855-854},
doi = {10.1145/3313276.3316405},
year = {2019},
}
Publisher's Version
STOC '19: "Weak Zero-Knowledge Beyond ..."
Weak Zero-Knowledge Beyond the Black-Box Barrier
Nir Bitansky, Dakshita Khurana, and Omer Paneth
(Tel Aviv University, Israel; Microsoft Research, USA; University of Illinois at Urbana-Champaign, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1373,
author = {Nir Bitansky and Dakshita Khurana and Omer Paneth},
title = {Weak Zero-Knowledge Beyond the Black-Box Barrier},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1373-1372},
doi = {10.1145/3313276.3316382},
year = {2019},
}
Publisher's Version
STOC '19: "Good Approximate Quantum LDPC ..."
Good Approximate Quantum LDPC Codes from Spacetime Circuit Hamiltonians
Thomas C. Bohdanowicz, Elizabeth Crosson, Chinmay Nirkhe, and Henry Yuen
(California Institute of Technology, USA; University of New Mexico, USA; University of California at Berkeley, USA; University of Toronto, Canada)
@InProceedings{STOC19p603,
author = {Thomas C. Bohdanowicz and Elizabeth Crosson and Chinmay Nirkhe and Henry Yuen},
title = {Good Approximate Quantum LDPC Codes from Spacetime Circuit Hamiltonians},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {603-602},
doi = {10.1145/3313276.3316384},
year = {2019},
}
Publisher's Version
STOC '19: "1+ε Approximation ..."
1+ε Approximation of Tree Edit Distance in Quadratic Time
Mahdi Boroujeni, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, and Saeed Seddighin
(Sharif University of Technology, Iran; Institute for Research in Fundamental Sciences, Iran; University of Maryland, USA)
@InProceedings{STOC19p883,
author = {Mahdi Boroujeni and Mohammad Ghodsi and MohammadTaghi Hajiaghayi and Saeed Seddighin},
title = {1+<i>ε</i> Approximation of Tree Edit Distance in Quadratic Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {883-882},
doi = {10.1145/3313276.3316388},
year = {2019},
}
Publisher's Version
STOC '19: "Bridging between 0/1 and Linear ..."
Bridging between 0/1 and Linear Programming via Random Walks
Joshua Brakensiek and Venkatesan Guruswami
(Stanford University, USA; Carnegie Mellon University, USA)
@InProceedings{STOC19p715,
author = {Joshua Brakensiek and Venkatesan Guruswami},
title = {Bridging between 0/1 and Linear Programming via Random Walks},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {715-714},
doi = {10.1145/3313276.3316347},
year = {2019},
}
Publisher's Version
STOC '19: "CSPs with Global Modular Constraints: ..."
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
Joshua Brakensiek, Sivakanth Gopi, and Venkatesan Guruswami
(Stanford University, USA; Microsoft Research, USA; Carnegie Mellon University, USA)
@InProceedings{STOC19p743,
author = {Joshua Brakensiek and Sivakanth Gopi and Venkatesan Guruswami},
title = {CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {743-742},
doi = {10.1145/3313276.3316401},
year = {2019},
}
Publisher's Version
STOC '19: "Learning Restricted Boltzmann ..."
Learning Restricted Boltzmann Machines via Influence Maximization
Guy Bresler, Frederic Koehler, and Ankur Moitra
(Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1023,
author = {Guy Bresler and Frederic Koehler and Ankur Moitra},
title = {Learning Restricted Boltzmann Machines via Influence Maximization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1023-1022},
doi = {10.1145/3313276.3316372},
year = {2019},
}
Publisher's Version
STOC '19: "Approximating APSP without ..."
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max
Karl Bringmann, Marvin Künnemann, and Karol Węgrzycki
(Max Planck Institute for Informatics, Germany; University of Warsaw, Poland)
@InProceedings{STOC19p1177,
author = {Karl Bringmann and Marvin Künnemann and Karol Węgrzycki},
title = {Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1177-1176},
doi = {10.1145/3313276.3316373},
year = {2019},
}
Publisher's Version
STOC '19: "Competitively Chasing Convex ..."
Competitively Chasing Convex Bodies
Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, and Mark Sellke
(Microsoft Research, USA; University of Washington, USA; Stanford University, USA)
@InProceedings{STOC19p1065,
author = {Sébastien Bubeck and Yin Tat Lee and Yuanzhi Li and Mark Sellke},
title = {Competitively Chasing Convex Bodies},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1065-1064},
doi = {10.1145/3313276.3316314},
year = {2019},
}
Publisher's Version
STOC '19: "Algebraic Approach to Promise ..."
Algebraic Approach to Promise Constraint Satisfaction
Jakub Bulín, Andrei Krokhin, and Jakub Opršal
(Charles University in Prague, Czechia; University of Durham, UK)
@InProceedings{STOC19p757,
author = {Jakub Bulín and Andrei Krokhin and Jakub Opršal},
title = {Algebraic Approach to Promise Constraint Satisfaction},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {757-756},
doi = {10.1145/3313276.3316300},
year = {2019},
}
Publisher's Version
STOC '19: "Oblivious Dimension Reduction ..."
Oblivious Dimension Reduction for k-Means: Beyond Subspaces and the Johnson-Lindenstrauss Lemma
Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn
(Sapienza University of Rome, Italy; Zalando, Switzerland; CNRS, France; IDSIA, Switzerland)
@InProceedings{STOC19p1303,
author = {Luca Becchetti and Marc Bury and Vincent Cohen-Addad and Fabrizio Grandoni and Chris Schwiegelshohn},
title = {Oblivious Dimension Reduction for <i>k</i>-Means: Beyond Subspaces and the Johnson-Lindenstrauss Lemma},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1303-1302},
doi = {10.1145/3313276.3316318},
year = {2019},
}
Publisher's Version
STOC '19: "Fiat-Shamir: From Practice ..."
Fiat-Shamir: From Practice to Theory
Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, and Daniel Wichs
(Boston University, USA; Tel Aviv University, Israel; Visa Research, USA; Princeton University, USA; Massachusetts Institute of Technology, USA; Weizmann Institute of Science, Israel; Technion, Israel; Northeastern University, USA)
@InProceedings{STOC19p1359,
author = {Ran Canetti and Yilei Chen and Justin Holmgren and Alex Lombardi and Guy N. Rothblum and Ron D. Rothblum and Daniel Wichs},
title = {Fiat-Shamir: From Practice to Theory},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1359-1358},
doi = {10.1145/3313276.3316380},
year = {2019},
}
Publisher's Version
STOC '19: "The Structure of Optimal Private ..."
The Structure of Optimal Private Tests for Simple Hypotheses
Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam Smith, and Jonathan Ullman
(Stanford University, USA; Simons Institute for the Theory of Computing Berkeley, USA; Boston University, USA; Northeastern University, USA)
@InProceedings{STOC19p379,
author = {Clément L. Canonne and Gautam Kamath and Audra McMillan and Adam Smith and Jonathan Ullman},
title = {The Structure of Optimal Private Tests for Simple Hypotheses},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {379-378},
doi = {10.1145/3313276.3316336},
year = {2019},
}
Publisher's Version
STOC '19: "Explicit 𝑁-Vertex Graphs ..."
Explicit 𝑁-Vertex Graphs with Maximum Degree 𝐾 and Diameter [1+𝑜(1)]log𝐾-1 𝑁 for Each 𝐾-1 a Prime Power
Michael Capalbo
(Center for Computing Sciences, USA)
@InProceedings{STOC19p1499,
author = {Michael Capalbo},
title = {Explicit 𝑁-Vertex Graphs with Maximum Degree 𝐾 and Diameter [1+𝑜(1)]log<sub>𝐾-1</sub> 𝑁 for Each 𝐾-1 a Prime Power},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1499-1498},
doi = {10.1145/3313276.3316399},
year = {2019},
}
Publisher's Version
STOC '19: "Approximation Algorithms for ..."
Approximation Algorithms for Minimum Norm and Ordered Optimization Problems
Deeparnab Chakrabarty and Chaitanya Swamy
(Dartmouth College, USA; University of Waterloo, Canada)
@InProceedings{STOC19p155,
author = {Deeparnab Chakrabarty and Chaitanya Swamy},
title = {Approximation Algorithms for Minimum Norm and Ordered Optimization Problems},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {155-154},
doi = {10.1145/3313276.3316322},
year = {2019},
}
Publisher's Version
STOC '19: "Almost Optimal Distance Oracles ..."
Almost Optimal Distance Oracles for Planar Graphs
Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, and Oren Weimann
(King's College London, UK; University of Wrocław, Poland; IDC Herzliya, Israel; University of Haifa, Israel)
@InProceedings{STOC19p169,
author = {Panagiotis Charalampopoulos and Paweł Gawrychowski and Shay Mozes and Oren Weimann},
title = {Almost Optimal Distance Oracles for Planar Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {169-168},
doi = {10.1145/3313276.3316316},
year = {2019},
}
Publisher's Version
STOC '19: "Efficient Profile Maximum ..."
Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation
Moses Charikar, Kirankumar Shiragur, and Aaron Sidford
(Stanford University, USA)
@InProceedings{STOC19p967,
author = {Moses Charikar and Kirankumar Shiragur and Aaron Sidford},
title = {Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {967-966},
doi = {10.1145/3313276.3316398},
year = {2019},
}
Publisher's Version
STOC '19: "The Log-Approximate-Rank Conjecture ..."
The Log-Approximate-Rank Conjecture Is False
Arkadev Chattopadhyay, Nikhil S. Mande, and Suhail Sherif
(TIFR, India; Georgetown University, USA)
@InProceedings{STOC19p57,
author = {Arkadev Chattopadhyay and Nikhil S. Mande and Suhail Sherif},
title = {The Log-Approximate-Rank Conjecture Is False},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {57-56},
doi = {10.1145/3313276.3316353},
year = {2019},
}
Publisher's Version
STOC '19: "Parallelizing Greedy for Submodular ..."
Parallelizing Greedy for Submodular Set Function Maximization in Matroids and Beyond
Chandra Chekuri and Kent Quanrud
(University of Illinois at Urbana-Champaign, USA)
@InProceedings{STOC19p99,
author = {Chandra Chekuri and Kent Quanrud},
title = {Parallelizing Greedy for Submodular Set Function Maximization in Matroids and Beyond},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {99-98},
doi = {10.1145/3313276.3316406},
year = {2019},
}
Publisher's Version
STOC '19: "Bootstrapping Results for ..."
Bootstrapping Results for Threshold Circuits “Just Beyond” Known Lower Bounds
Lijie Chen and Roei Tell
(Massachusetts Institute of Technology, USA; Weizmann Institute of Science, Israel)
@InProceedings{STOC19p43,
author = {Lijie Chen and Roei Tell},
title = {Bootstrapping Results for Threshold Circuits “Just Beyond” Known Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {43-42},
doi = {10.1145/3313276.3316333},
year = {2019},
}
Publisher's Version
STOC '19: "Unconstrained Submodular Maximization ..."
Unconstrained Submodular Maximization with Constant Adaptive Complexity
Lin Chen, Moran Feldman, and Amin Karbasi
(Yale University, USA; Open University of Israel, Israel)
@InProceedings{STOC19p127,
author = {Lin Chen and Moran Feldman and Amin Karbasi},
title = {Unconstrained Submodular Maximization with Constant Adaptive Complexity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {127-126},
doi = {10.1145/3313276.3316327},
year = {2019},
}
Publisher's Version
STOC '19: "Beyond the Low-Degree Algorithm: ..."
Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications
Sitan Chen and Ankur Moitra
(Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1079,
author = {Sitan Chen and Ankur Moitra},
title = {Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1079-1078},
doi = {10.1145/3313276.3316375},
year = {2019},
}
Publisher's Version
STOC '19: "Testing Unateness Nearly Optimally ..."
Testing Unateness Nearly Optimally
Xi Chen and Erik Waingarten
(Columbia University, USA)
@InProceedings{STOC19p687,
author = {Xi Chen and Erik Waingarten},
title = {Testing Unateness Nearly Optimally},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {687-686},
doi = {10.1145/3313276.3316351},
year = {2019},
}
Publisher's Version
STOC '19: "Fiat-Shamir: From Practice ..."
Fiat-Shamir: From Practice to Theory
Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, and Daniel Wichs
(Boston University, USA; Tel Aviv University, Israel; Visa Research, USA; Princeton University, USA; Massachusetts Institute of Technology, USA; Weizmann Institute of Science, Israel; Technion, Israel; Northeastern University, USA)
@InProceedings{STOC19p1359,
author = {Ran Canetti and Yilei Chen and Justin Holmgren and Alex Lombardi and Guy N. Rothblum and Ron D. Rothblum and Daniel Wichs},
title = {Fiat-Shamir: From Practice to Theory},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1359-1358},
doi = {10.1145/3313276.3316380},
year = {2019},
}
Publisher's Version
STOC '19: "Polynomial Pass Lower Bounds ..."
Polynomial Pass Lower Bounds for Graph Streaming Algorithms
Sepehr Assadi, Yu Chen, and Sanjeev Khanna
(Princeton University, USA; University of Pennsylvania, USA)
@InProceedings{STOC19p323,
author = {Sepehr Assadi and Yu Chen and Sanjeev Khanna},
title = {Polynomial Pass Lower Bounds for Graph Streaming Algorithms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {323-322},
doi = {10.1145/3313276.3316361},
year = {2019},
}
Publisher's Version
STOC '19: "Finding a Nash Equilibrium ..."
Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir
Arka Rai Choudhuri, Pavel Hubáček, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum
(Johns Hopkins University, USA; Charles University in Prague, Czechia; IST Austria, Austria; IDC Herzliya, Israel; Weizmann Institute of Science, Israel)
@InProceedings{STOC19p1387,
author = {Arka Rai Choudhuri and Pavel Hubáček and Chethan Kamath and Krzysztof Pietrzak and Alon Rosen and Guy N. Rothblum},
title = {Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1387-1386},
doi = {10.1145/3313276.3316400},
year = {2019},
}
Publisher's Version
STOC '19: "A New Algorithm for Decremental ..."
A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems
Julia Chuzhoy and Sanjeev Khanna
(Toyota Technological Institute at Chicago, USA; University of Pennsylvania, USA)
@InProceedings{STOC19p477,
author = {Julia Chuzhoy and Sanjeev Khanna},
title = {A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {477-476},
doi = {10.1145/3313276.3316320},
year = {2019},
}
Publisher's Version
STOC '19: "The Online 𝑘-Taxi Problem ..."
The Online 𝑘-Taxi Problem
Christian Coester and Elias Koutsoupias
(University of Oxford, UK)
@InProceedings{STOC19p1429,
author = {Christian Coester and Elias Koutsoupias},
title = {The Online 𝑘-Taxi Problem},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1429-1428},
doi = {10.1145/3313276.3316370},
year = {2019},
}
Publisher's Version
STOC '19: "Solving Linear Programs in ..."
Solving Linear Programs in the Current Matrix Multiplication Time
Michael B. Cohen, Yin Tat Lee, and Zhao Song
(Massachusetts Institute of Technology, USA; University of Washington, USA; Microsoft Research, USA; University of Texas at Austin, USA)
@InProceedings{STOC19p1163,
author = {Michael B. Cohen and Yin Tat Lee and Zhao Song},
title = {Solving Linear Programs in the Current Matrix Multiplication Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1163-1162},
doi = {10.1145/3313276.3316303},
year = {2019},
}
Publisher's Version
STOC '19: "Oblivious Dimension Reduction ..."
Oblivious Dimension Reduction for k-Means: Beyond Subspaces and the Johnson-Lindenstrauss Lemma
Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn
(Sapienza University of Rome, Italy; Zalando, Switzerland; CNRS, France; IDSIA, Switzerland)
@InProceedings{STOC19p1303,
author = {Luca Becchetti and Marc Bury and Vincent Cohen-Addad and Fabrizio Grandoni and Chris Schwiegelshohn},
title = {Oblivious Dimension Reduction for <i>k</i>-Means: Beyond Subspaces and the Johnson-Lindenstrauss Lemma},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1303-1302},
doi = {10.1145/3313276.3316318},
year = {2019},
}
Publisher's Version
STOC '19: "New Polynomial Delay Bounds ..."
New Polynomial Delay Bounds for Maximal Subgraph Enumeration by Proximity Search
Alessio Conte and Takeaki Uno
(National Institute of Informatics, Japan; University of Pisa, Italy)
@InProceedings{STOC19p1485,
author = {Alessio Conte and Takeaki Uno},
title = {New Polynomial Delay Bounds for Maximal Subgraph Enumeration by Proximity Search},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1485-1484},
doi = {10.1145/3313276.3316402},
year = {2019},
}
Publisher's Version
STOC '19: "Good Approximate Quantum LDPC ..."
Good Approximate Quantum LDPC Codes from Spacetime Circuit Hamiltonians
Thomas C. Bohdanowicz, Elizabeth Crosson, Chinmay Nirkhe, and Henry Yuen
(California Institute of Technology, USA; University of New Mexico, USA; University of California at Berkeley, USA; University of Toronto, Canada)
@InProceedings{STOC19p603,
author = {Thomas C. Bohdanowicz and Elizabeth Crosson and Chinmay Nirkhe and Henry Yuen},
title = {Good Approximate Quantum LDPC Codes from Spacetime Circuit Hamiltonians},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {603-602},
doi = {10.1145/3313276.3316384},
year = {2019},
}
Publisher's Version
STOC '19: "The Reachability Problem for ..."
The Reachability Problem for Petri Nets Is Not Elementary
Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić, Jérôme Leroux, and Filip Mazowiecki
(University of Warsaw, Poland; University of Warwick, UK; CNRS, France; University of Bordeaux, France)
@InProceedings{STOC19p29,
author = {Wojciech Czerwiński and Sławomir Lasota and Ranko Lazić and Jérôme Leroux and Filip Mazowiecki},
title = {The Reachability Problem for Petri Nets Is Not Elementary},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {29-28},
doi = {10.1145/3313276.3316369},
year = {2019},
}
Publisher's Version
STOC '19: "On Approximating the Covering ..."
On Approximating the Covering Radius and Finding Dense Lattice Subspaces
Daniel Dadush
(CWI, Netherlands)
@InProceedings{STOC19p1275,
author = {Daniel Dadush},
title = {On Approximating the Covering Radius and Finding Dense Lattice Subspaces},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1275-1274},
doi = {10.1145/3313276.3316397},
year = {2019},
}
Publisher's Version
STOC '19: "Distributed Edge Connectivity ..."
Distributed Edge Connectivity in Sublinear Time
Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak
(KTH, Sweden; University of Vienna, Austria; Toyota Technological Institute at Chicago, USA)
@InProceedings{STOC19p421,
author = {Mohit Daga and Monika Henzinger and Danupon Nanongkai and Thatchaphol Saranurak},
title = {Distributed Edge Connectivity in Sublinear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {421-420},
doi = {10.1145/3313276.3316346},
year = {2019},
}
Publisher's Version
STOC '19: "Graph Pattern Detection: Hardness ..."
Graph Pattern Detection: Hardness for All Induced Patterns and Faster Non-induced Cycles
Mina Dalirrooyfard, Thuy Duong Vuong, and Virginia Vassilevska Williams
(Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1471,
author = {Mina Dalirrooyfard and Thuy Duong Vuong and Virginia Vassilevska Williams},
title = {Graph Pattern Detection: Hardness for All Induced Patterns and Faster Non-induced Cycles},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1471-1470},
doi = {10.1145/3313276.3316329},
year = {2019},
}
Publisher's Version
STOC '19: "Regression from Dependent ..."
Regression from Dependent Observations
Constantinos Daskalakis, Nishanth Dikkala, and Ioannis Panageas
(Massachusetts Institute of Technology, USA; Singapore University of Technology and Design, Singapore)
@InProceedings{STOC19p1093,
author = {Constantinos Daskalakis and Nishanth Dikkala and Ioannis Panageas},
title = {Regression from Dependent Observations},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1093-1092},
doi = {10.1145/3313276.3316362},
year = {2019},
}
Publisher's Version
STOC '19: "Degree-𝑑 Chow Parameters ..."
Degree-𝑑 Chow Parameters Robustly Determine Degree-𝑑 PTFs (and Algorithmic Applications)
Ilias Diakonikolas and Daniel M. Kane
(University of Southern California, USA; University of California at San Diego, USA)
@InProceedings{STOC19p995,
author = {Ilias Diakonikolas and Daniel M. Kane},
title = {Degree-𝑑 Chow Parameters Robustly Determine Degree-𝑑 PTFs (and Algorithmic Applications)},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {995-994},
doi = {10.1145/3313276.3316301},
year = {2019},
}
Publisher's Version
STOC '19: "Regression from Dependent ..."
Regression from Dependent Observations
Constantinos Daskalakis, Nishanth Dikkala, and Ioannis Panageas
(Massachusetts Institute of Technology, USA; Singapore University of Technology and Design, Singapore)
@InProceedings{STOC19p1093,
author = {Constantinos Daskalakis and Nishanth Dikkala and Ioannis Panageas},
title = {Regression from Dependent Observations},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1093-1092},
doi = {10.1145/3313276.3316362},
year = {2019},
}
Publisher's Version
STOC '19: "Capacity Lower Bound for the ..."
Capacity Lower Bound for the Ising Perceptron
Jian Ding and Nike Sun
(University of Pennsylvania, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1009,
author = {Jian Ding and Nike Sun},
title = {Capacity Lower Bound for the Ising Perceptron},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1009-1008},
doi = {10.1145/3313276.3316383},
year = {2019},
}
Publisher's Version
STOC '19: "The Communication Complexity ..."
The Communication Complexity of Local Search
Yakov Babichenko, Shahar Dobzinski, and Noam Nisan
(Technion, Israel; Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel)
@InProceedings{STOC19p813,
author = {Yakov Babichenko and Shahar Dobzinski and Noam Nisan},
title = {The Communication Complexity of Local Search},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {813-812},
doi = {10.1145/3313276.3316354},
year = {2019},
}
Publisher's Version
STOC '19: "Computing Quartet Distance ..."
Computing Quartet Distance Is Equivalent to Counting 4-Cycles
Bartłomiej Dudek and Paweł Gawrychowski
(University of Wrocław, Poland)
@InProceedings{STOC19p911,
author = {Bartłomiej Dudek and Paweł Gawrychowski},
title = {Computing Quartet Distance Is Equivalent to Counting 4-Cycles},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {911-910},
doi = {10.1145/3313276.3316390},
year = {2019},
}
Publisher's Version
STOC '19: "Fully Dynamic Spectral Vertex ..."
Fully Dynamic Spectral Vertex Sparsifiers and Applications
David Durfee, Yu Gao, Gramoz Goranci, and Richard Peng
(Georgia Tech, USA; University of Vienna, Austria)
@InProceedings{STOC19p1135,
author = {David Durfee and Yu Gao and Gramoz Goranci and Richard Peng},
title = {Fully Dynamic Spectral Vertex Sparsifiers and Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1135-1134},
doi = {10.1145/3313276.3316379},
year = {2019},
}
Publisher's Version
STOC '19: "Static Data Structure Lower ..."
Static Data Structure Lower Bounds Imply Rigidity
Zeev Dvir, Alexander Golovnev, and Omri Weinstein
(Princeton University, USA; Harvard University, USA; Columbia University, USA)
@InProceedings{STOC19p1205,
author = {Zeev Dvir and Alexander Golovnev and Omri Weinstein},
title = {Static Data Structure Lower Bounds Imply Rigidity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1205-1204},
doi = {10.1145/3313276.3316348},
year = {2019},
}
Publisher's Version
STOC '19: "Why Extension-Based Proofs ..."
Why Extension-Based Proofs Fail
Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu
(IST Austria, Austria; Yale University, USA; University of Toronto, Canada)
@InProceedings{STOC19p1233,
author = {Dan Alistarh and James Aspnes and Faith Ellen and Rati Gelashvili and Leqi Zhu},
title = {Why Extension-Based Proofs Fail},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1233-1232},
doi = {10.1145/3313276.3316407},
year = {2019},
}
Publisher's Version
STOC '19: "Submodular Maximization with ..."
Submodular Maximization with Matroid and Packing Constraints in Parallel
Alina Ene, Huy L. Nguyễn, and Adrian Vladu
(Boston University, USA; Northeastern University, USA)
@InProceedings{STOC19p113,
author = {Alina Ene and Huy L. Nguyễn and Adrian Vladu},
title = {Submodular Maximization with Matroid and Packing Constraints in Parallel},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {113-112},
doi = {10.1145/3313276.3316389},
year = {2019},
}
Publisher's Version
STOC '19: "Achieving Optimal Backlog ..."
Achieving Optimal Backlog in Multi-processor Cup Games
Michael A. Bender, Martín Farach-Colton, and William Kuszmaul
(Stony Brook University, USA; Rutgers University, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1443,
author = {Michael A. Bender and Martín Farach-Colton and William Kuszmaul},
title = {Achieving Optimal Backlog in Multi-processor Cup Games},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1443-1442},
doi = {10.1145/3313276.3316342},
year = {2019},
}
Publisher's Version
STOC '19: "Lower Bounds for External ..."
Lower Bounds for External Memory Integer Sorting via Network Coding
Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, and Elaine Shi
(University of Maryland, USA; Aarhus University, Denmark; Cornell University, USA)
@InProceedings{STOC19p1247,
author = {Alireza Farhadi and MohammadTaghi Hajiaghayi and Kasper Green Larsen and Elaine Shi},
title = {Lower Bounds for External Memory Integer Sorting via Network Coding},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1247-1246},
doi = {10.1145/3313276.3316337},
year = {2019},
}
Publisher's Version
STOC '19: "Unconstrained Submodular Maximization ..."
Unconstrained Submodular Maximization with Constant Adaptive Complexity
Lin Chen, Moran Feldman, and Amin Karbasi
(Yale University, USA; Open University of Israel, Israel)
@InProceedings{STOC19p127,
author = {Lin Chen and Moran Feldman and Amin Karbasi},
title = {Unconstrained Submodular Maximization with Constant Adaptive Complexity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {127-126},
doi = {10.1145/3313276.3316327},
year = {2019},
}
Publisher's Version
STOC '19: "Dynamic Sampling from Graphical ..."
Dynamic Sampling from Graphical Models
Weiming Feng, Nisheeth K. Vishnoi, and Yitong Yin
(Nanjing University, China; Yale University, USA)
@InProceedings{STOC19p1345,
author = {Weiming Feng and Nisheeth K. Vishnoi and Yitong Yin},
title = {Dynamic Sampling from Graphical Models},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1345-1344},
doi = {10.1145/3313276.3316365},
year = {2019},
}
Publisher's Version
STOC '19: "The Complexity of Splitting ..."
The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches
Aris Filos-Ratsikas and Paul W. Goldberg
(EPFL, Switzerland; University of Oxford, UK)
@InProceedings{STOC19p799,
author = {Aris Filos-Ratsikas and Paul W. Goldberg},
title = {The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {799-798},
doi = {10.1145/3313276.3316334},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum Proof Systems for ..."
Quantum Proof Systems for Iterated Exponential Time, and Beyond
Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, and Henry Yuen
(Horizon Quantum Computing, Singapore; University of Technology Sydney, Australia; California Institute of Technology, USA; University of Toronto, Canada)
@InProceedings{STOC19p589,
author = {Joseph Fitzsimons and Zhengfeng Ji and Thomas Vidick and Henry Yuen},
title = {Quantum Proof Systems for Iterated Exponential Time, and Beyond},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {589-588},
doi = {10.1145/3313276.3316343},
year = {2019},
}
Publisher's Version
STOC '19: "Planar Graphs of Bounded Degree ..."
Planar Graphs of Bounded Degree Have Bounded Queue Number
Michael Bekos, Henry Förster, Martin Gronemann, Tamara Mchedlidze, Fabrizio Montecchiani, Chrysanthi Raftopoulou, and Torsten Ueckerdt
(University of Tübingen, Germany; University of Cologne, Germany; KIT, Germany; University of Perugia, Italy; National Technical University of Athens, Greece)
@InProceedings{STOC19p211,
author = {Michael Bekos and Henry Förster and Martin Gronemann and Tamara Mchedlidze and Fabrizio Montecchiani and Chrysanthi Raftopoulou and Torsten Ueckerdt},
title = {Planar Graphs of Bounded Degree Have Bounded Queue Number},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {211-210},
doi = {10.1145/3313276.3316324},
year = {2019},
}
Publisher's Version
STOC '19: "Dynamic Low-Stretch Trees ..."
Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions
Sebastian Forster and Gramoz Goranci
(University of Salzburg, Austria; University of Vienna, Austria)
@InProceedings{STOC19p463,
author = {Sebastian Forster and Gramoz Goranci},
title = {Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {463-462},
doi = {10.1145/3313276.3316381},
year = {2019},
}
Publisher's Version
STOC '19: "Optimal Sequence Length Requirements ..."
Optimal Sequence Length Requirements for Phylogenetic Tree Reconstruction with Indels
Arun Ganesh and Qiuyi (Richard) Zhang
(University of California at Berkeley, USA)
@InProceedings{STOC19p897,
author = {Arun Ganesh and Qiuyi (Richard) Zhang},
title = {Optimal Sequence Length Requirements for Phylogenetic Tree Reconstruction with Indels},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {897-896},
doi = {10.1145/3313276.3316345},
year = {2019},
}
Publisher's Version
STOC '19: "Fully Dynamic Spectral Vertex ..."
Fully Dynamic Spectral Vertex Sparsifiers and Applications
David Durfee, Yu Gao, Gramoz Goranci, and Richard Peng
(Georgia Tech, USA; University of Vienna, Austria)
@InProceedings{STOC19p1135,
author = {David Durfee and Yu Gao and Gramoz Goranci and Richard Peng},
title = {Fully Dynamic Spectral Vertex Sparsifiers and Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1135-1134},
doi = {10.1145/3313276.3316379},
year = {2019},
}
Publisher's Version
STOC '19: "A Strongly Polynomial Algorithm ..."
A Strongly Polynomial Algorithm for Linear Exchange Markets
Jugal Garg and László A. Végh
(University of Illinois at Urbana-Champaign, USA; London School of Economics and Political Science, UK)
@InProceedings{STOC19p71,
author = {Jugal Garg and László A. Végh},
title = {A Strongly Polynomial Algorithm for Linear Exchange Markets},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {71-70},
doi = {10.1145/3313276.3316340},
year = {2019},
}
Publisher's Version
STOC '19: "Almost Optimal Distance Oracles ..."
Almost Optimal Distance Oracles for Planar Graphs
Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, and Oren Weimann
(King's College London, UK; University of Wrocław, Poland; IDC Herzliya, Israel; University of Haifa, Israel)
@InProceedings{STOC19p169,
author = {Panagiotis Charalampopoulos and Paweł Gawrychowski and Shay Mozes and Oren Weimann},
title = {Almost Optimal Distance Oracles for Planar Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {169-168},
doi = {10.1145/3313276.3316316},
year = {2019},
}
Publisher's Version
STOC '19: "Computing Quartet Distance ..."
Computing Quartet Distance Is Equivalent to Counting 4-Cycles
Bartłomiej Dudek and Paweł Gawrychowski
(University of Wrocław, Poland)
@InProceedings{STOC19p911,
author = {Bartłomiej Dudek and Paweł Gawrychowski},
title = {Computing Quartet Distance Is Equivalent to Counting 4-Cycles},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {911-910},
doi = {10.1145/3313276.3316390},
year = {2019},
}
Publisher's Version
STOC '19: "Why Extension-Based Proofs ..."
Why Extension-Based Proofs Fail
Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu
(IST Austria, Austria; Yale University, USA; University of Toronto, Canada)
@InProceedings{STOC19p1233,
author = {Dan Alistarh and James Aspnes and Faith Ellen and Rati Gelashvili and Leqi Zhu},
title = {Why Extension-Based Proofs Fail},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1233-1232},
doi = {10.1145/3313276.3316407},
year = {2019},
}
Publisher's Version
STOC '19: "Log-Concave Polynomials II: ..."
Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant
(Stanford University, USA; University of Washington, USA; North Carolina State University, USA)
@InProceedings{STOC19p1,
author = {Nima Anari and Kuikui Liu and Shayan Oveis Gharan and Cynthia Vinzant},
title = {Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1-0},
doi = {10.1145/3313276.3316385},
year = {2019},
}
Publisher's Version
STOC '19: "1+ε Approximation ..."
1+ε Approximation of Tree Edit Distance in Quadratic Time
Mahdi Boroujeni, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, and Saeed Seddighin
(Sharif University of Technology, Iran; Institute for Research in Fundamental Sciences, Iran; University of Maryland, USA)
@InProceedings{STOC19p883,
author = {Mahdi Boroujeni and Mohammad Ghodsi and MohammadTaghi Hajiaghayi and Saeed Seddighin},
title = {1+<i>ε</i> Approximation of Tree Edit Distance in Quadratic Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {883-882},
doi = {10.1145/3313276.3316388},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum Singular Value Transformation ..."
Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe
(CWI, Netherlands; University of Amsterdam, Netherlands; University of Maryland, USA; Microsoft Research, USA)
@InProceedings{STOC19p239,
author = {András Gilyén and Yuan Su and Guang Hao Low and Nathan Wiebe},
title = {Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {239-238},
doi = {10.1145/3313276.3316366},
year = {2019},
}
Publisher's Version
STOC '19: "Testing Graphs against an ..."
Testing Graphs against an Unknown Distribution
Lior Gishboliner and Asaf Shapira
(Tel Aviv University, Israel)
@InProceedings{STOC19p673,
author = {Lior Gishboliner and Asaf Shapira},
title = {Testing Graphs against an Unknown Distribution},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {673-672},
doi = {10.1145/3313276.3316308},
year = {2019},
}
Publisher's Version
STOC '19: "The Complexity of Splitting ..."
The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches
Aris Filos-Ratsikas and Paul W. Goldberg
(EPFL, Switzerland; University of Oxford, UK)
@InProceedings{STOC19p799,
author = {Aris Filos-Ratsikas and Paul W. Goldberg},
title = {The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {799-798},
doi = {10.1145/3313276.3316334},
year = {2019},
}
Publisher's Version
STOC '19: "Testing Graphs in Vertex-Distribution-Free ..."
Testing Graphs in Vertex-Distribution-Free Models
Oded Goldreich
(Weizmann Institute of Science, Israel)
@InProceedings{STOC19p659,
author = {Oded Goldreich},
title = {Testing Graphs in Vertex-Distribution-Free Models},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {659-658},
doi = {10.1145/3313276.3316302},
year = {2019},
}
Publisher's Version
STOC '19: "Static Data Structure Lower ..."
Static Data Structure Lower Bounds Imply Rigidity
Zeev Dvir, Alexander Golovnev, and Omri Weinstein
(Princeton University, USA; Harvard University, USA; Columbia University, USA)
@InProceedings{STOC19p1205,
author = {Zeev Dvir and Alexander Golovnev and Omri Weinstein},
title = {Static Data Structure Lower Bounds Imply Rigidity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1205-1204},
doi = {10.1145/3313276.3316348},
year = {2019},
}
Publisher's Version
STOC '19: "CSPs with Global Modular Constraints: ..."
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
Joshua Brakensiek, Sivakanth Gopi, and Venkatesan Guruswami
(Stanford University, USA; Microsoft Research, USA; Carnegie Mellon University, USA)
@InProceedings{STOC19p743,
author = {Joshua Brakensiek and Sivakanth Gopi and Venkatesan Guruswami},
title = {CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {743-742},
doi = {10.1145/3313276.3316401},
year = {2019},
}
Publisher's Version
STOC '19: "Fully Dynamic Spectral Vertex ..."
Fully Dynamic Spectral Vertex Sparsifiers and Applications
David Durfee, Yu Gao, Gramoz Goranci, and Richard Peng
(Georgia Tech, USA; University of Vienna, Austria)
@InProceedings{STOC19p1135,
author = {David Durfee and Yu Gao and Gramoz Goranci and Richard Peng},
title = {Fully Dynamic Spectral Vertex Sparsifiers and Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1135-1134},
doi = {10.1145/3313276.3316379},
year = {2019},
}
Publisher's Version
STOC '19: "Dynamic Low-Stretch Trees ..."
Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions
Sebastian Forster and Gramoz Goranci
(University of Salzburg, Austria; University of Vienna, Austria)
@InProceedings{STOC19p463,
author = {Sebastian Forster and Gramoz Goranci},
title = {Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {463-462},
doi = {10.1145/3313276.3316381},
year = {2019},
}
Publisher's Version
STOC '19: "Non-Gaussian Component Analysis ..."
Non-Gaussian Component Analysis using Entropy Methods
Navin Goyal and Abhishek Shetty
(Microsoft Research, India)
@InProceedings{STOC19p1037,
author = {Navin Goyal and Abhishek Shetty},
title = {Non-Gaussian Component Analysis using Entropy Methods},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1037-1036},
doi = {10.1145/3313276.3316309},
year = {2019},
}
Publisher's Version
STOC '19: "Oblivious Dimension Reduction ..."
Oblivious Dimension Reduction for k-Means: Beyond Subspaces and the Johnson-Lindenstrauss Lemma
Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn
(Sapienza University of Rome, Italy; Zalando, Switzerland; CNRS, France; IDSIA, Switzerland)
@InProceedings{STOC19p1303,
author = {Luca Becchetti and Marc Bury and Vincent Cohen-Addad and Fabrizio Grandoni and Chris Schwiegelshohn},
title = {Oblivious Dimension Reduction for <i>k</i>-Means: Beyond Subspaces and the Johnson-Lindenstrauss Lemma},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1303-1302},
doi = {10.1145/3313276.3316318},
year = {2019},
}
Publisher's Version
STOC '19: "Dynamic Set Cover: Improved ..."
Dynamic Set Cover: Improved Algorithms and Lower Bounds
Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, and Barna Saha
(IBM Research, USA; University of Massachusetts at Amherst, USA; IDSIA, Switzerland; Duke University, USA)
@InProceedings{STOC19p141,
author = {Amir Abboud and Raghavendra Addanki and Fabrizio Grandoni and Debmalya Panigrahi and Barna Saha},
title = {Dynamic Set Cover: Improved Algorithms and Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {141-140},
doi = {10.1145/3313276.3316376},
year = {2019},
}
Publisher's Version
STOC '19: "O(log² k / ..."
O(log² k / log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
Fabrizio Grandoni, Bundit Laekhanukit, and Shi Li
(IDSIA, Switzerland; Shanghai University of Finance and Economics, China; SUNY Buffalo, USA)
@InProceedings{STOC19p309,
author = {Fabrizio Grandoni and Bundit Laekhanukit and Shi Li},
title = {<i>O</i>(log² <i>k</i> / log log <i>k</i>)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {309-308},
doi = {10.1145/3313276.3316349},
year = {2019},
}
Publisher's Version
STOC '19: "Planar Graphs of Bounded Degree ..."
Planar Graphs of Bounded Degree Have Bounded Queue Number
Michael Bekos, Henry Förster, Martin Gronemann, Tamara Mchedlidze, Fabrizio Montecchiani, Chrysanthi Raftopoulou, and Torsten Ueckerdt
(University of Tübingen, Germany; University of Cologne, Germany; KIT, Germany; University of Perugia, Italy; National Technical University of Athens, Greece)
@InProceedings{STOC19p211,
author = {Michael Bekos and Henry Förster and Martin Gronemann and Tamara Mchedlidze and Fabrizio Montecchiani and Chrysanthi Raftopoulou and Torsten Ueckerdt},
title = {Planar Graphs of Bounded Degree Have Bounded Queue Number},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {211-210},
doi = {10.1145/3313276.3316324},
year = {2019},
}
Publisher's Version
STOC '19: "Settling the Sample Complexity ..."
Settling the Sample Complexity of Single-Parameter Revenue Maximization
Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang
(Tsinghua University, China; University of Hong Kong, China)
@InProceedings{STOC19p827,
author = {Chenghao Guo and Zhiyi Huang and Xinzhi Zhang},
title = {Settling the Sample Complexity of Single-Parameter Revenue Maximization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {827-826},
doi = {10.1145/3313276.3316325},
year = {2019},
}
Publisher's Version
STOC '19: "The Number of Minimum k-Cuts: ..."
The Number of Minimum k-Cuts: Improving the Karger-Stein Bound
Anupam Gupta, Euiwoong Lee, and Jason Li
(Carnegie Mellon University, USA; New York University, USA)
@InProceedings{STOC19p281,
author = {Anupam Gupta and Euiwoong Lee and Jason Li},
title = {The Number of Minimum <i>k</i>-Cuts: Improving the Karger-Stein Bound},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {281-280},
doi = {10.1145/3313276.3316395},
year = {2019},
}
Publisher's Version
STOC '19: "An Exponential Lower Bound ..."
An Exponential Lower Bound on the Sub-Packetization of MSR Codes
Omar Alrabiah and Venkatesan Guruswami
(Carnegie Mellon University, USA)
@InProceedings{STOC19p1219,
author = {Omar Alrabiah and Venkatesan Guruswami},
title = {An Exponential Lower Bound on the Sub-Packetization of MSR Codes},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1219-1218},
doi = {10.1145/3313276.3316387},
year = {2019},
}
Publisher's Version
STOC '19: "Bridging between 0/1 and Linear ..."
Bridging between 0/1 and Linear Programming via Random Walks
Joshua Brakensiek and Venkatesan Guruswami
(Stanford University, USA; Carnegie Mellon University, USA)
@InProceedings{STOC19p715,
author = {Joshua Brakensiek and Venkatesan Guruswami},
title = {Bridging between 0/1 and Linear Programming via Random Walks},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {715-714},
doi = {10.1145/3313276.3316347},
year = {2019},
}
Publisher's Version
STOC '19: "CSPs with Global Modular Constraints: ..."
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
Joshua Brakensiek, Sivakanth Gopi, and Venkatesan Guruswami
(Stanford University, USA; Microsoft Research, USA; Carnegie Mellon University, USA)
@InProceedings{STOC19p743,
author = {Joshua Brakensiek and Sivakanth Gopi and Venkatesan Guruswami},
title = {CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {743-742},
doi = {10.1145/3313276.3316401},
year = {2019},
}
Publisher's Version
STOC '19: "Communication Complexity of ..."
Communication Complexity of Estimating Correlations
Uri Hadar, Jingbo Liu, Yury Polyanskiy, and Ofer Shayevitz
(Tel Aviv University, Israel; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p981,
author = {Uri Hadar and Jingbo Liu and Yury Polyanskiy and Ofer Shayevitz},
title = {Communication Complexity of Estimating Correlations},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {981-980},
doi = {10.1145/3313276.3316332},
year = {2019},
}
Publisher's Version
STOC '19: "Near-Linear Time Insertion-Deletion ..."
Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing
Bernhard Haeupler, Aviad Rubinstein, and Amirbehshad Shahrasbi
(Carnegie Mellon University, USA; Stanford University, USA)
@InProceedings{STOC19p869,
author = {Bernhard Haeupler and Aviad Rubinstein and Amirbehshad Shahrasbi},
title = {Near-Linear Time Insertion-Deletion Codes and (1+<i>ε</i>)-Approximating Edit Distance via Indexing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {869-868},
doi = {10.1145/3313276.3316371},
year = {2019},
}
Publisher's Version
STOC '19: "Lower Bounds for External ..."
Lower Bounds for External Memory Integer Sorting via Network Coding
Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, and Elaine Shi
(University of Maryland, USA; Aarhus University, Denmark; Cornell University, USA)
@InProceedings{STOC19p1247,
author = {Alireza Farhadi and MohammadTaghi Hajiaghayi and Kasper Green Larsen and Elaine Shi},
title = {Lower Bounds for External Memory Integer Sorting via Network Coding},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1247-1246},
doi = {10.1145/3313276.3316337},
year = {2019},
}
Publisher's Version
STOC '19: "1+ε Approximation ..."
1+ε Approximation of Tree Edit Distance in Quadratic Time
Mahdi Boroujeni, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, and Saeed Seddighin
(Sharif University of Technology, Iran; Institute for Research in Fundamental Sciences, Iran; University of Maryland, USA)
@InProceedings{STOC19p883,
author = {Mahdi Boroujeni and Mohammad Ghodsi and MohammadTaghi Hajiaghayi and Saeed Seddighin},
title = {1+<i>ε</i> Approximation of Tree Edit Distance in Quadratic Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {883-882},
doi = {10.1145/3313276.3316388},
year = {2019},
}
Publisher's Version
STOC '19: "Faster k-SAT Algorithms ..."
Faster k-SAT Algorithms using Biased-PPSZ
Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, and Uri Zwick
(University of Copenhagen, Denmark; Tel Aviv University, Israel)
@InProceedings{STOC19p729,
author = {Thomas Dueholm Hansen and Haim Kaplan and Or Zamir and Uri Zwick},
title = {Faster <i>k</i>-SAT Algorithms using Biased-PPSZ},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {729-728},
doi = {10.1145/3313276.3316359},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum Lovász Local Lemma: ..."
Quantum Lovász Local Lemma: Shearer’s Bound Is Tight
Kun He, Qian Li, Xiaoming Sun, and Jiapeng Zhang
(Institute of Computing Technology at Chinese Academy of Sciences, China; University of Chinese Academy of Sciences, China; Shenzhen Institute of Computing Sciences, China; Shenzhen University, China; University of California at San Diego, USA)
@InProceedings{STOC19p575,
author = {Kun He and Qian Li and Xiaoming Sun and Jiapeng Zhang},
title = {Quantum Lovász Local Lemma: Shearer’s Bound Is Tight},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {575-574},
doi = {10.1145/3313276.3316392},
year = {2019},
}
Publisher's Version
STOC '19: "Algorithmic Pirogov-Sinai ..."
Algorithmic Pirogov-Sinai Theory
Tyler Helmuth, Will Perkins, and Guus Regts
(University of Bristol, UK; University of Illinois at Chicago, USA; University of Amsterdam, Netherlands)
@InProceedings{STOC19p1261,
author = {Tyler Helmuth and Will Perkins and Guus Regts},
title = {Algorithmic Pirogov-Sinai Theory},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1261-1260},
doi = {10.1145/3313276.3316305},
year = {2019},
}
Publisher's Version
STOC '19: "Distributed Edge Connectivity ..."
Distributed Edge Connectivity in Sublinear Time
Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak
(KTH, Sweden; University of Vienna, Austria; Toyota Technological Institute at Chicago, USA)
@InProceedings{STOC19p421,
author = {Mohit Daga and Monika Henzinger and Danupon Nanongkai and Thatchaphol Saranurak},
title = {Distributed Edge Connectivity in Sublinear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {421-420},
doi = {10.1145/3313276.3316346},
year = {2019},
}
Publisher's Version
STOC '19: "Fiat-Shamir: From Practice ..."
Fiat-Shamir: From Practice to Theory
Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, and Daniel Wichs
(Boston University, USA; Tel Aviv University, Israel; Visa Research, USA; Princeton University, USA; Massachusetts Institute of Technology, USA; Weizmann Institute of Science, Israel; Technion, Israel; Northeastern University, USA)
@InProceedings{STOC19p1359,
author = {Ran Canetti and Yilei Chen and Justin Holmgren and Alex Lombardi and Guy N. Rothblum and Ron D. Rothblum and Daniel Wichs},
title = {Fiat-Shamir: From Practice to Theory},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1359-1358},
doi = {10.1145/3313276.3316380},
year = {2019},
}
Publisher's Version
STOC '19: "The Parallel Repetition of ..."
The Parallel Repetition of Non-signaling Games: Counterexamples and Dichotomy
Justin Holmgren and Lisa Yang
(Princeton University, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p225,
author = {Justin Holmgren and Lisa Yang},
title = {The Parallel Repetition of Non-signaling Games: Counterexamples and Dichotomy},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {225-224},
doi = {10.1145/3313276.3316367},
year = {2019},
}
Publisher's Version
STOC '19: "Settling the Sample Complexity ..."
Settling the Sample Complexity of Single-Parameter Revenue Maximization
Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang
(Tsinghua University, China; University of Hong Kong, China)
@InProceedings{STOC19p827,
author = {Chenghao Guo and Zhiyi Huang and Xinzhi Zhang},
title = {Settling the Sample Complexity of Single-Parameter Revenue Maximization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {827-826},
doi = {10.1145/3313276.3316325},
year = {2019},
}
Publisher's Version
STOC '19: "Finding a Nash Equilibrium ..."
Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir
Arka Rai Choudhuri, Pavel Hubáček, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum
(Johns Hopkins University, USA; Charles University in Prague, Czechia; IST Austria, Austria; IDC Herzliya, Israel; Weizmann Institute of Science, Israel)
@InProceedings{STOC19p1387,
author = {Arka Rai Choudhuri and Pavel Hubáček and Chethan Kamath and Krzysztof Pietrzak and Alon Rosen and Guy N. Rothblum},
title = {Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1387-1386},
doi = {10.1145/3313276.3316400},
year = {2019},
}
Publisher's Version
STOC '19: "Mean-Field Approximation, ..."
Mean-Field Approximation, Convex Hierarchies, and the Optimality of Correlation Rounding: A Unified Perspective
Vishesh Jain, Frederic Koehler, and Andrej Risteski
(Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1541,
author = {Vishesh Jain and Frederic Koehler and Andrej Risteski},
title = {Mean-Field Approximation, Convex Hierarchies, and the Optimality of Correlation Rounding: A Unified Perspective},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1541-1540},
doi = {10.1145/3313276.3316299},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum Proof Systems for ..."
Quantum Proof Systems for Iterated Exponential Time, and Beyond
Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, and Henry Yuen
(Horizon Quantum Computing, Singapore; University of Technology Sydney, Australia; California Institute of Technology, USA; University of Toronto, Canada)
@InProceedings{STOC19p589,
author = {Joseph Fitzsimons and Zhengfeng Ji and Thomas Vidick and Henry Yuen},
title = {Quantum Proof Systems for Iterated Exponential Time, and Beyond},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {589-588},
doi = {10.1145/3313276.3316343},
year = {2019},
}
Publisher's Version
STOC '19: "Tight Approximation Ratio ..."
Tight Approximation Ratio of Anonymous Pricing
Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Gavin Tang, and Tao Xiao
(Columbia University, USA; Shanghai University of Finance and Economics, China; Hong Kong University of Science and Technology, China; Shanghai Jiao Tong University, China)
@InProceedings{STOC19p841,
author = {Yaonan Jin and Pinyan Lu and Qi Qi and Zhihao Gavin Tang and Tao Xiao},
title = {Tight Approximation Ratio of Anonymous Pricing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {841-840},
doi = {10.1145/3313276.3316331},
year = {2019},
}
Publisher's Version
STOC '19: "How to Delegate Computations ..."
How to Delegate Computations Publicly
Yael Tauman Kalai, Omer Paneth, and Lisa Yang
(Microsoft Research, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1401,
author = {Yael Tauman Kalai and Omer Paneth and Lisa Yang},
title = {How to Delegate Computations Publicly},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1401-1400},
doi = {10.1145/3313276.3316411},
year = {2019},
}
Publisher's Version
STOC '19: "Finding a Nash Equilibrium ..."
Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir
Arka Rai Choudhuri, Pavel Hubáček, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum
(Johns Hopkins University, USA; Charles University in Prague, Czechia; IST Austria, Austria; IDC Herzliya, Israel; Weizmann Institute of Science, Israel)
@InProceedings{STOC19p1387,
author = {Arka Rai Choudhuri and Pavel Hubáček and Chethan Kamath and Krzysztof Pietrzak and Alon Rosen and Guy N. Rothblum},
title = {Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1387-1386},
doi = {10.1145/3313276.3316400},
year = {2019},
}
Publisher's Version
STOC '19: "The Structure of Optimal Private ..."
The Structure of Optimal Private Tests for Simple Hypotheses
Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam Smith, and Jonathan Ullman
(Stanford University, USA; Simons Institute for the Theory of Computing Berkeley, USA; Boston University, USA; Northeastern University, USA)
@InProceedings{STOC19p379,
author = {Clément L. Canonne and Gautam Kamath and Audra McMillan and Adam Smith and Jonathan Ullman},
title = {The Structure of Optimal Private Tests for Simple Hypotheses},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {379-378},
doi = {10.1145/3313276.3316336},
year = {2019},
}
Publisher's Version
STOC '19: "Degree-𝑑 Chow Parameters ..."
Degree-𝑑 Chow Parameters Robustly Determine Degree-𝑑 PTFs (and Algorithmic Applications)
Ilias Diakonikolas and Daniel M. Kane
(University of Southern California, USA; University of California at San Diego, USA)
@InProceedings{STOC19p995,
author = {Ilias Diakonikolas and Daniel M. Kane},
title = {Degree-𝑑 Chow Parameters Robustly Determine Degree-𝑑 PTFs (and Algorithmic Applications)},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {995-994},
doi = {10.1145/3313276.3316301},
year = {2019},
}
Publisher's Version
STOC '19: "Faster k-SAT Algorithms ..."
Faster k-SAT Algorithms using Biased-PPSZ
Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, and Uri Zwick
(University of Copenhagen, Denmark; Tel Aviv University, Israel)
@InProceedings{STOC19p729,
author = {Thomas Dueholm Hansen and Haim Kaplan and Or Zamir and Uri Zwick},
title = {Faster <i>k</i>-SAT Algorithms using Biased-PPSZ},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {729-728},
doi = {10.1145/3313276.3316359},
year = {2019},
}
Publisher's Version
STOC '19: "A Universal Sampling Method ..."
A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh
(Tel Aviv University, Israel; EPFL, Switzerland; Microsoft Research, USA; Princeton University, USA; Google Research, USA)
@InProceedings{STOC19p1317,
author = {Haim Avron and Michael Kapralov and Cameron Musco and Christopher Musco and Ameya Velingker and Amir Zandieh},
title = {A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1317-1316},
doi = {10.1145/3313276.3316363},
year = {2019},
}
Publisher's Version
STOC '19: "An Optimal Space Lower Bound ..."
An Optimal Space Lower Bound for Approximating MAX-CUT
Michael Kapralov and Dmitry Krachun
(EPFL, Switzerland; University of Geneva, Switzerland)
@InProceedings{STOC19p337,
author = {Michael Kapralov and Dmitry Krachun},
title = {An Optimal Space Lower Bound for Approximating MAX-CUT},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {337-336},
doi = {10.1145/3313276.3316364},
year = {2019},
}
Publisher's Version
STOC '19: "Unconstrained Submodular Maximization ..."
Unconstrained Submodular Maximization with Constant Adaptive Complexity
Lin Chen, Moran Feldman, and Amin Karbasi
(Yale University, USA; Open University of Israel, Israel)
@InProceedings{STOC19p127,
author = {Lin Chen and Moran Feldman and Amin Karbasi},
title = {Unconstrained Submodular Maximization with Constant Adaptive Complexity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {127-126},
doi = {10.1145/3313276.3316327},
year = {2019},
}
Publisher's Version
STOC '19: "Polylogarithmic Approximation ..."
Polylogarithmic Approximation for Euler Genus on Bounded Degree Graphs
Ken-ichi Kawarabayashi and Anastasios Sidiropoulos
(National Institute of Informatics, Japan; University of Illinois at Chicago, USA)
@InProceedings{STOC19p197,
author = {Ken-ichi Kawarabayashi and Anastasios Sidiropoulos},
title = {Polylogarithmic Approximation for Euler Genus on Bounded Degree Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {197-196},
doi = {10.1145/3313276.3316409},
year = {2019},
}
Publisher's Version
STOC '19: "Reconstruction of Non-degenerate ..."
Reconstruction of Non-degenerate Homogeneous Depth Three Circuits
Neeraj Kayal and Chandan Saha
(Microsoft Research, India; Indian Institute of Science, India)
@InProceedings{STOC19p505,
author = {Neeraj Kayal and Chandan Saha},
title = {Reconstruction of Non-degenerate Homogeneous Depth Three Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {505-504},
doi = {10.1145/3313276.3316360},
year = {2019},
}
Publisher's Version
STOC '19: "String Synchronizing Sets: ..."
String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure
Dominik Kempa and Tomasz Kociumaka
(University of Warwick, UK; University of Warsaw, Poland; Bar-Ilan University, Israel)
@InProceedings{STOC19p939,
author = {Dominik Kempa and Tomasz Kociumaka},
title = {String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {939-938},
doi = {10.1145/3313276.3316368},
year = {2019},
}
Publisher's Version
STOC '19: "Polynomial Pass Lower Bounds ..."
Polynomial Pass Lower Bounds for Graph Streaming Algorithms
Sepehr Assadi, Yu Chen, and Sanjeev Khanna
(Princeton University, USA; University of Pennsylvania, USA)
@InProceedings{STOC19p323,
author = {Sepehr Assadi and Yu Chen and Sanjeev Khanna},
title = {Polynomial Pass Lower Bounds for Graph Streaming Algorithms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {323-322},
doi = {10.1145/3313276.3316361},
year = {2019},
}
Publisher's Version
STOC '19: "A New Algorithm for Decremental ..."
A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems
Julia Chuzhoy and Sanjeev Khanna
(Toyota Technological Institute at Chicago, USA; University of Pennsylvania, USA)
@InProceedings{STOC19p477,
author = {Julia Chuzhoy and Sanjeev Khanna},
title = {A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {477-476},
doi = {10.1145/3313276.3316320},
year = {2019},
}
Publisher's Version
STOC '19: "Weak Zero-Knowledge Beyond ..."
Weak Zero-Knowledge Beyond the Black-Box Barrier
Nir Bitansky, Dakshita Khurana, and Omer Paneth
(Tel Aviv University, Israel; Microsoft Research, USA; University of Illinois at Urbana-Champaign, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1373,
author = {Nir Bitansky and Dakshita Khurana and Omer Paneth},
title = {Weak Zero-Knowledge Beyond the Black-Box Barrier},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1373-1372},
doi = {10.1145/3313276.3316382},
year = {2019},
}
Publisher's Version
STOC '19: "String Synchronizing Sets: ..."
String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure
Dominik Kempa and Tomasz Kociumaka
(University of Warwick, UK; University of Warsaw, Poland; Bar-Ilan University, Israel)
@InProceedings{STOC19p939,
author = {Dominik Kempa and Tomasz Kociumaka},
title = {String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {939-938},
doi = {10.1145/3313276.3316368},
year = {2019},
}
Publisher's Version
STOC '19: "Learning Restricted Boltzmann ..."
Learning Restricted Boltzmann Machines via Influence Maximization
Guy Bresler, Frederic Koehler, and Ankur Moitra
(Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1023,
author = {Guy Bresler and Frederic Koehler and Ankur Moitra},
title = {Learning Restricted Boltzmann Machines via Influence Maximization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1023-1022},
doi = {10.1145/3313276.3316372},
year = {2019},
}
Publisher's Version
STOC '19: "Mean-Field Approximation, ..."
Mean-Field Approximation, Convex Hierarchies, and the Optimality of Correlation Rounding: A Unified Perspective
Vishesh Jain, Frederic Koehler, and Andrej Risteski
(Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1541,
author = {Vishesh Jain and Frederic Koehler and Andrej Risteski},
title = {Mean-Field Approximation, Convex Hierarchies, and the Optimality of Correlation Rounding: A Unified Perspective},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1541-1540},
doi = {10.1145/3313276.3316299},
year = {2019},
}
Publisher's Version
STOC '19: "Exponential Separation between ..."
Exponential Separation between Shallow Quantum Circuits and Unbounded Fan-In Shallow Classical Circuits
Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal
(Massachusetts Institute of Technology, USA; Microsoft Research, USA; Stanford University, USA)
@InProceedings{STOC19p645,
author = {Adam Bene Watts and Robin Kothari and Luke Schaeffer and Avishay Tal},
title = {Exponential Separation between Shallow Quantum Circuits and Unbounded Fan-In Shallow Classical Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {645-644},
doi = {10.1145/3313276.3316404},
year = {2019},
}
Publisher's Version
STOC '19: "The Online 𝑘-Taxi Problem ..."
The Online 𝑘-Taxi Problem
Christian Coester and Elias Koutsoupias
(University of Oxford, UK)
@InProceedings{STOC19p1429,
author = {Christian Coester and Elias Koutsoupias},
title = {The Online 𝑘-Taxi Problem},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1429-1428},
doi = {10.1145/3313276.3316370},
year = {2019},
}
Publisher's Version
STOC '19: "An Optimal Space Lower Bound ..."
An Optimal Space Lower Bound for Approximating MAX-CUT
Michael Kapralov and Dmitry Krachun
(EPFL, Switzerland; University of Geneva, Switzerland)
@InProceedings{STOC19p337,
author = {Michael Kapralov and Dmitry Krachun},
title = {An Optimal Space Lower Bound for Approximating MAX-CUT},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {337-336},
doi = {10.1145/3313276.3316364},
year = {2019},
}
Publisher's Version
STOC '19: "Algebraic Approach to Promise ..."
Algebraic Approach to Promise Constraint Satisfaction
Jakub Bulín, Andrei Krokhin, and Jakub Opršal
(Charles University in Prague, Czechia; University of Durham, UK)
@InProceedings{STOC19p757,
author = {Jakub Bulín and Andrei Krokhin and Jakub Opršal},
title = {Algebraic Approach to Promise Constraint Satisfaction},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {757-756},
doi = {10.1145/3313276.3316300},
year = {2019},
}
Publisher's Version
STOC '19: "Random Walks and Forbidden ..."
Random Walks and Forbidden Minors II: A poly(d ε⁻¹)-Query Tester for Minor-Closed Properties of Bounded Degree Graphs
Akash Kumar, C. Seshadhri, and Andrew Stolman
(Purdue University, USA; University of California at Santa Cruz, USA)
@InProceedings{STOC19p701,
author = {Akash Kumar and C. Seshadhri and Andrew Stolman},
title = {Random Walks and Forbidden Minors II: A poly(<i>d ε</i>⁻¹)-Query Tester for Minor-Closed Properties of Bounded Degree Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {701-700},
doi = {10.1145/3313276.3316330},
year = {2019},
}
Publisher's Version
STOC '19: "Approximating APSP without ..."
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max
Karl Bringmann, Marvin Künnemann, and Karol Węgrzycki
(Max Planck Institute for Informatics, Germany; University of Warsaw, Poland)
@InProceedings{STOC19p1177,
author = {Karl Bringmann and Marvin Künnemann and Karol Węgrzycki},
title = {Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1177-1176},
doi = {10.1145/3313276.3316373},
year = {2019},
}
Publisher's Version
STOC '19: "Achieving Optimal Backlog ..."
Achieving Optimal Backlog in Multi-processor Cup Games
Michael A. Bender, Martín Farach-Colton, and William Kuszmaul
(Stony Brook University, USA; Rutgers University, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1443,
author = {Michael A. Bender and Martín Farach-Colton and William Kuszmaul},
title = {Achieving Optimal Backlog in Multi-processor Cup Games},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1443-1442},
doi = {10.1145/3313276.3316342},
year = {2019},
}
Publisher's Version
STOC '19: "Flows in Almost Linear Time ..."
Flows in Almost Linear Time via Adaptive Preconditioning
Rasmus Kyng, Richard Peng, Sushant Sachdeva, and Di Wang
(Harvard University, USA; Georgia Tech, USA; Microsoft Research, USA; University of Toronto, Canada)
@InProceedings{STOC19p1121,
author = {Rasmus Kyng and Richard Peng and Sushant Sachdeva and Di Wang},
title = {Flows in Almost Linear Time via Adaptive Preconditioning},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1121-1120},
doi = {10.1145/3313276.3316410},
year = {2019},
}
Publisher's Version
STOC '19: "O(log² k / ..."
O(log² k / log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
Fabrizio Grandoni, Bundit Laekhanukit, and Shi Li
(IDSIA, Switzerland; Shanghai University of Finance and Economics, China; SUNY Buffalo, USA)
@InProceedings{STOC19p309,
author = {Fabrizio Grandoni and Bundit Laekhanukit and Shi Li},
title = {<i>O</i>(log² <i>k</i> / log log <i>k</i>)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {309-308},
doi = {10.1145/3313276.3316349},
year = {2019},
}
Publisher's Version
STOC '19: "Lower Bounds for External ..."
Lower Bounds for External Memory Integer Sorting via Network Coding
Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, and Elaine Shi
(University of Maryland, USA; Aarhus University, Denmark; Cornell University, USA)
@InProceedings{STOC19p1247,
author = {Alireza Farhadi and MohammadTaghi Hajiaghayi and Kasper Green Larsen and Elaine Shi},
title = {Lower Bounds for External Memory Integer Sorting via Network Coding},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1247-1246},
doi = {10.1145/3313276.3316337},
year = {2019},
}
Publisher's Version
STOC '19: "The Reachability Problem for ..."
The Reachability Problem for Petri Nets Is Not Elementary
Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić, Jérôme Leroux, and Filip Mazowiecki
(University of Warsaw, Poland; University of Warwick, UK; CNRS, France; University of Bordeaux, France)
@InProceedings{STOC19p29,
author = {Wojciech Czerwiński and Sławomir Lasota and Ranko Lazić and Jérôme Leroux and Filip Mazowiecki},
title = {The Reachability Problem for Petri Nets Is Not Elementary},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {29-28},
doi = {10.1145/3313276.3316369},
year = {2019},
}
Publisher's Version
STOC '19: "The Reachability Problem for ..."
The Reachability Problem for Petri Nets Is Not Elementary
Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić, Jérôme Leroux, and Filip Mazowiecki
(University of Warsaw, Poland; University of Warwick, UK; CNRS, France; University of Bordeaux, France)
@InProceedings{STOC19p29,
author = {Wojciech Czerwiński and Sławomir Lasota and Ranko Lazić and Jérôme Leroux and Filip Mazowiecki},
title = {The Reachability Problem for Petri Nets Is Not Elementary},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {29-28},
doi = {10.1145/3313276.3316369},
year = {2019},
}
Publisher's Version
STOC '19: "The Number of Minimum k-Cuts: ..."
The Number of Minimum k-Cuts: Improving the Karger-Stein Bound
Anupam Gupta, Euiwoong Lee, and Jason Li
(Carnegie Mellon University, USA; New York University, USA)
@InProceedings{STOC19p281,
author = {Anupam Gupta and Euiwoong Lee and Jason Li},
title = {The Number of Minimum <i>k</i>-Cuts: Improving the Karger-Stein Bound},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {281-280},
doi = {10.1145/3313276.3316395},
year = {2019},
}
Publisher's Version
STOC '19: "Competitively Chasing Convex ..."
Competitively Chasing Convex Bodies
Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, and Mark Sellke
(Microsoft Research, USA; University of Washington, USA; Stanford University, USA)
@InProceedings{STOC19p1065,
author = {Sébastien Bubeck and Yin Tat Lee and Yuanzhi Li and Mark Sellke},
title = {Competitively Chasing Convex Bodies},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1065-1064},
doi = {10.1145/3313276.3316314},
year = {2019},
}
Publisher's Version
STOC '19: "Solving Linear Programs in ..."
Solving Linear Programs in the Current Matrix Multiplication Time
Michael B. Cohen, Yin Tat Lee, and Zhao Song
(Massachusetts Institute of Technology, USA; University of Washington, USA; Microsoft Research, USA; University of Texas at Austin, USA)
@InProceedings{STOC19p1163,
author = {Michael B. Cohen and Yin Tat Lee and Zhao Song},
title = {Solving Linear Programs in the Current Matrix Multiplication Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1163-1162},
doi = {10.1145/3313276.3316303},
year = {2019},
}
Publisher's Version
STOC '19: "The Reachability Problem for ..."
The Reachability Problem for Petri Nets Is Not Elementary
Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić, Jérôme Leroux, and Filip Mazowiecki
(University of Warsaw, Poland; University of Warwick, UK; CNRS, France; University of Bordeaux, France)
@InProceedings{STOC19p29,
author = {Wojciech Czerwiński and Sławomir Lasota and Ranko Lazić and Jérôme Leroux and Filip Mazowiecki},
title = {The Reachability Problem for Petri Nets Is Not Elementary},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {29-28},
doi = {10.1145/3313276.3316369},
year = {2019},
}
Publisher's Version
STOC '19: "Planar Diameter via Metric ..."
Planar Diameter via Metric Compression
Jason Li and Merav Parter
(Carnegie Mellon University, USA; Weizmann Institute of Science, Israel)
@InProceedings{STOC19p183,
author = {Jason Li and Merav Parter},
title = {Planar Diameter via Metric Compression},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {183-182},
doi = {10.1145/3313276.3316358},
year = {2019},
}
Publisher's Version
STOC '19: "The Number of Minimum k-Cuts: ..."
The Number of Minimum k-Cuts: Improving the Karger-Stein Bound
Anupam Gupta, Euiwoong Lee, and Jason Li
(Carnegie Mellon University, USA; New York University, USA)
@InProceedings{STOC19p281,
author = {Anupam Gupta and Euiwoong Lee and Jason Li},
title = {The Number of Minimum <i>k</i>-Cuts: Improving the Karger-Stein Bound},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {281-280},
doi = {10.1145/3313276.3316395},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum Lovász Local Lemma: ..."
Quantum Lovász Local Lemma: Shearer’s Bound Is Tight
Kun He, Qian Li, Xiaoming Sun, and Jiapeng Zhang
(Institute of Computing Technology at Chinese Academy of Sciences, China; University of Chinese Academy of Sciences, China; Shenzhen Institute of Computing Sciences, China; Shenzhen University, China; University of California at San Diego, USA)
@InProceedings{STOC19p575,
author = {Kun He and Qian Li and Xiaoming Sun and Jiapeng Zhang},
title = {Quantum Lovász Local Lemma: Shearer’s Bound Is Tight},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {575-574},
doi = {10.1145/3313276.3316392},
year = {2019},
}
Publisher's Version
STOC '19: "O(log² k / ..."
O(log² k / log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
Fabrizio Grandoni, Bundit Laekhanukit, and Shi Li
(IDSIA, Switzerland; Shanghai University of Finance and Economics, China; SUNY Buffalo, USA)
@InProceedings{STOC19p309,
author = {Fabrizio Grandoni and Bundit Laekhanukit and Shi Li},
title = {<i>O</i>(log² <i>k</i> / log log <i>k</i>)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {309-308},
doi = {10.1145/3313276.3316349},
year = {2019},
}
Publisher's Version
STOC '19: "Competitively Chasing Convex ..."
Competitively Chasing Convex Bodies
Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, and Mark Sellke
(Microsoft Research, USA; University of Washington, USA; Stanford University, USA)
@InProceedings{STOC19p1065,
author = {Sébastien Bubeck and Yin Tat Lee and Yuanzhi Li and Mark Sellke},
title = {Competitively Chasing Convex Bodies},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1065-1064},
doi = {10.1145/3313276.3316314},
year = {2019},
}
Publisher's Version
STOC '19: "A Fixed-Depth Size-Hierarchy ..."
A Fixed-Depth Size-Hierarchy Theorem for AC0[⊕] via the Coin Problem
Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh
(IIT Bombay, India; IIT Hyderabad, India)
@InProceedings{STOC19p547,
author = {Nutan Limaye and Karteek Sreenivasaiah and Srikanth Srinivasan and Utkarsh Tripathi and S. Venkitesh},
title = {A Fixed-Depth Size-Hierarchy Theorem for AC<sup>0</sup>[⊕] via the Coin Problem},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {547-546},
doi = {10.1145/3313276.3316339},
year = {2019},
}
Publisher's Version
STOC '19: "Approximation Algorithms for ..."
Approximation Algorithms for Distributionally-Robust Stochastic Optimization with Black-Box Distributions
André Linhares and Chaitanya Swamy
(University of Waterloo, Canada)
@InProceedings{STOC19p953,
author = {André Linhares and Chaitanya Swamy},
title = {Approximation Algorithms for Distributionally-Robust Stochastic Optimization with Black-Box Distributions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {953-952},
doi = {10.1145/3313276.3316391},
year = {2019},
}
Publisher's Version
STOC '19: "Communication Complexity of ..."
Communication Complexity of Estimating Correlations
Uri Hadar, Jingbo Liu, Yury Polyanskiy, and Ofer Shayevitz
(Tel Aviv University, Israel; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p981,
author = {Uri Hadar and Jingbo Liu and Yury Polyanskiy and Ofer Shayevitz},
title = {Communication Complexity of Estimating Correlations},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {981-980},
doi = {10.1145/3313276.3316332},
year = {2019},
}
Publisher's Version
STOC '19: "Private Selection from Private ..."
Private Selection from Private Candidates
Jingcheng Liu and Kunal Talwar
(University of California at Berkeley, USA; Google Brain, USA)
@InProceedings{STOC19p365,
author = {Jingcheng Liu and Kunal Talwar},
title = {Private Selection from Private Candidates},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {365-364},
doi = {10.1145/3313276.3316377},
year = {2019},
}
Publisher's Version
STOC '19: "Log-Concave Polynomials II: ..."
Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant
(Stanford University, USA; University of Washington, USA; North Carolina State University, USA)
@InProceedings{STOC19p1,
author = {Nima Anari and Kuikui Liu and Shayan Oveis Gharan and Cynthia Vinzant},
title = {Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1-0},
doi = {10.1145/3313276.3316385},
year = {2019},
}
Publisher's Version
STOC '19: "Private PAC Learning Implies ..."
Private PAC Learning Implies Finite Littlestone Dimension
Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran
(Princeton University, USA; Tel Aviv University, Israel; University of Chicago, USA)
@InProceedings{STOC19p1051,
author = {Noga Alon and Roi Livni and Maryanthe Malliaris and Shay Moran},
title = {Private PAC Learning Implies Finite Littlestone Dimension},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1051-1050},
doi = {10.1145/3313276.3316312},
year = {2019},
}
Publisher's Version
STOC '19: "Fiat-Shamir: From Practice ..."
Fiat-Shamir: From Practice to Theory
Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, and Daniel Wichs
(Boston University, USA; Tel Aviv University, Israel; Visa Research, USA; Princeton University, USA; Massachusetts Institute of Technology, USA; Weizmann Institute of Science, Israel; Technion, Israel; Northeastern University, USA)
@InProceedings{STOC19p1359,
author = {Ran Canetti and Yilei Chen and Justin Holmgren and Alex Lombardi and Guy N. Rothblum and Ron D. Rothblum and Daniel Wichs},
title = {Fiat-Shamir: From Practice to Theory},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1359-1358},
doi = {10.1145/3313276.3316380},
year = {2019},
}
Publisher's Version
STOC '19: "DNF Sparsification beyond ..."
DNF Sparsification beyond Sunflowers
Shachar Lovett and Jiapeng Zhang
(University of California at San Diego, USA)
@InProceedings{STOC19p561,
author = {Shachar Lovett and Jiapeng Zhang},
title = {DNF Sparsification beyond Sunflowers},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {561-560},
doi = {10.1145/3313276.3316323},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum Singular Value Transformation ..."
Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe
(CWI, Netherlands; University of Amsterdam, Netherlands; University of Maryland, USA; Microsoft Research, USA)
@InProceedings{STOC19p239,
author = {András Gilyén and Yuan Su and Guang Hao Low and Nathan Wiebe},
title = {Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {239-238},
doi = {10.1145/3313276.3316366},
year = {2019},
}
Publisher's Version
STOC '19: "Hamiltonian Simulation with ..."
Hamiltonian Simulation with Nearly Optimal Dependence on Spectral Norm
Guang Hao Low
(Microsoft Research, USA)
@InProceedings{STOC19p617,
author = {Guang Hao Low},
title = {Hamiltonian Simulation with Nearly Optimal Dependence on Spectral Norm},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {617-616},
doi = {10.1145/3313276.3316386},
year = {2019},
}
Publisher's Version
STOC '19: "Tight Approximation Ratio ..."
Tight Approximation Ratio of Anonymous Pricing
Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Gavin Tang, and Tao Xiao
(Columbia University, USA; Shanghai University of Finance and Economics, China; Hong Kong University of Science and Technology, China; Shanghai Jiao Tong University, China)
@InProceedings{STOC19p841,
author = {Yaonan Jin and Pinyan Lu and Qi Qi and Zhihao Gavin Tang and Tao Xiao},
title = {Tight Approximation Ratio of Anonymous Pricing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {841-840},
doi = {10.1145/3313276.3316331},
year = {2019},
}
Publisher's Version
STOC '19: "Performance of Johnson-Lindenstrauss ..."
Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering
Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn
(Northwestern University, USA; Toyota Technological Institute at Chicago, USA; Microsoft Research, USA)
@InProceedings{STOC19p1289,
author = {Konstantin Makarychev and Yury Makarychev and Ilya Razenshteyn},
title = {Performance of Johnson-Lindenstrauss Transform for <i>k</i>-Means and <i>k</i>-Medians Clustering},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1289-1288},
doi = {10.1145/3313276.3316350},
year = {2019},
}
Publisher's Version
STOC '19: "Performance of Johnson-Lindenstrauss ..."
Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering
Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn
(Northwestern University, USA; Toyota Technological Institute at Chicago, USA; Microsoft Research, USA)
@InProceedings{STOC19p1289,
author = {Konstantin Makarychev and Yury Makarychev and Ilya Razenshteyn},
title = {Performance of Johnson-Lindenstrauss Transform for <i>k</i>-Means and <i>k</i>-Medians Clustering},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1289-1288},
doi = {10.1145/3313276.3316350},
year = {2019},
}
Publisher's Version
STOC '19: "Private PAC Learning Implies ..."
Private PAC Learning Implies Finite Littlestone Dimension
Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran
(Princeton University, USA; Tel Aviv University, Israel; University of Chicago, USA)
@InProceedings{STOC19p1051,
author = {Noga Alon and Roi Livni and Maryanthe Malliaris and Shay Moran},
title = {Private PAC Learning Implies Finite Littlestone Dimension},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1051-1050},
doi = {10.1145/3313276.3316312},
year = {2019},
}
Publisher's Version
STOC '19: "The Log-Approximate-Rank Conjecture ..."
The Log-Approximate-Rank Conjecture Is False
Arkadev Chattopadhyay, Nikhil S. Mande, and Suhail Sherif
(TIFR, India; Georgetown University, USA)
@InProceedings{STOC19p57,
author = {Arkadev Chattopadhyay and Nikhil S. Mande and Suhail Sherif},
title = {The Log-Approximate-Rank Conjecture Is False},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {57-56},
doi = {10.1145/3313276.3316353},
year = {2019},
}
Publisher's Version
STOC '19: "The Reachability Problem for ..."
The Reachability Problem for Petri Nets Is Not Elementary
Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić, Jérôme Leroux, and Filip Mazowiecki
(University of Warsaw, Poland; University of Warwick, UK; CNRS, France; University of Bordeaux, France)
@InProceedings{STOC19p29,
author = {Wojciech Czerwiński and Sławomir Lasota and Ranko Lazić and Jérôme Leroux and Filip Mazowiecki},
title = {The Reachability Problem for Petri Nets Is Not Elementary},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {29-28},
doi = {10.1145/3313276.3316369},
year = {2019},
}
Publisher's Version
STOC '19: "Planar Graphs of Bounded Degree ..."
Planar Graphs of Bounded Degree Have Bounded Queue Number
Michael Bekos, Henry Förster, Martin Gronemann, Tamara Mchedlidze, Fabrizio Montecchiani, Chrysanthi Raftopoulou, and Torsten Ueckerdt
(University of Tübingen, Germany; University of Cologne, Germany; KIT, Germany; University of Perugia, Italy; National Technical University of Athens, Greece)
@InProceedings{STOC19p211,
author = {Michael Bekos and Henry Förster and Martin Gronemann and Tamara Mchedlidze and Fabrizio Montecchiani and Chrysanthi Raftopoulou and Torsten Ueckerdt},
title = {Planar Graphs of Bounded Degree Have Bounded Queue Number},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {211-210},
doi = {10.1145/3313276.3316324},
year = {2019},
}
Publisher's Version
STOC '19: "Weak Lower Bounds on Resource-Bounded ..."
Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes
Dylan M. McKay, Cody D. Murray, and R. Ryan Williams
(Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)
@InProceedings{STOC19p1527,
author = {Dylan M. McKay and Cody D. Murray and R. Ryan Williams},
title = {Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1527-1526},
doi = {10.1145/3313276.3316396},
year = {2019},
}
Publisher's Version
STOC '19: "The Structure of Optimal Private ..."
The Structure of Optimal Private Tests for Simple Hypotheses
Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam Smith, and Jonathan Ullman
(Stanford University, USA; Simons Institute for the Theory of Computing Berkeley, USA; Boston University, USA; Northeastern University, USA)
@InProceedings{STOC19p379,
author = {Clément L. Canonne and Gautam Kamath and Audra McMillan and Adam Smith and Jonathan Ullman},
title = {The Structure of Optimal Private Tests for Simple Hypotheses},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {379-378},
doi = {10.1145/3313276.3316336},
year = {2019},
}
Publisher's Version
STOC '19: "Pseudorandom Generators for ..."
Pseudorandom Generators for Width-3 Branching Programs
Raghu Meka, Omer Reingold, and Avishay Tal
(University of California at Los Angeles, USA; Stanford University, USA)
@InProceedings{STOC19p785,
author = {Raghu Meka and Omer Reingold and Avishay Tal},
title = {Pseudorandom Generators for Width-3 Branching Programs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {785-784},
doi = {10.1145/3313276.3316319},
year = {2019},
}
Publisher's Version
STOC '19: "Learning Restricted Boltzmann ..."
Learning Restricted Boltzmann Machines via Influence Maximization
Guy Bresler, Frederic Koehler, and Ankur Moitra
(Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1023,
author = {Guy Bresler and Frederic Koehler and Ankur Moitra},
title = {Learning Restricted Boltzmann Machines via Influence Maximization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1023-1022},
doi = {10.1145/3313276.3316372},
year = {2019},
}
Publisher's Version
STOC '19: "Beyond the Low-Degree Algorithm: ..."
Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications
Sitan Chen and Ankur Moitra
(Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1079,
author = {Sitan Chen and Ankur Moitra},
title = {Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1079-1078},
doi = {10.1145/3313276.3316375},
year = {2019},
}
Publisher's Version
STOC '19: "Spectral Methods from Tensor ..."
Spectral Methods from Tensor Networks
Ankur Moitra and Alexander S. Wein
(Massachusetts Institute of Technology, USA; New York University, USA)
@InProceedings{STOC19p1149,
author = {Ankur Moitra and Alexander S. Wein},
title = {Spectral Methods from Tensor Networks},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1149-1148},
doi = {10.1145/3313276.3316357},
year = {2019},
}
Publisher's Version
STOC '19: "Planar Graphs of Bounded Degree ..."
Planar Graphs of Bounded Degree Have Bounded Queue Number
Michael Bekos, Henry Förster, Martin Gronemann, Tamara Mchedlidze, Fabrizio Montecchiani, Chrysanthi Raftopoulou, and Torsten Ueckerdt
(University of Tübingen, Germany; University of Cologne, Germany; KIT, Germany; University of Perugia, Italy; National Technical University of Athens, Greece)
@InProceedings{STOC19p211,
author = {Michael Bekos and Henry Förster and Martin Gronemann and Tamara Mchedlidze and Fabrizio Montecchiani and Chrysanthi Raftopoulou and Torsten Ueckerdt},
title = {Planar Graphs of Bounded Degree Have Bounded Queue Number},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {211-210},
doi = {10.1145/3313276.3316324},
year = {2019},
}
Publisher's Version
STOC '19: "Private PAC Learning Implies ..."
Private PAC Learning Implies Finite Littlestone Dimension
Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran
(Princeton University, USA; Tel Aviv University, Israel; University of Chicago, USA)
@InProceedings{STOC19p1051,
author = {Noga Alon and Roi Livni and Maryanthe Malliaris and Shay Moran},
title = {Private PAC Learning Implies Finite Littlestone Dimension},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1051-1050},
doi = {10.1145/3313276.3316312},
year = {2019},
}
Publisher's Version
STOC '19: "Almost Optimal Distance Oracles ..."
Almost Optimal Distance Oracles for Planar Graphs
Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, and Oren Weimann
(King's College London, UK; University of Wrocław, Poland; IDC Herzliya, Israel; University of Haifa, Israel)
@InProceedings{STOC19p169,
author = {Panagiotis Charalampopoulos and Paweł Gawrychowski and Shay Mozes and Oren Weimann},
title = {Almost Optimal Distance Oracles for Planar Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {169-168},
doi = {10.1145/3313276.3316316},
year = {2019},
}
Publisher's Version
STOC '19: "Weak Lower Bounds on Resource-Bounded ..."
Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes
Dylan M. McKay, Cody D. Murray, and R. Ryan Williams
(Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)
@InProceedings{STOC19p1527,
author = {Dylan M. McKay and Cody D. Murray and R. Ryan Williams},
title = {Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1527-1526},
doi = {10.1145/3313276.3316396},
year = {2019},
}
Publisher's Version
STOC '19: "A Universal Sampling Method ..."
A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh
(Tel Aviv University, Israel; EPFL, Switzerland; Microsoft Research, USA; Princeton University, USA; Google Research, USA)
@InProceedings{STOC19p1317,
author = {Haim Avron and Michael Kapralov and Cameron Musco and Christopher Musco and Ameya Velingker and Amir Zandieh},
title = {A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1317-1316},
doi = {10.1145/3313276.3316363},
year = {2019},
}
Publisher's Version
STOC '19: "A Universal Sampling Method ..."
A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh
(Tel Aviv University, Israel; EPFL, Switzerland; Microsoft Research, USA; Princeton University, USA; Google Research, USA)
@InProceedings{STOC19p1317,
author = {Haim Avron and Michael Kapralov and Cameron Musco and Christopher Musco and Ameya Velingker and Amir Zandieh},
title = {A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1317-1316},
doi = {10.1145/3313276.3316363},
year = {2019},
}
Publisher's Version
STOC '19: "Stronger L2/L2 Compressed ..."
Stronger L2/L2 Compressed Sensing; Without Iterating
Vasileios Nakos and Zhao Song
(Harvard University, USA; University of Texas at Austin, USA)
@InProceedings{STOC19p351,
author = {Vasileios Nakos and Zhao Song},
title = {Stronger L2/L2 Compressed Sensing; Without Iterating},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {351-350},
doi = {10.1145/3313276.3316355},
year = {2019},
}
Publisher's Version
STOC '19: "Breaking Quadratic Time for ..."
Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme
Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai
(KTH, Sweden; Toyota Technological Institute at Chicago, USA; Michigan State University, USA; Aalto University, Finland)
@InProceedings{STOC19p295,
author = {Danupon Nanongkai and Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai},
title = {Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {295-294},
doi = {10.1145/3313276.3316394},
year = {2019},
}
Publisher's Version
STOC '19: "Distributed Exact Weighted ..."
Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time
Aaron Bernstein and Danupon Nanongkai
(Rutgers University, USA; KTH, Sweden)
@InProceedings{STOC19p407,
author = {Aaron Bernstein and Danupon Nanongkai},
title = {Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {407-406},
doi = {10.1145/3313276.3316326},
year = {2019},
}
Publisher's Version
STOC '19: "Distributed Edge Connectivity ..."
Distributed Edge Connectivity in Sublinear Time
Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak
(KTH, Sweden; University of Vienna, Austria; Toyota Technological Institute at Chicago, USA)
@InProceedings{STOC19p421,
author = {Mohit Daga and Monika Henzinger and Danupon Nanongkai and Thatchaphol Saranurak},
title = {Distributed Edge Connectivity in Sublinear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {421-420},
doi = {10.1145/3313276.3316346},
year = {2019},
}
Publisher's Version
STOC '19: "Optimal Terminal Dimensionality ..."
Optimal Terminal Dimensionality Reduction in Euclidean Space
Shyam Narayanan and Jelani Nelson
(Harvard University, USA)
@InProceedings{STOC19p1331,
author = {Shyam Narayanan and Jelani Nelson},
title = {Optimal Terminal Dimensionality Reduction in Euclidean Space},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1331-1330},
doi = {10.1145/3313276.3316307},
year = {2019},
}
Publisher's Version
STOC '19: "Optimal Terminal Dimensionality ..."
Optimal Terminal Dimensionality Reduction in Euclidean Space
Shyam Narayanan and Jelani Nelson
(Harvard University, USA)
@InProceedings{STOC19p1331,
author = {Shyam Narayanan and Jelani Nelson},
title = {Optimal Terminal Dimensionality Reduction in Euclidean Space},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1331-1330},
doi = {10.1145/3313276.3316307},
year = {2019},
}
Publisher's Version
STOC '19: "Submodular Maximization with ..."
Submodular Maximization with Matroid and Packing Constraints in Parallel
Alina Ene, Huy L. Nguyễn, and Adrian Vladu
(Boston University, USA; Northeastern University, USA)
@InProceedings{STOC19p113,
author = {Alina Ene and Huy L. Nguyễn and Adrian Vladu},
title = {Submodular Maximization with Matroid and Packing Constraints in Parallel},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {113-112},
doi = {10.1145/3313276.3316389},
year = {2019},
}
Publisher's Version
STOC '19: "Good Approximate Quantum LDPC ..."
Good Approximate Quantum LDPC Codes from Spacetime Circuit Hamiltonians
Thomas C. Bohdanowicz, Elizabeth Crosson, Chinmay Nirkhe, and Henry Yuen
(California Institute of Technology, USA; University of New Mexico, USA; University of California at Berkeley, USA; University of Toronto, Canada)
@InProceedings{STOC19p603,
author = {Thomas C. Bohdanowicz and Elizabeth Crosson and Chinmay Nirkhe and Henry Yuen},
title = {Good Approximate Quantum LDPC Codes from Spacetime Circuit Hamiltonians},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {603-602},
doi = {10.1145/3313276.3316384},
year = {2019},
}
Publisher's Version
STOC '19: "The Communication Complexity ..."
The Communication Complexity of Local Search
Yakov Babichenko, Shahar Dobzinski, and Noam Nisan
(Technion, Israel; Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel)
@InProceedings{STOC19p813,
author = {Yakov Babichenko and Shahar Dobzinski and Noam Nisan},
title = {The Communication Complexity of Local Search},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {813-812},
doi = {10.1145/3313276.3316354},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum State Certification ..."
Quantum State Certification
Costin Bădescu, Ryan O'Donnell, and John Wright
(Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p631,
author = {Costin Bădescu and Ryan O'Donnell and John Wright},
title = {Quantum State Certification},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {631-630},
doi = {10.1145/3313276.3316344},
year = {2019},
}
Publisher's Version
STOC '19: "Fooling Polytopes ..."
Fooling Polytopes
Ryan O'Donnell, Rocco A. Servedio, and Li-Yang Tan
(Carnegie Mellon University, USA; Columbia University, USA; Stanford University, USA)
@InProceedings{STOC19p771,
author = {Ryan O'Donnell and Rocco A. Servedio and Li-Yang Tan},
title = {Fooling Polytopes},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {771-770},
doi = {10.1145/3313276.3316321},
year = {2019},
}
Publisher's Version
STOC '19: "Algebraic Approach to Promise ..."
Algebraic Approach to Promise Constraint Satisfaction
Jakub Bulín, Andrei Krokhin, and Jakub Opršal
(Charles University in Prague, Czechia; University of Durham, UK)
@InProceedings{STOC19p757,
author = {Jakub Bulín and Andrei Krokhin and Jakub Opršal},
title = {Algebraic Approach to Promise Constraint Satisfaction},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {757-756},
doi = {10.1145/3313276.3316300},
year = {2019},
}
Publisher's Version
STOC '19: "Planar Point Sets Determine ..."
Planar Point Sets Determine Many Pairwise Crossing Segments
János Pach, Natan Rubin, and Gábor Tardos
(EPFL, Switzerland; Renyi Institute, Hungary; Ben-Gurion University of the Negev, Israel; Central European University, Hungary)
@InProceedings{STOC19p1457,
author = {János Pach and Natan Rubin and Gábor Tardos},
title = {Planar Point Sets Determine Many Pairwise Crossing Segments},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1457-1456},
doi = {10.1145/3313276.3316328},
year = {2019},
}
Publisher's Version
STOC '19: "Regression from Dependent ..."
Regression from Dependent Observations
Constantinos Daskalakis, Nishanth Dikkala, and Ioannis Panageas
(Massachusetts Institute of Technology, USA; Singapore University of Technology and Design, Singapore)
@InProceedings{STOC19p1093,
author = {Constantinos Daskalakis and Nishanth Dikkala and Ioannis Panageas},
title = {Regression from Dependent Observations},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1093-1092},
doi = {10.1145/3313276.3316362},
year = {2019},
}
Publisher's Version
STOC '19: "Weak Zero-Knowledge Beyond ..."
Weak Zero-Knowledge Beyond the Black-Box Barrier
Nir Bitansky, Dakshita Khurana, and Omer Paneth
(Tel Aviv University, Israel; Microsoft Research, USA; University of Illinois at Urbana-Champaign, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1373,
author = {Nir Bitansky and Dakshita Khurana and Omer Paneth},
title = {Weak Zero-Knowledge Beyond the Black-Box Barrier},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1373-1372},
doi = {10.1145/3313276.3316382},
year = {2019},
}
Publisher's Version
STOC '19: "How to Delegate Computations ..."
How to Delegate Computations Publicly
Yael Tauman Kalai, Omer Paneth, and Lisa Yang
(Microsoft Research, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1401,
author = {Yael Tauman Kalai and Omer Paneth and Lisa Yang},
title = {How to Delegate Computations Publicly},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1401-1400},
doi = {10.1145/3313276.3316411},
year = {2019},
}
Publisher's Version
STOC '19: "Dynamic Set Cover: Improved ..."
Dynamic Set Cover: Improved Algorithms and Lower Bounds
Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, and Barna Saha
(IBM Research, USA; University of Massachusetts at Amherst, USA; IDSIA, Switzerland; Duke University, USA)
@InProceedings{STOC19p141,
author = {Amir Abboud and Raghavendra Addanki and Fabrizio Grandoni and Debmalya Panigrahi and Barna Saha},
title = {Dynamic Set Cover: Improved Algorithms and Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {141-140},
doi = {10.1145/3313276.3316376},
year = {2019},
}
Publisher's Version
STOC '19: "Planar Diameter via Metric ..."
Planar Diameter via Metric Compression
Jason Li and Merav Parter
(Carnegie Mellon University, USA; Weizmann Institute of Science, Israel)
@InProceedings{STOC19p183,
author = {Jason Li and Merav Parter},
title = {Planar Diameter via Metric Compression},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {183-182},
doi = {10.1145/3313276.3316358},
year = {2019},
}
Publisher's Version
STOC '19: "Flows in Almost Linear Time ..."
Flows in Almost Linear Time via Adaptive Preconditioning
Rasmus Kyng, Richard Peng, Sushant Sachdeva, and Di Wang
(Harvard University, USA; Georgia Tech, USA; Microsoft Research, USA; University of Toronto, Canada)
@InProceedings{STOC19p1121,
author = {Rasmus Kyng and Richard Peng and Sushant Sachdeva and Di Wang},
title = {Flows in Almost Linear Time via Adaptive Preconditioning},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1121-1120},
doi = {10.1145/3313276.3316410},
year = {2019},
}
Publisher's Version
STOC '19: "Fully Dynamic Spectral Vertex ..."
Fully Dynamic Spectral Vertex Sparsifiers and Applications
David Durfee, Yu Gao, Gramoz Goranci, and Richard Peng
(Georgia Tech, USA; University of Vienna, Austria)
@InProceedings{STOC19p1135,
author = {David Durfee and Yu Gao and Gramoz Goranci and Richard Peng},
title = {Fully Dynamic Spectral Vertex Sparsifiers and Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1135-1134},
doi = {10.1145/3313276.3316379},
year = {2019},
}
Publisher's Version
STOC '19: "Algorithmic Pirogov-Sinai ..."
Algorithmic Pirogov-Sinai Theory
Tyler Helmuth, Will Perkins, and Guus Regts
(University of Bristol, UK; University of Illinois at Chicago, USA; University of Amsterdam, Netherlands)
@InProceedings{STOC19p1261,
author = {Tyler Helmuth and Will Perkins and Guus Regts},
title = {Algorithmic Pirogov-Sinai Theory},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1261-1260},
doi = {10.1145/3313276.3316305},
year = {2019},
}
Publisher's Version
STOC '19: "Finding a Nash Equilibrium ..."
Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir
Arka Rai Choudhuri, Pavel Hubáček, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum
(Johns Hopkins University, USA; Charles University in Prague, Czechia; IST Austria, Austria; IDC Herzliya, Israel; Weizmann Institute of Science, Israel)
@InProceedings{STOC19p1387,
author = {Arka Rai Choudhuri and Pavel Hubáček and Chethan Kamath and Krzysztof Pietrzak and Alon Rosen and Guy N. Rothblum},
title = {Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1387-1386},
doi = {10.1145/3313276.3316400},
year = {2019},
}
Publisher's Version
STOC '19: "Communication Complexity of ..."
Communication Complexity of Estimating Correlations
Uri Hadar, Jingbo Liu, Yury Polyanskiy, and Ofer Shayevitz
(Tel Aviv University, Israel; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p981,
author = {Uri Hadar and Jingbo Liu and Yury Polyanskiy and Ofer Shayevitz},
title = {Communication Complexity of Estimating Correlations},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {981-980},
doi = {10.1145/3313276.3316332},
year = {2019},
}
Publisher's Version
STOC '19: "On the Approximation Resistance ..."
On the Approximation Resistance of Balanced Linear Threshold Functions
Aaron Potechin
(University of Chicago, USA)
@InProceedings{STOC19p533,
author = {Aaron Potechin},
title = {On the Approximation Resistance of Balanced Linear Threshold Functions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {533-532},
doi = {10.1145/3313276.3316374},
year = {2019},
}
Publisher's Version
STOC '19: "Decremental Strongly-Connected ..."
Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time
Aaron Bernstein, Maximilian Probst, and Christian Wulff-Nilsen
(Rutgers University, USA; University of Copenhagen, Denmark)
@InProceedings{STOC19p449,
author = {Aaron Bernstein and Maximilian Probst and Christian Wulff-Nilsen},
title = {Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {449-448},
doi = {10.1145/3313276.3316335},
year = {2019},
}
Publisher's Version
STOC '19: "Tight Approximation Ratio ..."
Tight Approximation Ratio of Anonymous Pricing
Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Gavin Tang, and Tao Xiao
(Columbia University, USA; Shanghai University of Finance and Economics, China; Hong Kong University of Science and Technology, China; Shanghai Jiao Tong University, China)
@InProceedings{STOC19p841,
author = {Yaonan Jin and Pinyan Lu and Qi Qi and Zhihao Gavin Tang and Tao Xiao},
title = {Tight Approximation Ratio of Anonymous Pricing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {841-840},
doi = {10.1145/3313276.3316331},
year = {2019},
}
Publisher's Version
STOC '19: "Parallelizing Greedy for Submodular ..."
Parallelizing Greedy for Submodular Set Function Maximization in Matroids and Beyond
Chandra Chekuri and Kent Quanrud
(University of Illinois at Urbana-Champaign, USA)
@InProceedings{STOC19p99,
author = {Chandra Chekuri and Kent Quanrud},
title = {Parallelizing Greedy for Submodular Set Function Maximization in Matroids and Beyond},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {99-98},
doi = {10.1145/3313276.3316406},
year = {2019},
}
Publisher's Version
STOC '19: "Planar Graphs of Bounded Degree ..."
Planar Graphs of Bounded Degree Have Bounded Queue Number
Michael Bekos, Henry Förster, Martin Gronemann, Tamara Mchedlidze, Fabrizio Montecchiani, Chrysanthi Raftopoulou, and Torsten Ueckerdt
(University of Tübingen, Germany; University of Cologne, Germany; KIT, Germany; University of Perugia, Italy; National Technical University of Athens, Greece)
@InProceedings{STOC19p211,
author = {Michael Bekos and Henry Förster and Martin Gronemann and Tamara Mchedlidze and Fabrizio Montecchiani and Chrysanthi Raftopoulou and Torsten Ueckerdt},
title = {Planar Graphs of Bounded Degree Have Bounded Queue Number},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {211-210},
doi = {10.1145/3313276.3316324},
year = {2019},
}
Publisher's Version
STOC '19: "Oracle Separation of BQP and ..."
Oracle Separation of BQP and PH
Ran Raz and Avishay Tal
(Princeton University, USA; Stanford University, USA)
@InProceedings{STOC19p15,
author = {Ran Raz and Avishay Tal},
title = {Oracle Separation of BQP and PH},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {15-14},
doi = {10.1145/3313276.3316315},
year = {2019},
}
Publisher's Version
STOC '19: "Performance of Johnson-Lindenstrauss ..."
Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering
Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn
(Northwestern University, USA; Toyota Technological Institute at Chicago, USA; Microsoft Research, USA)
@InProceedings{STOC19p1289,
author = {Konstantin Makarychev and Yury Makarychev and Ilya Razenshteyn},
title = {Performance of Johnson-Lindenstrauss Transform for <i>k</i>-Means and <i>k</i>-Medians Clustering},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1289-1288},
doi = {10.1145/3313276.3316350},
year = {2019},
}
Publisher's Version
STOC '19: "Algorithmic Pirogov-Sinai ..."
Algorithmic Pirogov-Sinai Theory
Tyler Helmuth, Will Perkins, and Guus Regts
(University of Bristol, UK; University of Illinois at Chicago, USA; University of Amsterdam, Netherlands)
@InProceedings{STOC19p1261,
author = {Tyler Helmuth and Will Perkins and Guus Regts},
title = {Algorithmic Pirogov-Sinai Theory},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1261-1260},
doi = {10.1145/3313276.3316305},
year = {2019},
}
Publisher's Version
STOC '19: "Pseudorandom Generators for ..."
Pseudorandom Generators for Width-3 Branching Programs
Raghu Meka, Omer Reingold, and Avishay Tal
(University of California at Los Angeles, USA; Stanford University, USA)
@InProceedings{STOC19p785,
author = {Raghu Meka and Omer Reingold and Avishay Tal},
title = {Pseudorandom Generators for Width-3 Branching Programs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {785-784},
doi = {10.1145/3313276.3316319},
year = {2019},
}
Publisher's Version
STOC '19: "Mean-Field Approximation, ..."
Mean-Field Approximation, Convex Hierarchies, and the Optimality of Correlation Rounding: A Unified Perspective
Vishesh Jain, Frederic Koehler, and Andrej Risteski
(Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1541,
author = {Vishesh Jain and Frederic Koehler and Andrej Risteski},
title = {Mean-Field Approximation, Convex Hierarchies, and the Optimality of Correlation Rounding: A Unified Perspective},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1541-1540},
doi = {10.1145/3313276.3316299},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum Weak Coin Flipping ..."
Quantum Weak Coin Flipping
Atul Singh Arora, Jérémie Roland, and Stephan Weis
(Université libre de Bruxelles, Belgium)
@InProceedings{STOC19p253,
author = {Atul Singh Arora and Jérémie Roland and Stephan Weis},
title = {Quantum Weak Coin Flipping},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {253-252},
doi = {10.1145/3313276.3316306},
year = {2019},
}
Publisher's Version
STOC '19: "Finding a Nash Equilibrium ..."
Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir
Arka Rai Choudhuri, Pavel Hubáček, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum
(Johns Hopkins University, USA; Charles University in Prague, Czechia; IST Austria, Austria; IDC Herzliya, Israel; Weizmann Institute of Science, Israel)
@InProceedings{STOC19p1387,
author = {Arka Rai Choudhuri and Pavel Hubáček and Chethan Kamath and Krzysztof Pietrzak and Alon Rosen and Guy N. Rothblum},
title = {Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1387-1386},
doi = {10.1145/3313276.3316400},
year = {2019},
}
Publisher's Version
STOC '19: "Fiat-Shamir: From Practice ..."
Fiat-Shamir: From Practice to Theory
Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, and Daniel Wichs
(Boston University, USA; Tel Aviv University, Israel; Visa Research, USA; Princeton University, USA; Massachusetts Institute of Technology, USA; Weizmann Institute of Science, Israel; Technion, Israel; Northeastern University, USA)
@InProceedings{STOC19p1359,
author = {Ran Canetti and Yilei Chen and Justin Holmgren and Alex Lombardi and Guy N. Rothblum and Ron D. Rothblum and Daniel Wichs},
title = {Fiat-Shamir: From Practice to Theory},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1359-1358},
doi = {10.1145/3313276.3316380},
year = {2019},
}
Publisher's Version
STOC '19: "Finding a Nash Equilibrium ..."
Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir
Arka Rai Choudhuri, Pavel Hubáček, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum
(Johns Hopkins University, USA; Charles University in Prague, Czechia; IST Austria, Austria; IDC Herzliya, Israel; Weizmann Institute of Science, Israel)
@InProceedings{STOC19p1387,
author = {Arka Rai Choudhuri and Pavel Hubáček and Chethan Kamath and Krzysztof Pietrzak and Alon Rosen and Guy N. Rothblum},
title = {Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1387-1386},
doi = {10.1145/3313276.3316400},
year = {2019},
}
Publisher's Version
STOC '19: "Gentle Measurement of Quantum ..."
Gentle Measurement of Quantum States and Differential Privacy
Scott Aaronson and Guy N. Rothblum
(University of Texas at Austin, USA; Weizmann Institute of Science, Israel)
@InProceedings{STOC19p393,
author = {Scott Aaronson and Guy N. Rothblum},
title = {Gentle Measurement of Quantum States and Differential Privacy},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {393-392},
doi = {10.1145/3313276.3316378},
year = {2019},
}
Publisher's Version
STOC '19: "Fiat-Shamir: From Practice ..."
Fiat-Shamir: From Practice to Theory
Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, and Daniel Wichs
(Boston University, USA; Tel Aviv University, Israel; Visa Research, USA; Princeton University, USA; Massachusetts Institute of Technology, USA; Weizmann Institute of Science, Israel; Technion, Israel; Northeastern University, USA)
@InProceedings{STOC19p1359,
author = {Ran Canetti and Yilei Chen and Justin Holmgren and Alex Lombardi and Guy N. Rothblum and Ron D. Rothblum and Daniel Wichs},
title = {Fiat-Shamir: From Practice to Theory},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1359-1358},
doi = {10.1145/3313276.3316380},
year = {2019},
}
Publisher's Version
STOC '19: "Planar Point Sets Determine ..."
Planar Point Sets Determine Many Pairwise Crossing Segments
János Pach, Natan Rubin, and Gábor Tardos
(EPFL, Switzerland; Renyi Institute, Hungary; Ben-Gurion University of the Negev, Israel; Central European University, Hungary)
@InProceedings{STOC19p1457,
author = {János Pach and Natan Rubin and Gábor Tardos},
title = {Planar Point Sets Determine Many Pairwise Crossing Segments},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1457-1456},
doi = {10.1145/3313276.3316328},
year = {2019},
}
Publisher's Version
STOC '19: "An Optimal Approximation for ..."
An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model
Eric Balkanski, Aviad Rubinstein, and Yaron Singer
(Harvard University, USA; Stanford University, USA)
@InProceedings{STOC19p85,
author = {Eric Balkanski and Aviad Rubinstein and Yaron Singer},
title = {An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {85-84},
doi = {10.1145/3313276.3316304},
year = {2019},
}
Publisher's Version
STOC '19: "Near-Linear Time Insertion-Deletion ..."
Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing
Bernhard Haeupler, Aviad Rubinstein, and Amirbehshad Shahrasbi
(Carnegie Mellon University, USA; Stanford University, USA)
@InProceedings{STOC19p869,
author = {Bernhard Haeupler and Aviad Rubinstein and Amirbehshad Shahrasbi},
title = {Near-Linear Time Insertion-Deletion Codes and (1+<i>ε</i>)-Approximating Edit Distance via Indexing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {869-868},
doi = {10.1145/3313276.3316371},
year = {2019},
}
Publisher's Version
STOC '19: "Flows in Almost Linear Time ..."
Flows in Almost Linear Time via Adaptive Preconditioning
Rasmus Kyng, Richard Peng, Sushant Sachdeva, and Di Wang
(Harvard University, USA; Georgia Tech, USA; Microsoft Research, USA; University of Toronto, Canada)
@InProceedings{STOC19p1121,
author = {Rasmus Kyng and Richard Peng and Sushant Sachdeva and Di Wang},
title = {Flows in Almost Linear Time via Adaptive Preconditioning},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1121-1120},
doi = {10.1145/3313276.3316410},
year = {2019},
}
Publisher's Version
STOC '19: "Dynamic Set Cover: Improved ..."
Dynamic Set Cover: Improved Algorithms and Lower Bounds
Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, and Barna Saha
(IBM Research, USA; University of Massachusetts at Amherst, USA; IDSIA, Switzerland; Duke University, USA)
@InProceedings{STOC19p141,
author = {Amir Abboud and Raghavendra Addanki and Fabrizio Grandoni and Debmalya Panigrahi and Barna Saha},
title = {Dynamic Set Cover: Improved Algorithms and Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {141-140},
doi = {10.1145/3313276.3316376},
year = {2019},
}
Publisher's Version
STOC '19: "Reconstruction of Non-degenerate ..."
Reconstruction of Non-degenerate Homogeneous Depth Three Circuits
Neeraj Kayal and Chandan Saha
(Microsoft Research, India; Indian Institute of Science, India)
@InProceedings{STOC19p505,
author = {Neeraj Kayal and Chandan Saha},
title = {Reconstruction of Non-degenerate Homogeneous Depth Three Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {505-504},
doi = {10.1145/3313276.3316360},
year = {2019},
}
Publisher's Version
STOC '19: "Breaking Quadratic Time for ..."
Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme
Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai
(KTH, Sweden; Toyota Technological Institute at Chicago, USA; Michigan State University, USA; Aalto University, Finland)
@InProceedings{STOC19p295,
author = {Danupon Nanongkai and Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai},
title = {Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {295-294},
doi = {10.1145/3313276.3316394},
year = {2019},
}
Publisher's Version
STOC '19: "Distributed Edge Connectivity ..."
Distributed Edge Connectivity in Sublinear Time
Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak
(KTH, Sweden; University of Vienna, Austria; Toyota Technological Institute at Chicago, USA)
@InProceedings{STOC19p421,
author = {Mohit Daga and Monika Henzinger and Danupon Nanongkai and Thatchaphol Saranurak},
title = {Distributed Edge Connectivity in Sublinear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {421-420},
doi = {10.1145/3313276.3316346},
year = {2019},
}
Publisher's Version
STOC '19: "Exponential Separation between ..."
Exponential Separation between Shallow Quantum Circuits and Unbounded Fan-In Shallow Classical Circuits
Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal
(Massachusetts Institute of Technology, USA; Microsoft Research, USA; Stanford University, USA)
@InProceedings{STOC19p645,
author = {Adam Bene Watts and Robin Kothari and Luke Schaeffer and Avishay Tal},
title = {Exponential Separation between Shallow Quantum Circuits and Unbounded Fan-In Shallow Classical Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {645-644},
doi = {10.1145/3313276.3316404},
year = {2019},
}
Publisher's Version
STOC '19: "A Unifying Method for the ..."
A Unifying Method for the Design of Algorithms Canonizing Combinatorial Objects
Pascal Schweitzer and Daniel Wiebking
(TU Kaiserslautern, Germany; RWTH Aachen University, Germany)
@InProceedings{STOC19p1569,
author = {Pascal Schweitzer and Daniel Wiebking},
title = {A Unifying Method for the Design of Algorithms Canonizing Combinatorial Objects},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1569-1568},
doi = {10.1145/3313276.3316338},
year = {2019},
}
Publisher's Version
STOC '19: "Oblivious Dimension Reduction ..."
Oblivious Dimension Reduction for k-Means: Beyond Subspaces and the Johnson-Lindenstrauss Lemma
Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn
(Sapienza University of Rome, Italy; Zalando, Switzerland; CNRS, France; IDSIA, Switzerland)
@InProceedings{STOC19p1303,
author = {Luca Becchetti and Marc Bury and Vincent Cohen-Addad and Fabrizio Grandoni and Chris Schwiegelshohn},
title = {Oblivious Dimension Reduction for <i>k</i>-Means: Beyond Subspaces and the Johnson-Lindenstrauss Lemma},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1303-1302},
doi = {10.1145/3313276.3316318},
year = {2019},
}
Publisher's Version
STOC '19: "1+ε Approximation ..."
1+ε Approximation of Tree Edit Distance in Quadratic Time
Mahdi Boroujeni, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, and Saeed Seddighin
(Sharif University of Technology, Iran; Institute for Research in Fundamental Sciences, Iran; University of Maryland, USA)
@InProceedings{STOC19p883,
author = {Mahdi Boroujeni and Mohammad Ghodsi and MohammadTaghi Hajiaghayi and Saeed Seddighin},
title = {1+<i>ε</i> Approximation of Tree Edit Distance in Quadratic Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {883-882},
doi = {10.1145/3313276.3316388},
year = {2019},
}
Publisher's Version
STOC '19: "Competitively Chasing Convex ..."
Competitively Chasing Convex Bodies
Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, and Mark Sellke
(Microsoft Research, USA; University of Washington, USA; Stanford University, USA)
@InProceedings{STOC19p1065,
author = {Sébastien Bubeck and Yin Tat Lee and Yuanzhi Li and Mark Sellke},
title = {Competitively Chasing Convex Bodies},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1065-1064},
doi = {10.1145/3313276.3316314},
year = {2019},
}
Publisher's Version
STOC '19: "Fooling Polytopes ..."
Fooling Polytopes
Ryan O'Donnell, Rocco A. Servedio, and Li-Yang Tan
(Carnegie Mellon University, USA; Columbia University, USA; Stanford University, USA)
@InProceedings{STOC19p771,
author = {Ryan O'Donnell and Rocco A. Servedio and Li-Yang Tan},
title = {Fooling Polytopes},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {771-770},
doi = {10.1145/3313276.3316321},
year = {2019},
}
Publisher's Version
STOC '19: "Random Walks and Forbidden ..."
Random Walks and Forbidden Minors II: A poly(d ε⁻¹)-Query Tester for Minor-Closed Properties of Bounded Degree Graphs
Akash Kumar, C. Seshadhri, and Andrew Stolman
(Purdue University, USA; University of California at Santa Cruz, USA)
@InProceedings{STOC19p701,
author = {Akash Kumar and C. Seshadhri and Andrew Stolman},
title = {Random Walks and Forbidden Minors II: A poly(<i>d ε</i>⁻¹)-Query Tester for Minor-Closed Properties of Bounded Degree Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {701-700},
doi = {10.1145/3313276.3316330},
year = {2019},
}
Publisher's Version
STOC '19: "Near-Linear Time Insertion-Deletion ..."
Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing
Bernhard Haeupler, Aviad Rubinstein, and Amirbehshad Shahrasbi
(Carnegie Mellon University, USA; Stanford University, USA)
@InProceedings{STOC19p869,
author = {Bernhard Haeupler and Aviad Rubinstein and Amirbehshad Shahrasbi},
title = {Near-Linear Time Insertion-Deletion Codes and (1+<i>ε</i>)-Approximating Edit Distance via Indexing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {869-868},
doi = {10.1145/3313276.3316371},
year = {2019},
}
Publisher's Version
STOC '19: "Testing Graphs against an ..."
Testing Graphs against an Unknown Distribution
Lior Gishboliner and Asaf Shapira
(Tel Aviv University, Israel)
@InProceedings{STOC19p673,
author = {Lior Gishboliner and Asaf Shapira},
title = {Testing Graphs against an Unknown Distribution},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {673-672},
doi = {10.1145/3313276.3316308},
year = {2019},
}
Publisher's Version
STOC '19: "Memory-Sample Tradeoffs for ..."
Memory-Sample Tradeoffs for Linear Regression with Small Error
Vatsal Sharan, Aaron Sidford, and Gregory Valiant
(Stanford University, USA)
@InProceedings{STOC19p1107,
author = {Vatsal Sharan and Aaron Sidford and Gregory Valiant},
title = {Memory-Sample Tradeoffs for Linear Regression with Small Error},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1107-1106},
doi = {10.1145/3313276.3316403},
year = {2019},
}
Publisher's Version
STOC '19: "Communication Complexity of ..."
Communication Complexity of Estimating Correlations
Uri Hadar, Jingbo Liu, Yury Polyanskiy, and Ofer Shayevitz
(Tel Aviv University, Israel; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p981,
author = {Uri Hadar and Jingbo Liu and Yury Polyanskiy and Ofer Shayevitz},
title = {Communication Complexity of Estimating Correlations},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {981-980},
doi = {10.1145/3313276.3316332},
year = {2019},
}
Publisher's Version
STOC '19: "The Log-Approximate-Rank Conjecture ..."
The Log-Approximate-Rank Conjecture Is False
Arkadev Chattopadhyay, Nikhil S. Mande, and Suhail Sherif
(TIFR, India; Georgetown University, USA)
@InProceedings{STOC19p57,
author = {Arkadev Chattopadhyay and Nikhil S. Mande and Suhail Sherif},
title = {The Log-Approximate-Rank Conjecture Is False},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {57-56},
doi = {10.1145/3313276.3316353},
year = {2019},
}
Publisher's Version
STOC '19: "Near-Optimal Lower Bounds ..."
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC0
Alexander A. Sherstov and Pei Wu
(University of California at Los Angeles, USA)
@InProceedings{STOC19p491,
author = {Alexander A. Sherstov and Pei Wu},
title = {Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC<sup>0</sup>},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {491-490},
doi = {10.1145/3313276.3316408},
year = {2019},
}
Publisher's Version
STOC '19: "Non-Gaussian Component Analysis ..."
Non-Gaussian Component Analysis using Entropy Methods
Navin Goyal and Abhishek Shetty
(Microsoft Research, India)
@InProceedings{STOC19p1037,
author = {Navin Goyal and Abhishek Shetty},
title = {Non-Gaussian Component Analysis using Entropy Methods},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1037-1036},
doi = {10.1145/3313276.3316309},
year = {2019},
}
Publisher's Version
STOC '19: "Lower Bounds for External ..."
Lower Bounds for External Memory Integer Sorting via Network Coding
Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, and Elaine Shi
(University of Maryland, USA; Aarhus University, Denmark; Cornell University, USA)
@InProceedings{STOC19p1247,
author = {Alireza Farhadi and MohammadTaghi Hajiaghayi and Kasper Green Larsen and Elaine Shi},
title = {Lower Bounds for External Memory Integer Sorting via Network Coding},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1247-1246},
doi = {10.1145/3313276.3316337},
year = {2019},
}
Publisher's Version
STOC '19: "Efficient Profile Maximum ..."
Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation
Moses Charikar, Kirankumar Shiragur, and Aaron Sidford
(Stanford University, USA)
@InProceedings{STOC19p967,
author = {Moses Charikar and Kirankumar Shiragur and Aaron Sidford},
title = {Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {967-966},
doi = {10.1145/3313276.3316398},
year = {2019},
}
Publisher's Version
STOC '19: "Sylvester-Gallai Type Theorems ..."
Sylvester-Gallai Type Theorems for Quadratic Polynomials
Amir Shpilka
(Tel Aviv University, Israel)
@InProceedings{STOC19p1513,
author = {Amir Shpilka},
title = {Sylvester-Gallai Type Theorems for Quadratic Polynomials},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1513-1512},
doi = {10.1145/3313276.3316341},
year = {2019},
}
Publisher's Version
STOC '19: "Memory-Sample Tradeoffs for ..."
Memory-Sample Tradeoffs for Linear Regression with Small Error
Vatsal Sharan, Aaron Sidford, and Gregory Valiant
(Stanford University, USA)
@InProceedings{STOC19p1107,
author = {Vatsal Sharan and Aaron Sidford and Gregory Valiant},
title = {Memory-Sample Tradeoffs for Linear Regression with Small Error},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1107-1106},
doi = {10.1145/3313276.3316403},
year = {2019},
}
Publisher's Version
STOC '19: "Efficient Profile Maximum ..."
Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation
Moses Charikar, Kirankumar Shiragur, and Aaron Sidford
(Stanford University, USA)
@InProceedings{STOC19p967,
author = {Moses Charikar and Kirankumar Shiragur and Aaron Sidford},
title = {Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {967-966},
doi = {10.1145/3313276.3316398},
year = {2019},
}
Publisher's Version
STOC '19: "Polylogarithmic Approximation ..."
Polylogarithmic Approximation for Euler Genus on Bounded Degree Graphs
Ken-ichi Kawarabayashi and Anastasios Sidiropoulos
(National Institute of Informatics, Japan; University of Illinois at Chicago, USA)
@InProceedings{STOC19p197,
author = {Ken-ichi Kawarabayashi and Anastasios Sidiropoulos},
title = {Polylogarithmic Approximation for Euler Genus on Bounded Degree Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {197-196},
doi = {10.1145/3313276.3316409},
year = {2019},
}
Publisher's Version
STOC '19: "An Optimal Approximation for ..."
An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model
Eric Balkanski, Aviad Rubinstein, and Yaron Singer
(Harvard University, USA; Stanford University, USA)
@InProceedings{STOC19p85,
author = {Eric Balkanski and Aviad Rubinstein and Yaron Singer},
title = {An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {85-84},
doi = {10.1145/3313276.3316304},
year = {2019},
}
Publisher's Version
STOC '19: "Local Decodability of the ..."
Local Decodability of the Burrows-Wheeler Transform
Sandip Sinha and Omri Weinstein
(Columbia University, USA)
@InProceedings{STOC19p925,
author = {Sandip Sinha and Omri Weinstein},
title = {Local Decodability of the Burrows-Wheeler Transform},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {925-924},
doi = {10.1145/3313276.3316317},
year = {2019},
}
Publisher's Version
STOC '19: "The Structure of Optimal Private ..."
The Structure of Optimal Private Tests for Simple Hypotheses
Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam Smith, and Jonathan Ullman
(Stanford University, USA; Simons Institute for the Theory of Computing Berkeley, USA; Boston University, USA; Northeastern University, USA)
@InProceedings{STOC19p379,
author = {Clément L. Canonne and Gautam Kamath and Audra McMillan and Adam Smith and Jonathan Ullman},
title = {The Structure of Optimal Private Tests for Simple Hypotheses},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {379-378},
doi = {10.1145/3313276.3316336},
year = {2019},
}
Publisher's Version
STOC '19: "Solving Linear Programs in ..."
Solving Linear Programs in the Current Matrix Multiplication Time
Michael B. Cohen, Yin Tat Lee, and Zhao Song
(Massachusetts Institute of Technology, USA; University of Washington, USA; Microsoft Research, USA; University of Texas at Austin, USA)
@InProceedings{STOC19p1163,
author = {Michael B. Cohen and Yin Tat Lee and Zhao Song},
title = {Solving Linear Programs in the Current Matrix Multiplication Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1163-1162},
doi = {10.1145/3313276.3316303},
year = {2019},
}
Publisher's Version
STOC '19: "Stronger L2/L2 Compressed ..."
Stronger L2/L2 Compressed Sensing; Without Iterating
Vasileios Nakos and Zhao Song
(Harvard University, USA; University of Texas at Austin, USA)
@InProceedings{STOC19p351,
author = {Vasileios Nakos and Zhao Song},
title = {Stronger L2/L2 Compressed Sensing; Without Iterating},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {351-350},
doi = {10.1145/3313276.3316355},
year = {2019},
}
Publisher's Version
STOC '19: "A Fixed-Depth Size-Hierarchy ..."
A Fixed-Depth Size-Hierarchy Theorem for AC0[⊕] via the Coin Problem
Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh
(IIT Bombay, India; IIT Hyderabad, India)
@InProceedings{STOC19p547,
author = {Nutan Limaye and Karteek Sreenivasaiah and Srikanth Srinivasan and Utkarsh Tripathi and S. Venkitesh},
title = {A Fixed-Depth Size-Hierarchy Theorem for AC<sup>0</sup>[⊕] via the Coin Problem},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {547-546},
doi = {10.1145/3313276.3316339},
year = {2019},
}
Publisher's Version
STOC '19: "A Fixed-Depth Size-Hierarchy ..."
A Fixed-Depth Size-Hierarchy Theorem for AC0[⊕] via the Coin Problem
Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh
(IIT Bombay, India; IIT Hyderabad, India)
@InProceedings{STOC19p547,
author = {Nutan Limaye and Karteek Sreenivasaiah and Srikanth Srinivasan and Utkarsh Tripathi and S. Venkitesh},
title = {A Fixed-Depth Size-Hierarchy Theorem for AC<sup>0</sup>[⊕] via the Coin Problem},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {547-546},
doi = {10.1145/3313276.3316339},
year = {2019},
}
Publisher's Version
STOC '19: "Random Walks and Forbidden ..."
Random Walks and Forbidden Minors II: A poly(d ε⁻¹)-Query Tester for Minor-Closed Properties of Bounded Degree Graphs
Akash Kumar, C. Seshadhri, and Andrew Stolman
(Purdue University, USA; University of California at Santa Cruz, USA)
@InProceedings{STOC19p701,
author = {Akash Kumar and C. Seshadhri and Andrew Stolman},
title = {Random Walks and Forbidden Minors II: A poly(<i>d ε</i>⁻¹)-Query Tester for Minor-Closed Properties of Bounded Degree Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {701-700},
doi = {10.1145/3313276.3316330},
year = {2019},
}
Publisher's Version
STOC '19: "Towards the Locality of Vizing’s ..."
Towards the Locality of Vizing’s Theorem
Hsin-Hao Su and Hoa T. Vu
(Boston College, USA)
@InProceedings{STOC19p435,
author = {Hsin-Hao Su and Hoa T. Vu},
title = {Towards the Locality of Vizing’s Theorem},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {435-434},
doi = {10.1145/3313276.3316393},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum Singular Value Transformation ..."
Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe
(CWI, Netherlands; University of Amsterdam, Netherlands; University of Maryland, USA; Microsoft Research, USA)
@InProceedings{STOC19p239,
author = {András Gilyén and Yuan Su and Guang Hao Low and Nathan Wiebe},
title = {Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {239-238},
doi = {10.1145/3313276.3316366},
year = {2019},
}
Publisher's Version
STOC '19: "Capacity Lower Bound for the ..."
Capacity Lower Bound for the Ising Perceptron
Jian Ding and Nike Sun
(University of Pennsylvania, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1009,
author = {Jian Ding and Nike Sun},
title = {Capacity Lower Bound for the Ising Perceptron},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1009-1008},
doi = {10.1145/3313276.3316383},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum Lovász Local Lemma: ..."
Quantum Lovász Local Lemma: Shearer’s Bound Is Tight
Kun He, Qian Li, Xiaoming Sun, and Jiapeng Zhang
(Institute of Computing Technology at Chinese Academy of Sciences, China; University of Chinese Academy of Sciences, China; Shenzhen Institute of Computing Sciences, China; Shenzhen University, China; University of California at San Diego, USA)
@InProceedings{STOC19p575,
author = {Kun He and Qian Li and Xiaoming Sun and Jiapeng Zhang},
title = {Quantum Lovász Local Lemma: Shearer’s Bound Is Tight},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {575-574},
doi = {10.1145/3313276.3316392},
year = {2019},
}
Publisher's Version
STOC '19: "Approximation Algorithms for ..."
Approximation Algorithms for Minimum Norm and Ordered Optimization Problems
Deeparnab Chakrabarty and Chaitanya Swamy
(Dartmouth College, USA; University of Waterloo, Canada)
@InProceedings{STOC19p155,
author = {Deeparnab Chakrabarty and Chaitanya Swamy},
title = {Approximation Algorithms for Minimum Norm and Ordered Optimization Problems},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {155-154},
doi = {10.1145/3313276.3316322},
year = {2019},
}
Publisher's Version
STOC '19: "Approximation Algorithms for ..."
Approximation Algorithms for Distributionally-Robust Stochastic Optimization with Black-Box Distributions
André Linhares and Chaitanya Swamy
(University of Waterloo, Canada)
@InProceedings{STOC19p953,
author = {André Linhares and Chaitanya Swamy},
title = {Approximation Algorithms for Distributionally-Robust Stochastic Optimization with Black-Box Distributions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {953-952},
doi = {10.1145/3313276.3316391},
year = {2019},
}
Publisher's Version
STOC '19: "Oracle Separation of BQP and ..."
Oracle Separation of BQP and PH
Ran Raz and Avishay Tal
(Princeton University, USA; Stanford University, USA)
@InProceedings{STOC19p15,
author = {Ran Raz and Avishay Tal},
title = {Oracle Separation of BQP and PH},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {15-14},
doi = {10.1145/3313276.3316315},
year = {2019},
}
Publisher's Version
STOC '19: "Exponential Separation between ..."
Exponential Separation between Shallow Quantum Circuits and Unbounded Fan-In Shallow Classical Circuits
Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal
(Massachusetts Institute of Technology, USA; Microsoft Research, USA; Stanford University, USA)
@InProceedings{STOC19p645,
author = {Adam Bene Watts and Robin Kothari and Luke Schaeffer and Avishay Tal},
title = {Exponential Separation between Shallow Quantum Circuits and Unbounded Fan-In Shallow Classical Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {645-644},
doi = {10.1145/3313276.3316404},
year = {2019},
}
Publisher's Version
STOC '19: "Pseudorandom Generators for ..."
Pseudorandom Generators for Width-3 Branching Programs
Raghu Meka, Omer Reingold, and Avishay Tal
(University of California at Los Angeles, USA; Stanford University, USA)
@InProceedings{STOC19p785,
author = {Raghu Meka and Omer Reingold and Avishay Tal},
title = {Pseudorandom Generators for Width-3 Branching Programs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {785-784},
doi = {10.1145/3313276.3316319},
year = {2019},
}
Publisher's Version
STOC '19: "Private Selection from Private ..."
Private Selection from Private Candidates
Jingcheng Liu and Kunal Talwar
(University of California at Berkeley, USA; Google Brain, USA)
@InProceedings{STOC19p365,
author = {Jingcheng Liu and Kunal Talwar},
title = {Private Selection from Private Candidates},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {365-364},
doi = {10.1145/3313276.3316377},
year = {2019},
}
Publisher's Version
STOC '19: "Fooling Polytopes ..."
Fooling Polytopes
Ryan O'Donnell, Rocco A. Servedio, and Li-Yang Tan
(Carnegie Mellon University, USA; Columbia University, USA; Stanford University, USA)
@InProceedings{STOC19p771,
author = {Ryan O'Donnell and Rocco A. Servedio and Li-Yang Tan},
title = {Fooling Polytopes},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {771-770},
doi = {10.1145/3313276.3316321},
year = {2019},
}
Publisher's Version
STOC '19: "A Quantum-Inspired Classical ..."
A Quantum-Inspired Classical Algorithm for Recommendation Systems
Ewin Tang
(University of Texas at Austin, USA)
@InProceedings{STOC19p267,
author = {Ewin Tang},
title = {A Quantum-Inspired Classical Algorithm for Recommendation Systems},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {267-266},
doi = {10.1145/3313276.3316310},
year = {2019},
}
Publisher's Version
STOC '19: "Tight Approximation Ratio ..."
Tight Approximation Ratio of Anonymous Pricing
Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Gavin Tang, and Tao Xiao
(Columbia University, USA; Shanghai University of Finance and Economics, China; Hong Kong University of Science and Technology, China; Shanghai Jiao Tong University, China)
@InProceedings{STOC19p841,
author = {Yaonan Jin and Pinyan Lu and Qi Qi and Zhihao Gavin Tang and Tao Xiao},
title = {Tight Approximation Ratio of Anonymous Pricing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {841-840},
doi = {10.1145/3313276.3316331},
year = {2019},
}
Publisher's Version
STOC '19: "Planar Point Sets Determine ..."
Planar Point Sets Determine Many Pairwise Crossing Segments
János Pach, Natan Rubin, and Gábor Tardos
(EPFL, Switzerland; Renyi Institute, Hungary; Ben-Gurion University of the Negev, Israel; Central European University, Hungary)
@InProceedings{STOC19p1457,
author = {János Pach and Natan Rubin and Gábor Tardos},
title = {Planar Point Sets Determine Many Pairwise Crossing Segments},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1457-1456},
doi = {10.1145/3313276.3316328},
year = {2019},
}
Publisher's Version
STOC '19: "Bootstrapping Results for ..."
Bootstrapping Results for Threshold Circuits “Just Beyond” Known Lower Bounds
Lijie Chen and Roei Tell
(Massachusetts Institute of Technology, USA; Weizmann Institute of Science, Israel)
@InProceedings{STOC19p43,
author = {Lijie Chen and Roei Tell},
title = {Bootstrapping Results for Threshold Circuits “Just Beyond” Known Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {43-42},
doi = {10.1145/3313276.3316333},
year = {2019},
}
Publisher's Version
STOC '19: "A Fixed-Depth Size-Hierarchy ..."
A Fixed-Depth Size-Hierarchy Theorem for AC0[⊕] via the Coin Problem
Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh
(IIT Bombay, India; IIT Hyderabad, India)
@InProceedings{STOC19p547,
author = {Nutan Limaye and Karteek Sreenivasaiah and Srikanth Srinivasan and Utkarsh Tripathi and S. Venkitesh},
title = {A Fixed-Depth Size-Hierarchy Theorem for AC<sup>0</sup>[⊕] via the Coin Problem},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {547-546},
doi = {10.1145/3313276.3316339},
year = {2019},
}
Publisher's Version
STOC '19: "Planar Graphs of Bounded Degree ..."
Planar Graphs of Bounded Degree Have Bounded Queue Number
Michael Bekos, Henry Förster, Martin Gronemann, Tamara Mchedlidze, Fabrizio Montecchiani, Chrysanthi Raftopoulou, and Torsten Ueckerdt
(University of Tübingen, Germany; University of Cologne, Germany; KIT, Germany; University of Perugia, Italy; National Technical University of Athens, Greece)
@InProceedings{STOC19p211,
author = {Michael Bekos and Henry Förster and Martin Gronemann and Tamara Mchedlidze and Fabrizio Montecchiani and Chrysanthi Raftopoulou and Torsten Ueckerdt},
title = {Planar Graphs of Bounded Degree Have Bounded Queue Number},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {211-210},
doi = {10.1145/3313276.3316324},
year = {2019},
}
Publisher's Version
STOC '19: "The Structure of Optimal Private ..."
The Structure of Optimal Private Tests for Simple Hypotheses
Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam Smith, and Jonathan Ullman
(Stanford University, USA; Simons Institute for the Theory of Computing Berkeley, USA; Boston University, USA; Northeastern University, USA)
@InProceedings{STOC19p379,
author = {Clément L. Canonne and Gautam Kamath and Audra McMillan and Adam Smith and Jonathan Ullman},
title = {The Structure of Optimal Private Tests for Simple Hypotheses},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {379-378},
doi = {10.1145/3313276.3316336},
year = {2019},
}
Publisher's Version
STOC '19: "New Polynomial Delay Bounds ..."
New Polynomial Delay Bounds for Maximal Subgraph Enumeration by Proximity Search
Alessio Conte and Takeaki Uno
(National Institute of Informatics, Japan; University of Pisa, Italy)
@InProceedings{STOC19p1485,
author = {Alessio Conte and Takeaki Uno},
title = {New Polynomial Delay Bounds for Maximal Subgraph Enumeration by Proximity Search},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1485-1484},
doi = {10.1145/3313276.3316402},
year = {2019},
}
Publisher's Version
STOC '19: "Memory-Sample Tradeoffs for ..."
Memory-Sample Tradeoffs for Linear Regression with Small Error
Vatsal Sharan, Aaron Sidford, and Gregory Valiant
(Stanford University, USA)
@InProceedings{STOC19p1107,
author = {Vatsal Sharan and Aaron Sidford and Gregory Valiant},
title = {Memory-Sample Tradeoffs for Linear Regression with Small Error},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1107-1106},
doi = {10.1145/3313276.3316403},
year = {2019},
}
Publisher's Version
STOC '19: "A Strongly Polynomial Algorithm ..."
A Strongly Polynomial Algorithm for Linear Exchange Markets
Jugal Garg and László A. Végh
(University of Illinois at Urbana-Champaign, USA; London School of Economics and Political Science, UK)
@InProceedings{STOC19p71,
author = {Jugal Garg and László A. Végh},
title = {A Strongly Polynomial Algorithm for Linear Exchange Markets},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {71-70},
doi = {10.1145/3313276.3316340},
year = {2019},
}
Publisher's Version
STOC '19: "A Universal Sampling Method ..."
A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh
(Tel Aviv University, Israel; EPFL, Switzerland; Microsoft Research, USA; Princeton University, USA; Google Research, USA)
@InProceedings{STOC19p1317,
author = {Haim Avron and Michael Kapralov and Cameron Musco and Christopher Musco and Ameya Velingker and Amir Zandieh},
title = {A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1317-1316},
doi = {10.1145/3313276.3316363},
year = {2019},
}
Publisher's Version
STOC '19: "A Fixed-Depth Size-Hierarchy ..."
A Fixed-Depth Size-Hierarchy Theorem for AC0[⊕] via the Coin Problem
Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh
(IIT Bombay, India; IIT Hyderabad, India)
@InProceedings{STOC19p547,
author = {Nutan Limaye and Karteek Sreenivasaiah and Srikanth Srinivasan and Utkarsh Tripathi and S. Venkitesh},
title = {A Fixed-Depth Size-Hierarchy Theorem for AC<sup>0</sup>[⊕] via the Coin Problem},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {547-546},
doi = {10.1145/3313276.3316339},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum Proof Systems for ..."
Quantum Proof Systems for Iterated Exponential Time, and Beyond
Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, and Henry Yuen
(Horizon Quantum Computing, Singapore; University of Technology Sydney, Australia; California Institute of Technology, USA; University of Toronto, Canada)
@InProceedings{STOC19p589,
author = {Joseph Fitzsimons and Zhengfeng Ji and Thomas Vidick and Henry Yuen},
title = {Quantum Proof Systems for Iterated Exponential Time, and Beyond},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {589-588},
doi = {10.1145/3313276.3316343},
year = {2019},
}
Publisher's Version
STOC '19: "Log-Concave Polynomials II: ..."
Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant
(Stanford University, USA; University of Washington, USA; North Carolina State University, USA)
@InProceedings{STOC19p1,
author = {Nima Anari and Kuikui Liu and Shayan Oveis Gharan and Cynthia Vinzant},
title = {Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1-0},
doi = {10.1145/3313276.3316385},
year = {2019},
}
Publisher's Version
STOC '19: "Dynamic Sampling from Graphical ..."
Dynamic Sampling from Graphical Models
Weiming Feng, Nisheeth K. Vishnoi, and Yitong Yin
(Nanjing University, China; Yale University, USA)
@InProceedings{STOC19p1345,
author = {Weiming Feng and Nisheeth K. Vishnoi and Yitong Yin},
title = {Dynamic Sampling from Graphical Models},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1345-1344},
doi = {10.1145/3313276.3316365},
year = {2019},
}
Publisher's Version
STOC '19: "Submodular Maximization with ..."
Submodular Maximization with Matroid and Packing Constraints in Parallel
Alina Ene, Huy L. Nguyễn, and Adrian Vladu
(Boston University, USA; Northeastern University, USA)
@InProceedings{STOC19p113,
author = {Alina Ene and Huy L. Nguyễn and Adrian Vladu},
title = {Submodular Maximization with Matroid and Packing Constraints in Parallel},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {113-112},
doi = {10.1145/3313276.3316389},
year = {2019},
}
Publisher's Version
STOC '19: "Towards the Locality of Vizing’s ..."
Towards the Locality of Vizing’s Theorem
Hsin-Hao Su and Hoa T. Vu
(Boston College, USA)
@InProceedings{STOC19p435,
author = {Hsin-Hao Su and Hoa T. Vu},
title = {Towards the Locality of Vizing’s Theorem},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {435-434},
doi = {10.1145/3313276.3316393},
year = {2019},
}
Publisher's Version
STOC '19: "Graph Pattern Detection: Hardness ..."
Graph Pattern Detection: Hardness for All Induced Patterns and Faster Non-induced Cycles
Mina Dalirrooyfard, Thuy Duong Vuong, and Virginia Vassilevska Williams
(Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1471,
author = {Mina Dalirrooyfard and Thuy Duong Vuong and Virginia Vassilevska Williams},
title = {Graph Pattern Detection: Hardness for All Induced Patterns and Faster Non-induced Cycles},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1471-1470},
doi = {10.1145/3313276.3316329},
year = {2019},
}
Publisher's Version
STOC '19: "Testing Unateness Nearly Optimally ..."
Testing Unateness Nearly Optimally
Xi Chen and Erik Waingarten
(Columbia University, USA)
@InProceedings{STOC19p687,
author = {Xi Chen and Erik Waingarten},
title = {Testing Unateness Nearly Optimally},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {687-686},
doi = {10.1145/3313276.3316351},
year = {2019},
}
Publisher's Version
STOC '19: "Flows in Almost Linear Time ..."
Flows in Almost Linear Time via Adaptive Preconditioning
Rasmus Kyng, Richard Peng, Sushant Sachdeva, and Di Wang
(Harvard University, USA; Georgia Tech, USA; Microsoft Research, USA; University of Toronto, Canada)
@InProceedings{STOC19p1121,
author = {Rasmus Kyng and Richard Peng and Sushant Sachdeva and Di Wang},
title = {Flows in Almost Linear Time via Adaptive Preconditioning},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1121-1120},
doi = {10.1145/3313276.3316410},
year = {2019},
}
Publisher's Version
STOC '19: "Exponential Separation between ..."
Exponential Separation between Shallow Quantum Circuits and Unbounded Fan-In Shallow Classical Circuits
Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal
(Massachusetts Institute of Technology, USA; Microsoft Research, USA; Stanford University, USA)
@InProceedings{STOC19p645,
author = {Adam Bene Watts and Robin Kothari and Luke Schaeffer and Avishay Tal},
title = {Exponential Separation between Shallow Quantum Circuits and Unbounded Fan-In Shallow Classical Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {645-644},
doi = {10.1145/3313276.3316404},
year = {2019},
}
Publisher's Version
STOC '19: "Approximating APSP without ..."
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max
Karl Bringmann, Marvin Künnemann, and Karol Węgrzycki
(Max Planck Institute for Informatics, Germany; University of Warsaw, Poland)
@InProceedings{STOC19p1177,
author = {Karl Bringmann and Marvin Künnemann and Karol Węgrzycki},
title = {Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1177-1176},
doi = {10.1145/3313276.3316373},
year = {2019},
}
Publisher's Version
STOC '19: "Almost Optimal Distance Oracles ..."
Almost Optimal Distance Oracles for Planar Graphs
Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, and Oren Weimann
(King's College London, UK; University of Wrocław, Poland; IDC Herzliya, Israel; University of Haifa, Israel)
@InProceedings{STOC19p169,
author = {Panagiotis Charalampopoulos and Paweł Gawrychowski and Shay Mozes and Oren Weimann},
title = {Almost Optimal Distance Oracles for Planar Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {169-168},
doi = {10.1145/3313276.3316316},
year = {2019},
}
Publisher's Version
STOC '19: "Spectral Methods from Tensor ..."
Spectral Methods from Tensor Networks
Ankur Moitra and Alexander S. Wein
(Massachusetts Institute of Technology, USA; New York University, USA)
@InProceedings{STOC19p1149,
author = {Ankur Moitra and Alexander S. Wein},
title = {Spectral Methods from Tensor Networks},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1149-1148},
doi = {10.1145/3313276.3316357},
year = {2019},
}
Publisher's Version
STOC '19: "Optimal (and Benchmark-Optimal) ..."
Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items
Hedyeh Beyhaghi and S. Matthew Weinberg
(Cornell University, USA; Princeton University, USA)
@InProceedings{STOC19p855,
author = {Hedyeh Beyhaghi and S. Matthew Weinberg},
title = {Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {855-854},
doi = {10.1145/3313276.3316405},
year = {2019},
}
Publisher's Version
STOC '19: "Static Data Structure Lower ..."
Static Data Structure Lower Bounds Imply Rigidity
Zeev Dvir, Alexander Golovnev, and Omri Weinstein
(Princeton University, USA; Harvard University, USA; Columbia University, USA)
@InProceedings{STOC19p1205,
author = {Zeev Dvir and Alexander Golovnev and Omri Weinstein},
title = {Static Data Structure Lower Bounds Imply Rigidity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1205-1204},
doi = {10.1145/3313276.3316348},
year = {2019},
}
Publisher's Version
STOC '19: "Local Decodability of the ..."
Local Decodability of the Burrows-Wheeler Transform
Sandip Sinha and Omri Weinstein
(Columbia University, USA)
@InProceedings{STOC19p925,
author = {Sandip Sinha and Omri Weinstein},
title = {Local Decodability of the Burrows-Wheeler Transform},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {925-924},
doi = {10.1145/3313276.3316317},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum Weak Coin Flipping ..."
Quantum Weak Coin Flipping
Atul Singh Arora, Jérémie Roland, and Stephan Weis
(Université libre de Bruxelles, Belgium)
@InProceedings{STOC19p253,
author = {Atul Singh Arora and Jérémie Roland and Stephan Weis},
title = {Quantum Weak Coin Flipping},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {253-252},
doi = {10.1145/3313276.3316306},
year = {2019},
}
Publisher's Version
STOC '19: "Fiat-Shamir: From Practice ..."
Fiat-Shamir: From Practice to Theory
Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, and Daniel Wichs
(Boston University, USA; Tel Aviv University, Israel; Visa Research, USA; Princeton University, USA; Massachusetts Institute of Technology, USA; Weizmann Institute of Science, Israel; Technion, Israel; Northeastern University, USA)
@InProceedings{STOC19p1359,
author = {Ran Canetti and Yilei Chen and Justin Holmgren and Alex Lombardi and Guy N. Rothblum and Ron D. Rothblum and Daniel Wichs},
title = {Fiat-Shamir: From Practice to Theory},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1359-1358},
doi = {10.1145/3313276.3316380},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum Singular Value Transformation ..."
Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe
(CWI, Netherlands; University of Amsterdam, Netherlands; University of Maryland, USA; Microsoft Research, USA)
@InProceedings{STOC19p239,
author = {András Gilyén and Yuan Su and Guang Hao Low and Nathan Wiebe},
title = {Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {239-238},
doi = {10.1145/3313276.3316366},
year = {2019},
}
Publisher's Version
STOC '19: "A Unifying Method for the ..."
A Unifying Method for the Design of Algorithms Canonizing Combinatorial Objects
Pascal Schweitzer and Daniel Wiebking
(TU Kaiserslautern, Germany; RWTH Aachen University, Germany)
@InProceedings{STOC19p1569,
author = {Pascal Schweitzer and Daniel Wiebking},
title = {A Unifying Method for the Design of Algorithms Canonizing Combinatorial Objects},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1569-1568},
doi = {10.1145/3313276.3316338},
year = {2019},
}
Publisher's Version
STOC '19: "Weak Lower Bounds on Resource-Bounded ..."
Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes
Dylan M. McKay, Cody D. Murray, and R. Ryan Williams
(Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)
@InProceedings{STOC19p1527,
author = {Dylan M. McKay and Cody D. Murray and R. Ryan Williams},
title = {Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1527-1526},
doi = {10.1145/3313276.3316396},
year = {2019},
}
Publisher's Version
STOC '19: "Graph Pattern Detection: Hardness ..."
Graph Pattern Detection: Hardness for All Induced Patterns and Faster Non-induced Cycles
Mina Dalirrooyfard, Thuy Duong Vuong, and Virginia Vassilevska Williams
(Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1471,
author = {Mina Dalirrooyfard and Thuy Duong Vuong and Virginia Vassilevska Williams},
title = {Graph Pattern Detection: Hardness for All Induced Patterns and Faster Non-induced Cycles},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1471-1470},
doi = {10.1145/3313276.3316329},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum State Certification ..."
Quantum State Certification
Costin Bădescu, Ryan O'Donnell, and John Wright
(Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p631,
author = {Costin Bădescu and Ryan O'Donnell and John Wright},
title = {Quantum State Certification},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {631-630},
doi = {10.1145/3313276.3316344},
year = {2019},
}
Publisher's Version
STOC '19: "Near-Optimal Lower Bounds ..."
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC0
Alexander A. Sherstov and Pei Wu
(University of California at Los Angeles, USA)
@InProceedings{STOC19p491,
author = {Alexander A. Sherstov and Pei Wu},
title = {Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC<sup>0</sup>},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {491-490},
doi = {10.1145/3313276.3316408},
year = {2019},
}
Publisher's Version
STOC '19: "Decremental Strongly-Connected ..."
Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time
Aaron Bernstein, Maximilian Probst, and Christian Wulff-Nilsen
(Rutgers University, USA; University of Copenhagen, Denmark)
@InProceedings{STOC19p449,
author = {Aaron Bernstein and Maximilian Probst and Christian Wulff-Nilsen},
title = {Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {449-448},
doi = {10.1145/3313276.3316335},
year = {2019},
}
Publisher's Version
STOC '19: "Tight Approximation Ratio ..."
Tight Approximation Ratio of Anonymous Pricing
Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Gavin Tang, and Tao Xiao
(Columbia University, USA; Shanghai University of Finance and Economics, China; Hong Kong University of Science and Technology, China; Shanghai Jiao Tong University, China)
@InProceedings{STOC19p841,
author = {Yaonan Jin and Pinyan Lu and Qi Qi and Zhihao Gavin Tang and Tao Xiao},
title = {Tight Approximation Ratio of Anonymous Pricing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {841-840},
doi = {10.1145/3313276.3316331},
year = {2019},
}
Publisher's Version
STOC '19: "How to Delegate Computations ..."
How to Delegate Computations Publicly
Yael Tauman Kalai, Omer Paneth, and Lisa Yang
(Microsoft Research, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p1401,
author = {Yael Tauman Kalai and Omer Paneth and Lisa Yang},
title = {How to Delegate Computations Publicly},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1401-1400},
doi = {10.1145/3313276.3316411},
year = {2019},
}
Publisher's Version
STOC '19: "The Parallel Repetition of ..."
The Parallel Repetition of Non-signaling Games: Counterexamples and Dichotomy
Justin Holmgren and Lisa Yang
(Princeton University, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC19p225,
author = {Justin Holmgren and Lisa Yang},
title = {The Parallel Repetition of Non-signaling Games: Counterexamples and Dichotomy},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {225-224},
doi = {10.1145/3313276.3316367},
year = {2019},
}
Publisher's Version
STOC '19: "Separating Monotone VP and ..."
Separating Monotone VP and VNP
Amir Yehudayoff
(Technion, Israel)
@InProceedings{STOC19p519,
author = {Amir Yehudayoff},
title = {Separating Monotone VP and VNP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {519-518},
doi = {10.1145/3313276.3316311},
year = {2019},
}
Publisher's Version
STOC '19: "Dynamic Sampling from Graphical ..."
Dynamic Sampling from Graphical Models
Weiming Feng, Nisheeth K. Vishnoi, and Yitong Yin
(Nanjing University, China; Yale University, USA)
@InProceedings{STOC19p1345,
author = {Weiming Feng and Nisheeth K. Vishnoi and Yitong Yin},
title = {Dynamic Sampling from Graphical Models},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1345-1344},
doi = {10.1145/3313276.3316365},
year = {2019},
}
Publisher's Version
STOC '19: "Breaking Quadratic Time for ..."
Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme
Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai
(KTH, Sweden; Toyota Technological Institute at Chicago, USA; Michigan State University, USA; Aalto University, Finland)
@InProceedings{STOC19p295,
author = {Danupon Nanongkai and Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai},
title = {Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {295-294},
doi = {10.1145/3313276.3316394},
year = {2019},
}
Publisher's Version
STOC '19: "Optimal Succinct Rank Data ..."
Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition
Huacheng Yu
(Harvard University, USA)
@InProceedings{STOC19p1191,
author = {Huacheng Yu},
title = {Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1191-1190},
doi = {10.1145/3313276.3316352},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum Proof Systems for ..."
Quantum Proof Systems for Iterated Exponential Time, and Beyond
Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, and Henry Yuen
(Horizon Quantum Computing, Singapore; University of Technology Sydney, Australia; California Institute of Technology, USA; University of Toronto, Canada)
@InProceedings{STOC19p589,
author = {Joseph Fitzsimons and Zhengfeng Ji and Thomas Vidick and Henry Yuen},
title = {Quantum Proof Systems for Iterated Exponential Time, and Beyond},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {589-588},
doi = {10.1145/3313276.3316343},
year = {2019},
}
Publisher's Version
STOC '19: "Good Approximate Quantum LDPC ..."
Good Approximate Quantum LDPC Codes from Spacetime Circuit Hamiltonians
Thomas C. Bohdanowicz, Elizabeth Crosson, Chinmay Nirkhe, and Henry Yuen
(California Institute of Technology, USA; University of New Mexico, USA; University of California at Berkeley, USA; University of Toronto, Canada)
@InProceedings{STOC19p603,
author = {Thomas C. Bohdanowicz and Elizabeth Crosson and Chinmay Nirkhe and Henry Yuen},
title = {Good Approximate Quantum LDPC Codes from Spacetime Circuit Hamiltonians},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {603-602},
doi = {10.1145/3313276.3316384},
year = {2019},
}
Publisher's Version
STOC '19: "Faster k-SAT Algorithms ..."
Faster k-SAT Algorithms using Biased-PPSZ
Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, and Uri Zwick
(University of Copenhagen, Denmark; Tel Aviv University, Israel)
@InProceedings{STOC19p729,
author = {Thomas Dueholm Hansen and Haim Kaplan and Or Zamir and Uri Zwick},
title = {Faster <i>k</i>-SAT Algorithms using Biased-PPSZ},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {729-728},
doi = {10.1145/3313276.3316359},
year = {2019},
}
Publisher's Version
STOC '19: "A Universal Sampling Method ..."
A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh
(Tel Aviv University, Israel; EPFL, Switzerland; Microsoft Research, USA; Princeton University, USA; Google Research, USA)
@InProceedings{STOC19p1317,
author = {Haim Avron and Michael Kapralov and Cameron Musco and Christopher Musco and Ameya Velingker and Amir Zandieh},
title = {A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1317-1316},
doi = {10.1145/3313276.3316363},
year = {2019},
}
Publisher's Version
STOC '19: "DNF Sparsification beyond ..."
DNF Sparsification beyond Sunflowers
Shachar Lovett and Jiapeng Zhang
(University of California at San Diego, USA)
@InProceedings{STOC19p561,
author = {Shachar Lovett and Jiapeng Zhang},
title = {DNF Sparsification beyond Sunflowers},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {561-560},
doi = {10.1145/3313276.3316323},
year = {2019},
}
Publisher's Version
STOC '19: "Quantum Lovász Local Lemma: ..."
Quantum Lovász Local Lemma: Shearer’s Bound Is Tight
Kun He, Qian Li, Xiaoming Sun, and Jiapeng Zhang
(Institute of Computing Technology at Chinese Academy of Sciences, China; University of Chinese Academy of Sciences, China; Shenzhen Institute of Computing Sciences, China; Shenzhen University, China; University of California at San Diego, USA)
@InProceedings{STOC19p575,
author = {Kun He and Qian Li and Xiaoming Sun and Jiapeng Zhang},
title = {Quantum Lovász Local Lemma: Shearer’s Bound Is Tight},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {575-574},
doi = {10.1145/3313276.3316392},
year = {2019},
}
Publisher's Version
STOC '19: "Optimal Sequence Length Requirements ..."
Optimal Sequence Length Requirements for Phylogenetic Tree Reconstruction with Indels
Arun Ganesh and Qiuyi (Richard) Zhang
(University of California at Berkeley, USA)
@InProceedings{STOC19p897,
author = {Arun Ganesh and Qiuyi (Richard) Zhang},
title = {Optimal Sequence Length Requirements for Phylogenetic Tree Reconstruction with Indels},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {897-896},
doi = {10.1145/3313276.3316345},
year = {2019},
}
Publisher's Version
STOC '19: "Settling the Sample Complexity ..."
Settling the Sample Complexity of Single-Parameter Revenue Maximization
Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang
(Tsinghua University, China; University of Hong Kong, China)
@InProceedings{STOC19p827,
author = {Chenghao Guo and Zhiyi Huang and Xinzhi Zhang},
title = {Settling the Sample Complexity of Single-Parameter Revenue Maximization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {827-826},
doi = {10.1145/3313276.3316325},
year = {2019},
}
Publisher's Version
STOC '19: "Why Extension-Based Proofs ..."
Why Extension-Based Proofs Fail
Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu
(IST Austria, Austria; Yale University, USA; University of Toronto, Canada)
@InProceedings{STOC19p1233,
author = {Dan Alistarh and James Aspnes and Faith Ellen and Rati Gelashvili and Leqi Zhu},
title = {Why Extension-Based Proofs Fail},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1233-1232},
doi = {10.1145/3313276.3316407},
year = {2019},
}
Publisher's Version
STOC '19: "Faster k-SAT Algorithms ..."
Faster k-SAT Algorithms using Biased-PPSZ
Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, and Uri Zwick
(University of Copenhagen, Denmark; Tel Aviv University, Israel)
@InProceedings{STOC19p729,
author = {Thomas Dueholm Hansen and Haim Kaplan and Or Zamir and Uri Zwick},
title = {Faster <i>k</i>-SAT Algorithms using Biased-PPSZ},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {729-728},
doi = {10.1145/3313276.3316359},
year = {2019},
}
Publisher's Version