Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model

DOI10.1007/978-3-319-55911-7_30zbMath1460.68045OpenAlexW2600893748MaRDI QIDQ2988839

Dzmitry Sledneu, Mia Persson, Andrzej Lingas

Publication date: 19 May 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-55911-7_30

zbMATH Keywords

time complexitycircuit complexitysemiringmatrix multiplicationvector convolutiondistance productsemi-disjoint bilinear formunit-cost ram

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Quadratic and bilinear forms, inner products (15A63) Numerical linear algebra (65F99)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Necklaces, convolutions, and \(X+Y\)
• Matrix multiplication via arithmetic progressions
• Shortest-path problem is not harder than matrix multiplication
• Monotone switching circuits and Boolean matrix product
• An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
• A lower bound on the number of additions in monotone computations
• On the exponent of all pairs shortest path problem
• Gaussian elimination is not optimal
• Deterministic Verification of Integer Matrix Multiplication in Quadratic Time
• Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds’ Algorithm
• Powers of tensors and fast matrix multiplication
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• On the complexity of matrix product
• The Power of Negative Thinking in Multiplying Boolean Matrices
• Multiplying matrices faster than coppersmith-winograd