On the complexity of computing bilinear forms with \(\{0,1\}\) constants

DOI10.1016/0022-0000(80)90006-9zbMath0444.68033OpenAlexW2061364362MaRDI QIDQ1144927

Joseph F. Ja'Ja', Teofilo F. Gonzalez

Publication date: 1980

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(80)90006-9

zbMATH Keywords

bilinear formsNP-completearithmetic complexitymultiplicative complexitybilinear programsadditions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (4)

A randomized algorithm for a tensor-based generalization of the singular value decomposition ⋮ An introduction to the computational complexity of matrix multiplication ⋮ On the complexity of simplifying quadratic forms ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems)

Cites Work

• Negation can be exponentially powerful
• Some simplified NP-complete graph problems
• On the optimal evaluation of a set of bilinear forms
• Parallel concepts in graph theory
• Gaussian elimination is not optimal
• Evaluation of Arithmetic Expressions with Algebraic Identities
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of computing bilinear forms with \(\{0,1\}\) constants