STOC 2020
52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020)
Powered by
Conference Publishing Consulting

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020), June 22–26, 2020, Chicago, IL, USA

STOC 2020 – 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

Aamand, Anders STOC '20: "Fast Hashing with Strong Concentration ..."
Abboud, Amir STOC '20: "New Hardness Results for Planar ..."
Alekseev, Yaroslav STOC '20: "Semi-algebraic Proofs, IPS ..."
Alev, Vedat Levi STOC '20: "Improved Analysis of Higher ..."
Alweiss, Ryan STOC '20: "Improved Bounds for the Sunflower ..."
Ambainis, Andris STOC '20: "Quadratic Speedup for Finding ..."
Ameli, Afrouz Jabal STOC '20: "Breaching the 2-Approximation ..."
Amos, Ryan STOC '20: "One-Shot Signatures and Applications ..."
Andoni, Alexandr STOC '20: "Parallel Approximate Undirected ..."
Anshu, Anurag STOC '20: "Entanglement Subvolume Law ..."
Applebaum, Benny STOC '20: "Better Secret Sharing via ..."
Arad, Itai STOC '20: "Entanglement Subvolume Law ..."
Assadi, Sepehr STOC '20: "Separating the Communication ..." STOC '20: "Exploration with Limited Memory: ..."
Balkanski, Eric STOC '20: "A Lower Bound for Parallel ..."
Bansal, Nikhil STOC '20: "Online Vector Balancing and ..."
Behnezhad, Soheil STOC '20: "Stochastic Matching with Few ..."
Beimel, Amos STOC '20: "Better Secret Sharing via ..."
Bender, Michael A. STOC '20: "Contention Resolution without ..."
Berenbrink, Petra STOC '20: "Optimal Time and Space Leader ..."
Bhandari, Siddharth STOC '20: "Improved Bounds for Perfect ..."
Bienkowski, Marcin STOC '20: "Unbounded Lower Bound for ..."
Bitansky, Nir STOC '20: "Post-quantum Zero Knowledge ..."
Borgs, Christian STOC '20: "Efficient Sampling and Counting ..."
Brakensiek, Joshua STOC '20: "Constant-Factor Approximation ..."
Bringmann, Karl STOC '20: "Top-𝑘-Convolution and the ..."
Byrka, Jarosław STOC '20: "Unbounded Lower Bound for ..." STOC '20: "Breaching the 2-Approximation ..."
Cao, Nairen STOC '20: "Efficient Construction of ..."
Chakraborty, Sayantan STOC '20: "Improved Bounds for Perfect ..."
Chan, Timothy M. STOC '20: "Approximating Text-to-Pattern ..."
Chattopadhyay, Eshan STOC '20: "Extractors for Adversarial ..." STOC '20: "XOR Lemmas for Resilient Functions ..."
Chayes, Jennifer STOC '20: "Efficient Sampling and Counting ..."
Chechik, Shiri STOC '20: "Constant Girth Approximation ..." STOC '20: "Distance Sensitivity Oracles ..."
Chen, Lijie STOC '20: "Strong Average-Case Lower ..." STOC '20: "Sharp Threshold Results for ..."
Chen, Sitan STOC '20: "Learning Mixtures of Linear ..." STOC '20: "Efficiently Learning Structured ..."
Chen, Xi STOC '20: "Smoothed Complexity of Local ..."
Chen, Xue STOC '20: "Testing Noisy Linear Functions ..."
Cherapanamjeri, Yeshwanth STOC '20: "Algorithms for Heavy-Tailed ..."
Chia, Nai-Hui STOC '20: "Sampling-Based Sublinear Low-Rank ..." STOC '20: "On the Need for Large Quantum ..."
Christodoulou, George STOC '20: "On the Nisan-Ronen Conjecture ..."
Chung, Kai-Min STOC '20: "On the Need for Large Quantum ..."
Coester, Christian STOC '20: "Unbounded Lower Bound for ..."
Cohen, Sarel STOC '20: "Distance Sensitivity Oracles ..."
Cohen-Addad, Vincent STOC '20: "New Hardness Results for Planar ..."
Cook, James STOC '20: "Catalytic Approaches to the ..."
Coudron, Matthew STOC '20: "Computations with Greater ..."
Dadush, Daniel STOC '20: "A Scaling-Invariant Algorithm ..."
Dagan, Yuval STOC '20: "Interaction Is Necessary for ..."
De, Anindya STOC '20: "Testing Noisy Linear Functions ..."
Derakhshan, Mahsa STOC '20: "Stochastic Matching with Few ..."
Dudek, Bartłomiej STOC '20: "All Non-trivial Variants of ..."
Edmonds, Alexander STOC '20: "The Power of Factorization ..."
Efremenko, Klim STOC '20: "Interactive Error Resilience ..."
Eldan, Ronen STOC '20: "Concentration on the Boolean ..."
Feldman, Moran STOC '20: "The One-Way Communication ..."
Feldman, Vitaly STOC '20: "Private Stochastic Convex ..." STOC '20: "Interaction Is Necessary for ..." STOC '20: "Does Learning Require Memorization? ..."
Feng, Weiming STOC '20: "Fast Sampling and Counting ..."
Filmus, Yuval STOC '20: "AND Testing and Robust Judgement ..."
Fineman, Jeremy T. STOC '20: "Efficient Construction of ..."
Fomin, Fedor V. STOC '20: "Hitting Topological Minors ..."
Gavinsky, Dmitry STOC '20: "Bare Quantum Simultaneity ..."
Gawrychowski, Paweł STOC '20: "All Non-trivial Variants of ..."
Ge, Rong STOC '20: "Estimating Normalizing Constants ..."
Georgiou, Marios STOC '20: "One-Shot Signatures and Applications ..."
Ghaffari, Mohsen STOC '20: "Polylogarithmic-Time Deterministic ..."
Gharan, Shayan Oveis STOC '20: "An Improved Approximation ..."
Giakkoupis, George STOC '20: "Optimal Time and Space Leader ..."
Gilyén, András STOC '20: "Sampling-Based Sublinear Low-Rank ..." STOC '20: "Quadratic Speedup for Finding ..."
Golan, Shay STOC '20: "Approximating Text-to-Pattern ..."
Goldenberg, Elazar STOC '20: "Does Preprocessing Help in ..."
Golovnev, Alexander STOC '20: "Data Structures Meet Cryptography: ..."
Goodman, Jesse STOC '20: "Extractors for Adversarial ..."
Göös, Mika STOC '20: "Automating Cutting Planes ..."
Gosset, David STOC '20: "Entanglement Subvolume Law ..."
Goyal, Vipul STOC '20: "Extractors for Adversarial ..."
Grandoni, Fabrizio STOC '20: "Breaching the 2-Approximation ..."
Grier, Daniel STOC '20: "Interactive Shallow Clifford ..."
Grigoriev, Dima STOC '20: "Semi-algebraic Proofs, IPS ..."
Gross, Renan STOC '20: "Concentration on the Boolean ..."
Guo, Chenghao STOC '20: "Smoothed Complexity of Local ..."
Guo, Heng STOC '20: "Fast Sampling and Counting ..."
Guo, Siyao STOC '20: "Data Structures Meet Cryptography: ..."
Gupta, Anupam STOC '20: "Caching with Time Windows ..." STOC '20: "The Karger-Stein Algorithm ..."
Guruswami, Venkatesan STOC '20: "Optimally Resilient Codes ..." STOC '20: "Arikan Meets Shannon: Polar ..."
Haeupler, Bernhard STOC '20: "Optimally Resilient Codes ..."
Hajiaghayi, MohammadTaghi STOC '20: "Stochastic Matching with Few ..."
Harrow, Aram W. STOC '20: "Classical Algorithms, Correlation ..."
Hatami, Pooya STOC '20: "XOR Lemmas for Resilient Functions ..."
Helmuth, Tyler STOC '20: "Efficient Sampling and Counting ..."
Hirahara, Shuichi STOC '20: "Unexpected Hardness Results ..."
Hirsch, Edward A. STOC '20: "Semi-algebraic Proofs, IPS ..."
Holden, Dhiraj STOC '20: "Non-signaling Proofs with ..."
Holm, Jacob STOC '20: "Fully-Dynamic Planarity Testing ..."
Hopkins, Samuel B. STOC '20: "Algorithms for Heavy-Tailed ..."
Horel, Thibaut STOC '20: "Data Structures Meet Cryptography: ..."
Hosseini, Kaave STOC '20: "XOR Lemmas for Resilient Functions ..."
Huang, Lingxiao STOC '20: "Coresets for Clustering in ..."
Huang, Zhiyi STOC '20: "Online Primal Dual Meets Online ..."
Huiberts, Sophie STOC '20: "A Scaling-Invariant Algorithm ..."
Ikenmeyer, Christian STOC '20: "Implementing Geometric Complexity ..."
Jambulapati, Arun STOC '20: "Positive Semidefinite Programming: ..."
Jeffery, Stacey STOC '20: "Quadratic Speedup for Finding ..."
Jeż, Łukasz STOC '20: "Unbounded Lower Bound for ..."
Jiang, Haotian STOC '20: "Online Vector Balancing and ..." STOC '20: "An Improved Cutting Plane ..."
Jiang, Zhihao STOC '20: "Approximately Stable Committee ..."
Jin, Ce STOC '20: "Sharp Threshold Results for ..."
Kalai, Yael Tauman STOC '20: "Non-signaling Proofs with ..."
Kallaugher, John STOC '20: "Separations and Equivalences ..."
Kandasamy, Umangathan STOC '20: "Implementing Geometric Complexity ..."
Karger, David R. STOC '20: "A Phase Transition and a Quadratic ..."
Karlin, Anna R. STOC '20: "An Improved Approximation ..."
Kathuria, Tarun STOC '20: "Algorithms for Heavy-Tailed ..."
Khandeparkar, Hrishikesh STOC '20: "Separating the Communication ..."
Kiayias, Aggelos STOC '20: "One-Shot Signatures and Applications ..."
Klein, Nathan STOC '20: "An Improved Approximation ..."
Klein, Philip N. STOC '20: "New Hardness Results for Planar ..."
Kling, Peter STOC '20: "Optimal Time and Space Leader ..."
Knudsen, Jakob Bæk Tejs STOC '20: "Fast Hashing with Strong Concentration ..."
Knudsen, Mathias Bæk Tejs STOC '20: "Fast Hashing with Strong Concentration ..."
Kociumaka, Tomasz STOC '20: "Approximating Text-to-Pattern ..."
Kokainis, Martins STOC '20: "Quadratic Speedup for Finding ..."
Kol, Gillat STOC '20: "Interactive Error Resilience ..."
Kopelowitz, Tsvi STOC '20: "Contention Resolution without ..." STOC '20: "Approximating Text-to-Pattern ..."
Koren, Tomer STOC '20: "Private Stochastic Convex ..."
Koroth, Sajin STOC '20: "Automating Cutting Planes ..."
Koucký, Michal STOC '20: "Constant Factor Approximations ..."
Koutsoupias, Elias STOC '20: "On the Nisan-Ronen Conjecture ..."
Kovács, Annamária STOC '20: "On the Nisan-Ronen Conjecture ..."
Kumar, Amit STOC '20: "Caching with Time Windows ..."
Kuszmaul, William STOC '20: "Contention Resolution without ..."
Łącki, Jakub STOC '20: "Walking Randomly, Massively, ..."
Laddha, Aditi STOC '20: "Strong Self-Concordance and ..."
Lai, Ching-Yi STOC '20: "On the Need for Large Quantum ..."
Lai, Kai-Yuan STOC '20: "Three-in-a-Tree in Near Linear ..."
Lau, Lap Chi STOC '20: "Improved Analysis of Higher ..." STOC '20: "A Spectral Approach to Network ..."
Leake, Jonathan STOC '20: "On the Computability of Continuous ..."
Lee, Euiwoong STOC '20: "The Karger-Stein Algorithm ..."
Lee, Holden STOC '20: "Estimating Normalizing Constants ..."
Lee, Yin Tat STOC '20: "Strong Self-Concordance and ..." STOC '20: "Solving Tall Dense Linear ..." STOC '20: "Positive Semidefinite Programming: ..." STOC '20: "An Improved Cutting Plane ..."
Li, Jason STOC '20: "Faster Parallel Algorithm ..." STOC '20: "The Karger-Stein Algorithm ..."
Li, Jerry STOC '20: "Learning Mixtures of Linear ..." STOC '20: "Positive Semidefinite Programming: ..." STOC '20: "Efficiently Learning Structured ..."
Li, Tongyang STOC '20: "Sampling-Based Sublinear Low-Rank ..."
Li, Wenzheng STOC '20: "A Polynomial Lower Bound on ..."
Li, Xin STOC '20: "Extractors for Adversarial ..."
Lifshitz, Noam STOC '20: "AND Testing and Robust Judgement ..."
Lin, Han-Hsuan STOC '20: "Sampling-Based Sublinear Low-Rank ..."
Liu, Mingmou STOC '20: "Lower Bound for Succinct Range ..."
Liu, Paul STOC '20: "A Polynomial Lower Bound on ..."
Liu, Yang P. STOC '20: "Constant Girth Approximation ..." STOC '20: "Faster Energy Maximization ..."
Lokshtanov, Daniel STOC '20: "An Exponential Time Parameterized ..." STOC '20: "Hitting Topological Minors ..."
Lovett, Shachar STOC '20: "XOR Lemmas for Resilient Functions ..." STOC '20: "Decision List Compression ..." STOC '20: "Improved Bounds for the Sunflower ..."
Lu, Hsueh-I STOC '20: "Three-in-a-Tree in Near Linear ..."
Lu, Jianfeng STOC '20: "Estimating Normalizing Constants ..."
Mahabadi, Sepideh STOC '20: "Non-adaptive Adaptive Sampling ..."
Martin, Barnaby STOC '20: "QCSP Monsters and the Demise ..."
Mehraban, Saeed STOC '20: "Classical Algorithms, Correlation ..."
Menda, Sanketh STOC '20: "Computations with Greater ..."
Mertz, Ian STOC '20: "Automating Cutting Planes ..." STOC '20: "Catalytic Approaches to the ..."
Meunier, Pierre-Étienne STOC '20: "The Program-Size Complexity ..."
Miller, Carl A. STOC '20: "The Impossibility of Efficient ..."
Minzer, Dor STOC '20: "AND Testing and Robust Judgement ..."
Misra, Pranabendu STOC '20: "An Exponential Time Parameterized ..."
Mitrović, Slobodan STOC '20: "Walking Randomly, Massively, ..."
Mitzenmacher, Michael STOC '20: "Dynamic Algorithms for LIS ..."
Mohanty, Sidhanth STOC '20: "Explicit Near-Ramanujan Graphs ..." STOC '20: "Lifting Sum-of-Squares Lower ..."
Moitra, Ankur STOC '20: "Efficiently Learning Structured ..."
Mossel, Elchanan STOC '20: "AND Testing and Robust Judgement ..."
Mukhopadhyay, Sagnik STOC '20: "Weighted Min-Cut: Sequential, ..."
Munagala, Kamesh STOC '20: "Approximately Stable Committee ..."
Nakos, Vasileios STOC '20: "Top-𝑘-Convolution and the ..."
Nanongkai, Danupon STOC '20: "Weighted Min-Cut: Sequential, ..."
Natura, Bento STOC '20: "A Scaling-Invariant Algorithm ..."
Nederlof, Jesper STOC '20: "Detecting and Counting Small ..." STOC '20: "Bipartite TSP in O(1.9999ⁿ) ..."
Nikolov, Aleksandar STOC '20: "The Power of Factorization ..."
Nir, Oded STOC '20: "Better Secret Sharing via ..."
Norouzi-Fard, Ashkan STOC '20: "The One-Way Communication ..."
O'Donnell, Ryan STOC '20: "Fooling Gaussian PTFs via ..." STOC '20: "Explicit Near-Ramanujan Graphs ..."
Onak, Krzysztof STOC '20: "Walking Randomly, Massively, ..."
Padmanabhan, Swati STOC '20: "Positive Semidefinite Programming: ..."
Panigrahi, Debmalya STOC '20: "Caching with Time Windows ..."
Panolan, Fahad STOC '20: "Hitting Topological Minors ..."
Paredes, Pedro STOC '20: "Explicit Near-Ramanujan Graphs ..."
Park, Sunoo STOC '20: "Data Structures Meet Cryptography: ..."
Perkins, Will STOC '20: "Efficient Sampling and Counting ..."
Peter, Naty STOC '20: "Better Secret Sharing via ..."
Pettie, Seth STOC '20: "Contention Resolution without ..."
Pilipczuk, Michał STOC '20: "An Exponential Time Parameterized ..."
Pitassi, Toniann STOC '20: "Automating Cutting Planes ..."
Porat, Ely STOC '20: "Approximating Text-to-Pattern ..."
Price, Eric STOC '20: "Separations and Equivalences ..."
Probst Gutenberg, Maximilian STOC '20: "New Algorithms and Hardness ..."
Raghavendra, Prasad STOC '20: "Algorithms for Heavy-Tailed ..." STOC '20: "Lifting Sum-of-Squares Lower ..."
Rasmussen, Peter Michael Reichstein STOC '20: "Fast Hashing with Strong Concentration ..."
Razenshteyn, Ilya STOC '20: "Non-adaptive Adaptive Sampling ..."
Regnault, Damien STOC '20: "The Program-Size Complexity ..."
Ren, Hanlin STOC '20: "Strong Average-Case Lower ..."
Riazanov, Andrii STOC '20: "Arikan Meets Shannon: Polar ..."
Rojas, Cristobal STOC '20: "How to Lose at Monte Carlo: ..."
Rotem, Omer STOC '20: "Constant Girth Approximation ..."
Rotenberg, Eva STOC '20: "Fully-Dynamic Planarity Testing ..."
Rozhoň, Václav STOC '20: "Polylogarithmic-Time Deterministic ..."
Rubinstein, Aviad STOC '20: "Does Preprocessing Help in ..." STOC '20: "Constant-Factor Approximation ..."
Russell, Katina STOC '20: "Efficient Construction of ..."
Saha, Barna STOC '20: "Does Preprocessing Help in ..."
Saks, Michael STOC '20: "Constant Factor Approximations ..."
Sankowski, Piotr STOC '20: "Walking Randomly, Massively, ..."
Saurabh, Saket STOC '20: "An Exponential Time Parameterized ..." STOC '20: "Hitting Topological Minors ..."
Sawlani, Saurabh STOC '20: "Near-Optimal Fully Dynamic ..."
Saxena, Raghuvansh R. STOC '20: "Separating the Communication ..." STOC '20: "Interactive Error Resilience ..."
Schaeffer, Luke STOC '20: "Interactive Shallow Clifford ..."
Seddighin, Saeed STOC '20: "Dynamic Algorithms for LIS ..."
Servedio, Rocco A. STOC '20: "Fooling Gaussian PTFs via ..." STOC '20: "Testing Noisy Linear Functions ..."
Shahrasbi, Amirbehshad STOC '20: "Optimally Resilient Codes ..."
Shangguan, Chong STOC '20: "Combinatorial List-Decoding ..."
Shmueli, Omri STOC '20: "Post-quantum Zero Knowledge ..."
Sidford, Aaron STOC '20: "Constant Girth Approximation ..." STOC '20: "Solving Tall Dense Linear ..." STOC '20: "Faster Energy Maximization ..."
Singer, Yaron STOC '20: "A Lower Bound for Parallel ..."
Singla, Sahil STOC '20: "Online Vector Balancing and ..."
Sinha, Makrand STOC '20: "Online Vector Balancing and ..."
Sokolov, Dmitry STOC '20: "(Semi)Algebraic Proofs over ..."
Soleimanifar, Mehdi STOC '20: "Classical Algorithms, Correlation ..."
Song, Zhao STOC '20: "Learning Mixtures of Linear ..." STOC '20: "Solving Tall Dense Linear ..." STOC '20: "An Improved Cutting Plane ..."
Srinivasan, Srikanth STOC '20: "A Robust Version of Hegedus’s ..."
Starikovskaya, Tatiana STOC '20: "All Non-trivial Variants of ..."
Stein, Clifford STOC '20: "Parallel Approximate Undirected ..."
Svensson, Ola STOC '20: "The One-Way Communication ..."
Talwar, Kunal STOC '20: "Private Stochastic Convex ..."
Tamo, Itzhak STOC '20: "Combinatorial List-Decoding ..."
Tan, Li-Yang STOC '20: "Fooling Gaussian PTFs via ..."
Tang, Ewin STOC '20: "Sampling-Based Sublinear Low-Rank ..."
Tang, Zhihao Gavin STOC '20: "Towards a Better Understanding ..."
Tetali, Prasad STOC '20: "Efficient Sampling and Counting ..."
Thorup, Mikkel STOC '20: "Fast Hashing with Strong Concentration ..." STOC '20: "Three-in-a-Tree in Near Linear ..."
Tian, Kevin STOC '20: "Positive Semidefinite Programming: ..."
Traub, Vera STOC '20: "An Improved Approximation ..." STOC '20: "Reducing Path TSP to TSP ..."
Tripuraneni, Nilesh STOC '20: "Algorithms for Heavy-Tailed ..."
Tzameret, Iddo STOC '20: "Semi-algebraic Proofs, IPS ..."