Arithmetic circuit complexity

Informally, an arithmetic circuit takes as inputs either variables or numbers, and is allowed to either add or multiply two expressions it has already computed.

Arithmetic circuits provide a formal way to understand the complexity of computing polynomials.

The basic type of question in this line of research is "what is the most efficient way to compute a given polynomial

Every node in it with indegree zero is called an input gate and is labeled by either a variable

An arithmetic formula is a circuit in which every gate has outdegree one (and so the underlying graph is a directed tree).

An input gate computes the polynomial it is labeled by.

Consider the circuit in the figure, for example: the input gates compute (from left to right)

this part is usually called upper bounding the complexity of

Although these two tasks are strongly related, proving lower bounds is usually harder, since in order to prove a lower bound one needs to argue about all circuits at the same time.

As part of the study of the complexity of computing polynomials, some clever circuits (alternatively algorithms) were found.

A well-known example is Strassen's algorithm for matrix product.

Strassen showed that we can, in fact, multiply two matrices using a circuit of size roughly

Strassen's basic idea is a clever way for multiplying

This idea is the starting point of the best theoretical way for multiplying two matrices that takes time roughly

Another interesting story lies behind the computation of the determinant of an

The naive way for computing the determinant requires circuits of size roughly

As for the determinant, the naive circuit for the permanent has size roughly

In terms of proving lower bounds, our knowledge is very limited.

However, these counting arguments usually do not improve our understanding of computation.

The following problem is the main open problem in this area of research: find an explicit polynomial of polynomial degree that requires circuits of superpolynomial size.

lower bound for the size of a circuit computing, e.g., the polynomial

More precisely, Strassen used Bézout's theorem to show that any circuit that simultaneously computes the

and later Baur and Strassen showed the following: given an arithmetic circuit of size

The lack of ability to prove lower bounds brings us to consider simpler models of computation.

These restricted models have been studied extensively and some understanding and results were obtained.

of polynomial degree such that given a monomial we can determine its coefficient in

Valiant showed that the permanent is complete for the class VNP.

One benchmark in our understanding of the computation of polynomials is the work of Valiant, Skyum, Berkowitz and Rackoff.

The analog of this result in the Boolean setting is believed to be false.

This simulation is easier than the depth reduction of Valiant el al. and was shown earlier by Hyafil.