| No. |
Title |
Author |
Year |
| 1 |
Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution |
Bringmann, Karl et al. |
2023 |
| 2 |
A Structural Investigation of the Approximability of Polynomial-Time Problems |
Bringmann, Karl et al. |
2022 |
| 3 |
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves |
Bringmann, Karl et al. |
2022 |
| 4 |
Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution |
Bringmann, Karl et al. |
2022 |
| 5 |
Improved Sublinear-Time Edit Distance for Preprocessed Strings |
Bringmann, Karl et al. |
2022 |
| 6 |
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs |
Bringmann, Karl et al. |
2022 |
| 7 |
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds |
Banyassady, Bahareh et al. |
2022 |
| 8 |
A Linear-Time n^{0.4}-Approximation for Longest Common Subsequence |
Bringmann, Karl et al. |
2021 |
| 9 |
Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal |
Bringmann, Karl et al. |
2021 |
| 10 |
Fast n-Fold Boolean Convolution via Additive Combinatorics |
Bringmann, Karl et al. |
2021 |
| 11 |
Fine-Grained Completeness for Optimization in P |
Bringmann, Karl et al. |
2021 |
| 12 |
Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation |
Bringmann, Karl et al. |
2021 |
| 13 |
Faster Minimization of Tardy Processing Time on a Single Machine |
Bringmann, Karl et al. |
2020 |
| 14 |
Scheduling Lower Bounds via AND Subset Sum |
Abboud, Amir et al. |
2020 |
| 15 |
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance Under Translation |
Bringmann, Karl et al. |
2020 |
| 16 |
A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties |
Bringmann, Karl et al. |
2019 |
| 17 |
Fine-Grained Complexity Theory (Tutorial) |
Bringmann, Karl |
2019 |
| 18 |
Multivariate Analysis of Orthogonal Range Searching and Graph Distances |
Bringmann, Karl et al. |
2019 |
| 19 |
On Geometric Set Cover for Orthants |
Bringmann, Karl et al. |
2019 |
| 20 |
Polyline Simplification has Cubic Complexity |
Bringmann, Karl et al. |
2019 |
| 21 |
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance |
Bringmann, Karl et al. |
2019 |
| 22 |
Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS |
Bringmann, Karl et al. |
2018 |
| 23 |
Tighter Connections Between Formula-SAT and Shaving Logs |
Abboud, Amir et al. |
2018 |
| 24 |
Brief Announcement: A Note on Hardness of Diameter Approximation |
Bringmann, Karl et al. |
2017 |
| 25 |
Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars |
Bringmann, Karl et al. |
2017 |
| 26 |
Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs |
Bringmann, Karl et al. |
2017 |
| 27 |
Maximum Volume Subset Selection for Anchored Boxes |
Bringmann, Karl et al. |
2017 |
| 28 |
On Algebraic Branching Programs of Small Width |
Bringmann, Karl et al. |
2017 |
| 29 |
Sampling Geometric Inhomogeneous Random Graphs in Linear Time |
Bringmann, Karl et al. |
2017 |
| 30 |
Hitting Set for Hypergraphs of Low VC-dimension |
Bringmann, Karl et al. |
2016 |
| 31 |
Approximability of the Discrete Fréchet Distance |
Bringmann, Karl et al. |
2015 |
| 32 |
Parameterized Complexity Dichotomy for Steiner Multicut |
Bringmann, Karl et al. |
2015 |
| 33 |
Balls into bins via local search: cover time and maximum load |
Bringmann, Karl et al. |
2014 |
