Volume 13 (2017) Article 1 pp. 1-3

This collection comprises the expanded and fully refereed versions of selected papers presented at the 31st Conference on Computational Complexity (CCC 2016) held in Tokyo, Japan, May 29 -- 31, 2016. 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. The CCC Program Committee selected 34 out of 91 submissions for presentation at the conference; of these, 5 were invited to this Special Issue. All papers were refereed in accordance with the usual rigorous standards of Theory of Computing.

Below are brief summaries of the five papers that appear in this collection.

• The paper “Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits” by Ruiwen Chen, Rahul Santhanam and Srikanth Srinivasan proves strong (inverse-polynomial) correlation lower bounds for bounded-depth threshold circuits computing parity and the generalized Andreev function, while previously only worst-case lower bounds were known in these settings. These results are then used to give satisfiability algorithms for bounded-depth threshold circuits with a superlinear number of wires which in turn imply sublinear-exponential ($2^{o(n)}$) learning algorithms for the related circuit class.
• The paper “Proof Complexity Lower Bounds from Algebraic Circuit Complexity” by Michael A. Forbes, Amir Shpilka, Iddo Tzameret and Avi Wigderson studies proof complexity in the algebraic framework using connections between algebraic circuit lower bounds and proof complexity, a connection which has been well-explored in the Boolean setting. In particular, this paper shows the first unconditional lower bounds for versions of the Ideal Proof System, introduced by Grochow and Pitassi (2014), restricted to various natural circuit classes like depth 2, depth 3 powering circuits, read-once algebraic branching programs, and various multilinear circuit classes, by adapting techniques from circuit complexity.
• Reed-Muller codes are one of the most studied family of codes. In particular, $m$-variate Reed Muller codes can be seen as the evaluation of a low-degree polynomial on $S^m$ where $S$ is a subset of the underlying finite field $\mathbb{F}$. While the information-theoretic unique decodability is not affected by the specific choice of $S$ (and only depends on the size of $S$), the algorithmic story used to be different. Previous algorithms either required $S =\mathbb{F}$ or that the degree is considerably smaller than $|S|$, the size of the set $S$. The paper “Decoding Reed-Muller codes over product sets” by John Kim and Swastik Kopparty fixes this gap in our understanding and gives an efficient algorithm for unique decoding of RM codes for all settings where the degree is at most the set size $|S|$.
• The paper “Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs” by Rohit Gurjar, Arpita Korwar and Nitin Saxena provides a polynomial-size hitting set for read-once algebraic branching programs of constant width. Prior to this work only quasi-polynomial-size hitting sets were known for this model.
• The paper “Arithmetic circuits with locally low algebraic rank” by Mrinal Kumar and Shubhangi Saraf demonstrates an explicit exponential lower bound for depth-4 arithmetic circuits that are sums of products of polynomials such that the set of polynomials in each product is of low algebraic rank. Then, the authors construct quasi-polynomial-size hitting sets (and hence quasi-polynomial-time deterministic PIT algorithms) for the same class of arithmetic circuits with an additional restriction. These results give a clean generalization of the recent results in algebraic circuit complexity that dealt with depth-4 circuits.

I would like to thank the authors for their contributions and the anonymous referees for their hard work that helped improve the quality of this issue. It was a pleasure to edit this special issue for Theory of Computing.

---

CCC 2016 Program Committee

Anindya De (Northwestern University)
Prahladh Harsha (Tata Institute of Fundamental Research)
Neeraj Kayal (Microsoft Research)
Jakob Nordström (KTH Royal Institute of Technology)
Toniann Pitassi (University of Toronto)
Anup Rao (University of Washington)
Ran Raz (Weizmann Institute & Institute for Advanced Study) (Chair)
David Steurer (Cornell University)
Thomas Vidick (California Institute of Technology)
Amir Yehudayoff (Technion)
Sergey Yekhanin (Microsoft Research)

---

DOI: 10.4086/toc.2017.v013a001

© 2017 Prahladh Harsha
Licensed under a Creative Commons Attribution License