Arithmetic Circuit Complexity - Overview

Overview

Given a polynomial f, we may ask ourselves what is the best way to compute it - for example, what is the smallest size of a circuit computing f. The answer to this question consists of two parts. The first part is finding some circuit that computes f; this part is usually called upper bounding the complexity of f. The second part is showing that no other circuit can do better; this part is called lower bounding the complexity of f. 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.

Note that we are interested in the formal computation of polynomials, rather than the functions that the polynomials define. For example, consider the polynomial x2 + x; over the field of two elements this polynomial represents the zero function, but it is not the zero polynomial. This is one of the differences between the study of arithmetic circuits and the study of Boolean circuits. In Boolean complexity, one is mostly interested in computing a function, rather than some representation of it (in our case, a representation by a polynomial). This is one of the reasons that make Boolean complexity harder than arithmetic complexity. The study of arithmetic circuits may also be considered as one of the intermediate steps towards the study of the Boolean case, which we hardly understand.