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