The boolean circuit complexity classes
AC^0 \subseteq AC^0[m] \subseteq TC^0 \subseteq NC^1 have been studied
intensely. Other than NC^1, they are defined by constant-depth
circuits of polynomial size and unbounded fan-in over some set of
allowed gates. One reason for interest in these classes is that they
contain the ... more >>>

Suppose $f$ is a univariate polynomial of degree $r=r(n)$ that is computed by a size $n$ arithmetic circuit.
It is a basic fact of algebra that a nonzero univariate polynomial of degree $r$ can vanish on at most $r$ points. This implies that for checking whether $f$ is identically zero, ... more >>>

We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit $C(x_1,\ldots,x_n)$ of size $s$ and degree $d$ over a field ${\mathbb F}$, and any inputs $a_1,\ldots,a_K \in {\mathbb F}^n$,
$\bullet$ the Prover sends the Verifier the values $C(a_1), \ldots, C(a_K) \in {\mathbb F}$ and ... more >>>

In the setting of non-commutative arithmetic computations, we define a class of circuits that gener-
alize algebraic branching programs (ABP). This model is called unambiguous because it captures the
polynomials in which all monomials are computed in a similar way (that is, all the parse trees are iso-
morphic).
We ... more >>>

We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring $\mathbb{F}\langle x_1,\dots,x_N \rangle$, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse ... more >>>