Small space analogues of Valiant's classes and the limitations of skew formulas
type: Item
instance of: scholarly article
title: Small space analogues of Valiant's classes and the limitations of skew formulas
zbMATH Open document ID: 1279.68083
author: Meena Mahajan
author: B. V. Raghavendra Rao
published in: Computational Complexity
publication date: 2013-04-11T00:00:00Z
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 6153146
zbMATH Keywords: arithmetic circuits
zbMATH Keywords: Valiant's classes
zbMATH Keywords: space complexity
zbMATH Keywords: circuit width
zbMATH Keywords: algebraic branching programs
MaRDI profile type: Publication
full work available at URL: s00037-011-0024-2
OpenAlex ID: W2012433578
cites work: Computational Complexity
cites work: On Lower Bounds for Constant Width Arithmetic Circuits
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
cites work: On Relating Time and Space to Size and Depth
cites work: Q4331740
cites work: Completeness and reduction in algebraic complexity theory
cites work: Nondeterministic \(NC^1\) computation
cites work: Division in logspace-uniform NC
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: VPSPACE and a transfer theorem over the reals
cites work: On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth
cites work: Q4843270
cites work: Balancing Bounded Treewidth Circuits
cites work: Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
cites work: Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
cites work: Q4385525
cites work: Expressing a fraction of two determinants as a determinant
cites work: VPSPACE and a transfer theorem over the complex field
cites work: Arithmetizing Classes Around NC 1 and L
cites work: Small-Space Analogues of Valiant’s Classes
cites work: The complexity of computing the permanent
cites work: Characterizing Valiant's algebraic complexity classes
cites work: Q4729767
cites work: Logical Approaches to Computational Barriers
cites work: Q4234123
cites work: Depth-3 arithmetic circuits over fields of characteristic zero
cites work: On polynomial-time truth-table reducibility of intractable sets to P-selective sets
cites work: Graph-theoretic properties in computational complexity
cites work: Q3929052
cites work: Circuit Definitions of Nondeterministic Complexity Classes
cites work: Q4393484
DOI: 10.1007/S00037-011-0024-2
Recommended article: Small-Space Analogues of Valiant’s Classes
Recommended article: Small-dimensional classifying spaces for arithmetic subgroups of general linear groups
Recommended article: Q3635985
Recommended article: A finite analog to the Löwenheim-Skolem theorem
Recommended article: Q3971307
Recommended article: Small maximal partial spreads in classical finite polar spaces
Recommended article: Small \(\Pi^{0}_{1}\) classes
Recommended article: On the structure of the spectrum of small sets
Recommended article: Small skew lattices in rings
Recommended article: Small sets with respect to certain classes of topologies
description: scientific article; zbMATH DE number 6153146