Josh Alman

Publication Activity (10 Years)

Years Active: 2015-2024
Publications (10 Years): 60

Top Topics

Matrix Multiplication

Nearest Neighbor

Kernel Density Estimation

Top Venues

Publications

Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou
More Asymmetry Yields Faster Matrix Multiplication. CoRR (2024)
Josh Alman, Yunfeng Guan
Finer-Grained Hardness of Kernel Density Estimation. CCC (2024)
Josh Alman, Zhao Song
How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation. ICLR (2024)
Josh Alman, Yunfeng Guan
Finer-Grained Hardness of Kernel Density Estimation. CoRR (2024)
Josh Alman, Ethan Turok, Hantao Yu, Hengzhi Zhang
Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming. ITCS (2024)
Josh Alman, Zhao Song
The Fine-Grained Complexity of Gradient Computation for Training Large Language Models. CoRR (2024)
Josh Alman, Zhao Song
Fast Attention Requires Bounded Entries. CoRR (2023)
Josh Alman, Jaroslaw Blasiok
Matrix Multiplication and Number On the Forehead Communication. CoRR (2023)
Josh Alman, Yunfeng Guan, Ashwin Padaki
Smaller Low-Depth Circuits for Kronecker Powers. SODA (2023)
Josh Alman, Zhao Song
How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation. CoRR (2023)
Josh Alman, Kevin Rao
Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity. STOC (2023)
Josh Alman, Virginia Vassilevska Williams
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication. SIAM J. Comput. 52 (6) (2023)
Josh Alman, Zhao Song
Fast Attention Requires Bounded Entries. NeurIPS (2023)
Josh Alman
Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables. SOSA (2023)
Josh Alman, Hengjie Zhang
Generalizations of Matrix Multiplication can solve the Light Bulb Problem. FOCS (2023)
Josh Alman, Jaroslaw Blasiok
Matrix Multiplication and Number on the Forehead Communication. CCC (2023)
Josh Alman, Jiehao Liang, Zhao Song, Ruizhe Zhang, Danyang Zhuo
Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing. NeurIPS (2023)
Josh Alman, Hengjie Zhang
Generalizations of Matrix Multiplication can solve the Light Bulb Problem. CoRR (2023)
Josh Alman, Ethan Turok, Hantao Yu, Hengzhi Zhang
Tensors Ranks and the Fine-Grained Complexity of Dynamic Programming. CoRR (2023)
Josh Alman, Yunfeng Guan, Ashwin Padaki
Smaller Low-Depth Circuits for Kronecker Powers. CoRR (2022)
Josh Alman, Jiehao Liang, Zhao Song, Ruizhe Zhang, Danyang Zhuo
Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing. CoRR (2022)
Josh Alman, Dean Hirsch
Parameterized Sensitivity Oracles and Dynamic Algorithms Using Exterior Algebras. ICALP (2022)
Josh Alman
Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables. CoRR (2022)
Josh Alman, Kevin Rao
Faster Walsh-Hadamard and Discrete Fourier Transforms From Matrix Non-Rigidity. CoRR (2022)
Amol Aggarwal, Josh Alman
Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation. CoRR (2022)
Josh Alman, Dean Hirsch
Parameterized Sensitivity Oracles and Dynamic Algorithms using Exterior Algebras. CoRR (2022)
Amol Aggarwal, Josh Alman
Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation. CCC (2022)
Josh Alman
Limits on the Universal Method for Matrix Multiplication. Theory Comput. 17 (2021)
Josh Alman
Kronecker products, low-depth circuits, and matrix rigidity. STOC (2021)
Josh Alman
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity. CoRR (2021)
Josh Alman, Virginia Vassilevska Williams
A Refined Laser Method and Faster Matrix Multiplication. SODA (2021)
Josh Alman, Timothy M. Chan, R. Ryan Williams
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions. SODA (2020)
Josh Alman, Timothy Chu, Aaron Schild, Zhao Song
Algorithms and Hardness for Linear Algebra on Geometric Graphs. CoRR (2020)
Josh Alman, Matthias Mnich, Virginia Vassilevska Williams
Dynamic Parameterized Problems and Algorithms. ACM Trans. Algorithms 16 (4) (2020)
Josh Alman, Virginia Vassilevska Williams
A Refined Laser Method and Faster Matrix Multiplication. CoRR (2020)
Josh Alman, Virginia Vassilevska Williams
OV Graphs Are (Probably) Hard Instances. ITCS (2020)
Josh Alman, Timothy Chu, Aaron Schild, Zhao Song
Algorithms and Hardness for Linear Algebra on Geometric Graphs. FOCS (2020)
Josh Alman, Huacheng Yu
Faster Update Time for Turnstile Streaming Algorithms. SODA (2020)
Josh Alman
An Illuminating Algorithm for the Light Bulb Problem. SOSA (2019)
Josh Alman, Lijie Chen
Efficient Construction of Rigid Matrices Using an NP Oracle. FOCS (2019)
Josh Alman, Robin Hui
Predicate Encryption from Bilinear Maps and One-Sided Probabilistic Rank. IACR Cryptol. ePrint Arch. 2019 (2019)
Josh Alman, Huacheng Yu
Faster Update Time for Turnstile Streaming Algorithms. CoRR (2019)
Josh Alman
Limits on the Universal Method for Matrix Multiplication. Computational Complexity Conference (2019)
Josh Alman, Robin Hui
Predicate Encryption from Bilinear Maps and One-Sided Probabilistic Rank. TCC (1) (2019)
Josh Alman, Virginia Vassilevska Williams
Further Limitations of the Known Approaches for Matrix Multiplication. ITCS (2018)
Josh Alman, Virginia Vassilevska Williams
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication. CoRR (2018)
Josh Alman, Virginia Vassilevska Williams
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication. FOCS (2018)
Josh Alman, Joshua R. Wang, Huacheng Yu
Cell-probe lower bounds from online communication complexity. STOC (2018)
Josh Alman
An Illuminating Algorithm for the Light Bulb Problem. CoRR (2018)
Josh Alman
Limits on the Universal Method for Matrix Multiplication. CoRR (2018)
Josh Alman, Dylan McKay
Theoretical Foundations of Team Matchmaking. AAMAS (2017)
Josh Alman, Virginia Vassilevska Williams
Further limitations of the known approaches for matrix multiplication. CoRR (2017)
Josh Alman, Matthias Mnich, Virginia Vassilevska Williams
Dynamic Parameterized Problems and Algorithms. CoRR (2017)
Josh Alman, Joshua R. Wang, Huacheng Yu
Cell-Probe Lower Bounds from Online Communication Complexity. Electron. Colloquium Comput. Complex. 24 (2017)
Josh Alman, Joshua R. Wang, Huacheng Yu
Cell-Probe Lower Bounds from Online Communication Complexity. CoRR (2017)
Josh Alman, Matthias Mnich, Virginia Vassilevska Williams
Dynamic Parameterized Problems and Algorithms. ICALP (2017)
Josh Alman, R. Ryan Williams
Probabilistic rank and matrix rigidity. STOC (2017)
Josh Alman, Ryan Williams
Probabilistic Rank and Matrix Rigidity. CoRR (2016)
Josh Alman, Timothy M. Chan, R. Ryan Williams
Polynomial Representations of Threshold Functions and Algorithmic Applications. FOCS (2016)
Josh Alman, Timothy M. Chan, Ryan Williams
Polynomial Representations of Threshold Functions and Algorithmic Applications. CoRR (2016)
Josh Alman, Ryan Williams
Probabilistic Polynomials and Hamming Nearest Neighbors. CoRR (2015)
Josh Alman, Ryan Williams
Probabilistic Polynomials and Hamming Nearest Neighbors. FOCS (2015)