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.

@InProceedings{mahajan_et_al:DSP:2010:2412,
  author =	{Meena Mahajan and Raghavendra Rao B. V. },
  title =	{Small space analogues of Valiant's classes and the limitations of   skew formula},
  booktitle =	{Algebraic Methods in Computational Complexity},
  year =	{2010},
  editor =	{Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
  number =	{09421},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2412},
  annote =	{Keywords: Algebraic circuits, space bounds, circuit width, nondeterministic circuits, skew formulas}
}