Unexpected Power of Low-Depth
By Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi
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.
The field of computational complexity broadly attempts
to understand the limits of computation under certain
resource bounds. The main goal of this field is to understand which problems have efficient solutions and which
problems do not. The resources that are often studied are
running time of the algorithm, the space used, the randomness used, number of I/O operations, etc.
In the context of time complexity, recall the Boolean class P,
containing all decision problems that can be solved by an
algorithm that takes polynomial-time in the size of the
input. The class P is the class of all problems that we deem
efficiently computable with respect to time, and we would like
to know if certain algorithmic tasks are in P or not. Some
examples are the traveling salesman problem (TSP) (given a
weighted graph G and a parameter k, check if there is a tour
to visit all vertices of the graph of total cost at most k) or satis-
fiability (SAT) (where given a Boolean formula, check if there
is an assignment to the variables that satisfies the formula).
This question is precisely the well-known “P versus NP” ques-
tion and it is widely believed that there are no efficient algo-
rithms for TSP or SAT. Such conjectures can be interpreted
as saying that these computational tasks require many “basic
elementary operations.” For example, in Boolean circuit
complexity, the goal is to understand the minimum num-
ber of AND, OR, and NOT gates required to compute a given
The classes of problems of interest in this paper are inherently
algebraic such as integer multiplication, matrix multiplication,
where Sd refers to the set of all permutations of d symbols.
The original version of this paper was published in
The 54th Annual Symposium on Foundations of Computer
Science (FOCS 2013), and would also appear in the
SICOMP Special Issue for FOCS 2013.