Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model
From MaRDI portal
Publication:2988839
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
time complexitycircuit complexitysemiringmatrix multiplicationvector convolutiondistance productsemi-disjoint bilinear formunit-cost ram
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