Name
Abstract | ||
|---|---|---|
In the uniform circuit model of computation, the width of a boolean circuit exactly characterizes 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. In the uniform setting, we show that our definition coincides with that of VPSPACE at polynomial width. We introduce the class VL as an algebraic variant of deterministic log-space L; VL is a subclass of VP.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 (an algebraic analog of NL) can be expressed as read-once exponential sums over polynomials in $${{\sf VL}, {\it i.e.}\quad{\sf VBP} \in \Sigma^R \cdot {\sf VL}}$$ . Thus, read-once exponential sums can be viewed as a reasonable way of capturing space-bounded non-determinism. We also show that Σ R ·VBP = VBP, i.e. VBPs are stable under read-once exponential sums. Though the best upper bound we have for Σ R ·VL itself is VNP, we can obtain better upper bounds for width-bounded multiplicatively disjoint (md-) circuits. Without the width restriction, md- arithmetic circuits are known to capture all of VP. We show that read-once exponential sums over md- constant-width arithmetic circuits are within VP and that read-once exponential sums over md- polylog-width arithmetic circuits are within VQP.We also show that exponential sums of a skew formula cannot represent the determinant polynomial. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00037-011-0024-2 | Computational Complexity |
Keywords | DocType | Volume |
arithmetic circuit,algebraic variant,small space analogues,read-once exponential sum,skew formulas,class vl,algebraic model,constant-width arithmetic circuit,sf vl,algebraic analog,polylog-width arithmetic circuit,exponential sum,model of computation,space complexity,boolean circuits | Journal | 22 |
Issue | ISSN | Citations |
1 | 1420-8954 | 3 |
PageRank | References | Authors |
0.42 | 24 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Meena Mahajan | 1 | 688 | 56.90 |
| B. V. Raghavendra Rao | 2 | 53 | 13.86 |