Algebraic complexity classes
From MaRDI portal
Abstract: This survey describes, at an introductory level, the algebraic complexity framework originally proposed by Leslie Valiant in 1979, and some of the insights that have been obtained more recently.
Recommendations
Cites work
- A Dichotomy Theorem for Polynomial Evaluation
- A Lower Bound for the Formula Size of Rational Functions
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
- A note on the determinant and permanent problem
- A partial k-arboretum of graphs with bounded treewidth
- Approaching the chasm at depth four
- Arithmetic circuits: a chasm at depth 3
- Arithmetic circuits: a survey of recent results and open questions
- Arithmetic circuits: the chasm at depth four gets wider
- Balancing syntactically multilinear arithmetic circuits
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
- Characterizing Valiant's algebraic complexity classes
- Circuit Definitions of Nondeterministic Complexity Classes
- Completeness and reduction in algebraic complexity theory
- Computing Algebraic Formulas Using a Constant Number of Registers
- Cook's versus Valiant's hypothesis
- Elusive functions and lower bounds for arithmetic circuits
- Expressing a fraction of two determinants as a determinant
- Fast Parallel Computation of Polynomials Using Few Processors
- Fast Parallel Matrix Inversion Algorithms
- scientific article; zbMATH DE number 3182201 (Why is no real title available?)
- scientific article; zbMATH DE number 3744549 (Why is no real title available?)
- scientific article; zbMATH DE number 176871 (Why is no real title available?)
- scientific article; zbMATH DE number 3461412 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 1161568 (Why is no real title available?)
- scientific article; zbMATH DE number 2151804 (Why is no real title available?)
- scientific article; zbMATH DE number 6472651 (Why is no real title available?)
- Improved Bounds for Reduction to Depth 4 and Depth 3
- Lower bounds and separations for constant depth multilinear circuits
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
- Monomials in arithmetic circuits: complete problems in the counting hierarchy
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Noncommutativity makes determinants hard
- On asymptotic estimates for arithmetic cost functions
- On defining integers and proving arithmetic circuit lower bounds
- On the Complexity of Numerical Analysis
- On the expressive power of CNF formulas of bounded tree- and clique-width
- On the Parallel Evaluation of Multivariate Polynomials
- On the power of algebraic branching programs of width two
- On the relation between the determinant and the permanent
- On the ultimate complexity of factorials
- On two extremal matrix problems
- Permanent and determinant
- Quadratic lower bound for permanent vs. determinant in any characteristic
- Relationships between nondeterministic and deterministic tape complexities
- Resource trade-offs in syntactically multilinear arithmetic circuits
- Separating multilinear branching programs and formulas
- Separation of multilinear circuit and formula size
- Symmetric Determinantal Representation of Weakly-Skew Circuits
- Symmetric determinantal representations in characteristic 2
- The arithmetic complexity of tensor contractions
- The cost of computing integers
- The Parallel Evaluation of General Arithmetic Expressions
- Valiant's model and the cost of computing integers
Cited in
(18)- On the relative power of reduction notions in arithmetic circuit complexity
- Factorization of polynomials given by arithmetic branching programs
- Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
- On the complexity of the differential-algebraic description of analytic complexity classes
- Counting complexity classes for numeric computations II
- Decision Versus Evaluation in Algebraic Complexity
- On the complexity of symmetric polynomials
- Factorization of polynomials given by arithmetic branching programs
- Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
- Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)
- Lower bounds for the sum of small-size algebraic branching programs
- On the power of border width-2 ABPs over fields of characteristic 2
- Improved lower bound, and proof barrier, for constant depth algebraic circuits
- Lower bounds for the sum of small-size algebraic branching programs
- A largish sum-of-squares implies circuit hardness and derandomization
- The existential theory of the reals with summation operators
- Monotone bounded-depth complexity of homomorphism polynomials
- \textsf{VNP} = \textsf{VP} in the multilinear world
This page was built for publication: Algebraic complexity classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2821695)
