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 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.
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 = {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}
}
Keywords: |
|
Algebraic circuits, space bounds, circuit width, nondeterministic circuits, skew formulas |
Seminar: |
|
09421 - Algebraic Methods in Computational Complexity
|
Issue date: |
|
2010 |
Date of publication: |
|
2010 |
2010