Theory of Computing
-------------------
Title : Special Issue: CCC 2016: Guest Editor's Foreword
Authors : Prahladh Harsha
Volume : 13
Number : 1
Pages : 1-3
URL : http://www.theoryofcomputing.org/articles/v013a001
Abstract
--------
Special Issue: CCC 2016
Guest Editor's Foreword
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.
May 15, 2017
Prahladh Harsha
Guest Editor
* * *
### CCC 2016 Program Committee
Anindya De (Northwestern University)
Prahladh Harsha (Tata Institute of Fundamental Research)
Neeraj Kayal (Microsoft Research)
Jakob Nordstrom (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)
* * *