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       : https://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)