Marvin Künnemann
Head of the Algorithms & Complexity Group
Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics
| marvin.kuennemann@kit.edu | |
| office | room 317, Computer Science building 50.34 |
| office hours | by appointment |
Publications
2024
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds.
Innovations in Theoretical Computer Science (ITCS) 2024
The Time Complexity of Fully Sparse Matrix Multiplication.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2024
The Effect of Sparsity on -Dominating Set and Related First-Order Graph Properties.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2024
2023
Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions d ≥ 4.
International Symposium on Computational Geometry (SoCG) 2023
Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality.
International Colloquium on Automata, Languages and Programming (ICALP) 2023
2022
The Fine-Grained Complexity of Multi-Dimensional Ordering Properties.
Algorithmica 2022
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves.
International Symposium on Computational Geometry (SoCG) 2022
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs.
International Symposium on Computational Geometry (SoCG) 2022
A tight (non-combinatorial) conditional lower bound for Klee's Measure Problem in 3D.
IEEE Annual Symposium on Foundations of Computer Science (FOCS) 2022
A Structural Investigation of the Approximability of Polynomial-Time Problems.
International Colloquium on Automata, Languages and Programming (ICALP) 2022
Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2022
2021
Walking the dog fast in practice: Algorithm engineering of the Fréchet distance.
Journal of Computational Geometry (JoCG) 2021
Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm.
ACM Transactions on Algorithms (TALG) 2021
Fine-Grained Completeness for Optimization in P.
International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX) 2021
The Fine-Grained Complexity of Multi-Dimensional Ordering Properties.
International Symposium on Parameterized and Exact Computation (IPEC) 2021
2020
Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem.
IEEE Transactions on Information Theory 2020
Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction.
Computational Complexity Conference (CCC) 2020
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance Under Translation.
European Symposium on Algorithms (ESA) 2020
Impossibility Results for Grammar-Compressed Linear Algebra.
Conference on Neural Information Processing Systems (NeurIPS) 2020
2019
Subquadratic Algorithms for Succinct Stable Matching.
Algorithmica 2019
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence.
Algorithmica 2019
Secretary markets with local information.
Distributed Computing 2019
A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties.
Computational Complexity Conference (CCC) 2019
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance.
International Symposium on Computational Geometry (SoCG) 2019
Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019
Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max.
Symposium on the Theory of Computing (STOC) 2019
2018
On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress.
European Symposium on Algorithms (ESA) 2018
Multivariate Fine-Grained Complexity of Longest Common Subsequence.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2018
2017
Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds.
International Journal of Computational Geometry and Applications 2017
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve.
IEEE Annual Symposium on Foundations of Computer Science (FOCS) 2017
On the Fine-Grained Complexity of One-Dimensional Dynamic Programming.
International Colloquium on Automata, Languages and Programming (ICALP) 2017
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence.
International Symposium on Parameterized and Exact Computation (IPEC) 2017
2016
Tight(er) bounds for similarity measures, smoothed approximation and broadcasting.
Saarland University, Germany 2016
Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem.
International Colloquium on Automata, Languages and Programming (ICALP) 2016
2015
A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems.
Algorithmica 2015
Optimizing linear functions with the (1+λ) evolutionary algorithm - Different asymptotic runtimes for different instances.
Theoretical Computer Science 2015
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping.
IEEE Annual Symposium on Foundations of Computer Science (FOCS) 2015
Secretary Markets with Local Information.
International Colloquium on Automata, Languages and Programming (ICALP) 2015
Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic.
International Colloquium on Automata, Languages and Programming (ICALP) 2015
Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds.
International Symposium on Algorithms and Computation (ISAAC) 2015
2014
Tight Analysis of Randomized Rumor Spreading in Complete Graphs.
Workshop on Analytic Algorithmics and Combinatorics (ANALCO) 2014
2013
Royal road functions and the (1 + λ) evolutionary algorithm: Almost no speed-up from larger offspring populations.
IEEE Congress on Evolutionary Computation (CEC) 2013
A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems.
European Symposium on Algorithms (ESA) 2013
How the (1+λ) evolutionary algorithm optimizes linear functions.
Annual Conference on Genetic and Evolutionary Computation (GECCO) 2013
2011
Quasirandom rumor spreading: An experimental analysis.
ACM Journal of Experimental Algorithmics (JEA) 2011
Dependent Randomized Rounding: The Bipartite Case.
Symposium on Algorithm Engineering and Experiments (ALENEX) 2011
2010
Randomized Rounding for Routing and Covering Problems: Experiments and Improvements.
Symposium on Experimental and Efficient Algorithms (SEA) 2010
2009
Quasirandom Rumor Spreading: An Experimental Analysis.
Symposium on Algorithm Engineering and Experiments (ALENEX) 2009