Josh Alman

activity

20172022

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

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

collaborators

10 papers

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…

cs.DS2021

Kronecker Products, Low-Depth Circuits, and Matrix Rigidity

Josh Alman

For a matrix $M$ and a positive integer $r$ , the rank $r$ rigidity of $M$ is the smallest number of entries of $M$ which one must change to make its rank at most $r$ . There are man…

cs.DS2020

Algorithms and Hardness for Linear Algebra on Geometric Graphs

Josh Alman, Timothy Chu, Aaron Schild +1

For a function $K : R^{d} \times R^{d} \to R_{\geq 0}$ , and a set $P = {x_{1}, \dots, x_{n}} \subset R^{d}$ of $n$ points, the $\mathsf{K…

cs.CG2020

Metric Transforms and Low Rank Matrices via Representation Theory of the Real Hyperrectangle

Josh Alman, Timothy Chu, Gary Miller +3

In this paper, we develop a new technique which we call representation theory of the real hyperrectangle, which describes how to compute the eigenvectors and eigenvalues of certain…

cs.DS2019★ 1 cited

Faster Update Time for Turnstile Streaming Algorithms

Josh Alman, Huacheng Yu

In this paper, we present a new algorithm for maintaining linear sketches in turnstile streams with faster update time. As an application, we show that $lo g n$ \texttt{Count} sket…

cs.CC2018

Limits on the Universal Method for Matrix Multiplication

Josh Alman

In this work, we prove limitations on the known methods for designing matrix multiplication algorithms. Alman and Vassilevska Williams recently defined the Universal Method, which…