STOC 2018
50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2018)
Powered by
Conference Publishing Consulting

50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2018), June 25–29, 2018, Los Angeles, CA, USA

STOC 2018 – Author Index

Contents - Abstracts - Authors

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 ..."
Abboud, Amir STOC '18: "More Consequences of Falsifying ..."
Abraham, Ittai STOC '18: "Metric Embedding via Shortest ..."
Abrahamsen, Mikkel STOC '18: "The Art Gallery Problem Is ..." STOC '18: "Fast Fencing ..."
Adamaszek, Anna STOC '18: "The Art Gallery Problem Is ..." STOC '18: "Fast Fencing ..."
Agarwal, Udit STOC '18: "Fine-Grained Complexity for ..."
Aggarwal, Divesh STOC '18: "(Gap/S)ETH Hardness of SVP ..."
Agrawal, Manindra STOC '18: "Bootstrapping Variables in ..."
Allen-Zhu, Zeyuan STOC '18: "Operator Scaling via Geodesically ..."
Alman, Josh STOC '18: "Cell-Probe Lower Bounds from ..."
Andoni, Alexandr STOC '18: "Data-Dependent Hashing via ..."
Assadi, Sepehr STOC '18: "Fully Dynamic Maximal Independent ..."
Atserias, Albert STOC '18: "Clique Is Hard on Average ..."
Backurs, Arturs STOC '18: "Towards Tight Approximation ..."
Badrinarayanan, Saikrishna STOC '18: "Succinct Delegation for Low-Space ..."
Balkanski, Eric STOC '18: "The Adaptive Complexity of ..."
Balliu, Alkida STOC '18: "New Classes of Distributed ..."
Bansal, Nikhil STOC '18: "The Gram-Schmidt Walk: A Cure ..."
Bateni, MohammadHossein STOC '18: "Fast Algorithms for Knapsack ..."
Bezáková, Ivona STOC '18: "Inapproximability of the Independent ..."
Bitansky, Nir STOC '18: "Multi-collision Resistance: ..."
Bläser, Markus STOC '18: "Generalized Matrix Completion ..."
Bodlaender, Hans L. STOC '18: "A Framework for ETH-Tight ..."
Bonacina, Ilario STOC '18: "Clique Is Hard on Average ..."
Brand, Cornelius STOC '18: "Extensor-Coding ..."
Braverman, Mark STOC '18: "Hitting Sets with Near-Optimal ..." STOC '18: "Interactive Compression to ..."
Bringmann, Karl STOC '18: "Fast Fencing ..." STOC '18: "More Consequences of Falsifying ..."
Bubeck, Sébastien STOC '18: "k-Server via Multiscale Entropic ..." STOC '18: "An Homotopy Method for lp ..."
Bun, Mark STOC '18: "Composable and Versatile Privacy ..." STOC '18: "The Polynomial Method Strikes ..."
Byrka, Jarosław STOC '18: "Constant-Factor Approximation ..."
Błasiok, Jarosław STOC '18: "General Strong Polarization ..."
Canonne, Clément L. STOC '18: "Testing Conditional Independence ..."
Chakraborty, Diptarka STOC '18: "Tight Cell Probe Bounds for ..."
Chang, Yi-Jun STOC '18: "An Optimal Distributed (Δ+1)-Coloring ..."
Chattopadhyay, Arkadev STOC '18: "Simulation Beats Richness: ..."
Chattopadhyay, Eshan STOC '18: "Improved Pseudorandomness ..."
Chen, Xi STOC '18: "Distribution-Free Junta Testing ..."
Cheraghchi, Mahdi STOC '18: "Capacity Upper Bounds for ..."
Christandl, Matthias STOC '18: "Universal Points in the Asymptotic ..."
Chuzhoy, Julia STOC '18: "Almost Polynomial Hardness ..."
Cohen, Gil STOC '18: "Explicit Binary Tree Codes ..." STOC '18: "Hitting Sets with Near-Optimal ..."
Cohen, Michael B. STOC '18: "k-Server via Multiscale Entropic ..." STOC '18: "An Homotopy Method for lp ..."
Cohen-Addad, Vincent STOC '18: "Fast Fencing ..."
Czumaj, Artur STOC '18: "Round Compression for Parallel ..."
Dadush, Daniel STOC '18: "The Gram-Schmidt Walk: A Cure ..." STOC '18: "A Friendly Smoothed Analysis ..."
Daskalakis, Constantinos STOC '18: "A Converse to Banach's ..."
De Berg, Mark STOC '18: "A Framework for ETH-Tight ..."
Dell, Holger STOC '18: "Extensor-Coding ..." STOC '18: "Fine-Grained Reductions from ..." STOC '18: "More Consequences of Falsifying ..."
De Loera, Jesús A. STOC '18: "The Minimum Euclidean-Norm ..."
De Rezende, Susanna F. STOC '18: "Clique Is Hard on Average ..."
Diakonikolas, Ilias STOC '18: "List-Decodable Robust Mean ..." STOC '18: "Learning Geometric Concepts ..." STOC '18: "Testing Conditional Independence ..."
Dinur, Irit STOC '18: "Towards a Proof of the 2-to-1 ..." STOC '18: "On Non-optimally Expanding ..."
Dudek, Bartłomiej STOC '18: "Universal Protocols for Information ..."
Dutta, Pranjal STOC '18: "Discovering the Roots: Uniform ..."
Dwork, Cynthia STOC '18: "Composable and Versatile Privacy ..."
Eden, Talya STOC '18: "On Approximating the Number ..."
Efremenko, Klim STOC '18: "Interactive Coding over the ..."
El Alaoui, Ahmed STOC '18: "Tight Query Complexity Lower ..."
Emek, Yuval STOC '18: "Approximating Generalized ..."
Erickson, Jeff STOC '18: "Holiest Minimum-Cost Paths ..."
Fawzi, Omar STOC '18: "Efficient Decoding of Random ..."
Filos-Ratsikas, Aris STOC '18: "Consensus Halving Is PPA-Complete ..."
Filtser, Arnold STOC '18: "Metric Embedding via Shortest ..."
Fineman, Jeremy T. STOC '18: "Nearly Work-Efficient Parallel ..."
Forbes, Michael A. STOC '18: "A PSPACE Construction of a ..."
Fox, Kyle STOC '18: "Holiest Minimum-Cost Paths ..."
Franceschetti, Massimo STOC '18: "Shape of Diffusion and Size ..."
Franks, Cole STOC '18: "Operator Scaling with Specified ..."
Galanis, Andreas STOC '18: "Inapproximability of the Independent ..."
Garg, Ankit STOC '18: "A Matrix Expander Chernoff ..." STOC '18: "Operator Scaling via Geodesically ..." STOC '18: "Monotone Circuit Lower Bounds ..."
Garg, Shashwat STOC '18: "The Gram-Schmidt Walk: A Cure ..."
Garg, Sumegha STOC '18: "Extractor-Based Time-Space ..." STOC '18: "Hitting Sets with Near-Optimal ..."
Ghaffari, Mohsen STOC '18: "Improved Distributed Algorithms ..." STOC '18: "Deterministic Distributed ..."
Gharan, Shayan Oveis STOC '18: "A Simply Exponential Upper ..."
Ghosh, Sumanta STOC '18: "Bootstrapping Variables in ..."
Gishboliner, Lior STOC '18: "A Generalized Turán Problem ..."
Goldberg, Leslie Ann STOC '18: "Inapproximability of the Independent ..."
Goldberg, Paul W. STOC '18: "Consensus Halving Is PPA-Complete ..."
Gonczarowski, Yannai A. STOC '18: "Bounding the Menu-Size of ..."
Göös, Mika STOC '18: "Monotone Circuit Lower Bounds ..."
Goyal, Rishab STOC '18: "Collusion Resistant Traitor ..."
Goyal, Vipul STOC '18: "Non-malleable Secret Sharing ..."
Grandoni, Fabrizio STOC '18: "Improved Approximation for ..." STOC '18: "A (5/3 + ε)-Approximation ..."
Grospellier, Antoine STOC '18: "Efficient Decoding of Random ..."
Guo, Heng STOC '18: "Counting Hypergraph Colourings ..."
Gupta, Anupam STOC '18: "Metric Embedding via Shortest ..."
Guruswami, Venkatesan STOC '18: "General Strong Polarization ..."
Haddock, Jamie STOC '18: "The Minimum Euclidean-Norm ..."
Haeupler, Bernhard STOC '18: "Synchronization Strings: Explicit ..." STOC '18: "Explicit Binary Tree Codes ..."
Hajiaghayi, MohammadTaghi STOC '18: "Fast Algorithms for Knapsack ..."
Hatami, Pooya STOC '18: "Improved Pseudorandomness ..."
Hirvonen, Juho STOC '18: "New Classes of Distributed ..."
Hopkins, Samuel B. STOC '18: "Mixture Models, Robustness, ..."
Hoy, Darrell STOC '18: "A Tighter Welfare Guarantee ..."
Huang, Zhiyi STOC '18: "How to Match When All Vertices ..."
Huiberts, Sophie STOC '18: "A Friendly Smoothed Analysis ..."
Husfeldt, Thore STOC '18: "Extensor-Coding ..."
Ikenmeyer, Christian STOC '18: "Generalized Matrix Completion ..." STOC '18: "On the Complexity of Hazard-Free ..."
Im, Sungjin STOC '18: "Online Load Balancing on Related ..."
Jindal, Gorav STOC '18: "Generalized Matrix Completion ..."
Kakade, Sham STOC '18: "Prediction with a Short Memory ..."
Kalai, Yael Tauman STOC '18: "Multi-collision Resistance: ..." STOC '18: "Succinct Delegation for Low-Space ..."
Kalaitzis, Christos STOC '18: "Improved Approximation for ..."
Kamath, Pritish STOC '18: "Monotone Circuit Lower Bounds ..."
Kamma, Lior STOC '18: "Tight Cell Probe Bounds for ..."
Kane, Daniel M. STOC '18: "List-Decodable Robust Mean ..." STOC '18: "Near-Optimal Linear Decision ..." STOC '18: "Learning Geometric Concepts ..." STOC '18: "Testing Conditional Independence ..."
Kang, Ning STOC '18: "How to Match When All Vertices ..."
Karlin, Anna R. STOC '18: "A Simply Exponential Upper ..."
Kaufman, Tali STOC '18: "Construction of New Local ..."
Kell, Nathaniel STOC '18: "Online Load Balancing on Related ..."
Kempa, Dominik STOC '18: "At the Roots of Dictionary ..."
Khot, Subhash STOC '18: "Towards a Proof of the 2-to-1 ..." STOC '18: "On Non-optimally Expanding ..."
Khurana, Dakshita STOC '18: "Succinct Delegation for Low-Space ..."
Kim, David H. K. STOC '18: "Almost Polynomial Hardness ..."
Kindler, Guy STOC '18: "Towards a Proof of the 2-to-1 ..." STOC '18: "On Non-optimally Expanding ..."
Kisfaludi-Bak, Sándor STOC '18: "A Framework for ETH-Tight ..."
Kol, Gillat STOC '18: "Interactive Coding over the ..." STOC '18: "Interactive Compression to ..."
Komarath, Balagopal STOC '18: "On the Complexity of Hazard-Free ..."
Koppula, Venkata STOC '18: "Collusion Resistant Traitor ..."
Korhonen, Janne H. STOC '18: "New Classes of Distributed ..."
Kosowski, Adrian STOC '18: "Universal Protocols for Information ..."
Kothari, Pravesh K. STOC '18: "Robust Moment Estimation and ..." STOC '18: "Sum-of-Squares Meets Nash: ..."
Kothari, Robin STOC '18: "The Polynomial Method Strikes ..."
Koucký, Michal STOC '18: "Simulation Beats Richness: ..."
Kozma, László STOC '18: "Smooth Heaps and a Dual View ..."
Krishnaswamy, Ravishankar STOC '18: "Constant Approximation for ..."
Kuhn, Fabian STOC '18: "Deterministic Distributed ..."
Kumar, Ashutosh STOC '18: "Non-malleable Secret Sharing ..."
Kutten, Shay STOC '18: "Approximating Generalized ..."
Kwok, Tsz Chiu STOC '18: "The Paulsen Problem, Continuous ..."
Kyng, Rasmus STOC '18: "Incomplete Nested Dissection ..."
Łącki, Jakub STOC '18: "Round Compression for Parallel ..."
Laekhanukit, Bundit STOC '18: "On the Parameterized Complexity ..."
Lapinskas, John STOC '18: "Fine-Grained Reductions from ..."
Larsen, Kasper Green STOC '18: "Tight Cell Probe Bounds for ..." STOC '18: "Crossing the Logarithmic Barrier ..."
Lau, Lap Chi STOC '18: "The Paulsen Problem, Continuous ..."
Lauria, Massimo STOC '18: "Clique Is Hard on Average ..."
Lavi, Ron STOC '18: "Approximating Generalized ..."
Lee, James R. STOC '18: "k-Server via Multiscale Entropic ..."
Lee, Yin Tat STOC '18: "A Matrix Expander Chernoff ..." STOC '18: "k-Server via Multiscale Entropic ..." STOC '18: "Convergence Rate of Riemannian ..." STOC '18: "Stochastic Localization + ..." STOC '18: "The Paulsen Problem, Continuous ..." STOC '18: "An Homotopy Method for lp ..."
Lempiäinen, Tuomo STOC '18: "New Classes of Distributed ..."
Lenzen, Christoph STOC '18: "On the Complexity of Hazard-Free ..."
Leung, Debbie STOC '18: "Capacity Approaching Coding ..."
Leverrier, Anthony STOC '18: "Efficient Decoding of Random ..."
Li, Jason STOC '18: "Improved Distributed Algorithms ..."
Li, Jerry STOC '18: "Mixture Models, Robustness, ..."
Li, Shi STOC '18: "Constant Approximation for ..."
Li, Wenzheng STOC '18: "An Optimal Distributed (Δ+1)-Coloring ..."
Li, Yuanzhi STOC '18: "Operator Scaling via Geodesically ..." STOC '18: "An Homotopy Method for lp ..."
Liang, Percy STOC '18: "Prediction with a Short Memory ..."
Liao, Chao STOC '18: "Counting Hypergraph Colourings ..."
Liu, Tianren STOC '18: "Breaking the Circuit-Size ..."
Liu, Zhengyang STOC '18: "Distribution-Free Junta Testing ..."
Lkhamsuren, Luvsandondov STOC '18: "Holiest Minimum-Cost Paths ..."
Lo, Irene STOC '18: "Dynamic Matching in School ..."
Loff, Bruno STOC '18: "Simulation Beats Richness: ..."
Lovett, Shachar STOC '18: "The Gram-Schmidt Walk: A Cure ..." STOC '18: "Near-Optimal Linear Decision ..."
Lu, Pinyan STOC '18: "Counting Hypergraph Colourings ..."
Lykouris, Thodoris STOC '18: "Stochastic Bandits Robust ..."
Lysikov, Vladimir STOC '18: "Generalized Matrix Completion ..." STOC '18: "On the Complexity of Hazard-Free ..."
Ma, Tengyu STOC '18: "Generalization and Equilibrium ..."
Mądry, Aleksander STOC '18: "k-Server via Multiscale Entropic ..." STOC '18: "Round Compression for Parallel ..."
Mahabadi, Sepideh STOC '18: "Nonlinear Dimension Reduction ..."
Makarychev, Konstantin STOC '18: "Nonlinear Dimension Reduction ..."
Makarychev, Yury STOC '18: "Nonlinear Dimension Reduction ..."
Manurangsi, Pasin STOC '18: "On the Parameterized Complexity ..."
Marx, Dániel STOC '18: "A Framework for ETH-Tight ..."
Maus, Yannic STOC '18: "Deterministic Distributed ..."
Mehr, Mehran STOC '18: "Fast Fencing ..."
Mehta, Ruta STOC '18: "Sum-of-Squares Meets Nash: ..."
Miltzow, Tillmann STOC '18: "The Art Gallery Problem Is ..."
Minzer, Dor STOC '18: "Towards a Proof of the 2-to-1 ..." STOC '18: "On Non-optimally Expanding ..."
Mirrokni, Vahab STOC '18: "Stochastic Bandits Robust ..."
Mitrović, Slobodan STOC '18: "Round Compression for Parallel ..."
Mokhov, Andrey STOC '18: "On the Complexity of Hazard-Free ..."
Mömke, Tobias STOC '18: "A (5/3 + ε)-Approximation ..."
Moran, Shay STOC '18: "Near-Optimal Linear Decision ..."
Mukhopadhyay, Sagnik STOC '18: "Simulation Beats Richness: ..."
Murray, Cody STOC '18: "Circuit Lower Bounds for Nondeterministic ..."
Mütze, Torsten STOC '18: "Sparse Kneser Graphs Are Hamiltonian ..."
Nakkiran, Preetum STOC '18: "General Strong Polarization ..."
Naor, Assaf STOC '18: "Data-Dependent Hashing via ..."
Nayak, Ashwin STOC '18: "Capacity Approaching Coding ..."
Nederlof, Jesper STOC '18: "More Consequences of Falsifying ..."
Neiman, Ofer STOC '18: "Metric Embedding via Shortest ..."
Neuen, Daniel STOC '18: "An Exponential Lower Bound ..."
Nikolov, Aleksandar STOC '18: "Data-Dependent Hashing via ..."
Nimavat, Rachit STOC '18: "Almost Polynomial Hardness ..."
Nordström, Jakob STOC '18: "Clique Is Hard on Average ..."
Nummenpalo, Jerri STOC '18: "Sparse Kneser Graphs Are Hamiltonian ..."
Oliveira, Rafael STOC '18: "Operator Scaling via Geodesically ..."
Olivetti, Dennis STOC '18: "New Classes of Distributed ..."
Omidvar, Hamed STOC '18: "Shape of Diffusion and Size ..."
Onak, Krzysztof STOC '18: "The Query Complexity of Graph ..." STOC '18: "Fully Dynamic Maximal Independent ..." STOC '18: "Round Compression for Parallel ..."
Oppenheim, Izhar STOC '18: "Construction of New Local ..."
Paes Leme, Renato STOC '18: "Stochastic Bandits Robust ..."
Paneth, Omer STOC '18: "Multi-collision Resistance: ..."
Panigrahi, Debmalya STOC '18: "Online Load Balancing on Related ..."
Peng, Richard STOC '18: "Incomplete Nested Dissection ..."
Pettie, Seth STOC '18: "An Optimal Distributed (Δ+1)-Coloring ..."
Pitassi, Toniann STOC '18: "Lifting Nullstellensatz to ..."
Prezza, Nicola STOC '18: "At the Roots of Dictionary ..."
Rademacher, Luis STOC '18: "The Minimum Euclidean-Norm ..."
Ramachandran, Akshay STOC '18: "The Paulsen Problem, Continuous ..."
Ramachandran, Vijaya STOC '18: "Fine-Grained Complexity for ..."
Raz, Ran STOC '18: "Extractor-Based Time-Space ..."
Razborov, Alexander STOC '18: "Clique Is Hard on Average ..."
Razenshteyn, Ilya STOC '18: "Nonlinear Dimension Reduction ..." STOC '18: "Data-Dependent Hashing via ..."
Recht, Benjamin STOC '18: "Tight Query Complexity Lower ..."
Reingold, Omer STOC '18: "Improved Pseudorandomness ..."
Robere, Robert STOC '18: "Lifting Nullstellensatz to ..."
Roditty, Liam STOC '18: "Towards Tight Approximation ..."
Ron, Dana STOC '18: "On Approximating the Number ..."
Rotenberg, Eva STOC '18: "Fast Fencing ..."
Rothblum, Guy N. STOC '18: "Composable and Versatile Privacy ..."
Roytman, Alan STOC '18: "Fast Fencing ..."
Rubinstein, Aviad STOC '18: "Hardness of Approximate Nearest ..."
Rudra, Atri STOC '18: "General Strong Polarization ..."
S., Karthik C. STOC '18: "On the Parameterized Complexity ..."
Safra, Muli STOC '18: "Towards a Proof of the 2-to-1 ..." STOC '18: "On Non-optimally Expanding ..."
Sahai, Amit STOC '18: "Succinct Delegation for Low-Space ..."
Sandeep, Sai STOC '18: "Constant Approximation for ..."
Sankowski, Piotr STOC '18: "Round Compression for Parallel ..."
Saranurak, Thatchaphol STOC '18: "Smooth Heaps and a Dual View ..."
Saxena, Nitin STOC '18: "Bootstrapping Variables in ..." STOC '18: "Discovering the Roots: Uniform ..."
Saxena, Raghuvansh STOC '18: "Interactive Coding over the ..."
Schieber, Baruch STOC '18: "Fully Dynamic Maximal Independent ..."
Schild, Aaron STOC '18: "An Almost-Linear Time Algorithm ..."
Schulman, Leonard J. STOC '18: "Explicit Binary Tree Codes ..."
Schweitzer, Pascal STOC '18: "An Exponential Lower Bound ..."
Schwieterman, Robert STOC '18: "Incomplete Nested Dissection ..."
Seddighin, Saeed STOC '18: "Fast Algorithms for Knapsack ..."
Segal, Gilad STOC '18: "Towards Tight Approximation ..."
Servedio, Rocco A. STOC '18: "Distribution-Free Junta Testing ..."
Seshadhri, C. STOC '18: "On Approximating the Number ..."
Shadloo, Maryam STOC '18: "Online Load Balancing on Related ..."
Shahrasbi, Amirbehshad STOC '18: "Synchronization Strings: Explicit ..."