## Arithmetic Circuits: A survey of recent results and open questions

by Amir Shpilka and Amir Yehudayoff.

#### Oded's comments

This excellent survey has just appeared as Volume 5, Issue 3-4, in
Foundations
and Trends in Theoretical Computer Science, Now publishers, 2010.

#### The original abstract

A large class of problems in symbolic computation can be expressed as
the task of computing some polynomials; and arithmetic circuits form
the most standard model for studying the complexity of such
computations. This algebraic model of computation attracted a large
amount of research in the last five decades, partially due to its
simplicity and elegance. Being a more structured model than Boolean
circuits, one could hope that the fundamental problems of theoretical
computer science, such as separating P from NP, will be easier to
solve for arithmetic circuits. However, in spite of the appearing
simplicity and the vast amount of mathematical tools available, no
major breakthrough has been seen. In fact, all the fundamental
questions are still open for this model as well. Nevertheless, there
has been a lot of progress in the area and beautiful results have been
found, some in the last few years. As examples we mention the
connection between polynomial identity testing and lower bounds of
Kabanets and Impagliazzo, the lower bounds of Raz for multilinear
formulas, and two new approaches for proving lower bounds: Geometric
Complexity Theory and Elusive Functions.

The goal of this monograph is to survey the field of arithmetic
circuit complexity, focusing mainly on what we find to be the most
interesting and accessible research directions. We aim to cover the
main results and techniques, with an emphasis on works from the last
two decades. In particular, we discuss the recent lower bounds for
multilinear circuits and formulas, the advances in the question of
deterministically checking polynomial identities, and the results
regarding reconstruction of arithmetic circuits. We do, however, also
cover part of the classical works on arithmetic circuits. In order to
keep this monograph at a reasonable length, we do not give full proofs
of most theorems, but rather try to convey the main ideas behind each
proof and demonstrate it, where possible, by proving some special cases.

Back to
list of Oded's choices.