Theory of Computing
-------------------
Title : Special Issue: CCC 2017: Guest Editor's Foreword
Authors : Shachar Lovett and Ryan O'Donnell
Volume : 14
Number : 2
Pages : 1-2
URL : http://www.theoryofcomputing.org/articles/v014a002
Abstract
--------
This collection comprises the expanded and fully refereed versions of
selected papers presented at the 32nd Computational Complexity
Conference (CCC 2017) held in Riga, Latvia, July 6--9, 2017. These
papers were selected by the Program Committee from among the 34
papers that appeared in the conference proceedings. Preliminary
versions of the papers were presented at the conference and the
extended abstracts appeared in the proceedings of the conference
published by Dagstuhl Publishing, LIPIcs. The CCC Program Committee
selected 34 out of 98 submissions for presentation at the
conference; of these, the 5 described below were invited to this
Special Issue. These 5 were refereed in accordance with the usual
rigorous standards of Theory of Computing.
* The paper "A Deterministic PTAS for the Commutative Rank of
Matrix Spaces" by Markus Blaser, Gorav Jindal, and Anurag Pandey,
which shows that there is a deterministic, polynomial-time
algorithm for finding a matrix of rank at least (1-\epsilon)
times the maximum within a given matrix space--namely, the
natural greedy algorithm.
* The paper "From Weak to Strong LP Gaps for All CSPs" by
Mrinalkanti Ghosh and Madhur Tulsiani, which shows that for
constraint satisfaction problems, the basic LP relaxation is
as powerful (in terms of the approximation ratio) as _any_
polynomial-size extended formulation.
* The paper "Trading Information Complexity for Error" by Yuval
Dagan, Yuval Filmus, Hamed Hatami, and Yaqiao Li, which gives
a thorough analysis of the relationship between small-error
information cost and zero-error information cost within
communication complexity.
* "Complexity-Theoretic Foundations of Quantum Supremacy Experiments"
by Scott Aaronson and Lijie Chen, which studies the theoretical
underpinnings of potential near-term separations between quantum
computing and classical computing.
* "Noise Stability Is Computable and Approximately Low-Dimensional"
by Anindya De, Elchanan Mossel, Joe Neeman, which shows that the
solution to the "Gaussian double-bubble problem," and its k-part
generalization, can be computed to any prescribed accuracy in
finite time.
We would very much like to thank the authors for their contributions,
the CCC program committee for their initial reviews, Dieter van
Melkebeek for his advice on all matters related to CCC, and the
anonymous referees for their hard work. It was a pleasure to edit
this special issue for Theory of Computing.
Shachar Lovett
Ryan O'Donnell
Guest Editors
-----------------------------------------------
CCC 2017 Program Committee
* Manindra Agrawal (IIT Kanpur)
* Eli Ben-Sasson (Technion)
* Amit Chakrabarti (Dartmouth College)
* Kai-Min Chung (Academia Sinica)
* Dmitry Gavinsky (Czech Academy of Sciences)
* Joshua Grochow (University of Colorado, Boulder)
* Michal Koucký (Charles University)
* Shachar Lovett (University of California, San Diego)
* Ryan O'Donnell (Carnegie Mellon University) (Chair)
* Dana Ron (Tel Aviv University)
* Benjamin Rossman (University of Toronto)