Josh Alman

According to our database, Josh Alman authored at least 32 papers between 2015 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models.

Josh Alman, Zhao Song

CoRR, 2024

Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming.

Josh Alman, Ethan Turok, Hantao Yu, Hengzhi Zhang

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication.

Josh Alman, Virginia Vassilevska Williams

SIAM J. Comput., December, 2023

How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation.

Josh Alman, Zhao Song

CoRR, 2023

Tensors Ranks and the Fine-Grained Complexity of Dynamic Programming.

Josh Alman, Ethan Turok, Hantao Yu, Hengzhi Zhang

CoRR, 2023

Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity.

Josh Alman, Kevin Rao

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables.

Josh Alman

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Smaller Low-Depth Circuits for Kronecker Powers.

Josh Alman, Yunfeng Guan, Ashwin Padaki

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing.

Josh Alman, Jiehao Liang, Zhao Song, Ruizhe Zhang, Danyang Zhuo

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Fast Attention Requires Bounded Entries.

Josh Alman, Zhao Song

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Generalizations of Matrix Multiplication can solve the Light Bulb Problem.

Josh Alman, Hengjie Zhang

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Matrix Multiplication and Number on the Forehead Communication.

Josh Alman, Jaroslaw Blasiok

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Parameterized Sensitivity Oracles and Dynamic Algorithms Using Exterior Algebras.

Josh Alman, Dean Hirsch

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

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

Amol Aggarwal, Josh Alman

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Limits on the Universal Method for Matrix Multiplication.

Josh Alman

Theory Comput., 2021

Kronecker products, low-depth circuits, and matrix rigidity.

Josh Alman

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

A Refined Laser Method and Faster Matrix Multiplication.

Josh Alman, Virginia Vassilevska Williams

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

Dynamic Parameterized Problems and Algorithms.

Josh Alman, Matthias Mnich, Virginia Vassilevska Williams

ACM Trans. Algorithms, 2020

Faster Update Time for Turnstile Streaming Algorithms.

Josh Alman, Huacheng Yu

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions.

Josh Alman, Timothy M. Chan, R. Ryan Williams

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

OV Graphs Are (Probably) Hard Instances.

Josh Alman, Virginia Vassilevska Williams

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Algorithms and Hardness for Linear Algebra on Geometric Graphs.

Josh Alman, Timothy Chu, Aaron Schild, Zhao Song

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Predicate Encryption from Bilinear Maps and One-Sided Probabilistic Rank.

Josh Alman, Robin Hui

IACR Cryptol. ePrint Arch., 2019

An Illuminating Algorithm for the Light Bulb Problem.

Josh Alman

Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

Efficient Construction of Rigid Matrices Using an NP Oracle.

Josh Alman, Lijie Chen

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Further Limitations of the Known Approaches for Matrix Multiplication.

Josh Alman, Virginia Vassilevska Williams

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Cell-Probe Lower Bounds from Online Communication Complexity.

Josh Alman, Joshua R. Wang, Huacheng Yu

Electron. Colloquium Comput. Complex., 2017

Probabilistic rank and matrix rigidity.

Josh Alman, R. Ryan Williams

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Theoretical Foundations of Team Matchmaking.

Josh Alman, Dylan M. McKay

Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, 2017

2016

Polynomial Representations of Threshold Functions and Algorithmic Applications.

Josh Alman, Timothy M. Chan, R. Ryan Williams

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Circular planar electrical networks: Posets and positivity.

Joshua Alman, Carl Lian, Brandon Tran

J. Comb. Theory, Ser. A, 2015

Probabilistic Polynomials and Hamming Nearest Neighbors.

Josh Alman, Ryan Williams

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015