Lower bounds in algebraic computational complexity
From MaRDI portal
Translation from Zap. Nauchn. Semin. Leningr. Otd. Mat. Inst. Steklova 118, 25-82 (Russian) (1982; Zbl 0504.68024).
Cites work
- A lower bound for the computational complexity of a set of disjunctives in a monotone basis
- A lower bound on the number of additions in monotone computations
- Additive complexity in directed computations
- Algebras Having Linear Multiplicative Complexities
- An Algorithm for the Computation of Linear Forms
- An Improved Lower Bound on Polynomial Multiplication
- Application of separability and independence notions for proving lower bounds of circuit complexity
- Computational complexity of computing polynomials over the fields of real and complex numbers
- Computational Complexity over Finite Fields
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
- scientific article; zbMATH DE number 3426889 (Why is no real title available?)
- scientific article; zbMATH DE number 3172224 (Why is no real title available?)
- scientific article; zbMATH DE number 3949711 (Why is no real title available?)
- scientific article; zbMATH DE number 3765129 (Why is no real title available?)
- scientific article; zbMATH DE number 3461412 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3487716 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3597878 (Why is no real title available?)
- scientific article; zbMATH DE number 3628385 (Why is no real title available?)
- scientific article; zbMATH DE number 3628386 (Why is no real title available?)
- scientific article; zbMATH DE number 3214278 (Why is no real title available?)
- scientific article; zbMATH DE number 3227613 (Why is no real title available?)
- scientific article; zbMATH DE number 3276110 (Why is no real title available?)
- scientific article; zbMATH DE number 3079573 (Why is no real title available?)
- Lectures on Chevalley groups
- Lower bounds for polynomials with algebraic coefficients
- Negation can be exponentially powerful
- Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
- On the additive complexity of polynomials
- On the algorithmic complexity of associative algebras
- On the Asymptotic Complexity of Matrix Multiplication
- On the Number of Additions to Compute Specific Polynomials
- On the number of multiplications necessary to compute certain functions
- On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
- Optimal evaluation of pairs of bilinear forms
- Partial and Total Matrix Multiplication
- Polynomials with Rational Coefficients Which are Hard to Compute
- Relation between rank and multiplicative complexity of a bilinear form over a commutative Noetherian ring
- Space-time trade-offs on the FFT algorithm
- Superconcentrators
- The noncommutative Markovian property
- Time-space tradeoffs for computing functions, using connectivity properties of their circuits
Cited in
(9)- Computability of the additive complexity of algebraic circuits with root extracting
- Lower bounds for arithmetic networks
- Some lower bound results for set-multilinear arithmetic computations
- On Kolmogorov complexity in the real Turing machine setting
- Tensor rank: matching polynomials and Schur rings
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- On topological lower bounds for algebraic computation trees
- Subtraction-free complexity, cluster transformations, and spanning trees
- Integer complexity and well-ordering
This page was built for publication: Lower bounds in algebraic computational complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1057648)
