Sign In

Communications of the ACM

Research highlights

Unexpected Power of Low-Depth Arithmetic Circuits

Unexpected Power of Low-Depth Arithmetic Circuits, illustration


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.

Back to Top

1. Introduction

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 satisfiability (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" question and it is widely believed that there are no efficient algorithms 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 number of AND, OR, and NOT gates required to compute a given Boolean function.


No entries found

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account