Josh Alman

activity

20172026

most citedBypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing

4 citations · 5 across the 21 of their papers we have counts for

collaborators

Showing cs.CCShow all

9 papers · 1 filter

cs.CC2026

Superlogarithmic-Rank Matrix Rigidity for the Walsh-Hadamard Transform

Josh Alman

For sufficiently large $N$ which is a power of 2, we prove that changing at most one percent of the entries of the $N \times N$ Walsh-Hadamard Transform cannot reduce its rank over…

cs.CC2026

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…

cs.CC2026

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…

cs.CC2025

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification

Josh Alman, Jingxun Liang

For an $N \times N$ matrix $A$ , its rank- $r$ rigidity, denoted $R_{A} (r)$ , is the minimum number of entries of $A$ that one must change to make its rank become at most $r$ .…

cs.CC2024

Improving the Leading Constant of Matrix Multiplication

Josh Alman, Hantao Yu

Algebraic matrix multiplication algorithms are designed by bounding the rank of matrix multiplication tensors, and then using a recursive method. However, designing algorithms in t…

cs.CC2022

Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation

Amol Aggarwal, Josh Alman

For any real numbers $B \geq 1$ and $δ \in (0, 1)$ and function $f : [0, B] \to R$ , let $d_{B; δ} (f) \in Z_{> 0}$ denote the minimum degree of a polynomial…