4 papers · 1 filter
An algorithm for -set cover
Josh Alman, Baitian Li, Kevin Pratt
We show that set cover on a universe of size and with sets of size at most can be solved in time . This improves on a -time alg…
Asymptotic Rank Speedup Theorems, Revisited
Josh Alman, Baitian Li
Motivated by fast matrix multiplication and recent connections between asymptotic tensor rank and fine-grained complexity, we revisit classical tools from the matrix multiplication…
The edge of the asymptotic spectrum of tensors
Josh Alman, Baitian Li, Kevin Pratt
Strassen founded the theory of the asymptotic spectrum of tensors to study the complexity of matrix multiplication. A central challenge in this theory is to explicitly construct ne…
Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?
Cornelius Brand, Radu Curticapean, Petteri Kaski +4
The complexity of bilinear maps (equivalently, of -mode tensors) has been studied extensively, most notably in the context of matrix multiplication. While circuit complexity and…