Powered by
48th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2016),
June 19–21, 2016,
Cambridge, MA, USA
Frontmatter
Foreword
The papers in this volume were presented at the Forty-Eighth Annual ACM Symposium on Theory of Computing (STOC 2016), held in Cambridge, Massachusetts, June 19--June 21, 2016. The Symposium was sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT). On June 18, the day before STOC, there was a workshop and tutorial day held jointly with the 32nd International Symposium on Computational Geometry (SOCG 2016), which was organized by Alexandr Andoni, Chandra Chekuri, Suresh Venkatasubramanian and Yusu Wang. In response to a Call for Papers, 370 submissions were received by the submission deadline of November 2, 2015 (23:59pm EST). The Program Committee electronic deliberations continued until its meeting at MSR in New York, NY on January 29 -- January 31, 2016, where final decisions were made. The Program Committee meeting was attended by 24 (of the 25) Program Committee members and one member joined the discussions by phone. The Program Committee selected 92 papers for presentation. The submissions were not refereed, and many of these papers represent reports of continuing research. It is expected that most of them will appear in a more polished and complete form in scientific journals. The Program Committee would like to thank all authors who submitted papers for consideration. From among many excellent candidates, the papers ``Explicit Two-Source Extractors and Resilient Functions'' by Eshan Chattopadhyay and David Zuckerman, ``Graph Isomorphism in Quasipolynomial Time'' by Laszlo Babai and ``Reed-Muller Codes Achieve Capacity on Erasure Channels'' by Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Sasoglu and Rudiger Urbanke were selected for the STOC Best Paper Award. The papers ``The 4/3 Additive Spanner Exponent is Tight'' by Amir Abboud and Greg Bodwin, and ``A Tight Space Bound for Consensus'' by Leqi Zhu, were selected for the Danny Lewin Best Student Paper Award. The committee is very grateful to Shai Halevi for providing access to and support for his conference program committee software. The committee is also very grateful to the large number of members of the community (listed on a separate page) who assisted the committee in assessing the merits of the submissions. I am extremely grateful to Paul Beame and Michael Mitzenmacher, the SIGACT Executive Committee Chairs, for their useful guidance, advice, and help in the process. I would like to thank Daniel Wichs, the General Chair, for his help, responsiveness and hard work. I would like to thank the staff of MSR NYC, who provided many amenities during the Program Committee meeting. I am especially grateful to Ronitt Rubinfeld for her continuous support and guidance throughout the entire process. Last, but far from least, I wish to thank the Program Committee for their incredibly hard work, for their wisdom and for their devotion to our field. It was a great honor to work with them. Yishay Mansour MSR and Tel Aviv University STOC 2016 Program Chair
proc time: 0.05