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 Bläser, 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.

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)