Unexpected Power of Low-Depth Arithmetic Circuits

作者：Gupta Ankit^*; Kamath Pritish; Kayal Neeraj; Saptharishi Ramprasad

来源：Communications of the ACM, 2017, 60(6): 93-100.

DOI：10.1145/3065470

Complexity theory aims at understanding the "hardness" of certain tasks with respect to the number of "basic operations" required to perform it. In the case of arithmetic circuit complexity, the goal is to understand how hard it is to compute a formal polynomial in terms of the number of additions and multiplications required. Several earlier results have shown that it is possible to rearrange basic computational elements in surprising ways to give more efficient algorithms. The main result of this article is along a similar vein.
We present a simulation of any formal polynomial computed by an arithmetic circuit by a shallow circuit of not-much larger size. Roughly, depth corresponds to the time required in a massively parallel computation. This result shows that efficient computations can be speedup to run in depth three, while requiring surprisingly low size.
In addition to the possible usefulness of the shallow simulations, this theorem has implications in computational complexity lower bounds, since this implies that any small improvement in current lower bound approaches would lead to dramatic advances in lower bounds research.

• 出版日期2017-6
• 单位Microsoft; MIT