93 citations · 174 across the 42 of their papers we have counts for
6 papers · 1 filter
Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing
Josh Alman, Jiehao Liang, Zhao Song +2
Over the last decade, deep neural networks have transformed our society, and they are already widely applied in various machine learning applications. State-of-art deep neural netw…
Smaller Low-Depth Circuits for Kronecker Powers
Josh Alman, Yunfeng Guan, Ashwin Padaki
We give new, smaller constructions of constant-depth linear circuits for computing any matrix which is the Kronecker power of a fixed matrix. A standard argument (e.g., the mixed p…
Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables
Josh Alman
We use lookup tables to design faster algorithms for important algebraic problems over finite fields. These faster algorithms, which only use arithmetic operations and lookup table…
Faster Walsh-Hadamard and Discrete Fourier Transforms From Matrix Non-Rigidity
Josh Alman, Kevin Rao
We give algorithms with lower arithmetic operation counts for both the Walsh-Hadamard Transform (WHT) and the Discrete Fourier Transform (DFT) on inputs of power-of-2 size . For…
Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation
Amol Aggarwal, Josh Alman
For any real numbers and and function , let denote the minimum degree of a polynomial…
Parameterized Sensitivity Oracles and Dynamic Algorithms using Exterior Algebras
Josh Alman, Dean Hirsch
We design the first efficient sensitivity oracles and dynamic algorithms for a variety of parameterized problems. Our main approach is to modify the algebraic coding technique from…