Marvin Künnemann

Bodo Manthey

Rianne Veenstra

Algorithmica, November, 2025

Coverability in VASS Revisited: Improving Rackoff's Bounds to Obtain Conditional Optimality.

[BibT_eX]

[DOI]

J. ACM, October, 2025

Engineering Dominating Patterns: A Fine-grained Case Study.

[BibT_eX]

[DOI]

CoRR, October, 2025

Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic.

[BibT_eX]

[DOI]

Geri Gokaj

CoRR, February, 2025

Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Linear Integer Arithmetic.

[BibT_eX]

[DOI]

Geri Gokaj

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs.

[BibT_eX]

[DOI]

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

(Multivariate) k-SUM as Barrier to Succinct Computation.

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual European Symposium on Algorithms, 2025

Fine-Grained Classification of Detecting Dominating Patterns.

[BibT_eX]

[DOI]

Jonathan Dransfeld

Proceedings of the 33rd Annual European Symposium on Algorithms, 2025

2024

On Extremal Properties of k-CNF: Capturing Threshold Functions.

[BibT_eX]

[DOI]

Mohit Gurumukhani

Ramamohan Paturi

CoRR, 2024

The Effect of Sparsity on <i>k</i>-Dominating Set and Related First-Order Graph Properties.

[BibT_eX]

[DOI]

Nick Fischer

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

The Time Complexity of Fully Sparse Matrix Multiplication.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs.

[BibT_eX]

[DOI]

Proceedings of the 19th International Symposium on Parameterized and Exact Computation, 2024

The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Exploring the Approximability Landscape of 3SUM.

[BibT_eX]

[DOI]

Ahmed Ghazy

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

The Effect of Sparsity on k-Dominating Set and Related First-Order Graph Properties.

[BibT_eX]

[DOI]

Nick Fischer

CoRR, 2023

Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions d ≥ 4.

[BibT_eX]

[DOI]

Egor Gorbachev

Proceedings of the 39th International Symposium on Computational Geometry, 2023

2022

Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

A Structural Investigation of the Approximability of Polynomial-Time Problems.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

A tight (non-combinatorial) conditional lower bound for Klee's Measure Problem in 3D.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Computational Geometry, 2022

Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

The Fine-Grained Complexity of Multi-Dimensional Ordering Properties.

[BibT_eX]

[DOI]

Maria Paula Parga Nina

Proceedings of the 16th International Symposium on Parameterized and Exact Computation, 2021

Fine-Grained Completeness for Optimization in P.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

Impossibility Results for Grammar-Compressed Linear Algebra.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance Under Translation.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction.

[BibT_eX]

[DOI]

Dániel Marx

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Subquadratic Algorithms for Succinct Stable Matching.

[BibT_eX]

[DOI]

Algorithmica, 2019

Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max.

[BibT_eX]

[DOI]

Karol Wegrzycki

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts.

[BibT_eX]

[DOI]

Philip Wellnitz

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Computational Geometry, 2019

A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties.

[BibT_eX]

[DOI]

Nick Fischer

Proceedings of the 34th Computational Complexity Conference, 2019

2018

Multivariate Fine-Grained Complexity of Longest Common Subsequence.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Tight Conditional Lower Bounds for Longest Common Increasing Subsequence.

[BibT_eX]

[DOI]

Lech Duraj

Adam Polak

Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

On the Fine-Grained Complexity of One-Dimensional Dynamic Programming.

[BibT_eX]

[DOI]

Ramamohan Paturi

Stefan Schneider

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Tight(er) bounds for similarity measures, smoothed approximation and broadcasting.

[BibT_eX]

[DOI]

PhD thesis, 2016

Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Optimizing linear functions with the (1+λ) evolutionary algorithm - Different asymptotic runtimes for different instances.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic.

[BibT_eX]

[DOI]

Bodo Manthey

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Secretary Markets with Local Information.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

On the Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP.

[BibT_eX]

Bodo Manthey

Proceedings of the 13th Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2015

2014

Tight Analysis of Randomized Rumor Spreading in Complete Graphs.

[BibT_eX]

[DOI]

Proceedings of the 2014 Proceedings of the Eleventh Workshop on Analytic Algorithmics and Combinatorics, 2014

2013

How the (1+λ) evolutionary algorithm optimizes linear functions.

[BibT_eX]

[DOI]

Proceedings of the Genetic and Evolutionary Computation Conference, 2013

A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems.

[BibT_eX]

[DOI]

Radu Curticapean

Proceedings of the Algorithms - ESA 2013, 2013

Royal road functions and the (1 + λ) evolutionary algorithm: Almost no speed-up from larger offspring populations.

[BibT_eX]

[DOI]

Proceedings of the IEEE Congress on Evolutionary Computation, 2013

2011

Dependent Randomized Rounding: The Bipartite Case.

[BibT_eX]

[DOI]

Magnus Wahlström

Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments, 2011

2010

Randomized Rounding for Routing and Covering Problems: Experiments and Improvements.

[BibT_eX]

[DOI]