Powered by
48th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2016), June 19–21, 2016,
Cambridge, MA, USA
Frontmatter
Title Page
Article: stoc16foreword-fm000-p (type: Frontmatter) doi:
Foreword
Article: stoc16foreword-fm001-p (type: Frontmatter) doi:
Session 1A
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)
Article: stoc16main-main436-p (type: Full Paper (14 pages)) doi:
Session 1B
Candidate Hard Unique Game
Subhash Khot and
Dana Moshkovitz
(New York University, USA; Massachusetts Institute of Technology, USA)
Article: stoc16main-main140-p (type: Full Paper (14 pages)) doi:
Matrix Rigidity of Random Toeplitz Matrices
Oded Goldreich and
Avishay Tal
(Weizmann Institute of Science, Israel; Institute for Advanced Study at Princeton, USA)
Article: stoc16main-main359-p (type: Full Paper (14 pages)) doi:
Session 2A
Session 2B
Session 3A
Repairing Reed-Solomon Codes
Venkatesan Guruswami and
Mary Wootters
(Carnegie Mellon University, USA)
Article: stoc16main-main125-p (type: Full Paper (14 pages)) doi:
Session 3B
Session 4A
Extractors for Sumset Sources
Eshan Chattopadhyay and
Xin Li
(University of Texas at Austin, USA; Johns Hopkins University, USA)
Article: stoc16main-main422-p (type: Full Paper (14 pages)) doi:
Session 4B
Online Matching: Haste Makes Waste!
Yuval Emek,
Shay Kutten, and
Roger Wattenhofer
(Technion, Israel; ETH Zurich, Switzerland)
Article: stoc16main-main239-p (type: Full Paper (14 pages)) doi:
Session 5
Session 6A
Session 6B
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)
Article: stoc16main-main219-p (type: Full Paper (14 pages)) doi:
Do Prices Coordinate Markets?
Justin Hsu,
Jamie Morgenstern,
Ryan Rogers,
Aaron Roth, and
Rakesh Vohra
(University of Pennsylvania, USA)
Article: stoc16main-main246-p (type: Full Paper (14 pages)) doi:
Session 7A
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)
Article: stoc16main-main152-p (type: Full Paper (14 pages)) doi:
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)
Article: stoc16main-main300-p (type: Full Paper (14 pages)) doi:
Session 7B
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)
Article: stoc16main-main313-p (type: Full Paper (14 pages)) doi:
Session 8A
Routing under Balance
Alina Ene,
Gary Miller,
Jakub Pachocki, and
Aaron Sidford
(University of Warwick, UK; Carnegie Mellon University, USA; Microsoft Research, USA)
Article: stoc16main-main454-p (type: Full Paper (14 pages)) doi:
Session 8B
Session 9
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)
Article: stoc16main-main347-p (type: Full Paper (14 pages)) doi:
Session 10A
Session 10B
Bipartite Perfect Matching Is in Quasi-NC
Stephen Fenner,
Rohit Gurjar, and
Thomas Thierauf
(University of South Carolina, USA; Aalen University, Germany)
Article: stoc16main-main260-p (type: Full Paper (14 pages)) doi:
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)
Article: stoc16main-main123-p (type: Full Paper (14 pages)) doi:
Session 11A
Session 11B
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)
Article: stoc16main-main351-p (type: Full Paper (14 pages)) doi:
Session 12A
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)
Article: stoc16main-main340-p (type: Full Paper (14 pages)) doi:
Session 12B
Session 13A
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)
Article: stoc16main-main278-p (type: Full Paper (14 pages)) doi:
Session 13B
Textbook Non-malleable Commitments
Vipul Goyal,
Omkant Pandey, and
Silas Richelson
(Microsoft Research, India; Drexel University, USA; Massachusetts Institute of Technology, USA)
Article: stoc16main-main464-p (type: Full Paper (14 pages)) doi:
proc time: 0.15