STOC 2019
51st Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2019)
Powered by
Conference Publishing Consulting

51st Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2019), June 23–26, 2019, Phoenix, AZ, USA

STOC 2019 – Author Index

Contents - Abstracts - Authors

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

Aaronson, Scott STOC '19: "Gentle Measurement of Quantum ..."
Abboud, Amir STOC '19: "Dynamic Set Cover: Improved ..."
Addanki, Raghavendra STOC '19: "Dynamic Set Cover: Improved ..."
Alistarh, Dan STOC '19: "Why Extension-Based Proofs ..."
Alon, Noga STOC '19: "Private PAC Learning Implies ..."
Alrabiah, Omar STOC '19: "An Exponential Lower Bound ..."
Anari, Nima STOC '19: "Log-Concave Polynomials II: ..."
Arora, Atul Singh STOC '19: "Quantum Weak Coin Flipping ..."
Aspnes, James STOC '19: "Why Extension-Based Proofs ..."
Assadi, Sepehr STOC '19: "Polynomial Pass Lower Bounds ..."
Avron, Haim STOC '19: "A Universal Sampling Method ..."
Babai, Laszlo STOC '19: "Canonical Form for Graphs ..."
Babichenko, Yakov STOC '19: "The Communication Complexity ..."
Bădescu, Costin STOC '19: "Quantum State Certification ..."
Balkanski, Eric STOC '19: "An Optimal Approximation for ..."
Bansal, Nikhil STOC '19: "On a Generalization of Iterated ..."
Becchetti, Luca STOC '19: "Oblivious Dimension Reduction ..."
Bekos, Michael STOC '19: "Planar Graphs of Bounded Degree ..."
Bender, Michael A. STOC '19: "Achieving Optimal Backlog ..."
Bernstein, Aaron STOC '19: "Distributed Exact Weighted ..." STOC '19: "Decremental Strongly-Connected ..."
Beyhaghi, Hedyeh STOC '19: "Optimal (and Benchmark-Optimal) ..."
Bitansky, Nir STOC '19: "Weak Zero-Knowledge Beyond ..."
Bohdanowicz, Thomas C. STOC '19: "Good Approximate Quantum LDPC ..."
Boroujeni, Mahdi STOC '19: "1+\epsilon Approximation of ..."
Brakensiek, Joshua STOC '19: "Bridging between 0/1 and Linear ..." STOC '19: "CSPs with Global Modular Constraints: ..."
Bresler, Guy STOC '19: "Learning Restricted Boltzmann ..."
Bringmann, Karl STOC '19: "Approximating APSP without ..."
Bubeck, Sébastien STOC '19: "Competitively Chasing Convex ..."
Bulín, Jakub STOC '19: "Algebraic Approach to Promise ..."
Bury, Marc STOC '19: "Oblivious Dimension Reduction ..."
Canetti, Ran STOC '19: "Fiat-Shamir: From Practice ..."
Canonne, Clément L. STOC '19: "The Structure of Optimal Private ..."
Capalbo, Michael STOC '19: "Explicit N-Vertex Graphs with ..."
Chakrabarty, Deeparnab STOC '19: "Approximation Algorithms for ..."
Charalampopoulos, Panagiotis STOC '19: "Almost Optimal Distance Oracles ..."
Charikar, Moses STOC '19: "Efficient Profile Maximum ..."
Chattopadhyay, Arkadev STOC '19: "The Log-Approximate-Rank Conjecture ..."
Chekuri, Chandra STOC '19: "Parallelizing Greedy for Submodular ..."
Chen, Lijie STOC '19: "Bootstrapping Results for ..."
Chen, Lin STOC '19: "Unconstrained Submodular Maximization ..."
Chen, Sitan STOC '19: "Beyond the Low-Degree Algorithm: ..."
Chen, Xi STOC '19: "Testing Unateness Nearly Optimally ..."
Chen, Yilei STOC '19: "Fiat-Shamir: From Practice ..."
Chen, Yu STOC '19: "Polynomial Pass Lower Bounds ..."
Choudhuri, Arka Rai STOC '19: "Finding a Nash Equilibrium ..."
Chuzhoy, Julia STOC '19: "A New Algorithm for Decremental ..."
Coester, Christian STOC '19: "The Online k-Taxi Problem ..."
Cohen, Michael B. STOC '19: "Solving Linear Programs in ..."
Cohen-Addad, Vincent STOC '19: "Oblivious Dimension Reduction ..."
Conte, Alessio STOC '19: "New Polynomial Delay Bounds ..."
Crosson, Elizabeth STOC '19: "Good Approximate Quantum LDPC ..."
Czerwiński, Wojciech STOC '19: "The Reachability Problem for ..."
Dadush, Daniel STOC '19: "On Approximating the Covering ..."
Daga, Mohit STOC '19: "Distributed Edge Connectivity ..."
Dalirrooyfard, Mina STOC '19: "Graph Pattern Detection: Hardness ..."
Daskalakis, Constantinos STOC '19: "Regression from Dependent ..."
Diakonikolas, Ilias STOC '19: "Degree-d Chow Parameters ..."
Dikkala, Nishanth STOC '19: "Regression from Dependent ..."
Ding, Jian STOC '19: "Capacity Lower Bound for the ..."
Dobzinski, Shahar STOC '19: "The Communication Complexity ..."
Dudek, Bartłomiej STOC '19: "Computing Quartet Distance ..."
Durfee, David STOC '19: "Fully Dynamic Spectral Vertex ..."
Dvir, Zeev STOC '19: "Static Data Structure Lower ..."
Ellen, Faith STOC '19: "Why Extension-Based Proofs ..."
Ene, Alina STOC '19: "Submodular Maximization with ..."
Farach-Colton, Martin STOC '19: "Achieving Optimal Backlog ..."
Farhadi, Alireza STOC '19: "Lower Bounds for External ..."
Feldman, Moran STOC '19: "Unconstrained Submodular Maximization ..."
Feng, Weiming STOC '19: "Dynamic Sampling from Graphical ..."
Filos-Ratsikas, Aris STOC '19: "The Complexity of Splitting ..."
Fitzsimons, Joseph STOC '19: "Quantum Proof Systems for ..."
Förster, Henry STOC '19: "Planar Graphs of Bounded Degree ..."
Forster, Sebastian STOC '19: "Dynamic Low-Stretch Trees ..."
Ganesh, Arun STOC '19: "Optimal Sequence Length Requirements ..."
Gao, Yu STOC '19: "Fully Dynamic Spectral Vertex ..."
Garg, Jugal STOC '19: "A Strongly Polynomial Algorithm ..."
Gawrychowski, Paweł STOC '19: "Almost Optimal Distance Oracles ..." STOC '19: "Computing Quartet Distance ..."
Gelashvili, Rati STOC '19: "Why Extension-Based Proofs ..."
Gharan, Shayan Oveis STOC '19: "Log-Concave Polynomials II: ..."
Ghodsi, Mohammad STOC '19: "1+\epsilon Approximation of ..."
Gilyén, András STOC '19: "Quantum Singular Value Transformation ..."
Gishboliner, Lior STOC '19: "Testing Graphs against an ..."
Goldberg, Paul W. STOC '19: "The Complexity of Splitting ..."
Goldreich, Oded STOC '19: "Testing Graphs in Vertex-Distribution-Free ..."
Golovnev, Alexander STOC '19: "Static Data Structure Lower ..."
Gopi, Sivakanth STOC '19: "CSPs with Global Modular Constraints: ..."
Goranci, Gramoz STOC '19: "Fully Dynamic Spectral Vertex ..." STOC '19: "Dynamic Low-Stretch Trees ..."
Goyal, Navin STOC '19: "Non-Gaussian Component Analysis ..."
Grandoni, Fabrizio STOC '19: "Oblivious Dimension Reduction ..." STOC '19: "O(\log^2k/\log\log{k})-Approximation ..." STOC '19: "Dynamic Set Cover: Improved ..."
Gronemann, Martin STOC '19: "Planar Graphs of Bounded Degree ..."
Guo, Chenghao STOC '19: "Settling the Sample Complexity ..."
Gupta, Anupam STOC '19: "The Number of Minimum k-Cuts: ..."
Guruswami, Venkatesan STOC '19: "Bridging between 0/1 and Linear ..." STOC '19: "An Exponential Lower Bound ..." STOC '19: "CSPs with Global Modular Constraints: ..."
Hadar, Uri STOC '19: "Communication Complexity of ..."
Haeupler, Bernhard STOC '19: "Near-Linear Time Insertion-Deletion ..."
HajiAghayi, MohammadTaghi STOC '19: "1+\epsilon Approximation of ..."
Hajiaghayi, MohammadTaghi STOC '19: "Lower Bounds for External ..."
Hansen, Thomas Dueholm STOC '19: "Faster k-SAT Algorithms using ..."
He, Kun STOC '19: "Quantum Lovász Local Lemma: ..."
Helmuth, Tyler STOC '19: "Algorithmic Pirogov-Sinai ..."
Henzinger, Monika STOC '19: "Distributed Edge Connectivity ..."
Holmgren, Justin STOC '19: "Fiat-Shamir: From Practice ..." STOC '19: "The Parallel Repetition of ..."
Huang, Zhiyi STOC '19: "Settling the Sample Complexity ..."
Hubacek, Pavel STOC '19: "Finding a Nash Equilibrium ..."
Jain, Vishesh STOC '19: "Mean-Field Approximation, ..."
Ji, Zhengfeng STOC '19: "Quantum Proof Systems for ..."
Jin, Yaonan STOC '19: "Tight Approximation Ratio ..."
Kalai, Yael Tauman STOC '19: "How to Delegate Computations ..."
Kamath, Chethan STOC '19: "Finding a Nash Equilibrium ..."
Kamath, Gautam STOC '19: "The Structure of Optimal Private ..."
Kane, Daniel M. STOC '19: "Degree-d Chow Parameters ..."
Kaplan, Haim STOC '19: "Faster k-SAT Algorithms using ..."
Kapralov, Michael STOC '19: "A Universal Sampling Method ..." STOC '19: "An Optimal Space Lower Bound ..."
Karbasi, Amin STOC '19: "Unconstrained Submodular Maximization ..."
Kawarabayashi, Ken-ichi STOC '19: "Polylogarithmic Approximation ..."
Kayal, Neeraj STOC '19: "Reconstruction of Non-degenerate ..."
Kempa, Dominik STOC '19: "String Synchronizing Sets: ..."
Khanna, Sanjeev STOC '19: "Polynomial Pass Lower Bounds ..." STOC '19: "A New Algorithm for Decremental ..."
Khurana, Dakshita STOC '19: "Weak Zero-Knowledge Beyond ..."
Kociumaka, Tomasz STOC '19: "String Synchronizing Sets: ..."
Koehler, Frederic STOC '19: "Mean-Field Approximation, ..." STOC '19: "Learning Restricted Boltzmann ..."
Kothari, Robin STOC '19: "Exponential Separation between ..."
Koutsoupias, Elias STOC '19: "The Online k-Taxi Problem ..."
Krachun, Dmitry STOC '19: "An Optimal Space Lower Bound ..."
Krokhin, Andrei STOC '19: "Algebraic Approach to Promise ..."
Kumar, Akash STOC '19: "Random Walks and Forbidden ..."
Kunnemann, Marvin STOC '19: "Approximating APSP without ..."
Kuszmaul, William STOC '19: "Achieving Optimal Backlog ..."
Kyng, Rasmus STOC '19: "Flows in Almost Linear Time ..."
Laekhanukit, Bundit STOC '19: "O(\log^2k/\log\log{k})-Approximation ..."
Larsen, Kasper Green STOC '19: "Lower Bounds for External ..."
Lasota, Sławomir STOC '19: "The Reachability Problem for ..."
Lazić, Ranko STOC '19: "The Reachability Problem for ..."
Lee, Euiwoong STOC '19: "The Number of Minimum k-Cuts: ..."
Lee, Yin Tat STOC '19: "Solving Linear Programs in ..." STOC '19: "Competitively Chasing Convex ..."
Leroux, Jérôme STOC '19: "The Reachability Problem for ..."
Li, Jason STOC '19: "Planar Diameter via Metric ..." STOC '19: "The Number of Minimum k-Cuts: ..."
Li, Qian STOC '19: "Quantum Lovász Local Lemma: ..."
Li, Shi STOC '19: "O(\log^2k/\log\log{k})-Approximation ..."
Li, Yuanzhi STOC '19: "Competitively Chasing Convex ..."
Limaye, Nutan STOC '19: "A Fixed-Depth Size-Hierarchy ..."
Linhares, Andre STOC '19: "Approximation Algorithms for ..."
Liu, Jingbo STOC '19: "Communication Complexity of ..."
Liu, Jingcheng STOC '19: "Private Selection from Private ..."
Liu, Kuikui STOC '19: "Log-Concave Polynomials II: ..."
Livni, Roi STOC '19: "Private PAC Learning Implies ..."
Lombardi, Alex STOC '19: "Fiat-Shamir: From Practice ..."
Lovett, Shachar STOC '19: "DNF Sparsification beyond ..."
Low, Guang Hao STOC '19: "Quantum Singular Value Transformation ..." STOC '19: "Hamiltonian Simulation with ..."
Lu, Pinyan STOC '19: "Tight Approximation Ratio ..."
Makarychev, Konstantin STOC '19: "Performance of Johnson–Lindenstrauss ..."
Makarychev, Yury STOC '19: "Performance of Johnson–Lindenstrauss ..."
Malliaris, Maryanthe STOC '19: "Private PAC Learning Implies ..."
Mande, Nikhil S. STOC '19: "The Log-Approximate-Rank Conjecture ..."
Mazowiecki, Filip STOC '19: "The Reachability Problem for ..."
Mchedlidze, Tamara STOC '19: "Planar Graphs of Bounded Degree ..."
McKay, Dylan STOC '19: "Weak Lower Bounds on Resource-Bounded ..."
McMillan, Audra STOC '19: "The Structure of Optimal Private ..."
Meka, Raghu STOC '19: "Pseudorandom Generators for ..."
Moitra, Ankur STOC '19: "Spectral Methods from Tensor ..." STOC '19: "Beyond the Low-Degree Algorithm: ..." STOC '19: "Learning Restricted Boltzmann ..."
Montecchiani, Fabrizio STOC '19: "Planar Graphs of Bounded Degree ..."
Moran, Shay STOC '19: "Private PAC Learning Implies ..."
Mozes, Shay STOC '19: "Almost Optimal Distance Oracles ..."
Murray, Cody STOC '19: "Weak Lower Bounds on Resource-Bounded ..."
Musco, Cameron STOC '19: "A Universal Sampling Method ..."
Musco, Christopher STOC '19: "A Universal Sampling Method ..."
Nakos, Vasileios STOC '19: "Stronger L2/L2 Compressed ..."
Nanongkai, Danupon STOC '19: "Distributed Edge Connectivity ..." STOC '19: "Distributed Exact Weighted ..." STOC '19: "Breaking Quadratic Time for ..."
Narayanan, Shyam STOC '19: "Optimal Terminal Dimensionality ..."
Nelson, Jelani STOC '19: "Optimal Terminal Dimensionality ..."
Nguyen, Huy L. STOC '19: "Submodular Maximization with ..."
Nirkhe, Chinmay STOC '19: "Good Approximate Quantum LDPC ..."
Nisan, Noam STOC '19: "The Communication Complexity ..."
O'Donnell, Ryan STOC '19: "Quantum State Certification ..." STOC '19: "Fooling Polytopes ..."
Opršal, Jakub STOC '19: "Algebraic Approach to Promise ..."
Pach, János STOC '19: "Planar Point Sets Determine ..."
Panageas, Ioannis STOC '19: "Regression from Dependent ..."
Paneth, Omer STOC '19: "How to Delegate Computations ..." STOC '19: "Weak Zero-Knowledge Beyond ..."
Panigrahi, Debmalya STOC '19: "Dynamic Set Cover: Improved ..."
Parter, Merav STOC '19: "Planar Diameter via Metric ..."
Peng, Richard STOC '19: "Fully Dynamic Spectral Vertex ..." STOC '19: "Flows in Almost Linear Time ..."
Perkins, Will STOC '19: "Algorithmic Pirogov-Sinai ..."
Pietrzak, Krzysztof STOC '19: "Finding a Nash Equilibrium ..."
Polyanskiy, Yury STOC '19: "Communication Complexity of ..."
Potechin, Aaron STOC '19: "On the Approximation Resistance ..."
Probst, Maximilian STOC '19: "Decremental Strongly-Connected ..."
Qi, Qi STOC '19: "Tight Approximation Ratio ..."
Quanrud, Kent STOC '19: "Parallelizing Greedy for Submodular ..."
Raftopoulou, Chrysanthi STOC '19: "Planar Graphs of Bounded Degree ..."
Raz, Ran STOC '19: "Oracle Separation of BQP and ..."
Razenshteyn, Ilya STOC '19: "Performance of Johnson–Lindenstrauss ..."
Regts, Guus STOC '19: "Algorithmic Pirogov-Sinai ..."
Reingold, Omer STOC '19: "Pseudorandom Generators for ..."
Risteski, Andrej STOC '19: "Mean-Field Approximation, ..."
Roland, Jérémie STOC '19: "Quantum Weak Coin Flipping ..."
Rosen, Alon STOC '19: "Finding a Nash Equilibrium ..."
Rothblum, Guy N. STOC '19: "Gentle Measurement of Quantum ..." STOC '19: "Fiat-Shamir: From Practice ..." STOC '19: "Finding a Nash Equilibrium ..."
Rothblum, Ron D. STOC '19: "Fiat-Shamir: From Practice ..."
Rubin, Natan STOC '19: "Planar Point Sets Determine ..."
Rubinstein, Aviad STOC '19: "Near-Linear Time Insertion-Deletion ..." STOC '19: "An Optimal Approximation for ..."
Sachdeva, Sushant STOC '19: "Flows in Almost Linear Time ..."
Saha, Barna STOC '19: "Dynamic Set Cover: Improved ..."
Saha, Chandan STOC '19: "Reconstruction of Non-degenerate ..."
Saranurak, Thatchaphol STOC '19: "Distributed Edge Connectivity ..." STOC '19: "Breaking Quadratic Time for ..."
Schaeffer, Luke STOC '19: "Exponential Separation between ..."
Schweitzer, Pascal STOC '19: "A Unifying Method for the ..."
Schwiegelshohn, Chris STOC '19: "Oblivious Dimension Reduction ..."
Seddighin, Saeed STOC '19: "1+\epsilon Approximation of ..."
Sellke, Mark STOC '19: "Competitively Chasing Convex ..."
Servedio, Rocco A. STOC '19: "Fooling Polytopes ..."
Seshadhri, C. STOC '19: "Random Walks and Forbidden ..."
Shahrasbi, Amirbehshad STOC '19: "Near-Linear Time Insertion-Deletion ..."
Shapira, Asaf STOC '19: "Testing Graphs against an ..."
Sharan, Vatsal STOC '19: "Memory-Sample Tradeoffs for ..."
Shayevitz, Ofer STOC '19: "Communication Complexity of ..."
Sherif, Suhail STOC '19: "The Log-Approximate-Rank Conjecture ..."
Sherstov, Alexander A. STOC '19: "Near-Optimal Lower Bounds ..."
Shetty, Abhishek STOC '19: "Non-Gaussian Component Analysis ..."
Shi, Elaine STOC '19: "Lower Bounds for External ..."
Shiragur, Kirankumar STOC '19: "Efficient Profile Maximum ..."
Shpilka, Amir STOC '19: "Sylvester-Gallai Type Theorems ..."
Sidford, Aaron STOC '19: "Efficient Profile Maximum ..." STOC '19: "Memory-Sample Tradeoffs for ..."
Sidiropoulos, Anastasios STOC '19: "Polylogarithmic Approximation ..."
Singer, Yaron STOC '19: "An Optimal Approximation for ..."
Sinha, Sandip STOC '19: "Local Decodability of the ..."
Smith, Adam STOC '19: "The Structure of Optimal Private ..."
Song, Zhao STOC '19: "Solving Linear Programs in ..." STOC '19: "Stronger L2/L2 Compressed ..."
Sreenivasaiah, Karteek STOC '19: "A Fixed-Depth Size-Hierarchy ..."
Srinivasan, Srikanth STOC '19: "A Fixed-Depth Size-Hierarchy ..."
Stolman, Andrew STOC '19: "Random Walks and Forbidden ..."
Su, Hsin-Hao STOC '19: "Towards the Locality of Vizing’s ..."
Su, Yuan STOC '19: "Quantum Singular Value Transformation ..."
Sun, Nike STOC '19: "Capacity Lower Bound for the ..."
Sun, Xiaoming STOC '19: "Quantum Lovász Local Lemma: ..."
Swamy, Chaitanya STOC '19: "Approximation Algorithms for ..." STOC '19: "Approximation Algorithms for ..."
Tal, Avishay STOC '19: "Pseudorandom Generators for ..." STOC '19: "Exponential Separation between ..." STOC '19: "Oracle Separation of BQP and ..."
Talwar, Kunal STOC '19: "Private Selection from Private ..."
Tan, Li-Yang STOC '19: "Fooling Polytopes ..."
Tang, Ewin STOC '19: "A Quantum-Inspired Classical ..."
Tang, Zhihao Gavin STOC '19: "Tight Approximation Ratio ..."
Tardos, Gábor STOC '19: "Planar Point Sets Determine ..."
Tell, Roei STOC '19: "Bootstrapping Results for ..."
Tripathi, Utkarsh STOC '19: "A Fixed-Depth Size-Hierarchy ..."
Ueckerdt, Torsten STOC '19: "Planar Graphs of Bounded Degree ..."
Ullman, Jonathan STOC '19: "The Structure of Optimal Private ..."
Uno, Takeaki STOC '19: "New Polynomial Delay Bounds ..."
Valiant, Gregory STOC '19: "Memory-Sample Tradeoffs for ..."
Végh, László A. STOC '19: "A Strongly Polynomial Algorithm ..."
Velingker, Ameya STOC '19: "A Universal Sampling Method ..."
Venkitesh, S. STOC '19: "A Fixed-Depth Size-Hierarchy ..."
Vidick, Thomas STOC '19: "Quantum Proof Systems for ..."
Vinzant, Cynthia STOC '19: "Log-Concave Polynomials II: ..."
Vishnoi, Nisheeth K. STOC '19: "Dynamic Sampling from Graphical ..."
Vladu, Adrian STOC '19: "Submodular Maximization with ..."
Vu, Hoa T. STOC '19: "Towards the Locality of Vizing’s ..."
Vuong, Thuy Duong STOC '19: "Graph Pattern Detection: Hardness ..."
Waingarten, Erik