Additive complexity in directed computations

DOI10.1016/0304-3975(82)90014-7zbMath0486.68028OpenAlexW2118664263MaRDI QIDQ1164996

Dima Yu. Grigoriev

Publication date: 1982

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(82)90014-7

zbMATH Keywords

Coxeter groupsChevalley groupssubstitutionadditive straight-line programdirected complexity measuredirected computationgeneralized Bruhat decompositionnon- linear lower boundssets of linear formstriangular complexity measuretriangular computationweak form of Valiant's conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Linear algebraic groups over arbitrary fields (20G15) General structure theory for semigroups (20M10) Canonical forms, reductions, classification (15A21)

Related Items

A seven-dimensional family of simple harmonic functions, Computability of the additive complexity of algebraic circuits with root extracting, On rational functions of first-class complexity, A fast algorithm for expansion over spherical harmonics, Analytical complexity: development of the topic, Recognizing Schubert cells., Fast Generalized Bruhat Decomposition, Lower bounds in algebraic computational complexity, Fast distance multiplication of unit-Monge matrices, Arithmetic complexity of certain linear transformations

Cites Work

• An Algorithm for the Computation of Linear Forms
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• Introduction to Algebraic K-Theory. (AM-72)
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• Further Pathologies in Algebraic Geometry
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item