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: "Katyusha: The First Direct ..." STOC '17: "Finding Approximate Local ..."
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: "Algorithmic Discrepancy Beyond ..." STOC '17: "Faster Space-Efficient Algorithms ..."
Barak, Boaz STOC '17: "Quantum Entanglement, Sum ..."
Bavarian, Mohammad STOC '17: "Hardness Amplification for ..."
Ben-Aroya, Avraham STOC '17: "An Efficient Reduction from ..."
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: "Kernel-Based Methods for Bandit ..." STOC '17: "Local Max-Cut in Smoothed ..."
Bullins, Brian STOC '17: "Finding Approximate Local ..."
Błasiok, Jarosław STOC '17: "Streaming Symmetric Norms ..."
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: "Algorithmic Discrepancy Beyond ..." STOC '17: "Faster Space-Efficient Algorithms ..."
Ge, Rong STOC '17: "Online Service with Delay ..." STOC '17: "Provable Learning of Noisy-or ..."
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: "Quantum Entanglement, Sum ..." STOC '17: "Approximating Rectangles by ..." STOC '17: "Sum of Squares Lower Bounds ..."
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: "Kernel-Based Methods for Bandit ..." STOC '17: "An SDP-Based Algorithm for ..." STOC '17: "Subquadratic Submodular Function ..." STOC '17: "Geodesic Walks in Polytopes ..."
Li, Wei STOC '17: "Deciding Parity Games in Quasipolynomial ..."
Li, Xin STOC '17: "Non-malleable Codes and Extractors ..." STOC '17: "Improved Non-malleable 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: "Efficient Quantum Tomography ..." STOC '17: "Sum of Squares Lower Bounds ..."
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 Service with Delay ..." STOC '17: "Online and Dynamic Algorithms ..."
Panolan, Fahad STOC '17: "Lossy Kernelization ..."
Peebles, John STOC '17: "Sampling Random Spanning Trees ..." STOC '17: "Almost-Linear-Time Algorithms ..."
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: "Sampling Random Spanning Trees ..." STOC '17: "Almost-Linear-Time Algorithms ..."
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: "Addition Is Exponentially ..." STOC '17: "Optimal Mean-Based Algorithms ..."
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: "Formula Lower Bounds via the ..." STOC '17: "Time-Space Hardness of Learning ..."
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: "Hardness Amplification for ..." STOC '17: "A Quantum Linearity Test 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: "Approximate Near Neighbors ..." STOC '17: "Beyond Talagrand Functions: ..."
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 ..."
Xie, Jinyu STOC '17: "Beyond Talagrand Functions: ..."
Yang, Lin F. STOC '17: "Streaming Symmetric Norms ..."
Yao, Penghui STOC '17: "Exponential Separation of ..."
Yazdanbod, Sadra STOC '17: "Settling the Complexity of ..."
Young, Robert STOC '17: "The Integrality Gap of the ..."
Yu, Huacheng STOC '17: "DecreaseKeys Are Expensive ..."
Yu, Nengkun STOC '17: "Exponential Separation of ..."
Yuen, Henry STOC '17: "Hardness Amplification for ..."
Zandieh, Amir STOC '17: "An Adaptive Sublinear-Time ..."
Zdeborova, Lenka STOC '17: "Information-Theoretic Thresholds ..."
Zenklusen, Rico STOC '17: "A Strongly Polynomial Algorithm ..."