research
∙
09/09/2023
Tensors Ranks and the Fine-Grained Complexity of Dynamic Programming
Generalizing work of Künnemann, Paturi, and Schneider [ICALP 2017], we s...
share
research
∙
02/26/2023
Fast Attention Requires Bounded Entries
In modern machine learning, inner product attention computation is a fun...
research
∙
02/22/2023
Matrix Multiplication and Number On the Forehead Communication
Three-player Number On the Forehead communication may be thought of as a...
research
∙
11/25/2022
Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing
Over the last decade, deep neural networks have transformed our society,...
research
∙
11/11/2022
Faster Walsh-Hadamard and Discrete Fourier Transforms From Matrix Non-Rigidity
We give algorithms with lower arithmetic operation counts for both the W...
research
∙
11/09/2022
Smaller Low-Depth Circuits for Kronecker Powers
We give new, smaller constructions of constant-depth linear circuits for...
research
∙
11/09/2022
Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables
We use lookup tables to design faster algorithms for important algebraic...
research
∙
05/12/2022
Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation
For any real numbers B ≥ 1 and δ∈ (0, 1) and function f: [0, B] →ℝ, let ...
research
∙
04/22/2022
Parameterized Sensitivity Oracles and Dynamic Algorithms using Exterior Algebras
We design the first efficient sensitivity oracles and dynamic algorithms...
research
∙
02/24/2021
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity
For a matrix M and a positive integer r, the rank r rigidity of M is the...
research
∙
11/04/2020
Algorithms and Hardness for Linear Algebra on Geometric Graphs
For a function 𝖪 : ℝ^d×ℝ^d→ℝ_≥ 0, and a set P = { x_1, …, x_n}⊂ℝ^d of n ...
research
∙
10/12/2020
A Refined Laser Method and Faster Matrix Multiplication
The complexity of matrix multiplication is measured in terms of ω, the s...
research
∙
11/04/2019
Faster Update Time for Turnstile Streaming Algorithms
In this paper, we present a new algorithm for maintaining linear sketche...
research
∙
12/20/2018
Limits on the Universal Method for Matrix Multiplication
In a recent work, Alman and Vassilevska Williams [FOCS 2018, arXiv:1810....
research
∙
10/19/2018
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
We study the known techniques for designing Matrix Multiplication algori...
research
∙
10/15/2018
An Illuminating Algorithm for the Light Bulb Problem
The Light Bulb Problem is one of the most basic problems in data analysi...
research
∙
12/19/2017
Further limitations of the known approaches for matrix multiplication
We consider the techniques behind the current best algorithms for matrix...
research
∙
07/02/2017