Small space analogues of Valiant's classes and the limitations of skew formula

Abstract

In the uniform circuit model of computation, the width of a boolean
circuit exactly characterises the ``space'' complexity of the
computed function. Looking for a similar relationship in Valiant's
algebraic model of computation, we propose width of an arithmetic
circuit as a possible measure of space. We introduce the class
VL as an algebraic variant of deterministic log-space L. In
the uniform setting, we show that our definition coincides with that
of VPSPACE at polynomial width.

Further, to define algebraic variants of non-deterministic
space-bounded classes, we introduce the notion of ``read-once''
certificates for arithmetic circuits. We show that polynomial-size
algebraic branching programs can be expressed as a read-once
exponential sum over polynomials in VL, ie
$mbox{VBP}inSigma^R cdotmbox{VL}$.
We also show that $Sigma^R cdot mbox{VBP} =mbox{VBP}$, ie
VBPs are stable under read-once exponential sums.  Further, we
show that read-once exponential sums over a restricted class of
constant-width arithmetic circuits are within VQP, and this is the
largest known such subclass of poly-log-width circuits with this
property.

We also study the power of skew formulas and show that exponential
sums of a skew formula cannot represent the determinant polynomial.