JA
Josh Alman
cs.DScs.CCcs.LGmath.COcs.AIstat.MLcs.CLcs.CGcs.DMcs.NA
On Valency
published · living versionsW_3csmnyz7·v1 · currentpublished
Finding Hypercliques Faster Than Brute Force
with Baitian Li, Neha Pant, Kevin Pratt, Ryan Williams
1 version
W_s7c8pz9c·v1published
Preprints & journals
47 papers in the corpus · 2015–2026Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs2610.06783v1 · Josh Alman, Virginia Vassilevska Williams2026 · 0 citationsarXivon Valency
Improving the matrix multiplication exponent with modern optimization and AlphaEvolve2608.16884v1 · Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii et al.2026 · 0 citationsarXiv
An algorithm for -set cover2608.08328v1 · Josh Alman, Baitian Li, Kevin Pratt2026 · 0 citationsarXiv
Superlogarithmic-Rank Matrix Rigidity for the Walsh-Hadamard Transform2608.06592v1 · Josh Alman2026 · 0 citationsarXiv
Asymptotic Rank Speedup Theorems, Revisited2605.21738v2 · Josh Alman, Baitian Li2026 · 0 citationsarXiv
The edge of the asymptotic spectrum of tensors2604.01386v2 · Josh Alman, Baitian Li, Kevin Pratt2026 · 0 citationsarXiv
Learning Functions of Halfspaces2603.08700v2 · Josh Alman, Shyamal Patel, Rocco A. Servedio2026 · 0 citationsarXiv
Poly-attention: a general scheme for higher-order self-attention2602.02422v2 · Sayak Chakrabarti, Toniann Pitassi, Josh Alman2026 · 0 citationsarXiv
Every Bit Counts: A Theoretical Study of Precision-Expressivity Tradeoffs in Quantized Transformers2602.02707v1 · Sayak Chakrabarti, Toniann Pitassi, Josh Alman2026 · 0 citationsarXiv
Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum2509.14489v1 · Josh Alman, Baitian Li2025 · 0 citationsarXiv
Faster exact learning of k-term DNFs with membership and equivalence queries2507.20336v1 · Josh Alman, Shivam Nadimpalli, Shyamal Patel et al.2025 · 1 citationarXiv
Two Heads Are Better than One: Simulating Large Transformers with Small Ones2506.12220v2 · Hantao Yu, Josh Alman2025 · 1 citationarXiv
DNF Learning via Locally Mixing Random Walks2505.18839v1 · Josh Alman, Shivam Nadimpalli, Shyamal Patel et al.2025 · 1 citationarXiv
Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse2505.16284v1 · Josh Alman, Zhao Song2025 · 0 citationsarXiv
Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform2505.11892v1 · Josh Alman, Zhao Song2025 · 0 citationsarXiv
Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification2502.19580v1 · Josh Alman, Jingxun Liang2025 · 1 citationarXiv
Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems2410.22477v1 · Josh Alman, Alexandr Andoni, Hengjie Zhang2024 · 0 citationsarXiv
Improving the Leading Constant of Matrix Multiplication2410.20538v1 · Josh Alman, Hantao Yu2024 · 2 citationsarXiv
Fundamental Limitations on Subquadratic Alternatives to Transformers2410.04271v2 · Josh Alman, Hantao Yu2024 · 0 citationsarXiv
Finer-Grained Hardness of Kernel Density Estimation2407.02372v1 · Josh Alman, Yunfeng Guan2024 · 0 citationsarXiv
More Asymmetry Yields Faster Matrix Multiplication2404.16349v3 · Josh Alman, Ran Duan, Virginia Vassilevska Williams et al.2024 · 36 citationsarXiv
The Fine-Grained Complexity of Gradient Computation for Training Large Language Models2402.04497v1 · Josh Alman, Zhao Song2024 · 2 citationsarXiv
Generalizations of Matrix Multiplication can solve the Light Bulb Problem2311.01630v1 · Josh Alman, Hengjie Zhang2023 · 1 citationarXiv
How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation2310.04064v1 · Josh Alman, Zhao Song2023 · 1 citationarXiv
Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming2309.04683v2 · Josh Alman, Ethan Turok, Hantao Yu et al.2023 · 1 citationarXiv
Fast Attention Requires Bounded Entries2302.13214v2 · Josh Alman, Zhao Song2023 · 13 citationsarXiv
Matrix Multiplication and Number On the Forehead Communication2302.11476v1 · Josh Alman, Jaros\law B\lasiok2023 · 1 citationarXiv
Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing2211.14227v1 · Josh Alman, Jiehao Liang, Zhao Song et al.2022 · 7 citationsarXiv
Faster Walsh-Hadamard and Discrete Fourier Transforms From Matrix Non-Rigidity2211.06459v2 · Josh Alman, Kevin Rao2022 · 3 citationsarXiv
Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables2211.04643v1 · Josh Alman2022 · 1 citationarXiv
Smaller Low-Depth Circuits for Kronecker Powers2211.05217v1 · Josh Alman, Yunfeng Guan, Ashwin Padaki2022 · 1 citationarXiv
Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation2205.06249v1 · Amol Aggarwal, Josh Alman2022 · 2 citationsarXiv
Parameterized Sensitivity Oracles and Dynamic Algorithms using Exterior Algebras2204.10819v2 · Josh Alman, Dean Hirsch2022 · 0 citationsarXiv
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity2102.11992v1 · Josh Alman2021 · 8 citationsarXiv
Metric Transforms and Low Rank Matrices via Representation Theory of the Real Hyperrectangle2011.11503v2 · Josh Alman, Timothy Chu, Gary Miller et al.2020 · 1 citationarXiv
Algorithms and Hardness for Linear Algebra on Geometric Graphs2011.02466v1 · Josh Alman, Timothy Chu, Aaron Schild et al.2020 · 6 citationsarXiv
A Refined Laser Method and Faster Matrix Multiplication2010.05846v2 · Josh Alman, Virginia Vassilevska Williams2020 · 48 citationsTheoretiCS, Volume 3 (September 4, 2024) theoretics:11261
Faster Update Time for Turnstile Streaming Algorithms1911.01351v1 · Josh Alman, Huacheng Yu2019 · 4 citationsarXiv
Limits on the Universal Method for Matrix Multiplication1812.08731v2 · Josh Alman2018 · 8 citationsarXiv
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication1810.08671v1 · Josh Alman, Virginia Vassilevska Williams2018 · 36 citationsarXiv
An Illuminating Algorithm for the Light Bulb Problem1810.06740v1 · Josh Alman2018 · 14 citationsarXiv
Further limitations of the known approaches for matrix multiplication1712.07246v1 · Josh Alman, Virginia Vassilevska Williams2017 · 31 citationsarXiv
Dynamic Parameterized Problems and Algorithms1707.00362v1 · Josh Alman, Matthias Mnich, Virginia Vassilevska Williams2017 · 10 citationsarXiv
Cell-Probe Lower Bounds from Online Communication Complexity1704.06185v2 · Josh Alman, Joshua R. Wang, Huacheng Yu2017 · 3 citationsarXiv
Probabilistic Rank and Matrix Rigidity1611.05558v2 · Josh Alman, Ryan Williams2016 · 52 citationsarXiv
Polynomial Representations of Threshold Functions and Algorithmic Applications1608.04355v1 · Josh Alman, Timothy M. Chan, Ryan Williams2016 · 68 citationsarXiv
Probabilistic Polynomials and Hamming Nearest Neighbors1507.05106v1 · Josh Alman, Ryan Williams2015 · 93 citationsarXiv
Career total: 72 works. 47 are in this corpus.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.