Completeness and reduction in algebraic complexity theory
From MaRDI portal
(Redirected from Publication:1567446)
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
Cited in
(78)- Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
- A duality between Boolean functions
- A complexity theory of constructible functions and sheaves
- A Dichotomy Theorem for Polynomial Evaluation
- Resource trade-offs in syntactically multilinear arithmetic circuits
- scientific article; zbMATH DE number 7561742 (Why is no real title available?)
- A super-quadratic lower bound for depth four arithmetic circuits
- Log-concavity and lower bounds for arithmetic circuits
- scientific article; zbMATH DE number 1722667 (Why is no real title available?)
- 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
- The stabilizer of immanants
- On the distribution of runners on a circle
- Permanent versus determinant: not via saturations
- A \(\tau \)-conjecture for Newton polygons
- A note on VNP-completeness and border complexity
- scientific article; zbMATH DE number 7340317 (Why is no real title available?)
- The arithmetic complexity of tensor contraction
- Exotic quantifiers, complexity classes, and complete problems
- New directions in real algebraic geometry. Abstracts from the workshop held March 19--24, 2023
- How I got to like graph polynomials
- 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
- 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
- Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
- Factorization of polynomials given by arithmetic branching programs
- 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
- On the algebraic complexity of some families of coloured Tutte polynomials
- scientific article; zbMATH DE number 7559090 (Why is no real title available?)
- A Wronskian approach to the real \(\tau\)-conjecture
- Non-commutative circuits and the sum-of-squares problem
- ON RELATIVE COMPLETE REDUCIBILITY
- A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant
- Factorization of polynomials given by arithmetic branching programs
- Improved bounds for reduction to depth 4 and depth 3
- Lower bounds for the sum of small-size algebraic branching programs
- Lower bounds for the determinantal complexity of explicit low degree polynomials
- Ulrich complexity
- On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
- Characterizing Valiant's algebraic complexity classes
- From a zoo to a zoology: Towards a general theory of graph polynomials
- Categorical complexity
- Sparse multivariate polynomial interpolation on the basis of Schubert polynomials
- Symmetric determinantal representation of polynomials
- Algebraic complexity classes
- Geometric complexity theory. V: Efficient algorithms for Noether normalization
- No occurrence obstructions in geometric complexity theory
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- Intersection multiplicity of a sparse curve and a low-degree curve
- On hard instances of non-commutative permanent
- Kolmogorov Complexity Theory over the Reals
- The complexity of two problems on arithmetic circuits
- Succinct algebraic branching programs characterizing non-uniform complexity classes
- Rigid continuation paths II. structured polynomial systems
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
- Complexity classes and completeness in algebraic geometry
- scientific article; zbMATH DE number 7561749 (Why is no real title available?)
- Schur polynomials do not have small formulas if the determinant does not
- 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
- Cook's versus Valiant's hypothesis
- On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
- scientific article; zbMATH DE number 7561765 (Why is no real title available?)
- Shadows of Newton polytopes
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)
