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: "Exploration with Limited Memory: ..." STOC '20: "Separating the Communication ..."
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: "Breaching the 2-Approximation ..." STOC '20: "Unbounded Lower Bound for ..."
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: "Distance Sensitivity Oracles ..." STOC '20: "Constant Girth Approximation ..."
Chen, Lijie STOC '20: "Sharp Threshold Results for ..." STOC '20: "Strong Average-Case Lower ..."
Chen, Sitan STOC '20: "Efficiently Learning Structured ..." STOC '20: "Learning Mixtures of Linear ..."
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: "Interaction Is Necessary for ..." STOC '20: "Private Stochastic Convex ..." 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: "The Karger-Stein Algorithm ..." STOC '20: "Caching with Time Windows ..."
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: "Approximating Text-to-Pattern ..." STOC '20: "Contention Resolution without ..."
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: "A Spectral Approach to Network ..." STOC '20: "Improved Analysis of Higher ..."
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: "Solving Tall Dense Linear ..." STOC '20: "Strong Self-Concordance and ..." STOC '20: "An Improved Cutting Plane ..." STOC '20: "Positive Semidefinite Programming: ..."
Li, Jason STOC '20: "The Karger-Stein Algorithm ..." STOC '20: "Faster Parallel Algorithm ..."
Li, Jerry STOC '20: "Efficiently Learning Structured ..." STOC '20: "Learning Mixtures of Linear ..." STOC '20: "Positive Semidefinite Programming: ..."
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: "Faster Energy Maximization ..." STOC '20: "Constant Girth Approximation ..."
Lokshtanov, Daniel STOC '20: "An Exponential Time Parameterized ..." STOC '20: "Hitting Topological Minors ..."
Lovett, Shachar STOC '20: "Decision List Compression ..." STOC '20: "Improved Bounds for the Sunflower ..." STOC '20: "XOR Lemmas for Resilient Functions ..."
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: "Bipartite TSP in O(1.9999ⁿ) ..." STOC '20: "Detecting and Counting Small ..."
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: "Constant-Factor Approximation ..." STOC '20: "Does Preprocessing Help in ..."
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: "Testing Noisy Linear Functions ..." STOC '20: "Fooling Gaussian PTFs via ..."
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: "Solving Tall Dense Linear ..." STOC '20: "Faster Energy Maximization ..." STOC '20: "Constant Girth Approximation ..."
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: "Solving Tall Dense Linear ..." STOC '20: "Learning Mixtures of 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: "Three-in-a-Tree in Near Linear ..." STOC '20: "Fast Hashing with Strong Concentration ..."
Tian, Kevin STOC '20: "Positive Semidefinite Programming: ..."