Arithmetic circuit complexity is the object of intense study in four different subareas of theoretical computer science:
1. Derandomization. The problem of determining if two arithmetic circuits compute the same function is known as ACIT (arithmetic circuit identity testing). ACIT is the canonical example of a problem in BPP that is not known to have a deterministic polynomial-time algorithm. Kabanets and Impagliazzo showed that the question of whether or not ACIT is in P very tightly linked to the question of proving circuit size lower bounds.
2. Counting Classes (such as #P and #L) can be characterized using arithmetic circuits.
3. Computation over the Reals. The Blum-Shub-Smale model of computation over the reals is an algebraic model that has received wide attention.
4. Valiant's Classes VP and VNP. Valiant characterized the complexity of the permanent in two different ways. Viewed as a function mapping n-bit strings to binary encodings of Natural numbers, the permanent is complete for the class #P. Viewed as an n-variate polynomial, the permanent is complete for the class VNP.
The general thrust of these four subareas has been in four different directions, and the questions addressed seem quite different from those addressed by work in the numerical analysis community, such as that surveyed by Demmel and Koev.
This talk will survey some recent work that ties all of these areas together in surprising ways. Most of the results that will be discussed can be found in [ABKM, Bu] but I will also discuss some more recent progress.
[Al]
Eric Allender
Arithmetic Circuits and Counting Complexity Classes.
In Complexity of Computations and Proofs, edited by Jan Krajíček, Quaderni di Matematica Vol. 13, Seconda Universita di Napoli, 2004, pp. 33-72.
[ABKM]
E. Allender and P. Buergisser and Johann Kjeldgaard-Pedersen and Peter Bro Miltersen,
On the Complexity of Numerical Analysis,
Proc. 21st Ann. IEEE Conf. on Computational Complexity (CCC '06),
2006, 331--339.
[Bu]
P. Buergisser,
On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity,
TR06-113, ECCC, 2006.
[DK]
J. Demmel and P. Koev,
Accurate and efficient algorithms for floating point computation,
Proceedings of the 2003 International Congress of Industrial
and Applied Mathematics, 2003
[KI]
V. Kabanets and R. Impagliazzo,
Derandomizing polynomial identity tests means proving circuit lower bounds,
STOC 2003, 355--364.