Algebraic Complexity Classes
From MaRDI portal
Publication:2821695
DOI10.1007/978-3-319-05446-9_4zbMath1345.68145arXiv1307.3863OpenAlexW1479979187MaRDI QIDQ2821695
Publication date: 22 September 2016
Published in: Perspectives in Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1307.3863
Related Items
Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring, On the relative power of reduction notions in arithmetic circuit complexity, \textsf{VNP} = \textsf{VP} in the multilinear world, Unnamed Item, Factorization of polynomials given by arithmetic branching programs, Factorization of polynomials given by arithmetic branching programs, Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Resource trade-offs in syntactically multilinear arithmetic circuits
- Arithmetic circuits: the chasm at depth four gets wider
- On the expressive power of CNF formulas of bounded tree- and clique-width
- Quadratic lower bound for permanent vs. determinant in any characteristic
- On defining integers and proving arithmetic circuit lower bounds
- Lower bounds and separations for constant depth multilinear circuits
- On the ultimate complexity of factorials
- On the relation between the determinant and the permanent
- Permanent and determinant
- On two extremal matrix problems
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- A note on the determinant and permanent problem
- A partial k-arboretum of graphs with bounded treewidth
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Completeness and reduction in algebraic complexity theory
- Valiant's model and the cost of computing integers
- Cook's versus Valiant's hypothesis
- Balancing syntactically multilinear arithmetic circuits
- Characterizing Valiant's algebraic complexity classes
- Relationships between nondeterministic and deterministic tape complexities
- Symmetric determinantal representations in characteristic 2
- Arithmetic Circuits: A Chasm at Depth 3
- Improved Bounds for Reduction to Depth 4 and Depth 3
- The arithmetic complexity of tensor contractions
- Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
- On the Power of Algebraic Branching Programs of Width Two
- Fast Parallel Computation of Polynomials Using Few Processors
- Arithmetic Circuits: A survey of recent results and open questions
- Symmetric Determinantal Representation of Weakly-Skew Circuits
- A Dichotomy Theorem for Polynomial Evaluation
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
- Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
- On the Complexity of Numerical Analysis
- A Lower Bound for the Formula Size of Rational Functions
- Computing Algebraic Formulas Using a Constant Number of Registers
- Circuit Definitions of Nondeterministic Complexity Classes
- Fast Parallel Matrix Inversion Algorithms
- On the Parallel Evaluation of Multivariate Polynomials
- On asymptotic estimates for arithmetic cost functions
- The Parallel Evaluation of General Arithmetic Expressions
- The cost of computing integers
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- Expressing a fraction of two determinants as a determinant
- Noncommutativity Makes Determinants Hard
- Separating multilinear branching programs and formulas
- Approaching the Chasm at Depth Four
- Multi-linear formulas for permanent and determinant are of super-polynomial size
