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
∙
08/06/2023
Knapsack with Small Items in Near-Quadratic Time
The Bounded Knapsack problem is one of the most fundamental NP-complete ...
research
∙
05/02/2023
Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution
We revisit the classic 0-1-Knapsack problem, in which we are given n ite...
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
∙
10/21/2022
Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries
We study the enumeration of answers to Unions of Conjunctive Queries (UC...
research
∙
05/17/2022
Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution
We present new exact and approximation algorithms for 0-1-Knapsack and U...
research
∙
05/16/2022
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds
We consider the unlabeled motion-planning problem of m unit-disc robots ...
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
∙
04/22/2022
Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond
We present a new technique for efficiently removing almost all short cyc...
research
∙
03/15/2022
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
The Dynamic Time Warping (DTW) distance is a popular measure of similari...
research
∙
03/07/2022
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs
We initiate the study of diameter computation in geometric intersection ...
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
∙
01/07/2022
Tight Fine-Grained Bounds for Direct Access on Join Queries
We consider the task of lexicographic direct access to query answers. Th...
research
∙
10/19/2021
Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry
Fine-grained complexity theory is the area of theoretical computer scien...
research
∙
07/28/2021
Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum
In the classical Subset Sum problem we are given a set X and a target t,...
research
∙
07/16/2021
Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance
We study the c-approximate near neighbor problem under the continuous Fr...
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/15/2021
Sparse Fourier Transform by traversing Cooley-Tukey FFT computation graphs
Computing the dominant Fourier coefficients of a vector is a common task...
research
∙
07/04/2021
Fine-Grained Completeness for Optimization in P
We initiate the study of fine-grained completeness theorems for exact an...
research
∙
06/15/2021
A Linear-Time n^0.4-Approximation for Longest Common Subsequence
We consider the classic problem of computing the Longest Common Subseque...
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
∙
05/11/2021
Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal
The Subgraph Isomorphism problem is of considerable importance in comput...
research
∙
05/09/2021
Fast n-fold Boolean Convolution via Additive Combinatorics
We consider the problem of computing the Boolean convolution (with wrapa...
research
∙
01/19/2021
Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation
Computing the similarity of two point sets is a ubiquitous task in medic...
research
∙
10/27/2020
Impossibility Results for Grammar-Compressed Linear Algebra
To handle vast amounts of data, it is natural and popular to compress ve...
research
∙
10/18/2020
On Near-Linear-Time Algorithms for Dense Subset Sum
In the Subset Sum problem we are given a set of n positive integers X an...
research
∙
08/24/2020
Fast and Simple Modular Subset Sum
We revisit the Subset Sum problem over the finite cyclic group ℤ_m for s...
research
∙
08/17/2020
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation
Consider the natural question of how to measure the similarity of curves...
research
∙
03/16/2020
Scheduling Lower Bounds via AND Subset Sum
Given N instances (X_1,t_1),...,(X_N,t_N) of Subset Sum, the AND Subset ...
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
∙
12/28/2019
Approximating Subset Sum is equivalent to Min-Plus-Convolution
Approximating Subset Sum is a classic and fundamental problem in compute...
research
∙
07/25/2019
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max
Zwick's (1+ε)-approximation algorithm for the All Pairs Shortest Path (A...
research
∙
01/06/2019
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
The Fréchet distance provides a natural and intuitive measure for the po...
research
∙
10/25/2018
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability
The discrete Fréchet distance is a popular measure for comparing polygon...
research
∙
10/02/2018
Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS
We study sketching and streaming algorithms for the Longest Common Subse...
research
∙
10/01/2018
Polyline Simplification has Cubic Complexity
In the classic polyline simplification problem we want to replace a give...
research
∙
07/16/2018
A PTAS for ℓ_p-Low Rank Approximation
A number of recent works have studied algorithms for entrywise ℓ_p-low r...
research
∙
05/22/2018
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
The Strong Exponential Time Hypothesis and the OV-conjecture are two pop...
research
∙
05/18/2018
Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth
We show that the eccentricities, diameter, radius, and Wiener index of a...
research
∙
04/24/2018
Tighter Connections Between Formula-SAT and Shaving Logs
A noticeable fraction of Algorithms papers in the last few decades impro...
research
∙
03/31/2018
Fast Fencing
We consider very natural "fence enclosure" problems studied by Capoyleas...
research
∙
03/02/2018
Multivariate Fine-Grained Complexity of Longest Common Subsequence
We revisit the classic combinatorial pattern matching problem of finding...
research
∙
03/02/2018
Maximum Volume Subset Selection for Anchored Boxes
Let B be a set of n axis-parallel boxes in R^d such that each box has a ...
research
∙
03/02/2018
A fast implementation of near neighbors queries for Fréchet distance (GIS Cup)
This paper describes an implementation of fast near-neighbours queries (...
research
∙
03/02/2018
Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars
Tree-adjoining grammars are a generalization of context-free grammars th...
research
∙
03/02/2018
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve
Can we analyze data without decompressing it? As our data keeps growing,...
research
∙
10/30/2017