STOC 2016 – Author Index

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 ..." Separations in Query Complexity using Cheat Sheets Scott Aaronson, Shalev Ben-David, and Robin Kothari (Massachusetts Institute of Technology, USA) @InProceedings{STOC16p981, author = {Scott Aaronson and Shalev Ben-David and Robin Kothari}, title = {Separations in Query Complexity using Cheat Sheets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {981-980}, doi = {}, year = {2016}, } Article: stoc16main-main423-p (type: Full Paper (14 pages)) doi:
	Abboud, Amir	STOC '16: "The 4/3 Additive Spanner Exponent ..." The 4/3 Additive Spanner Exponent Is Tight Amir Abboud and Greg Bodwin (Stanford University, USA) @InProceedings{STOC16p407, author = {Amir Abboud and Greg Bodwin}, title = {The 4/3 Additive Spanner Exponent Is Tight}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {407-406}, doi = {}, year = {2016}, } Article: stoc16main-main234-p (type: Full Paper (14 pages)) doi: STOC '16: "Simulating Branching Programs ..." Simulating Branching Programs with Edit Distance and Friends: Or: A Polylog Shaved Is a Lower Bound Made Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams (Stanford University, USA; Aarhus University, Denmark) @InProceedings{STOC16p435, author = {Amir Abboud and Thomas Dueholm Hansen and Virginia Vassilevska Williams and Ryan Williams}, title = {Simulating Branching Programs with Edit Distance and Friends: Or: A Polylog Shaved Is a Lower Bound Made}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {435-434}, doi = {}, year = {2016}, } Article: stoc16main-main451-p (type: Full Paper (14 pages)) doi:
	Ambainis, Andris	STOC '16: "Separations in Query Complexity ..." Separations in Query Complexity Based on Pointer Functions Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs (University of Latvia, Latvia; CWI, Netherlands; Nanyang Technological University, Singapore; National University of Singapore, Singapore; CNRS, France) @InProceedings{STOC16p911, author = {Andris Ambainis and Kaspars Balodis and Aleksandrs Belovs and Troy Lee and Miklos Santha and Juris Smotrovs}, title = {Separations in Query Complexity Based on Pointer Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {911-910}, doi = {}, year = {2016}, } Article: stoc16main-main123-p (type: Full Paper (14 pages)) doi:
	Applebaum, Benny	STOC '16: "Algebraic Attacks against ..." Algebraic Attacks against Random Local Functions and Their Countermeasures Benny Applebaum and Shachar Lovett (Tel Aviv University, Israel; University of California at San Diego, USA) @InProceedings{STOC16p1233, author = {Benny Applebaum and Shachar Lovett}, title = {Algebraic Attacks against Random Local Functions and Their Countermeasures}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1233-1232}, doi = {}, year = {2016}, } Article: stoc16main-main230-p (type: Full Paper (14 pages)) doi:
	Aronov, Boris	STOC '16: "Almost Tight Bounds for Eliminating ..." Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions Boris Aronov and Micha Sharir (New York University, USA; Tel Aviv University, Israel) @InProceedings{STOC16p1, author = {Boris Aronov and Micha Sharir}, title = {Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1-0}, doi = {}, year = {2016}, } Article: stoc16main-main171-p (type: Full Paper (14 pages)) doi:
	Asharov, Gilad	STOC '16: "Searchable Symmetric Encryption: ..." Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations Gilad Asharov, Moni Naor, Gil Segev, and Ido Shahaf (IBM Research, USA; Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel) @InProceedings{STOC16p1247, author = {Gilad Asharov and Moni Naor and Gil Segev and Ido Shahaf}, title = {Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1247-1246}, doi = {}, year = {2016}, } Article: stoc16main-main256-p (type: Full Paper (14 pages)) doi:
	Assadi, Sepehr	STOC '16: "Tight Bounds for Single-Pass ..." Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem Sepehr Assadi, Sanjeev Khanna, and Yang Li (University of Pennsylvania, USA) @InProceedings{STOC16p799, author = {Sepehr Assadi and Sanjeev Khanna and Yang Li}, title = {Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {799-798}, doi = {}, year = {2016}, } Article: stoc16main-main319-p (type: Full Paper (14 pages)) doi:
	Aziz, Haris	STOC '16: "A Discrete and Bounded Envy-Free ..." A Discrete and Bounded Envy-Free Cake Cutting Protocol for Four Agents Haris Aziz and Simon Mackenzie (Data61, Australia; UNSW, Australia) @InProceedings{STOC16p519, author = {Haris Aziz and Simon Mackenzie}, title = {A Discrete and Bounded Envy-Free Cake Cutting Protocol for Four Agents}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {519-518}, doi = {}, year = {2016}, } Article: stoc16main-main121-p (type: Full Paper (14 pages)) doi:
	Babai, László	STOC '16: "Graph Isomorphism in Quasipolynomial ..." Graph Isomorphism in Quasipolynomial Time [Extended Abstract] László Babai (University of Chicago, USA) @InProceedings{STOC16p785, author = {László Babai}, title = {Graph Isomorphism in Quasipolynomial Time [Extended Abstract]}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {785-784}, doi = {}, year = {2016}, } Article: stoc16main-main187-p (type: Full Paper (14 pages)) doi:
	Balodis, Kaspars	STOC '16: "Separations in Query Complexity ..." Separations in Query Complexity Based on Pointer Functions Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs (University of Latvia, Latvia; CWI, Netherlands; Nanyang Technological University, Singapore; National University of Singapore, Singapore; CNRS, France) @InProceedings{STOC16p911, author = {Andris Ambainis and Kaspars Balodis and Aleksandrs Belovs and Troy Lee and Miklos Santha and Juris Smotrovs}, title = {Separations in Query Complexity Based on Pointer Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {911-910}, doi = {}, year = {2016}, } Article: stoc16main-main123-p (type: Full Paper (14 pages)) doi:
	Bansal, Nikhil	STOC '16: "Lift-and-Round to Improve ..." Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines Nikhil Bansal, Aravind Srinivasan, and Ola Svensson (Eindhoven University of Technology, Netherlands; University of Maryland, USA; EPFL, Switzerland) @InProceedings{STOC16p169, author = {Nikhil Bansal and Aravind Srinivasan and Ola Svensson}, title = {Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {169-168}, doi = {}, year = {2016}, } Article: stoc16main-main307-p (type: Full Paper (14 pages)) doi:
	Bassily, Raef	STOC '16: "Algorithmic Stability for ..." Algorithmic Stability for Adaptive Data Analysis Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman (University of California at San Diego, USA; Ben-Gurion University of the Negev, Israel; Harvard University, USA; Pennsylvania State University, USA; Northeastern University, USA) @InProceedings{STOC16p1191, author = {Raef Bassily and Kobbi Nissim and Adam Smith and Thomas Steinke and Uri Stemmer and Jonathan Ullman}, title = {Algorithmic Stability for Adaptive Data Analysis}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1191-1190}, doi = {}, year = {2016}, } Article: stoc16main-main278-p (type: Full Paper (14 pages)) doi:
	Baswana, Surender	STOC '16: "Fault Tolerant Subgraph for ..." Fault Tolerant Subgraph for Single Source Reachability: Generic and Optimal Surender Baswana, Keerti Choudhary, and Liam Roditty (IIT Kanpur, India; Bar-Ilan University, Israel) @InProceedings{STOC16p589, author = {Surender Baswana and Keerti Choudhary and Liam Roditty}, title = {Fault Tolerant Subgraph for Single Source Reachability: Generic and Optimal}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {589-588}, doi = {}, year = {2016}, } Article: stoc16main-main437-p (type: Full Paper (14 pages)) doi:
	Bateni, MohammadHossein	STOC '16: "A PTAS for Planar Group Steiner ..." A PTAS for Planar Group Steiner Tree via Spanner Bootstrapping and Prize Collecting MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx (Google, USA; Massachusetts Institute of Technology, USA; University of Maryland at College Park, USA; Hungarian Academy of Sciences, Hungary) @InProceedings{STOC16p659, author = {MohammadHossein Bateni and Erik D. Demaine and MohammadTaghi Hajiaghayi and Dániel Marx}, title = {A PTAS for Planar Group Steiner Tree via Spanner Bootstrapping and Prize Collecting}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {659-658}, doi = {}, year = {2016}, } Article: stoc16main-main213-p (type: Full Paper (14 pages)) doi:
	Belovs, Aleksandrs	STOC '16: "A Polynomial Lower Bound for ..." A Polynomial Lower Bound for Testing Monotonicity Aleksandrs Belovs and Eric Blais (CWI, Netherlands; University of Waterloo, Canada) @InProceedings{STOC16p1163, author = {Aleksandrs Belovs and Eric Blais}, title = {A Polynomial Lower Bound for Testing Monotonicity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1163-1162}, doi = {}, year = {2016}, } Article: stoc16main-main280-p (type: Full Paper (14 pages)) doi: STOC '16: "Separations in Query Complexity ..." Separations in Query Complexity Based on Pointer Functions Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs (University of Latvia, Latvia; CWI, Netherlands; Nanyang Technological University, Singapore; National University of Singapore, Singapore; CNRS, France) @InProceedings{STOC16p911, author = {Andris Ambainis and Kaspars Balodis and Aleksandrs Belovs and Troy Lee and Miklos Santha and Juris Smotrovs}, title = {Separations in Query Complexity Based on Pointer Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {911-910}, doi = {}, year = {2016}, } Article: stoc16main-main123-p (type: Full Paper (14 pages)) doi:
	Ben-David, Shalev	STOC '16: "Separations in Query Complexity ..." Separations in Query Complexity using Cheat Sheets Scott Aaronson, Shalev Ben-David, and Robin Kothari (Massachusetts Institute of Technology, USA) @InProceedings{STOC16p981, author = {Scott Aaronson and Shalev Ben-David and Robin Kothari}, title = {Separations in Query Complexity using Cheat Sheets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {981-980}, doi = {}, year = {2016}, } Article: stoc16main-main423-p (type: Full Paper (14 pages)) doi:
	Bender, Michael A.	STOC '16: "Contention Resolution with ..." Contention Resolution with Log-Logstar Channel Accesses Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young (Stony Brook University, USA; University of Michigan, USA; Mississippi State University, USA) @InProceedings{STOC16p575, author = {Michael A. Bender and Tsvi Kopelowitz and Seth Pettie and Maxwell Young}, title = {Contention Resolution with Log-Logstar Channel Accesses}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {575-574}, doi = {}, year = {2016}, } Article: stoc16main-main456-p (type: Full Paper (14 pages)) doi:
	Bernstein, Aaron	STOC '16: "Deterministic Decremental ..." Deterministic Decremental Single Source Shortest Paths: Beyond the O(mn) Bound Aaron Bernstein and Shiri Chechik (Columbia University, USA; Tel Aviv University, Israel) @InProceedings{STOC16p449, author = {Aaron Bernstein and Shiri Chechik}, title = {Deterministic Decremental Single Source Shortest Paths: Beyond the O(mn) Bound}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {449-448}, doi = {}, year = {2016}, } Article: stoc16main-main112-p (type: Full Paper (14 pages)) doi:
	Bhattacharya, Sayan	STOC '16: "New Deterministic Approximation ..." New Deterministic Approximation Algorithms for Fully Dynamic Matching Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai (Institute of Mathematical Sciences at Chennai, India; University of Vienna, Austria; KTH, Sweden) @InProceedings{STOC16p463, author = {Sayan Bhattacharya and Monika Henzinger and Danupon Nanongkai}, title = {New Deterministic Approximation Algorithms for Fully Dynamic Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {463-462}, doi = {}, year = {2016}, } Article: stoc16main-main293-p (type: Full Paper (14 pages)) doi:
	Blais, Eric	STOC '16: "A Polynomial Lower Bound for ..." A Polynomial Lower Bound for Testing Monotonicity Aleksandrs Belovs and Eric Blais (CWI, Netherlands; University of Waterloo, Canada) @InProceedings{STOC16p1163, author = {Aleksandrs Belovs and Eric Blais}, title = {A Polynomial Lower Bound for Testing Monotonicity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1163-1162}, doi = {}, year = {2016}, } Article: stoc16main-main280-p (type: Full Paper (14 pages)) doi:
	Bodwin, Greg	STOC '16: "The 4/3 Additive Spanner Exponent ..." The 4/3 Additive Spanner Exponent Is Tight Amir Abboud and Greg Bodwin (Stanford University, USA) @InProceedings{STOC16p407, author = {Amir Abboud and Greg Bodwin}, title = {The 4/3 Additive Spanner Exponent Is Tight}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {407-406}, doi = {}, year = {2016}, } Article: stoc16main-main234-p (type: Full Paper (14 pages)) doi:
	Boutsidis, Christos	STOC '16: "Optimal Principal Component ..." Optimal Principal Component Analysis in Distributed and Streaming Models Christos Boutsidis, David P. Woodruff, and Peilin Zhong (Goldman Sachs, USA; IBM Research, USA; Tsinghua University, China) @InProceedings{STOC16p267, author = {Christos Boutsidis and David P. Woodruff and Peilin Zhong}, title = {Optimal Principal Component Analysis in Distributed and Streaming Models}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {267-266}, doi = {}, year = {2016}, } Article: stoc16main-main431-p (type: Full Paper (14 pages)) doi:
	Brandt, Sebastian	STOC '16: "A Lower Bound for the Distributed ..." A Lower Bound for the Distributed Lovász Local Lemma Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto (ETH Zurich, Switzerland; Tel Aviv University, Israel; Aalto University, Finland; Bitsplitters, Switzerland) @InProceedings{STOC16p547, author = {Sebastian Brandt and Orr Fischer and Juho Hirvonen and Barbara Keller and Tuomo Lempiäinen and Joel Rybicki and Jukka Suomela and Jara Uitto}, title = {A Lower Bound for the Distributed Lovász Local Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {}, year = {2016}, } Article: stoc16main-main300-p (type: Full Paper (14 pages)) doi:
	Braverman, Mark	STOC '16: "Constant-Rate Coding for Multiparty ..." Constant-Rate Coding for Multiparty Interactive Communication Is Impossible Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler (Princeton University, USA; Tel Aviv University, Israel; Carnegie Mellon University, USA) @InProceedings{STOC16p1135, author = {Mark Braverman and Klim Efremenko and Ran Gelles and Bernhard Haeupler}, title = {Constant-Rate Coding for Multiparty Interactive Communication Is Impossible}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1135-1134}, doi = {}, year = {2016}, } Article: stoc16main-main257-p (type: Full Paper (14 pages)) doi: STOC '16: "Communication Lower Bounds ..." Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, and David P. Woodruff (Princeton University, USA; Toyota Technological Institute at Chicago, USA; IBM Research, USA) @InProceedings{STOC16p1149, author = {Mark Braverman and Ankit Garg and Tengyu Ma and Huy L. Nguyen and David P. Woodruff}, title = {Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1149-1148}, doi = {}, year = {2016}, } Article: stoc16main-main342-p (type: Full Paper (14 pages)) doi: STOC '16: "Parallel Algorithms for Select ..." Parallel Algorithms for Select and Partition with Noisy Comparisons Mark Braverman, Jieming Mao, and S. Matthew Weinberg (Princeton University, USA) @InProceedings{STOC16p967, author = {Mark Braverman and Jieming Mao and S. Matthew Weinberg}, title = {Parallel Algorithms for Select and Partition with Noisy Comparisons}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {967-966}, doi = {}, year = {2016}, } Article: stoc16main-main419-p (type: Full Paper (14 pages)) doi:
	Braverman, Vladimir	STOC '16: "Beating CountSketch for Heavy ..." Beating CountSketch for Heavy Hitters in Insertion Streams Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, and David P. Woodruff (Johns Hopkins University, USA; ETH Zurich, Switzerland; IBM Research, USA) @InProceedings{STOC16p841, author = {Vladimir Braverman and Stephen R. Chestnut and Nikita Ivkin and David P. Woodruff}, title = {Beating CountSketch for Heavy Hitters in Insertion Streams}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {841-840}, doi = {}, year = {2016}, } Article: stoc16main-main240-p (type: Full Paper (14 pages)) doi:
	Cai, Yang	STOC '16: "A Duality Based Unified Approach ..." A Duality Based Unified Approach to Bayesian Mechanism Design Yang Cai, Nikhil R. Devanur, and S. Matthew Weinberg (McGill University, Canada; Microsoft Research, USA; Princeton University, USA) @InProceedings{STOC16p1051, author = {Yang Cai and Nikhil R. Devanur and S. Matthew Weinberg}, title = {A Duality Based Unified Approach to Bayesian Mechanism Design}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1051-1050}, doi = {}, year = {2016}, } Article: stoc16main-main430-p (type: Full Paper (14 pages)) doi:
	Chakraborty, Diptarka	STOC '16: "Streaming Algorithms for Embedding ..." Streaming Algorithms for Embedding and Computing Edit Distance in the Low Distance Regime Diptarka Chakraborty, Elazar Goldenberg, and Michal Koucký (IIT Kanpur, India; Charles University in Prague, Czechia) @InProceedings{STOC16p813, author = {Diptarka Chakraborty and Elazar Goldenberg and Michal Koucký}, title = {Streaming Algorithms for Embedding and Computing Edit Distance in the Low Distance Regime}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {813-812}, doi = {}, year = {2016}, } Article: stoc16main-main330-p (type: Full Paper (14 pages)) doi:
	Chattopadhyay, Eshan	STOC '16: "Non-malleable Extractors and ..." Non-malleable Extractors and Codes, with Their Many Tampered Extensions Eshan Chattopadhyay, Vipul Goyal, and Xin Li (University of Texas at Austin, USA; Microsoft Research, India; Johns Hopkins University, USA) @InProceedings{STOC16p323, author = {Eshan Chattopadhyay and Vipul Goyal and Xin Li}, title = {Non-malleable Extractors and Codes, with Their Many Tampered Extensions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {323-322}, doi = {}, year = {2016}, } Article: stoc16main-main207-p (type: Full Paper (14 pages)) doi: STOC '16: "Extractors for Sumset Sources ..." Extractors for Sumset Sources Eshan Chattopadhyay and Xin Li (University of Texas at Austin, USA; Johns Hopkins University, USA) @InProceedings{STOC16p337, author = {Eshan Chattopadhyay and Xin Li}, title = {Extractors for Sumset Sources}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {337-336}, doi = {}, year = {2016}, } Article: stoc16main-main422-p (type: Full Paper (14 pages)) doi: STOC '16: "Explicit Two-Source Extractors ..." Explicit Two-Source Extractors and Resilient Functions Eshan Chattopadhyay and David Zuckerman (University of Texas at Austin, USA) @InProceedings{STOC16p771, author = {Eshan Chattopadhyay and David Zuckerman}, title = {Explicit Two-Source Extractors and Resilient Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {771-770}, doi = {}, year = {2016}, } Article: stoc16main-main134-p (type: Full Paper (14 pages)) doi:
	Chechik, Shiri	STOC '16: "Deterministic Decremental ..." Deterministic Decremental Single Source Shortest Paths: Beyond the O(mn) Bound Aaron Bernstein and Shiri Chechik (Columbia University, USA; Tel Aviv University, Israel) @InProceedings{STOC16p449, author = {Aaron Bernstein and Shiri Chechik}, title = {Deterministic Decremental Single Source Shortest Paths: Beyond the O(mn) Bound}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {449-448}, doi = {}, year = {2016}, } Article: stoc16main-main112-p (type: Full Paper (14 pages)) doi:
	Chen, Sitan	STOC '16: "Basis Collapse for Holographic ..." Basis Collapse for Holographic Algorithms over All Domain Sizes Sitan Chen (Harvard University, USA) @InProceedings{STOC16p883, author = {Sitan Chen}, title = {Basis Collapse for Holographic Algorithms over All Domain Sizes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {883-882}, doi = {}, year = {2016}, } Article: stoc16main-main206-p (type: Full Paper (14 pages)) doi:
	Chen, Xi	STOC '16: "Near-Optimal Small-Depth Lower ..." Near-Optimal Small-Depth Lower Bounds for Small Distance Connectivity Xi Chen, Igor C. Oliveira, Rocco A. Servedio, and Li-Yang Tan (Columbia University, USA; Charles University in Prague, Czechia; Toyota Technological Institute at Chicago, USA) @InProceedings{STOC16p701, author = {Xi Chen and Igor C. Oliveira and Rocco A. Servedio and Li-Yang Tan}, title = {Near-Optimal Small-Depth Lower Bounds for Small Distance Connectivity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {701-700}, doi = {}, year = {2016}, } Article: stoc16main-main158-p (type: Full Paper (14 pages)) doi:
	Chestnut, Stephen R.	STOC '16: "Beating CountSketch for Heavy ..." Beating CountSketch for Heavy Hitters in Insertion Streams Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, and David P. Woodruff (Johns Hopkins University, USA; ETH Zurich, Switzerland; IBM Research, USA) @InProceedings{STOC16p841, author = {Vladimir Braverman and Stephen R. Chestnut and Nikita Ivkin and David P. Woodruff}, title = {Beating CountSketch for Heavy Hitters in Insertion Streams}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {841-840}, doi = {}, year = {2016}, } Article: stoc16main-main240-p (type: Full Paper (14 pages)) doi:
	Choudhary, Keerti	STOC '16: "Fault Tolerant Subgraph for ..." Fault Tolerant Subgraph for Single Source Reachability: Generic and Optimal Surender Baswana, Keerti Choudhary, and Liam Roditty (IIT Kanpur, India; Bar-Ilan University, Israel) @InProceedings{STOC16p589, author = {Surender Baswana and Keerti Choudhary and Liam Roditty}, title = {Fault Tolerant Subgraph for Single Source Reachability: Generic and Optimal}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {589-588}, doi = {}, year = {2016}, } Article: stoc16main-main437-p (type: Full Paper (14 pages)) doi:
	Chuzhoy, Julia	STOC '16: "Improved Approximation for ..." Improved Approximation for Node-Disjoint Paths in Planar Graphs Julia Chuzhoy, David H. K. Kim, and Shi Li (Toyota Technological Institute at Chicago, USA; University of Chicago, USA; State University of New York at Buffalo, USA) @InProceedings{STOC16p645, author = {Julia Chuzhoy and David H. K. Kim and Shi Li}, title = {Improved Approximation for Node-Disjoint Paths in Planar Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {645-644}, doi = {}, year = {2016}, } Article: stoc16main-main169-p (type: Full Paper (14 pages)) doi:
	Cohen, Aloni	STOC '16: "Watermarking Cryptographic ..." Watermarking Cryptographic Capabilities Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, and Daniel Wichs (Massachusetts Institute of Technology, USA; NTT, Japan; Northeastern University, USA) @InProceedings{STOC16p1261, author = {Aloni Cohen and Justin Holmgren and Ryo Nishimaki and Vinod Vaikuntanathan and Daniel Wichs}, title = {Watermarking Cryptographic Capabilities}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1261-1260}, doi = {}, year = {2016}, } Article: stoc16main-main448-p (type: Full Paper (14 pages)) doi:
	Cohen, Gil	STOC '16: "Two-Source Dispersers for ..." Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs Gil Cohen (Weizmann Institute of Science, Israel) @InProceedings{STOC16p309, author = {Gil Cohen}, title = {Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {309-308}, doi = {}, year = {2016}, } Article: stoc16main-main138-p (type: Full Paper (14 pages)) doi:
	Cohen, Michael B.	STOC '16: "Geometric Median in Nearly ..." Geometric Median in Nearly Linear Time Michael B. Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford (Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; Microsoft Research, USA) @InProceedings{STOC16p15, author = {Michael B. Cohen and Yin Tat Lee and Gary Miller and Jakub Pachocki and Aaron Sidford}, title = {Geometric Median in Nearly Linear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {15-14}, doi = {}, year = {2016}, } Article: stoc16main-main436-p (type: Full Paper (14 pages)) doi:
	Cohen-Addad, Vincent	STOC '16: "Approximating Connectivity ..." Approximating Connectivity Domination in Weighted Bounded-Genus Graphs Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, and David Meierfrankenfeld (ENS, France; CNRS, France; Brown University, USA) @InProceedings{STOC16p673, author = {Vincent Cohen-Addad and Éric Colin de Verdière and Philip N. Klein and Claire Mathieu and David Meierfrankenfeld}, title = {Approximating Connectivity Domination in Weighted Bounded-Genus Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {673-672}, doi = {}, year = {2016}, } Article: stoc16main-main369-p (type: Full Paper (14 pages)) doi:
	Colin de Verdière, Éric	STOC '16: "Approximating Connectivity ..." Approximating Connectivity Domination in Weighted Bounded-Genus Graphs Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, and David Meierfrankenfeld (ENS, France; CNRS, France; Brown University, USA) @InProceedings{STOC16p673, author = {Vincent Cohen-Addad and Éric Colin de Verdière and Philip N. Klein and Claire Mathieu and David Meierfrankenfeld}, title = {Approximating Connectivity Domination in Weighted Bounded-Genus Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {673-672}, doi = {}, year = {2016}, } Article: stoc16main-main369-p (type: Full Paper (14 pages)) doi:
	Czumaj, Artur	STOC '16: "Relating Two Property Testing ..." Relating Two Property Testing Models for Bounded Degree Directed Graphs Artur Czumaj, Pan Peng, and Christian Sohler (University of Warwick, UK; TU Dortmund, Germany; Institute of Software at Chinese Academy of Sciences, China) @InProceedings{STOC16p1177, author = {Artur Czumaj and Pan Peng and Christian Sohler}, title = {Relating Two Property Testing Models for Bounded Degree Directed Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1177-1176}, doi = {}, year = {2016}, } Article: stoc16main-main314-p (type: Full Paper (14 pages)) doi:
	Daniely, Amit	STOC '16: "Complexity Theoretic Limitations ..." Complexity Theoretic Limitations on Learning Halfspaces Amit Daniely (Google, USA) @InProceedings{STOC16p113, author = {Amit Daniely}, title = {Complexity Theoretic Limitations on Learning Halfspaces}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {113-112}, doi = {}, year = {2016}, } Article: stoc16main-main108-p (type: Full Paper (14 pages)) doi:
	Dasgupta, Sanjoy	STOC '16: "A Cost Function for Similarity-Based ..." A Cost Function for Similarity-Based Hierarchical Clustering Sanjoy Dasgupta (University of California at San Diego, USA) @InProceedings{STOC16p127, author = {Sanjoy Dasgupta}, title = {A Cost Function for Similarity-Based Hierarchical Clustering}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {127-126}, doi = {}, year = {2016}, } Article: stoc16main-main131-p (type: Full Paper (14 pages)) doi:
	Daskalakis, Constantinos	STOC '16: "A Size-Free CLT for Poisson ..." A Size-Free CLT for Poisson Multinomials and Its Applications Constantinos Daskalakis, Anindya De, Gautam Kamath, and Christos Tzamos (Massachusetts Institute of Technology, USA; Northwestern University, USA) @InProceedings{STOC16p1219, author = {Constantinos Daskalakis and Anindya De and Gautam Kamath and Christos Tzamos}, title = {A Size-Free CLT for Poisson Multinomials and Its Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1219-1218}, doi = {}, year = {2016}, } Article: stoc16main-main104-p (type: Full Paper (14 pages)) doi:
	David, Roee	STOC '16: "On the Effect of Randomness ..." On the Effect of Randomness on Planted 3-Coloring Models Roee David and Uriel Feige (Weizmann Institute of Science, Israel) @InProceedings{STOC16p85, author = {Roee David and Uriel Feige}, title = {On the Effect of Randomness on Planted 3-Coloring Models}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {85-84}, doi = {}, year = {2016}, } Article: stoc16main-main250-p (type: Full Paper (14 pages)) doi:
	De, Anindya	STOC '16: "A Size-Free CLT for Poisson ..." A Size-Free CLT for Poisson Multinomials and Its Applications Constantinos Daskalakis, Anindya De, Gautam Kamath, and Christos Tzamos (Massachusetts Institute of Technology, USA; Northwestern University, USA) @InProceedings{STOC16p1219, author = {Constantinos Daskalakis and Anindya De and Gautam Kamath and Christos Tzamos}, title = {A Size-Free CLT for Poisson Multinomials and Its Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1219-1218}, doi = {}, year = {2016}, } Article: stoc16main-main104-p (type: Full Paper (14 pages)) doi:
	Demaine, Erik D.	STOC '16: "A PTAS for Planar Group Steiner ..." A PTAS for Planar Group Steiner Tree via Spanner Bootstrapping and Prize Collecting MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx (Google, USA; Massachusetts Institute of Technology, USA; University of Maryland at College Park, USA; Hungarian Academy of Sciences, Hungary) @InProceedings{STOC16p659, author = {MohammadHossein Bateni and Erik D. Demaine and MohammadTaghi Hajiaghayi and Dániel Marx}, title = {A PTAS for Planar Group Steiner Tree via Spanner Bootstrapping and Prize Collecting}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {659-658}, doi = {}, year = {2016}, } Article: stoc16main-main213-p (type: Full Paper (14 pages)) doi:
	Devanur, Nikhil R.	STOC '16: "A Duality Based Unified Approach ..." A Duality Based Unified Approach to Bayesian Mechanism Design Yang Cai, Nikhil R. Devanur, and S. Matthew Weinberg (McGill University, Canada; Microsoft Research, USA; Princeton University, USA) @InProceedings{STOC16p1051, author = {Yang Cai and Nikhil R. Devanur and S. Matthew Weinberg}, title = {A Duality Based Unified Approach to Bayesian Mechanism Design}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1051-1050}, doi = {}, year = {2016}, } Article: stoc16main-main430-p (type: Full Paper (14 pages)) doi: STOC '16: "The Sample Complexity of Auctions ..." The Sample Complexity of Auctions with Side Information Nikhil R. Devanur, Zhiyi Huang, and Christos-Alexandros Psomas (Microsoft Research, USA; University of Hong Kong, China; University of California at Berkeley, USA) @InProceedings{STOC16p491, author = {Nikhil R. Devanur and Zhiyi Huang and Christos-Alexandros Psomas}, title = {The Sample Complexity of Auctions with Side Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {491-490}, doi = {}, year = {2016}, } Article: stoc16main-main219-p (type: Full Paper (14 pages)) doi:
	Diakonikolas, Ilias	STOC '16: "The Fourier Transform of Poisson ..." The Fourier Transform of Poisson Multinomial Distributions and Its Algorithmic Applications Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart (University of Southern California, USA; University of California at San Diego, USA) @InProceedings{STOC16p1205, author = {Ilias Diakonikolas and Daniel M. Kane and Alistair Stewart}, title = {The Fourier Transform of Poisson Multinomial Distributions and Its Algorithmic Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1205-1204}, doi = {}, year = {2016}, } Article: stoc16main-main218-p (type: Full Paper (14 pages)) doi:
	Dobzinski, Shahar	STOC '16: "Breaking the Logarithmic Barrier ..." Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders Shahar Dobzinski (Weizmann Institute of Science, Israel) @InProceedings{STOC16p1065, author = {Shahar Dobzinski}, title = {Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1065-1064}, doi = {}, year = {2016}, } Article: stoc16main-main296-p (type: Full Paper (14 pages)) doi:
	Dughmi, Shaddin	STOC '16: "Algorithmic Bayesian Persuasion ..." Algorithmic Bayesian Persuasion Shaddin Dughmi and Haifeng Xu (University of Southern California, USA) @InProceedings{STOC16p477, author = {Shaddin Dughmi and Haifeng Xu}, title = {Algorithmic Bayesian Persuasion}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {477-476}, doi = {}, year = {2016}, } Article: stoc16main-main346-p (type: Full Paper (14 pages)) doi:
	Efremenko, Klim	STOC '16: "Constant-Rate Coding for Multiparty ..." Constant-Rate Coding for Multiparty Interactive Communication Is Impossible Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler (Princeton University, USA; Tel Aviv University, Israel; Carnegie Mellon University, USA) @InProceedings{STOC16p1135, author = {Mark Braverman and Klim Efremenko and Ran Gelles and Bernhard Haeupler}, title = {Constant-Rate Coding for Multiparty Interactive Communication Is Impossible}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1135-1134}, doi = {}, year = {2016}, } Article: stoc16main-main257-p (type: Full Paper (14 pages)) doi:
	Emamjomeh-Zadeh, Ehsan	STOC '16: "Deterministic and Probabilistic ..." Deterministic and Probabilistic Binary Search in Graphs Ehsan Emamjomeh-Zadeh, David Kempe, and Vikrant Singhal (University of Southern California, USA) @InProceedings{STOC16p603, author = {Ehsan Emamjomeh-Zadeh and David Kempe and Vikrant Singhal}, title = {Deterministic and Probabilistic Binary Search in Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {603-602}, doi = {}, year = {2016}, } Article: stoc16main-main462-p (type: Full Paper (14 pages)) doi:
	Emek, Yuval	STOC '16: "Online Matching: Haste Makes ..." Online Matching: Haste Makes Waste! Yuval Emek, Shay Kutten, and Roger Wattenhofer (Technion, Israel; ETH Zurich, Switzerland) @InProceedings{STOC16p379, author = {Yuval Emek and Shay Kutten and Roger Wattenhofer}, title = {Online Matching: Haste Makes Waste!}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {379-378}, doi = {}, year = {2016}, } Article: stoc16main-main239-p (type: Full Paper (14 pages)) doi:
	Ene, Alina	STOC '16: "Routing under Balance ..." Routing under Balance Alina Ene, Gary Miller, Jakub Pachocki, and Aaron Sidford (University of Warwick, UK; Carnegie Mellon University, USA; Microsoft Research, USA) @InProceedings{STOC16p687, author = {Alina Ene and Gary Miller and Jakub Pachocki and Aaron Sidford}, title = {Routing under Balance}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {687-686}, doi = {}, year = {2016}, } Article: stoc16main-main454-p (type: Full Paper (14 pages)) doi:
	Evra, Shai	STOC '16: "Bounded Degree Cosystolic ..." Bounded Degree Cosystolic Expanders of Every Dimension Shai Evra and Tali Kaufman (Hebrew University of Jerusalem, Israel; Bar-Ilan University, Israel) @InProceedings{STOC16p43, author = {Shai Evra and Tali Kaufman}, title = {Bounded Degree Cosystolic Expanders of Every Dimension}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {43-42}, doi = {}, year = {2016}, } Article: stoc16main-main190-p (type: Full Paper (14 pages)) doi:
	Feige, Uriel	STOC '16: "On the Effect of Randomness ..." On the Effect of Randomness on Planted 3-Coloring Models Roee David and Uriel Feige (Weizmann Institute of Science, Israel) @InProceedings{STOC16p85, author = {Roee David and Uriel Feige}, title = {On the Effect of Randomness on Planted 3-Coloring Models}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {85-84}, doi = {}, year = {2016}, } Article: stoc16main-main250-p (type: Full Paper (14 pages)) doi:
	Feldman, Michal	STOC '16: "The Price of Anarchy in Large ..." The Price of Anarchy in Large Games Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden, and Vasilis Syrgkanis (Tel Aviv University, Israel; Microsoft Research, USA; Stanford University, USA) @InProceedings{STOC16p1093, author = {Michal Feldman and Nicole Immorlica and Brendan Lucier and Tim Roughgarden and Vasilis Syrgkanis}, title = {The Price of Anarchy in Large Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1093-1092}, doi = {}, year = {2016}, } Article: stoc16main-main340-p (type: Full Paper (14 pages)) doi:
	Fenner, Stephen	STOC '16: "Bipartite Perfect Matching ..." Bipartite Perfect Matching Is in Quasi-NC Stephen Fenner, Rohit Gurjar, and Thomas Thierauf (University of South Carolina, USA; Aalen University, Germany) @InProceedings{STOC16p855, author = {Stephen Fenner and Rohit Gurjar and Thomas Thierauf}, title = {Bipartite Perfect Matching Is in Quasi-NC}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {855-854}, doi = {}, year = {2016}, } Article: stoc16main-main260-p (type: Full Paper (14 pages)) doi:
	Fischer, Orr	STOC '16: "A Lower Bound for the Distributed ..." A Lower Bound for the Distributed Lovász Local Lemma Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto (ETH Zurich, Switzerland; Tel Aviv University, Israel; Aalto University, Finland; Bitsplitters, Switzerland) @InProceedings{STOC16p547, author = {Sebastian Brandt and Orr Fischer and Juho Hirvonen and Barbara Keller and Tuomo Lempiäinen and Joel Rybicki and Jukka Suomela and Jara Uitto}, title = {A Lower Bound for the Distributed Lovász Local Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {}, year = {2016}, } Article: stoc16main-main300-p (type: Full Paper (14 pages)) doi:
	Fomin, Fedor V.	STOC '16: "Exact Algorithms via Monotone ..." Exact Algorithms via Monotone Local Search Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh (University of Bergen, Norway; UNSW, Australia; Data61, Australia; Institute of Mathematical Sciences at Chennai, India) @InProceedings{STOC16p869, author = {Fedor V. Fomin and Serge Gaspers and Daniel Lokshtanov and Saket Saurabh}, title = {Exact Algorithms via Monotone Local Search}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {869-868}, doi = {}, year = {2016}, } Article: stoc16main-main216-p (type: Full Paper (14 pages)) doi:
	Fraigniaud, Pierre	STOC '16: "Parallel Exhaustive Search ..." Parallel Exhaustive Search without Coordination Pierre Fraigniaud, Amos Korman, and Yoav Rodeh (CNRS, France; University of Paris Diderot, France; Weizmann Institute of Science, Israel) @InProceedings{STOC16p351, author = {Pierre Fraigniaud and Amos Korman and Yoav Rodeh}, title = {Parallel Exhaustive Search without Coordination}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {351-350}, doi = {}, year = {2016}, } Article: stoc16main-main182-p (type: Full Paper (14 pages)) doi:
	Frieze, Alan	STOC '16: "Separating Subadditive Euclidean ..." Separating Subadditive Euclidean Functionals Alan Frieze and Wesley Pegden (Carnegie Mellon University, USA) @InProceedings{STOC16p29, author = {Alan Frieze and Wesley Pegden}, title = {Separating Subadditive Euclidean Functionals}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {29-28}, doi = {}, year = {2016}, } Article: stoc16main-main301-p (type: Full Paper (14 pages)) doi:
	Ganor, Anat	STOC '16: "Exponential Separation of ..." Exponential Separation of Communication and External Information Anat Ganor, Gillat Kol, and Ran Raz (Weizmann Institute of Science, Israel; Institute for Advanced Study at Princeton, USA) @InProceedings{STOC16p1107, author = {Anat Ganor and Gillat Kol and Ran Raz}, title = {Exponential Separation of Communication and External Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1107-1106}, doi = {}, year = {2016}, } Article: stoc16main-main164-p (type: Full Paper (14 pages)) doi:
	Garg, Ankit	STOC '16: "Communication Lower Bounds ..." Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, and David P. Woodruff (Princeton University, USA; Toyota Technological Institute at Chicago, USA; IBM Research, USA) @InProceedings{STOC16p1149, author = {Mark Braverman and Ankit Garg and Tengyu Ma and Huy L. Nguyen and David P. Woodruff}, title = {Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1149-1148}, doi = {}, year = {2016}, } Article: stoc16main-main342-p (type: Full Paper (14 pages)) doi:
	Gaspers, Serge	STOC '16: "Exact Algorithms via Monotone ..." Exact Algorithms via Monotone Local Search Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh (University of Bergen, Norway; UNSW, Australia; Data61, Australia; Institute of Mathematical Sciences at Chennai, India) @InProceedings{STOC16p869, author = {Fedor V. Fomin and Serge Gaspers and Daniel Lokshtanov and Saket Saurabh}, title = {Exact Algorithms via Monotone Local Search}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {869-868}, doi = {}, year = {2016}, } Article: stoc16main-main216-p (type: Full Paper (14 pages)) doi:
	Gavinsky, Dmitry	STOC '16: "Entangled Simultaneity versus ..." Entangled Simultaneity versus Classical Interactivity in Communication Complexity Dmitry Gavinsky (Czech Academy of Sciences, Czechia) @InProceedings{STOC16p995, author = {Dmitry Gavinsky}, title = {Entangled Simultaneity versus Classical Interactivity in Communication Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {995-994}, doi = {}, year = {2016}, } Article: stoc16main-main203-p (type: Full Paper (14 pages)) doi:
	Gelles, Ran	STOC '16: "Constant-Rate Coding for Multiparty ..." Constant-Rate Coding for Multiparty Interactive Communication Is Impossible Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler (Princeton University, USA; Tel Aviv University, Israel; Carnegie Mellon University, USA) @InProceedings{STOC16p1135, author = {Mark Braverman and Klim Efremenko and Ran Gelles and Bernhard Haeupler}, title = {Constant-Rate Coding for Multiparty Interactive Communication Is Impossible}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1135-1134}, doi = {}, year = {2016}, } Article: stoc16main-main257-p (type: Full Paper (14 pages)) doi:
	Goldenberg, Elazar	STOC '16: "Streaming Algorithms for Embedding ..." Streaming Algorithms for Embedding and Computing Edit Distance in the Low Distance Regime Diptarka Chakraborty, Elazar Goldenberg, and Michal Koucký (IIT Kanpur, India; Charles University in Prague, Czechia) @InProceedings{STOC16p813, author = {Diptarka Chakraborty and Elazar Goldenberg and Michal Koucký}, title = {Streaming Algorithms for Embedding and Computing Edit Distance in the Low Distance Regime}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {813-812}, doi = {}, year = {2016}, } Article: stoc16main-main330-p (type: Full Paper (14 pages)) doi:
	Goldreich, Oded	STOC '16: "Matrix Rigidity of Random ..." Matrix Rigidity of Random Toeplitz Matrices Oded Goldreich and Avishay Tal (Weizmann Institute of Science, Israel; Institute for Advanced Study at Princeton, USA) @InProceedings{STOC16p99, author = {Oded Goldreich and Avishay Tal}, title = {Matrix Rigidity of Random Toeplitz Matrices}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {99-98}, doi = {}, year = {2016}, } Article: stoc16main-main359-p (type: Full Paper (14 pages)) doi:
	Goyal, Vipul	STOC '16: "Textbook Non-malleable Commitments ..." Textbook Non-malleable Commitments Vipul Goyal, Omkant Pandey, and Silas Richelson (Microsoft Research, India; Drexel University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC16p1275, author = {Vipul Goyal and Omkant Pandey and Silas Richelson}, title = {Textbook Non-malleable Commitments}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1275-1274}, doi = {}, year = {2016}, } Article: stoc16main-main464-p (type: Full Paper (14 pages)) doi: STOC '16: "Non-malleable Extractors and ..." Non-malleable Extractors and Codes, with Their Many Tampered Extensions Eshan Chattopadhyay, Vipul Goyal, and Xin Li (University of Texas at Austin, USA; Microsoft Research, India; Johns Hopkins University, USA) @InProceedings{STOC16p323, author = {Eshan Chattopadhyay and Vipul Goyal and Xin Li}, title = {Non-malleable Extractors and Codes, with Their Many Tampered Extensions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {323-322}, doi = {}, year = {2016}, } Article: stoc16main-main207-p (type: Full Paper (14 pages)) doi:
	Gurjar, Rohit	STOC '16: "Bipartite Perfect Matching ..." Bipartite Perfect Matching Is in Quasi-NC Stephen Fenner, Rohit Gurjar, and Thomas Thierauf (University of South Carolina, USA; Aalen University, Germany) @InProceedings{STOC16p855, author = {Stephen Fenner and Rohit Gurjar and Thomas Thierauf}, title = {Bipartite Perfect Matching Is in Quasi-NC}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {855-854}, doi = {}, year = {2016}, } Article: stoc16main-main260-p (type: Full Paper (14 pages)) doi:
	Guruswami, Venkatesan	STOC '16: "Repairing Reed-Solomon Codes ..." Repairing Reed-Solomon Codes Venkatesan Guruswami and Mary Wootters (Carnegie Mellon University, USA) @InProceedings{STOC16p239, author = {Venkatesan Guruswami and Mary Wootters}, title = {Repairing Reed-Solomon Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {239-238}, doi = {}, year = {2016}, } Article: stoc16main-main125-p (type: Full Paper (14 pages)) doi:
	Haah, Jeongwan	STOC '16: "Sample-Optimal Tomography ..." Sample-Optimal Tomography of Quantum States Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu (Massachusetts Institute of Technology, USA; University of Technology Sydney, Australia; University of Waterloo, Canada; Institute of Software at Chinese Academy of Sciences, China; University of Oregon, USA; University of Guelph, Canada) @InProceedings{STOC16p1037, author = {Jeongwan Haah and Aram W. Harrow and Zhengfeng Ji and Xiaodi Wu and Nengkun Yu}, title = {Sample-Optimal Tomography of Quantum States}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1037-1036}, doi = {}, year = {2016}, } Article: stoc16main-main351-p (type: Full Paper (14 pages)) doi:
	Haeupler, Bernhard	STOC '16: "Constant-Rate Coding for Multiparty ..." Constant-Rate Coding for Multiparty Interactive Communication Is Impossible Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler (Princeton University, USA; Tel Aviv University, Israel; Carnegie Mellon University, USA) @InProceedings{STOC16p1135, author = {Mark Braverman and Klim Efremenko and Ran Gelles and Bernhard Haeupler}, title = {Constant-Rate Coding for Multiparty Interactive Communication Is Impossible}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1135-1134}, doi = {}, year = {2016}, } Article: stoc16main-main257-p (type: Full Paper (14 pages)) doi:
	Hajiaghayi, MohammadTaghi	STOC '16: "A PTAS for Planar Group Steiner ..." A PTAS for Planar Group Steiner Tree via Spanner Bootstrapping and Prize Collecting MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx (Google, USA; Massachusetts Institute of Technology, USA; University of Maryland at College Park, USA; Hungarian Academy of Sciences, Hungary) @InProceedings{STOC16p659, author = {MohammadHossein Bateni and Erik D. Demaine and MohammadTaghi Hajiaghayi and Dániel Marx}, title = {A PTAS for Planar Group Steiner Tree via Spanner Bootstrapping and Prize Collecting}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {659-658}, doi = {}, year = {2016}, } Article: stoc16main-main213-p (type: Full Paper (14 pages)) doi:
	Hall, Chris	STOC '16: "Ramanujan Coverings of Graphs ..." Ramanujan Coverings of Graphs Chris Hall, Doron Puder, and William F. Sawin (University of Wyoming, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA) @InProceedings{STOC16p617, author = {Chris Hall and Doron Puder and William F. Sawin}, title = {Ramanujan Coverings of Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {617-616}, doi = {}, year = {2016}, } Article: stoc16main-main313-p (type: Full Paper (14 pages)) doi:
	Hansen, Thomas Dueholm	STOC '16: "Simulating Branching Programs ..." Simulating Branching Programs with Edit Distance and Friends: Or: A Polylog Shaved Is a Lower Bound Made Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams (Stanford University, USA; Aarhus University, Denmark) @InProceedings{STOC16p435, author = {Amir Abboud and Thomas Dueholm Hansen and Virginia Vassilevska Williams and Ryan Williams}, title = {Simulating Branching Programs with Edit Distance and Friends: Or: A Polylog Shaved Is a Lower Bound Made}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {435-434}, doi = {}, year = {2016}, } Article: stoc16main-main451-p (type: Full Paper (14 pages)) doi:
	Harris, David G.	STOC '16: "Distributed (Δ+1)-Coloring ..." Distributed (Δ+1)-Coloring in Sublogarithmic Rounds David G. Harris, Johannes Schneider, and Hsin-Hao Su (University of Maryland, USA; ABB Corporate Research, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC16p533, author = {David G. Harris and Johannes Schneider and Hsin-Hao Su}, title = {Distributed (Δ+1)-Coloring in Sublogarithmic Rounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {533-532}, doi = {}, year = {2016}, } Article: stoc16main-main152-p (type: Full Paper (14 pages)) doi:
	Harrow, Aram W.	STOC '16: "Sample-Optimal Tomography ..." Sample-Optimal Tomography of Quantum States Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu (Massachusetts Institute of Technology, USA; University of Technology Sydney, Australia; University of Waterloo, Canada; Institute of Software at Chinese Academy of Sciences, China; University of Oregon, USA; University of Guelph, Canada) @InProceedings{STOC16p1037, author = {Jeongwan Haah and Aram W. Harrow and Zhengfeng Ji and Xiaodi Wu and Nengkun Yu}, title = {Sample-Optimal Tomography of Quantum States}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1037-1036}, doi = {}, year = {2016}, } Article: stoc16main-main351-p (type: Full Paper (14 pages)) doi:
	Hazan, Elad	STOC '16: "The Computational Power of ..." The Computational Power of Optimization in Online Learning Elad Hazan and Tomer Koren (Princeton University, USA; Technion, Israel) @InProceedings{STOC16p141, author = {Elad Hazan and Tomer Koren}, title = {The Computational Power of Optimization in Online Learning}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {141-140}, doi = {}, year = {2016}, } Article: stoc16main-main167-p (type: Full Paper (14 pages)) doi:
	Henzinger, Monika	STOC '16: "New Deterministic Approximation ..." New Deterministic Approximation Algorithms for Fully Dynamic Matching Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai (Institute of Mathematical Sciences at Chennai, India; University of Vienna, Austria; KTH, Sweden) @InProceedings{STOC16p463, author = {Sayan Bhattacharya and Monika Henzinger and Danupon Nanongkai}, title = {New Deterministic Approximation Algorithms for Fully Dynamic Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {463-462}, doi = {}, year = {2016}, } Article: stoc16main-main293-p (type: Full Paper (14 pages)) doi: STOC '16: "A Deterministic Almost-Tight ..." A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai (University of Vienna, Austria; Max Planck Institute for Informatics, Germany; KTH, Sweden) @InProceedings{STOC16p561, author = {Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai}, title = {A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {561-560}, doi = {}, year = {2016}, } Article: stoc16main-main382-p (type: Full Paper (14 pages)) doi:
	Hirvonen, Juho	STOC '16: "A Lower Bound for the Distributed ..." A Lower Bound for the Distributed Lovász Local Lemma Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto (ETH Zurich, Switzerland; Tel Aviv University, Israel; Aalto University, Finland; Bitsplitters, Switzerland) @InProceedings{STOC16p547, author = {Sebastian Brandt and Orr Fischer and Juho Hirvonen and Barbara Keller and Tuomo Lempiäinen and Joel Rybicki and Jukka Suomela and Jara Uitto}, title = {A Lower Bound for the Distributed Lovász Local Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {}, year = {2016}, } Article: stoc16main-main300-p (type: Full Paper (14 pages)) doi:
	Holmgren, Justin	STOC '16: "Watermarking Cryptographic ..." Watermarking Cryptographic Capabilities Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, and Daniel Wichs (Massachusetts Institute of Technology, USA; NTT, Japan; Northeastern University, USA) @InProceedings{STOC16p1261, author = {Aloni Cohen and Justin Holmgren and Ryo Nishimaki and Vinod Vaikuntanathan and Daniel Wichs}, title = {Watermarking Cryptographic Capabilities}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1261-1260}, doi = {}, year = {2016}, } Article: stoc16main-main448-p (type: Full Paper (14 pages)) doi:
	Hopkins, Samuel B.	STOC '16: "Fast Spectral Algorithms from ..." Fast Spectral Algorithms from Sum-of-Squares Proofs: Tensor Decomposition and Planted Sparse Vectors Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer (Cornell University, USA; University of California at Berkeley, USA) @InProceedings{STOC16p197, author = {Samuel B. Hopkins and Tselil Schramm and Jonathan Shi and David Steurer}, title = {Fast Spectral Algorithms from Sum-of-Squares Proofs: Tensor Decomposition and Planted Sparse Vectors}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {197-196}, doi = {}, year = {2016}, } Article: stoc16main-main137-p (type: Full Paper (14 pages)) doi:
	Hsu, Justin	STOC '16: "Do Prices Coordinate Markets? ..." Do Prices Coordinate Markets? Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth, and Rakesh Vohra (University of Pennsylvania, USA) @InProceedings{STOC16p505, author = {Justin Hsu and Jamie Morgenstern and Ryan Rogers and Aaron Roth and Rakesh Vohra}, title = {Do Prices Coordinate Markets?}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {505-504}, doi = {}, year = {2016}, } Article: stoc16main-main246-p (type: Full Paper (14 pages)) doi:
	Huang, Zhiyi	STOC '16: "The Sample Complexity of Auctions ..." The Sample Complexity of Auctions with Side Information Nikhil R. Devanur, Zhiyi Huang, and Christos-Alexandros Psomas (Microsoft Research, USA; University of Hong Kong, China; University of California at Berkeley, USA) @InProceedings{STOC16p491, author = {Nikhil R. Devanur and Zhiyi Huang and Christos-Alexandros Psomas}, title = {The Sample Complexity of Auctions with Side Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {491-490}, doi = {}, year = {2016}, } Article: stoc16main-main219-p (type: Full Paper (14 pages)) doi:
	Immorlica, Nicole	STOC '16: "The Price of Anarchy in Large ..." The Price of Anarchy in Large Games Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden, and Vasilis Syrgkanis (Tel Aviv University, Israel; Microsoft Research, USA; Stanford University, USA) @InProceedings{STOC16p1093, author = {Michal Feldman and Nicole Immorlica and Brendan Lucier and Tim Roughgarden and Vasilis Syrgkanis}, title = {The Price of Anarchy in Large Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1093-1092}, doi = {}, year = {2016}, } Article: stoc16main-main340-p (type: Full Paper (14 pages)) doi:
	Ivkin, Nikita	STOC '16: "Beating CountSketch for Heavy ..." Beating CountSketch for Heavy Hitters in Insertion Streams Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, and David P. Woodruff (Johns Hopkins University, USA; ETH Zurich, Switzerland; IBM Research, USA) @InProceedings{STOC16p841, author = {Vladimir Braverman and Stephen R. Chestnut and Nikita Ivkin and David P. Woodruff}, title = {Beating CountSketch for Heavy Hitters in Insertion Streams}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {841-840}, doi = {}, year = {2016}, } Article: stoc16main-main240-p (type: Full Paper (14 pages)) doi:
	Ji, Zhengfeng	STOC '16: "Classical Verification of ..." Classical Verification of Quantum Proofs Zhengfeng Ji (University of Technology Sydney, Australia; University of Waterloo, Canada; Institute of Software at Chinese Academy of Sciences, China) @InProceedings{STOC16p1009, author = {Zhengfeng Ji}, title = {Classical Verification of Quantum Proofs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1009-1008}, doi = {}, year = {2016}, } Article: stoc16main-main364-p (type: Full Paper (14 pages)) doi: STOC '16: "Sample-Optimal Tomography ..." Sample-Optimal Tomography of Quantum States Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu (Massachusetts Institute of Technology, USA; University of Technology Sydney, Australia; University of Waterloo, Canada; Institute of Software at Chinese Academy of Sciences, China; University of Oregon, USA; University of Guelph, Canada) @InProceedings{STOC16p1037, author = {Jeongwan Haah and Aram W. Harrow and Zhengfeng Ji and Xiaodi Wu and Nengkun Yu}, title = {Sample-Optimal Tomography of Quantum States}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1037-1036}, doi = {}, year = {2016}, } Article: stoc16main-main351-p (type: Full Paper (14 pages)) doi:
	Kamath, Gautam	STOC '16: "A Size-Free CLT for Poisson ..." A Size-Free CLT for Poisson Multinomials and Its Applications Constantinos Daskalakis, Anindya De, Gautam Kamath, and Christos Tzamos (Massachusetts Institute of Technology, USA; Northwestern University, USA) @InProceedings{STOC16p1219, author = {Constantinos Daskalakis and Anindya De and Gautam Kamath and Christos Tzamos}, title = {A Size-Free CLT for Poisson Multinomials and Its Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1219-1218}, doi = {}, year = {2016}, } Article: stoc16main-main104-p (type: Full Paper (14 pages)) doi:
	Kane, Daniel M.	STOC '16: "The Fourier Transform of Poisson ..." The Fourier Transform of Poisson Multinomial Distributions and Its Algorithmic Applications Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart (University of Southern California, USA; University of California at San Diego, USA) @InProceedings{STOC16p1205, author = {Ilias Diakonikolas and Daniel M. Kane and Alistair Stewart}, title = {The Fourier Transform of Poisson Multinomial Distributions and Its Algorithmic Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1205-1204}, doi = {}, year = {2016}, } Article: stoc16main-main218-p (type: Full Paper (14 pages)) doi: STOC '16: "Super-Linear Gate and Super-Quadratic ..." Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits Daniel M. Kane and Ryan Williams (University of California at San Diego, USA; Stanford University, USA) @InProceedings{STOC16p729, author = {Daniel M. Kane and Ryan Williams}, title = {Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {729-728}, doi = {}, year = {2016}, } Article: stoc16main-main370-p (type: Full Paper (14 pages)) doi:
	Kapralov, Michael	STOC '16: "Sparse Fourier Transform in ..." Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time Michael Kapralov (EPFL, Switzerland) @InProceedings{STOC16p295, author = {Michael Kapralov}, title = {Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {295-294}, doi = {}, year = {2016}, } Article: stoc16main-main442-p (type: Full Paper (14 pages)) doi:
	Karger, David R.	STOC '16: "Enumerating Parametric Global ..." Enumerating Parametric Global Minimum Cuts by Random Interleaving David R. Karger (Massachusetts Institute of Technology, USA) @InProceedings{STOC16p631, author = {David R. Karger}, title = {Enumerating Parametric Global Minimum Cuts by Random Interleaving}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {631-630}, doi = {}, year = {2016}, } Article: stoc16main-main335-p (type: Full Paper (14 pages)) doi:
	Kaufman, Tali	STOC '16: "Bounded Degree Cosystolic ..." Bounded Degree Cosystolic Expanders of Every Dimension Shai Evra and Tali Kaufman (Hebrew University of Jerusalem, Israel; Bar-Ilan University, Israel) @InProceedings{STOC16p43, author = {Shai Evra and Tali Kaufman}, title = {Bounded Degree Cosystolic Expanders of Every Dimension}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {43-42}, doi = {}, year = {2016}, } Article: stoc16main-main190-p (type: Full Paper (14 pages)) doi:
	Kayal, Neeraj	STOC '16: "On the Size of Homogeneous ..." On the Size of Homogeneous and of Depth Four Formulas with Low Individual Degree Neeraj Kayal, Chandan Saha, and Sébastien Tavenas (Microsoft Research, India; Indian Institute of Science, India) @InProceedings{STOC16p715, author = {Neeraj Kayal and Chandan Saha and Sébastien Tavenas}, title = {On the Size of Homogeneous and of Depth Four Formulas with Low Individual Degree}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {715-714}, doi = {}, year = {2016}, } Article: stoc16main-main214-p (type: Full Paper (14 pages)) doi:
	Keller, Barbara	STOC '16: "A Lower Bound for the Distributed ..." A Lower Bound for the Distributed Lovász Local Lemma Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto (ETH Zurich, Switzerland; Tel Aviv University, Israel; Aalto University, Finland; Bitsplitters, Switzerland) @InProceedings{STOC16p547, author = {Sebastian Brandt and Orr Fischer and Juho Hirvonen and Barbara Keller and Tuomo Lempiäinen and Joel Rybicki and Jukka Suomela and Jara Uitto}, title = {A Lower Bound for the Distributed Lovász Local Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {}, year = {2016}, } Article: stoc16main-main300-p (type: Full Paper (14 pages)) doi:
	Kempe, David	STOC '16: "Deterministic and Probabilistic ..." Deterministic and Probabilistic Binary Search in Graphs Ehsan Emamjomeh-Zadeh, David Kempe, and Vikrant Singhal (University of Southern California, USA) @InProceedings{STOC16p603, author = {Ehsan Emamjomeh-Zadeh and David Kempe and Vikrant Singhal}, title = {Deterministic and Probabilistic Binary Search in Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {603-602}, doi = {}, year = {2016}, } Article: stoc16main-main462-p (type: Full Paper (14 pages)) doi:
	Khanna, Sanjeev	STOC '16: "Tight Bounds for Single-Pass ..." Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem Sepehr Assadi, Sanjeev Khanna, and Yang Li (University of Pennsylvania, USA) @InProceedings{STOC16p799, author = {Sepehr Assadi and Sanjeev Khanna and Yang Li}, title = {Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {799-798}, doi = {}, year = {2016}, } Article: stoc16main-main319-p (type: Full Paper (14 pages)) doi:
	Khot, Subhash	STOC '16: "Candidate Hard Unique Game ..." Candidate Hard Unique Game Subhash Khot and Dana Moshkovitz (New York University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC16p71, author = {Subhash Khot and Dana Moshkovitz}, title = {Candidate Hard Unique Game}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {71-70}, doi = {}, year = {2016}, } Article: stoc16main-main140-p (type: Full Paper (14 pages)) doi:
	Kim, David H. K.	STOC '16: "Improved Approximation for ..." Improved Approximation for Node-Disjoint Paths in Planar Graphs Julia Chuzhoy, David H. K. Kim, and Shi Li (Toyota Technological Institute at Chicago, USA; University of Chicago, USA; State University of New York at Buffalo, USA) @InProceedings{STOC16p645, author = {Julia Chuzhoy and David H. K. Kim and Shi Li}, title = {Improved Approximation for Node-Disjoint Paths in Planar Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {645-644}, doi = {}, year = {2016}, } Article: stoc16main-main169-p (type: Full Paper (14 pages)) doi:
	Klein, Philip N.	STOC '16: "Approximating Connectivity ..." Approximating Connectivity Domination in Weighted Bounded-Genus Graphs Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, and David Meierfrankenfeld (ENS, France; CNRS, France; Brown University, USA) @InProceedings{STOC16p673, author = {Vincent Cohen-Addad and Éric Colin de Verdière and Philip N. Klein and Claire Mathieu and David Meierfrankenfeld}, title = {Approximating Connectivity Domination in Weighted Bounded-Genus Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {673-672}, doi = {}, year = {2016}, } Article: stoc16main-main369-p (type: Full Paper (14 pages)) doi:
	Kol, Gillat	STOC '16: "Exponential Separation of ..." Exponential Separation of Communication and External Information Anat Ganor, Gillat Kol, and Ran Raz (Weizmann Institute of Science, Israel; Institute for Advanced Study at Princeton, USA) @InProceedings{STOC16p1107, author = {Anat Ganor and Gillat Kol and Ran Raz}, title = {Exponential Separation of Communication and External Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1107-1106}, doi = {}, year = {2016}, } Article: stoc16main-main164-p (type: Full Paper (14 pages)) doi: STOC '16: "Interactive Compression for ..." Interactive Compression for Product Distributions Gillat Kol (Institute for Advanced Study at Princeton, USA) @InProceedings{STOC16p1121, author = {Gillat Kol}, title = {Interactive Compression for Product Distributions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1121-1120}, doi = {}, year = {2016}, } Article: stoc16main-main168-p (type: Full Paper (14 pages)) doi:
	Kopelowitz, Tsvi	STOC '16: "Contention Resolution with ..." Contention Resolution with Log-Logstar Channel Accesses Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young (Stony Brook University, USA; University of Michigan, USA; Mississippi State University, USA) @InProceedings{STOC16p575, author = {Michael A. Bender and Tsvi Kopelowitz and Seth Pettie and Maxwell Young}, title = {Contention Resolution with Log-Logstar Channel Accesses}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {575-574}, doi = {}, year = {2016}, } Article: stoc16main-main456-p (type: Full Paper (14 pages)) doi:
	Kopparty, Swastik	STOC '16: "High-Rate Locally-Correctable ..." High-Rate Locally-Correctable and Locally-Testable Codes with Sub-polynomial Query Complexity Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf (Rutgers University, USA; Weizmann Institute of Science, Israel; Institute for Advanced Study at Princeton, USA) @InProceedings{STOC16p225, author = {Swastik Kopparty and Or Meir and Noga Ron-Zewi and Shubhangi Saraf}, title = {High-Rate Locally-Correctable and Locally-Testable Codes with Sub-polynomial Query Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {225-224}, doi = {}, year = {2016}, } Article: stoc16main-main122-p (type: Full Paper (14 pages)) doi:
	Koren, Tomer	STOC '16: "The Computational Power of ..." The Computational Power of Optimization in Online Learning Elad Hazan and Tomer Koren (Princeton University, USA; Technion, Israel) @InProceedings{STOC16p141, author = {Elad Hazan and Tomer Koren}, title = {The Computational Power of Optimization in Online Learning}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {141-140}, doi = {}, year = {2016}, } Article: stoc16main-main167-p (type: Full Paper (14 pages)) doi:
	Korman, Amos	STOC '16: "Parallel Exhaustive Search ..." Parallel Exhaustive Search without Coordination Pierre Fraigniaud, Amos Korman, and Yoav Rodeh (CNRS, France; University of Paris Diderot, France; Weizmann Institute of Science, Israel) @InProceedings{STOC16p351, author = {Pierre Fraigniaud and Amos Korman and Yoav Rodeh}, title = {Parallel Exhaustive Search without Coordination}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {351-350}, doi = {}, year = {2016}, } Article: stoc16main-main182-p (type: Full Paper (14 pages)) doi:
	Kothari, Robin	STOC '16: "Separations in Query Complexity ..." Separations in Query Complexity using Cheat Sheets Scott Aaronson, Shalev Ben-David, and Robin Kothari (Massachusetts Institute of Technology, USA) @InProceedings{STOC16p981, author = {Scott Aaronson and Shalev Ben-David and Robin Kothari}, title = {Separations in Query Complexity using Cheat Sheets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {981-980}, doi = {}, year = {2016}, } Article: stoc16main-main423-p (type: Full Paper (14 pages)) doi:
	Koucký, Michal	STOC '16: "Streaming Algorithms for Embedding ..." Streaming Algorithms for Embedding and Computing Edit Distance in the Low Distance Regime Diptarka Chakraborty, Elazar Goldenberg, and Michal Koucký (IIT Kanpur, India; Charles University in Prague, Czechia) @InProceedings{STOC16p813, author = {Diptarka Chakraborty and Elazar Goldenberg and Michal Koucký}, title = {Streaming Algorithms for Embedding and Computing Edit Distance in the Low Distance Regime}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {813-812}, doi = {}, year = {2016}, } Article: stoc16main-main330-p (type: Full Paper (14 pages)) doi:
	Krinninger, Sebastian	STOC '16: "A Deterministic Almost-Tight ..." A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai (University of Vienna, Austria; Max Planck Institute for Informatics, Germany; KTH, Sweden) @InProceedings{STOC16p561, author = {Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai}, title = {A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {561-560}, doi = {}, year = {2016}, } Article: stoc16main-main382-p (type: Full Paper (14 pages)) doi:
	Kudekar, Shrinivas	STOC '16: "Reed-Muller Codes Achieve ..." Reed-Muller Codes Achieve Capacity on Erasure Channels Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Şaşoğlu, and Rüdiger Urbanke (Qualcomm Research, USA; Texas A&M University, USA; EPFL, Switzerland; Duke University, USA; Intel, USA) @InProceedings{STOC16p757, author = {Shrinivas Kudekar and Santhosh Kumar and Marco Mondelli and Henry D. Pfister and Eren Şaşoğlu and Rüdiger Urbanke}, title = {Reed-Muller Codes Achieve Capacity on Erasure Channels}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {757-756}, doi = {}, year = {2016}, } Article: stoc16main-main347-p (type: Full Paper (14 pages)) doi:
	Kumar, Santhosh	STOC '16: "Reed-Muller Codes Achieve ..." Reed-Muller Codes Achieve Capacity on Erasure Channels Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Şaşoğlu, and Rüdiger Urbanke (Qualcomm Research, USA; Texas A&M University, USA; EPFL, Switzerland; Duke University, USA; Intel, USA) @InProceedings{STOC16p757, author = {Shrinivas Kudekar and Santhosh Kumar and Marco Mondelli and Henry D. Pfister and Eren Şaşoğlu and Rüdiger Urbanke}, title = {Reed-Muller Codes Achieve Capacity on Erasure Channels}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {757-756}, doi = {}, year = {2016}, } Article: stoc16main-main347-p (type: Full Paper (14 pages)) doi:
	Kutten, Shay	STOC '16: "Online Matching: Haste Makes ..." Online Matching: Haste Makes Waste! Yuval Emek, Shay Kutten, and Roger Wattenhofer (Technion, Israel; ETH Zurich, Switzerland) @InProceedings{STOC16p379, author = {Yuval Emek and Shay Kutten and Roger Wattenhofer}, title = {Online Matching: Haste Makes Waste!}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {379-378}, doi = {}, year = {2016}, } Article: stoc16main-main239-p (type: Full Paper (14 pages)) doi:
	Kyng, Rasmus	STOC '16: "Sparsified Cholesky and Multigrid ..." Sparsified Cholesky and Multigrid Solvers for Connection Laplacians Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman (Yale University, USA; Massachusetts Institute of Technology, USA; Georgia Tech, USA) @InProceedings{STOC16p953, author = {Rasmus Kyng and Yin Tat Lee and Richard Peng and Sushant Sachdeva and Daniel A. Spielman}, title = {Sparsified Cholesky and Multigrid Solvers for Connection Laplacians}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {953-952}, doi = {}, year = {2016}, } Article: stoc16main-main390-p (type: Full Paper (14 pages)) doi:
	Lee, Troy	STOC '16: "Separations in Query Complexity ..." Separations in Query Complexity Based on Pointer Functions Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs (University of Latvia, Latvia; CWI, Netherlands; Nanyang Technological University, Singapore; National University of Singapore, Singapore; CNRS, France) @InProceedings{STOC16p911, author = {Andris Ambainis and Kaspars Balodis and Aleksandrs Belovs and Troy Lee and Miklos Santha and Juris Smotrovs}, title = {Separations in Query Complexity Based on Pointer Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {911-910}, doi = {}, year = {2016}, } Article: stoc16main-main123-p (type: Full Paper (14 pages)) doi:
	Lee, Yin Tat	STOC '16: "Geometric Median in Nearly ..." Geometric Median in Nearly Linear Time Michael B. Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford (Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; Microsoft Research, USA) @InProceedings{STOC16p15, author = {Michael B. Cohen and Yin Tat Lee and Gary Miller and Jakub Pachocki and Aaron Sidford}, title = {Geometric Median in Nearly Linear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {15-14}, doi = {}, year = {2016}, } Article: stoc16main-main436-p (type: Full Paper (14 pages)) doi: STOC '16: "Sparsified Cholesky and Multigrid ..." Sparsified Cholesky and Multigrid Solvers for Connection Laplacians Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman (Yale University, USA; Massachusetts Institute of Technology, USA; Georgia Tech, USA) @InProceedings{STOC16p953, author = {Rasmus Kyng and Yin Tat Lee and Richard Peng and Sushant Sachdeva and Daniel A. Spielman}, title = {Sparsified Cholesky and Multigrid Solvers for Connection Laplacians}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {953-952}, doi = {}, year = {2016}, } Article: stoc16main-main390-p (type: Full Paper (14 pages)) doi:
	Lempiäinen, Tuomo	STOC '16: "A Lower Bound for the Distributed ..." A Lower Bound for the Distributed Lovász Local Lemma Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto (ETH Zurich, Switzerland; Tel Aviv University, Israel; Aalto University, Finland; Bitsplitters, Switzerland) @InProceedings{STOC16p547, author = {Sebastian Brandt and Orr Fischer and Juho Hirvonen and Barbara Keller and Tuomo Lempiäinen and Joel Rybicki and Jukka Suomela and Jara Uitto}, title = {A Lower Bound for the Distributed Lovász Local Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {}, year = {2016}, } Article: stoc16main-main300-p (type: Full Paper (14 pages)) doi:
	Levey, Elaine	STOC '16: "A (1+epsilon)-Approximation ..." A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints using LP Hierarchies Elaine Levey and Thomas Rothvoss (University of Washington, USA) @InProceedings{STOC16p183, author = {Elaine Levey and Thomas Rothvoss}, title = {A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints using LP Hierarchies}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {183-182}, doi = {}, year = {2016}, } Article: stoc16main-main145-p (type: Full Paper (14 pages)) doi:
	Li, Shi	STOC '16: "Improved Approximation for ..." Improved Approximation for Node-Disjoint Paths in Planar Graphs Julia Chuzhoy, David H. K. Kim, and Shi Li (Toyota Technological Institute at Chicago, USA; University of Chicago, USA; State University of New York at Buffalo, USA) @InProceedings{STOC16p645, author = {Julia Chuzhoy and David H. K. Kim and Shi Li}, title = {Improved Approximation for Node-Disjoint Paths in Planar Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {645-644}, doi = {}, year = {2016}, } Article: stoc16main-main169-p (type: Full Paper (14 pages)) doi:
	Li, Xin	STOC '16: "Non-malleable Extractors and ..." Non-malleable Extractors and Codes, with Their Many Tampered Extensions Eshan Chattopadhyay, Vipul Goyal, and Xin Li (University of Texas at Austin, USA; Microsoft Research, India; Johns Hopkins University, USA) @InProceedings{STOC16p323, author = {Eshan Chattopadhyay and Vipul Goyal and Xin Li}, title = {Non-malleable Extractors and Codes, with Their Many Tampered Extensions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {323-322}, doi = {}, year = {2016}, } Article: stoc16main-main207-p (type: Full Paper (14 pages)) doi: STOC '16: "Extractors for Sumset Sources ..." Extractors for Sumset Sources Eshan Chattopadhyay and Xin Li (University of Texas at Austin, USA; Johns Hopkins University, USA) @InProceedings{STOC16p337, author = {Eshan Chattopadhyay and Xin Li}, title = {Extractors for Sumset Sources}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {337-336}, doi = {}, year = {2016}, } Article: stoc16main-main422-p (type: Full Paper (14 pages)) doi:
	Li, Yang	STOC '16: "Tight Bounds for Single-Pass ..." Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem Sepehr Assadi, Sanjeev Khanna, and Yang Li (University of Pennsylvania, USA) @InProceedings{STOC16p799, author = {Sepehr Assadi and Sanjeev Khanna and Yang Li}, title = {Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {799-798}, doi = {}, year = {2016}, } Article: stoc16main-main319-p (type: Full Paper (14 pages)) doi:
	Li, Yi	STOC '16: "On Approximating Functions ..." On Approximating Functions of the Singular Values in a Stream Yi Li and David P. Woodruff (Facebook, USA; IBM Research, USA) @InProceedings{STOC16p827, author = {Yi Li and David P. Woodruff}, title = {On Approximating Functions of the Singular Values in a Stream}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {827-826}, doi = {}, year = {2016}, } Article: stoc16main-main341-p (type: Full Paper (14 pages)) doi:
	Lokshtanov, Daniel	STOC '16: "Exact Algorithms via Monotone ..." Exact Algorithms via Monotone Local Search Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh (University of Bergen, Norway; UNSW, Australia; Data61, Australia; Institute of Mathematical Sciences at Chennai, India) @InProceedings{STOC16p869, author = {Fedor V. Fomin and Serge Gaspers and Daniel Lokshtanov and Saket Saurabh}, title = {Exact Algorithms via Monotone Local Search}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {869-868}, doi = {}, year = {2016}, } Article: stoc16main-main216-p (type: Full Paper (14 pages)) doi:
	Lovett, Shachar	STOC '16: "Algebraic Attacks against ..." Algebraic Attacks against Random Local Functions and Their Countermeasures Benny Applebaum and Shachar Lovett (Tel Aviv University, Israel; University of California at San Diego, USA) @InProceedings{STOC16p1233, author = {Benny Applebaum and Shachar Lovett}, title = {Algebraic Attacks against Random Local Functions and Their Countermeasures}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1233-1232}, doi = {}, year = {2016}, } Article: stoc16main-main230-p (type: Full Paper (14 pages)) doi:
	Lucier, Brendan	STOC '16: "The Price of Anarchy in Large ..." The Price of Anarchy in Large Games Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden, and Vasilis Syrgkanis (Tel Aviv University, Israel; Microsoft Research, USA; Stanford University, USA) @InProceedings{STOC16p1093, author = {Michal Feldman and Nicole Immorlica and Brendan Lucier and Tim Roughgarden and Vasilis Syrgkanis}, title = {The Price of Anarchy in Large Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1093-1092}, doi = {}, year = {2016}, } Article: stoc16main-main340-p (type: Full Paper (14 pages)) doi:
	Ma, Tengyu	STOC '16: "Communication Lower Bounds ..." Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, and David P. Woodruff (Princeton University, USA; Toyota Technological Institute at Chicago, USA; IBM Research, USA) @InProceedings{STOC16p1149, author = {Mark Braverman and Ankit Garg and Tengyu Ma and Huy L. Nguyen and David P. Woodruff}, title = {Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1149-1148}, doi = {}, year = {2016}, } Article: stoc16main-main342-p (type: Full Paper (14 pages)) doi:
	Mackenzie, Simon	STOC '16: "A Discrete and Bounded Envy-Free ..." A Discrete and Bounded Envy-Free Cake Cutting Protocol for Four Agents Haris Aziz and Simon Mackenzie (Data61, Australia; UNSW, Australia) @InProceedings{STOC16p519, author = {Haris Aziz and Simon Mackenzie}, title = {A Discrete and Bounded Envy-Free Cake Cutting Protocol for Four Agents}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {519-518}, doi = {}, year = {2016}, } Article: stoc16main-main121-p (type: Full Paper (14 pages)) doi:
	Mao, Jieming	STOC '16: "Parallel Algorithms for Select ..." Parallel Algorithms for Select and Partition with Noisy Comparisons Mark Braverman, Jieming Mao, and S. Matthew Weinberg (Princeton University, USA) @InProceedings{STOC16p967, author = {Mark Braverman and Jieming Mao and S. Matthew Weinberg}, title = {Parallel Algorithms for Select and Partition with Noisy Comparisons}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {967-966}, doi = {}, year = {2016}, } Article: stoc16main-main419-p (type: Full Paper (14 pages)) doi:
	Marx, Dániel	STOC '16: "A PTAS for Planar Group Steiner ..." A PTAS for Planar Group Steiner Tree via Spanner Bootstrapping and Prize Collecting MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx (Google, USA; Massachusetts Institute of Technology, USA; University of Maryland at College Park, USA; Hungarian Academy of Sciences, Hungary) @InProceedings{STOC16p659, author = {MohammadHossein Bateni and Erik D. Demaine and MohammadTaghi Hajiaghayi and Dániel Marx}, title = {A PTAS for Planar Group Steiner Tree via Spanner Bootstrapping and Prize Collecting}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {659-658}, doi = {}, year = {2016}, } Article: stoc16main-main213-p (type: Full Paper (14 pages)) doi:
	Mathieu, Claire	STOC '16: "Approximating Connectivity ..." Approximating Connectivity Domination in Weighted Bounded-Genus Graphs Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, and David Meierfrankenfeld (ENS, France; CNRS, France; Brown University, USA) @InProceedings{STOC16p673, author = {Vincent Cohen-Addad and Éric Colin de Verdière and Philip N. Klein and Claire Mathieu and David Meierfrankenfeld}, title = {Approximating Connectivity Domination in Weighted Bounded-Genus Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {673-672}, doi = {}, year = {2016}, } Article: stoc16main-main369-p (type: Full Paper (14 pages)) doi:
	Meierfrankenfeld, David	STOC '16: "Approximating Connectivity ..." Approximating Connectivity Domination in Weighted Bounded-Genus Graphs Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, and David Meierfrankenfeld (ENS, France; CNRS, France; Brown University, USA) @InProceedings{STOC16p673, author = {Vincent Cohen-Addad and Éric Colin de Verdière and Philip N. Klein and Claire Mathieu and David Meierfrankenfeld}, title = {Approximating Connectivity Domination in Weighted Bounded-Genus Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {673-672}, doi = {}, year = {2016}, } Article: stoc16main-main369-p (type: Full Paper (14 pages)) doi:
	Meir, Or	STOC '16: "High-Rate Locally-Correctable ..." High-Rate Locally-Correctable and Locally-Testable Codes with Sub-polynomial Query Complexity Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf (Rutgers University, USA; Weizmann Institute of Science, Israel; Institute for Advanced Study at Princeton, USA) @InProceedings{STOC16p225, author = {Swastik Kopparty and Or Meir and Noga Ron-Zewi and Shubhangi Saraf}, title = {High-Rate Locally-Correctable and Locally-Testable Codes with Sub-polynomial Query Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {225-224}, doi = {}, year = {2016}, } Article: stoc16main-main122-p (type: Full Paper (14 pages)) doi:
	Miller, Gary	STOC '16: "Geometric Median in Nearly ..." Geometric Median in Nearly Linear Time Michael B. Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford (Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; Microsoft Research, USA) @InProceedings{STOC16p15, author = {Michael B. Cohen and Yin Tat Lee and Gary Miller and Jakub Pachocki and Aaron Sidford}, title = {Geometric Median in Nearly Linear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {15-14}, doi = {}, year = {2016}, } Article: stoc16main-main436-p (type: Full Paper (14 pages)) doi: STOC '16: "Routing under Balance ..." Routing under Balance Alina Ene, Gary Miller, Jakub Pachocki, and Aaron Sidford (University of Warwick, UK; Carnegie Mellon University, USA; Microsoft Research, USA) @InProceedings{STOC16p687, author = {Alina Ene and Gary Miller and Jakub Pachocki and Aaron Sidford}, title = {Routing under Balance}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {687-686}, doi = {}, year = {2016}, } Article: stoc16main-main454-p (type: Full Paper (14 pages)) doi:
	Moitra, Ankur	STOC '16: "How Robust Are Reconstruction ..." How Robust Are Reconstruction Thresholds for Community Detection? Ankur Moitra, William Perry, and Alexander S. Wein (Massachusetts Institute of Technology, USA) @InProceedings{STOC16p939, author = {Ankur Moitra and William Perry and Alexander S. Wein}, title = {How Robust Are Reconstruction Thresholds for Community Detection?}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {939-938}, doi = {}, year = {2016}, } Article: stoc16main-main311-p (type: Full Paper (14 pages)) doi:
	Mondelli, Marco	STOC '16: "Reed-Muller Codes Achieve ..." Reed-Muller Codes Achieve Capacity on Erasure Channels Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Şaşoğlu, and Rüdiger Urbanke (Qualcomm Research, USA; Texas A&M University, USA; EPFL, Switzerland; Duke University, USA; Intel, USA) @InProceedings{STOC16p757, author = {Shrinivas Kudekar and Santhosh Kumar and Marco Mondelli and Henry D. Pfister and Eren Şaşoğlu and Rüdiger Urbanke}, title = {Reed-Muller Codes Achieve Capacity on Erasure Channels}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {757-756}, doi = {}, year = {2016}, } Article: stoc16main-main347-p (type: Full Paper (14 pages)) doi:
	Montanari, Andrea	STOC '16: "Semidefinite Programs on Sparse ..." Semidefinite Programs on Sparse Random Graphs and Their Application to Community Detection Andrea Montanari and Subhabrata Sen (Stanford University, USA) @InProceedings{STOC16p925, author = {Andrea Montanari and Subhabrata Sen}, title = {Semidefinite Programs on Sparse Random Graphs and Their Application to Community Detection}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {925-924}, doi = {}, year = {2016}, } Article: stoc16main-main209-p (type: Full Paper (14 pages)) doi:
	Morgenstern, Jamie	STOC '16: "Do Prices Coordinate Markets? ..." Do Prices Coordinate Markets? Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth, and Rakesh Vohra (University of Pennsylvania, USA) @InProceedings{STOC16p505, author = {Justin Hsu and Jamie Morgenstern and Ryan Rogers and Aaron Roth and Rakesh Vohra}, title = {Do Prices Coordinate Markets?}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {505-504}, doi = {}, year = {2016}, } Article: stoc16main-main246-p (type: Full Paper (14 pages)) doi:
	Moshkovitz, Dana	STOC '16: "Candidate Hard Unique Game ..." Candidate Hard Unique Game Subhash Khot and Dana Moshkovitz (New York University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC16p71, author = {Subhash Khot and Dana Moshkovitz}, title = {Candidate Hard Unique Game}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {71-70}, doi = {}, year = {2016}, } Article: stoc16main-main140-p (type: Full Paper (14 pages)) doi:
	Nanongkai, Danupon	STOC '16: "New Deterministic Approximation ..." New Deterministic Approximation Algorithms for Fully Dynamic Matching Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai (Institute of Mathematical Sciences at Chennai, India; University of Vienna, Austria; KTH, Sweden) @InProceedings{STOC16p463, author = {Sayan Bhattacharya and Monika Henzinger and Danupon Nanongkai}, title = {New Deterministic Approximation Algorithms for Fully Dynamic Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {463-462}, doi = {}, year = {2016}, } Article: stoc16main-main293-p (type: Full Paper (14 pages)) doi: STOC '16: "A Deterministic Almost-Tight ..." A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai (University of Vienna, Austria; Max Planck Institute for Informatics, Germany; KTH, Sweden) @InProceedings{STOC16p561, author = {Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai}, title = {A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {561-560}, doi = {}, year = {2016}, } Article: stoc16main-main382-p (type: Full Paper (14 pages)) doi:
	Naor, Moni	STOC '16: "Searchable Symmetric Encryption: ..." Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations Gilad Asharov, Moni Naor, Gil Segev, and Ido Shahaf (IBM Research, USA; Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel) @InProceedings{STOC16p1247, author = {Gilad Asharov and Moni Naor and Gil Segev and Ido Shahaf}, title = {Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1247-1246}, doi = {}, year = {2016}, } Article: stoc16main-main256-p (type: Full Paper (14 pages)) doi:
	Nguyen, Huy L.	STOC '16: "Communication Lower Bounds ..." Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, and David P. Woodruff (Princeton University, USA; Toyota Technological Institute at Chicago, USA; IBM Research, USA) @InProceedings{STOC16p1149, author = {Mark Braverman and Ankit Garg and Tengyu Ma and Huy L. Nguyen and David P. Woodruff}, title = {Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1149-1148}, doi = {}, year = {2016}, } Article: stoc16main-main342-p (type: Full Paper (14 pages)) doi:
	Nikolov, Aleksandar	STOC '16: "Maximizing Determinants under ..." Maximizing Determinants under Partition Constraints Aleksandar Nikolov and Mohit Singh (University of Toronto, Canada; Microsoft Research, USA) @InProceedings{STOC16p211, author = {Aleksandar Nikolov and Mohit Singh}, title = {Maximizing Determinants under Partition Constraints}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {211-210}, doi = {}, year = {2016}, } Article: stoc16main-main440-p (type: Full Paper (14 pages)) doi:
	Nishimaki, Ryo	STOC '16: "Watermarking Cryptographic ..." Watermarking Cryptographic Capabilities Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, and Daniel Wichs (Massachusetts Institute of Technology, USA; NTT, Japan; Northeastern University, USA) @InProceedings{STOC16p1261, author = {Aloni Cohen and Justin Holmgren and Ryo Nishimaki and Vinod Vaikuntanathan and Daniel Wichs}, title = {Watermarking Cryptographic Capabilities}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1261-1260}, doi = {}, year = {2016}, } Article: stoc16main-main448-p (type: Full Paper (14 pages)) doi:
	Nissim, Kobbi	STOC '16: "Algorithmic Stability for ..." Algorithmic Stability for Adaptive Data Analysis Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman (University of California at San Diego, USA; Ben-Gurion University of the Negev, Israel; Harvard University, USA; Pennsylvania State University, USA; Northeastern University, USA) @InProceedings{STOC16p1191, author = {Raef Bassily and Kobbi Nissim and Adam Smith and Thomas Steinke and Uri Stemmer and Jonathan Ullman}, title = {Algorithmic Stability for Adaptive Data Analysis}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1191-1190}, doi = {}, year = {2016}, } Article: stoc16main-main278-p (type: Full Paper (14 pages)) doi:
	O'Donnell, Ryan	STOC '16: "Efficient Quantum Tomography ..." Efficient Quantum Tomography Ryan O'Donnell and John Wright (Carnegie Mellon University, USA) @InProceedings{STOC16p1023, author = {Ryan O'Donnell and John Wright}, title = {Efficient Quantum Tomography}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1023-1022}, doi = {}, year = {2016}, } Article: stoc16main-main191-p (type: Full Paper (14 pages)) doi:
	Oliveira, Igor C.	STOC '16: "Near-Optimal Small-Depth Lower ..." Near-Optimal Small-Depth Lower Bounds for Small Distance Connectivity Xi Chen, Igor C. Oliveira, Rocco A. Servedio, and Li-Yang Tan (Columbia University, USA; Charles University in Prague, Czechia; Toyota Technological Institute at Chicago, USA) @InProceedings{STOC16p701, author = {Xi Chen and Igor C. Oliveira and Rocco A. Servedio and Li-Yang Tan}, title = {Near-Optimal Small-Depth Lower Bounds for Small Distance Connectivity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {701-700}, doi = {}, year = {2016}, } Article: stoc16main-main158-p (type: Full Paper (14 pages)) doi:
	Pachocki, Jakub	STOC '16: "Geometric Median in Nearly ..." Geometric Median in Nearly Linear Time Michael B. Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford (Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; Microsoft Research, USA) @InProceedings{STOC16p15, author = {Michael B. Cohen and Yin Tat Lee and Gary Miller and Jakub Pachocki and Aaron Sidford}, title = {Geometric Median in Nearly Linear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {15-14}, doi = {}, year = {2016}, } Article: stoc16main-main436-p (type: Full Paper (14 pages)) doi: STOC '16: "Routing under Balance ..." Routing under Balance Alina Ene, Gary Miller, Jakub Pachocki, and Aaron Sidford (University of Warwick, UK; Carnegie Mellon University, USA; Microsoft Research, USA) @InProceedings{STOC16p687, author = {Alina Ene and Gary Miller and Jakub Pachocki and Aaron Sidford}, title = {Routing under Balance}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {687-686}, doi = {}, year = {2016}, } Article: stoc16main-main454-p (type: Full Paper (14 pages)) doi:
	Pandey, Omkant	STOC '16: "Textbook Non-malleable Commitments ..." Textbook Non-malleable Commitments Vipul Goyal, Omkant Pandey, and Silas Richelson (Microsoft Research, India; Drexel University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC16p1275, author = {Vipul Goyal and Omkant Pandey and Silas Richelson}, title = {Textbook Non-malleable Commitments}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1275-1274}, doi = {}, year = {2016}, } Article: stoc16main-main464-p (type: Full Paper (14 pages)) doi:
	Pegden, Wesley	STOC '16: "Separating Subadditive Euclidean ..." Separating Subadditive Euclidean Functionals Alan Frieze and Wesley Pegden (Carnegie Mellon University, USA) @InProceedings{STOC16p29, author = {Alan Frieze and Wesley Pegden}, title = {Separating Subadditive Euclidean Functionals}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {29-28}, doi = {}, year = {2016}, } Article: stoc16main-main301-p (type: Full Paper (14 pages)) doi:
	Peng, Pan	STOC '16: "Relating Two Property Testing ..." Relating Two Property Testing Models for Bounded Degree Directed Graphs Artur Czumaj, Pan Peng, and Christian Sohler (University of Warwick, UK; TU Dortmund, Germany; Institute of Software at Chinese Academy of Sciences, China) @InProceedings{STOC16p1177, author = {Artur Czumaj and Pan Peng and Christian Sohler}, title = {Relating Two Property Testing Models for Bounded Degree Directed Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1177-1176}, doi = {}, year = {2016}, } Article: stoc16main-main314-p (type: Full Paper (14 pages)) doi:
	Peng, Richard	STOC '16: "Sparsified Cholesky and Multigrid ..." Sparsified Cholesky and Multigrid Solvers for Connection Laplacians Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman (Yale University, USA; Massachusetts Institute of Technology, USA; Georgia Tech, USA) @InProceedings{STOC16p953, author = {Rasmus Kyng and Yin Tat Lee and Richard Peng and Sushant Sachdeva and Daniel A. Spielman}, title = {Sparsified Cholesky and Multigrid Solvers for Connection Laplacians}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {953-952}, doi = {}, year = {2016}, } Article: stoc16main-main390-p (type: Full Paper (14 pages)) doi:
	Perry, William	STOC '16: "How Robust Are Reconstruction ..." How Robust Are Reconstruction Thresholds for Community Detection? Ankur Moitra, William Perry, and Alexander S. Wein (Massachusetts Institute of Technology, USA) @InProceedings{STOC16p939, author = {Ankur Moitra and William Perry and Alexander S. Wein}, title = {How Robust Are Reconstruction Thresholds for Community Detection?}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {939-938}, doi = {}, year = {2016}, } Article: stoc16main-main311-p (type: Full Paper (14 pages)) doi:
	Pettie, Seth	STOC '16: "Contention Resolution with ..." Contention Resolution with Log-Logstar Channel Accesses Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young (Stony Brook University, USA; University of Michigan, USA; Mississippi State University, USA) @InProceedings{STOC16p575, author = {Michael A. Bender and Tsvi Kopelowitz and Seth Pettie and Maxwell Young}, title = {Contention Resolution with Log-Logstar Channel Accesses}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {575-574}, doi = {}, year = {2016}, } Article: stoc16main-main456-p (type: Full Paper (14 pages)) doi:
	Pfister, Henry D.	STOC '16: "Reed-Muller Codes Achieve ..." Reed-Muller Codes Achieve Capacity on Erasure Channels Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Şaşoğlu, and Rüdiger Urbanke (Qualcomm Research, USA; Texas A&M University, USA; EPFL, Switzerland; Duke University, USA; Intel, USA) @InProceedings{STOC16p757, author = {Shrinivas Kudekar and Santhosh Kumar and Marco Mondelli and Henry D. Pfister and Eren Şaşoğlu and Rüdiger Urbanke}, title = {Reed-Muller Codes Achieve Capacity on Erasure Channels}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {757-756}, doi = {}, year = {2016}, } Article: stoc16main-main347-p (type: Full Paper (14 pages)) doi:
	Pitassi, Toniann	STOC '16: "Poly-logarithmic Frege Depth ..." Poly-logarithmic Frege Depth Lower Bounds via an Expander Switching Lemma Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan (University of Toronto, Canada; National Institute of Informatics, Japan; Columbia University, USA; Toyota Technological Institute at Chicago, USA) @InProceedings{STOC16p743, author = {Toniann Pitassi and Benjamin Rossman and Rocco A. Servedio and Li-Yang Tan}, title = {Poly-logarithmic Frege Depth Lower Bounds via an Expander Switching Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {743-742}, doi = {}, year = {2016}, } Article: stoc16main-main380-p (type: Full Paper (14 pages)) doi:
	Psomas, Christos-Alexandros	STOC '16: "The Sample Complexity of Auctions ..." The Sample Complexity of Auctions with Side Information Nikhil R. Devanur, Zhiyi Huang, and Christos-Alexandros Psomas (Microsoft Research, USA; University of Hong Kong, China; University of California at Berkeley, USA) @InProceedings{STOC16p491, author = {Nikhil R. Devanur and Zhiyi Huang and Christos-Alexandros Psomas}, title = {The Sample Complexity of Auctions with Side Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {491-490}, doi = {}, year = {2016}, } Article: stoc16main-main219-p (type: Full Paper (14 pages)) doi:
	Puder, Doron	STOC '16: "Ramanujan Coverings of Graphs ..." Ramanujan Coverings of Graphs Chris Hall, Doron Puder, and William F. Sawin (University of Wyoming, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA) @InProceedings{STOC16p617, author = {Chris Hall and Doron Puder and William F. Sawin}, title = {Ramanujan Coverings of Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {617-616}, doi = {}, year = {2016}, } Article: stoc16main-main313-p (type: Full Paper (14 pages)) doi:
	Raz, Ran	STOC '16: "Exponential Separation of ..." Exponential Separation of Communication and External Information Anat Ganor, Gillat Kol, and Ran Raz (Weizmann Institute of Science, Israel; Institute for Advanced Study at Princeton, USA) @InProceedings{STOC16p1107, author = {Anat Ganor and Gillat Kol and Ran Raz}, title = {Exponential Separation of Communication and External Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1107-1106}, doi = {}, year = {2016}, } Article: stoc16main-main164-p (type: Full Paper (14 pages)) doi:
	Razenshteyn, Ilya	STOC '16: "Weighted Low Rank Approximations ..." Weighted Low Rank Approximations with Provable Guarantees Ilya Razenshteyn, Zhao Song, and David P. Woodruff (Massachusetts Institute of Technology, USA; University of Texas at Austin, USA; IBM Research, USA) @InProceedings{STOC16p281, author = {Ilya Razenshteyn and Zhao Song and David P. Woodruff}, title = {Weighted Low Rank Approximations with Provable Guarantees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {281-280}, doi = {}, year = {2016}, } Article: stoc16main-main387-p (type: Full Paper (14 pages)) doi:
	Reingold, Omer	STOC '16: "Constant-Round Interactive ..." Constant-Round Interactive Proofs for Delegating Computation Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum (Samsung Research, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC16p57, author = {Omer Reingold and Guy N. Rothblum and Ron D. Rothblum}, title = {Constant-Round Interactive Proofs for Delegating Computation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {57-56}, doi = {}, year = {2016}, } Article: stoc16main-main449-p (type: Full Paper (14 pages)) doi:
	Richelson, Silas	STOC '16: "Textbook Non-malleable Commitments ..." Textbook Non-malleable Commitments Vipul Goyal, Omkant Pandey, and Silas Richelson (Microsoft Research, India; Drexel University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC16p1275, author = {Vipul Goyal and Omkant Pandey and Silas Richelson}, title = {Textbook Non-malleable Commitments}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1275-1274}, doi = {}, year = {2016}, } Article: stoc16main-main464-p (type: Full Paper (14 pages)) doi:
	Rodeh, Yoav	STOC '16: "Parallel Exhaustive Search ..." Parallel Exhaustive Search without Coordination Pierre Fraigniaud, Amos Korman, and Yoav Rodeh (CNRS, France; University of Paris Diderot, France; Weizmann Institute of Science, Israel) @InProceedings{STOC16p351, author = {Pierre Fraigniaud and Amos Korman and Yoav Rodeh}, title = {Parallel Exhaustive Search without Coordination}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {351-350}, doi = {}, year = {2016}, } Article: stoc16main-main182-p (type: Full Paper (14 pages)) doi:
	Roditty, Liam	STOC '16: "Fault Tolerant Subgraph for ..." Fault Tolerant Subgraph for Single Source Reachability: Generic and Optimal Surender Baswana, Keerti Choudhary, and Liam Roditty (IIT Kanpur, India; Bar-Ilan University, Israel) @InProceedings{STOC16p589, author = {Surender Baswana and Keerti Choudhary and Liam Roditty}, title = {Fault Tolerant Subgraph for Single Source Reachability: Generic and Optimal}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {589-588}, doi = {}, year = {2016}, } Article: stoc16main-main437-p (type: Full Paper (14 pages)) doi:
	Rogers, Ryan	STOC '16: "Do Prices Coordinate Markets? ..." Do Prices Coordinate Markets? Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth, and Rakesh Vohra (University of Pennsylvania, USA) @InProceedings{STOC16p505, author = {Justin Hsu and Jamie Morgenstern and Ryan Rogers and Aaron Roth and Rakesh Vohra}, title = {Do Prices Coordinate Markets?}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {505-504}, doi = {}, year = {2016}, } Article: stoc16main-main246-p (type: Full Paper (14 pages)) doi:
	Ron-Zewi, Noga	STOC '16: "High-Rate Locally-Correctable ..." High-Rate Locally-Correctable and Locally-Testable Codes with Sub-polynomial Query Complexity Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf (Rutgers University, USA; Weizmann Institute of Science, Israel; Institute for Advanced Study at Princeton, USA) @InProceedings{STOC16p225, author = {Swastik Kopparty and Or Meir and Noga Ron-Zewi and Shubhangi Saraf}, title = {High-Rate Locally-Correctable and Locally-Testable Codes with Sub-polynomial Query Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {225-224}, doi = {}, year = {2016}, } Article: stoc16main-main122-p (type: Full Paper (14 pages)) doi:
	Rossman, Benjamin	STOC '16: "Poly-logarithmic Frege Depth ..." Poly-logarithmic Frege Depth Lower Bounds via an Expander Switching Lemma Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan (University of Toronto, Canada; National Institute of Informatics, Japan; Columbia University, USA; Toyota Technological Institute at Chicago, USA) @InProceedings{STOC16p743, author = {Toniann Pitassi and Benjamin Rossman and Rocco A. Servedio and Li-Yang Tan}, title = {Poly-logarithmic Frege Depth Lower Bounds via an Expander Switching Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {743-742}, doi = {}, year = {2016}, } Article: stoc16main-main380-p (type: Full Paper (14 pages)) doi:
	Roth, Aaron	STOC '16: "Watch and Learn: Optimizing ..." Watch and Learn: Optimizing from Revealed Preferences Feedback Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu (University of Pennsylvania, USA; Northeastern University, USA) @InProceedings{STOC16p1079, author = {Aaron Roth and Jonathan Ullman and Zhiwei Steven Wu}, title = {Watch and Learn: Optimizing from Revealed Preferences Feedback}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1079-1078}, doi = {}, year = {2016}, } Article: stoc16main-main336-p (type: Full Paper (14 pages)) doi: STOC '16: "Do Prices Coordinate Markets? ..." Do Prices Coordinate Markets? Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth, and Rakesh Vohra (University of Pennsylvania, USA) @InProceedings{STOC16p505, author = {Justin Hsu and Jamie Morgenstern and Ryan Rogers and Aaron Roth and Rakesh Vohra}, title = {Do Prices Coordinate Markets?}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {505-504}, doi = {}, year = {2016}, } Article: stoc16main-main246-p (type: Full Paper (14 pages)) doi:
	Rothblum, Guy N.	STOC '16: "Constant-Round Interactive ..." Constant-Round Interactive Proofs for Delegating Computation Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum (Samsung Research, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC16p57, author = {Omer Reingold and Guy N. Rothblum and Ron D. Rothblum}, title = {Constant-Round Interactive Proofs for Delegating Computation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {57-56}, doi = {}, year = {2016}, } Article: stoc16main-main449-p (type: Full Paper (14 pages)) doi:
	Rothblum, Ron D.	STOC '16: "Constant-Round Interactive ..." Constant-Round Interactive Proofs for Delegating Computation Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum (Samsung Research, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC16p57, author = {Omer Reingold and Guy N. Rothblum and Ron D. Rothblum}, title = {Constant-Round Interactive Proofs for Delegating Computation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {57-56}, doi = {}, year = {2016}, } Article: stoc16main-main449-p (type: Full Paper (14 pages)) doi:
	Rothvoss, Thomas	STOC '16: "A (1+epsilon)-Approximation ..." A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints using LP Hierarchies Elaine Levey and Thomas Rothvoss (University of Washington, USA) @InProceedings{STOC16p183, author = {Elaine Levey and Thomas Rothvoss}, title = {A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints using LP Hierarchies}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {183-182}, doi = {}, year = {2016}, } Article: stoc16main-main145-p (type: Full Paper (14 pages)) doi:
	Roughgarden, Tim	STOC '16: "The Price of Anarchy in Large ..." The Price of Anarchy in Large Games Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden, and Vasilis Syrgkanis (Tel Aviv University, Israel; Microsoft Research, USA; Stanford University, USA) @InProceedings{STOC16p1093, author = {Michal Feldman and Nicole Immorlica and Brendan Lucier and Tim Roughgarden and Vasilis Syrgkanis}, title = {The Price of Anarchy in Large Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1093-1092}, doi = {}, year = {2016}, } Article: stoc16main-main340-p (type: Full Paper (14 pages)) doi:
	Rubinstein, Aviad	STOC '16: "Beyond Matroids: Secretary ..." Beyond Matroids: Secretary Problem and Prophet Inequality with General Constraints Aviad Rubinstein (University of California at Berkeley, USA) @InProceedings{STOC16p365, author = {Aviad Rubinstein}, title = {Beyond Matroids: Secretary Problem and Prophet Inequality with General Constraints}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {365-364}, doi = {}, year = {2016}, } Article: stoc16main-main176-p (type: Full Paper (14 pages)) doi:
	Rybicki, Joel	STOC '16: "A Lower Bound for the Distributed ..." A Lower Bound for the Distributed Lovász Local Lemma Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto (ETH Zurich, Switzerland; Tel Aviv University, Israel; Aalto University, Finland; Bitsplitters, Switzerland) @InProceedings{STOC16p547, author = {Sebastian Brandt and Orr Fischer and Juho Hirvonen and Barbara Keller and Tuomo Lempiäinen and Joel Rybicki and Jukka Suomela and Jara Uitto}, title = {A Lower Bound for the Distributed Lovász Local Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {}, year = {2016}, } Article: stoc16main-main300-p (type: Full Paper (14 pages)) doi:
	Sachdeva, Sushant	STOC '16: "Sparsified Cholesky and Multigrid ..." Sparsified Cholesky and Multigrid Solvers for Connection Laplacians Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman (Yale University, USA; Massachusetts Institute of Technology, USA; Georgia Tech, USA) @InProceedings{STOC16p953, author = {Rasmus Kyng and Yin Tat Lee and Richard Peng and Sushant Sachdeva and Daniel A. Spielman}, title = {Sparsified Cholesky and Multigrid Solvers for Connection Laplacians}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {953-952}, doi = {}, year = {2016}, } Article: stoc16main-main390-p (type: Full Paper (14 pages)) doi:
	Saha, Chandan	STOC '16: "On the Size of Homogeneous ..." On the Size of Homogeneous and of Depth Four Formulas with Low Individual Degree Neeraj Kayal, Chandan Saha, and Sébastien Tavenas (Microsoft Research, India; Indian Institute of Science, India) @InProceedings{STOC16p715, author = {Neeraj Kayal and Chandan Saha and Sébastien Tavenas}, title = {On the Size of Homogeneous and of Depth Four Formulas with Low Individual Degree}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {715-714}, doi = {}, year = {2016}, } Article: stoc16main-main214-p (type: Full Paper (14 pages)) doi:
	Santha, Miklos	STOC '16: "Separations in Query Complexity ..." Separations in Query Complexity Based on Pointer Functions Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs (University of Latvia, Latvia; CWI, Netherlands; Nanyang Technological University, Singapore; National University of Singapore, Singapore; CNRS, France) @InProceedings{STOC16p911, author = {Andris Ambainis and Kaspars Balodis and Aleksandrs Belovs and Troy Lee and Miklos Santha and Juris Smotrovs}, title = {Separations in Query Complexity Based on Pointer Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {911-910}, doi = {}, year = {2016}, } Article: stoc16main-main123-p (type: Full Paper (14 pages)) doi:
	Saptharishi, Ramprasad	STOC '16: "Efficiently Decoding Reed-Muller ..." Efficiently Decoding Reed-Muller Codes from Random Errors Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk (Tel Aviv University, Israel) @InProceedings{STOC16p253, author = {Ramprasad Saptharishi and Amir Shpilka and Ben Lee Volk}, title = {Efficiently Decoding Reed-Muller Codes from Random Errors}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {253-252}, doi = {}, year = {2016}, } Article: stoc16main-main128-p (type: Full Paper (14 pages)) doi:
	Saraf, Shubhangi	STOC '16: "High-Rate Locally-Correctable ..." High-Rate Locally-Correctable and Locally-Testable Codes with Sub-polynomial Query Complexity Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf (Rutgers University, USA; Weizmann Institute of Science, Israel; Institute for Advanced Study at Princeton, USA) @InProceedings{STOC16p225, author = {Swastik Kopparty and Or Meir and Noga Ron-Zewi and Shubhangi Saraf}, title = {High-Rate Locally-Correctable and Locally-Testable Codes with Sub-polynomial Query Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {225-224}, doi = {}, year = {2016}, } Article: stoc16main-main122-p (type: Full Paper (14 pages)) doi:
	Şaşoğlu, Eren	STOC '16: "Reed-Muller Codes Achieve ..." Reed-Muller Codes Achieve Capacity on Erasure Channels Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Şaşoğlu, and Rüdiger Urbanke (Qualcomm Research, USA; Texas A&M University, USA; EPFL, Switzerland; Duke University, USA; Intel, USA) @InProceedings{STOC16p757, author = {Shrinivas Kudekar and Santhosh Kumar and Marco Mondelli and Henry D. Pfister and Eren Şaşoğlu and Rüdiger Urbanke}, title = {Reed-Muller Codes Achieve Capacity on Erasure Channels}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {757-756}, doi = {}, year = {2016}, } Article: stoc16main-main347-p (type: Full Paper (14 pages)) doi:
	Saurabh, Saket	STOC '16: "Exact Algorithms via Monotone ..." Exact Algorithms via Monotone Local Search Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh (University of Bergen, Norway; UNSW, Australia; Data61, Australia; Institute of Mathematical Sciences at Chennai, India) @InProceedings{STOC16p869, author = {Fedor V. Fomin and Serge Gaspers and Daniel Lokshtanov and Saket Saurabh}, title = {Exact Algorithms via Monotone Local Search}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {869-868}, doi = {}, year = {2016}, } Article: stoc16main-main216-p (type: Full Paper (14 pages)) doi:
	Sawin, William F.	STOC '16: "Ramanujan Coverings of Graphs ..." Ramanujan Coverings of Graphs Chris Hall, Doron Puder, and William F. Sawin (University of Wyoming, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA) @InProceedings{STOC16p617, author = {Chris Hall and Doron Puder and William F. Sawin}, title = {Ramanujan Coverings of Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {617-616}, doi = {}, year = {2016}, } Article: stoc16main-main313-p (type: Full Paper (14 pages)) doi:
	Schneider, Johannes	STOC '16: "Distributed (Δ+1)-Coloring ..." Distributed (Δ+1)-Coloring in Sublogarithmic Rounds David G. Harris, Johannes Schneider, and Hsin-Hao Su (University of Maryland, USA; ABB Corporate Research, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC16p533, author = {David G. Harris and Johannes Schneider and Hsin-Hao Su}, title = {Distributed (Δ+1)-Coloring in Sublogarithmic Rounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {533-532}, doi = {}, year = {2016}, } Article: stoc16main-main152-p (type: Full Paper (14 pages)) doi:
	Schramm, Tselil	STOC '16: "Fast Spectral Algorithms from ..." Fast Spectral Algorithms from Sum-of-Squares Proofs: Tensor Decomposition and Planted Sparse Vectors Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer (Cornell University, USA; University of California at Berkeley, USA) @InProceedings{STOC16p197, author = {Samuel B. Hopkins and Tselil Schramm and Jonathan Shi and David Steurer}, title = {Fast Spectral Algorithms from Sum-of-Squares Proofs: Tensor Decomposition and Planted Sparse Vectors}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {197-196}, doi = {}, year = {2016}, } Article: stoc16main-main137-p (type: Full Paper (14 pages)) doi:
	Segev, Gil	STOC '16: "Searchable Symmetric Encryption: ..." Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations Gilad Asharov, Moni Naor, Gil Segev, and Ido Shahaf (IBM Research, USA; Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel) @InProceedings{STOC16p1247, author = {Gilad Asharov and Moni Naor and Gil Segev and Ido Shahaf}, title = {Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1247-1246}, doi = {}, year = {2016}, } Article: stoc16main-main256-p (type: Full Paper (14 pages)) doi:
	Sen, Subhabrata	STOC '16: "Semidefinite Programs on Sparse ..." Semidefinite Programs on Sparse Random Graphs and Their Application to Community Detection Andrea Montanari and Subhabrata Sen (Stanford University, USA) @InProceedings{STOC16p925, author = {Andrea Montanari and Subhabrata Sen}, title = {Semidefinite Programs on Sparse Random Graphs and Their Application to Community Detection}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {925-924}, doi = {}, year = {2016}, } Article: stoc16main-main209-p (type: Full Paper (14 pages)) doi:
	Servedio, Rocco A.	STOC '16: "Near-Optimal Small-Depth Lower ..." Near-Optimal Small-Depth Lower Bounds for Small Distance Connectivity Xi Chen, Igor C. Oliveira, Rocco A. Servedio, and Li-Yang Tan (Columbia University, USA; Charles University in Prague, Czechia; Toyota Technological Institute at Chicago, USA) @InProceedings{STOC16p701, author = {Xi Chen and Igor C. Oliveira and Rocco A. Servedio and Li-Yang Tan}, title = {Near-Optimal Small-Depth Lower Bounds for Small Distance Connectivity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {701-700}, doi = {}, year = {2016}, } Article: stoc16main-main158-p (type: Full Paper (14 pages)) doi: STOC '16: "Poly-logarithmic Frege Depth ..." Poly-logarithmic Frege Depth Lower Bounds via an Expander Switching Lemma Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan (University of Toronto, Canada; National Institute of Informatics, Japan; Columbia University, USA; Toyota Technological Institute at Chicago, USA) @InProceedings{STOC16p743, author = {Toniann Pitassi and Benjamin Rossman and Rocco A. Servedio and Li-Yang Tan}, title = {Poly-logarithmic Frege Depth Lower Bounds via an Expander Switching Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {743-742}, doi = {}, year = {2016}, } Article: stoc16main-main380-p (type: Full Paper (14 pages)) doi:
	Shahaf, Ido	STOC '16: "Searchable Symmetric Encryption: ..." Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations Gilad Asharov, Moni Naor, Gil Segev, and Ido Shahaf (IBM Research, USA; Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel) @InProceedings{STOC16p1247, author = {Gilad Asharov and Moni Naor and Gil Segev and Ido Shahaf}, title = {Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1247-1246}, doi = {}, year = {2016}, } Article: stoc16main-main256-p (type: Full Paper (14 pages)) doi:
	Sharir, Micha	STOC '16: "Almost Tight Bounds for Eliminating ..." Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions Boris Aronov and Micha Sharir (New York University, USA; Tel Aviv University, Israel) @InProceedings{STOC16p1, author = {Boris Aronov and Micha Sharir}, title = {Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1-0}, doi = {}, year = {2016}, } Article: stoc16main-main171-p (type: Full Paper (14 pages)) doi:
	Shi, Jonathan	STOC '16: "Fast Spectral Algorithms from ..." Fast Spectral Algorithms from Sum-of-Squares Proofs: Tensor Decomposition and Planted Sparse Vectors Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer (Cornell University, USA; University of California at Berkeley, USA) @InProceedings{STOC16p197, author = {Samuel B. Hopkins and Tselil Schramm and Jonathan Shi and David Steurer}, title = {Fast Spectral Algorithms from Sum-of-Squares Proofs: Tensor Decomposition and Planted Sparse Vectors}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {197-196}, doi = {}, year = {2016}, } Article: stoc16main-main137-p (type: Full Paper (14 pages)) doi:
	Shpilka, Amir	STOC '16: "Efficiently Decoding Reed-Muller ..." Efficiently Decoding Reed-Muller Codes from Random Errors Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk (Tel Aviv University, Israel) @InProceedings{STOC16p253, author = {Ramprasad Saptharishi and Amir Shpilka and Ben Lee Volk}, title = {Efficiently Decoding Reed-Muller Codes from Random Errors}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {253-252}, doi = {}, year = {2016}, } Article: stoc16main-main128-p (type: Full Paper (14 pages)) doi:
	Sidford, Aaron	STOC '16: "Geometric Median in Nearly ..." Geometric Median in Nearly Linear Time Michael B. Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford (Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; Microsoft Research, USA) @InProceedings{STOC16p15, author = {Michael B. Cohen and Yin Tat Lee and Gary Miller and Jakub Pachocki and Aaron Sidford}, title = {Geometric Median in Nearly Linear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {15-14}, doi = {}, year = {2016}, } Article: stoc16main-main436-p (type: Full Paper (14 pages)) doi: STOC '16: "Routing under Balance ..." Routing under Balance Alina Ene, Gary Miller, Jakub Pachocki, and Aaron Sidford (University of Warwick, UK; Carnegie Mellon University, USA; Microsoft Research, USA) @InProceedings{STOC16p687, author = {Alina Ene and Gary Miller and Jakub Pachocki and Aaron Sidford}, title = {Routing under Balance}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {687-686}, doi = {}, year = {2016}, } Article: stoc16main-main454-p (type: Full Paper (14 pages)) doi:
	Singh, Mohit	STOC '16: "Maximizing Determinants under ..." Maximizing Determinants under Partition Constraints Aleksandar Nikolov and Mohit Singh (University of Toronto, Canada; Microsoft Research, USA) @InProceedings{STOC16p211, author = {Aleksandar Nikolov and Mohit Singh}, title = {Maximizing Determinants under Partition Constraints}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {211-210}, doi = {}, year = {2016}, } Article: stoc16main-main440-p (type: Full Paper (14 pages)) doi:
	Singhal, Vikrant	STOC '16: "Deterministic and Probabilistic ..." Deterministic and Probabilistic Binary Search in Graphs Ehsan Emamjomeh-Zadeh, David Kempe, and Vikrant Singhal (University of Southern California, USA) @InProceedings{STOC16p603, author = {Ehsan Emamjomeh-Zadeh and David Kempe and Vikrant Singhal}, title = {Deterministic and Probabilistic Binary Search in Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {603-602}, doi = {}, year = {2016}, } Article: stoc16main-main462-p (type: Full Paper (14 pages)) doi:
	Smith, Adam	STOC '16: "Algorithmic Stability for ..." Algorithmic Stability for Adaptive Data Analysis Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman (University of California at San Diego, USA; Ben-Gurion University of the Negev, Israel; Harvard University, USA; Pennsylvania State University, USA; Northeastern University, USA) @InProceedings{STOC16p1191, author = {Raef Bassily and Kobbi Nissim and Adam Smith and Thomas Steinke and Uri Stemmer and Jonathan Ullman}, title = {Algorithmic Stability for Adaptive Data Analysis}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1191-1190}, doi = {}, year = {2016}, } Article: stoc16main-main278-p (type: Full Paper (14 pages)) doi:
	Smotrovs, Juris	STOC '16: "Separations in Query Complexity ..." Separations in Query Complexity Based on Pointer Functions Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs (University of Latvia, Latvia; CWI, Netherlands; Nanyang Technological University, Singapore; National University of Singapore, Singapore; CNRS, France) @InProceedings{STOC16p911, author = {Andris Ambainis and Kaspars Balodis and Aleksandrs Belovs and Troy Lee and Miklos Santha and Juris Smotrovs}, title = {Separations in Query Complexity Based on Pointer Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {911-910}, doi = {}, year = {2016}, } Article: stoc16main-main123-p (type: Full Paper (14 pages)) doi:
	Sohler, Christian	STOC '16: "Relating Two Property Testing ..." Relating Two Property Testing Models for Bounded Degree Directed Graphs Artur Czumaj, Pan Peng, and Christian Sohler (University of Warwick, UK; TU Dortmund, Germany; Institute of Software at Chinese Academy of Sciences, China) @InProceedings{STOC16p1177, author = {Artur Czumaj and Pan Peng and Christian Sohler}, title = {Relating Two Property Testing Models for Bounded Degree Directed Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1177-1176}, doi = {}, year = {2016}, } Article: stoc16main-main314-p (type: Full Paper (14 pages)) doi:
	Song, Zhao	STOC '16: "Weighted Low Rank Approximations ..." Weighted Low Rank Approximations with Provable Guarantees Ilya Razenshteyn, Zhao Song, and David P. Woodruff (Massachusetts Institute of Technology, USA; University of Texas at Austin, USA; IBM Research, USA) @InProceedings{STOC16p281, author = {Ilya Razenshteyn and Zhao Song and David P. Woodruff}, title = {Weighted Low Rank Approximations with Provable Guarantees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {281-280}, doi = {}, year = {2016}, } Article: stoc16main-main387-p (type: Full Paper (14 pages)) doi:
	Spielman, Daniel A.	STOC '16: "Sparsified Cholesky and Multigrid ..." Sparsified Cholesky and Multigrid Solvers for Connection Laplacians Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman (Yale University, USA; Massachusetts Institute of Technology, USA; Georgia Tech, USA) @InProceedings{STOC16p953, author = {Rasmus Kyng and Yin Tat Lee and Richard Peng and Sushant Sachdeva and Daniel A. Spielman}, title = {Sparsified Cholesky and Multigrid Solvers for Connection Laplacians}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {953-952}, doi = {}, year = {2016}, } Article: stoc16main-main390-p (type: Full Paper (14 pages)) doi:
	Srinivasan, Aravind	STOC '16: "Lift-and-Round to Improve ..." Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines Nikhil Bansal, Aravind Srinivasan, and Ola Svensson (Eindhoven University of Technology, Netherlands; University of Maryland, USA; EPFL, Switzerland) @InProceedings{STOC16p169, author = {Nikhil Bansal and Aravind Srinivasan and Ola Svensson}, title = {Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {169-168}, doi = {}, year = {2016}, } Article: stoc16main-main307-p (type: Full Paper (14 pages)) doi:
	Steinke, Thomas	STOC '16: "Algorithmic Stability for ..." Algorithmic Stability for Adaptive Data Analysis Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman (University of California at San Diego, USA; Ben-Gurion University of the Negev, Israel; Harvard University, USA; Pennsylvania State University, USA; Northeastern University, USA) @InProceedings{STOC16p1191, author = {Raef Bassily and Kobbi Nissim and Adam Smith and Thomas Steinke and Uri Stemmer and Jonathan Ullman}, title = {Algorithmic Stability for Adaptive Data Analysis}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1191-1190}, doi = {}, year = {2016}, } Article: stoc16main-main278-p (type: Full Paper (14 pages)) doi:
	Stemmer, Uri	STOC '16: "Algorithmic Stability for ..." Algorithmic Stability for Adaptive Data Analysis Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman (University of California at San Diego, USA; Ben-Gurion University of the Negev, Israel; Harvard University, USA; Pennsylvania State University, USA; Northeastern University, USA) @InProceedings{STOC16p1191, author = {Raef Bassily and Kobbi Nissim and Adam Smith and Thomas Steinke and Uri Stemmer and Jonathan Ullman}, title = {Algorithmic Stability for Adaptive Data Analysis}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1191-1190}, doi = {}, year = {2016}, } Article: stoc16main-main278-p (type: Full Paper (14 pages)) doi:
	Steurer, David	STOC '16: "Fast Spectral Algorithms from ..." Fast Spectral Algorithms from Sum-of-Squares Proofs: Tensor Decomposition and Planted Sparse Vectors Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer (Cornell University, USA; University of California at Berkeley, USA) @InProceedings{STOC16p197, author = {Samuel B. Hopkins and Tselil Schramm and Jonathan Shi and David Steurer}, title = {Fast Spectral Algorithms from Sum-of-Squares Proofs: Tensor Decomposition and Planted Sparse Vectors}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {197-196}, doi = {}, year = {2016}, } Article: stoc16main-main137-p (type: Full Paper (14 pages)) doi:
	Stewart, Alistair	STOC '16: "The Fourier Transform of Poisson ..." The Fourier Transform of Poisson Multinomial Distributions and Its Algorithmic Applications Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart (University of Southern California, USA; University of California at San Diego, USA) @InProceedings{STOC16p1205, author = {Ilias Diakonikolas and Daniel M. Kane and Alistair Stewart}, title = {The Fourier Transform of Poisson Multinomial Distributions and Its Algorithmic Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1205-1204}, doi = {}, year = {2016}, } Article: stoc16main-main218-p (type: Full Paper (14 pages)) doi:
	Su, Hsin-Hao	STOC '16: "Distributed (Δ+1)-Coloring ..." Distributed (Δ+1)-Coloring in Sublogarithmic Rounds David G. Harris, Johannes Schneider, and Hsin-Hao Su (University of Maryland, USA; ABB Corporate Research, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC16p533, author = {David G. Harris and Johannes Schneider and Hsin-Hao Su}, title = {Distributed (Δ+1)-Coloring in Sublogarithmic Rounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {533-532}, doi = {}, year = {2016}, } Article: stoc16main-main152-p (type: Full Paper (14 pages)) doi:
	Suomela, Jukka	STOC '16: "A Lower Bound for the Distributed ..." A Lower Bound for the Distributed Lovász Local Lemma Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto (ETH Zurich, Switzerland; Tel Aviv University, Israel; Aalto University, Finland; Bitsplitters, Switzerland) @InProceedings{STOC16p547, author = {Sebastian Brandt and Orr Fischer and Juho Hirvonen and Barbara Keller and Tuomo Lempiäinen and Joel Rybicki and Jukka Suomela and Jara Uitto}, title = {A Lower Bound for the Distributed Lovász Local Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {}, year = {2016}, } Article: stoc16main-main300-p (type: Full Paper (14 pages)) doi:
	Svensson, Ola	STOC '16: "Lift-and-Round to Improve ..." Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines Nikhil Bansal, Aravind Srinivasan, and Ola Svensson (Eindhoven University of Technology, Netherlands; University of Maryland, USA; EPFL, Switzerland) @InProceedings{STOC16p169, author = {Nikhil Bansal and Aravind Srinivasan and Ola Svensson}, title = {Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {169-168}, doi = {}, year = {2016}, } Article: stoc16main-main307-p (type: Full Paper (14 pages)) doi:
	Syrgkanis, Vasilis	STOC '16: "The Price of Anarchy in Large ..." The Price of Anarchy in Large Games Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden, and Vasilis Syrgkanis (Tel Aviv University, Israel; Microsoft Research, USA; Stanford University, USA) @InProceedings{STOC16p1093, author = {Michal Feldman and Nicole Immorlica and Brendan Lucier and Tim Roughgarden and Vasilis Syrgkanis}, title = {The Price of Anarchy in Large Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1093-1092}, doi = {}, year = {2016}, } Article: stoc16main-main340-p (type: Full Paper (14 pages)) doi:
	Tal, Avishay	STOC '16: "Matrix Rigidity of Random ..." Matrix Rigidity of Random Toeplitz Matrices Oded Goldreich and Avishay Tal (Weizmann Institute of Science, Israel; Institute for Advanced Study at Princeton, USA) @InProceedings{STOC16p99, author = {Oded Goldreich and Avishay Tal}, title = {Matrix Rigidity of Random Toeplitz Matrices}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {99-98}, doi = {}, year = {2016}, } Article: stoc16main-main359-p (type: Full Paper (14 pages)) doi:
	Tan, Li-Yang	STOC '16: "Near-Optimal Small-Depth Lower ..." Near-Optimal Small-Depth Lower Bounds for Small Distance Connectivity Xi Chen, Igor C. Oliveira, Rocco A. Servedio, and Li-Yang Tan (Columbia University, USA; Charles University in Prague, Czechia; Toyota Technological Institute at Chicago, USA) @InProceedings{STOC16p701, author = {Xi Chen and Igor C. Oliveira and Rocco A. Servedio and Li-Yang Tan}, title = {Near-Optimal Small-Depth Lower Bounds for Small Distance Connectivity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {701-700}, doi = {}, year = {2016}, } Article: stoc16main-main158-p (type: Full Paper (14 pages)) doi: STOC '16: "Poly-logarithmic Frege Depth ..." Poly-logarithmic Frege Depth Lower Bounds via an Expander Switching Lemma Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan (University of Toronto, Canada; National Institute of Informatics, Japan; Columbia University, USA; Toyota Technological Institute at Chicago, USA) @InProceedings{STOC16p743, author = {Toniann Pitassi and Benjamin Rossman and Rocco A. Servedio and Li-Yang Tan}, title = {Poly-logarithmic Frege Depth Lower Bounds via an Expander Switching Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {743-742}, doi = {}, year = {2016}, } Article: stoc16main-main380-p (type: Full Paper (14 pages)) doi:
	Tavenas, Sébastien	STOC '16: "On the Size of Homogeneous ..." On the Size of Homogeneous and of Depth Four Formulas with Low Individual Degree Neeraj Kayal, Chandan Saha, and Sébastien Tavenas (Microsoft Research, India; Indian Institute of Science, India) @InProceedings{STOC16p715, author = {Neeraj Kayal and Chandan Saha and Sébastien Tavenas}, title = {On the Size of Homogeneous and of Depth Four Formulas with Low Individual Degree}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {715-714}, doi = {}, year = {2016}, } Article: stoc16main-main214-p (type: Full Paper (14 pages)) doi:
	Thierauf, Thomas	STOC '16: "Bipartite Perfect Matching ..." Bipartite Perfect Matching Is in Quasi-NC Stephen Fenner, Rohit Gurjar, and Thomas Thierauf (University of South Carolina, USA; Aalen University, Germany) @InProceedings{STOC16p855, author = {Stephen Fenner and Rohit Gurjar and Thomas Thierauf}, title = {Bipartite Perfect Matching Is in Quasi-NC}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {855-854}, doi = {}, year = {2016}, } Article: stoc16main-main260-p (type: Full Paper (14 pages)) doi:
	Tzamos, Christos	STOC '16: "A Size-Free CLT for Poisson ..." A Size-Free CLT for Poisson Multinomials and Its Applications Constantinos Daskalakis, Anindya De, Gautam Kamath, and Christos Tzamos (Massachusetts Institute of Technology, USA; Northwestern University, USA) @InProceedings{STOC16p1219, author = {Constantinos Daskalakis and Anindya De and Gautam Kamath and Christos Tzamos}, title = {A Size-Free CLT for Poisson Multinomials and Its Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1219-1218}, doi = {}, year = {2016}, } Article: stoc16main-main104-p (type: Full Paper (14 pages)) doi:
	Uitto, Jara	STOC '16: "A Lower Bound for the Distributed ..." A Lower Bound for the Distributed Lovász Local Lemma Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto (ETH Zurich, Switzerland; Tel Aviv University, Israel; Aalto University, Finland; Bitsplitters, Switzerland) @InProceedings{STOC16p547, author = {Sebastian Brandt and Orr Fischer and Juho Hirvonen and Barbara Keller and Tuomo Lempiäinen and Joel Rybicki and Jukka Suomela and Jara Uitto}, title = {A Lower Bound for the Distributed Lovász Local Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {}, year = {2016}, } Article: stoc16main-main300-p (type: Full Paper (14 pages)) doi:
	Ullman, Jonathan	STOC '16: "Watch and Learn: Optimizing ..." Watch and Learn: Optimizing from Revealed Preferences Feedback Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu (University of Pennsylvania, USA; Northeastern University, USA) @InProceedings{STOC16p1079, author = {Aaron Roth and Jonathan Ullman and Zhiwei Steven Wu}, title = {Watch and Learn: Optimizing from Revealed Preferences Feedback}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1079-1078}, doi = {}, year = {2016}, } Article: stoc16main-main336-p (type: Full Paper (14 pages)) doi: STOC '16: "Algorithmic Stability for ..." Algorithmic Stability for Adaptive Data Analysis Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman (University of California at San Diego, USA; Ben-Gurion University of the Negev, Israel; Harvard University, USA; Pennsylvania State University, USA; Northeastern University, USA) @InProceedings{STOC16p1191, author = {Raef Bassily and Kobbi Nissim and Adam Smith and Thomas Steinke and Uri Stemmer and Jonathan Ullman}, title = {Algorithmic Stability for Adaptive Data Analysis}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1191-1190}, doi = {}, year = {2016}, } Article: stoc16main-main278-p (type: Full Paper (14 pages)) doi:
	Urbanke, Rüdiger	STOC '16: "Reed-Muller Codes Achieve ..." Reed-Muller Codes Achieve Capacity on Erasure Channels Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Şaşoğlu, and Rüdiger Urbanke (Qualcomm Research, USA; Texas A&M University, USA; EPFL, Switzerland; Duke University, USA; Intel, USA) @InProceedings{STOC16p757, author = {Shrinivas Kudekar and Santhosh Kumar and Marco Mondelli and Henry D. Pfister and Eren Şaşoğlu and Rüdiger Urbanke}, title = {Reed-Muller Codes Achieve Capacity on Erasure Channels}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {757-756}, doi = {}, year = {2016}, } Article: stoc16main-main347-p (type: Full Paper (14 pages)) doi:
	Vaikuntanathan, Vinod	STOC '16: "Watermarking Cryptographic ..." Watermarking Cryptographic Capabilities Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, and Daniel Wichs (Massachusetts Institute of Technology, USA; NTT, Japan; Northeastern University, USA) @InProceedings{STOC16p1261, author = {Aloni Cohen and Justin Holmgren and Ryo Nishimaki and Vinod Vaikuntanathan and Daniel Wichs}, title = {Watermarking Cryptographic Capabilities}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1261-1260}, doi = {}, year = {2016}, } Article: stoc16main-main448-p (type: Full Paper (14 pages)) doi:
	Valiant, Gregory	STOC '16: "Instance Optimal Learning ..." Instance Optimal Learning of Discrete Distributions Gregory Valiant and Paul Valiant (Stanford University, USA; Brown University, USA) @InProceedings{STOC16p155, author = {Gregory Valiant and Paul Valiant}, title = {Instance Optimal Learning of Discrete Distributions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {155-154}, doi = {}, year = {2016}, } Article: stoc16main-main391-p (type: Full Paper (14 pages)) doi:
	Valiant, Paul	STOC '16: "Instance Optimal Learning ..." Instance Optimal Learning of Discrete Distributions Gregory Valiant and Paul Valiant (Stanford University, USA; Brown University, USA) @InProceedings{STOC16p155, author = {Gregory Valiant and Paul Valiant}, title = {Instance Optimal Learning of Discrete Distributions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {155-154}, doi = {}, year = {2016}, } Article: stoc16main-main391-p (type: Full Paper (14 pages)) doi:
	Vohra, Rakesh	STOC '16: "Do Prices Coordinate Markets? ..." Do Prices Coordinate Markets? Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth, and Rakesh Vohra (University of Pennsylvania, USA) @InProceedings{STOC16p505, author = {Justin Hsu and Jamie Morgenstern and Ryan Rogers and Aaron Roth and Rakesh Vohra}, title = {Do Prices Coordinate Markets?}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {505-504}, doi = {}, year = {2016}, } Article: stoc16main-main246-p (type: Full Paper (14 pages)) doi:
	Volk, Ben Lee	STOC '16: "Efficiently Decoding Reed-Muller ..." Efficiently Decoding Reed-Muller Codes from Random Errors Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk (Tel Aviv University, Israel) @InProceedings{STOC16p253, author = {Ramprasad Saptharishi and Amir Shpilka and Ben Lee Volk}, title = {Efficiently Decoding Reed-Muller Codes from Random Errors}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {253-252}, doi = {}, year = {2016}, } Article: stoc16main-main128-p (type: Full Paper (14 pages)) doi:
	Wattenhofer, Roger	STOC '16: "Online Matching: Haste Makes ..." Online Matching: Haste Makes Waste! Yuval Emek, Shay Kutten, and Roger Wattenhofer (Technion, Israel; ETH Zurich, Switzerland) @InProceedings{STOC16p379, author = {Yuval Emek and Shay Kutten and Roger Wattenhofer}, title = {Online Matching: Haste Makes Waste!}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {379-378}, doi = {}, year = {2016}, } Article: stoc16main-main239-p (type: Full Paper (14 pages)) doi:
	Wein, Alexander S.	STOC '16: "How Robust Are Reconstruction ..." How Robust Are Reconstruction Thresholds for Community Detection? Ankur Moitra, William Perry, and Alexander S. Wein (Massachusetts Institute of Technology, USA) @InProceedings{STOC16p939, author = {Ankur Moitra and William Perry and Alexander S. Wein}, title = {How Robust Are Reconstruction Thresholds for Community Detection?}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {939-938}, doi = {}, year = {2016}, } Article: stoc16main-main311-p (type: Full Paper (14 pages)) doi:
	Weinberg, S. Matthew	STOC '16: "A Duality Based Unified Approach ..." A Duality Based Unified Approach to Bayesian Mechanism Design Yang Cai, Nikhil R. Devanur, and S. Matthew Weinberg (McGill University, Canada; Microsoft Research, USA; Princeton University, USA) @InProceedings{STOC16p1051, author = {Yang Cai and Nikhil R. Devanur and S. Matthew Weinberg}, title = {A Duality Based Unified Approach to Bayesian Mechanism Design}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1051-1050}, doi = {}, year = {2016}, } Article: stoc16main-main430-p (type: Full Paper (14 pages)) doi: STOC '16: "Parallel Algorithms for Select ..." Parallel Algorithms for Select and Partition with Noisy Comparisons Mark Braverman, Jieming Mao, and S. Matthew Weinberg (Princeton University, USA) @InProceedings{STOC16p967, author = {Mark Braverman and Jieming Mao and S. Matthew Weinberg}, title = {Parallel Algorithms for Select and Partition with Noisy Comparisons}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {967-966}, doi = {}, year = {2016}, } Article: stoc16main-main419-p (type: Full Paper (14 pages)) doi:
	Wichs, Daniel	STOC '16: "Watermarking Cryptographic ..." Watermarking Cryptographic Capabilities Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, and Daniel Wichs (Massachusetts Institute of Technology, USA; NTT, Japan; Northeastern University, USA) @InProceedings{STOC16p1261, author = {Aloni Cohen and Justin Holmgren and Ryo Nishimaki and Vinod Vaikuntanathan and Daniel Wichs}, title = {Watermarking Cryptographic Capabilities}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1261-1260}, doi = {}, year = {2016}, } Article: stoc16main-main448-p (type: Full Paper (14 pages)) doi:
	Williams, Ryan	STOC '16: "Simulating Branching Programs ..." Simulating Branching Programs with Edit Distance and Friends: Or: A Polylog Shaved Is a Lower Bound Made Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams (Stanford University, USA; Aarhus University, Denmark) @InProceedings{STOC16p435, author = {Amir Abboud and Thomas Dueholm Hansen and Virginia Vassilevska Williams and Ryan Williams}, title = {Simulating Branching Programs with Edit Distance and Friends: Or: A Polylog Shaved Is a Lower Bound Made}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {435-434}, doi = {}, year = {2016}, } Article: stoc16main-main451-p (type: Full Paper (14 pages)) doi: STOC '16: "Super-Linear Gate and Super-Quadratic ..." Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits Daniel M. Kane and Ryan Williams (University of California at San Diego, USA; Stanford University, USA) @InProceedings{STOC16p729, author = {Daniel M. Kane and Ryan Williams}, title = {Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {729-728}, doi = {}, year = {2016}, } Article: stoc16main-main370-p (type: Full Paper (14 pages)) doi:
	Williams, Virginia Vassilevska	STOC '16: "Simulating Branching Programs ..." Simulating Branching Programs with Edit Distance and Friends: Or: A Polylog Shaved Is a Lower Bound Made Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams (Stanford University, USA; Aarhus University, Denmark) @InProceedings{STOC16p435, author = {Amir Abboud and Thomas Dueholm Hansen and Virginia Vassilevska Williams and Ryan Williams}, title = {Simulating Branching Programs with Edit Distance and Friends: Or: A Polylog Shaved Is a Lower Bound Made}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {435-434}, doi = {}, year = {2016}, } Article: stoc16main-main451-p (type: Full Paper (14 pages)) doi:
	Woodruff, David P.	STOC '16: "Communication Lower Bounds ..." Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, and David P. Woodruff (Princeton University, USA; Toyota Technological Institute at Chicago, USA; IBM Research, USA) @InProceedings{STOC16p1149, author = {Mark Braverman and Ankit Garg and Tengyu Ma and Huy L. Nguyen and David P. Woodruff}, title = {Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1149-1148}, doi = {}, year = {2016}, } Article: stoc16main-main342-p (type: Full Paper (14 pages)) doi: STOC '16: "Optimal Principal Component ..." Optimal Principal Component Analysis in Distributed and Streaming Models Christos Boutsidis, David P. Woodruff, and Peilin Zhong (Goldman Sachs, USA; IBM Research, USA; Tsinghua University, China) @InProceedings{STOC16p267, author = {Christos Boutsidis and David P. Woodruff and Peilin Zhong}, title = {Optimal Principal Component Analysis in Distributed and Streaming Models}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {267-266}, doi = {}, year = {2016}, } Article: stoc16main-main431-p (type: Full Paper (14 pages)) doi: STOC '16: "Weighted Low Rank Approximations ..." Weighted Low Rank Approximations with Provable Guarantees Ilya Razenshteyn, Zhao Song, and David P. Woodruff (Massachusetts Institute of Technology, USA; University of Texas at Austin, USA; IBM Research, USA) @InProceedings{STOC16p281, author = {Ilya Razenshteyn and Zhao Song and David P. Woodruff}, title = {Weighted Low Rank Approximations with Provable Guarantees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {281-280}, doi = {}, year = {2016}, } Article: stoc16main-main387-p (type: Full Paper (14 pages)) doi: STOC '16: "On Approximating Functions ..." On Approximating Functions of the Singular Values in a Stream Yi Li and David P. Woodruff (Facebook, USA; IBM Research, USA) @InProceedings{STOC16p827, author = {Yi Li and David P. Woodruff}, title = {On Approximating Functions of the Singular Values in a Stream}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {827-826}, doi = {}, year = {2016}, } Article: stoc16main-main341-p (type: Full Paper (14 pages)) doi: STOC '16: "Beating CountSketch for Heavy ..." Beating CountSketch for Heavy Hitters in Insertion Streams Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, and David P. Woodruff (Johns Hopkins University, USA; ETH Zurich, Switzerland; IBM Research, USA) @InProceedings{STOC16p841, author = {Vladimir Braverman and Stephen R. Chestnut and Nikita Ivkin and David P. Woodruff}, title = {Beating CountSketch for Heavy Hitters in Insertion Streams}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {841-840}, doi = {}, year = {2016}, } Article: stoc16main-main240-p (type: Full Paper (14 pages)) doi:
	Wootters, Mary	STOC '16: "Repairing Reed-Solomon Codes ..." Repairing Reed-Solomon Codes Venkatesan Guruswami and Mary Wootters (Carnegie Mellon University, USA) @InProceedings{STOC16p239, author = {Venkatesan Guruswami and Mary Wootters}, title = {Repairing Reed-Solomon Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {239-238}, doi = {}, year = {2016}, } Article: stoc16main-main125-p (type: Full Paper (14 pages)) doi:
	Wright, John	STOC '16: "Efficient Quantum Tomography ..." Efficient Quantum Tomography Ryan O'Donnell and John Wright (Carnegie Mellon University, USA) @InProceedings{STOC16p1023, author = {Ryan O'Donnell and John Wright}, title = {Efficient Quantum Tomography}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1023-1022}, doi = {}, year = {2016}, } Article: stoc16main-main191-p (type: Full Paper (14 pages)) doi:
	Wu, Xiaodi	STOC '16: "Sample-Optimal Tomography ..." Sample-Optimal Tomography of Quantum States Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu (Massachusetts Institute of Technology, USA; University of Technology Sydney, Australia; University of Waterloo, Canada; Institute of Software at Chinese Academy of Sciences, China; University of Oregon, USA; University of Guelph, Canada) @InProceedings{STOC16p1037, author = {Jeongwan Haah and Aram W. Harrow and Zhengfeng Ji and Xiaodi Wu and Nengkun Yu}, title = {Sample-Optimal Tomography of Quantum States}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1037-1036}, doi = {}, year = {2016}, } Article: stoc16main-main351-p (type: Full Paper (14 pages)) doi:
	Wu, Zhiwei Steven	STOC '16: "Watch and Learn: Optimizing ..." Watch and Learn: Optimizing from Revealed Preferences Feedback Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu (University of Pennsylvania, USA; Northeastern University, USA) @InProceedings{STOC16p1079, author = {Aaron Roth and Jonathan Ullman and Zhiwei Steven Wu}, title = {Watch and Learn: Optimizing from Revealed Preferences Feedback}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1079-1078}, doi = {}, year = {2016}, } Article: stoc16main-main336-p (type: Full Paper (14 pages)) doi:
	Xia, Mingji	STOC '16: "Base Collapse of Holographic ..." Base Collapse of Holographic Algorithms Mingji Xia (Institute of Software at Chinese Academy of Sciences, China) @InProceedings{STOC16p897, author = {Mingji Xia}, title = {Base Collapse of Holographic Algorithms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {897-896}, doi = {}, year = {2016}, } Article: stoc16main-main249-p (type: Full Paper (14 pages)) doi:
	Xu, Haifeng	STOC '16: "Algorithmic Bayesian Persuasion ..." Algorithmic Bayesian Persuasion Shaddin Dughmi and Haifeng Xu (University of Southern California, USA) @InProceedings{STOC16p477, author = {Shaddin Dughmi and Haifeng Xu}, title = {Algorithmic Bayesian Persuasion}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {477-476}, doi = {}, year = {2016}, } Article: stoc16main-main346-p (type: Full Paper (14 pages)) doi:
	Young, Maxwell	STOC '16: "Contention Resolution with ..." Contention Resolution with Log-Logstar Channel Accesses Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young (Stony Brook University, USA; University of Michigan, USA; Mississippi State University, USA) @InProceedings{STOC16p575, author = {Michael A. Bender and Tsvi Kopelowitz and Seth Pettie and Maxwell Young}, title = {Contention Resolution with Log-Logstar Channel Accesses}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {575-574}, doi = {}, year = {2016}, } Article: stoc16main-main456-p (type: Full Paper (14 pages)) doi:
	Yu, Huacheng	STOC '16: "Cell-Probe Lower Bounds for ..." Cell-Probe Lower Bounds for Dynamic Problems via a New Communication Model Huacheng Yu (Stanford University, USA) @InProceedings{STOC16p421, author = {Huacheng Yu}, title = {Cell-Probe Lower Bounds for Dynamic Problems via a New Communication Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {421-420}, doi = {}, year = {2016}, } Article: stoc16main-main235-p (type: Full Paper (14 pages)) doi:
	Yu, Nengkun	STOC '16: "Sample-Optimal Tomography ..." Sample-Optimal Tomography of Quantum States Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu (Massachusetts Institute of Technology, USA; University of Technology Sydney, Australia; University of Waterloo, Canada; Institute of Software at Chinese Academy of Sciences, China; University of Oregon, USA; University of Guelph, Canada) @InProceedings{STOC16p1037, author = {Jeongwan Haah and Aram W. Harrow and Zhengfeng Ji and Xiaodi Wu and Nengkun Yu}, title = {Sample-Optimal Tomography of Quantum States}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1037-1036}, doi = {}, year = {2016}, } Article: stoc16main-main351-p (type: Full Paper (14 pages)) doi:
	Zhong, Peilin	STOC '16: "Optimal Principal Component ..." Optimal Principal Component Analysis in Distributed and Streaming Models Christos Boutsidis, David P. Woodruff, and Peilin Zhong (Goldman Sachs, USA; IBM Research, USA; Tsinghua University, China) @InProceedings{STOC16p267, author = {Christos Boutsidis and David P. Woodruff and Peilin Zhong}, title = {Optimal Principal Component Analysis in Distributed and Streaming Models}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {267-266}, doi = {}, year = {2016}, } Article: stoc16main-main431-p (type: Full Paper (14 pages)) doi:
	Zhu, Leqi	STOC '16: "A Tight Space Bound for Consensus ..." A Tight Space Bound for Consensus Leqi Zhu (University of Toronto, Canada) @InProceedings{STOC16p393, author = {Leqi Zhu}, title = {A Tight Space Bound for Consensus}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {393-392}, doi = {}, year = {2016}, } Article: stoc16main-main266-p (type: Full Paper (14 pages)) doi:
	Zuckerman, David	STOC '16: "Explicit Two-Source Extractors ..." Explicit Two-Source Extractors and Resilient Functions Eshan Chattopadhyay and David Zuckerman (University of Texas at Austin, USA) @InProceedings{STOC16p771, author = {Eshan Chattopadhyay and David Zuckerman}, title = {Explicit Two-Source Extractors and Resilient Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {771-770}, doi = {}, year = {2016}, } Article: stoc16main-main134-p (type: Full Paper (14 pages)) doi:

266 authors

proc time: 0.26