Small space analogues of Valiant's classes and the limitations of skew formulas (Q1947043): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1007/s00037-011-0024-2
+Normal rank
@@ Property / OpenAlex ID @@
+W2012433578
@@ Property / OpenAlex ID: W2012433578 / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+On Lower Bounds for Constant Width Arithmetic Circuits
+Normal rank
@@ Property / cites work @@
+Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
+Normal rank
@@ Property / cites work @@
+COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
@@ Property / cites work: COMPLEXITY AND REAL COMPUTATION: A MANIFESTO / rank @@
+Normal rank
@@ Property / cites work @@
+On Relating Time and Space to Size and Depth
@@ Property / cites work: On Relating Time and Space to Size and Depth / rank @@
+Normal rank
@@ Property / cites work @@
+Q4331740
@@ Property / cites work: Q4331740 / rank @@
+Normal rank
@@ Property / cites work @@
+Completeness and reduction in algebraic complexity theory
+Normal rank
@@ Property / cites work @@
+Nondeterministic \(NC^1\) computation
@@ Property / cites work: Nondeterministic \(NC^1\) computation / rank @@
+Normal rank
@@ Property / cites work @@
+Division in logspace-uniform<i>NC</i><sup>1</sup>
@@ Property / cites work: Division in logspace-uniform<i>NC</i><sup>1</sup> / rank @@
+Normal rank
@@ Property / cites work @@
+Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
+Normal rank
@@ Property / cites work @@
+VPSPACE and a transfer theorem over the reals
@@ Property / cites work: VPSPACE and a transfer theorem over the reals / rank @@
+Normal rank
@@ Property / cites work @@
+On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth
+Normal rank
@@ Property / cites work @@
+Q4843270
@@ Property / cites work: Q4843270 / rank @@
+Normal rank
@@ Property / cites work @@
+Balancing Bounded Treewidth Circuits
@@ Property / cites work: Balancing Bounded Treewidth Circuits / rank @@
+Normal rank
@@ Property / cites work @@
+Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
+Normal rank
@@ Property / cites work @@
+Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
+Normal rank
@@ Property / cites work @@
+Q4385525
@@ Property / cites work: Q4385525 / rank @@
+Normal rank
@@ Property / cites work @@
+Expressing a fraction of two determinants as a determinant
+Normal rank
@@ Property / cites work @@
+VPSPACE and a transfer theorem over the complex field
+Normal rank
@@ Property / cites work @@
+Arithmetizing Classes Around NC 1 and L
@@ Property / cites work: Arithmetizing Classes Around NC 1 and L / rank @@
+Normal rank
@@ Property / cites work @@
+Small-Space Analogues of Valiant’s Classes
@@ Property / cites work: Small-Space Analogues of Valiant’s Classes / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of computing the permanent
@@ Property / cites work: The complexity of computing the permanent / rank @@
+Normal rank
@@ Property / cites work @@
+Characterizing Valiant's algebraic complexity classes
+Normal rank
@@ Property / cites work @@
+Q4729767
@@ Property / cites work: Q4729767 / rank @@
+Normal rank
@@ Property / cites work @@
+Logical Approaches to Computational Barriers
@@ Property / cites work: Logical Approaches to Computational Barriers / rank @@
+Normal rank
@@ Property / cites work @@
+Q4234123
@@ Property / cites work: Q4234123 / rank @@
+Normal rank
@@ Property / cites work @@
+Depth-3 arithmetic circuits over fields of characteristic zero
+Normal rank
@@ Property / cites work @@
+On polynomial-time truth-table reducibility of intractable sets to P-selective sets
+Normal rank
@@ Property / cites work @@
+Graph-theoretic properties in computational complexity
+Normal rank
@@ Property / cites work @@
+Q3929052
@@ Property / cites work: Q3929052 / rank @@
+Normal rank
@@ Property / cites work @@
+Circuit Definitions of Nondeterministic Complexity Classes
+Normal rank
@@ Property / cites work @@
+Q4393484
@@ Property / cites work: Q4393484 / rank @@
+Normal rank