STOC 2018 – Author Index

A B C D E F G H I J K L M N O P R S T U V W X Y Z

	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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}, }
	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 = {}, year = {2018}, } 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}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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}, }
	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 = {}, year = {2018}, }
	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}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, } 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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	Łą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}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, } 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 = {}, year = {2018}, } 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 = {}, year = {2018}, } 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 = {}, year = {2018}, } 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}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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}, } 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}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	Š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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, } 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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }
	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 = {}, year = {2018}, }