| |
Aaronson, Scott
|
STOC '18: "Shadow Tomography of Quantum ..."
Shadow Tomography of Quantum States
Scott Aaronson
(University of Texas at Austin, USA)
@InProceedings{STOC18p395,
author = {Scott Aaronson},
title = {Shadow Tomography of Quantum States},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {395-394},
doi = {10.1145/3188745.3188802},
year = {2018},
}
 Publisher's Version
Article: stoc18main-p113-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188802
|
| |
Abboud, Amir |
STOC '18: "More Consequences of Falsifying ..."
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof
(IBM Research, USA; Max Planck Institute for Informatics, Germany; Saarland University, Germany; M2CI, Germany; Eindhoven University of Technology, Netherlands)
@InProceedings{STOC18p311,
author = {Amir Abboud and Karl Bringmann and Holger Dell and Jesper Nederlof},
title = {More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {311-310},
doi = {10.1145/3188745.3188938},
year = {2018},
}
Publisher's Version
Article: stoc18main-p376-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188938
|
| |
Abraham, Ittai |
STOC '18: "Metric Embedding via Shortest ..."
Metric Embedding via Shortest Path Decompositions
Ittai Abraham, Arnold Filtser, Anupam Gupta, and Ofer Neiman
(VMware, USA; Ben-Gurion University of the Negev, Israel; Carnegie Mellon University, USA)
@InProceedings{STOC18p1109,
author = {Ittai Abraham and Arnold Filtser and Anupam Gupta and Ofer Neiman},
title = {Metric Embedding via Shortest Path Decompositions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1109-1108},
doi = {10.1145/3188745.3188808},
year = {2018},
}
Publisher's Version
Article: stoc18main-p116-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188808
|
| |
Abrahamsen, Mikkel |
STOC '18: "Fast Fencing ..."
Fast Fencing
Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, and Mikkel Thorup
(University of Copenhagen, Denmark; Max Planck Institute for Informatics, Germany; Sorbonne University, France; UPMC, France; CNRS, France; LIP6, France; Eindhoven University of Technology, Netherlands; DTU, Denmark)
@InProceedings{STOC18p661,
author = {Mikkel Abrahamsen and Anna Adamaszek and Karl Bringmann and Vincent Cohen-Addad and Mehran Mehr and Eva Rotenberg and Alan Roytman and Mikkel Thorup},
title = {Fast Fencing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {661-660},
doi = {10.1145/3188745.3188878},
year = {2018},
}
Publisher's Version
Article: stoc18main-p248-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188878
STOC '18: "The Art Gallery Problem Is ..."
The Art Gallery Problem Is ∃ ℝ-Complete
Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow
(University of Copenhagen, Denmark; Université Libre de Bruxelles, Belgium)
@InProceedings{STOC18p73,
author = {Mikkel Abrahamsen and Anna Adamaszek and Tillmann Miltzow},
title = {The Art Gallery Problem Is ∃ ℝ-Complete},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {73-72},
doi = {},
year = {2018},
}
Article: stoc18main-p233-p (type: Full Paper (14 pages)) doi:
|
| |
Adamaszek, Anna |
STOC '18: "Fast Fencing ..."
Fast Fencing
Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, and Mikkel Thorup
(University of Copenhagen, Denmark; Max Planck Institute for Informatics, Germany; Sorbonne University, France; UPMC, France; CNRS, France; LIP6, France; Eindhoven University of Technology, Netherlands; DTU, Denmark)
@InProceedings{STOC18p661,
author = {Mikkel Abrahamsen and Anna Adamaszek and Karl Bringmann and Vincent Cohen-Addad and Mehran Mehr and Eva Rotenberg and Alan Roytman and Mikkel Thorup},
title = {Fast Fencing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {661-660},
doi = {10.1145/3188745.3188878},
year = {2018},
}
Publisher's Version
Article: stoc18main-p248-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188878
STOC '18: "The Art Gallery Problem Is ..."
The Art Gallery Problem Is ∃ ℝ-Complete
Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow
(University of Copenhagen, Denmark; Université Libre de Bruxelles, Belgium)
@InProceedings{STOC18p73,
author = {Mikkel Abrahamsen and Anna Adamaszek and Tillmann Miltzow},
title = {The Art Gallery Problem Is ∃ ℝ-Complete},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {73-72},
doi = {},
year = {2018},
}
Article: stoc18main-p233-p (type: Full Paper (14 pages)) doi:
|
| |
Agarwal, Udit |
STOC '18: "Fine-Grained Complexity for ..."
Fine-Grained Complexity for Sparse Graphs
Udit Agarwal and Vijaya Ramachandran
(University of Texas at Austin, USA)
@InProceedings{STOC18p297,
author = {Udit Agarwal and Vijaya Ramachandran},
title = {Fine-Grained Complexity for Sparse Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {297-296},
doi = {10.1145/3188745.3188888},
year = {2018},
}
Publisher's Version
Article: stoc18main-p268-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188888
|
| |
Aggarwal, Divesh |
STOC '18: "(Gap/S)ETH Hardness of SVP ..."
(Gap/S)ETH Hardness of SVP
Divesh Aggarwal and Noah Stephens-Davidowitz
(National University of Singapore, Singapore; Princeton University, USA)
@InProceedings{STOC18p283,
author = {Divesh Aggarwal and Noah Stephens-Davidowitz},
title = {(Gap/S)ETH Hardness of SVP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {283-282},
doi = {10.1145/3188745.3188840},
year = {2018},
}
Publisher's Version
Article: stoc18main-p183-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188840
|
| |
Agrawal, Manindra |
STOC '18: "Bootstrapping Variables in ..."
Bootstrapping Variables in Algebraic Circuits
Manindra Agrawal, Sumanta Ghosh, and Nitin Saxena
(IIT Kanpur, India)
@InProceedings{STOC18p1361,
author = {Manindra Agrawal and Sumanta Ghosh and Nitin Saxena},
title = {Bootstrapping Variables in Algebraic Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1361-1360},
doi = {10.1145/3188745.3188762},
year = {2018},
}
Publisher's Version
Article: stoc18main-p14-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188762
|
| |
Allen-Zhu, Zeyuan |
STOC '18: "Operator Scaling via Geodesically ..."
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson
(Microsoft Research, USA; Princeton University, USA; University of Toronto, Canada; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC18p213,
author = {Zeyuan Allen-Zhu and Ankit Garg and Yuanzhi Li and Rafael Oliveira and Avi Wigderson},
title = {Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {213-212},
doi = {10.1145/3188745.3188942},
year = {2018},
}
Publisher's Version
Article: stoc18main-p382-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188942
|
| |
Alman, Josh |
STOC '18: "Cell-Probe Lower Bounds from ..."
Cell-Probe Lower Bounds from Online Communication Complexity
Josh Alman, Joshua R. Wang, and Huacheng Yu
(Massachusetts Institute of Technology, USA; Stanford University, USA; Harvard University, USA)
@InProceedings{STOC18p1165,
author = {Josh Alman and Joshua R. Wang and Huacheng Yu},
title = {Cell-Probe Lower Bounds from Online Communication Complexity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1165-1164},
doi = {10.1145/3188745.3188862},
year = {2018},
}
Publisher's Version
Article: stoc18main-p223-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188862
|
| |
Andoni, Alexandr |
STOC '18: "Data-Dependent Hashing via ..."
Data-Dependent Hashing via Nonlinear Spectral Gaps
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten
(Columbia University, USA; Princeton University, USA; University of Toronto, Canada; Microsoft Research, USA)
@InProceedings{STOC18p913,
author = {Alexandr Andoni and Assaf Naor and Aleksandar Nikolov and Ilya Razenshteyn and Erik Waingarten},
title = {Data-Dependent Hashing via Nonlinear Spectral Gaps},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {913-912},
doi = {10.1145/3188745.3188846},
year = {2018},
}
Publisher's Version
Article: stoc18main-p189-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188846
|
| |
Assadi, Sepehr |
STOC '18: "Fully Dynamic Maximal Independent ..."
Fully Dynamic Maximal Independent Set with Sublinear Update Time
Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon
(University of Pennsylvania, USA; IBM Research, USA)
@InProceedings{STOC18p941,
author = {Sepehr Assadi and Krzysztof Onak and Baruch Schieber and Shay Solomon},
title = {Fully Dynamic Maximal Independent Set with Sublinear Update Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {941-940},
doi = {10.1145/3188745.3188922},
year = {2018},
}
Publisher's Version
Article: stoc18main-p309-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188922
|
| |
Atserias, Albert |
STOC '18: "Clique Is Hard on Average ..."
Clique Is Hard on Average for Regular Resolution
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, and Alexander Razborov
(Universitat Politècnica de Catalunya, Spain; KTH, Sweden; Sapienza University of Rome, Italy; University of Chicago, USA; Russian Academy of Sciences, Russia)
@InProceedings{STOC18p997,
author = {Albert Atserias and Ilario Bonacina and Susanna F. de Rezende and Massimo Lauria and Jakob Nordström and Alexander Razborov},
title = {Clique Is Hard on Average for Regular Resolution},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {997-996},
doi = {10.1145/3188745.3188856},
year = {2018},
}
Publisher's Version
Article: stoc18main-p211-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188856
|
| |
Backurs, Arturs
|
STOC '18: "Towards Tight Approximation ..."
Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein
(Massachusetts Institute of Technology, USA; Bar-Ilan University, Israel)
@InProceedings{STOC18p325,
author = {Arturs Backurs and Liam Roditty and Gilad Segal and Virginia Vassilevska Williams and Nicole Wein},
title = {Towards Tight Approximation Bounds for Graph Diameter and Eccentricities},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {325-324},
doi = {10.1145/3188745.3188950},
year = {2018},
}
Publisher's Version
Article: stoc18main-p403-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188950
|
| |
Badrinarayanan, Saikrishna |
STOC '18: "Succinct Delegation for Low-Space ..."
Succinct Delegation for Low-Space Non-deterministic Computation
Saikrishna Badrinarayanan, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai, and Daniel Wichs
(University of California at Los Angeles, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA; Northeastern University, USA)
@InProceedings{STOC18p829,
author = {Saikrishna Badrinarayanan and Yael Tauman Kalai and Dakshita Khurana and Amit Sahai and Daniel Wichs},
title = {Succinct Delegation for Low-Space Non-deterministic Computation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {829-828},
doi = {10.1145/3188745.3188924},
year = {2018},
}
Publisher's Version
Article: stoc18main-p312-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188924
|
| |
Balkanski, Eric |
STOC '18: "The Adaptive Complexity of ..."
The Adaptive Complexity of Maximizing a Submodular Function
Eric Balkanski and Yaron Singer
(Harvard University, USA)
@InProceedings{STOC18p1333,
author = {Eric Balkanski and Yaron Singer},
title = {The Adaptive Complexity of Maximizing a Submodular Function},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1333-1332},
doi = {10.1145/3188745.3188752},
year = {2018},
}
Publisher's Version
Article: stoc18main-p8-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188752
|
| |
Balliu, Alkida |
STOC '18: "New Classes of Distributed ..."
New Classes of Distributed Time Complexity
Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela
(Aalto University, Finland; University of Freiburg, Germany)
@InProceedings{STOC18p1529,
author = {Alkida Balliu and Juho Hirvonen and Janne H. Korhonen and Tuomo Lempiäinen and Dennis Olivetti and Jukka Suomela},
title = {New Classes of Distributed Time Complexity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1529-1528},
doi = {10.1145/3188745.3188860},
year = {2018},
}
Publisher's Version
Article: stoc18main-p220-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188860
|
| |
Bansal, Nikhil |
STOC '18: "The Gram-Schmidt Walk: A Cure ..."
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett
(Eindhoven University of Technology, Netherlands; CWI, Netherlands; University of California at San Diego, USA)
@InProceedings{STOC18p689,
author = {Nikhil Bansal and Daniel Dadush and Shashwat Garg and Shachar Lovett},
title = {The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {689-688},
doi = {10.1145/3188745.3188850},
year = {2018},
}
Publisher's Version
Article: stoc18main-p195-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188850
|
| |
Bateni, MohammadHossein |
STOC '18: "Fast Algorithms for Knapsack ..."
Fast Algorithms for Knapsack via Convolution and Prediction
MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Saeed Seddighin, and Cliff Stein
(Google, USA; University of Maryland, USA; Columbia University, USA)
@InProceedings{STOC18p1487,
author = {MohammadHossein Bateni and MohammadTaghi Hajiaghayi and Saeed Seddighin and Cliff Stein},
title = {Fast Algorithms for Knapsack via Convolution and Prediction},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1487-1486},
doi = {10.1145/3188745.3188876},
year = {2018},
}
Publisher's Version
Article: stoc18main-p247-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188876
|
| |
Bezáková, Ivona |
STOC '18: "Inapproximability of the Independent ..."
Inapproximability of the Independent Set Polynomial in the Complex Plane
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič
(Rochester Institute of Technology, USA; University of Oxford, UK; University of Rochester, USA)
@InProceedings{STOC18p1431,
author = {Ivona Bezáková and Andreas Galanis and Leslie Ann Goldberg and Daniel Štefankovič},
title = {Inapproximability of the Independent Set Polynomial in the Complex Plane},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1431-1430},
doi = {10.1145/3188745.3188788},
year = {2018},
}
Publisher's Version
Article: stoc18main-p77-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188788
|
| |
Bitansky, Nir |
STOC '18: "Multi-collision Resistance: ..."
Multi-collision Resistance: A Paradigm for Keyless Hash Functions
Nir Bitansky, Yael Tauman Kalai, and Omer Paneth
(Tel Aviv University, Israel; Microsoft, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC18p787,
author = {Nir Bitansky and Yael Tauman Kalai and Omer Paneth},
title = {Multi-collision Resistance: A Paradigm for Keyless Hash Functions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {787-786},
doi = {10.1145/3188745.3188870},
year = {2018},
}
Publisher's Version
Article: stoc18main-p236-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188870
|
| |
Bläser, Markus |
STOC '18: "Generalized Matrix Completion ..."
Generalized Matrix Completion and Algebraic Natural Proofs
Markus Bläser, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov
(Saarland University, Germany; Max Planck Institute for Informatics, Germany)
@InProceedings{STOC18p1389,
author = {Markus Bläser and Christian Ikenmeyer and Gorav Jindal and Vladimir Lysikov},
title = {Generalized Matrix Completion and Algebraic Natural Proofs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1389-1388},
doi = {10.1145/3188745.3188832},
year = {2018},
}
Publisher's Version
Article: stoc18main-p165-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188832
|
| |
Błasiok, Jarosław |
STOC '18: "General Strong Polarization ..."
General Strong Polarization
Jarosław Błasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, and Madhu Sudan
(Harvard University, USA; Carnegie Mellon University, USA; SUNY Buffalo, USA)
@InProceedings{STOC18p563,
author = {Jarosław Błasiok and Venkatesan Guruswami and Preetum Nakkiran and Atri Rudra and Madhu Sudan},
title = {General Strong Polarization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {563-562},
doi = {10.1145/3188745.3188816},
year = {2018},
}
Publisher's Version
Article: stoc18main-p140-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188816
|
| |
Bodlaender, Hans L. |
STOC '18: "A Framework for ETH-Tight ..."
A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden
(Eindhoven University of Technology, Netherlands; Utrecht University, Netherlands; Hungarian Academy of Sciences, Hungary)
@InProceedings{STOC18p675,
author = {Mark de Berg and Hans L. Bodlaender and Sándor Kisfaludi-Bak and Dániel Marx and Tom C. van der Zanden},
title = {A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {675-674},
doi = {10.1145/3188745.3188854},
year = {2018},
}
Publisher's Version
Article: stoc18main-p204-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188854
|
| |
Bonacina, Ilario |
STOC '18: "Clique Is Hard on Average ..."
Clique Is Hard on Average for Regular Resolution
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, and Alexander Razborov
(Universitat Politècnica de Catalunya, Spain; KTH, Sweden; Sapienza University of Rome, Italy; University of Chicago, USA; Russian Academy of Sciences, Russia)
@InProceedings{STOC18p997,
author = {Albert Atserias and Ilario Bonacina and Susanna F. de Rezende and Massimo Lauria and Jakob Nordström and Alexander Razborov},
title = {Clique Is Hard on Average for Regular Resolution},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {997-996},
doi = {10.1145/3188745.3188856},
year = {2018},
}
Publisher's Version
Article: stoc18main-p211-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188856
|
| |
Brand, Cornelius |
STOC '18: "Extensor-Coding ..."
Extensor-Coding
Cornelius Brand, Holger Dell, and Thore Husfeldt
(Saarland University, Germany; M2CI, Germany; Lund University, Sweden; IT University of Copenhagen, Denmark)
@InProceedings{STOC18p185,
author = {Cornelius Brand and Holger Dell and Thore Husfeldt},
title = {Extensor-Coding},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {185-184},
doi = {10.1145/3188745.3188902},
year = {2018},
}
Publisher's Version
Article: stoc18main-p288-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188902
|
| |
Braverman, Mark |
STOC '18: "Interactive Compression to ..."
Interactive Compression to External Information
Mark Braverman and Gillat Kol
(Princeton University, USA)
@InProceedings{STOC18p1123,
author = {Mark Braverman and Gillat Kol},
title = {Interactive Compression to External Information},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1123-1122},
doi = {10.1145/3188745.3188956},
year = {2018},
}
Publisher's Version
Article: stoc18main-p413-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188956
STOC '18: "Hitting Sets with Near-Optimal ..."
Hitting Sets with Near-Optimal Error for Read-Once Branching Programs
Mark Braverman, Gil Cohen, and Sumegha Garg
(Princeton University, USA)
@InProceedings{STOC18p423,
author = {Mark Braverman and Gil Cohen and Sumegha Garg},
title = {Hitting Sets with Near-Optimal Error for Read-Once Branching Programs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {423-422},
doi = {10.1145/3188745.3188780},
year = {2018},
}
Publisher's Version
Article: stoc18main-p68-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188780
|
| |
Bringmann, Karl |
STOC '18: "More Consequences of Falsifying ..."
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof
(IBM Research, USA; Max Planck Institute for Informatics, Germany; Saarland University, Germany; M2CI, Germany; Eindhoven University of Technology, Netherlands)
@InProceedings{STOC18p311,
author = {Amir Abboud and Karl Bringmann and Holger Dell and Jesper Nederlof},
title = {More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {311-310},
doi = {10.1145/3188745.3188938},
year = {2018},
}
Publisher's Version
Article: stoc18main-p376-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188938
STOC '18: "Fast Fencing ..."
Fast Fencing
Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, and Mikkel Thorup
(University of Copenhagen, Denmark; Max Planck Institute for Informatics, Germany; Sorbonne University, France; UPMC, France; CNRS, France; LIP6, France; Eindhoven University of Technology, Netherlands; DTU, Denmark)
@InProceedings{STOC18p661,
author = {Mikkel Abrahamsen and Anna Adamaszek and Karl Bringmann and Vincent Cohen-Addad and Mehran Mehr and Eva Rotenberg and Alan Roytman and Mikkel Thorup},
title = {Fast Fencing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {661-660},
doi = {10.1145/3188745.3188878},
year = {2018},
}
Publisher's Version
Article: stoc18main-p248-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188878
|
| |
Bubeck, Sébastien |
STOC '18: "An Homotopy Method for lp ..."
An Homotopy Method for lp Regression Provably beyond Self-Concordance and in Input-Sparsity Time
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, and Yuanzhi Li
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; University of Washington, USA; Princeton University, USA)
@InProceedings{STOC18p1319,
author = {Sébastien Bubeck and Michael B. Cohen and Yin Tat Lee and Yuanzhi Li},
title = {An Homotopy Method for l<sub>p</sub> Regression Provably beyond Self-Concordance and in Input-Sparsity Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1319-1318},
doi = {10.1145/3188745.3188776},
year = {2018},
}
Publisher's Version
Article: stoc18main-p62-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188776
STOC '18: "k-Server via Multiscale Entropic ..."
k-Server via Multiscale Entropic Regularization
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Mądry
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; University of Washington, USA)
@InProceedings{STOC18p3,
author = {Sébastien Bubeck and Michael B. Cohen and Yin Tat Lee and James R. Lee and Aleksander Mądry},
title = {k-Server via Multiscale Entropic Regularization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {3-2},
doi = {},
year = {2018},
}
Article: stoc18main-p111-p (type: Full Paper (14 pages)) doi:
|
| |
Bun, Mark |
STOC '18: "The Polynomial Method Strikes ..."
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
Mark Bun, Robin Kothari, and Justin Thaler
(Princeton University, USA; Microsoft Research, USA; Georgetown University, USA)
@InProceedings{STOC18p367,
author = {Mark Bun and Robin Kothari and Justin Thaler},
title = {The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {367-366},
doi = {10.1145/3188745.3188784},
year = {2018},
}
Publisher's Version
Article: stoc18main-p75-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188784
STOC '18: "Composable and Versatile Privacy ..."
Composable and Versatile Privacy via Truncated CDP
Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke
(Princeton University, USA; Harvard University, USA; Weizmann Institute of Science, Israel; IBM Research, USA)
@InProceedings{STOC18p87,
author = {Mark Bun and Cynthia Dwork and Guy N. Rothblum and Thomas Steinke},
title = {Composable and Versatile Privacy via Truncated CDP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {87-86},
doi = {10.1145/3188745.3188946},
year = {2018},
}
Publisher's Version
Article: stoc18main-p384-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188946
|
| |
Byrka, Jarosław |
STOC '18: "Constant-Factor Approximation ..."
Constant-Factor Approximation for Ordered k-Median
Jarosław Byrka, Krzysztof Sornat, and Joachim Spoerhase
(University of Wrocław, Poland)
@InProceedings{STOC18p731,
author = {Jarosław Byrka and Krzysztof Sornat and Joachim Spoerhase},
title = {Constant-Factor Approximation for Ordered k-Median},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {731-730},
doi = {10.1145/3188745.3188930},
year = {2018},
}
Publisher's Version
Article: stoc18main-p338-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188930
|
| |
Canonne, Clément L.
|
STOC '18: "Testing Conditional Independence ..."
Testing Conditional Independence of Discrete Distributions
Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart
(Stanford University, USA; University of Southern California, USA; University of California at San Diego, USA)
@InProceedings{STOC18p857,
author = {Clément L. Canonne and Ilias Diakonikolas and Daniel M. Kane and Alistair Stewart},
title = {Testing Conditional Independence of Discrete Distributions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {857-856},
doi = {10.1145/3188745.3188756},
year = {2018},
}
Publisher's Version
Article: stoc18main-p11-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188756
|
| |
Chakraborty, Diptarka |
STOC '18: "Tight Cell Probe Bounds for ..."
Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
Diptarka Chakraborty, Lior Kamma, and Kasper Green Larsen
(Charles University in Prague, Czechia; Aarhus University, Denmark)
@InProceedings{STOC18p1515,
author = {Diptarka Chakraborty and Lior Kamma and Kasper Green Larsen},
title = {Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1515-1514},
doi = {10.1145/3188745.3188830},
year = {2018},
}
Publisher's Version
Article: stoc18main-p160-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188830
|
| |
Chang, Yi-Jun |
STOC '18: "An Optimal Distributed (Δ+1)-Coloring ..."
An Optimal Distributed (Δ+1)-Coloring Algorithm?
Yi-Jun Chang, Wenzheng Li, and Seth Pettie
(University of Michigan, USA; Tsinghua University, China)
@InProceedings{STOC18p521,
author = {Yi-Jun Chang and Wenzheng Li and Seth Pettie},
title = {An Optimal Distributed (Δ+1)-Coloring Algorithm?},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {521-520},
doi = {10.1145/3188745.3188964},
year = {2018},
}
Publisher's Version
Article: stoc18main-p436-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188964
|
| |
Chattopadhyay, Arkadev |
STOC '18: "Simulation Beats Richness: ..."
Simulation Beats Richness: New Data-Structure Lower Bounds
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay
(TIFR, India; Charles University in Prague, Czechia; INESC TEC, Portugal; University of Porto, Portugal; KTH, Sweden)
@InProceedings{STOC18p1179,
author = {Arkadev Chattopadhyay and Michal Koucký and Bruno Loff and Sagnik Mukhopadhyay},
title = {Simulation Beats Richness: New Data-Structure Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1179-1178},
doi = {10.1145/3188745.3188874},
year = {2018},
}
Publisher's Version
Article: stoc18main-p242-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188874
|
| |
Chattopadhyay, Eshan |
STOC '18: "Improved Pseudorandomness ..."
Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, and Avishay Tal
(Cornell University, USA; Institute for Advanced Study at Princeton, USA; University of Texas at Austin, USA; Stanford University, USA)
@InProceedings{STOC18p437,
author = {Eshan Chattopadhyay and Pooya Hatami and Omer Reingold and Avishay Tal},
title = {Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {437-436},
doi = {10.1145/3188745.3188800},
year = {2018},
}
Publisher's Version
Article: stoc18main-p112-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188800
|
| |
Chen, Xi |
STOC '18: "Distribution-Free Junta Testing ..."
Distribution-Free Junta Testing
Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, and Jinyu Xie
(Shanghai Jiao Tong University, China; Columbia University, USA)
@InProceedings{STOC18p871,
author = {Zhengyang Liu and Xi Chen and Rocco A. Servedio and Ying Sheng and Jinyu Xie},
title = {Distribution-Free Junta Testing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {871-870},
doi = {10.1145/3188745.3188842},
year = {2018},
}
Publisher's Version
Article: stoc18main-p186-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188842
|
| |
Cheraghchi, Mahdi |
STOC '18: "Capacity Upper Bounds for ..."
Capacity Upper Bounds for Deletion-Type Channels
Mahdi Cheraghchi
(Imperial College London, UK)
@InProceedings{STOC18p577,
author = {Mahdi Cheraghchi},
title = {Capacity Upper Bounds for Deletion-Type Channels},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {577-576},
doi = {10.1145/3188745.3188768},
year = {2018},
}
Publisher's Version
Article: stoc18main-p42-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188768
|
| |
Christandl, Matthias |
STOC '18: "Universal Points in the Asymptotic ..."
Universal Points in the Asymptotic Spectrum of Tensors
Matthias Christandl, Péter Vrana, and Jeroen Zuiddam
(University of Copenhagen, Denmark; Budapest University of Technology and Economics, Hungary; CWI, Netherlands)
@InProceedings{STOC18p353,
author = {Matthias Christandl and Péter Vrana and Jeroen Zuiddam},
title = {Universal Points in the Asymptotic Spectrum of Tensors},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {353-352},
doi = {10.1145/3188745.3188766},
year = {2018},
}
Publisher's Version
Article: stoc18main-p32-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188766
|
| |
Chuzhoy, Julia |
STOC '18: "Almost Polynomial Hardness ..."
Almost Polynomial Hardness of Node-Disjoint Paths in Grids
Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat
(Toyota Technological Institute at Chicago, USA; University of Chicago, USA)
@InProceedings{STOC18p1417,
author = {Julia Chuzhoy and David H. K. Kim and Rachit Nimavat},
title = {Almost Polynomial Hardness of Node-Disjoint Paths in Grids},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1417-1416},
doi = {10.1145/3188745.3188772},
year = {2018},
}
Publisher's Version
Article: stoc18main-p53-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188772
|
| |
Cohen, Gil |
STOC '18: "Hitting Sets with Near-Optimal ..."
Hitting Sets with Near-Optimal Error for Read-Once Branching Programs
Mark Braverman, Gil Cohen, and Sumegha Garg
(Princeton University, USA)
@InProceedings{STOC18p423,
author = {Mark Braverman and Gil Cohen and Sumegha Garg},
title = {Hitting Sets with Near-Optimal Error for Read-Once Branching Programs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {423-422},
doi = {10.1145/3188745.3188780},
year = {2018},
}
Publisher's Version
Article: stoc18main-p68-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188780
STOC '18: "Explicit Binary Tree Codes ..."
Explicit Binary Tree Codes with Polylogarithmic Size Alphabet
Gil Cohen, Bernhard Haeupler, and Leonard J. Schulman
(Princeton University, USA; Carnegie Mellon University, USA; California Institute of Technology, USA)
@InProceedings{STOC18p619,
author = {Gil Cohen and Bernhard Haeupler and Leonard J. Schulman},
title = {Explicit Binary Tree Codes with Polylogarithmic Size Alphabet},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {619-618},
doi = {10.1145/3188745.3188928},
year = {2018},
}
Publisher's Version
Article: stoc18main-p326-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188928
|
| |
Cohen, Michael B. |
STOC '18: "An Homotopy Method for lp ..."
An Homotopy Method for lp Regression Provably beyond Self-Concordance and in Input-Sparsity Time
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, and Yuanzhi Li
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; University of Washington, USA; Princeton University, USA)
@InProceedings{STOC18p1319,
author = {Sébastien Bubeck and Michael B. Cohen and Yin Tat Lee and Yuanzhi Li},
title = {An Homotopy Method for l<sub>p</sub> Regression Provably beyond Self-Concordance and in Input-Sparsity Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1319-1318},
doi = {10.1145/3188745.3188776},
year = {2018},
}
Publisher's Version
Article: stoc18main-p62-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188776
STOC '18: "k-Server via Multiscale Entropic ..."
k-Server via Multiscale Entropic Regularization
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Mądry
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; University of Washington, USA)
@InProceedings{STOC18p3,
author = {Sébastien Bubeck and Michael B. Cohen and Yin Tat Lee and James R. Lee and Aleksander Mądry},
title = {k-Server via Multiscale Entropic Regularization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {3-2},
doi = {},
year = {2018},
}
Article: stoc18main-p111-p (type: Full Paper (14 pages)) doi:
|
| |
Cohen-Addad, Vincent |
STOC '18: "Fast Fencing ..."
Fast Fencing
Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, and Mikkel Thorup
(University of Copenhagen, Denmark; Max Planck Institute for Informatics, Germany; Sorbonne University, France; UPMC, France; CNRS, France; LIP6, France; Eindhoven University of Technology, Netherlands; DTU, Denmark)
@InProceedings{STOC18p661,
author = {Mikkel Abrahamsen and Anna Adamaszek and Karl Bringmann and Vincent Cohen-Addad and Mehran Mehr and Eva Rotenberg and Alan Roytman and Mikkel Thorup},
title = {Fast Fencing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {661-660},
doi = {10.1145/3188745.3188878},
year = {2018},
}
Publisher's Version
Article: stoc18main-p248-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188878
|
| |
Czumaj, Artur |
STOC '18: "Round Compression for Parallel ..."
Round Compression for Parallel Matching Algorithms
Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski
(University of Warwick, UK; Google Research, USA; Massachusetts Institute of Technology, USA; EPFL, Switzerland; IBM Research, USA; University of Warsaw, Poland)
@InProceedings{STOC18p549,
author = {Artur Czumaj and Jakub Łącki and Aleksander Mądry and Slobodan Mitrović and Krzysztof Onak and Piotr Sankowski},
title = {Round Compression for Parallel Matching Algorithms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {549-548},
doi = {},
year = {2018},
}
Article: stoc18main-p15-p (type: Full Paper (14 pages)) doi:
|
| |
Dadush, Daniel
|
STOC '18: "A Friendly Smoothed Analysis ..."
A Friendly Smoothed Analysis of the Simplex Method
Daniel Dadush and Sophie Huiberts
(CWI, Netherlands)
@InProceedings{STOC18p465,
author = {Daniel Dadush and Sophie Huiberts},
title = {A Friendly Smoothed Analysis of the Simplex Method},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {465-464},
doi = {10.1145/3188745.3188826},
year = {2018},
}
Publisher's Version
Article: stoc18main-p151-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188826
STOC '18: "The Gram-Schmidt Walk: A Cure ..."
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett
(Eindhoven University of Technology, Netherlands; CWI, Netherlands; University of California at San Diego, USA)
@InProceedings{STOC18p689,
author = {Nikhil Bansal and Daniel Dadush and Shashwat Garg and Shachar Lovett},
title = {The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {689-688},
doi = {10.1145/3188745.3188850},
year = {2018},
}
Publisher's Version
Article: stoc18main-p195-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188850
|
| |
Daskalakis, Constantinos |
STOC '18: "A Converse to Banach's ..."
A Converse to Banach's Fixed Point Theorem and Its CLS-Completeness
Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis
(Massachusetts Institute of Technology, USA; Microsoft Research, USA)
@InProceedings{STOC18p45,
author = {Constantinos Daskalakis and Christos Tzamos and Manolis Zampetakis},
title = {A Converse to Banach's Fixed Point Theorem and Its CLS-Completeness},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {45-44},
doi = {10.1145/3188745.3188968},
year = {2018},
}
Publisher's Version
Article: stoc18main-p443-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188968
|
| |
De Berg, Mark |
STOC '18: "A Framework for ETH-Tight ..."
A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden
(Eindhoven University of Technology, Netherlands; Utrecht University, Netherlands; Hungarian Academy of Sciences, Hungary)
@InProceedings{STOC18p675,
author = {Mark de Berg and Hans L. Bodlaender and Sándor Kisfaludi-Bak and Dániel Marx and Tom C. van der Zanden},
title = {A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {675-674},
doi = {10.1145/3188745.3188854},
year = {2018},
}
Publisher's Version
Article: stoc18main-p204-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188854
|
| |
Dell, Holger |
STOC '18: "Extensor-Coding ..."
Extensor-Coding
Cornelius Brand, Holger Dell, and Thore Husfeldt
(Saarland University, Germany; M2CI, Germany; Lund University, Sweden; IT University of Copenhagen, Denmark)
@InProceedings{STOC18p185,
author = {Cornelius Brand and Holger Dell and Thore Husfeldt},
title = {Extensor-Coding},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {185-184},
doi = {10.1145/3188745.3188902},
year = {2018},
}
Publisher's Version
Article: stoc18main-p288-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188902
STOC '18: "More Consequences of Falsifying ..."
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof
(IBM Research, USA; Max Planck Institute for Informatics, Germany; Saarland University, Germany; M2CI, Germany; Eindhoven University of Technology, Netherlands)
@InProceedings{STOC18p311,
author = {Amir Abboud and Karl Bringmann and Holger Dell and Jesper Nederlof},
title = {More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {311-310},
doi = {10.1145/3188745.3188938},
year = {2018},
}
Publisher's Version
Article: stoc18main-p376-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188938
STOC '18: "Fine-Grained Reductions from ..."
Fine-Grained Reductions from Approximate Counting to Decision
Holger Dell and John Lapinskas
(Saarland University, Germany; M2CI, Germany; University of Oxford, UK)
@InProceedings{STOC18p339,
author = {Holger Dell and John Lapinskas},
title = {Fine-Grained Reductions from Approximate Counting to Decision},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {339-338},
doi = {10.1145/3188745.3188920},
year = {2018},
}
Publisher's Version
Article: stoc18main-p307-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188920
|
| |
De Loera, Jesús A. |
STOC '18: "The Minimum Euclidean-Norm ..."
The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm Is Exponential
Jesús A. De Loera, Jamie Haddock, and Luis Rademacher
(University of California at Davis, USA)
@InProceedings{STOC18p633,
author = {Jesús A. De Loera and Jamie Haddock and Luis Rademacher},
title = {The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm Is Exponential},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {633-632},
doi = {},
year = {2018},
}
Article: stoc18main-p143-p (type: Full Paper (14 pages)) doi:
|
| |
De Rezende, Susanna F. |
STOC '18: "Clique Is Hard on Average ..."
Clique Is Hard on Average for Regular Resolution
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, and Alexander Razborov
(Universitat Politècnica de Catalunya, Spain; KTH, Sweden; Sapienza University of Rome, Italy; University of Chicago, USA; Russian Academy of Sciences, Russia)
@InProceedings{STOC18p997,
author = {Albert Atserias and Ilario Bonacina and Susanna F. de Rezende and Massimo Lauria and Jakob Nordström and Alexander Razborov},
title = {Clique Is Hard on Average for Regular Resolution},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {997-996},
doi = {10.1145/3188745.3188856},
year = {2018},
}
Publisher's Version
Article: stoc18main-p211-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188856
|
| |
Diakonikolas, Ilias |
STOC '18: "List-Decodable Robust Mean ..."
List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart
(University of Southern California, USA; University of California at San Diego, USA)
@InProceedings{STOC18p1221,
author = {Ilias Diakonikolas and Daniel M. Kane and Alistair Stewart},
title = {List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1221-1220},
doi = {10.1145/3188745.3188758},
year = {2018},
}
Publisher's Version
Article: stoc18main-p12-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188758
STOC '18: "Learning Geometric Concepts ..."
Learning Geometric Concepts with Nasty Noise
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart
(University of Southern California, USA; University of California at San Diego, USA)
@InProceedings{STOC18p1235,
author = {Ilias Diakonikolas and Daniel M. Kane and Alistair Stewart},
title = {Learning Geometric Concepts with Nasty Noise},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1235-1234},
doi = {10.1145/3188745.3188754},
year = {2018},
}
Publisher's Version
Article: stoc18main-p10-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188754
STOC '18: "Testing Conditional Independence ..."
Testing Conditional Independence of Discrete Distributions
Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart
(Stanford University, USA; University of Southern California, USA; University of California at San Diego, USA)
@InProceedings{STOC18p857,
author = {Clément L. Canonne and Ilias Diakonikolas and Daniel M. Kane and Alistair Stewart},
title = {Testing Conditional Independence of Discrete Distributions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {857-856},
doi = {10.1145/3188745.3188756},
year = {2018},
}
Publisher's Version
Article: stoc18main-p11-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188756
|
| |
Dinur, Irit |
STOC '18: "On Non-optimally Expanding ..."
On Non-optimally Expanding Sets in Grassmann Graphs
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra
(Weizmann Institute of Science, Israel; New York University, USA; Hebrew University of Jerusalem, Israel; Tel Aviv University, Israel)
@InProceedings{STOC18p1095,
author = {Irit Dinur and Subhash Khot and Guy Kindler and Dor Minzer and Muli Safra},
title = {On Non-optimally Expanding Sets in Grassmann Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1095-1094},
doi = {10.1145/3188745.3188806},
year = {2018},
}
Publisher's Version
Article: stoc18main-p115-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188806
STOC '18: "Towards a Proof of the 2-to-1 ..."
Towards a Proof of the 2-to-1 Games Conjecture?
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra
(Weizmann Institute of Science, Israel; New York University, USA; Hebrew University of Jerusalem, Israel; Tel Aviv University, Israel)
@InProceedings{STOC18p451,
author = {Irit Dinur and Subhash Khot and Guy Kindler and Dor Minzer and Muli Safra},
title = {Towards a Proof of the 2-to-1 Games Conjecture?},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {451-450},
doi = {10.1145/3188745.3188804},
year = {2018},
}
Publisher's Version
Article: stoc18main-p114-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188804
|
| |
Dudek, Bartłomiej |
STOC '18: "Universal Protocols for Information ..."
Universal Protocols for Information Dissemination using Emergent Signals
Bartłomiej Dudek and Adrian Kosowski
(University of Wrocław, Poland; Inria, France)
@InProceedings{STOC18p101,
author = {Bartłomiej Dudek and Adrian Kosowski},
title = {Universal Protocols for Information Dissemination using Emergent Signals},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {101-100},
doi = {10.1145/3188745.3188818},
year = {2018},
}
Publisher's Version
Article: stoc18main-p142-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188818
|
| |
Dutta, Pranjal |
STOC '18: "Discovering the Roots: Uniform ..."
Discovering the Roots: Uniform Closure Results for Algebraic Classes under Factoring
Pranjal Dutta, Nitin Saxena, and Amit Sinhababu
(Chennai Mathematical Institute, India; IIT Kanpur, India)
@InProceedings{STOC18p1347,
author = {Pranjal Dutta and Nitin Saxena and Amit Sinhababu},
title = {Discovering the Roots: Uniform Closure Results for Algebraic Classes under Factoring},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1347-1346},
doi = {10.1145/3188745.3188760},
year = {2018},
}
Publisher's Version
Article: stoc18main-p13-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188760
|
| |
Dwork, Cynthia |
STOC '18: "Composable and Versatile Privacy ..."
Composable and Versatile Privacy via Truncated CDP
Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke
(Princeton University, USA; Harvard University, USA; Weizmann Institute of Science, Israel; IBM Research, USA)
@InProceedings{STOC18p87,
author = {Mark Bun and Cynthia Dwork and Guy N. Rothblum and Thomas Steinke},
title = {Composable and Versatile Privacy via Truncated CDP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {87-86},
doi = {10.1145/3188745.3188946},
year = {2018},
}
Publisher's Version
Article: stoc18main-p384-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188946
|
| |
Eden, Talya
|
STOC '18: "On Approximating the Number ..."
On Approximating the Number of k-Cliques in Sublinear Time
Talya Eden, Dana Ron, and C. Seshadhri
(Tel Aviv University, Israel; University of California at Santa Cruz, USA)
@InProceedings{STOC18p843,
author = {Talya Eden and Dana Ron and C. Seshadhri},
title = {On Approximating the Number of k-Cliques in Sublinear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {843-842},
doi = {10.1145/3188745.3188810},
year = {2018},
}
Publisher's Version
Article: stoc18main-p120-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188810
|
| |
Efremenko, Klim |
STOC '18: "Interactive Coding over the ..."
Interactive Coding over the Noisy Broadcast Channel
Klim Efremenko, Gillat Kol, and Raghuvansh Saxena
(Ben-Gurion University of the Negev, Israel; Princeton University, USA)
@InProceedings{STOC18p591,
author = {Klim Efremenko and Gillat Kol and Raghuvansh Saxena},
title = {Interactive Coding over the Noisy Broadcast Channel},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {591-590},
doi = {10.1145/3188745.3188884},
year = {2018},
}
Publisher's Version
Article: stoc18main-p262-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188884
|
| |
El Alaoui, Ahmed |
STOC '18: "Tight Query Complexity Lower ..."
Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law
Max Simchowitz, Ahmed El Alaoui, and Benjamin Recht
(University of California at Berkeley, USA)
@InProceedings{STOC18p1459,
author = {Max Simchowitz and Ahmed El Alaoui and Benjamin Recht},
title = {Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1459-1458},
doi = {10.1145/3188745.3188796},
year = {2018},
}
Publisher's Version
Article: stoc18main-p106-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188796
|
| |
Emek, Yuval |
STOC '18: "Approximating Generalized ..."
Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency
Yuval Emek, Shay Kutten, Ron Lavi, and Yangguang Shi
(Technion, Israel)
@InProceedings{STOC18p703,
author = {Yuval Emek and Shay Kutten and Ron Lavi and Yangguang Shi},
title = {Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {703-702},
doi = {10.1145/3188745.3188812},
year = {2018},
}
Publisher's Version
Article: stoc18main-p121-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188812
|
| |
Erickson, Jeff |
STOC '18: "Holiest Minimum-Cost Paths ..."
Holiest Minimum-Cost Paths and Flows in Surface Graphs
Jeff Erickson, Kyle Fox, and Luvsandondov Lkhamsuren
(University of Illinois at Urbana-Champaign, USA; University of Texas at Dallas, USA; Airbnb, USA)
@InProceedings{STOC18p1543,
author = {Jeff Erickson and Kyle Fox and Luvsandondov Lkhamsuren},
title = {Holiest Minimum-Cost Paths and Flows in Surface Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1543-1542},
doi = {10.1145/3188745.3188904},
year = {2018},
}
Publisher's Version
Article: stoc18main-p289-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188904
|
| |
Fawzi, Omar
|
STOC '18: "Efficient Decoding of Random ..."
Efficient Decoding of Random Errors for Quantum Expander Codes
Omar Fawzi, Antoine Grospellier, and Anthony Leverrier
(ENS Lyon, France; Inria, France)
@InProceedings{STOC18p605,
author = {Omar Fawzi and Antoine Grospellier and Anthony Leverrier},
title = {Efficient Decoding of Random Errors for Quantum Expander Codes},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {605-604},
doi = {10.1145/3188745.3188886},
year = {2018},
}
Publisher's Version
Article: stoc18main-p263-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188886
|
| |
Filos-Ratsikas, Aris |
STOC '18: "Consensus Halving Is PPA-Complete ..."
Consensus Halving Is PPA-Complete
Aris Filos-Ratsikas and Paul W. Goldberg
(University of Oxford, UK)
@InProceedings{STOC18p59,
author = {Aris Filos-Ratsikas and Paul W. Goldberg},
title = {Consensus Halving Is PPA-Complete},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {59-58},
doi = {10.1145/3188745.3188880},
year = {2018},
}
Publisher's Version
Article: stoc18main-p257-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188880
|
| |
Filtser, Arnold |
STOC '18: "Metric Embedding via Shortest ..."
Metric Embedding via Shortest Path Decompositions
Ittai Abraham, Arnold Filtser, Anupam Gupta, and Ofer Neiman
(VMware, USA; Ben-Gurion University of the Negev, Israel; Carnegie Mellon University, USA)
@InProceedings{STOC18p1109,
author = {Ittai Abraham and Arnold Filtser and Anupam Gupta and Ofer Neiman},
title = {Metric Embedding via Shortest Path Decompositions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1109-1108},
doi = {10.1145/3188745.3188808},
year = {2018},
}
Publisher's Version
Article: stoc18main-p116-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188808
|
| |
Fineman, Jeremy T. |
STOC '18: "Nearly Work-Efficient Parallel ..."
Nearly Work-Efficient Parallel Algorithm for Digraph Reachability
Jeremy T. Fineman
(Georgetown University, USA)
@InProceedings{STOC18p535,
author = {Jeremy T. Fineman},
title = {Nearly Work-Efficient Parallel Algorithm for Digraph Reachability},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {535-534},
doi = {10.1145/3188745.3188926},
year = {2018},
}
Publisher's Version
Article: stoc18main-p320-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188926
|
| |
Forbes, Michael A. |
STOC '18: "A PSPACE Construction of a ..."
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits
Michael A. Forbes and Amir Shpilka
(University of Illinois at Urbana-Champaign, USA; Tel Aviv University, Israel)
@InProceedings{STOC18p1375,
author = {Michael A. Forbes and Amir Shpilka},
title = {A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1375-1374},
doi = {10.1145/3188745.3188792},
year = {2018},
}
Publisher's Version
Article: stoc18main-p98-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188792
|
| |
Fox, Kyle |
STOC '18: "Holiest Minimum-Cost Paths ..."
Holiest Minimum-Cost Paths and Flows in Surface Graphs
Jeff Erickson, Kyle Fox, and Luvsandondov Lkhamsuren
(University of Illinois at Urbana-Champaign, USA; University of Texas at Dallas, USA; Airbnb, USA)
@InProceedings{STOC18p1543,
author = {Jeff Erickson and Kyle Fox and Luvsandondov Lkhamsuren},
title = {Holiest Minimum-Cost Paths and Flows in Surface Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1543-1542},
doi = {10.1145/3188745.3188904},
year = {2018},
}
Publisher's Version
Article: stoc18main-p289-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188904
|
| |
Franceschetti, Massimo |
STOC '18: "Shape of Diffusion and Size ..."
Shape of Diffusion and Size of Monochromatic Region of a Two-Dimensional Spin System
Hamed Omidvar and Massimo Franceschetti
(University of California at San Diego, USA)
@InProceedings{STOC18p115,
author = {Hamed Omidvar and Massimo Franceschetti},
title = {Shape of Diffusion and Size of Monochromatic Region of a Two-Dimensional Spin System},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {115-114},
doi = {10.1145/3188745.3188836},
year = {2018},
}
Publisher's Version
Article: stoc18main-p167-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188836
|
| |
Franks, Cole |
STOC '18: "Operator Scaling with Specified ..."
Operator Scaling with Specified Marginals
Cole Franks
(Rutgers University, USA)
@InProceedings{STOC18p241,
author = {Cole Franks},
title = {Operator Scaling with Specified Marginals},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {241-240},
doi = {10.1145/3188745.3188932},
year = {2018},
}
Publisher's Version
Article: stoc18main-p339-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188932
|
| |
Galanis, Andreas
|
STOC '18: "Inapproximability of the Independent ..."
Inapproximability of the Independent Set Polynomial in the Complex Plane
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič
(Rochester Institute of Technology, USA; University of Oxford, UK; University of Rochester, USA)
@InProceedings{STOC18p1431,
author = {Ivona Bezáková and Andreas Galanis and Leslie Ann Goldberg and Daniel Štefankovič},
title = {Inapproximability of the Independent Set Polynomial in the Complex Plane},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1431-1430},
doi = {10.1145/3188745.3188788},
year = {2018},
}
Publisher's Version
Article: stoc18main-p77-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188788
|
| |
Garg, Ankit |
STOC '18: "Monotone Circuit Lower Bounds ..."
Monotone Circuit Lower Bounds from Resolution
Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov
(Microsoft Research, USA; Harvard University, USA; Massachusetts Institute of Technology, USA; KTH, Sweden)
@InProceedings{STOC18p1039,
author = {Ankit Garg and Mika Göös and Pritish Kamath and Dmitry Sokolov},
title = {Monotone Circuit Lower Bounds from Resolution},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1039-1038},
doi = {10.1145/3188745.3188838},
year = {2018},
}
Publisher's Version
Article: stoc18main-p179-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188838
STOC '18: "A Matrix Expander Chernoff ..."
A Matrix Expander Chernoff Bound
Ankit Garg, Yin Tat Lee, Zhao Song, and Nikhil Srivastava
(Microsoft Research, USA; University of Washington, USA; Harvard University, USA; University of Texas at Austin, USA; University of California at Berkeley, USA)
@InProceedings{STOC18p1277,
author = {Ankit Garg and Yin Tat Lee and Zhao Song and Nikhil Srivastava},
title = {A Matrix Expander Chernoff Bound},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1277-1276},
doi = {10.1145/3188745.3188890},
year = {2018},
}
Publisher's Version
Article: stoc18main-p275-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188890
STOC '18: "Operator Scaling via Geodesically ..."
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson
(Microsoft Research, USA; Princeton University, USA; University of Toronto, Canada; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC18p213,
author = {Zeyuan Allen-Zhu and Ankit Garg and Yuanzhi Li and Rafael Oliveira and Avi Wigderson},
title = {Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {213-212},
doi = {10.1145/3188745.3188942},
year = {2018},
}
Publisher's Version
Article: stoc18main-p382-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188942
|
| |
Garg, Shashwat |
STOC '18: "The Gram-Schmidt Walk: A Cure ..."
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett
(Eindhoven University of Technology, Netherlands; CWI, Netherlands; University of California at San Diego, USA)
@InProceedings{STOC18p689,
author = {Nikhil Bansal and Daniel Dadush and Shashwat Garg and Shachar Lovett},
title = {The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {689-688},
doi = {10.1145/3188745.3188850},
year = {2018},
}
Publisher's Version
Article: stoc18main-p195-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188850
|
| |
Garg, Sumegha |
STOC '18: "Extractor-Based Time-Space ..."
Extractor-Based Time-Space Lower Bounds for Learning
Sumegha Garg, Ran Raz, and Avishay Tal
(Princeton University, USA; Stanford University, USA)
@InProceedings{STOC18p1151,
author = {Sumegha Garg and Ran Raz and Avishay Tal},
title = {Extractor-Based Time-Space Lower Bounds for Learning},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1151-1150},
doi = {10.1145/3188745.3188962},
year = {2018},
}
Publisher's Version
Article: stoc18main-p430-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188962
STOC '18: "Hitting Sets with Near-Optimal ..."
Hitting Sets with Near-Optimal Error for Read-Once Branching Programs
Mark Braverman, Gil Cohen, and Sumegha Garg
(Princeton University, USA)
@InProceedings{STOC18p423,
author = {Mark Braverman and Gil Cohen and Sumegha Garg},
title = {Hitting Sets with Near-Optimal Error for Read-Once Branching Programs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {423-422},
doi = {10.1145/3188745.3188780},
year = {2018},
}
Publisher's Version
Article: stoc18main-p68-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188780
|
| |
Ghaffari, Mohsen |
STOC '18: "Deterministic Distributed ..."
Deterministic Distributed Edge-Coloring with Fewer Colors
Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, and Jara Uitto
(ETH Zurich, Switzerland; University of Freiburg, Germany)
@InProceedings{STOC18p493,
author = {Mohsen Ghaffari and Fabian Kuhn and Yannic Maus and Jara Uitto},
title = {Deterministic Distributed Edge-Coloring with Fewer Colors},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {493-492},
doi = {10.1145/3188745.3188906},
year = {2018},
}
Publisher's Version
Article: stoc18main-p293-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188906
STOC '18: "Improved Distributed Algorithms ..."
Improved Distributed Algorithms for Exact Shortest Paths
Mohsen Ghaffari and Jason Li
(ETH Zurich, Switzerland; Carnegie Mellon University, USA)
@InProceedings{STOC18p507,
author = {Mohsen Ghaffari and Jason Li},
title = {Improved Distributed Algorithms for Exact Shortest Paths},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {507-506},
doi = {10.1145/3188745.3188948},
year = {2018},
}
Publisher's Version
Article: stoc18main-p394-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188948
|
| |
Gharan, Shayan Oveis |
STOC '18: "A Simply Exponential Upper ..."
A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings
Anna R. Karlin, Shayan Oveis Gharan, and Robbie Weber
(University of Washington, USA)
@InProceedings{STOC18p1067,
author = {Anna R. Karlin and Shayan Oveis Gharan and Robbie Weber},
title = {A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1067-1066},
doi = {10.1145/3188745.3188848},
year = {2018},
}
Publisher's Version
Article: stoc18main-p191-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188848
|
| |
Ghosh, Sumanta |
STOC '18: "Bootstrapping Variables in ..."
Bootstrapping Variables in Algebraic Circuits
Manindra Agrawal, Sumanta Ghosh, and Nitin Saxena
(IIT Kanpur, India)
@InProceedings{STOC18p1361,
author = {Manindra Agrawal and Sumanta Ghosh and Nitin Saxena},
title = {Bootstrapping Variables in Algebraic Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1361-1360},
doi = {10.1145/3188745.3188762},
year = {2018},
}
Publisher's Version
Article: stoc18main-p14-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188762
|
| |
Gishboliner, Lior |
STOC '18: "A Generalized Turán Problem ..."
A Generalized Turán Problem and Its Applications
Lior Gishboliner and Asaf Shapira
(Tel Aviv University, Israel)
@InProceedings{STOC18p885,
author = {Lior Gishboliner and Asaf Shapira},
title = {A Generalized Turán Problem and Its Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {885-884},
doi = {10.1145/3188745.3188778},
year = {2018},
}
Publisher's Version
Article: stoc18main-p63-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188778
|
| |
Goldberg, Leslie Ann |
STOC '18: "Inapproximability of the Independent ..."
Inapproximability of the Independent Set Polynomial in the Complex Plane
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič
(Rochester Institute of Technology, USA; University of Oxford, UK; University of Rochester, USA)
@InProceedings{STOC18p1431,
author = {Ivona Bezáková and Andreas Galanis and Leslie Ann Goldberg and Daniel Štefankovič},
title = {Inapproximability of the Independent Set Polynomial in the Complex Plane},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1431-1430},
doi = {10.1145/3188745.3188788},
year = {2018},
}
Publisher's Version
Article: stoc18main-p77-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188788
|
| |
Goldberg, Paul W. |
STOC '18: "Consensus Halving Is PPA-Complete ..."
Consensus Halving Is PPA-Complete
Aris Filos-Ratsikas and Paul W. Goldberg
(University of Oxford, UK)
@InProceedings{STOC18p59,
author = {Aris Filos-Ratsikas and Paul W. Goldberg},
title = {Consensus Halving Is PPA-Complete},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {59-58},
doi = {10.1145/3188745.3188880},
year = {2018},
}
Publisher's Version
Article: stoc18main-p257-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188880
|
| |
Gonczarowski, Yannai A. |
STOC '18: "Bounding the Menu-Size of ..."
Bounding the Menu-Size of Approximately Optimal Auctions via Optimal-Transport Duality
Yannai A. Gonczarowski
(Hebrew University of Jerusalem, Israel; Microsoft Research, Israel)
@InProceedings{STOC18p143,
author = {Yannai A. Gonczarowski},
title = {Bounding the Menu-Size of Approximately Optimal Auctions via Optimal-Transport Duality},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {143-142},
doi = {10.1145/3188745.3188786},
year = {2018},
}
Publisher's Version
Article: stoc18main-p76-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188786
|
| |
Göös, Mika |
STOC '18: "Monotone Circuit Lower Bounds ..."
Monotone Circuit Lower Bounds from Resolution
Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov
(Microsoft Research, USA; Harvard University, USA; Massachusetts Institute of Technology, USA; KTH, Sweden)
@InProceedings{STOC18p1039,
author = {Ankit Garg and Mika Göös and Pritish Kamath and Dmitry Sokolov},
title = {Monotone Circuit Lower Bounds from Resolution},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1039-1038},
doi = {10.1145/3188745.3188838},
year = {2018},
}
Publisher's Version
Article: stoc18main-p179-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188838
|
| |
Goyal, Rishab |
STOC '18: "Collusion Resistant Traitor ..."
Collusion Resistant Traitor Tracing from Learning with Errors
Rishab Goyal, Venkata Koppula, and Brent Waters
(University of Texas at Austin, USA)
@InProceedings{STOC18p773,
author = {Rishab Goyal and Venkata Koppula and Brent Waters},
title = {Collusion Resistant Traitor Tracing from Learning with Errors},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {773-772},
doi = {10.1145/3188745.3188844},
year = {2018},
}
Publisher's Version
Article: stoc18main-p187-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188844
|
| |
Goyal, Vipul |
STOC '18: "Non-malleable Secret Sharing ..."
Non-malleable Secret Sharing
Vipul Goyal and Ashutosh Kumar
(Carnegie Mellon University, USA; University of California at Los Angeles, USA)
@InProceedings{STOC18p801,
author = {Vipul Goyal and Ashutosh Kumar},
title = {Non-malleable Secret Sharing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {801-800},
doi = {10.1145/3188745.3188872},
year = {2018},
}
Publisher's Version
Article: stoc18main-p238-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188872
|
| |
Grandoni, Fabrizio |
STOC '18: "A (5/3 + ε)-Approximation ..."
A (5/3 + ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes
Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou
(University of Lugano, Switzerland; University of Bremen, Germany; Saarland University, Germany; University of Chile, Chile; École Polytechnique, France)
@InProceedings{STOC18p717,
author = {Fabrizio Grandoni and Tobias Mömke and Andreas Wiese and Hang Zhou},
title = {A (5/3 + ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {717-716},
doi = {10.1145/3188745.3188894},
year = {2018},
}
Publisher's Version
Article: stoc18main-p278-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188894
STOC '18: "Improved Approximation for ..."
Improved Approximation for Tree Augmentation: Saving by Rewiring
Fabrizio Grandoni, Christos Kalaitzis, and Rico Zenklusen
(University of Lugano, Switzerland; ETH Zurich, Switzerland)
@InProceedings{STOC18p745,
author = {Fabrizio Grandoni and Christos Kalaitzis and Rico Zenklusen},
title = {Improved Approximation for Tree Augmentation: Saving by Rewiring},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {745-744},
doi = {10.1145/3188745.3188898},
year = {2018},
}
Publisher's Version
Article: stoc18main-p284-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188898
|
| |
Grospellier, Antoine |
STOC '18: "Efficient Decoding of Random ..."
Efficient Decoding of Random Errors for Quantum Expander Codes
Omar Fawzi, Antoine Grospellier, and Anthony Leverrier
(ENS Lyon, France; Inria, France)
@InProceedings{STOC18p605,
author = {Omar Fawzi and Antoine Grospellier and Anthony Leverrier},
title = {Efficient Decoding of Random Errors for Quantum Expander Codes},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {605-604},
doi = {10.1145/3188745.3188886},
year = {2018},
}
Publisher's Version
Article: stoc18main-p263-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188886
|
| |
Guo, Heng |
STOC '18: "Counting Hypergraph Colourings ..."
Counting Hypergraph Colourings in the Local Lemma Regime
Heng Guo, Chao Liao, Pinyan Lu, and Chihao Zhang
(University of Edinburgh, UK; Shanghai Jiao Tong University, China; Shanghai University of Finance and Economics, China; Chinese University of Hong Kong, China)
@InProceedings{STOC18p1081,
author = {Heng Guo and Chao Liao and Pinyan Lu and Chihao Zhang},
title = {Counting Hypergraph Colourings in the Local Lemma Regime},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1081-1080},
doi = {10.1145/3188745.3188934},
year = {2018},
}
Publisher's Version
Article: stoc18main-p364-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188934
|
| |
Gupta, Anupam |
STOC '18: "Metric Embedding via Shortest ..."
Metric Embedding via Shortest Path Decompositions
Ittai Abraham, Arnold Filtser, Anupam Gupta, and Ofer Neiman
(VMware, USA; Ben-Gurion University of the Negev, Israel; Carnegie Mellon University, USA)
@InProceedings{STOC18p1109,
author = {Ittai Abraham and Arnold Filtser and Anupam Gupta and Ofer Neiman},
title = {Metric Embedding via Shortest Path Decompositions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1109-1108},
doi = {10.1145/3188745.3188808},
year = {2018},
}
Publisher's Version
Article: stoc18main-p116-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188808
|
| |
Guruswami, Venkatesan |
STOC '18: "General Strong Polarization ..."
General Strong Polarization
Jarosław Błasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, and Madhu Sudan
(Harvard University, USA; Carnegie Mellon University, USA; SUNY Buffalo, USA)
@InProceedings{STOC18p563,
author = {Jarosław Błasiok and Venkatesan Guruswami and Preetum Nakkiran and Atri Rudra and Madhu Sudan},
title = {General Strong Polarization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {563-562},
doi = {10.1145/3188745.3188816},
year = {2018},
}
Publisher's Version
Article: stoc18main-p140-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188816
|
| |
Haddock, Jamie
|
STOC '18: "The Minimum Euclidean-Norm ..."
The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm Is Exponential
Jesús A. De Loera, Jamie Haddock, and Luis Rademacher
(University of California at Davis, USA)
@InProceedings{STOC18p633,
author = {Jesús A. De Loera and Jamie Haddock and Luis Rademacher},
title = {The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm Is Exponential},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {633-632},
doi = {},
year = {2018},
}
Article: stoc18main-p143-p (type: Full Paper (14 pages)) doi:
|
| |
Haeupler, Bernhard |
STOC '18: "Explicit Binary Tree Codes ..."
Explicit Binary Tree Codes with Polylogarithmic Size Alphabet
Gil Cohen, Bernhard Haeupler, and Leonard J. Schulman
(Princeton University, USA; Carnegie Mellon University, USA; California Institute of Technology, USA)
@InProceedings{STOC18p619,
author = {Gil Cohen and Bernhard Haeupler and Leonard J. Schulman},
title = {Explicit Binary Tree Codes with Polylogarithmic Size Alphabet},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {619-618},
doi = {10.1145/3188745.3188928},
year = {2018},
}
Publisher's Version
Article: stoc18main-p326-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188928
STOC '18: "Synchronization Strings: Explicit ..."
Synchronization Strings: Explicit Constructions, Local Decoding, and Applications
Bernhard Haeupler and Amirbehshad Shahrasbi
(Carnegie Mellon University, USA)
@InProceedings{STOC18p969,
author = {Bernhard Haeupler and Amirbehshad Shahrasbi},
title = {Synchronization Strings: Explicit Constructions, Local Decoding, and Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {969-968},
doi = {10.1145/3188745.3188940},
year = {2018},
}
Publisher's Version
Article: stoc18main-p379-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188940
|
| |
Hajiaghayi, MohammadTaghi |
STOC '18: "Fast Algorithms for Knapsack ..."
Fast Algorithms for Knapsack via Convolution and Prediction
MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Saeed Seddighin, and Cliff Stein
(Google, USA; University of Maryland, USA; Columbia University, USA)
@InProceedings{STOC18p1487,
author = {MohammadHossein Bateni and MohammadTaghi Hajiaghayi and Saeed Seddighin and Cliff Stein},
title = {Fast Algorithms for Knapsack via Convolution and Prediction},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1487-1486},
doi = {10.1145/3188745.3188876},
year = {2018},
}
Publisher's Version
Article: stoc18main-p247-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188876
|
| |
Hatami, Pooya |
STOC '18: "Improved Pseudorandomness ..."
Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, and Avishay Tal
(Cornell University, USA; Institute for Advanced Study at Princeton, USA; University of Texas at Austin, USA; Stanford University, USA)
@InProceedings{STOC18p437,
author = {Eshan Chattopadhyay and Pooya Hatami and Omer Reingold and Avishay Tal},
title = {Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {437-436},
doi = {10.1145/3188745.3188800},
year = {2018},
}
Publisher's Version
Article: stoc18main-p112-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188800
|
| |
Hirvonen, Juho |
STOC '18: "New Classes of Distributed ..."
New Classes of Distributed Time Complexity
Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela
(Aalto University, Finland; University of Freiburg, Germany)
@InProceedings{STOC18p1529,
author = {Alkida Balliu and Juho Hirvonen and Janne H. Korhonen and Tuomo Lempiäinen and Dennis Olivetti and Jukka Suomela},
title = {New Classes of Distributed Time Complexity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1529-1528},
doi = {10.1145/3188745.3188860},
year = {2018},
}
Publisher's Version
Article: stoc18main-p220-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188860
|
| |
Hopkins, Samuel B. |
STOC '18: "Mixture Models, Robustness, ..."
Mixture Models, Robustness, and Sum of Squares Proofs
Samuel B. Hopkins and Jerry Li
(Cornell University, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC18p1193,
author = {Samuel B. Hopkins and Jerry Li},
title = {Mixture Models, Robustness, and Sum of Squares Proofs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1193-1192},
doi = {10.1145/3188745.3188748},
year = {2018},
}
Publisher's Version
Article: stoc18main-p3-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188748
|
| |
Hoy, Darrell |
STOC '18: "A Tighter Welfare Guarantee ..."
A Tighter Welfare Guarantee for First-Price Auctions
Darrell Hoy, Samuel Taggart, and Zihe Wang
(Tremor Technologies, USA; Oberlin College, USA; Shanghai University of Finance and Economics, China)
@InProceedings{STOC18p157,
author = {Darrell Hoy and Samuel Taggart and Zihe Wang},
title = {A Tighter Welfare Guarantee for First-Price Auctions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {157-156},
doi = {10.1145/3188745.3188944},
year = {2018},
}
Publisher's Version
Article: stoc18main-p383-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188944
|
| |
Huang, Zhiyi |
STOC '18: "How to Match When All Vertices ..."
How to Match When All Vertices Arrive Online
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu
(University of Hong Kong, China)
@InProceedings{STOC18p17,
author = {Zhiyi Huang and Ning Kang and Zhihao Gavin Tang and Xiaowei Wu and Yuhao Zhang and Xue Zhu},
title = {How to Match When All Vertices Arrive Online},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {17-16},
doi = {10.1145/3188745.3188858},
year = {2018},
}
Publisher's Version
Article: stoc18main-p214-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188858
|
| |
Huiberts, Sophie |
STOC '18: "A Friendly Smoothed Analysis ..."
A Friendly Smoothed Analysis of the Simplex Method
Daniel Dadush and Sophie Huiberts
(CWI, Netherlands)
@InProceedings{STOC18p465,
author = {Daniel Dadush and Sophie Huiberts},
title = {A Friendly Smoothed Analysis of the Simplex Method},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {465-464},
doi = {10.1145/3188745.3188826},
year = {2018},
}
Publisher's Version
Article: stoc18main-p151-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188826
|
| |
Husfeldt, Thore |
STOC '18: "Extensor-Coding ..."
Extensor-Coding
Cornelius Brand, Holger Dell, and Thore Husfeldt
(Saarland University, Germany; M2CI, Germany; Lund University, Sweden; IT University of Copenhagen, Denmark)
@InProceedings{STOC18p185,
author = {Cornelius Brand and Holger Dell and Thore Husfeldt},
title = {Extensor-Coding},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {185-184},
doi = {10.1145/3188745.3188902},
year = {2018},
}
Publisher's Version
Article: stoc18main-p288-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188902
|
| |
Ikenmeyer, Christian
|
STOC '18: "On the Complexity of Hazard-Free ..."
On the Complexity of Hazard-Free Circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, and Karteek Sreenivasaiah
(Max Planck Institute for Informatics, Germany; Saarland University, Germany; M2CI, Germany; Newcastle University, UK; IIT Hyderabad, India)
@InProceedings{STOC18p1011,
author = {Christian Ikenmeyer and Balagopal Komarath and Christoph Lenzen and Vladimir Lysikov and Andrey Mokhov and Karteek Sreenivasaiah},
title = {On the Complexity of Hazard-Free Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1011-1010},
doi = {10.1145/3188745.3188912},
year = {2018},
}
Publisher's Version
Article: stoc18main-p297-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188912
STOC '18: "Generalized Matrix Completion ..."
Generalized Matrix Completion and Algebraic Natural Proofs
Markus Bläser, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov
(Saarland University, Germany; Max Planck Institute for Informatics, Germany)
@InProceedings{STOC18p1389,
author = {Markus Bläser and Christian Ikenmeyer and Gorav Jindal and Vladimir Lysikov},
title = {Generalized Matrix Completion and Algebraic Natural Proofs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1389-1388},
doi = {10.1145/3188745.3188832},
year = {2018},
}
Publisher's Version
Article: stoc18main-p165-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188832
|
| |
Im, Sungjin |
STOC '18: "Online Load Balancing on Related ..."
Online Load Balancing on Related Machines
Sungjin Im, Nathaniel Kell, Debmalya Panigrahi, and Maryam Shadloo
(University of California at Merced, USA; Duke University, USA)
@InProceedings{STOC18p31,
author = {Sungjin Im and Nathaniel Kell and Debmalya Panigrahi and Maryam Shadloo},
title = {Online Load Balancing on Related Machines},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {31-30},
doi = {10.1145/3188745.3188966},
year = {2018},
}
Publisher's Version
Article: stoc18main-p439-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188966
|
| |
Jindal, Gorav
|
STOC '18: "Generalized Matrix Completion ..."
Generalized Matrix Completion and Algebraic Natural Proofs
Markus Bläser, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov
(Saarland University, Germany; Max Planck Institute for Informatics, Germany)
@InProceedings{STOC18p1389,
author = {Markus Bläser and Christian Ikenmeyer and Gorav Jindal and Vladimir Lysikov},
title = {Generalized Matrix Completion and Algebraic Natural Proofs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1389-1388},
doi = {10.1145/3188745.3188832},
year = {2018},
}
Publisher's Version
Article: stoc18main-p165-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188832
|
| |
Kakade, Sham
|
STOC '18: "Prediction with a Short Memory ..."
Prediction with a Short Memory
Vatsal Sharan, Sham Kakade, Percy Liang, and Gregory Valiant
(Stanford University, USA; University of Washington, USA)
@InProceedings{STOC18p1249,
author = {Vatsal Sharan and Sham Kakade and Percy Liang and Gregory Valiant},
title = {Prediction with a Short Memory},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1249-1248},
doi = {10.1145/3188745.3188954},
year = {2018},
}
Publisher's Version
Article: stoc18main-p410-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188954
|
| |
Kalai, Yael Tauman |
STOC '18: "Multi-collision Resistance: ..."
Multi-collision Resistance: A Paradigm for Keyless Hash Functions
Nir Bitansky, Yael Tauman Kalai, and Omer Paneth
(Tel Aviv University, Israel; Microsoft, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC18p787,
author = {Nir Bitansky and Yael Tauman Kalai and Omer Paneth},
title = {Multi-collision Resistance: A Paradigm for Keyless Hash Functions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {787-786},
doi = {10.1145/3188745.3188870},
year = {2018},
}
Publisher's Version
Article: stoc18main-p236-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188870
STOC '18: "Succinct Delegation for Low-Space ..."
Succinct Delegation for Low-Space Non-deterministic Computation
Saikrishna Badrinarayanan, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai, and Daniel Wichs
(University of California at Los Angeles, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA; Northeastern University, USA)
@InProceedings{STOC18p829,
author = {Saikrishna Badrinarayanan and Yael Tauman Kalai and Dakshita Khurana and Amit Sahai and Daniel Wichs},
title = {Succinct Delegation for Low-Space Non-deterministic Computation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {829-828},
doi = {10.1145/3188745.3188924},
year = {2018},
}
Publisher's Version
Article: stoc18main-p312-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188924
|
| |
Kalaitzis, Christos |
STOC '18: "Improved Approximation for ..."
Improved Approximation for Tree Augmentation: Saving by Rewiring
Fabrizio Grandoni, Christos Kalaitzis, and Rico Zenklusen
(University of Lugano, Switzerland; ETH Zurich, Switzerland)
@InProceedings{STOC18p745,
author = {Fabrizio Grandoni and Christos Kalaitzis and Rico Zenklusen},
title = {Improved Approximation for Tree Augmentation: Saving by Rewiring},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {745-744},
doi = {10.1145/3188745.3188898},
year = {2018},
}
Publisher's Version
Article: stoc18main-p284-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188898
|
| |
Kamath, Pritish |
STOC '18: "Monotone Circuit Lower Bounds ..."
Monotone Circuit Lower Bounds from Resolution
Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov
(Microsoft Research, USA; Harvard University, USA; Massachusetts Institute of Technology, USA; KTH, Sweden)
@InProceedings{STOC18p1039,
author = {Ankit Garg and Mika Göös and Pritish Kamath and Dmitry Sokolov},
title = {Monotone Circuit Lower Bounds from Resolution},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1039-1038},
doi = {10.1145/3188745.3188838},
year = {2018},
}
Publisher's Version
Article: stoc18main-p179-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188838
|
| |
Kamma, Lior |
STOC '18: "Tight Cell Probe Bounds for ..."
Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
Diptarka Chakraborty, Lior Kamma, and Kasper Green Larsen
(Charles University in Prague, Czechia; Aarhus University, Denmark)
@InProceedings{STOC18p1515,
author = {Diptarka Chakraborty and Lior Kamma and Kasper Green Larsen},
title = {Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1515-1514},
doi = {10.1145/3188745.3188830},
year = {2018},
}
Publisher's Version
Article: stoc18main-p160-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188830
|
| |
Kane, Daniel M. |
STOC '18: "List-Decodable Robust Mean ..."
List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart
(University of Southern California, USA; University of California at San Diego, USA)
@InProceedings{STOC18p1221,
author = {Ilias Diakonikolas and Daniel M. Kane and Alistair Stewart},
title = {List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1221-1220},
doi = {10.1145/3188745.3188758},
year = {2018},
}
Publisher's Version
Article: stoc18main-p12-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188758
STOC '18: "Learning Geometric Concepts ..."
Learning Geometric Concepts with Nasty Noise
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart
(University of Southern California, USA; University of California at San Diego, USA)
@InProceedings{STOC18p1235,
author = {Ilias Diakonikolas and Daniel M. Kane and Alistair Stewart},
title = {Learning Geometric Concepts with Nasty Noise},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1235-1234},
doi = {10.1145/3188745.3188754},
year = {2018},
}
Publisher's Version
Article: stoc18main-p10-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188754
STOC '18: "Near-Optimal Linear Decision ..."
Near-Optimal Linear Decision Trees for k-SUM and Related Problems
Daniel M. Kane, Shachar Lovett, and Shay Moran
(University of California at San Diego, USA; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC18p647,
author = {Daniel M. Kane and Shachar Lovett and Shay Moran},
title = {Near-Optimal Linear Decision Trees for k-SUM and Related Problems},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {647-646},
doi = {10.1145/3188745.3188770},
year = {2018},
}
Publisher's Version
Article: stoc18main-p49-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188770
STOC '18: "Testing Conditional Independence ..."
Testing Conditional Independence of Discrete Distributions
Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart
(Stanford University, USA; University of Southern California, USA; University of California at San Diego, USA)
@InProceedings{STOC18p857,
author = {Clément L. Canonne and Ilias Diakonikolas and Daniel M. Kane and Alistair Stewart},
title = {Testing Conditional Independence of Discrete Distributions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {857-856},
doi = {10.1145/3188745.3188756},
year = {2018},
}
Publisher's Version
Article: stoc18main-p11-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188756
|
| |
Kang, Ning |
STOC '18: "How to Match When All Vertices ..."
How to Match When All Vertices Arrive Online
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu
(University of Hong Kong, China)
@InProceedings{STOC18p17,
author = {Zhiyi Huang and Ning Kang and Zhihao Gavin Tang and Xiaowei Wu and Yuhao Zhang and Xue Zhu},
title = {How to Match When All Vertices Arrive Online},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {17-16},
doi = {10.1145/3188745.3188858},
year = {2018},
}
Publisher's Version
Article: stoc18main-p214-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188858
|
| |
Karlin, Anna R. |
STOC '18: "A Simply Exponential Upper ..."
A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings
Anna R. Karlin, Shayan Oveis Gharan, and Robbie Weber
(University of Washington, USA)
@InProceedings{STOC18p1067,
author = {Anna R. Karlin and Shayan Oveis Gharan and Robbie Weber},
title = {A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1067-1066},
doi = {10.1145/3188745.3188848},
year = {2018},
}
Publisher's Version
Article: stoc18main-p191-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188848
|
| |
Kaufman, Tali |
STOC '18: "Construction of New Local ..."
Construction of New Local Spectral High Dimensional Expanders
Tali Kaufman and Izhar Oppenheim
(Bar-Ilan University, Israel; Ben-Gurion University of the Negev, Israel)
@InProceedings{STOC18p899,
author = {Tali Kaufman and Izhar Oppenheim},
title = {Construction of New Local Spectral High Dimensional Expanders},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {899-898},
doi = {10.1145/3188745.3188782},
year = {2018},
}
Publisher's Version
Article: stoc18main-p70-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188782
|
| |
Kell, Nathaniel |
STOC '18: "Online Load Balancing on Related ..."
Online Load Balancing on Related Machines
Sungjin Im, Nathaniel Kell, Debmalya Panigrahi, and Maryam Shadloo
(University of California at Merced, USA; Duke University, USA)
@InProceedings{STOC18p31,
author = {Sungjin Im and Nathaniel Kell and Debmalya Panigrahi and Maryam Shadloo},
title = {Online Load Balancing on Related Machines},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {31-30},
doi = {10.1145/3188745.3188966},
year = {2018},
}
Publisher's Version
Article: stoc18main-p439-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188966
|
| |
Kempa, Dominik |
STOC '18: "At the Roots of Dictionary ..."
At the Roots of Dictionary Compression: String Attractors
Dominik Kempa and Nicola Prezza
(University of Helsinki, Finland; DTU, Denmark; University of Pisa, Italy)
@InProceedings{STOC18p955,
author = {Dominik Kempa and Nicola Prezza},
title = {At the Roots of Dictionary Compression: String Attractors},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {955-954},
doi = {10.1145/3188745.3188814},
year = {2018},
}
Publisher's Version
Article: stoc18main-p125-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188814
|
| |
Khot, Subhash |
STOC '18: "On Non-optimally Expanding ..."
On Non-optimally Expanding Sets in Grassmann Graphs
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra
(Weizmann Institute of Science, Israel; New York University, USA; Hebrew University of Jerusalem, Israel; Tel Aviv University, Israel)
@InProceedings{STOC18p1095,
author = {Irit Dinur and Subhash Khot and Guy Kindler and Dor Minzer and Muli Safra},
title = {On Non-optimally Expanding Sets in Grassmann Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1095-1094},
doi = {10.1145/3188745.3188806},
year = {2018},
}
Publisher's Version
Article: stoc18main-p115-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188806
STOC '18: "Towards a Proof of the 2-to-1 ..."
Towards a Proof of the 2-to-1 Games Conjecture?
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra
(Weizmann Institute of Science, Israel; New York University, USA; Hebrew University of Jerusalem, Israel; Tel Aviv University, Israel)
@InProceedings{STOC18p451,
author = {Irit Dinur and Subhash Khot and Guy Kindler and Dor Minzer and Muli Safra},
title = {Towards a Proof of the 2-to-1 Games Conjecture?},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {451-450},
doi = {10.1145/3188745.3188804},
year = {2018},
}
Publisher's Version
Article: stoc18main-p114-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188804
|
| |
Khurana, Dakshita |
STOC '18: "Succinct Delegation for Low-Space ..."
Succinct Delegation for Low-Space Non-deterministic Computation
Saikrishna Badrinarayanan, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai, and Daniel Wichs
(University of California at Los Angeles, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA; Northeastern University, USA)
@InProceedings{STOC18p829,
author = {Saikrishna Badrinarayanan and Yael Tauman Kalai and Dakshita Khurana and Amit Sahai and Daniel Wichs},
title = {Succinct Delegation for Low-Space Non-deterministic Computation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {829-828},
doi = {10.1145/3188745.3188924},
year = {2018},
}
Publisher's Version
Article: stoc18main-p312-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188924
|
| |
Kim, David H. K. |
STOC '18: "Almost Polynomial Hardness ..."
Almost Polynomial Hardness of Node-Disjoint Paths in Grids
Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat
(Toyota Technological Institute at Chicago, USA; University of Chicago, USA)
@InProceedings{STOC18p1417,
author = {Julia Chuzhoy and David H. K. Kim and Rachit Nimavat},
title = {Almost Polynomial Hardness of Node-Disjoint Paths in Grids},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1417-1416},
doi = {10.1145/3188745.3188772},
year = {2018},
}
Publisher's Version
Article: stoc18main-p53-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188772
|
| |
Kindler, Guy |
STOC '18: "On Non-optimally Expanding ..."
On Non-optimally Expanding Sets in Grassmann Graphs
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra
(Weizmann Institute of Science, Israel; New York University, USA; Hebrew University of Jerusalem, Israel; Tel Aviv University, Israel)
@InProceedings{STOC18p1095,
author = {Irit Dinur and Subhash Khot and Guy Kindler and Dor Minzer and Muli Safra},
title = {On Non-optimally Expanding Sets in Grassmann Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1095-1094},
doi = {10.1145/3188745.3188806},
year = {2018},
}
Publisher's Version
Article: stoc18main-p115-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188806
STOC '18: "Towards a Proof of the 2-to-1 ..."
Towards a Proof of the 2-to-1 Games Conjecture?
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra
(Weizmann Institute of Science, Israel; New York University, USA; Hebrew University of Jerusalem, Israel; Tel Aviv University, Israel)
@InProceedings{STOC18p451,
author = {Irit Dinur and Subhash Khot and Guy Kindler and Dor Minzer and Muli Safra},
title = {Towards a Proof of the 2-to-1 Games Conjecture?},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {451-450},
doi = {10.1145/3188745.3188804},
year = {2018},
}
Publisher's Version
Article: stoc18main-p114-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188804
|
| |
Kisfaludi-Bak, Sándor |
STOC '18: "A Framework for ETH-Tight ..."
A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden
(Eindhoven University of Technology, Netherlands; Utrecht University, Netherlands; Hungarian Academy of Sciences, Hungary)
@InProceedings{STOC18p675,
author = {Mark de Berg and Hans L. Bodlaender and Sándor Kisfaludi-Bak and Dániel Marx and Tom C. van der Zanden},
title = {A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {675-674},
doi = {10.1145/3188745.3188854},
year = {2018},
}
Publisher's Version
Article: stoc18main-p204-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188854
|
| |
Kol, Gillat |
STOC '18: "Interactive Compression to ..."
Interactive Compression to External Information
Mark Braverman and Gillat Kol
(Princeton University, USA)
@InProceedings{STOC18p1123,
author = {Mark Braverman and Gillat Kol},
title = {Interactive Compression to External Information},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1123-1122},
doi = {10.1145/3188745.3188956},
year = {2018},
}
Publisher's Version
Article: stoc18main-p413-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188956
STOC '18: "Interactive Coding over the ..."
Interactive Coding over the Noisy Broadcast Channel
Klim Efremenko, Gillat Kol, and Raghuvansh Saxena
(Ben-Gurion University of the Negev, Israel; Princeton University, USA)
@InProceedings{STOC18p591,
author = {Klim Efremenko and Gillat Kol and Raghuvansh Saxena},
title = {Interactive Coding over the Noisy Broadcast Channel},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {591-590},
doi = {10.1145/3188745.3188884},
year = {2018},
}
Publisher's Version
Article: stoc18main-p262-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188884
|
| |
Komarath, Balagopal |
STOC '18: "On the Complexity of Hazard-Free ..."
On the Complexity of Hazard-Free Circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, and Karteek Sreenivasaiah
(Max Planck Institute for Informatics, Germany; Saarland University, Germany; M2CI, Germany; Newcastle University, UK; IIT Hyderabad, India)
@InProceedings{STOC18p1011,
author = {Christian Ikenmeyer and Balagopal Komarath and Christoph Lenzen and Vladimir Lysikov and Andrey Mokhov and Karteek Sreenivasaiah},
title = {On the Complexity of Hazard-Free Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1011-1010},
doi = {10.1145/3188745.3188912},
year = {2018},
}
Publisher's Version
Article: stoc18main-p297-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188912
|
| |
Koppula, Venkata |
STOC '18: "Collusion Resistant Traitor ..."
Collusion Resistant Traitor Tracing from Learning with Errors
Rishab Goyal, Venkata Koppula, and Brent Waters
(University of Texas at Austin, USA)
@InProceedings{STOC18p773,
author = {Rishab Goyal and Venkata Koppula and Brent Waters},
title = {Collusion Resistant Traitor Tracing from Learning with Errors},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {773-772},
doi = {10.1145/3188745.3188844},
year = {2018},
}
Publisher's Version
Article: stoc18main-p187-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188844
|
| |
Korhonen, Janne H. |
STOC '18: "New Classes of Distributed ..."
New Classes of Distributed Time Complexity
Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela
(Aalto University, Finland; University of Freiburg, Germany)
@InProceedings{STOC18p1529,
author = {Alkida Balliu and Juho Hirvonen and Janne H. Korhonen and Tuomo Lempiäinen and Dennis Olivetti and Jukka Suomela},
title = {New Classes of Distributed Time Complexity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1529-1528},
doi = {10.1145/3188745.3188860},
year = {2018},
}
Publisher's Version
Article: stoc18main-p220-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188860
|
| |
Kosowski, Adrian |
STOC '18: "Universal Protocols for Information ..."
Universal Protocols for Information Dissemination using Emergent Signals
Bartłomiej Dudek and Adrian Kosowski
(University of Wrocław, Poland; Inria, France)
@InProceedings{STOC18p101,
author = {Bartłomiej Dudek and Adrian Kosowski},
title = {Universal Protocols for Information Dissemination using Emergent Signals},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {101-100},
doi = {10.1145/3188745.3188818},
year = {2018},
}
Publisher's Version
Article: stoc18main-p142-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188818
|
| |
Kothari, Pravesh K. |
STOC '18: "Robust Moment Estimation and ..."
Robust Moment Estimation and Improved Clustering via Sum of Squares
Pravesh K. Kothari, Jacob Steinhardt, and David Steurer
(Princeton University, USA; Institute for Advanced Study at Princeton, USA; Stanford University, USA; ETH Zurich, Switzerland)
@InProceedings{STOC18p1207,
author = {Pravesh K. Kothari and Jacob Steinhardt and David Steurer},
title = {Robust Moment Estimation and Improved Clustering via Sum of Squares},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1207-1206},
doi = {10.1145/3188745.3188970},
year = {2018},
}
Publisher's Version
Article: stoc18main-p444-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188970
STOC '18: "Sum-of-Squares Meets Nash: ..."
Sum-of-Squares Meets Nash: Lower Bounds for Finding Any Equilibrium
Pravesh K. Kothari and Ruta Mehta
(Princeton University, USA; Institute for Advanced Study at Princeton, USA; University of Illinois at Urbana-Champaign, USA)
@InProceedings{STOC18p1445,
author = {Pravesh K. Kothari and Ruta Mehta},
title = {Sum-of-Squares Meets Nash: Lower Bounds for Finding Any Equilibrium},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1445-1444},
doi = {10.1145/3188745.3188892},
year = {2018},
}
Publisher's Version
Article: stoc18main-p277-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188892
|
| |
Kothari, Robin |
STOC '18: "The Polynomial Method Strikes ..."
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
Mark Bun, Robin Kothari, and Justin Thaler
(Princeton University, USA; Microsoft Research, USA; Georgetown University, USA)
@InProceedings{STOC18p367,
author = {Mark Bun and Robin Kothari and Justin Thaler},
title = {The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {367-366},
doi = {10.1145/3188745.3188784},
year = {2018},
}
Publisher's Version
Article: stoc18main-p75-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188784
|
| |
Koucký, Michal |
STOC '18: "Simulation Beats Richness: ..."
Simulation Beats Richness: New Data-Structure Lower Bounds
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay
(TIFR, India; Charles University in Prague, Czechia; INESC TEC, Portugal; University of Porto, Portugal; KTH, Sweden)
@InProceedings{STOC18p1179,
author = {Arkadev Chattopadhyay and Michal Koucký and Bruno Loff and Sagnik Mukhopadhyay},
title = {Simulation Beats Richness: New Data-Structure Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1179-1178},
doi = {10.1145/3188745.3188874},
year = {2018},
}
Publisher's Version
Article: stoc18main-p242-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188874
|
| |
Kozma, László |
STOC '18: "Smooth Heaps and a Dual View ..."
Smooth Heaps and a Dual View of Self-Adjusting Data Structures
László Kozma and Thatchaphol Saranurak
(Eindhoven University of Technology, Netherlands; KTH, Sweden)
@InProceedings{STOC18p927,
author = {László Kozma and Thatchaphol Saranurak},
title = {Smooth Heaps and a Dual View of Self-Adjusting Data Structures},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {927-926},
doi = {10.1145/3188745.3188864},
year = {2018},
}
Publisher's Version
Article: stoc18main-p225-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188864
|
| |
Krishnaswamy, Ravishankar |
STOC '18: "Constant Approximation for ..."
Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding
Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep
(Microsoft Research, India; SUNY Buffalo, USA)
@InProceedings{STOC18p759,
author = {Ravishankar Krishnaswamy and Shi Li and Sai Sandeep},
title = {Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {759-758},
doi = {10.1145/3188745.3188882},
year = {2018},
}
Publisher's Version
Article: stoc18main-p260-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188882
|
| |
Kuhn, Fabian |
STOC '18: "Deterministic Distributed ..."
Deterministic Distributed Edge-Coloring with Fewer Colors
Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, and Jara Uitto
(ETH Zurich, Switzerland; University of Freiburg, Germany)
@InProceedings{STOC18p493,
author = {Mohsen Ghaffari and Fabian Kuhn and Yannic Maus and Jara Uitto},
title = {Deterministic Distributed Edge-Coloring with Fewer Colors},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {493-492},
doi = {10.1145/3188745.3188906},
year = {2018},
}
Publisher's Version
Article: stoc18main-p293-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188906
|
| |
Kumar, Ashutosh |
STOC '18: "Non-malleable Secret Sharing ..."
Non-malleable Secret Sharing
Vipul Goyal and Ashutosh Kumar
(Carnegie Mellon University, USA; University of California at Los Angeles, USA)
@InProceedings{STOC18p801,
author = {Vipul Goyal and Ashutosh Kumar},
title = {Non-malleable Secret Sharing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {801-800},
doi = {10.1145/3188745.3188872},
year = {2018},
}
Publisher's Version
Article: stoc18main-p238-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188872
|
| |
Kutten, Shay |
STOC '18: "Approximating Generalized ..."
Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency
Yuval Emek, Shay Kutten, Ron Lavi, and Yangguang Shi
(Technion, Israel)
@InProceedings{STOC18p703,
author = {Yuval Emek and Shay Kutten and Ron Lavi and Yangguang Shi},
title = {Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {703-702},
doi = {10.1145/3188745.3188812},
year = {2018},
}
Publisher's Version
Article: stoc18main-p121-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188812
|
| |
Kwok, Tsz Chiu |
STOC '18: "The Paulsen Problem, Continuous ..."
The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, and Akshay Ramachandran
(University of Waterloo, Canada; University of Washington, USA)
@InProceedings{STOC18p227,
author = {Tsz Chiu Kwok and Lap Chi Lau and Yin Tat Lee and Akshay Ramachandran},
title = {The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {227-226},
doi = {10.1145/3188745.3188794},
year = {2018},
}
Publisher's Version
Article: stoc18main-p101-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188794
|
| |
Kyng, Rasmus |
STOC '18: "Incomplete Nested Dissection ..."
Incomplete Nested Dissection
Rasmus Kyng, Richard Peng, Robert Schwieterman, and Peng Zhang
(Simons Institute for the Theory of Computing Berkeley, USA; Georgia Tech, USA)
@InProceedings{STOC18p479,
author = {Rasmus Kyng and Richard Peng and Robert Schwieterman and Peng Zhang},
title = {Incomplete Nested Dissection},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {479-478},
doi = {10.1145/3188745.3188960},
year = {2018},
}
Publisher's Version
Article: stoc18main-p429-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188960
|
| |
Łącki, Jakub
|
STOC '18: "Round Compression for Parallel ..."
Round Compression for Parallel Matching Algorithms
Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski
(University of Warwick, UK; Google Research, USA; Massachusetts Institute of Technology, USA; EPFL, Switzerland; IBM Research, USA; University of Warsaw, Poland)
@InProceedings{STOC18p549,
author = {Artur Czumaj and Jakub Łącki and Aleksander Mądry and Slobodan Mitrović and Krzysztof Onak and Piotr Sankowski},
title = {Round Compression for Parallel Matching Algorithms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {549-548},
doi = {},
year = {2018},
}
Article: stoc18main-p15-p (type: Full Paper (14 pages)) doi:
|
| |
Laekhanukit, Bundit |
STOC '18: "On the Parameterized Complexity ..."
On the Parameterized Complexity of Approximating Dominating Set
Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi
(Weizmann Institute of Science, Israel; Max Planck Institute for Informatics, Germany; Shanghai University of Finance and Economics, China; University of California at Berkeley, USA)
@InProceedings{STOC18p1501,
author = {Karthik C. S. and Bundit Laekhanukit and Pasin Manurangsi},
title = {On the Parameterized Complexity of Approximating Dominating Set},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1501-1500},
doi = {10.1145/3188745.3188896},
year = {2018},
}
Publisher's Version
Article: stoc18main-p281-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188896
|
| |
Lapinskas, John |
STOC '18: "Fine-Grained Reductions from ..."
Fine-Grained Reductions from Approximate Counting to Decision
Holger Dell and John Lapinskas
(Saarland University, Germany; M2CI, Germany; University of Oxford, UK)
@InProceedings{STOC18p339,
author = {Holger Dell and John Lapinskas},
title = {Fine-Grained Reductions from Approximate Counting to Decision},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {339-338},
doi = {10.1145/3188745.3188920},
year = {2018},
}
Publisher's Version
Article: stoc18main-p307-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188920
|
| |
Larsen, Kasper Green |
STOC '18: "Crossing the Logarithmic Barrier ..."
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
Kasper Green Larsen, Omri Weinstein, and Huacheng Yu
(Aarhus University, Denmark; Columbia University, USA; Harvard University, USA)
@InProceedings{STOC18p1137,
author = {Kasper Green Larsen and Omri Weinstein and Huacheng Yu},
title = {Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1137-1136},
doi = {10.1145/3188745.3188790},
year = {2018},
}
Publisher's Version
Article: stoc18main-p97-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188790
STOC '18: "Tight Cell Probe Bounds for ..."
Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
Diptarka Chakraborty, Lior Kamma, and Kasper Green Larsen
(Charles University in Prague, Czechia; Aarhus University, Denmark)
@InProceedings{STOC18p1515,
author = {Diptarka Chakraborty and Lior Kamma and Kasper Green Larsen},
title = {Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1515-1514},
doi = {10.1145/3188745.3188830},
year = {2018},
}
Publisher's Version
Article: stoc18main-p160-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188830
|
| |
Lau, Lap Chi |
STOC '18: "The Paulsen Problem, Continuous ..."
The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, and Akshay Ramachandran
(University of Waterloo, Canada; University of Washington, USA)
@InProceedings{STOC18p227,
author = {Tsz Chiu Kwok and Lap Chi Lau and Yin Tat Lee and Akshay Ramachandran},
title = {The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {227-226},
doi = {10.1145/3188745.3188794},
year = {2018},
}
Publisher's Version
Article: stoc18main-p101-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188794
|
| |
Lauria, Massimo |
STOC '18: "Clique Is Hard on Average ..."
Clique Is Hard on Average for Regular Resolution
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, and Alexander Razborov
(Universitat Politècnica de Catalunya, Spain; KTH, Sweden; Sapienza University of Rome, Italy; University of Chicago, USA; Russian Academy of Sciences, Russia)
@InProceedings{STOC18p997,
author = {Albert Atserias and Ilario Bonacina and Susanna F. de Rezende and Massimo Lauria and Jakob Nordström and Alexander Razborov},
title = {Clique Is Hard on Average for Regular Resolution},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {997-996},
doi = {10.1145/3188745.3188856},
year = {2018},
}
Publisher's Version
Article: stoc18main-p211-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188856
|
| |
Lavi, Ron |
STOC '18: "Approximating Generalized ..."
Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency
Yuval Emek, Shay Kutten, Ron Lavi, and Yangguang Shi
(Technion, Israel)
@InProceedings{STOC18p703,
author = {Yuval Emek and Shay Kutten and Ron Lavi and Yangguang Shi},
title = {Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {703-702},
doi = {10.1145/3188745.3188812},
year = {2018},
}
Publisher's Version
Article: stoc18main-p121-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188812
|
| |
Lee, James R. |
STOC '18: "k-Server via Multiscale Entropic ..."
k-Server via Multiscale Entropic Regularization
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Mądry
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; University of Washington, USA)
@InProceedings{STOC18p3,
author = {Sébastien Bubeck and Michael B. Cohen and Yin Tat Lee and James R. Lee and Aleksander Mądry},
title = {k-Server via Multiscale Entropic Regularization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {3-2},
doi = {},
year = {2018},
}
Article: stoc18main-p111-p (type: Full Paper (14 pages)) doi:
|
| |
Lee, Yin Tat |
STOC '18: "A Matrix Expander Chernoff ..."
A Matrix Expander Chernoff Bound
Ankit Garg, Yin Tat Lee, Zhao Song, and Nikhil Srivastava
(Microsoft Research, USA; University of Washington, USA; Harvard University, USA; University of Texas at Austin, USA; University of California at Berkeley, USA)
@InProceedings{STOC18p1277,
author = {Ankit Garg and Yin Tat Lee and Zhao Song and Nikhil Srivastava},
title = {A Matrix Expander Chernoff Bound},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1277-1276},
doi = {10.1145/3188745.3188890},
year = {2018},
}
Publisher's Version
Article: stoc18main-p275-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188890
STOC '18: "Convergence Rate of Riemannian ..."
Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation
Yin Tat Lee and Santosh S. Vempala
(University of Washington, USA; Microsoft Research, USA; Georgia Tech, USA)
@InProceedings{STOC18p1291,
author = {Yin Tat Lee and Santosh S. Vempala},
title = {Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1291-1290},
doi = {10.1145/3188745.3188774},
year = {2018},
}
Publisher's Version
Article: stoc18main-p55-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188774
STOC '18: "Stochastic Localization + ..."
Stochastic Localization + Stieltjes Barrier = Tight Bound for Log-Sobolev
Yin Tat Lee and Santosh S. Vempala
(University of Washington, USA; Microsoft Research, USA; Georgia Tech, USA)
@InProceedings{STOC18p1305,
author = {Yin Tat Lee and Santosh S. Vempala},
title = {Stochastic Localization + Stieltjes Barrier = Tight Bound for Log-Sobolev},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1305-1304},
doi = {10.1145/3188745.3188866},
year = {2018},
}
Publisher's Version
Article: stoc18main-p230-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188866
STOC '18: "An Homotopy Method for lp ..."
An Homotopy Method for lp Regression Provably beyond Self-Concordance and in Input-Sparsity Time
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, and Yuanzhi Li
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; University of Washington, USA; Princeton University, USA)
@InProceedings{STOC18p1319,
author = {Sébastien Bubeck and Michael B. Cohen and Yin Tat Lee and Yuanzhi Li},
title = {An Homotopy Method for l<sub>p</sub> Regression Provably beyond Self-Concordance and in Input-Sparsity Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1319-1318},
doi = {10.1145/3188745.3188776},
year = {2018},
}
Publisher's Version
Article: stoc18main-p62-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188776
STOC '18: "The Paulsen Problem, Continuous ..."
The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, and Akshay Ramachandran
(University of Waterloo, Canada; University of Washington, USA)
@InProceedings{STOC18p227,
author = {Tsz Chiu Kwok and Lap Chi Lau and Yin Tat Lee and Akshay Ramachandran},
title = {The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {227-226},
doi = {10.1145/3188745.3188794},
year = {2018},
}
Publisher's Version
Article: stoc18main-p101-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188794
STOC '18: "k-Server via Multiscale Entropic ..."
k-Server via Multiscale Entropic Regularization
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Mądry
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; University of Washington, USA)
@InProceedings{STOC18p3,
author = {Sébastien Bubeck and Michael B. Cohen and Yin Tat Lee and James R. Lee and Aleksander Mądry},
title = {k-Server via Multiscale Entropic Regularization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {3-2},
doi = {},
year = {2018},
}
Article: stoc18main-p111-p (type: Full Paper (14 pages)) doi:
|
| |
Lempiäinen, Tuomo |
STOC '18: "New Classes of Distributed ..."
New Classes of Distributed Time Complexity
Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela
(Aalto University, Finland; University of Freiburg, Germany)
@InProceedings{STOC18p1529,
author = {Alkida Balliu and Juho Hirvonen and Janne H. Korhonen and Tuomo Lempiäinen and Dennis Olivetti and Jukka Suomela},
title = {New Classes of Distributed Time Complexity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1529-1528},
doi = {10.1145/3188745.3188860},
year = {2018},
}
Publisher's Version
Article: stoc18main-p220-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188860
|
| |
Lenzen, Christoph |
STOC '18: "On the Complexity of Hazard-Free ..."
On the Complexity of Hazard-Free Circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, and Karteek Sreenivasaiah
(Max Planck Institute for Informatics, Germany; Saarland University, Germany; M2CI, Germany; Newcastle University, UK; IIT Hyderabad, India)
@InProceedings{STOC18p1011,
author = {Christian Ikenmeyer and Balagopal Komarath and Christoph Lenzen and Vladimir Lysikov and Andrey Mokhov and Karteek Sreenivasaiah},
title = {On the Complexity of Hazard-Free Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1011-1010},
doi = {10.1145/3188745.3188912},
year = {2018},
}
Publisher's Version
Article: stoc18main-p297-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188912
|
| |
Leung, Debbie |
STOC '18: "Capacity Approaching Coding ..."
Capacity Approaching Coding for Low Noise Interactive Quantum Communication
Debbie Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, and Nengkun Yu
(University of Waterloo, Canada; Perimeter Institute Waterloo, Canada; Nanjing University, China; University of Technology Sydney, Australia)
@InProceedings{STOC18p409,
author = {Debbie Leung and Ashwin Nayak and Ala Shayeghi and Dave Touchette and Penghui Yao and Nengkun Yu},
title = {Capacity Approaching Coding for Low Noise Interactive Quantum Communication},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {409-408},
doi = {10.1145/3188745.3188908},
year = {2018},
}
Publisher's Version
Article: stoc18main-p294-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188908
|
| |
Leverrier, Anthony |
STOC '18: "Efficient Decoding of Random ..."
Efficient Decoding of Random Errors for Quantum Expander Codes
Omar Fawzi, Antoine Grospellier, and Anthony Leverrier
(ENS Lyon, France; Inria, France)
@InProceedings{STOC18p605,
author = {Omar Fawzi and Antoine Grospellier and Anthony Leverrier},
title = {Efficient Decoding of Random Errors for Quantum Expander Codes},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {605-604},
doi = {10.1145/3188745.3188886},
year = {2018},
}
Publisher's Version
Article: stoc18main-p263-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188886
|
| |
Li, Jason |
STOC '18: "Improved Distributed Algorithms ..."
Improved Distributed Algorithms for Exact Shortest Paths
Mohsen Ghaffari and Jason Li
(ETH Zurich, Switzerland; Carnegie Mellon University, USA)
@InProceedings{STOC18p507,
author = {Mohsen Ghaffari and Jason Li},
title = {Improved Distributed Algorithms for Exact Shortest Paths},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {507-506},
doi = {10.1145/3188745.3188948},
year = {2018},
}
Publisher's Version
Article: stoc18main-p394-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188948
|
| |
Li, Jerry |
STOC '18: "Mixture Models, Robustness, ..."
Mixture Models, Robustness, and Sum of Squares Proofs
Samuel B. Hopkins and Jerry Li
(Cornell University, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC18p1193,
author = {Samuel B. Hopkins and Jerry Li},
title = {Mixture Models, Robustness, and Sum of Squares Proofs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1193-1192},
doi = {10.1145/3188745.3188748},
year = {2018},
}
Publisher's Version
Article: stoc18main-p3-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188748
|
| |
Li, Shi |
STOC '18: "Constant Approximation for ..."
Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding
Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep
(Microsoft Research, India; SUNY Buffalo, USA)
@InProceedings{STOC18p759,
author = {Ravishankar Krishnaswamy and Shi Li and Sai Sandeep},
title = {Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {759-758},
doi = {10.1145/3188745.3188882},
year = {2018},
}
Publisher's Version
Article: stoc18main-p260-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188882
|
| |
Li, Wenzheng |
STOC '18: "An Optimal Distributed (Δ+1)-Coloring ..."
An Optimal Distributed (Δ+1)-Coloring Algorithm?
Yi-Jun Chang, Wenzheng Li, and Seth Pettie
(University of Michigan, USA; Tsinghua University, China)
@InProceedings{STOC18p521,
author = {Yi-Jun Chang and Wenzheng Li and Seth Pettie},
title = {An Optimal Distributed (Δ+1)-Coloring Algorithm?},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {521-520},
doi = {10.1145/3188745.3188964},
year = {2018},
}
Publisher's Version
Article: stoc18main-p436-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188964
|
| |
Li, Yuanzhi |
STOC '18: "An Homotopy Method for lp ..."
An Homotopy Method for lp Regression Provably beyond Self-Concordance and in Input-Sparsity Time
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, and Yuanzhi Li
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; University of Washington, USA; Princeton University, USA)
@InProceedings{STOC18p1319,
author = {Sébastien Bubeck and Michael B. Cohen and Yin Tat Lee and Yuanzhi Li},
title = {An Homotopy Method for l<sub>p</sub> Regression Provably beyond Self-Concordance and in Input-Sparsity Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1319-1318},
doi = {10.1145/3188745.3188776},
year = {2018},
}
Publisher's Version
Article: stoc18main-p62-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188776
STOC '18: "Operator Scaling via Geodesically ..."
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson
(Microsoft Research, USA; Princeton University, USA; University of Toronto, Canada; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC18p213,
author = {Zeyuan Allen-Zhu and Ankit Garg and Yuanzhi Li and Rafael Oliveira and Avi Wigderson},
title = {Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {213-212},
doi = {10.1145/3188745.3188942},
year = {2018},
}
Publisher's Version
Article: stoc18main-p382-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188942
|
| |
Liang, Percy |
STOC '18: "Prediction with a Short Memory ..."
Prediction with a Short Memory
Vatsal Sharan, Sham Kakade, Percy Liang, and Gregory Valiant
(Stanford University, USA; University of Washington, USA)
@InProceedings{STOC18p1249,
author = {Vatsal Sharan and Sham Kakade and Percy Liang and Gregory Valiant},
title = {Prediction with a Short Memory},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1249-1248},
doi = {10.1145/3188745.3188954},
year = {2018},
}
Publisher's Version
Article: stoc18main-p410-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188954
|
| |
Liao, Chao |
STOC '18: "Counting Hypergraph Colourings ..."
Counting Hypergraph Colourings in the Local Lemma Regime
Heng Guo, Chao Liao, Pinyan Lu, and Chihao Zhang
(University of Edinburgh, UK; Shanghai Jiao Tong University, China; Shanghai University of Finance and Economics, China; Chinese University of Hong Kong, China)
@InProceedings{STOC18p1081,
author = {Heng Guo and Chao Liao and Pinyan Lu and Chihao Zhang},
title = {Counting Hypergraph Colourings in the Local Lemma Regime},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1081-1080},
doi = {10.1145/3188745.3188934},
year = {2018},
}
Publisher's Version
Article: stoc18main-p364-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188934
|
| |
Liu, Tianren |
STOC '18: "Breaking the Circuit-Size ..."
Breaking the Circuit-Size Barrier in Secret Sharing
Tianren Liu and Vinod Vaikuntanathan
(Massachusetts Institute of Technology, USA)
@InProceedings{STOC18p815,
author = {Tianren Liu and Vinod Vaikuntanathan},
title = {Breaking the Circuit-Size Barrier in Secret Sharing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {815-814},
doi = {10.1145/3188745.3188936},
year = {2018},
}
Publisher's Version
Article: stoc18main-p368-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188936
|
| |
Liu, Zhengyang |
STOC '18: "Distribution-Free Junta Testing ..."
Distribution-Free Junta Testing
Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, and Jinyu Xie
(Shanghai Jiao Tong University, China; Columbia University, USA)
@InProceedings{STOC18p871,
author = {Zhengyang Liu and Xi Chen and Rocco A. Servedio and Ying Sheng and Jinyu Xie},
title = {Distribution-Free Junta Testing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {871-870},
doi = {10.1145/3188745.3188842},
year = {2018},
}
Publisher's Version
Article: stoc18main-p186-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188842
|
| |
Lkhamsuren, Luvsandondov |
STOC '18: "Holiest Minimum-Cost Paths ..."
Holiest Minimum-Cost Paths and Flows in Surface Graphs
Jeff Erickson, Kyle Fox, and Luvsandondov Lkhamsuren
(University of Illinois at Urbana-Champaign, USA; University of Texas at Dallas, USA; Airbnb, USA)
@InProceedings{STOC18p1543,
author = {Jeff Erickson and Kyle Fox and Luvsandondov Lkhamsuren},
title = {Holiest Minimum-Cost Paths and Flows in Surface Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1543-1542},
doi = {10.1145/3188745.3188904},
year = {2018},
}
Publisher's Version
Article: stoc18main-p289-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188904
|
| |
Lo, Irene |
STOC '18: "Dynamic Matching in School ..."
Dynamic Matching in School Choice: Efficient Seat Reassignment after Late Cancellations (Invited Talk)
Irene Lo
(Columbia University, USA)
@InProceedings{STOC18p1,
author = {Irene Lo},
title = {Dynamic Matching in School Choice: Efficient Seat Reassignment after Late Cancellations (Invited Talk)},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1-0},
doi = {10.1145/3188745.3232193},
year = {2018},
}
Publisher's Version
Article: stoc18key-idk3-p (type: Invited Talk Paper (1 page)) doi:10.1145/3188745.3232193
|
| |
Loff, Bruno |
STOC '18: "Simulation Beats Richness: ..."
Simulation Beats Richness: New Data-Structure Lower Bounds
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay
(TIFR, India; Charles University in Prague, Czechia; INESC TEC, Portugal; University of Porto, Portugal; KTH, Sweden)
@InProceedings{STOC18p1179,
author = {Arkadev Chattopadhyay and Michal Koucký and Bruno Loff and Sagnik Mukhopadhyay},
title = {Simulation Beats Richness: New Data-Structure Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1179-1178},
doi = {10.1145/3188745.3188874},
year = {2018},
}
Publisher's Version
Article: stoc18main-p242-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188874
|
| |
Lovett, Shachar |
STOC '18: "Near-Optimal Linear Decision ..."
Near-Optimal Linear Decision Trees for k-SUM and Related Problems
Daniel M. Kane, Shachar Lovett, and Shay Moran
(University of California at San Diego, USA; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC18p647,
author = {Daniel M. Kane and Shachar Lovett and Shay Moran},
title = {Near-Optimal Linear Decision Trees for k-SUM and Related Problems},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {647-646},
doi = {10.1145/3188745.3188770},
year = {2018},
}
Publisher's Version
Article: stoc18main-p49-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188770
STOC '18: "The Gram-Schmidt Walk: A Cure ..."
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett
(Eindhoven University of Technology, Netherlands; CWI, Netherlands; University of California at San Diego, USA)
@InProceedings{STOC18p689,
author = {Nikhil Bansal and Daniel Dadush and Shashwat Garg and Shachar Lovett},
title = {The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {689-688},
doi = {10.1145/3188745.3188850},
year = {2018},
}
Publisher's Version
Article: stoc18main-p195-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188850
|
| |
Lu, Pinyan |
STOC '18: "Counting Hypergraph Colourings ..."
Counting Hypergraph Colourings in the Local Lemma Regime
Heng Guo, Chao Liao, Pinyan Lu, and Chihao Zhang
(University of Edinburgh, UK; Shanghai Jiao Tong University, China; Shanghai University of Finance and Economics, China; Chinese University of Hong Kong, China)
@InProceedings{STOC18p1081,
author = {Heng Guo and Chao Liao and Pinyan Lu and Chihao Zhang},
title = {Counting Hypergraph Colourings in the Local Lemma Regime},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1081-1080},
doi = {10.1145/3188745.3188934},
year = {2018},
}
Publisher's Version
Article: stoc18main-p364-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188934
|
| |
Lykouris, Thodoris |
STOC '18: "Stochastic Bandits Robust ..."
Stochastic Bandits Robust to Adversarial Corruptions
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme
(Cornell University, USA; Google Research, USA)
@InProceedings{STOC18p129,
author = {Thodoris Lykouris and Vahab Mirrokni and Renato Paes Leme},
title = {Stochastic Bandits Robust to Adversarial Corruptions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {129-128},
doi = {10.1145/3188745.3188918},
year = {2018},
}
Publisher's Version
Article: stoc18main-p304-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188918
|
| |
Lysikov, Vladimir |
STOC '18: "On the Complexity of Hazard-Free ..."
On the Complexity of Hazard-Free Circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, and Karteek Sreenivasaiah
(Max Planck Institute for Informatics, Germany; Saarland University, Germany; M2CI, Germany; Newcastle University, UK; IIT Hyderabad, India)
@InProceedings{STOC18p1011,
author = {Christian Ikenmeyer and Balagopal Komarath and Christoph Lenzen and Vladimir Lysikov and Andrey Mokhov and Karteek Sreenivasaiah},
title = {On the Complexity of Hazard-Free Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1011-1010},
doi = {10.1145/3188745.3188912},
year = {2018},
}
Publisher's Version
Article: stoc18main-p297-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188912
STOC '18: "Generalized Matrix Completion ..."
Generalized Matrix Completion and Algebraic Natural Proofs
Markus Bläser, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov
(Saarland University, Germany; Max Planck Institute for Informatics, Germany)
@InProceedings{STOC18p1389,
author = {Markus Bläser and Christian Ikenmeyer and Gorav Jindal and Vladimir Lysikov},
title = {Generalized Matrix Completion and Algebraic Natural Proofs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1389-1388},
doi = {10.1145/3188745.3188832},
year = {2018},
}
Publisher's Version
Article: stoc18main-p165-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188832
|
| |
Ma, Tengyu
|
STOC '18: "Generalization and Equilibrium ..."
Generalization and Equilibrium in Generative Adversarial Nets (GANs) (Invited Talk)
Tengyu Ma
(Stanford University, USA)
@InProceedings{STOC18p2,
author = {Tengyu Ma},
title = {Generalization and Equilibrium in Generative Adversarial Nets (GANs) (Invited Talk)},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {2-1},
doi = {10.1145/3188745.3232194},
year = {2018},
}
Publisher's Version
Article: stoc18key-idk8-p (type: Invited Talk Paper (1 page)) doi:10.1145/3188745.3232194
|
| |
Mądry, Aleksander |
STOC '18: "k-Server via Multiscale Entropic ..."
k-Server via Multiscale Entropic Regularization
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Mądry
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; University of Washington, USA)
@InProceedings{STOC18p3,
author = {Sébastien Bubeck and Michael B. Cohen and Yin Tat Lee and James R. Lee and Aleksander Mądry},
title = {k-Server via Multiscale Entropic Regularization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {3-2},
doi = {},
year = {2018},
}
Article: stoc18main-p111-p (type: Full Paper (14 pages)) doi:
STOC '18: "Round Compression for Parallel ..."
Round Compression for Parallel Matching Algorithms
Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski
(University of Warwick, UK; Google Research, USA; Massachusetts Institute of Technology, USA; EPFL, Switzerland; IBM Research, USA; University of Warsaw, Poland)
@InProceedings{STOC18p549,
author = {Artur Czumaj and Jakub Łącki and Aleksander Mądry and Slobodan Mitrović and Krzysztof Onak and Piotr Sankowski},
title = {Round Compression for Parallel Matching Algorithms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {549-548},
doi = {},
year = {2018},
}
Article: stoc18main-p15-p (type: Full Paper (14 pages)) doi:
|
| |
Mahabadi, Sepideh |
STOC '18: "Nonlinear Dimension Reduction ..."
Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn
(Columbia University, USA; Northwestern University, USA; Toyota Technological Institute at Chicago, USA; Microsoft Research, USA)
@InProceedings{STOC18p1263,
author = {Sepideh Mahabadi and Konstantin Makarychev and Yury Makarychev and Ilya Razenshteyn},
title = {Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1263-1262},
doi = {10.1145/3188745.3188828},
year = {2018},
}
Publisher's Version
Article: stoc18main-p152-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188828
|
| |
Makarychev, Konstantin |
STOC '18: "Nonlinear Dimension Reduction ..."
Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn
(Columbia University, USA; Northwestern University, USA; Toyota Technological Institute at Chicago, USA; Microsoft Research, USA)
@InProceedings{STOC18p1263,
author = {Sepideh Mahabadi and Konstantin Makarychev and Yury Makarychev and Ilya Razenshteyn},
title = {Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1263-1262},
doi = {10.1145/3188745.3188828},
year = {2018},
}
Publisher's Version
Article: stoc18main-p152-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188828
|
| |
Makarychev, Yury |
STOC '18: "Nonlinear Dimension Reduction ..."
Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn
(Columbia University, USA; Northwestern University, USA; Toyota Technological Institute at Chicago, USA; Microsoft Research, USA)
@InProceedings{STOC18p1263,
author = {Sepideh Mahabadi and Konstantin Makarychev and Yury Makarychev and Ilya Razenshteyn},
title = {Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1263-1262},
doi = {10.1145/3188745.3188828},
year = {2018},
}
Publisher's Version
Article: stoc18main-p152-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188828
|
| |
Manurangsi, Pasin |
STOC '18: "On the Parameterized Complexity ..."
On the Parameterized Complexity of Approximating Dominating Set
Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi
(Weizmann Institute of Science, Israel; Max Planck Institute for Informatics, Germany; Shanghai University of Finance and Economics, China; University of California at Berkeley, USA)
@InProceedings{STOC18p1501,
author = {Karthik C. S. and Bundit Laekhanukit and Pasin Manurangsi},
title = {On the Parameterized Complexity of Approximating Dominating Set},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1501-1500},
doi = {10.1145/3188745.3188896},
year = {2018},
}
Publisher's Version
Article: stoc18main-p281-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188896
|
| |
Marx, Dániel |
STOC '18: "A Framework for ETH-Tight ..."
A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden
(Eindhoven University of Technology, Netherlands; Utrecht University, Netherlands; Hungarian Academy of Sciences, Hungary)
@InProceedings{STOC18p675,
author = {Mark de Berg and Hans L. Bodlaender and Sándor Kisfaludi-Bak and Dániel Marx and Tom C. van der Zanden},
title = {A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {675-674},
doi = {10.1145/3188745.3188854},
year = {2018},
}
Publisher's Version
Article: stoc18main-p204-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188854
|
| |
Maus, Yannic |
STOC '18: "Deterministic Distributed ..."
Deterministic Distributed Edge-Coloring with Fewer Colors
Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, and Jara Uitto
(ETH Zurich, Switzerland; University of Freiburg, Germany)
@InProceedings{STOC18p493,
author = {Mohsen Ghaffari and Fabian Kuhn and Yannic Maus and Jara Uitto},
title = {Deterministic Distributed Edge-Coloring with Fewer Colors},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {493-492},
doi = {10.1145/3188745.3188906},
year = {2018},
}
Publisher's Version
Article: stoc18main-p293-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188906
|
| |
Mehr, Mehran |
STOC '18: "Fast Fencing ..."
Fast Fencing
Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, and Mikkel Thorup
(University of Copenhagen, Denmark; Max Planck Institute for Informatics, Germany; Sorbonne University, France; UPMC, France; CNRS, France; LIP6, France; Eindhoven University of Technology, Netherlands; DTU, Denmark)
@InProceedings{STOC18p661,
author = {Mikkel Abrahamsen and Anna Adamaszek and Karl Bringmann and Vincent Cohen-Addad and Mehran Mehr and Eva Rotenberg and Alan Roytman and Mikkel Thorup},
title = {Fast Fencing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {661-660},
doi = {10.1145/3188745.3188878},
year = {2018},
}
Publisher's Version
Article: stoc18main-p248-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188878
|
| |
Mehta, Ruta |
STOC '18: "Sum-of-Squares Meets Nash: ..."
Sum-of-Squares Meets Nash: Lower Bounds for Finding Any Equilibrium
Pravesh K. Kothari and Ruta Mehta
(Princeton University, USA; Institute for Advanced Study at Princeton, USA; University of Illinois at Urbana-Champaign, USA)
@InProceedings{STOC18p1445,
author = {Pravesh K. Kothari and Ruta Mehta},
title = {Sum-of-Squares Meets Nash: Lower Bounds for Finding Any Equilibrium},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1445-1444},
doi = {10.1145/3188745.3188892},
year = {2018},
}
Publisher's Version
Article: stoc18main-p277-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188892
|
| |
Miltzow, Tillmann |
STOC '18: "The Art Gallery Problem Is ..."
The Art Gallery Problem Is ∃ ℝ-Complete
Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow
(University of Copenhagen, Denmark; Université Libre de Bruxelles, Belgium)
@InProceedings{STOC18p73,
author = {Mikkel Abrahamsen and Anna Adamaszek and Tillmann Miltzow},
title = {The Art Gallery Problem Is ∃ ℝ-Complete},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {73-72},
doi = {},
year = {2018},
}
Article: stoc18main-p233-p (type: Full Paper (14 pages)) doi:
|
| |
Minzer, Dor |
STOC '18: "On Non-optimally Expanding ..."
On Non-optimally Expanding Sets in Grassmann Graphs
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra
(Weizmann Institute of Science, Israel; New York University, USA; Hebrew University of Jerusalem, Israel; Tel Aviv University, Israel)
@InProceedings{STOC18p1095,
author = {Irit Dinur and Subhash Khot and Guy Kindler and Dor Minzer and Muli Safra},
title = {On Non-optimally Expanding Sets in Grassmann Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1095-1094},
doi = {10.1145/3188745.3188806},
year = {2018},
}
Publisher's Version
Article: stoc18main-p115-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188806
STOC '18: "Towards a Proof of the 2-to-1 ..."
Towards a Proof of the 2-to-1 Games Conjecture?
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra
(Weizmann Institute of Science, Israel; New York University, USA; Hebrew University of Jerusalem, Israel; Tel Aviv University, Israel)
@InProceedings{STOC18p451,
author = {Irit Dinur and Subhash Khot and Guy Kindler and Dor Minzer and Muli Safra},
title = {Towards a Proof of the 2-to-1 Games Conjecture?},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {451-450},
doi = {10.1145/3188745.3188804},
year = {2018},
}
Publisher's Version
Article: stoc18main-p114-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188804
|
| |
Mirrokni, Vahab |
STOC '18: "Stochastic Bandits Robust ..."
Stochastic Bandits Robust to Adversarial Corruptions
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme
(Cornell University, USA; Google Research, USA)
@InProceedings{STOC18p129,
author = {Thodoris Lykouris and Vahab Mirrokni and Renato Paes Leme},
title = {Stochastic Bandits Robust to Adversarial Corruptions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {129-128},
doi = {10.1145/3188745.3188918},
year = {2018},
}
Publisher's Version
Article: stoc18main-p304-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188918
|
| |
Mitrović, Slobodan |
STOC '18: "Round Compression for Parallel ..."
Round Compression for Parallel Matching Algorithms
Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski
(University of Warwick, UK; Google Research, USA; Massachusetts Institute of Technology, USA; EPFL, Switzerland; IBM Research, USA; University of Warsaw, Poland)
@InProceedings{STOC18p549,
author = {Artur Czumaj and Jakub Łącki and Aleksander Mądry and Slobodan Mitrović and Krzysztof Onak and Piotr Sankowski},
title = {Round Compression for Parallel Matching Algorithms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {549-548},
doi = {},
year = {2018},
}
Article: stoc18main-p15-p (type: Full Paper (14 pages)) doi:
|
| |
Mokhov, Andrey |
STOC '18: "On the Complexity of Hazard-Free ..."
On the Complexity of Hazard-Free Circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, and Karteek Sreenivasaiah
(Max Planck Institute for Informatics, Germany; Saarland University, Germany; M2CI, Germany; Newcastle University, UK; IIT Hyderabad, India)
@InProceedings{STOC18p1011,
author = {Christian Ikenmeyer and Balagopal Komarath and Christoph Lenzen and Vladimir Lysikov and Andrey Mokhov and Karteek Sreenivasaiah},
title = {On the Complexity of Hazard-Free Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1011-1010},
doi = {10.1145/3188745.3188912},
year = {2018},
}
Publisher's Version
Article: stoc18main-p297-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188912
|
| |
Mömke, Tobias |
STOC '18: "A (5/3 + ε)-Approximation ..."
A (5/3 + ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes
Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou
(University of Lugano, Switzerland; University of Bremen, Germany; Saarland University, Germany; University of Chile, Chile; École Polytechnique, France)
@InProceedings{STOC18p717,
author = {Fabrizio Grandoni and Tobias Mömke and Andreas Wiese and Hang Zhou},
title = {A (5/3 + ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {717-716},
doi = {10.1145/3188745.3188894},
year = {2018},
}
Publisher's Version
Article: stoc18main-p278-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188894
|
| |
Moran, Shay |
STOC '18: "Near-Optimal Linear Decision ..."
Near-Optimal Linear Decision Trees for k-SUM and Related Problems
Daniel M. Kane, Shachar Lovett, and Shay Moran
(University of California at San Diego, USA; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC18p647,
author = {Daniel M. Kane and Shachar Lovett and Shay Moran},
title = {Near-Optimal Linear Decision Trees for k-SUM and Related Problems},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {647-646},
doi = {10.1145/3188745.3188770},
year = {2018},
}
Publisher's Version
Article: stoc18main-p49-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188770
|
| |
Mukhopadhyay, Sagnik |
STOC '18: "Simulation Beats Richness: ..."
Simulation Beats Richness: New Data-Structure Lower Bounds
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay
(TIFR, India; Charles University in Prague, Czechia; INESC TEC, Portugal; University of Porto, Portugal; KTH, Sweden)
@InProceedings{STOC18p1179,
author = {Arkadev Chattopadhyay and Michal Koucký and Bruno Loff and Sagnik Mukhopadhyay},
title = {Simulation Beats Richness: New Data-Structure Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1179-1178},
doi = {10.1145/3188745.3188874},
year = {2018},
}
Publisher's Version
Article: stoc18main-p242-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188874
|
| |
Murray, Cody |
STOC '18: "Circuit Lower Bounds for Nondeterministic ..."
Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP
Cody Murray and Ryan Williams
(Massachusetts Institute of Technology, USA)
@InProceedings{STOC18p1025,
author = {Cody Murray and Ryan Williams},
title = {Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1025-1024},
doi = {10.1145/3188745.3188910},
year = {2018},
}
Publisher's Version
Article: stoc18main-p295-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188910
|
| |
Mütze, Torsten |
STOC '18: "Sparse Kneser Graphs Are Hamiltonian ..."
Sparse Kneser Graphs Are Hamiltonian
Torsten Mütze, Jerri Nummenpalo, and Bartosz Walczak
(TU Berlin, Germany; ETH Zurich, Switzerland; Jagiellonian University, Poland)
@InProceedings{STOC18p1053,
author = {Torsten Mütze and Jerri Nummenpalo and Bartosz Walczak},
title = {Sparse Kneser Graphs Are Hamiltonian},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1053-1052},
doi = {10.1145/3188745.3188834},
year = {2018},
}
Publisher's Version
Article: stoc18main-p166-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188834
|
| |
Nakkiran, Preetum
|
STOC '18: "General Strong Polarization ..."
General Strong Polarization
Jarosław Błasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, and Madhu Sudan
(Harvard University, USA; Carnegie Mellon University, USA; SUNY Buffalo, USA)
@InProceedings{STOC18p563,
author = {Jarosław Błasiok and Venkatesan Guruswami and Preetum Nakkiran and Atri Rudra and Madhu Sudan},
title = {General Strong Polarization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {563-562},
doi = {10.1145/3188745.3188816},
year = {2018},
}
Publisher's Version
Article: stoc18main-p140-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188816
|
| |
Naor, Assaf |
STOC '18: "Data-Dependent Hashing via ..."
Data-Dependent Hashing via Nonlinear Spectral Gaps
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten
(Columbia University, USA; Princeton University, USA; University of Toronto, Canada; Microsoft Research, USA)
@InProceedings{STOC18p913,
author = {Alexandr Andoni and Assaf Naor and Aleksandar Nikolov and Ilya Razenshteyn and Erik Waingarten},
title = {Data-Dependent Hashing via Nonlinear Spectral Gaps},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {913-912},
doi = {10.1145/3188745.3188846},
year = {2018},
}
Publisher's Version
Article: stoc18main-p189-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188846
|
| |
Nayak, Ashwin |
STOC '18: "Capacity Approaching Coding ..."
Capacity Approaching Coding for Low Noise Interactive Quantum Communication
Debbie Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, and Nengkun Yu
(University of Waterloo, Canada; Perimeter Institute Waterloo, Canada; Nanjing University, China; University of Technology Sydney, Australia)
@InProceedings{STOC18p409,
author = {Debbie Leung and Ashwin Nayak and Ala Shayeghi and Dave Touchette and Penghui Yao and Nengkun Yu},
title = {Capacity Approaching Coding for Low Noise Interactive Quantum Communication},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {409-408},
doi = {10.1145/3188745.3188908},
year = {2018},
}
Publisher's Version
Article: stoc18main-p294-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188908
|
| |
Nederlof, Jesper |
STOC '18: "More Consequences of Falsifying ..."
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof
(IBM Research, USA; Max Planck Institute for Informatics, Germany; Saarland University, Germany; M2CI, Germany; Eindhoven University of Technology, Netherlands)
@InProceedings{STOC18p311,
author = {Amir Abboud and Karl Bringmann and Holger Dell and Jesper Nederlof},
title = {More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {311-310},
doi = {10.1145/3188745.3188938},
year = {2018},
}
Publisher's Version
Article: stoc18main-p376-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188938
|
| |
Neiman, Ofer |
STOC '18: "Metric Embedding via Shortest ..."
Metric Embedding via Shortest Path Decompositions
Ittai Abraham, Arnold Filtser, Anupam Gupta, and Ofer Neiman
(VMware, USA; Ben-Gurion University of the Negev, Israel; Carnegie Mellon University, USA)
@InProceedings{STOC18p1109,
author = {Ittai Abraham and Arnold Filtser and Anupam Gupta and Ofer Neiman},
title = {Metric Embedding via Shortest Path Decompositions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1109-1108},
doi = {10.1145/3188745.3188808},
year = {2018},
}
Publisher's Version
Article: stoc18main-p116-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188808
|
| |
Neuen, Daniel |
STOC '18: "An Exponential Lower Bound ..."
An Exponential Lower Bound for Individualization-Refinement Algorithms for Graph Isomorphism
Daniel Neuen and Pascal Schweitzer
(RWTH Aachen University, Germany; TU Kaiserslautern, Germany)
@InProceedings{STOC18p171,
author = {Daniel Neuen and Pascal Schweitzer},
title = {An Exponential Lower Bound for Individualization-Refinement Algorithms for Graph Isomorphism},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {171-170},
doi = {10.1145/3188745.3188900},
year = {2018},
}
Publisher's Version
Article: stoc18main-p286-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188900
|
| |
Nikolov, Aleksandar |
STOC '18: "Data-Dependent Hashing via ..."
Data-Dependent Hashing via Nonlinear Spectral Gaps
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten
(Columbia University, USA; Princeton University, USA; University of Toronto, Canada; Microsoft Research, USA)
@InProceedings{STOC18p913,
author = {Alexandr Andoni and Assaf Naor and Aleksandar Nikolov and Ilya Razenshteyn and Erik Waingarten},
title = {Data-Dependent Hashing via Nonlinear Spectral Gaps},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {913-912},
doi = {10.1145/3188745.3188846},
year = {2018},
}
Publisher's Version
Article: stoc18main-p189-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188846
|
| |
Nimavat, Rachit |
STOC '18: "Almost Polynomial Hardness ..."
Almost Polynomial Hardness of Node-Disjoint Paths in Grids
Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat
(Toyota Technological Institute at Chicago, USA; University of Chicago, USA)
@InProceedings{STOC18p1417,
author = {Julia Chuzhoy and David H. K. Kim and Rachit Nimavat},
title = {Almost Polynomial Hardness of Node-Disjoint Paths in Grids},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1417-1416},
doi = {10.1145/3188745.3188772},
year = {2018},
}
Publisher's Version
Article: stoc18main-p53-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188772
|
| |
Nordström, Jakob |
STOC '18: "Clique Is Hard on Average ..."
Clique Is Hard on Average for Regular Resolution
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, and Alexander Razborov
(Universitat Politècnica de Catalunya, Spain; KTH, Sweden; Sapienza University of Rome, Italy; University of Chicago, USA; Russian Academy of Sciences, Russia)
@InProceedings{STOC18p997,
author = {Albert Atserias and Ilario Bonacina and Susanna F. de Rezende and Massimo Lauria and Jakob Nordström and Alexander Razborov},
title = {Clique Is Hard on Average for Regular Resolution},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {997-996},
doi = {10.1145/3188745.3188856},
year = {2018},
}
Publisher's Version
Article: stoc18main-p211-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188856
|
| |
Nummenpalo, Jerri |
STOC '18: "Sparse Kneser Graphs Are Hamiltonian ..."
Sparse Kneser Graphs Are Hamiltonian
Torsten Mütze, Jerri Nummenpalo, and Bartosz Walczak
(TU Berlin, Germany; ETH Zurich, Switzerland; Jagiellonian University, Poland)
@InProceedings{STOC18p1053,
author = {Torsten Mütze and Jerri Nummenpalo and Bartosz Walczak},
title = {Sparse Kneser Graphs Are Hamiltonian},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1053-1052},
doi = {10.1145/3188745.3188834},
year = {2018},
}
Publisher's Version
Article: stoc18main-p166-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188834
|
| |
Oliveira, Rafael
|
STOC '18: "Operator Scaling via Geodesically ..."
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson
(Microsoft Research, USA; Princeton University, USA; University of Toronto, Canada; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC18p213,
author = {Zeyuan Allen-Zhu and Ankit Garg and Yuanzhi Li and Rafael Oliveira and Avi Wigderson},
title = {Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {213-212},
doi = {10.1145/3188745.3188942},
year = {2018},
}
Publisher's Version
Article: stoc18main-p382-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188942
|
| |
Olivetti, Dennis |
STOC '18: "New Classes of Distributed ..."
New Classes of Distributed Time Complexity
Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela
(Aalto University, Finland; University of Freiburg, Germany)
@InProceedings{STOC18p1529,
author = {Alkida Balliu and Juho Hirvonen and Janne H. Korhonen and Tuomo Lempiäinen and Dennis Olivetti and Jukka Suomela},
title = {New Classes of Distributed Time Complexity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1529-1528},
doi = {10.1145/3188745.3188860},
year = {2018},
}
Publisher's Version
Article: stoc18main-p220-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188860
|
| |
Omidvar, Hamed |
STOC '18: "Shape of Diffusion and Size ..."
Shape of Diffusion and Size of Monochromatic Region of a Two-Dimensional Spin System
Hamed Omidvar and Massimo Franceschetti
(University of California at San Diego, USA)
@InProceedings{STOC18p115,
author = {Hamed Omidvar and Massimo Franceschetti},
title = {Shape of Diffusion and Size of Monochromatic Region of a Two-Dimensional Spin System},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {115-114},
doi = {10.1145/3188745.3188836},
year = {2018},
}
Publisher's Version
Article: stoc18main-p167-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188836
|
| |
Onak, Krzysztof |
STOC '18: "The Query Complexity of Graph ..."
The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds
Krzysztof Onak and Xiaorui Sun
(IBM Research, USA; Microsoft Research, USA)
@InProceedings{STOC18p199,
author = {Krzysztof Onak and Xiaorui Sun},
title = {The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {199-198},
doi = {10.1145/3188745.3188952},
year = {2018},
}
Publisher's Version
Article: stoc18main-p404-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188952
STOC '18: "Round Compression for Parallel ..."
Round Compression for Parallel Matching Algorithms
Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski
(University of Warwick, UK; Google Research, USA; Massachusetts Institute of Technology, USA; EPFL, Switzerland; IBM Research, USA; University of Warsaw, Poland)
@InProceedings{STOC18p549,
author = {Artur Czumaj and Jakub Łącki and Aleksander Mądry and Slobodan Mitrović and Krzysztof Onak and Piotr Sankowski},
title = {Round Compression for Parallel Matching Algorithms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {549-548},
doi = {},
year = {2018},
}
Article: stoc18main-p15-p (type: Full Paper (14 pages)) doi:
STOC '18: "Fully Dynamic Maximal Independent ..."
Fully Dynamic Maximal Independent Set with Sublinear Update Time
Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon
(University of Pennsylvania, USA; IBM Research, USA)
@InProceedings{STOC18p941,
author = {Sepehr Assadi and Krzysztof Onak and Baruch Schieber and Shay Solomon},
title = {Fully Dynamic Maximal Independent Set with Sublinear Update Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {941-940},
doi = {10.1145/3188745.3188922},
year = {2018},
}
Publisher's Version
Article: stoc18main-p309-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188922
|
| |
Oppenheim, Izhar |
STOC '18: "Construction of New Local ..."
Construction of New Local Spectral High Dimensional Expanders
Tali Kaufman and Izhar Oppenheim
(Bar-Ilan University, Israel; Ben-Gurion University of the Negev, Israel)
@InProceedings{STOC18p899,
author = {Tali Kaufman and Izhar Oppenheim},
title = {Construction of New Local Spectral High Dimensional Expanders},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {899-898},
doi = {10.1145/3188745.3188782},
year = {2018},
}
Publisher's Version
Article: stoc18main-p70-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188782
|
| |
Paes Leme, Renato
|
STOC '18: "Stochastic Bandits Robust ..."
Stochastic Bandits Robust to Adversarial Corruptions
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme
(Cornell University, USA; Google Research, USA)
@InProceedings{STOC18p129,
author = {Thodoris Lykouris and Vahab Mirrokni and Renato Paes Leme},
title = {Stochastic Bandits Robust to Adversarial Corruptions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {129-128},
doi = {10.1145/3188745.3188918},
year = {2018},
}
Publisher's Version
Article: stoc18main-p304-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188918
|
| |
Paneth, Omer |
STOC '18: "Multi-collision Resistance: ..."
Multi-collision Resistance: A Paradigm for Keyless Hash Functions
Nir Bitansky, Yael Tauman Kalai, and Omer Paneth
(Tel Aviv University, Israel; Microsoft, USA; Massachusetts Institute of Technology, USA)
@InProceedings{STOC18p787,
author = {Nir Bitansky and Yael Tauman Kalai and Omer Paneth},
title = {Multi-collision Resistance: A Paradigm for Keyless Hash Functions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {787-786},
doi = {10.1145/3188745.3188870},
year = {2018},
}
Publisher's Version
Article: stoc18main-p236-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188870
|
| |
Panigrahi, Debmalya |
STOC '18: "Online Load Balancing on Related ..."
Online Load Balancing on Related Machines
Sungjin Im, Nathaniel Kell, Debmalya Panigrahi, and Maryam Shadloo
(University of California at Merced, USA; Duke University, USA)
@InProceedings{STOC18p31,
author = {Sungjin Im and Nathaniel Kell and Debmalya Panigrahi and Maryam Shadloo},
title = {Online Load Balancing on Related Machines},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {31-30},
doi = {10.1145/3188745.3188966},
year = {2018},
}
Publisher's Version
Article: stoc18main-p439-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188966
|
| |
Peng, Richard |
STOC '18: "Incomplete Nested Dissection ..."
Incomplete Nested Dissection
Rasmus Kyng, Richard Peng, Robert Schwieterman, and Peng Zhang
(Simons Institute for the Theory of Computing Berkeley, USA; Georgia Tech, USA)
@InProceedings{STOC18p479,
author = {Rasmus Kyng and Richard Peng and Robert Schwieterman and Peng Zhang},
title = {Incomplete Nested Dissection},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {479-478},
doi = {10.1145/3188745.3188960},
year = {2018},
}
Publisher's Version
Article: stoc18main-p429-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188960
|
| |
Pettie, Seth |
STOC '18: "An Optimal Distributed (Δ+1)-Coloring ..."
An Optimal Distributed (Δ+1)-Coloring Algorithm?
Yi-Jun Chang, Wenzheng Li, and Seth Pettie
(University of Michigan, USA; Tsinghua University, China)
@InProceedings{STOC18p521,
author = {Yi-Jun Chang and Wenzheng Li and Seth Pettie},
title = {An Optimal Distributed (Δ+1)-Coloring Algorithm?},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {521-520},
doi = {10.1145/3188745.3188964},
year = {2018},
}
Publisher's Version
Article: stoc18main-p436-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188964
|
| |
Pitassi, Toniann |
STOC '18: "Lifting Nullstellensatz to ..."
Lifting Nullstellensatz to Monotone Span Programs over Any Field
Toniann Pitassi and Robert Robere
(University of Toronto, Canada; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC18p1403,
author = {Toniann Pitassi and Robert Robere},
title = {Lifting Nullstellensatz to Monotone Span Programs over Any Field},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1403-1402},
doi = {10.1145/3188745.3188914},
year = {2018},
}
Publisher's Version
Article: stoc18main-p301-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188914
|
| |
Prezza, Nicola |
STOC '18: "At the Roots of Dictionary ..."
At the Roots of Dictionary Compression: String Attractors
Dominik Kempa and Nicola Prezza
(University of Helsinki, Finland; DTU, Denmark; University of Pisa, Italy)
@InProceedings{STOC18p955,
author = {Dominik Kempa and Nicola Prezza},
title = {At the Roots of Dictionary Compression: String Attractors},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {955-954},
doi = {10.1145/3188745.3188814},
year = {2018},
}
Publisher's Version
Article: stoc18main-p125-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188814
|
| |
Rademacher, Luis
|
STOC '18: "The Minimum Euclidean-Norm ..."
The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm Is Exponential
Jesús A. De Loera, Jamie Haddock, and Luis Rademacher
(University of California at Davis, USA)
@InProceedings{STOC18p633,
author = {Jesús A. De Loera and Jamie Haddock and Luis Rademacher},
title = {The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm Is Exponential},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {633-632},
doi = {},
year = {2018},
}
Article: stoc18main-p143-p (type: Full Paper (14 pages)) doi:
|
| |
Ramachandran, Akshay |
STOC '18: "The Paulsen Problem, Continuous ..."
The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, and Akshay Ramachandran
(University of Waterloo, Canada; University of Washington, USA)
@InProceedings{STOC18p227,
author = {Tsz Chiu Kwok and Lap Chi Lau and Yin Tat Lee and Akshay Ramachandran},
title = {The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {227-226},
doi = {10.1145/3188745.3188794},
year = {2018},
}
Publisher's Version
Article: stoc18main-p101-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188794
|
| |
Ramachandran, Vijaya |
STOC '18: "Fine-Grained Complexity for ..."
Fine-Grained Complexity for Sparse Graphs
Udit Agarwal and Vijaya Ramachandran
(University of Texas at Austin, USA)
@InProceedings{STOC18p297,
author = {Udit Agarwal and Vijaya Ramachandran},
title = {Fine-Grained Complexity for Sparse Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {297-296},
doi = {10.1145/3188745.3188888},
year = {2018},
}
Publisher's Version
Article: stoc18main-p268-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188888
|
| |
Raz, Ran |
STOC '18: "Extractor-Based Time-Space ..."
Extractor-Based Time-Space Lower Bounds for Learning
Sumegha Garg, Ran Raz, and Avishay Tal
(Princeton University, USA; Stanford University, USA)
@InProceedings{STOC18p1151,
author = {Sumegha Garg and Ran Raz and Avishay Tal},
title = {Extractor-Based Time-Space Lower Bounds for Learning},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1151-1150},
doi = {10.1145/3188745.3188962},
year = {2018},
}
Publisher's Version
Article: stoc18main-p430-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188962
|
| |
Razborov, Alexander |
STOC '18: "Clique Is Hard on Average ..."
Clique Is Hard on Average for Regular Resolution
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, and Alexander Razborov
(Universitat Politècnica de Catalunya, Spain; KTH, Sweden; Sapienza University of Rome, Italy; University of Chicago, USA; Russian Academy of Sciences, Russia)
@InProceedings{STOC18p997,
author = {Albert Atserias and Ilario Bonacina and Susanna F. de Rezende and Massimo Lauria and Jakob Nordström and Alexander Razborov},
title = {Clique Is Hard on Average for Regular Resolution},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {997-996},
doi = {10.1145/3188745.3188856},
year = {2018},
}
Publisher's Version
Article: stoc18main-p211-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188856
|
| |
Razenshteyn, Ilya |
STOC '18: "Nonlinear Dimension Reduction ..."
Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn
(Columbia University, USA; Northwestern University, USA; Toyota Technological Institute at Chicago, USA; Microsoft Research, USA)
@InProceedings{STOC18p1263,
author = {Sepideh Mahabadi and Konstantin Makarychev and Yury Makarychev and Ilya Razenshteyn},
title = {Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1263-1262},
doi = {10.1145/3188745.3188828},
year = {2018},
}
Publisher's Version
Article: stoc18main-p152-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188828
STOC '18: "Data-Dependent Hashing via ..."
Data-Dependent Hashing via Nonlinear Spectral Gaps
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten
(Columbia University, USA; Princeton University, USA; University of Toronto, Canada; Microsoft Research, USA)
@InProceedings{STOC18p913,
author = {Alexandr Andoni and Assaf Naor and Aleksandar Nikolov and Ilya Razenshteyn and Erik Waingarten},
title = {Data-Dependent Hashing via Nonlinear Spectral Gaps},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {913-912},
doi = {10.1145/3188745.3188846},
year = {2018},
}
Publisher's Version
Article: stoc18main-p189-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188846
|
| |
Recht, Benjamin |
STOC '18: "Tight Query Complexity Lower ..."
Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law
Max Simchowitz, Ahmed El Alaoui, and Benjamin Recht
(University of California at Berkeley, USA)
@InProceedings{STOC18p1459,
author = {Max Simchowitz and Ahmed El Alaoui and Benjamin Recht},
title = {Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1459-1458},
doi = {10.1145/3188745.3188796},
year = {2018},
}
Publisher's Version
Article: stoc18main-p106-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188796
|
| |
Reingold, Omer |
STOC '18: "Improved Pseudorandomness ..."
Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, and Avishay Tal
(Cornell University, USA; Institute for Advanced Study at Princeton, USA; University of Texas at Austin, USA; Stanford University, USA)
@InProceedings{STOC18p437,
author = {Eshan Chattopadhyay and Pooya Hatami and Omer Reingold and Avishay Tal},
title = {Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {437-436},
doi = {10.1145/3188745.3188800},
year = {2018},
}
Publisher's Version
Article: stoc18main-p112-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188800
|
| |
Robere, Robert |
STOC '18: "Lifting Nullstellensatz to ..."
Lifting Nullstellensatz to Monotone Span Programs over Any Field
Toniann Pitassi and Robert Robere
(University of Toronto, Canada; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC18p1403,
author = {Toniann Pitassi and Robert Robere},
title = {Lifting Nullstellensatz to Monotone Span Programs over Any Field},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1403-1402},
doi = {10.1145/3188745.3188914},
year = {2018},
}
Publisher's Version
Article: stoc18main-p301-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188914
|
| |
Roditty, Liam |
STOC '18: "Towards Tight Approximation ..."
Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein
(Massachusetts Institute of Technology, USA; Bar-Ilan University, Israel)
@InProceedings{STOC18p325,
author = {Arturs Backurs and Liam Roditty and Gilad Segal and Virginia Vassilevska Williams and Nicole Wein},
title = {Towards Tight Approximation Bounds for Graph Diameter and Eccentricities},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {325-324},
doi = {10.1145/3188745.3188950},
year = {2018},
}
Publisher's Version
Article: stoc18main-p403-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188950
|
| |
Ron, Dana |
STOC '18: "On Approximating the Number ..."
On Approximating the Number of k-Cliques in Sublinear Time
Talya Eden, Dana Ron, and C. Seshadhri
(Tel Aviv University, Israel; University of California at Santa Cruz, USA)
@InProceedings{STOC18p843,
author = {Talya Eden and Dana Ron and C. Seshadhri},
title = {On Approximating the Number of k-Cliques in Sublinear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {843-842},
doi = {10.1145/3188745.3188810},
year = {2018},
}
Publisher's Version
Article: stoc18main-p120-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188810
|
| |
Rotenberg, Eva |
STOC '18: "Fast Fencing ..."
Fast Fencing
Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, and Mikkel Thorup
(University of Copenhagen, Denmark; Max Planck Institute for Informatics, Germany; Sorbonne University, France; UPMC, France; CNRS, France; LIP6, France; Eindhoven University of Technology, Netherlands; DTU, Denmark)
@InProceedings{STOC18p661,
author = {Mikkel Abrahamsen and Anna Adamaszek and Karl Bringmann and Vincent Cohen-Addad and Mehran Mehr and Eva Rotenberg and Alan Roytman and Mikkel Thorup},
title = {Fast Fencing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {661-660},
doi = {10.1145/3188745.3188878},
year = {2018},
}
Publisher's Version
Article: stoc18main-p248-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188878
|
| |
Rothblum, Guy N. |
STOC '18: "Composable and Versatile Privacy ..."
Composable and Versatile Privacy via Truncated CDP
Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke
(Princeton University, USA; Harvard University, USA; Weizmann Institute of Science, Israel; IBM Research, USA)
@InProceedings{STOC18p87,
author = {Mark Bun and Cynthia Dwork and Guy N. Rothblum and Thomas Steinke},
title = {Composable and Versatile Privacy via Truncated CDP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {87-86},
doi = {10.1145/3188745.3188946},
year = {2018},
}
Publisher's Version
Article: stoc18main-p384-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188946
|
| |
Roytman, Alan |
STOC '18: "Fast Fencing ..."
Fast Fencing
Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, and Mikkel Thorup
(University of Copenhagen, Denmark; Max Planck Institute for Informatics, Germany; Sorbonne University, France; UPMC, France; CNRS, France; LIP6, France; Eindhoven University of Technology, Netherlands; DTU, Denmark)
@InProceedings{STOC18p661,
author = {Mikkel Abrahamsen and Anna Adamaszek and Karl Bringmann and Vincent Cohen-Addad and Mehran Mehr and Eva Rotenberg and Alan Roytman and Mikkel Thorup},
title = {Fast Fencing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {661-660},
doi = {10.1145/3188745.3188878},
year = {2018},
}
Publisher's Version
Article: stoc18main-p248-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188878
|
| |
Rubinstein, Aviad |
STOC '18: "Hardness of Approximate Nearest ..."
Hardness of Approximate Nearest Neighbor Search
Aviad Rubinstein
(Harvard University, USA)
@InProceedings{STOC18p1473,
author = {Aviad Rubinstein},
title = {Hardness of Approximate Nearest Neighbor Search},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1473-1472},
doi = {10.1145/3188745.3188916},
year = {2018},
}
Publisher's Version
Article: stoc18main-p302-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188916
|
| |
Rudra, Atri |
STOC '18: "General Strong Polarization ..."
General Strong Polarization
Jarosław Błasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, and Madhu Sudan
(Harvard University, USA; Carnegie Mellon University, USA; SUNY Buffalo, USA)
@InProceedings{STOC18p563,
author = {Jarosław Błasiok and Venkatesan Guruswami and Preetum Nakkiran and Atri Rudra and Madhu Sudan},
title = {General Strong Polarization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {563-562},
doi = {10.1145/3188745.3188816},
year = {2018},
}
Publisher's Version
Article: stoc18main-p140-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188816
|
| |
S., Karthik C.
|
STOC '18: "On the Parameterized Complexity ..."
On the Parameterized Complexity of Approximating Dominating Set
Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi
(Weizmann Institute of Science, Israel; Max Planck Institute for Informatics, Germany; Shanghai University of Finance and Economics, China; University of California at Berkeley, USA)
@InProceedings{STOC18p1501,
author = {Karthik C. S. and Bundit Laekhanukit and Pasin Manurangsi},
title = {On the Parameterized Complexity of Approximating Dominating Set},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1501-1500},
doi = {10.1145/3188745.3188896},
year = {2018},
}
Publisher's Version
Article: stoc18main-p281-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188896
|
| |
Safra, Muli |
STOC '18: "On Non-optimally Expanding ..."
On Non-optimally Expanding Sets in Grassmann Graphs
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra
(Weizmann Institute of Science, Israel; New York University, USA; Hebrew University of Jerusalem, Israel; Tel Aviv University, Israel)
@InProceedings{STOC18p1095,
author = {Irit Dinur and Subhash Khot and Guy Kindler and Dor Minzer and Muli Safra},
title = {On Non-optimally Expanding Sets in Grassmann Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1095-1094},
doi = {10.1145/3188745.3188806},
year = {2018},
}
Publisher's Version
Article: stoc18main-p115-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188806
STOC '18: "Towards a Proof of the 2-to-1 ..."
Towards a Proof of the 2-to-1 Games Conjecture?
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra
(Weizmann Institute of Science, Israel; New York University, USA; Hebrew University of Jerusalem, Israel; Tel Aviv University, Israel)
@InProceedings{STOC18p451,
author = {Irit Dinur and Subhash Khot and Guy Kindler and Dor Minzer and Muli Safra},
title = {Towards a Proof of the 2-to-1 Games Conjecture?},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {451-450},
doi = {10.1145/3188745.3188804},
year = {2018},
}
Publisher's Version
Article: stoc18main-p114-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188804
|
| |
Sahai, Amit |
STOC '18: "Succinct Delegation for Low-Space ..."
Succinct Delegation for Low-Space Non-deterministic Computation
Saikrishna Badrinarayanan, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai, and Daniel Wichs
(University of California at Los Angeles, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA; Northeastern University, USA)
@InProceedings{STOC18p829,
author = {Saikrishna Badrinarayanan and Yael Tauman Kalai and Dakshita Khurana and Amit Sahai and Daniel Wichs},
title = {Succinct Delegation for Low-Space Non-deterministic Computation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {829-828},
doi = {10.1145/3188745.3188924},
year = {2018},
}
Publisher's Version
Article: stoc18main-p312-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188924
|
| |
Sandeep, Sai |
STOC '18: "Constant Approximation for ..."
Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding
Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep
(Microsoft Research, India; SUNY Buffalo, USA)
@InProceedings{STOC18p759,
author = {Ravishankar Krishnaswamy and Shi Li and Sai Sandeep},
title = {Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {759-758},
doi = {10.1145/3188745.3188882},
year = {2018},
}
Publisher's Version
Article: stoc18main-p260-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188882
|
| |
Sankowski, Piotr |
STOC '18: "Round Compression for Parallel ..."
Round Compression for Parallel Matching Algorithms
Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski
(University of Warwick, UK; Google Research, USA; Massachusetts Institute of Technology, USA; EPFL, Switzerland; IBM Research, USA; University of Warsaw, Poland)
@InProceedings{STOC18p549,
author = {Artur Czumaj and Jakub Łącki and Aleksander Mądry and Slobodan Mitrović and Krzysztof Onak and Piotr Sankowski},
title = {Round Compression for Parallel Matching Algorithms},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {549-548},
doi = {},
year = {2018},
}
Article: stoc18main-p15-p (type: Full Paper (14 pages)) doi:
|
| |
Saranurak, Thatchaphol |
STOC '18: "Smooth Heaps and a Dual View ..."
Smooth Heaps and a Dual View of Self-Adjusting Data Structures
László Kozma and Thatchaphol Saranurak
(Eindhoven University of Technology, Netherlands; KTH, Sweden)
@InProceedings{STOC18p927,
author = {László Kozma and Thatchaphol Saranurak},
title = {Smooth Heaps and a Dual View of Self-Adjusting Data Structures},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {927-926},
doi = {10.1145/3188745.3188864},
year = {2018},
}
Publisher's Version
Article: stoc18main-p225-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188864
|
| |
Saxena, Nitin |
STOC '18: "Discovering the Roots: Uniform ..."
Discovering the Roots: Uniform Closure Results for Algebraic Classes under Factoring
Pranjal Dutta, Nitin Saxena, and Amit Sinhababu
(Chennai Mathematical Institute, India; IIT Kanpur, India)
@InProceedings{STOC18p1347,
author = {Pranjal Dutta and Nitin Saxena and Amit Sinhababu},
title = {Discovering the Roots: Uniform Closure Results for Algebraic Classes under Factoring},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1347-1346},
doi = {10.1145/3188745.3188760},
year = {2018},
}
Publisher's Version
Article: stoc18main-p13-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188760
STOC '18: "Bootstrapping Variables in ..."
Bootstrapping Variables in Algebraic Circuits
Manindra Agrawal, Sumanta Ghosh, and Nitin Saxena
(IIT Kanpur, India)
@InProceedings{STOC18p1361,
author = {Manindra Agrawal and Sumanta Ghosh and Nitin Saxena},
title = {Bootstrapping Variables in Algebraic Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1361-1360},
doi = {10.1145/3188745.3188762},
year = {2018},
}
Publisher's Version
Article: stoc18main-p14-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188762
|
| |
Saxena, Raghuvansh |
STOC '18: "Interactive Coding over the ..."
Interactive Coding over the Noisy Broadcast Channel
Klim Efremenko, Gillat Kol, and Raghuvansh Saxena
(Ben-Gurion University of the Negev, Israel; Princeton University, USA)
@InProceedings{STOC18p591,
author = {Klim Efremenko and Gillat Kol and Raghuvansh Saxena},
title = {Interactive Coding over the Noisy Broadcast Channel},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {591-590},
doi = {10.1145/3188745.3188884},
year = {2018},
}
Publisher's Version
Article: stoc18main-p262-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188884
|
| |
Schieber, Baruch |
STOC '18: "Fully Dynamic Maximal Independent ..."
Fully Dynamic Maximal Independent Set with Sublinear Update Time
Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon
(University of Pennsylvania, USA; IBM Research, USA)
@InProceedings{STOC18p941,
author = {Sepehr Assadi and Krzysztof Onak and Baruch Schieber and Shay Solomon},
title = {Fully Dynamic Maximal Independent Set with Sublinear Update Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {941-940},
doi = {10.1145/3188745.3188922},
year = {2018},
}
Publisher's Version
Article: stoc18main-p309-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188922
|
| |
Schild, Aaron |
STOC '18: "An Almost-Linear Time Algorithm ..."
An Almost-Linear Time Algorithm for Uniform Random Spanning Tree Generation
Aaron Schild
(University of California at Berkeley, USA)
@InProceedings{STOC18p269,
author = {Aaron Schild},
title = {An Almost-Linear Time Algorithm for Uniform Random Spanning Tree Generation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {269-268},
doi = {10.1145/3188745.3188852},
year = {2018},
}
Publisher's Version
Article: stoc18main-p201-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188852
|
| |
Schulman, Leonard J. |
STOC '18: "Explicit Binary Tree Codes ..."
Explicit Binary Tree Codes with Polylogarithmic Size Alphabet
Gil Cohen, Bernhard Haeupler, and Leonard J. Schulman
(Princeton University, USA; Carnegie Mellon University, USA; California Institute of Technology, USA)
@InProceedings{STOC18p619,
author = {Gil Cohen and Bernhard Haeupler and Leonard J. Schulman},
title = {Explicit Binary Tree Codes with Polylogarithmic Size Alphabet},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {619-618},
doi = {10.1145/3188745.3188928},
year = {2018},
}
Publisher's Version
Article: stoc18main-p326-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188928
|
| |
Schweitzer, Pascal |
STOC '18: "An Exponential Lower Bound ..."
An Exponential Lower Bound for Individualization-Refinement Algorithms for Graph Isomorphism
Daniel Neuen and Pascal Schweitzer
(RWTH Aachen University, Germany; TU Kaiserslautern, Germany)
@InProceedings{STOC18p171,
author = {Daniel Neuen and Pascal Schweitzer},
title = {An Exponential Lower Bound for Individualization-Refinement Algorithms for Graph Isomorphism},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {171-170},
doi = {10.1145/3188745.3188900},
year = {2018},
}
Publisher's Version
Article: stoc18main-p286-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188900
|
| |
Schwieterman, Robert |
STOC '18: "Incomplete Nested Dissection ..."
Incomplete Nested Dissection
Rasmus Kyng, Richard Peng, Robert Schwieterman, and Peng Zhang
(Simons Institute for the Theory of Computing Berkeley, USA; Georgia Tech, USA)
@InProceedings{STOC18p479,
author = {Rasmus Kyng and Richard Peng and Robert Schwieterman and Peng Zhang},
title = {Incomplete Nested Dissection},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {479-478},
doi = {10.1145/3188745.3188960},
year = {2018},
}
Publisher's Version
Article: stoc18main-p429-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188960
|
| |
Seddighin, Saeed |
STOC '18: "Fast Algorithms for Knapsack ..."
Fast Algorithms for Knapsack via Convolution and Prediction
MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Saeed Seddighin, and Cliff Stein
(Google, USA; University of Maryland, USA; Columbia University, USA)
@InProceedings{STOC18p1487,
author = {MohammadHossein Bateni and MohammadTaghi Hajiaghayi and Saeed Seddighin and Cliff Stein},
title = {Fast Algorithms for Knapsack via Convolution and Prediction},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1487-1486},
doi = {10.1145/3188745.3188876},
year = {2018},
}
Publisher's Version
Article: stoc18main-p247-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188876
|
| |
Segal, Gilad |
STOC '18: "Towards Tight Approximation ..."
Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein
(Massachusetts Institute of Technology, USA; Bar-Ilan University, Israel)
@InProceedings{STOC18p325,
author = {Arturs Backurs and Liam Roditty and Gilad Segal and Virginia Vassilevska Williams and Nicole Wein},
title = {Towards Tight Approximation Bounds for Graph Diameter and Eccentricities},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {325-324},
doi = {10.1145/3188745.3188950},
year = {2018},
}
Publisher's Version
Article: stoc18main-p403-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188950
|
| |
Servedio, Rocco A. |
STOC '18: "Distribution-Free Junta Testing ..."
Distribution-Free Junta Testing
Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, and Jinyu Xie
(Shanghai Jiao Tong University, China; Columbia University, USA)
@InProceedings{STOC18p871,
author = {Zhengyang Liu and Xi Chen and Rocco A. Servedio and Ying Sheng and Jinyu Xie},
title = {Distribution-Free Junta Testing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {871-870},
doi = {10.1145/3188745.3188842},
year = {2018},
}
Publisher's Version
Article: stoc18main-p186-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188842
|
| |
Seshadhri, C. |
STOC '18: "On Approximating the Number ..."
On Approximating the Number of k-Cliques in Sublinear Time
Talya Eden, Dana Ron, and C. Seshadhri
(Tel Aviv University, Israel; University of California at Santa Cruz, USA)
@InProceedings{STOC18p843,
author = {Talya Eden and Dana Ron and C. Seshadhri},
title = {On Approximating the Number of k-Cliques in Sublinear Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {843-842},
doi = {10.1145/3188745.3188810},
year = {2018},
}
Publisher's Version
Article: stoc18main-p120-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188810
|
| |
Shadloo, Maryam |
STOC '18: "Online Load Balancing on Related ..."
Online Load Balancing on Related Machines
Sungjin Im, Nathaniel Kell, Debmalya Panigrahi, and Maryam Shadloo
(University of California at Merced, USA; Duke University, USA)
@InProceedings{STOC18p31,
author = {Sungjin Im and Nathaniel Kell and Debmalya Panigrahi and Maryam Shadloo},
title = {Online Load Balancing on Related Machines},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {31-30},
doi = {10.1145/3188745.3188966},
year = {2018},
}
Publisher's Version
Article: stoc18main-p439-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188966
|
| |
Shahrasbi, Amirbehshad |
STOC '18: "Synchronization Strings: Explicit ..."
Synchronization Strings: Explicit Constructions, Local Decoding, and Applications
Bernhard Haeupler and Amirbehshad Shahrasbi
(Carnegie Mellon University, USA)
@InProceedings{STOC18p969,
author = {Bernhard Haeupler and Amirbehshad Shahrasbi},
title = {Synchronization Strings: Explicit Constructions, Local Decoding, and Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {969-968},
doi = {10.1145/3188745.3188940},
year = {2018},
}
Publisher's Version
Article: stoc18main-p379-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188940
|
| |
Shapira, Asaf |
STOC '18: "A Generalized Turán Problem ..."
A Generalized Turán Problem and Its Applications
Lior Gishboliner and Asaf Shapira
(Tel Aviv University, Israel)
@InProceedings{STOC18p885,
author = {Lior Gishboliner and Asaf Shapira},
title = {A Generalized Turán Problem and Its Applications},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {885-884},
doi = {10.1145/3188745.3188778},
year = {2018},
}
Publisher's Version
Article: stoc18main-p63-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188778
|
| |
Sharan, Vatsal |
STOC '18: "Prediction with a Short Memory ..."
Prediction with a Short Memory
Vatsal Sharan, Sham Kakade, Percy Liang, and Gregory Valiant
(Stanford University, USA; University of Washington, USA)
@InProceedings{STOC18p1249,
author = {Vatsal Sharan and Sham Kakade and Percy Liang and Gregory Valiant},
title = {Prediction with a Short Memory},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1249-1248},
doi = {10.1145/3188745.3188954},
year = {2018},
}
Publisher's Version
Article: stoc18main-p410-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188954
|
| |
Shayeghi, Ala |
STOC '18: "Capacity Approaching Coding ..."
Capacity Approaching Coding for Low Noise Interactive Quantum Communication
Debbie Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, and Nengkun Yu
(University of Waterloo, Canada; Perimeter Institute Waterloo, Canada; Nanjing University, China; University of Technology Sydney, Australia)
@InProceedings{STOC18p409,
author = {Debbie Leung and Ashwin Nayak and Ala Shayeghi and Dave Touchette and Penghui Yao and Nengkun Yu},
title = {Capacity Approaching Coding for Low Noise Interactive Quantum Communication},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {409-408},
doi = {10.1145/3188745.3188908},
year = {2018},
}
Publisher's Version
Article: stoc18main-p294-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188908
|
| |
Sheng, Ying |
STOC '18: "Distribution-Free Junta Testing ..."
Distribution-Free Junta Testing
Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, and Jinyu Xie
(Shanghai Jiao Tong University, China; Columbia University, USA)
@InProceedings{STOC18p871,
author = {Zhengyang Liu and Xi Chen and Rocco A. Servedio and Ying Sheng and Jinyu Xie},
title = {Distribution-Free Junta Testing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {871-870},
doi = {10.1145/3188745.3188842},
year = {2018},
}
Publisher's Version
Article: stoc18main-p186-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188842
|
| |
Sherstov, Alexander A. |
STOC '18: "Algorithmic Polynomials ..."
Algorithmic Polynomials
Alexander A. Sherstov
(University of California at Los Angeles, USA)
@InProceedings{STOC18p381,
author = {Alexander A. Sherstov},
title = {Algorithmic Polynomials},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {381-380},
doi = {10.1145/3188745.3188958},
year = {2018},
}
Publisher's Version
Article: stoc18main-p427-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188958
|
| |
Shi, Yangguang |
STOC '18: "Approximating Generalized ..."
Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency
Yuval Emek, Shay Kutten, Ron Lavi, and Yangguang Shi
(Technion, Israel)
@InProceedings{STOC18p703,
author = {Yuval Emek and Shay Kutten and Ron Lavi and Yangguang Shi},
title = {Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {703-702},
doi = {10.1145/3188745.3188812},
year = {2018},
}
Publisher's Version
Article: stoc18main-p121-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188812
|
| |
Shpilka, Amir |
STOC '18: "A PSPACE Construction of a ..."
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits
Michael A. Forbes and Amir Shpilka
(University of Illinois at Urbana-Champaign, USA; Tel Aviv University, Israel)
@InProceedings{STOC18p1375,
author = {Michael A. Forbes and Amir Shpilka},
title = {A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1375-1374},
doi = {10.1145/3188745.3188792},
year = {2018},
}
Publisher's Version
Article: stoc18main-p98-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188792
|
| |
Simchowitz, Max |
STOC '18: "Tight Query Complexity Lower ..."
Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law
Max Simchowitz, Ahmed El Alaoui, and Benjamin Recht
(University of California at Berkeley, USA)
@InProceedings{STOC18p1459,
author = {Max Simchowitz and Ahmed El Alaoui and Benjamin Recht},
title = {Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1459-1458},
doi = {10.1145/3188745.3188796},
year = {2018},
}
Publisher's Version
Article: stoc18main-p106-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188796
|
| |
Singer, Yaron |
STOC '18: "The Adaptive Complexity of ..."
The Adaptive Complexity of Maximizing a Submodular Function
Eric Balkanski and Yaron Singer
(Harvard University, USA)
@InProceedings{STOC18p1333,
author = {Eric Balkanski and Yaron Singer},
title = {The Adaptive Complexity of Maximizing a Submodular Function},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1333-1332},
doi = {10.1145/3188745.3188752},
year = {2018},
}
Publisher's Version
Article: stoc18main-p8-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188752
|
| |
Sinhababu, Amit |
STOC '18: "Discovering the Roots: Uniform ..."
Discovering the Roots: Uniform Closure Results for Algebraic Classes under Factoring
Pranjal Dutta, Nitin Saxena, and Amit Sinhababu
(Chennai Mathematical Institute, India; IIT Kanpur, India)
@InProceedings{STOC18p1347,
author = {Pranjal Dutta and Nitin Saxena and Amit Sinhababu},
title = {Discovering the Roots: Uniform Closure Results for Algebraic Classes under Factoring},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1347-1346},
doi = {10.1145/3188745.3188760},
year = {2018},
}
Publisher's Version
Article: stoc18main-p13-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188760
|
| |
Sokolov, Dmitry |
STOC '18: "Monotone Circuit Lower Bounds ..."
Monotone Circuit Lower Bounds from Resolution
Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov
(Microsoft Research, USA; Harvard University, USA; Massachusetts Institute of Technology, USA; KTH, Sweden)
@InProceedings{STOC18p1039,
author = {Ankit Garg and Mika Göös and Pritish Kamath and Dmitry Sokolov},
title = {Monotone Circuit Lower Bounds from Resolution},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1039-1038},
doi = {10.1145/3188745.3188838},
year = {2018},
}
Publisher's Version
Article: stoc18main-p179-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188838
|
| |
Solomon, Shay |
STOC '18: "Fully Dynamic Maximal Independent ..."
Fully Dynamic Maximal Independent Set with Sublinear Update Time
Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon
(University of Pennsylvania, USA; IBM Research, USA)
@InProceedings{STOC18p941,
author = {Sepehr Assadi and Krzysztof Onak and Baruch Schieber and Shay Solomon},
title = {Fully Dynamic Maximal Independent Set with Sublinear Update Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {941-940},
doi = {10.1145/3188745.3188922},
year = {2018},
}
Publisher's Version
Article: stoc18main-p309-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188922
|
| |
Song, Zhao |
STOC '18: "A Matrix Expander Chernoff ..."
A Matrix Expander Chernoff Bound
Ankit Garg, Yin Tat Lee, Zhao Song, and Nikhil Srivastava
(Microsoft Research, USA; University of Washington, USA; Harvard University, USA; University of Texas at Austin, USA; University of California at Berkeley, USA)
@InProceedings{STOC18p1277,
author = {Ankit Garg and Yin Tat Lee and Zhao Song and Nikhil Srivastava},
title = {A Matrix Expander Chernoff Bound},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1277-1276},
doi = {10.1145/3188745.3188890},
year = {2018},
}
Publisher's Version
Article: stoc18main-p275-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188890
|
| |
Sornat, Krzysztof |
STOC '18: "Constant-Factor Approximation ..."
Constant-Factor Approximation for Ordered k-Median
Jarosław Byrka, Krzysztof Sornat, and Joachim Spoerhase
(University of Wrocław, Poland)
@InProceedings{STOC18p731,
author = {Jarosław Byrka and Krzysztof Sornat and Joachim Spoerhase},
title = {Constant-Factor Approximation for Ordered k-Median},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {731-730},
doi = {10.1145/3188745.3188930},
year = {2018},
}
Publisher's Version
Article: stoc18main-p338-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188930
|
| |
Spoerhase, Joachim |
STOC '18: "Constant-Factor Approximation ..."
Constant-Factor Approximation for Ordered k-Median
Jarosław Byrka, Krzysztof Sornat, and Joachim Spoerhase
(University of Wrocław, Poland)
@InProceedings{STOC18p731,
author = {Jarosław Byrka and Krzysztof Sornat and Joachim Spoerhase},
title = {Constant-Factor Approximation for Ordered k-Median},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {731-730},
doi = {10.1145/3188745.3188930},
year = {2018},
}
Publisher's Version
Article: stoc18main-p338-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188930
|
| |
Sreenivasaiah, Karteek |
STOC '18: "On the Complexity of Hazard-Free ..."
On the Complexity of Hazard-Free Circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, and Karteek Sreenivasaiah
(Max Planck Institute for Informatics, Germany; Saarland University, Germany; M2CI, Germany; Newcastle University, UK; IIT Hyderabad, India)
@InProceedings{STOC18p1011,
author = {Christian Ikenmeyer and Balagopal Komarath and Christoph Lenzen and Vladimir Lysikov and Andrey Mokhov and Karteek Sreenivasaiah},
title = {On the Complexity of Hazard-Free Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1011-1010},
doi = {10.1145/3188745.3188912},
year = {2018},
}
Publisher's Version
Article: stoc18main-p297-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188912
|
| |
Srivastava, Nikhil |
STOC '18: "A Matrix Expander Chernoff ..."
A Matrix Expander Chernoff Bound
Ankit Garg, Yin Tat Lee, Zhao Song, and Nikhil Srivastava
(Microsoft Research, USA; University of Washington, USA; Harvard University, USA; University of Texas at Austin, USA; University of California at Berkeley, USA)
@InProceedings{STOC18p1277,
author = {Ankit Garg and Yin Tat Lee and Zhao Song and Nikhil Srivastava},
title = {A Matrix Expander Chernoff Bound},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1277-1276},
doi = {10.1145/3188745.3188890},
year = {2018},
}
Publisher's Version
Article: stoc18main-p275-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188890
|
| |
Štefankovič, Daniel |
STOC '18: "Inapproximability of the Independent ..."
Inapproximability of the Independent Set Polynomial in the Complex Plane
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič
(Rochester Institute of Technology, USA; University of Oxford, UK; University of Rochester, USA)
@InProceedings{STOC18p1431,
author = {Ivona Bezáková and Andreas Galanis and Leslie Ann Goldberg and Daniel Štefankovič},
title = {Inapproximability of the Independent Set Polynomial in the Complex Plane},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1431-1430},
doi = {10.1145/3188745.3188788},
year = {2018},
}
Publisher's Version
Article: stoc18main-p77-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188788
|
| |
Stein, Cliff |
STOC '18: "Fast Algorithms for Knapsack ..."
Fast Algorithms for Knapsack via Convolution and Prediction
MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Saeed Seddighin, and Cliff Stein
(Google, USA; University of Maryland, USA; Columbia University, USA)
@InProceedings{STOC18p1487,
author = {MohammadHossein Bateni and MohammadTaghi Hajiaghayi and Saeed Seddighin and Cliff Stein},
title = {Fast Algorithms for Knapsack via Convolution and Prediction},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1487-1486},
doi = {10.1145/3188745.3188876},
year = {2018},
}
Publisher's Version
Article: stoc18main-p247-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188876
|
| |
Steinhardt, Jacob |
STOC '18: "Robust Moment Estimation and ..."
Robust Moment Estimation and Improved Clustering via Sum of Squares
Pravesh K. Kothari, Jacob Steinhardt, and David Steurer
(Princeton University, USA; Institute for Advanced Study at Princeton, USA; Stanford University, USA; ETH Zurich, Switzerland)
@InProceedings{STOC18p1207,
author = {Pravesh K. Kothari and Jacob Steinhardt and David Steurer},
title = {Robust Moment Estimation and Improved Clustering via Sum of Squares},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1207-1206},
doi = {10.1145/3188745.3188970},
year = {2018},
}
Publisher's Version
Article: stoc18main-p444-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188970
|
| |
Steinke, Thomas |
STOC '18: "Composable and Versatile Privacy ..."
Composable and Versatile Privacy via Truncated CDP
Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke
(Princeton University, USA; Harvard University, USA; Weizmann Institute of Science, Israel; IBM Research, USA)
@InProceedings{STOC18p87,
author = {Mark Bun and Cynthia Dwork and Guy N. Rothblum and Thomas Steinke},
title = {Composable and Versatile Privacy via Truncated CDP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {87-86},
doi = {10.1145/3188745.3188946},
year = {2018},
}
Publisher's Version
Article: stoc18main-p384-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188946
|
| |
Stephens-Davidowitz, Noah |
STOC '18: "(Gap/S)ETH Hardness of SVP ..."
(Gap/S)ETH Hardness of SVP
Divesh Aggarwal and Noah Stephens-Davidowitz
(National University of Singapore, Singapore; Princeton University, USA)
@InProceedings{STOC18p283,
author = {Divesh Aggarwal and Noah Stephens-Davidowitz},
title = {(Gap/S)ETH Hardness of SVP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {283-282},
doi = {10.1145/3188745.3188840},
year = {2018},
}
Publisher's Version
Article: stoc18main-p183-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188840
|
| |
Steurer, David |
STOC '18: "Robust Moment Estimation and ..."
Robust Moment Estimation and Improved Clustering via Sum of Squares
Pravesh K. Kothari, Jacob Steinhardt, and David Steurer
(Princeton University, USA; Institute for Advanced Study at Princeton, USA; Stanford University, USA; ETH Zurich, Switzerland)
@InProceedings{STOC18p1207,
author = {Pravesh K. Kothari and Jacob Steinhardt and David Steurer},
title = {Robust Moment Estimation and Improved Clustering via Sum of Squares},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1207-1206},
doi = {10.1145/3188745.3188970},
year = {2018},
}
Publisher's Version
Article: stoc18main-p444-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188970
|
| |
Stewart, Alistair |
STOC '18: "List-Decodable Robust Mean ..."
List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart
(University of Southern California, USA; University of California at San Diego, USA)
@InProceedings{STOC18p1221,
author = {Ilias Diakonikolas and Daniel M. Kane and Alistair Stewart},
title = {List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1221-1220},
doi = {10.1145/3188745.3188758},
year = {2018},
}
Publisher's Version
Article: stoc18main-p12-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188758
STOC '18: "Learning Geometric Concepts ..."
Learning Geometric Concepts with Nasty Noise
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart
(University of Southern California, USA; University of California at San Diego, USA)
@InProceedings{STOC18p1235,
author = {Ilias Diakonikolas and Daniel M. Kane and Alistair Stewart},
title = {Learning Geometric Concepts with Nasty Noise},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1235-1234},
doi = {10.1145/3188745.3188754},
year = {2018},
}
Publisher's Version
Article: stoc18main-p10-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188754
STOC '18: "Testing Conditional Independence ..."
Testing Conditional Independence of Discrete Distributions
Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart
(Stanford University, USA; University of Southern California, USA; University of California at San Diego, USA)
@InProceedings{STOC18p857,
author = {Clément L. Canonne and Ilias Diakonikolas and Daniel M. Kane and Alistair Stewart},
title = {Testing Conditional Independence of Discrete Distributions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {857-856},
doi = {10.1145/3188745.3188756},
year = {2018},
}
Publisher's Version
Article: stoc18main-p11-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188756
|
| |
Sudan, Madhu |
STOC '18: "General Strong Polarization ..."
General Strong Polarization
Jarosław Błasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, and Madhu Sudan
(Harvard University, USA; Carnegie Mellon University, USA; SUNY Buffalo, USA)
@InProceedings{STOC18p563,
author = {Jarosław Błasiok and Venkatesan Guruswami and Preetum Nakkiran and Atri Rudra and Madhu Sudan},
title = {General Strong Polarization},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {563-562},
doi = {10.1145/3188745.3188816},
year = {2018},
}
Publisher's Version
Article: stoc18main-p140-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188816
|
| |
Sun, Xiaorui |
STOC '18: "The Query Complexity of Graph ..."
The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds
Krzysztof Onak and Xiaorui Sun
(IBM Research, USA; Microsoft Research, USA)
@InProceedings{STOC18p199,
author = {Krzysztof Onak and Xiaorui Sun},
title = {The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {199-198},
doi = {10.1145/3188745.3188952},
year = {2018},
}
Publisher's Version
Article: stoc18main-p404-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188952
|
| |
Suomela, Jukka |
STOC '18: "New Classes of Distributed ..."
New Classes of Distributed Time Complexity
Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela
(Aalto University, Finland; University of Freiburg, Germany)
@InProceedings{STOC18p1529,
author = {Alkida Balliu and Juho Hirvonen and Janne H. Korhonen and Tuomo Lempiäinen and Dennis Olivetti and Jukka Suomela},
title = {New Classes of Distributed Time Complexity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1529-1528},
doi = {10.1145/3188745.3188860},
year = {2018},
}
Publisher's Version
Article: stoc18main-p220-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188860
|
| |
Svensson, Ola |
STOC '18: "A Constant-Factor Approximation ..."
A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
Ola Svensson, Jakub Tarnawski, and László A. Végh
(EPFL, Switzerland; London School of Economics, UK)
@InProceedings{STOC18p255,
author = {Ola Svensson and Jakub Tarnawski and László A. Végh},
title = {A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {255-254},
doi = {10.1145/3188745.3188824},
year = {2018},
}
Publisher's Version
Article: stoc18main-p150-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188824
|
| |
Taggart, Samuel
|
STOC '18: "A Tighter Welfare Guarantee ..."
A Tighter Welfare Guarantee for First-Price Auctions
Darrell Hoy, Samuel Taggart, and Zihe Wang
(Tremor Technologies, USA; Oberlin College, USA; Shanghai University of Finance and Economics, China)
@InProceedings{STOC18p157,
author = {Darrell Hoy and Samuel Taggart and Zihe Wang},
title = {A Tighter Welfare Guarantee for First-Price Auctions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {157-156},
doi = {10.1145/3188745.3188944},
year = {2018},
}
Publisher's Version
Article: stoc18main-p383-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188944
|
| |
Tal, Avishay |
STOC '18: "Extractor-Based Time-Space ..."
Extractor-Based Time-Space Lower Bounds for Learning
Sumegha Garg, Ran Raz, and Avishay Tal
(Princeton University, USA; Stanford University, USA)
@InProceedings{STOC18p1151,
author = {Sumegha Garg and Ran Raz and Avishay Tal},
title = {Extractor-Based Time-Space Lower Bounds for Learning},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1151-1150},
doi = {10.1145/3188745.3188962},
year = {2018},
}
Publisher's Version
Article: stoc18main-p430-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188962
STOC '18: "Improved Pseudorandomness ..."
Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, and Avishay Tal
(Cornell University, USA; Institute for Advanced Study at Princeton, USA; University of Texas at Austin, USA; Stanford University, USA)
@InProceedings{STOC18p437,
author = {Eshan Chattopadhyay and Pooya Hatami and Omer Reingold and Avishay Tal},
title = {Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {437-436},
doi = {10.1145/3188745.3188800},
year = {2018},
}
Publisher's Version
Article: stoc18main-p112-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188800
|
| |
Tang, Zhihao Gavin |
STOC '18: "How to Match When All Vertices ..."
How to Match When All Vertices Arrive Online
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu
(University of Hong Kong, China)
@InProceedings{STOC18p17,
author = {Zhiyi Huang and Ning Kang and Zhihao Gavin Tang and Xiaowei Wu and Yuhao Zhang and Xue Zhu},
title = {How to Match When All Vertices Arrive Online},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {17-16},
doi = {10.1145/3188745.3188858},
year = {2018},
}
Publisher's Version
Article: stoc18main-p214-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188858
|
| |
Tarnawski, Jakub |
STOC '18: "A Constant-Factor Approximation ..."
A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
Ola Svensson, Jakub Tarnawski, and László A. Végh
(EPFL, Switzerland; London School of Economics, UK)
@InProceedings{STOC18p255,
author = {Ola Svensson and Jakub Tarnawski and László A. Végh},
title = {A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {255-254},
doi = {10.1145/3188745.3188824},
year = {2018},
}
Publisher's Version
Article: stoc18main-p150-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188824
|
| |
Tell, Roei |
STOC '18: "Quantified Derandomization ..."
Quantified Derandomization of Linear Threshold Circuits
Roei Tell
(Weizmann Institute of Science, Israel)
@InProceedings{STOC18p983,
author = {Roei Tell},
title = {Quantified Derandomization of Linear Threshold Circuits},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {983-982},
doi = {10.1145/3188745.3188822},
year = {2018},
}
Publisher's Version
Article: stoc18main-p147-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188822
|
| |
Thaler, Justin |
STOC '18: "The Polynomial Method Strikes ..."
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
Mark Bun, Robin Kothari, and Justin Thaler
(Princeton University, USA; Microsoft Research, USA; Georgetown University, USA)
@InProceedings{STOC18p367,
author = {Mark Bun and Robin Kothari and Justin Thaler},
title = {The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {367-366},
doi = {10.1145/3188745.3188784},
year = {2018},
}
Publisher's Version
Article: stoc18main-p75-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188784
|
| |
Thorup, Mikkel |
STOC '18: "Fast Fencing ..."
Fast Fencing
Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, and Mikkel Thorup
(University of Copenhagen, Denmark; Max Planck Institute for Informatics, Germany; Sorbonne University, France; UPMC, France; CNRS, France; LIP6, France; Eindhoven University of Technology, Netherlands; DTU, Denmark)
@InProceedings{STOC18p661,
author = {Mikkel Abrahamsen and Anna Adamaszek and Karl Bringmann and Vincent Cohen-Addad and Mehran Mehr and Eva Rotenberg and Alan Roytman and Mikkel Thorup},
title = {Fast Fencing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {661-660},
doi = {10.1145/3188745.3188878},
year = {2018},
}
Publisher's Version
Article: stoc18main-p248-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188878
|
| |
Touchette, Dave |
STOC '18: "Capacity Approaching Coding ..."
Capacity Approaching Coding for Low Noise Interactive Quantum Communication
Debbie Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, and Nengkun Yu
(University of Waterloo, Canada; Perimeter Institute Waterloo, Canada; Nanjing University, China; University of Technology Sydney, Australia)
@InProceedings{STOC18p409,
author = {Debbie Leung and Ashwin Nayak and Ala Shayeghi and Dave Touchette and Penghui Yao and Nengkun Yu},
title = {Capacity Approaching Coding for Low Noise Interactive Quantum Communication},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {409-408},
doi = {10.1145/3188745.3188908},
year = {2018},
}
Publisher's Version
Article: stoc18main-p294-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188908
|
| |
Tzamos, Christos |
STOC '18: "A Converse to Banach's ..."
A Converse to Banach's Fixed Point Theorem and Its CLS-Completeness
Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis
(Massachusetts Institute of Technology, USA; Microsoft Research, USA)
@InProceedings{STOC18p45,
author = {Constantinos Daskalakis and Christos Tzamos and Manolis Zampetakis},
title = {A Converse to Banach's Fixed Point Theorem and Its CLS-Completeness},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {45-44},
doi = {10.1145/3188745.3188968},
year = {2018},
}
Publisher's Version
Article: stoc18main-p443-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188968
|
| |
Uitto, Jara
|
STOC '18: "Deterministic Distributed ..."
Deterministic Distributed Edge-Coloring with Fewer Colors
Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, and Jara Uitto
(ETH Zurich, Switzerland; University of Freiburg, Germany)
@InProceedings{STOC18p493,
author = {Mohsen Ghaffari and Fabian Kuhn and Yannic Maus and Jara Uitto},
title = {Deterministic Distributed Edge-Coloring with Fewer Colors},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {493-492},
doi = {10.1145/3188745.3188906},
year = {2018},
}
Publisher's Version
Article: stoc18main-p293-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188906
|
| |
Vaikuntanathan, Vinod
|
STOC '18: "Breaking the Circuit-Size ..."
Breaking the Circuit-Size Barrier in Secret Sharing
Tianren Liu and Vinod Vaikuntanathan
(Massachusetts Institute of Technology, USA)
@InProceedings{STOC18p815,
author = {Tianren Liu and Vinod Vaikuntanathan},
title = {Breaking the Circuit-Size Barrier in Secret Sharing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {815-814},
doi = {10.1145/3188745.3188936},
year = {2018},
}
Publisher's Version
Article: stoc18main-p368-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188936
|
| |
Valiant, Gregory |
STOC '18: "Prediction with a Short Memory ..."
Prediction with a Short Memory
Vatsal Sharan, Sham Kakade, Percy Liang, and Gregory Valiant
(Stanford University, USA; University of Washington, USA)
@InProceedings{STOC18p1249,
author = {Vatsal Sharan and Sham Kakade and Percy Liang and Gregory Valiant},
title = {Prediction with a Short Memory},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1249-1248},
doi = {10.1145/3188745.3188954},
year = {2018},
}
Publisher's Version
Article: stoc18main-p410-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188954
|
| |
Végh, László A. |
STOC '18: "A Constant-Factor Approximation ..."
A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
Ola Svensson, Jakub Tarnawski, and László A. Végh
(EPFL, Switzerland; London School of Economics, UK)
@InProceedings{STOC18p255,
author = {Ola Svensson and Jakub Tarnawski and László A. Végh},
title = {A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {255-254},
doi = {10.1145/3188745.3188824},
year = {2018},
}
Publisher's Version
Article: stoc18main-p150-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188824
|
| |
Vempala, Santosh S. |
STOC '18: "Convergence Rate of Riemannian ..."
Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation
Yin Tat Lee and Santosh S. Vempala
(University of Washington, USA; Microsoft Research, USA; Georgia Tech, USA)
@InProceedings{STOC18p1291,
author = {Yin Tat Lee and Santosh S. Vempala},
title = {Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1291-1290},
doi = {10.1145/3188745.3188774},
year = {2018},
}
Publisher's Version
Article: stoc18main-p55-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188774
STOC '18: "Stochastic Localization + ..."
Stochastic Localization + Stieltjes Barrier = Tight Bound for Log-Sobolev
Yin Tat Lee and Santosh S. Vempala
(University of Washington, USA; Microsoft Research, USA; Georgia Tech, USA)
@InProceedings{STOC18p1305,
author = {Yin Tat Lee and Santosh S. Vempala},
title = {Stochastic Localization + Stieltjes Barrier = Tight Bound for Log-Sobolev},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1305-1304},
doi = {10.1145/3188745.3188866},
year = {2018},
}
Publisher's Version
Article: stoc18main-p230-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188866
|
| |
Vrana, Péter |
STOC '18: "Universal Points in the Asymptotic ..."
Universal Points in the Asymptotic Spectrum of Tensors
Matthias Christandl, Péter Vrana, and Jeroen Zuiddam
(University of Copenhagen, Denmark; Budapest University of Technology and Economics, Hungary; CWI, Netherlands)
@InProceedings{STOC18p353,
author = {Matthias Christandl and Péter Vrana and Jeroen Zuiddam},
title = {Universal Points in the Asymptotic Spectrum of Tensors},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {353-352},
doi = {10.1145/3188745.3188766},
year = {2018},
}
Publisher's Version
Article: stoc18main-p32-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188766
|
| |
Waingarten, Erik
|
STOC '18: "Data-Dependent Hashing via ..."
Data-Dependent Hashing via Nonlinear Spectral Gaps
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten
(Columbia University, USA; Princeton University, USA; University of Toronto, Canada; Microsoft Research, USA)
@InProceedings{STOC18p913,
author = {Alexandr Andoni and Assaf Naor and Aleksandar Nikolov and Ilya Razenshteyn and Erik Waingarten},
title = {Data-Dependent Hashing via Nonlinear Spectral Gaps},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {913-912},
doi = {10.1145/3188745.3188846},
year = {2018},
}
Publisher's Version
Article: stoc18main-p189-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188846
|
| |
Walczak, Bartosz |
STOC '18: "Sparse Kneser Graphs Are Hamiltonian ..."
Sparse Kneser Graphs Are Hamiltonian
Torsten Mütze, Jerri Nummenpalo, and Bartosz Walczak
(TU Berlin, Germany; ETH Zurich, Switzerland; Jagiellonian University, Poland)
@InProceedings{STOC18p1053,
author = {Torsten Mütze and Jerri Nummenpalo and Bartosz Walczak},
title = {Sparse Kneser Graphs Are Hamiltonian},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1053-1052},
doi = {10.1145/3188745.3188834},
year = {2018},
}
Publisher's Version
Article: stoc18main-p166-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188834
|
| |
Wang, Joshua R. |
STOC '18: "Cell-Probe Lower Bounds from ..."
Cell-Probe Lower Bounds from Online Communication Complexity
Josh Alman, Joshua R. Wang, and Huacheng Yu
(Massachusetts Institute of Technology, USA; Stanford University, USA; Harvard University, USA)
@InProceedings{STOC18p1165,
author = {Josh Alman and Joshua R. Wang and Huacheng Yu},
title = {Cell-Probe Lower Bounds from Online Communication Complexity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1165-1164},
doi = {10.1145/3188745.3188862},
year = {2018},
}
Publisher's Version
Article: stoc18main-p223-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188862
|
| |
Wang, Zihe |
STOC '18: "A Tighter Welfare Guarantee ..."
A Tighter Welfare Guarantee for First-Price Auctions
Darrell Hoy, Samuel Taggart, and Zihe Wang
(Tremor Technologies, USA; Oberlin College, USA; Shanghai University of Finance and Economics, China)
@InProceedings{STOC18p157,
author = {Darrell Hoy and Samuel Taggart and Zihe Wang},
title = {A Tighter Welfare Guarantee for First-Price Auctions},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {157-156},
doi = {10.1145/3188745.3188944},
year = {2018},
}
Publisher's Version
Article: stoc18main-p383-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188944
|
| |
Waters, Brent |
STOC '18: "Collusion Resistant Traitor ..."
Collusion Resistant Traitor Tracing from Learning with Errors
Rishab Goyal, Venkata Koppula, and Brent Waters
(University of Texas at Austin, USA)
@InProceedings{STOC18p773,
author = {Rishab Goyal and Venkata Koppula and Brent Waters},
title = {Collusion Resistant Traitor Tracing from Learning with Errors},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {773-772},
doi = {10.1145/3188745.3188844},
year = {2018},
}
Publisher's Version
Article: stoc18main-p187-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188844
|
| |
Weber, Robbie |
STOC '18: "A Simply Exponential Upper ..."
A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings
Anna R. Karlin, Shayan Oveis Gharan, and Robbie Weber
(University of Washington, USA)
@InProceedings{STOC18p1067,
author = {Anna R. Karlin and Shayan Oveis Gharan and Robbie Weber},
title = {A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1067-1066},
doi = {10.1145/3188745.3188848},
year = {2018},
}
Publisher's Version
Article: stoc18main-p191-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188848
|
| |
Wein, Nicole |
STOC '18: "Towards Tight Approximation ..."
Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein
(Massachusetts Institute of Technology, USA; Bar-Ilan University, Israel)
@InProceedings{STOC18p325,
author = {Arturs Backurs and Liam Roditty and Gilad Segal and Virginia Vassilevska Williams and Nicole Wein},
title = {Towards Tight Approximation Bounds for Graph Diameter and Eccentricities},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {325-324},
doi = {10.1145/3188745.3188950},
year = {2018},
}
Publisher's Version
Article: stoc18main-p403-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188950
|
| |
Weinstein, Omri |
STOC '18: "Crossing the Logarithmic Barrier ..."
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
Kasper Green Larsen, Omri Weinstein, and Huacheng Yu
(Aarhus University, Denmark; Columbia University, USA; Harvard University, USA)
@InProceedings{STOC18p1137,
author = {Kasper Green Larsen and Omri Weinstein and Huacheng Yu},
title = {Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1137-1136},
doi = {10.1145/3188745.3188790},
year = {2018},
}
Publisher's Version
Article: stoc18main-p97-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188790
|
| |
Wichs, Daniel |
STOC '18: "Succinct Delegation for Low-Space ..."
Succinct Delegation for Low-Space Non-deterministic Computation
Saikrishna Badrinarayanan, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai, and Daniel Wichs
(University of California at Los Angeles, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA; Northeastern University, USA)
@InProceedings{STOC18p829,
author = {Saikrishna Badrinarayanan and Yael Tauman Kalai and Dakshita Khurana and Amit Sahai and Daniel Wichs},
title = {Succinct Delegation for Low-Space Non-deterministic Computation},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {829-828},
doi = {10.1145/3188745.3188924},
year = {2018},
}
Publisher's Version
Article: stoc18main-p312-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188924
|
| |
Wiese, Andreas |
STOC '18: "A (5/3 + ε)-Approximation ..."
A (5/3 + ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes
Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou
(University of Lugano, Switzerland; University of Bremen, Germany; Saarland University, Germany; University of Chile, Chile; École Polytechnique, France)
@InProceedings{STOC18p717,
author = {Fabrizio Grandoni and Tobias Mömke and Andreas Wiese and Hang Zhou},
title = {A (5/3 + ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {717-716},
doi = {10.1145/3188745.3188894},
year = {2018},
}
Publisher's Version
Article: stoc18main-p278-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188894
|
| |
Wigderson, Avi |
STOC '18: "Operator Scaling via Geodesically ..."
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson
(Microsoft Research, USA; Princeton University, USA; University of Toronto, Canada; Institute for Advanced Study at Princeton, USA)
@InProceedings{STOC18p213,
author = {Zeyuan Allen-Zhu and Ankit Garg and Yuanzhi Li and Rafael Oliveira and Avi Wigderson},
title = {Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {213-212},
doi = {10.1145/3188745.3188942},
year = {2018},
}
Publisher's Version
Article: stoc18main-p382-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188942
|
| |
Williams, Ryan |
STOC '18: "Circuit Lower Bounds for Nondeterministic ..."
Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP
Cody Murray and Ryan Williams
(Massachusetts Institute of Technology, USA)
@InProceedings{STOC18p1025,
author = {Cody Murray and Ryan Williams},
title = {Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1025-1024},
doi = {10.1145/3188745.3188910},
year = {2018},
}
Publisher's Version
Article: stoc18main-p295-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188910
|
| |
Williams, Virginia Vassilevska |
STOC '18: "Towards Tight Approximation ..."
Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein
(Massachusetts Institute of Technology, USA; Bar-Ilan University, Israel)
@InProceedings{STOC18p325,
author = {Arturs Backurs and Liam Roditty and Gilad Segal and Virginia Vassilevska Williams and Nicole Wein},
title = {Towards Tight Approximation Bounds for Graph Diameter and Eccentricities},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {325-324},
doi = {10.1145/3188745.3188950},
year = {2018},
}
Publisher's Version
Article: stoc18main-p403-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188950
|
| |
Wu, Xiaowei |
STOC '18: "How to Match When All Vertices ..."
How to Match When All Vertices Arrive Online
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu
(University of Hong Kong, China)
@InProceedings{STOC18p17,
author = {Zhiyi Huang and Ning Kang and Zhihao Gavin Tang and Xiaowei Wu and Yuhao Zhang and Xue Zhu},
title = {How to Match When All Vertices Arrive Online},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {17-16},
doi = {10.1145/3188745.3188858},
year = {2018},
}
Publisher's Version
Article: stoc18main-p214-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188858
|
| |
Xie, Jinyu
|
STOC '18: "Distribution-Free Junta Testing ..."
Distribution-Free Junta Testing
Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, and Jinyu Xie
(Shanghai Jiao Tong University, China; Columbia University, USA)
@InProceedings{STOC18p871,
author = {Zhengyang Liu and Xi Chen and Rocco A. Servedio and Ying Sheng and Jinyu Xie},
title = {Distribution-Free Junta Testing},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {871-870},
doi = {10.1145/3188745.3188842},
year = {2018},
}
Publisher's Version
Article: stoc18main-p186-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188842
|
| |
Yao, Penghui
|
STOC '18: "Capacity Approaching Coding ..."
Capacity Approaching Coding for Low Noise Interactive Quantum Communication
Debbie Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, and Nengkun Yu
(University of Waterloo, Canada; Perimeter Institute Waterloo, Canada; Nanjing University, China; University of Technology Sydney, Australia)
@InProceedings{STOC18p409,
author = {Debbie Leung and Ashwin Nayak and Ala Shayeghi and Dave Touchette and Penghui Yao and Nengkun Yu},
title = {Capacity Approaching Coding for Low Noise Interactive Quantum Communication},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {409-408},
doi = {10.1145/3188745.3188908},
year = {2018},
}
Publisher's Version
Article: stoc18main-p294-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188908
|
| |
Yu, Huacheng |
STOC '18: "Crossing the Logarithmic Barrier ..."
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
Kasper Green Larsen, Omri Weinstein, and Huacheng Yu
(Aarhus University, Denmark; Columbia University, USA; Harvard University, USA)
@InProceedings{STOC18p1137,
author = {Kasper Green Larsen and Omri Weinstein and Huacheng Yu},
title = {Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1137-1136},
doi = {10.1145/3188745.3188790},
year = {2018},
}
Publisher's Version
Article: stoc18main-p97-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188790
STOC '18: "Cell-Probe Lower Bounds from ..."
Cell-Probe Lower Bounds from Online Communication Complexity
Josh Alman, Joshua R. Wang, and Huacheng Yu
(Massachusetts Institute of Technology, USA; Stanford University, USA; Harvard University, USA)
@InProceedings{STOC18p1165,
author = {Josh Alman and Joshua R. Wang and Huacheng Yu},
title = {Cell-Probe Lower Bounds from Online Communication Complexity},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1165-1164},
doi = {10.1145/3188745.3188862},
year = {2018},
}
Publisher's Version
Article: stoc18main-p223-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188862
|
| |
Yu, Nengkun |
STOC '18: "Capacity Approaching Coding ..."
Capacity Approaching Coding for Low Noise Interactive Quantum Communication
Debbie Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, and Nengkun Yu
(University of Waterloo, Canada; Perimeter Institute Waterloo, Canada; Nanjing University, China; University of Technology Sydney, Australia)
@InProceedings{STOC18p409,
author = {Debbie Leung and Ashwin Nayak and Ala Shayeghi and Dave Touchette and Penghui Yao and Nengkun Yu},
title = {Capacity Approaching Coding for Low Noise Interactive Quantum Communication},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {409-408},
doi = {10.1145/3188745.3188908},
year = {2018},
}
Publisher's Version
Article: stoc18main-p294-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188908
|
| |
Zampetakis, Manolis
|
STOC '18: "A Converse to Banach's ..."
A Converse to Banach's Fixed Point Theorem and Its CLS-Completeness
Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis
(Massachusetts Institute of Technology, USA; Microsoft Research, USA)
@InProceedings{STOC18p45,
author = {Constantinos Daskalakis and Christos Tzamos and Manolis Zampetakis},
title = {A Converse to Banach's Fixed Point Theorem and Its CLS-Completeness},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {45-44},
doi = {10.1145/3188745.3188968},
year = {2018},
}
Publisher's Version
Article: stoc18main-p443-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188968
|
| |
Zanden, Tom C. van der |
STOC '18: "A Framework for ETH-Tight ..."
A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden
(Eindhoven University of Technology, Netherlands; Utrecht University, Netherlands; Hungarian Academy of Sciences, Hungary)
@InProceedings{STOC18p675,
author = {Mark de Berg and Hans L. Bodlaender and Sándor Kisfaludi-Bak and Dániel Marx and Tom C. van der Zanden},
title = {A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {675-674},
doi = {10.1145/3188745.3188854},
year = {2018},
}
Publisher's Version
Article: stoc18main-p204-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188854
|
| |
Zenklusen, Rico |
STOC '18: "Improved Approximation for ..."
Improved Approximation for Tree Augmentation: Saving by Rewiring
Fabrizio Grandoni, Christos Kalaitzis, and Rico Zenklusen
(University of Lugano, Switzerland; ETH Zurich, Switzerland)
@InProceedings{STOC18p745,
author = {Fabrizio Grandoni and Christos Kalaitzis and Rico Zenklusen},
title = {Improved Approximation for Tree Augmentation: Saving by Rewiring},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {745-744},
doi = {10.1145/3188745.3188898},
year = {2018},
}
Publisher's Version
Article: stoc18main-p284-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188898
|
| |
Zhang, Chihao |
STOC '18: "Counting Hypergraph Colourings ..."
Counting Hypergraph Colourings in the Local Lemma Regime
Heng Guo, Chao Liao, Pinyan Lu, and Chihao Zhang
(University of Edinburgh, UK; Shanghai Jiao Tong University, China; Shanghai University of Finance and Economics, China; Chinese University of Hong Kong, China)
@InProceedings{STOC18p1081,
author = {Heng Guo and Chao Liao and Pinyan Lu and Chihao Zhang},
title = {Counting Hypergraph Colourings in the Local Lemma Regime},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1081-1080},
doi = {10.1145/3188745.3188934},
year = {2018},
}
Publisher's Version
Article: stoc18main-p364-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188934
|
| |
Zhang, Peng |
STOC '18: "Incomplete Nested Dissection ..."
Incomplete Nested Dissection
Rasmus Kyng, Richard Peng, Robert Schwieterman, and Peng Zhang
(Simons Institute for the Theory of Computing Berkeley, USA; Georgia Tech, USA)
@InProceedings{STOC18p479,
author = {Rasmus Kyng and Richard Peng and Robert Schwieterman and Peng Zhang},
title = {Incomplete Nested Dissection},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {479-478},
doi = {10.1145/3188745.3188960},
year = {2018},
}
Publisher's Version
Article: stoc18main-p429-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188960
|
| |
Zhang, Yuhao |
STOC '18: "How to Match When All Vertices ..."
How to Match When All Vertices Arrive Online
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu
(University of Hong Kong, China)
@InProceedings{STOC18p17,
author = {Zhiyi Huang and Ning Kang and Zhihao Gavin Tang and Xiaowei Wu and Yuhao Zhang and Xue Zhu},
title = {How to Match When All Vertices Arrive Online},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {17-16},
doi = {10.1145/3188745.3188858},
year = {2018},
}
Publisher's Version
Article: stoc18main-p214-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188858
|
| |
Zhou, Hang |
STOC '18: "A (5/3 + ε)-Approximation ..."
A (5/3 + ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes
Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou
(University of Lugano, Switzerland; University of Bremen, Germany; Saarland University, Germany; University of Chile, Chile; École Polytechnique, France)
@InProceedings{STOC18p717,
author = {Fabrizio Grandoni and Tobias Mömke and Andreas Wiese and Hang Zhou},
title = {A (5/3 + ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {717-716},
doi = {10.1145/3188745.3188894},
year = {2018},
}
Publisher's Version
Article: stoc18main-p278-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188894
|
| |
Zhu, Xue |
STOC '18: "How to Match When All Vertices ..."
How to Match When All Vertices Arrive Online
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu
(University of Hong Kong, China)
@InProceedings{STOC18p17,
author = {Zhiyi Huang and Ning Kang and Zhihao Gavin Tang and Xiaowei Wu and Yuhao Zhang and Xue Zhu},
title = {How to Match When All Vertices Arrive Online},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {17-16},
doi = {10.1145/3188745.3188858},
year = {2018},
}
Publisher's Version
Article: stoc18main-p214-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188858
|
| |
Zuiddam, Jeroen |
STOC '18: "Universal Points in the Asymptotic ..."
Universal Points in the Asymptotic Spectrum of Tensors
Matthias Christandl, Péter Vrana, and Jeroen Zuiddam
(University of Copenhagen, Denmark; Budapest University of Technology and Economics, Hungary; CWI, Netherlands)
@InProceedings{STOC18p353,
author = {Matthias Christandl and Péter Vrana and Jeroen Zuiddam},
title = {Universal Points in the Asymptotic Spectrum of Tensors},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {353-352},
doi = {10.1145/3188745.3188766},
year = {2018},
}
Publisher's Version
Article: stoc18main-p32-p (type: Full Paper (14 pages)) doi:10.1145/3188745.3188766
|