Lower bounds in algebraic computational complexity
From MaRDI portal
Publication:1057648
DOI10.1007/BF02104745zbMath0563.68040OpenAlexW4302593273MaRDI QIDQ1057648
Publication date: 1985
Published in: Journal of Soviet Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02104745
Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Discrete mathematics in relation to computer science (68R99)
Related Items (6)
On Kolmogorov complexity in the real Turing machine setting ⋮ Computability of the additive complexity of algebraic circuits with root extracting ⋮ Integer complexity and well-ordering ⋮ Tensor rank: matching polynomials and Schur rings ⋮ Subtraction-free complexity, cluster transformations, and spanning trees ⋮ Lower bounds for arithmetic networks
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Negation can be exponentially powerful
- Application of separability and independence notions for proving lower bounds of circuit complexity
- A lower bound for the computational complexity of a set of disjunctives in a monotone basis
- Lower bounds for polynomials with algebraic coefficients
- Relation between rank and multiplicative complexity of a bilinear form over a commutative Noetherian ring
- On the algorithmic complexity of associative algebras
- On the additive complexity of polynomials
- Additive complexity in directed computations
- A lower bound on the number of additions in monotone computations
- The noncommutative Markovian property
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
- Lectures on Chevalley Groups
- An Improved Lower Bound on Polynomial Multiplication
- Partial and Total Matrix Multiplication
- On the Asymptotic Complexity of Matrix Multiplication
- An Algorithm for the Computation of Linear Forms
- On the Number of Additions to Compute Specific Polynomials
- Computational Complexity over Finite Fields
- Superconcentrators
- Space-time trade-offs on the FFT algorithm
- Algebras Having Linear Multiplicative Complexities
- Polynomials with Rational Coefficients Which are Hard to Compute
- Computational complexity of computing polynomials over the fields of real and complex numbers
- Optimal evaluation of pairs of bilinear forms
- Time-space tradeoffs for computing functions, using connectivity properties of their circuits
- On the number of multiplications necessary to compute certain functions
- Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
- On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
This page was built for publication: Lower bounds in algebraic computational complexity
