
Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution
Computing the convolution A⋆ B of two lengthn vectors A,B is an ubiquit...
read it

Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal
The Subgraph Isomorphism problem is of considerable importance in comput...
read it

Fast nfold Boolean Convolution via Additive Combinatorics
We consider the problem of computing the Boolean convolution (with wrapa...
read it

Translating Hausdorff is Hard: FineGrained Lower Bounds for Hausdorff Distance Under Translation
Computing the similarity of two point sets is a ubiquitous task in medic...
read it

Impossibility Results for GrammarCompressed Linear Algebra
To handle vast amounts of data, it is natural and popular to compress ve...
read it

On NearLinearTime Algorithms for Dense Subset Sum
In the Subset Sum problem we are given a set of n positive integers X an...
read it

Fast and Simple Modular Subset Sum
We revisit the Subset Sum problem over the finite cyclic group ℤ_m for s...
read it

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...
read it

Scheduling Lower Bounds via AND Subset Sum
Given N instances (X_1,t_1),...,(X_N,t_N) of Subset Sum, the AND Subset ...
read it

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...
read it

Approximating Subset Sum is equivalent to MinPlusConvolution
Approximating Subset Sum is a classic and fundamental problem in compute...
read it

Approximating APSP without Scaling: Equivalence of Approximate MinPlus and Exact MinMax
Zwick's (1+ε)approximation algorithm for the All Pairs Shortest Path (A...
read it

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...
read it

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...
read it

Sketching, Streaming, and FineGrained Complexity of (Weighted) LCS
We study sketching and streaming algorithms for the Longest Common Subse...
read it

Polyline Simplification has Cubic Complexity
In the classic polyline simplification problem we want to replace a give...
read it

A PTAS for ℓ_pLow Rank Approximation
A number of recent works have studied algorithms for entrywise ℓ_plow r...
read it

More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
The Strong Exponential Time Hypothesis and the OVconjecture are two pop...
read it

Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth
We show that the eccentricities, diameter, radius, and Wiener index of a...
read it

Tighter Connections Between FormulaSAT and Shaving Logs
A noticeable fraction of Algorithms papers in the last few decades impro...
read it

Fast Fencing
We consider very natural "fence enclosure" problems studied by Capoyleas...
read it

Multivariate FineGrained Complexity of Longest Common Subsequence
We revisit the classic combinatorial pattern matching problem of finding...
read it

Maximum Volume Subset Selection for Anchored Boxes
Let B be a set of n axisparallel boxes in R^d such that each box has a ...
read it

A fast implementation of near neighbors queries for Fréchet distance (GIS Cup)
This paper describes an implementation of fast nearneighbours queries (...
read it

CliqueBased Lower Bounds for Parsing TreeAdjoining Grammars
Treeadjoining grammars are a generalization of contextfree grammars th...
read it

FineGrained Complexity of Analyzing Compressed Data: Quantifying Improvements over DecompressAndSolve
Can we analyze data without decompressing it? As our data keeps growing,...
read it

Approximation Algorithms for ℓ_0Low Rank Approximation
We study the ℓ_0Low Rank Approximation Problem, where the goal is, give...
read it
Karl Bringmann
is this you? claim profile