Completeness and reduction in algebraic complexity theory

Publication date: 14 June 2000

Published in: Algorithms and Computation in Mathematics (Search for Journal in Brave)

NP-completeness permanent algebraic complexity complexity classes structural complexity relativizations representations of groups Valiant's classes immanants P vs. NP

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (71)

Fast computation of discrete invariants associated to a differential rational mapping ⋮ Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring ⋮ The arithmetic complexity of tensor contraction ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ Ideals of spaces of degenerate matrices ⋮ A Dichotomy Theorem for Polynomial Evaluation ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ \(P\) versus \(NP\) and geometry ⋮ On enumerating monomials and other combinatorial structures by polynomial interpolation ⋮ Ulrich complexity ⋮ On the relative power of reduction notions in arithmetic circuit complexity ⋮ Log-Concavity and Lower Bounds for Arithmetic Circuits ⋮ Permanent versus determinant: Not via saturations ⋮ Sparse multivariate polynomial interpolation on the basis of Schubert polynomials ⋮ New directions in real algebraic geometry. Abstracts from the workshop held March 19--24, 2023 ⋮ Shadows of Newton polytopes ⋮ Rigid continuation paths II. structured polynomial systems ⋮ Schur polynomials do not have small formulas if the determinant does not ⋮ Symmetric determinantal representation of polynomials ⋮ On the distribution of runners on a circle ⋮ Small space analogues of Valiant's classes and the limitations of skew formulas ⋮ Lower bounds for the determinantal complexity of explicit low degree polynomials ⋮ Interpolation in Valiant's theory ⋮ On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices ⋮ On the algebraic complexity of some families of coloured Tutte polynomials ⋮ A Wronskian approach to the real \(\tau\)-conjecture ⋮ Cook's versus Valiant's hypothesis ⋮ CATEGORICAL COMPLEXITY ⋮ Complexity classes and completeness in algebraic geometry ⋮ The complexity of two problems on arithmetic circuits ⋮ Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems ⋮ Une dualité entre fonctions booléennes ⋮ An explicit solution to Post's problem over the reals ⋮ Characterizing Valiant's algebraic complexity classes ⋮ Kolmogorov Complexity Theory over the Reals ⋮ An extended tree-width notion for directed graphs related to the computation of permanents ⋮ Connectivity of joins, cohomological quantifier elimination, and an algebraic Toda's theorem ⋮ Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width ⋮ Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets ⋮ The stabilizer of immanants ⋮ Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improved bounds for reduction to depth 4 and depth 3 ⋮ On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant ⋮ Non-commutative circuits and the sum-of-squares problem ⋮ No occurrence obstructions in geometric complexity theory ⋮ Factorization of polynomials given by arithmetic branching programs ⋮ Intersection multiplicity of a sparse curve and a low-degree curve ⋮ From a zoo to a zoology: Towards a general theory of graph polynomials ⋮ On Hard Instances of Non-Commutative Permanent ⋮ Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes ⋮ On hard instances of non-commutative permanent ⋮ Algebraic Complexity Classes ⋮ Exotic quantifiers, complexity classes, and complete problems ⋮ Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials ⋮ Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Geometric complexity theory V: Efficient algorithms for Noether normalization ⋮ VPSPACE and a transfer theorem over the complex field ⋮ Unnamed Item ⋮ Factorization of polynomials given by arithmetic branching programs ⋮ A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant ⋮ A \(\tau \)-conjecture for Newton polygons ⋮ A complexity theory of constructible functions and sheaves ⋮ Monomials in arithmetic circuits: complete problems in the counting hierarchy ⋮ Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization ⋮ Limitations of sums of bounded read formulas and ABPs

This page was built for publication: Completeness and reduction in algebraic complexity theory