93 citations · 174 across the 42 of their papers we have counts for
25 papers · 1 filter
Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs
Josh Alman, Virginia Vassilevska Williams
We give the first polynomial improvements over the textbook algorithms for SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve SUM on integers…
Improving the matrix multiplication exponent with modern optimization and AlphaEvolve
Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii +7
The current best bounds on the matrix multiplication exponent are obtained through a refinement of the laser method called combination loss analysis (Duan et al., 2022; William…
An algorithm for -set cover
Josh Alman, Baitian Li, Kevin Pratt
We show that set cover on a universe of size and with sets of size at most can be solved in time . This improves on a -time alg…
Learning Functions of Halfspaces
Josh Alman, Shyamal Patel, Rocco A. Servedio
We give an algorithm that learns arbitrary Boolean functions of arbitrary halfspaces over , in the challenging distribution-free Probably Approximately Correct (P…
Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
Josh Alman, Baitian Li
We study circuits for computing depth-2 linear transforms defined by Kronecker power matrices. Recent works have improved on decades-old constructions in this area using a new ''re…
Faster exact learning of k-term DNFs with membership and equivalence queries
Josh Alman, Shivam Nadimpalli, Shyamal Patel +1
In 1992 Blum and Rudich [BR92] gave an algorithm that uses membership and equivalence queries to learn -term DNF formulas over in time , improv…
DNF Learning via Locally Mixing Random Walks
Josh Alman, Shivam Nadimpalli, Shyamal Patel +1
We give two results on PAC learning DNF formulas using membership queries in the challenging "distribution-free" learning framework, where learning algorithms must succeed for an a…
Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
Josh Alman, Alexandr Andoni, Hengjie Zhang
We study the average-case version of the Orthogonal Vectors problem, in which one is given as input vectors from which are chosen randomly so that each coordinate i…
Finer-Grained Hardness of Kernel Density Estimation
Josh Alman, Yunfeng Guan
In batch Kernel Density Estimation (KDE) for a kernel function , we are given as input points in dimension , as well…
More Asymmetry Yields Faster Matrix Multiplication
Josh Alman, Ran Duan, Virginia Vassilevska Williams +3
We present a new improvement on the laser method for designing fast matrix multiplication algorithms. The new method further develops the recent advances by [Duan, Wu, Zhou FOCS 20…
Generalizations of Matrix Multiplication can solve the Light Bulb Problem
Josh Alman, Hengjie Zhang
In the light bulb problem, one is given uniformly random vectors . They are all chosen independently except a planted pair $(x_{i…
How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation
Josh Alman, Zhao Song
In the classical transformer attention scheme, we are given three size matrices (the query, key, and value tokens), and the goal is to compute a new $n \time…
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…
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…
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity
Josh Alman
For a matrix and a positive integer , the rank rigidity of is the smallest number of entries of which one must change to make its rank at most . There are man…
Algorithms and Hardness for Linear Algebra on Geometric Graphs
Josh Alman, Timothy Chu, Aaron Schild +1
For a function , and a set of points, the $\mathsf{K…
A Refined Laser Method and Faster Matrix Multiplication
Josh Alman, Virginia Vassilevska Williams
The complexity of matrix multiplication is measured in terms of , the smallest real number such that two matrices can be multiplied using field operatio…
Faster Update Time for Turnstile Streaming Algorithms
Josh Alman, Huacheng Yu
In this paper, we present a new algorithm for maintaining linear sketches in turnstile streams with faster update time. As an application, we show that \texttt{Count} sket…
An Illuminating Algorithm for the Light Bulb Problem
Josh Alman
The Light Bulb Problem is one of the most basic problems in data analysis. One is given as input vectors in , which are all independently and uniformly random, exce…
Dynamic Parameterized Problems and Algorithms
Josh Alman, Matthias Mnich, Virginia Vassilevska Williams
Fixed-parameter algorithms and kernelization are two powerful methods to solve -hard problems. Yet, so far those algorithms have been largely restricted to static inpu…
Cell-Probe Lower Bounds from Online Communication Complexity
Josh Alman, Joshua R. Wang, Huacheng Yu
In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the player…
Polynomial Representations of Threshold Functions and Algorithmic Applications
Josh Alman, Timothy M. Chan, Ryan Williams
We design new polynomials for representing threshold functions in three different regimes: probabilistic polynomials of low degree, which need far less randomness than previous con…