Probabilistic Polynomials and Hamming Nearest Neighbors. - Josh Alman; Ryan Williams 001 (FOCS, 2015)

Circular planar electrical networks: Posets and positivity. - Joshua Alman; Carl Lian; Brandon Tran (J. Comb. Theory A, 2015)

Polynomial Representations of Threshold Functions and Algorithmic Applications. - Josh Alman; Timothy M. Chan; R. Ryan Williams (FOCS, 2016)

Theoretical Foundations of Team Matchmaking. - Josh Alman; Dylan M. McKay (AAMAS, 2017)

Probabilistic rank and matrix rigidity. - Josh Alman; R. Ryan Williams (STOC, 2017)

Cell-Probe Lower Bounds from Online Communication Complexity. - Josh Alman; Joshua R. Wang; Huacheng Yu (Electron. Colloquium Comput. Complex., 2017)

Further Limitations of the Known Approaches for Matrix Multiplication. - Josh Alman; Virginia Vassilevska Williams (ITCS, 2018)

Efficient Construction of Rigid Matrices Using an NP Oracle. - Josh Alman; Lijie Chen 001 (FOCS, 2019)

An Illuminating Algorithm for the Light Bulb Problem. - Josh Alman (SOSA, 2019)

Predicate Encryption from Bilinear Maps and One-Sided Probabilistic Rank. - Josh Alman; Robin Hui (IACR Cryptol. ePrint Arch., 2019)

Algorithms and Hardness for Linear Algebra on Geometric Graphs. - Josh Alman; Timothy Chu; Aaron Schild; Zhao Song 002 (FOCS, 2020)

OV Graphs Are (Probably) Hard Instances. - Josh Alman; Virginia Vassilevska Williams (ITCS, 2020)

Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions. - Josh Alman; Timothy M. Chan; R. Ryan Williams (SODA, 2020)

Faster Update Time for Turnstile Streaming Algorithms. - Josh Alman; Huacheng Yu (SODA, 2020)

Dynamic Parameterized Problems and Algorithms. - Josh Alman; Matthias Mnich; Virginia Vassilevska Williams (ACM Trans. Algorithms, 2020)

Kronecker products, low-depth circuits, and matrix rigidity. - Josh Alman (STOC, 2021)

Limits on the Universal Method for Matrix Multiplication. - Josh Alman (Adv. Math. Commun., 2021)

Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation. - Amol Aggarwal; Josh Alman (CCC, 2022)

Parameterized Sensitivity Oracles and Dynamic Algorithms Using Exterior Algebras. - Josh Alman; Dean Hirsch (ICALP, 2022)

Matrix Multiplication and Number on the Forehead Communication. - Josh Alman; Jaroslaw Blasiok (CCC, 2023)

Generalizations of Matrix Multiplication can solve the Light Bulb Problem. - Josh Alman; Hengjie Zhang (FOCS, 2023)

Fast Attention Requires Bounded Entries. - Josh Alman; Zhao Song 002 (NeurIPS, 2023)

Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing. - Josh Alman; Jiehao Liang; Zhao Song 002; Ruizhe Zhang 001; Danyang Zhuo (NeurIPS, 2023)

Smaller Low-Depth Circuits for Kronecker Powers. - Josh Alman; Yunfeng Guan 002; Ashwin Padaki (SODA, 2023)

Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables. - Josh Alman (SOSA, 2023)

Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity. - Josh Alman; Kevin Rao (STOC, 2023)

Tensors Ranks and the Fine-Grained Complexity of Dynamic Programming. - Josh Alman; Ethan Turok; Hantao Yu; Hengzhi Zhang (CoRR, 2023)

Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication. - Josh Alman; Virginia Vassilevska Williams (SIAM J. Comput., 2023)

Finer-Grained Hardness of Kernel Density Estimation. - Josh Alman; Yunfeng Guan 002 (CCC, 2024)

How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation. - Josh Alman; Zhao Song 002 (ICLR, 2024)

Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming. - Josh Alman; Ethan Turok; Hantao Yu; Hengzhi Zhang (ITCS, 2024)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models. - Josh Alman; Zhao Song 002 (NeurIPS, 2024)

Metric Transforms and Low Rank Representations of Kernels for Fast Attention. - Timothy Chu; Josh Alman; Gary L. Miller; Shyam Narayanan; Mark Sellke; Zhao Song 002 (NeurIPS, 2024)

Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems. - Josh Alman; Alexandr Andoni; Hengjie Zhang (CoRR, 2024)

A Refined Laser Method and Faster Matrix Multiplication. - Josh Alman; Virginia Vassilevska Williams (TheoretiCS, 2024)

Fundamental Limitations on Subquadratic Alternatives to Transformers. - Josh Alman; Hantao Yu (ICLR, 2025)

Sparsity Lower Bounds for Probabilistic Polynomials. - Josh Alman; Arkadev Chattopadhyay; Ryan Williams 001 (ITCS, 2025)

More Asymmetry Yields Faster Matrix Multiplication. - Josh Alman; Ran Duan; Virginia Vassilevska Williams; Yinzhan Xu; Zixuan Xu; Renfei Zhou (SODA, 2025)

Improving the Leading Constant of Matrix Multiplication. - Josh Alman; Hantao Yu (SODA, 2025)

Faster Algorithms for Average-Case Orthogonal Vectors and Closes Pair Problems. - Josh Alman; Alexandr Andoni; Hengjie Zhang (SOSA, 2025)

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification. - Josh Alman; Jingxun Liang (STOC, 2025)

DNF Learning via Locally Mixing Random Walks. - Josh Alman; Shivam Nadimpalli; Shyamal Patel; Rocco A. Servedio (STOC, 2025)

Fine-Grained Complexity in a World without Cryptography. - Josh Alman; Yizhi Huang; Kevin Yeo (IACR Cryptol. ePrint Arch., 2025)

Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform. - Josh Alman; Zhao Song 002 (CoRR, 2025)

Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse. - Josh Alman; Zhao Song 002 (CoRR, 2025)

Two Heads Are Better than One: Simulating Large Transformers with Small Ones. - Hantao Yu; Josh Alman (CoRR, 2025)

Faster exact learning of k-term DNFs with membership and equivalence queries. - Josh Alman; Shivam Nadimpalli; Shyamal Patel; Rocco A. Servedio (CoRR, 2025)