Name
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, todefinealgebraicvariants ofnon-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, i.e. VBP ∈ ΣR ċ VL. We also show that ΣR ċ VBP = VBP, i.e. VBPs are stable under read-once exponential sums. Further, we show that read-once exponential sumsover 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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-03409-1_23 | FCT |
Keywords | Field | DocType |
arithmetic circuit,read-once exponential sum,read-once exponential sumsover,boolean circuit,algebraic variant,polynomial width,algebraic model,poly-log-width circuit,small-space analogue,constant-width arithmetic circuit,class vl,boolean circuits,model of computation,exponential sum,branching program,space complexity | Discrete mathematics,Combinatorics,Boolean circuit,Algebraic number,Circuit complexity,Exponential sum,Polynomial,PSPACE,Model of computation,Arithmetic circuit complexity,Mathematics | Conference |
Volume | ISSN | ISBN |
5699 | 0302-9743 | 3-642-03408-X |
Citations | PageRank | References |
8 | 0.56 | 14 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Meena Mahajan | 1 | 688 | 56.90 |
| B. V. Raghavendra Rao | 2 | 53 | 13.86 |