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

48th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2016), June 19–21, 2016, Cambridge, MA, USA

STOC 2016 – 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'16: "Separations in Query Complexity ..."
Abboud, Amir STOC'16: "The 4/3 Additive Spanner Exponent ..." STOC'16: "Simulating Branching Programs ..."
Ambainis, Andris STOC'16: "Separations in Query Complexity ..."
Applebaum, Benny STOC'16: "Algebraic Attacks against ..."
Aronov, Boris STOC'16: "Almost Tight Bounds for Eliminating ..."
Asharov, Gilad STOC'16: "Searchable Symmetric Encryption: ..."
Assadi, Sepehr STOC'16: "Tight Bounds for Single-Pass ..."
Aziz, Haris STOC'16: "A Discrete and Bounded Envy-Free ..."
Babai, László STOC'16: "Graph Isomorphism in Quasipolynomial ..."
Balodis, Kaspars STOC'16: "Separations in Query Complexity ..."
Bansal, Nikhil STOC'16: "Lift-and-Round to Improve ..."
Bassily, Raef STOC'16: "Algorithmic Stability for ..."
Baswana, Surender STOC'16: "Fault Tolerant Subgraph for ..."
Bateni, MohammadHossein STOC'16: "A PTAS for Planar Group Steiner ..."
Belovs, Aleksandrs STOC'16: "A Polynomial Lower Bound for ..." STOC'16: "Separations in Query Complexity ..."
Ben-David, Shalev STOC'16: "Separations in Query Complexity ..."
Bender, Michael A. STOC'16: "Contention Resolution with ..."
Bernstein, Aaron STOC'16: "Deterministic Decremental ..."
Bhattacharya, Sayan STOC'16: "New Deterministic Approximation ..."
Blais, Eric STOC'16: "A Polynomial Lower Bound for ..."
Bodwin, Greg STOC'16: "The 4/3 Additive Spanner Exponent ..."
Boutsidis, Christos STOC'16: "Optimal Principal Component ..."
Brandt, Sebastian STOC'16: "A Lower Bound for the Distributed ..."
Braverman, Mark STOC'16: "Constant-Rate Coding for Multiparty ..." STOC'16: "Parallel Algorithms for Select ..." STOC'16: "Communication Lower Bounds ..."
Braverman, Vladimir STOC'16: "Beating CountSketch for Heavy ..."
Cai, Yang STOC'16: "A Duality Based Unified Approach ..."
Chakraborty, Diptarka STOC'16: "Streaming Algorithms for Embedding ..."
Chattopadhyay, Eshan STOC'16: "Explicit Two-Source Extractors ..." STOC'16: "Extractors for Sumset Sources ..." STOC'16: "Non-malleable Extractors and ..."
Chechik, Shiri STOC'16: "Deterministic Decremental ..."
Chen, Sitan STOC'16: "Basis Collapse for Holographic ..."
Chen, Xi STOC'16: "Near-Optimal Small-Depth Lower ..."
Chestnut, Stephen R. STOC'16: "Beating CountSketch for Heavy ..."
Choudhary, Keerti STOC'16: "Fault Tolerant Subgraph for ..."
Chuzhoy, Julia STOC'16: "Improved Approximation for ..."
Cohen, Aloni STOC'16: "Watermarking Cryptographic ..."
Cohen, Gil STOC'16: "Two-Source Dispersers for ..."
Cohen, Michael B. STOC'16: "Geometric Median in Nearly ..."
Cohen-Addad, Vincent STOC'16: "Approximating Connectivity ..."
Colin de Verdière, Éric STOC'16: "Approximating Connectivity ..."
Czumaj, Artur STOC'16: "Relating Two Property Testing ..."
Daniely, Amit STOC'16: "Complexity Theoretic Limitations ..."
Dasgupta, Sanjoy STOC'16: "A Cost Function for Similarity-Based ..."
Daskalakis, Constantinos STOC'16: "A Size-Free CLT for Poisson ..."
David, Roee STOC'16: "On the Effect of Randomness ..."
De, Anindya STOC'16: "A Size-Free CLT for Poisson ..."
Demaine, Erik D. STOC'16: "A PTAS for Planar Group Steiner ..."
Devanur, Nikhil R. STOC'16: "The Sample Complexity of Auctions ..." STOC'16: "A Duality Based Unified Approach ..."
Diakonikolas, Ilias STOC'16: "The Fourier Transform of Poisson ..."
Dobzinski, Shahar STOC'16: "Breaking the Logarithmic Barrier ..."
Dughmi, Shaddin STOC'16: "Algorithmic Bayesian Persuasion ..."
Efremenko, Klim STOC'16: "Constant-Rate Coding for Multiparty ..."
Emamjomeh-Zadeh, Ehsan STOC'16: "Deterministic and Probabilistic ..."
Emek, Yuval STOC'16: "Online Matching: Haste Makes ..."
Ene, Alina STOC'16: "Routing under Balance ..."
Evra, Shai STOC'16: "Bounded Degree Cosystolic ..."
Feige, Uriel STOC'16: "On the Effect of Randomness ..."
Feldman, Michal STOC'16: "The Price of Anarchy in Large ..."
Fenner, Stephen STOC'16: "Bipartite Perfect Matching ..."
Fischer, Orr STOC'16: "A Lower Bound for the Distributed ..."
Fomin, Fedor V. STOC'16: "Exact Algorithms via Monotone ..."
Fraigniaud, Pierre STOC'16: "Parallel Exhaustive Search ..."
Frieze, Alan STOC'16: "Separating Subadditive Euclidean ..."
Ganor, Anat STOC'16: "Exponential Separation of ..."
Garg, Ankit STOC'16: "Communication Lower Bounds ..."
Gaspers, Serge STOC'16: "Exact Algorithms via Monotone ..."
Gavinsky, Dmitry STOC'16: "Entangled Simultaneity versus ..."
Gelles, Ran STOC'16: "Constant-Rate Coding for Multiparty ..."
Goldenberg, Elazar STOC'16: "Streaming Algorithms for Embedding ..."
Goldreich, Oded STOC'16: "Matrix Rigidity of Random ..."
Goyal, Vipul STOC'16: "Non-malleable Extractors and ..." STOC'16: "Textbook Non-malleable Commitments ..."
Gurjar, Rohit STOC'16: "Bipartite Perfect Matching ..."
Guruswami, Venkatesan STOC'16: "Repairing Reed-Solomon Codes ..."
Haah, Jeongwan STOC'16: "Sample-Optimal Tomography ..."
Haeupler, Bernhard STOC'16: "Constant-Rate Coding for Multiparty ..."
Hajiaghayi, MohammadTaghi STOC'16: "A PTAS for Planar Group Steiner ..."
Hall, Chris STOC'16: "Ramanujan Coverings of Graphs ..."
Hansen, Thomas Dueholm STOC'16: "Simulating Branching Programs ..."
Harris, David G. STOC'16: "Distributed (Δ+1)-Coloring ..."
Harrow, Aram W. STOC'16: "Sample-Optimal Tomography ..."
Hazan, Elad STOC'16: "The Computational Power of ..."
Henzinger, Monika STOC'16: "A Deterministic Almost-Tight ..." STOC'16: "New Deterministic Approximation ..."
Hirvonen, Juho STOC'16: "A Lower Bound for the Distributed ..."
Holmgren, Justin STOC'16: "Watermarking Cryptographic ..."
Hopkins, Samuel B. STOC'16: "Fast Spectral Algorithms from ..."
Hsu, Justin STOC'16: "Do Prices Coordinate Markets? ..."
Huang, Zhiyi STOC'16: "The Sample Complexity of Auctions ..."
Immorlica, Nicole STOC'16: "The Price of Anarchy in Large ..."
Ivkin, Nikita STOC'16: "Beating CountSketch for Heavy ..."
Ji, Zhengfeng STOC'16: "Classical Verification of ..." STOC'16: "Sample-Optimal Tomography ..."
Kamath, Gautam STOC'16: "A Size-Free CLT for Poisson ..."
Kane, Daniel M. STOC'16: "Super-Linear Gate and Super-Quadratic ..." STOC'16: "The Fourier Transform of Poisson ..."
Kapralov, Michael STOC'16: "Sparse Fourier Transform in ..."
Karger, David R. STOC'16: "Enumerating Parametric Global ..."
Kaufman, Tali STOC'16: "Bounded Degree Cosystolic ..."
Kayal, Neeraj STOC'16: "On the Size of Homogeneous ..."
Keller, Barbara STOC'16: "A Lower Bound for the Distributed ..."
Kempe, David STOC'16: "Deterministic and Probabilistic ..."
Khanna, Sanjeev STOC'16: "Tight Bounds for Single-Pass ..."
Khot, Subhash STOC'16: "Candidate Hard Unique Game ..."
Kim, David H. K. STOC'16: "Improved Approximation for ..."
Klein, Philip N. STOC'16: "Approximating Connectivity ..."
Kol, Gillat STOC'16: "Exponential Separation of ..." STOC'16: "Interactive Compression for ..."
Kopelowitz, Tsvi STOC'16: "Contention Resolution with ..."
Kopparty, Swastik STOC'16: "High-Rate Locally-Correctable ..."
Koren, Tomer STOC'16: "The Computational Power of ..."
Korman, Amos STOC'16: "Parallel Exhaustive Search ..."
Kothari, Robin STOC'16: "Separations in Query Complexity ..."
Koucký, Michal STOC'16: "Streaming Algorithms for Embedding ..."
Krinninger, Sebastian STOC'16: "A Deterministic Almost-Tight ..."
Kudekar, Shrinivas STOC'16: "Reed-Muller Codes Achieve ..."
Kumar, Santhosh STOC'16: "Reed-Muller Codes Achieve ..."
Kutten, Shay STOC'16: "Online Matching: Haste Makes ..."
Kyng, Rasmus STOC'16: "Sparsified Cholesky and Multigrid ..."
Lee, Troy STOC'16: "Separations in Query Complexity ..."
Lee, Yin Tat STOC'16: "Geometric Median in Nearly ..." STOC'16: "Sparsified Cholesky and Multigrid ..."
Lempiäinen, Tuomo STOC'16: "A Lower Bound for the Distributed ..."
Levey, Elaine STOC'16: "A (1+epsilon)-Approximation ..."
Li, Shi STOC'16: "Improved Approximation for ..."
Li, Xin STOC'16: "Extractors for Sumset Sources ..." STOC'16: "Non-malleable Extractors and ..."
Li, Yang STOC'16: "Tight Bounds for Single-Pass ..."
Li, Yi STOC'16: "On Approximating Functions ..."
Lokshtanov, Daniel STOC'16: "Exact Algorithms via Monotone ..."
Lovett, Shachar STOC'16: "Algebraic Attacks against ..."
Lucier, Brendan STOC'16: "The Price of Anarchy in Large ..."
Ma, Tengyu STOC'16: "Communication Lower Bounds ..."
Mackenzie, Simon STOC'16: "A Discrete and Bounded Envy-Free ..."
Mao, Jieming STOC'16: "Parallel Algorithms for Select ..."
Marx, Dániel STOC'16: "A PTAS for Planar Group Steiner ..."
Mathieu, Claire STOC'16: "Approximating Connectivity ..."
Meierfrankenfeld, David STOC'16: "Approximating Connectivity ..."
Meir, Or STOC'16: "High-Rate Locally-Correctable ..."
Miller, Gary STOC'16: "Geometric Median in Nearly ..." STOC'16: "Routing under Balance ..."
Moitra, Ankur STOC'16: "How Robust Are Reconstruction ..."
Mondelli, Marco STOC'16: "Reed-Muller Codes Achieve ..."
Montanari, Andrea STOC'16: "Semidefinite Programs on Sparse ..."
Morgenstern, Jamie STOC'16: "Do Prices Coordinate Markets? ..."
Moshkovitz, Dana STOC'16: "Candidate Hard Unique Game ..."
Nanongkai, Danupon STOC'16: "A Deterministic Almost-Tight ..." STOC'16: "New Deterministic Approximation ..."
Naor, Moni STOC'16: "Searchable Symmetric Encryption: ..."
Nguyen, Huy L. STOC'16: "Communication Lower Bounds ..."
Nikolov, Aleksandar STOC'16: "Maximizing Determinants under ..."
Nishimaki, Ryo STOC'16: "Watermarking Cryptographic ..."
Nissim, Kobbi STOC'16: "Algorithmic Stability for ..."
O'Donnell, Ryan STOC'16: "Efficient Quantum Tomography ..."
Oliveira, Igor C. STOC'16: "Near-Optimal Small-Depth Lower ..."
Pachocki, Jakub STOC'16: "Geometric Median in Nearly ..." STOC'16: "Routing under Balance ..."
Pandey, Omkant STOC'16: "Textbook Non-malleable Commitments ..."
Pegden, Wesley STOC'16: "Separating Subadditive Euclidean ..."
Peng, Pan STOC'16: "Relating Two Property Testing ..."
Peng, Richard STOC'16: "Sparsified Cholesky and Multigrid ..."
Perry, William STOC'16: "How Robust Are Reconstruction ..."
Pettie, Seth STOC'16: "Contention Resolution with ..."
Pfister, Henry D. STOC'16: "Reed-Muller Codes Achieve ..."
Pitassi, Toniann STOC'16: "Poly-logarithmic Frege Depth ..."
Psomas, Christos-Alexandros STOC'16: "The Sample Complexity of Auctions ..."
Puder, Doron STOC'16: "Ramanujan Coverings of Graphs ..."
Raz, Ran STOC'16: "Exponential Separation of ..."
Razenshteyn, Ilya STOC'16: "Weighted Low Rank Approximations ..."
Reingold, Omer STOC'16: "Constant-Round Interactive ..."
Richelson, Silas STOC'16: "Textbook Non-malleable Commitments ..."
Rodeh, Yoav STOC'16: "Parallel Exhaustive Search ..."
Roditty, Liam STOC'16: "Fault Tolerant Subgraph for ..."
Rogers, Ryan STOC'16: "Do Prices Coordinate Markets? ..."
Ron-Zewi, Noga STOC'16: "High-Rate Locally-Correctable ..."
Rossman, Benjamin STOC'16: "Poly-logarithmic Frege Depth ..."
Roth, Aaron STOC'16: "Do Prices Coordinate Markets? ..." STOC'16: "Watch and Learn: Optimizing ..."
Rothblum, Guy N. STOC'16: "Constant-Round Interactive ..."
Rothblum, Ron D. STOC'16: "Constant-Round Interactive ..."
Rothvoss, Thomas STOC'16: "A (1+epsilon)-Approximation ..."
Roughgarden, Tim STOC'16: "The Price of Anarchy in Large ..."
Rubinstein, Aviad STOC'16: "Beyond Matroids: Secretary ..."
Rybicki, Joel STOC'16: "A Lower Bound for the Distributed ..."
Sachdeva, Sushant STOC'16: "Sparsified Cholesky and Multigrid ..."
Saha, Chandan STOC'16: "On the Size of Homogeneous ..."
Santha, Miklos STOC'16: "Separations in Query Complexity ..."
Saptharishi, Ramprasad STOC'16: "Efficiently Decoding Reed-Muller ..."
Saraf, Shubhangi STOC'16: "High-Rate Locally-Correctable ..."
Şaşoğlu, Eren STOC'16: "Reed-Muller Codes Achieve ..."
Saurabh, Saket STOC'16: "Exact Algorithms via Monotone ..."
Sawin, William F. STOC'16: "Ramanujan Coverings of Graphs ..."
Schneider, Johannes STOC'16: "Distributed (Δ+1)-Coloring ..."
Schramm, Tselil STOC'16: "Fast Spectral Algorithms from ..."
Segev, Gil STOC'16: "Searchable Symmetric Encryption: ..."
Sen, Subhabrata STOC'16: "Semidefinite Programs on Sparse ..."
Servedio, Rocco A. STOC'16: "Near-Optimal Small-Depth Lower ..." STOC'16: "Poly-logarithmic Frege Depth ..."
Shahaf, Ido STOC'16: "Searchable Symmetric Encryption: ..."
Sharir, Micha STOC'16: "Almost Tight Bounds for Eliminating ..."
Shi, Jonathan STOC'16: "Fast Spectral Algorithms from ..."
Shpilka, Amir STOC'16: "Efficiently Decoding Reed-Muller ..."
Sidford, Aaron STOC'16: "Geometric Median in Nearly ..." STOC'16: "Routing under Balance ..."
Singh, Mohit STOC'16: "Maximizing Determinants under ..."
Singhal, Vikrant STOC'16: "Deterministic and Probabilistic ..."
Smith, Adam STOC'16: "Algorithmic Stability for ..."
Smotrovs, Juris STOC'16: "Separations in Query Complexity ..."
Sohler, Christian STOC'16: "Relating Two Property Testing ..."
Song, Zhao STOC'16: "Weighted Low Rank Approximations ..."
Spielman, Daniel A. STOC'16: "Sparsified Cholesky and Multigrid ..."
Srinivasan, Aravind STOC'16: "Lift-and-Round to Improve ..."
Steinke, Thomas STOC'16: "Algorithmic Stability for ..."
Stemmer, Uri STOC'16: "Algorithmic Stability for ..."
Steurer, David STOC'16: "Fast Spectral Algorithms from ..."
Stewart, Alistair STOC'16: "The Fourier Transform of Poisson ..."
Su, Hsin-Hao STOC'16: "Distributed (Δ+1)-Coloring ..."
Suomela, Jukka STOC'16: "A Lower Bound for the Distributed ..."
Svensson, Ola STOC'16: "Lift-and-Round to Improve ..."
Syrgkanis, Vasilis STOC'16: "The Price of Anarchy in Large ..."
Tal, Avishay STOC'16: "Matrix Rigidity of Random ..."
Tan, Li-Yang STOC'16: "Near-Optimal Small-Depth Lower ..." STOC'16: "Poly-logarithmic Frege Depth ..."
Tavenas, Sébastien STOC'16: "On the Size of Homogeneous ..."
Thierauf, Thomas STOC'16: "Bipartite Perfect Matching ..."
Tzamos, Christos STOC'16: "A Size-Free CLT for Poisson ..."
Uitto, Jara STOC'16: "A Lower Bound for the Distributed ..."
Ullman, Jonathan STOC'16: "Watch and Learn: Optimizing ..." STOC'16: "Algorithmic Stability for ..."
Urbanke, Rüdiger STOC'16: "Reed-Muller Codes Achieve ..."
Vaikuntanathan, Vinod STOC'16: "Watermarking Cryptographic ..."
Valiant, Gregory