Mahajan, Meena ;
Rao B. V. , Raghavendra
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 logspace L. In
the uniform setting, we show that our definition coincides with that
of VPSPACE at polynomial width.
Further, to define algebraic variants of nondeterministic
spacebounded classes, we introduce the notion of ``readonce''
certificates for arithmetic circuits. We show that polynomialsize
algebraic branching programs can be expressed as a readonce
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 readonce exponential sums. Further, we
show that readonce exponential sums over a restricted class of
constantwidth arithmetic circuits are within VQP, and this is the
largest known such subclass of polylogwidth 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.
BibTeX  Entry
@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 = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum 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}
}
Keywords: 

Algebraic circuits, space bounds, circuit width, nondeterministic circuits, skew formulas 
Seminar: 

09421  Algebraic Methods in Computational Complexity

Issue date: 

2010 
Date of publication: 

19.01.2010 