2026-07-21T19:38:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2412 2024-03-06T11:09:02Z ddc:004 open_access

Small space analogues of Valiant's classes and the limitations of skew formula Mahajan, Meena Rao B. V., Raghavendra Algebraic circuits space bounds circuit width nondeterministic circuits skew formulas 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Meena Mahajan and Raghavendra Rao B. V. 2010 Is Part Of Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.09421.7 urn:nbn:de:0030-drops-24126 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.7 eng https://creativecommons.org/licenses/by/4.0/legalcode