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.68045MaRDI 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 complexity; circuit complexity; semiring; matrix multiplication; vector convolution; distance product; semi-disjoint bilinear form; unit-cost ram
68Q25: Analysis of algorithms and problem complexity
68R05: Combinatorics in computer science
15A63: Quadratic and bilinear forms, inner products
65F99: Numerical linear algebra
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
