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

49th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2017), June 19–23, 2017, Montreal, Canada

STOC 2017 – 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 '17: "The Computational Complexity ..."
Abolhassani, Melika STOC '17: "Beating 1-1/e for Ordered ..."
Agarwal, Naman STOC '17: "Finding Approximate Local ..."
Allen-Zhu, Zeyuan STOC '17: "Finding Approximate Local ..." STOC '17: "Katyusha: The First Direct ..."
Alman, Josh STOC '17: "Probabilistic Rank and Matrix ..."
Ambainis, Andris STOC '17: "Quantum Algorithm for Tree ..."
Anari, Nima STOC '17: "A Generalization of Permanent ..."
Andoni, Alexandr STOC '17: "Approximate Near Neighbors ..."
Angel, Omer STOC '17: "Local Max-Cut in Smoothed ..."
Angelidakis, Haris STOC '17: "Algorithms for Stable and ..."
Anshu, Anurag STOC '17: "Exponential Separation of ..."
Arora, Sanjeev STOC '17: "Provable Learning of Noisy-or ..."
Artmann, Stephan STOC '17: "A Strongly Polynomial Algorithm ..."
Arvind, V. STOC '17: "Randomized Polynomial Time ..."
Azar, Yossi STOC '17: "Online Service with Delay ..."
Babaioff, Moshe STOC '17: "The Menu-Size Complexity of ..."
Babichenko, Yakov STOC '17: "Communication Complexity of ..."
Balkanski, Eric STOC '17: "The Limitations of Optimization ..."
Ball, Marshall STOC '17: "Average-Case Fine-Grained ..."
Bansal, Nikhil STOC '17: "Faster Space-Efficient Algorithms ..." STOC '17: "Algorithmic Discrepancy Beyond ..."
Barak, Boaz STOC '17: "Quantum Entanglement, Sum ..."
Bavarian, Mohammad STOC '17: "Hardness Amplification for ..."
Ben-Aroya, Avraham STOC '17: "An Efficient Reduction from ..."
Błasiok, Jarosław STOC '17: "Streaming Symmetric Norms ..."
Bouland, Adam STOC '17: "The Computational Complexity ..."
Brakerski, Zvika STOC '17: "Non-interactive Delegation ..."
Braverman, Vladimir STOC '17: "Streaming Symmetric Norms ..."
Bubeck, Sébastien STOC '17: "Local Max-Cut in Smoothed ..." STOC '17: "Kernel-Based Methods for Bandit ..."
Bullins, Brian STOC '17: "Finding Approximate Local ..."
Cai, Jin-Yi STOC '17: "Holographic Algorithm with ..."
Cai, Yang STOC '17: "Simple Mechanisms for Subadditive ..."
Calude, Cristian S. STOC '17: "Deciding Parity Games in Quasipolynomial ..."
Canetti, Ran STOC '17: "Equivocating Yao: Constant-Round ..."
Cevher, Volkan STOC '17: "An Adaptive Sublinear-Time ..."
Chakrabarty, Deeparnab STOC '17: "Subquadratic Submodular Function ..."
Chang, Yi-Jun STOC '17: "Exponential Separations in ..."
Charikar, Moses STOC '17: "Learning from Untrusted Data ..."
Chattopadhyay, Eshan STOC '17: "Non-malleable Codes and Extractors ..."
Chawla, Shuchi STOC '17: "Stability of Service under ..."
Chen, Xi STOC '17: "Addition Is Exponentially ..." STOC '17: "Beyond Talagrand Functions: ..."
Chestnut, Stephen R. STOC '17: "Streaming Symmetric Norms ..."
Christiani, Tobias STOC '17: "Set Similarity Search Beyond ..."
Chuzhoy, Julia STOC '17: "New Hardness Results for Routing ..."
Cohen, Gil STOC '17: "Towards Optimal Two-Source ..."
Cohen, Michael B. STOC '17: "Almost-Linear-Time Algorithms ..."
Coja-Oghlan, Amin STOC '17: "Information-Theoretic Thresholds ..."
Curticapean, Radu STOC '17: "Homomorphisms Are a Good Basis ..."
Dagan, Yuval STOC '17: "Twenty (Simple) Questions ..."
Dahlgaard, Søren STOC '17: "Finding Even Cycles Faster ..."
De, Anindya STOC '17: "Optimal Mean-Based Algorithms ..."
Dell, Holger STOC '17: "Homomorphisms Are a Good Basis ..."
Devanur, Nikhil R. STOC '17: "Stability of Service under ..."
Doron, Dean STOC '17: "An Efficient Reduction from ..."
Dughmi, Shaddin STOC '17: "Bernoulli Factories and Black-Box ..."
Durfee, David STOC '17: "Sampling Random Spanning Trees ..."
Eenberg, Kasper STOC '17: "DecreaseKeys Are Expensive ..."
Ehsani, Soheil STOC '17: "Beating 1-1/e for Ordered ..."
Eldan, Ronen STOC '17: "Kernel-Based Methods for Bandit ..."
Elkin, Michael STOC '17: "Distributed Exact Shortest ..."
Esfandiari, Hossein STOC '17: "Beating 1-1/e for Ordered ..."
Fan, Zhou STOC '17: "How Well Do Local Algorithms ..."
Feige, Uriel STOC '17: "Approximate Modularity Revisited ..."
Feldman, Michal STOC '17: "Approximate Modularity Revisited ..."
Filmus, Yuval STOC '17: "Twenty (Simple) Questions ..."
Forbes, Michael A. STOC '17: "Succinct Hitting Sets and ..."
Foster, Nate STOC '17: "The Next 700 Network Programming ..."
Fu, Zhiguo STOC '17: "Holographic Algorithm with ..."
Gabizon, Ariel STOC '17: "Twenty (Simple) Questions ..."
Ganesh, Arun STOC '17: "Online Service with Delay ..."
Garg, Ankit STOC '17: "Algorithmic and Optimization ..."
Garg, Jugal STOC '17: "Settling the Complexity of ..."
Garg, Shashwat STOC '17: "Faster Space-Efficient Algorithms ..." STOC '17: "Algorithmic Discrepancy Beyond ..."
Ge, Rong STOC '17: "Provable Learning of Noisy-or ..." STOC '17: "Online Service with Delay ..."
Ghaffari, Mohsen STOC '17: "On the Complexity of Local ..."
Gharan, Shayan Oveis STOC '17: "A Generalization of Permanent ..."
Gishboliner, Lior STOC '17: "Removal Lemmas with Polynomial ..."
Gonczarowski, Yannai A. STOC '17: "Efficient Empirical Revenue ..." STOC '17: "The Menu-Size Complexity of ..."
Grandoni, Fabrizio STOC '17: "Surviving in Directed Graphs: ..."
Guo, Heng STOC '17: "Uniform Sampling through the ..."
Gupta, Anupam STOC '17: "Online and Dynamic Algorithms ..."
Gurjar, Rohit STOC '17: "Linear Matroid Intersection ..."
Gurvits, Leonid STOC '17: "Algorithmic and Optimization ..."
Haeupler, Bernhard STOC '17: "Synchronization Strings: Codes ..."
HajiAghayi, MohammadTaghi STOC '17: "Beating 1-1/e for Ordered ..."
Hartline, Jason D. STOC '17: "Bernoulli Factories and Black-Box ..."
Hazan, Elad STOC '17: "Finding Approximate Local ..."
Holmgren, Justin STOC '17: "Non-interactive Delegation ..."
Holroyd, Alexander E. STOC '17: "Stability of Service under ..."
Hoza, William M. STOC '17: "Targeted Pseudorandom Generators, ..."
Im, Sungjin STOC '17: "Efficient Massively Parallel ..."
Italiano, Giuseppe F. STOC '17: "Decremental Single-Source ..."
Iwata, Satoru STOC '17: "A Weighted Linear Matroid ..."
Jain, Sanjay STOC '17: "Deciding Parity Games in Quasipolynomial ..."
Jerrum, Mark STOC '17: "Uniform Sampling through the ..."
Ji, Zhengfeng STOC '17: "Compression of Quantum Multi-prover ..."
Joglekar, Pushkar S STOC '17: "Randomized Polynomial Time ..."
Kabanets, Valentine STOC '17: "A Polynomial Restriction Lemma ..."
Kalai, Yael STOC '17: "Non-interactive Delegation ..."
Kane, Daniel M. STOC '17: "A Polynomial Restriction Lemma ..."
Kapralov, Michael STOC '17: "An Adaptive Sublinear-Time ..."
Karczmarz, Adam STOC '17: "Decremental Single-Source ..."
Karlin, Anna R. STOC '17: "Stability of Service under ..."
Kelner, Jonathan STOC '17: "Almost-Linear-Time Algorithms ..."
Khot, Subhash STOC '17: "On Independent Sets, 2-to-2 ..."
Khoussainov, Bakhadyr STOC '17: "Deciding Parity Games in Quasipolynomial ..."
Kim, David H. K. STOC '17: "New Hardness Results for Routing ..."
Kleinberg, Robert STOC '17: "Bernoulli Factories and Black-Box ..." STOC '17: "Beating 1-1/e for Ordered ..."
Knudsen, Mathias Bæk Tejs STOC '17: "Finding Even Cycles Faster ..."
Kobayashi, Yusuke STOC '17: "A Weighted Linear Matroid ..."
Kokainis, Martins STOC '17: "Quantum Algorithm for Tree ..."
Kol, Gillat STOC '17: "Time-Space Hardness of Learning ..."
Kopelowitz, Tsvi STOC '17: "Exponential Separations in ..."
Kothari, Pravesh K. STOC '17: "Sum of Squares Lower Bounds ..." STOC '17: "Approximating Rectangles by ..." STOC '17: "Quantum Entanglement, Sum ..."
Krauthgamer, Robert STOC '17: "Streaming Symmetric Norms ..."
Krishnaswamy, Ravishankar STOC '17: "Online and Dynamic Algorithms ..."
Krzakala, Florent STOC '17: "Information-Theoretic Thresholds ..."
Kuhn, Fabian STOC '17: "On the Complexity of Local ..."
Kumar, Amit STOC '17: "Online and Dynamic Algorithms ..."
Kuperberg, Greg STOC '17: "The Computational Complexity ..."
Kupferman, Orna STOC '17: "Examining Classical Graph-Theory ..."
Kyng, Rasmus STOC '17: "Sampling Random Spanning Trees ..."
Łącki, Jakub STOC '17: "Decremental Single-Source ..."
Laekhanukit, Bundit STOC '17: "Surviving in Directed Graphs: ..."
Larsen, Kasper Green STOC '17: "DecreaseKeys Are Expensive ..."
Lee, Yin Tat STOC '17: "Subquadratic Submodular Function ..." STOC '17: "An SDP-Based Algorithm for ..." STOC '17: "Kernel-Based Methods for Bandit ..." STOC '17: "Geodesic Walks in Polytopes ..."
Li, Wei STOC '17: "Deciding Parity Games in Quasipolynomial ..."
Li, Xin STOC '17: "Improved Non-malleable Extractors, ..." STOC '17: "Non-malleable Codes and Extractors ..."
Liu, Jingcheng STOC '17: "Uniform Sampling through the ..."
Lokshtanov, Daniel STOC '17: "Lossy Kernelization ..."
Lu, Zhenjian STOC '17: "A Polynomial Restriction Lemma ..."
Lucier, Brendan STOC '17: "Beating 1-1/e for Ordered ..."
Ma, Tengyu STOC '17: "Provable Learning of Noisy-or ..." STOC '17: "Finding Approximate Local ..."
Makarychev, Konstantin STOC '17: "Algorithms for Stable and ..."
Makarychev, Yury STOC '17: "Algorithms for Stable and ..."
Manurangsi, Pasin STOC '17: "Almost-Polynomial Ratio ETH-Hardness ..."
Martens, Wim STOC '17: "Optimizing Tree Pattern Queries: ..."
Martin, James B. STOC '17: "Stability of Service under ..."
Marx, Dániel STOC '17: "Homomorphisms Are a Good Basis ..."
Maus, Yannic STOC '17: "On the Complexity of Local ..."
Mehraban, Saeed STOC '17: "The Computational Complexity ..."
Mehta, Ruta STOC '17: "Settling the Complexity of ..."
Meka, Raghu STOC '17: "Approximating Rectangles by ..."
Meunier, Pierre-Étienne STOC '17: "The Non-cooperative Tile Assembly ..."
Minzer, Dor STOC '17: "On Independent Sets, 2-to-2 ..."
Moitra, Ankur STOC '17: "Approximate Counting, the ..."
Montanari, Andrea STOC '17: "How Well Do Local Algorithms ..."
Moran, Shay STOC '17: "Twenty (Simple) Questions ..."
Mori, Ryuhei STOC '17: "Sum of Squares Lower Bounds ..."
Moseley, Benjamin STOC '17: "Efficient Massively Parallel ..."
Mukhopadhyay, Partha STOC '17: "Randomized Polynomial Time ..."
Nanongkai, Danupon STOC '17: "Dynamic Spanning Forest with ..."
Naor, Assaf STOC '17: "The Integrality Gap of the ..."
Natarajan, Anand STOC '17: "A Quantum Linearity Test for ..."
Nazarov, Fedor STOC '17: "Trace Reconstruction with ..."
Nederlof, Jesper STOC '17: "Faster Space-Efficient Algorithms ..."
Nguyen, Danny STOC '17: "Complexity of Short Presburger ..."
Nguyen, Huy L. STOC '17: "Approximate Near Neighbors ..."
Niazadeh, Rad STOC '17: "Bernoulli Factories and Black-Box ..."
Nikolaenko, Valeria STOC '17: "Practical Post-quantum Key ..."
Nikolov, Aleksandar STOC '17: "Approximate Near Neighbors ..."
Nimavat, Rachit STOC '17: "New Hardness Results for Routing ..."
Nisan, Noam STOC '17: "Efficient Empirical Revenue ..." STOC '17: "The Menu-Size Complexity of ..."
O'Donnell, Ryan STOC '17: "Optimal Mean-Based Algorithms ..." STOC '17: "Sum of Squares Lower Bounds ..." STOC '17: "Efficient Quantum Tomography ..."
Oliveira, Igor C. STOC '17: "Addition Is Exponentially ..." STOC '17: "Pseudodeterministic Constructions ..."
Oliveira, Rafael STOC '17: "Algorithmic and Optimization ..."
Olver, Neil STOC '17: "A Simpler and Faster Strongly ..."
Pagh, Rasmus STOC '17: "Set Similarity Search Beyond ..."
Pak, Igor STOC '17: "Complexity of Short Presburger ..."
Pandurangan, Gopal STOC '17: "A Time- and Message-Optimal ..."
Panigrahi, Debmalya STOC '17: "Online and Dynamic Algorithms ..." STOC '17: "Online Service with Delay ..."
Panolan, Fahad STOC '17: "Lossy Kernelization ..."
Peebles, John STOC '17: "Almost-Linear-Time Algorithms ..." STOC '17: "Sampling Random Spanning Trees ..."
Peikert, Chris STOC '17: "Pseudorandomness of Ring-LWE ..."
Peng, Richard STOC '17: "Almost-Linear-Time Algorithms ..."
Peres, Yuval STOC '17: "Trace Reconstruction with ..." STOC '17: "Local Max-Cut in Smoothed ..."
Perkins, Will STOC '17: "Information-Theoretic Thresholds ..."
Pettie, Seth STOC '17: "Exponential Separations in ..."
Pitassi, Toniann STOC '17: "Strongly Exponential Lower ..."
Poburinnaya, Oxana STOC '17: "Equivocating Yao: Constant-Round ..."
Raghavendra, Prasad STOC '17: "Strongly Refuting Random CSPs ..." STOC '17: "Approximating Rectangles by ..."
Raja, S. STOC '17: "Randomized Polynomial Time ..."
Ramanujan, M. S. STOC '17: "Lossy Kernelization ..."
Rao, Anup B. STOC '17: "Almost-Linear-Time Algorithms ..." STOC '17: "Sampling Random Spanning Trees ..."
Rao, Satish STOC '17: "Strongly Refuting Random CSPs ..."
Raz, Ran STOC '17: "Time-Space Hardness of Learning ..."
Razenshteyn, Ilya STOC '17: "Approximate Near Neighbors ..."
Regev, Oded STOC '17: "Pseudorandomness of Ring-LWE ..." STOC '17: "A Reverse Minkowski Theorem ..."
Risteski, Andrej STOC '17: "Provable Learning of Noisy-or ..."
Robere, Robert STOC '17: "Strongly Exponential Lower ..."
Robinson, Peter STOC '17: "A Time- and Message-Optimal ..."
Rosen, Alon STOC '17: "Average-Case Fine-Grained ..."
Roughgarden, Tim STOC '17: "Why Prices Need Algorithms ..."
Rubinstein, Aviad STOC '17: "The Limitations of Optimization ..." STOC '17: "Communication Complexity of ..."
Rudra, Atri STOC '17: "Answering FAQs in CSPs, Probabilistic ..."
Sabin, Manuel STOC '17: "Average-Case Fine-Grained ..."
Sachdeva, Sushant STOC '17: "Sampling Random Spanning Trees ..."
Safra, Muli STOC '17: "On Independent Sets, 2-to-2 ..."
Sankowski, Piotr STOC '17: "Decremental Single-Source ..."
Santhanam, Rahul STOC '17: "Pseudodeterministic Constructions ..."
Saranurak, Thatchaphol STOC '17: "Dynamic Spanning Forest with ..."
Saurabh, Saket STOC '17: "Lossy Kernelization ..."
Scarlett, Jonathan STOC '17: "An Adaptive Sublinear-Time ..."
Schramm, Tselil STOC '17: "Strongly Refuting Random CSPs ..."
Scquizzato, Michele STOC '17: "A Time- and Message-Optimal ..."
Servedio, Rocco A. STOC '17: "Optimal Mean-Based Algorithms ..." STOC '17: "Addition Is Exponentially ..."
Shahrasbi, Amirbehshad STOC '17: "Synchronization Strings: Codes ..."
Shapira, Asaf STOC '17: "Removal Lemmas with Polynomial ..."
Sherman, Jonah STOC '17: "Area-Convexity, ℓ ..."
Shpilka, Amir STOC '17: "Succinct Hitting Sets and ..."
Sidford, Aaron STOC '17: "Subquadratic Submodular Function ..." STOC '17: "Almost-Linear-Time Algorithms ..."
Singer, Yaron STOC '17: "The Limitations of Optimization ..."
Sivan, Balasubramanian STOC '17: "Stability of Service under ..."
Song, Zhao STOC '17: "Low Rank Approximation with ..."
Steinhardt, Jacob STOC '17: "Learning from Untrusted Data ..."
Stephan, Frank STOC '17: "Deciding Parity Games in Quasipolynomial ..."
Stephens-Davidowitz, Noah STOC '17: "Pseudorandomness of Ring-LWE ..." STOC '17: "A Reverse Minkowski Theorem ..."
Steurer, David STOC '17: "Quantum Entanglement, Sum ..."
Stöckel, Morten STOC '17: "Finding Even Cycles Faster ..."
Straszak, Damian STOC '17: "Real Stable Polynomials and ..."
Sun, He STOC '17: "An SDP-Based Algorithm for ..."
Sun, Xiaorui STOC '17: "Efficient Massively Parallel ..."
Syrgkanis, Vasilis STOC '17: "Fast Convergence of Learning ..."
Tal, Avishay STOC '17: "Time-Space Hardness of Learning ..." STOC '17: "Formula Lower Bounds via the ..."
Talgam-Cohen, Inbal STOC '17: "Why Prices Need Algorithms ..." STOC '17: "Approximate Modularity Revisited ..."
Ta-Shma, Amnon STOC '17: "An Efficient Reduction from ..." STOC '17: "Explicit, Almost Optimal, ..."
Thierauf, Thomas STOC '17: "Linear Matroid Intersection ..."
Touchette, Dave STOC '17: "Exponential Separation of ..."
Umans, Chris STOC '17: "Targeted Pseudorandom Generators, ..."
Valiant, Gregory STOC '17: "Learning from Untrusted Data ..."
Vasudevan, Prashant Nalini STOC '17: "Average-Case Fine-Grained ..."
Vazirani, Vijay V. STOC '17: "Settling the Complexity of ..."
Végh, László A. STOC '17: "A Simpler and Faster Strongly ..."
Vempala, Santosh S. STOC '17: "Geodesic Walks in Polytopes ..."
Venkitasubramaniam, Muthuramakrishnan STOC '17: "Equivocating Yao: Constant-Round ..."
Vidick, Thomas STOC '17: "A Quantum Linearity Test for ..." STOC '17: "Hardness Amplification for ..."
Vishnoi, Nisheeth K. STOC '17: "Real Stable Polynomials and ..."
Vladu, Adrian STOC '17: "Almost-Linear-Time Algorithms ..."
Volk, Ben Lee STOC '17: "Succinct Hitting Sets and ..."
Vyas, Nikhil STOC '17: "Faster Space-Efficient Algorithms ..."
Waingarten, Erik STOC '17: "Beyond Talagrand Functions: ..." STOC '17: "Approximate Near Neighbors ..."
Wang, Ruosong STOC '17: "Exponential Separations in ..."
Wei, Fan STOC '17: "Local Max-Cut in Smoothed ..."
Weismantel, Robert STOC '17: "A Strongly Polynomial Algorithm ..."
Wigderson, Avi STOC '17: "Algorithmic and Optimization ..."
Williams, Ryan STOC '17: "Probabilistic Rank and Matrix ..."
Witmer, David STOC '17: "Sum of Squares Lower Bounds ..."
Wong, Sam Chiu-wai STOC '17: "Subquadratic Submodular Function ..."
Woodruff, David P. STOC '17: "Low Rank Approximation with ..."
Woods, Damien STOC '17: "The Non-cooperative Tile Assembly ..."
Wright, John STOC '17: "Efficient Quantum Tomography ..."
Wulff-Nilsen, Christian STOC '17: "Fully-Dynamic Minimum Spanning ..."