Completeness and reduction in algebraic complexity theory

zbMATH Open0948.68082MaRDI QIDQ1567446FDOQ1567446

Publication date: 14 June 2000

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

Recommendations

Reductions, completeness and the hardness of approximability
Complexity classes and completeness in algebraic geometry
scientific article; zbMATH DE number 3972183
Sufficient-completeness, ground-reducibility and their complexity
Algorithmic reducibilities of algebraic structures
scientific article; zbMATH DE number 3936520
Complete problems and strong polynomial reducibilities
Complete Problems and Strong Polynomial Reducibilities
scientific article; zbMATH DE number 2203952
Computability in partial combinatory algebras

complexity classes NP-completeness permanent structural complexity relativizations algebraic complexity 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)

Cited In (78)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1567446)