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/01/2023
Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise
The 2-opt heuristic is a very simple local search heuristic for the trav...
research
∙
05/02/2023
Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality
Seminal results establish that the coverability problem for Vector Addit...
research
∙
03/15/2023
Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions d≥ 4
Klee's measure problem (computing the volume of the union of n axis-para...
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
∙
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
∙
11/03/2021
Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union
We revisit the classical problem of determining the largest copy of a si...
research
∙
07/04/2021
Fine-Grained Completeness for Optimization in P
We initiate the study of fine-grained completeness theorems for exact an...
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
∙
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
∙
05/23/2020
Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction
To study the question under which circumstances small solutions can be f...
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
∙
06/24/2018
On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress
Motivated by studying the power of randomness, certifying algorithms and...
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
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
∙
09/28/2017