research
∙
09/12/2023
The Time Complexity of Fully Sparse Matrix Multiplication
What is the time complexity of matrix multiplication of sparse integer m...
share
research
∙
05/26/2023
Can You Solve Closest String Faster than Exhaustive Search?
We study the fundamental problem of finding the best string to represent...
research
∙
04/11/2023
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
In this work we revisit the fundamental Single-Source Shortest Paths (SS...
research
∙
11/14/2022
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics
The "short cycle removal" technique was recently introduced by Abboud, B...
research
∙
04/29/2022
Improved Sublinear-Time Edit Distance for Preprocessed Strings
We study the problem of approximating the edit distance of two strings i...
research
∙
04/25/2022
A Structural Investigation of the Approximability of Polynomial-Time Problems
We initiate the systematic study of a recently introduced polynomial-tim...
research
∙
02/16/2022
Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime
We revisit the task of computing the edit distance in sublinear time. In...
research
∙
07/15/2021
Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution
Computing the convolution A⋆ B of two length-n integer vectors A,B is a ...
research
∙
07/04/2021
Fine-Grained Completeness for Optimization in P
We initiate the study of fine-grained completeness theorems for exact an...
research
∙
05/12/2021
Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution
Computing the convolution A⋆ B of two length-n vectors A,B is an ubiquit...
research
∙
03/16/2020
Faster Minimization of Tardy Processing Time on a Single Machine
This paper is concerned with the 1||∑ p_jU_j problem, the problem of min...
research
∙
02/03/2020
The Computational Complexity of Plethysm Coefficients
In two papers, Bürgisser and Ikenmeyer (STOC 2011, STOC 2013) used an ad...
research
∙
10/17/2018