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
- 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?)
- 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
- Improved Bounds for Reduction to Depth 4 and Depth 3
- Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
- Lower bounds and separations for constant depth multilinear circuits
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- 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 Parallel Evaluation of Multivariate Polynomials
- On the expressive power of CNF formulas of bounded tree- and clique-width
- 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 Parallel Evaluation of General Arithmetic Expressions
- The arithmetic complexity of tensor contractions
- The cost of computing integers
- Valiant's model and the cost of computing integers
Cited in
(17)- Decision Versus Evaluation in Algebraic Complexity
- Counting complexity classes for numeric computations II
- Lower bounds for the sum of small-size algebraic branching programs
- Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
- On the relative power of reduction notions in arithmetic circuit complexity
- Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
- A largish sum-of-squares implies circuit hardness and derandomization
- Factorization of polynomials given by arithmetic branching programs
- \textsf{VNP} = \textsf{VP} in the multilinear world
- scientific article; zbMATH DE number 7559090 (Why is no real title available?)
- Factorization of polynomials given by arithmetic branching programs
- Lower bounds for the sum of small-size algebraic branching programs
- The existential theory of the reals with summation operators
- On the power of border width-2 ABPs over fields of characteristic 2
- Improved lower bound, and proof barrier, for constant depth algebraic circuits
- On the complexity of the differential-algebraic description of analytic complexity classes
- Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)
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)
