Homepage

Marvin Künnemann

Since April 2021: I have moved to ETH Zurich, Institute for Theoretical Studies

Since April 2022: I have moved to TU Kaiserslautern

I'm looking for PhD students! Feel free to contact me at kuennemanncs.uni-kl.de for more information.

Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Campus E1 4, Room 325
66123 Saarbrücken
Germany

Email: kuennemanncs.uni-kl.de Phone: +49 681 9325 1025

Research Interests

fine-grained complexity, hardness within P
algorithm engineering
probabilistic analysis of algorithms
smoothed analysis
randomized communication protocols

Publications

Refereed Conference Proceedings

M. Künnemann.
A tight (non-combinatorial) conditional lower bound for Klee's Measure Problem in 3D
Proc. 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022). To appear.
M. Künnemann, A. Nusser.
Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Algorithm via Offline Dynamic Rectangle Union.
Proc. 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022). (arXiv version)
K. Bringmann, S. Kisfaludi-Bak, M. Künnemann, A. Nusser and Z. Parsaeian.
Towards sub-quadratic diameter computation in geometric intersection graphs.
Proc. 38th International Symposium on Computational Geometry (SoCG 2022). (arXiv version)
K. Bringmann, S. Kisfaludi-Bak, M. Künnemann, D. Marx, A. Nusser.
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves.
Proc. 38th International Symposium on Computational Geometry (SoCG 2022). (arXiv version)
K. Bringmann, A. Cassis, N. Fischer, M. Künnemann.
A Structural Investigation of the Approximability of Polynomial-Time Problem.
Proc. 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). (arXiv version)
H. An, M. J. Gurumukhani, R. Impagliazzo, M. Jaber, M. Künnemann and M. P. Parga Nina.
The fine-grained complexity of multi-dimensional ordering properties
Proc. 16th International Symposium on Parameterized and Exact Computation (IPEC 2021).
K. Bringmann, A. Cassis, N. Fischer, M. Künnemann.
Fine-Grained Completeness for Optimization in P.
Proc. International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2021). (arXiv version)
A. Abboud, A. Backurs, K. Bringmann, M. Künnemann.
Impossibility Results for Grammar-Compressed Linear Algebra.
Proc. 33rd Advances in Neural Information Processing Systems (NeurIPS 2020). (arXiv version)
M. Künnemann, D. Marx.
Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction
Proc. 35th Computational Complexity Conference (CCC 2020). (arXiv version)
K. Bringmann, M. Künnemann, A. Nusser.
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation.
Proc. 28th Annual European Symposium on Algorithms (ESA 2020).
K. Bringmann, N. Fischer, M. Künnemann.
A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of ∃^k∀-Quantified First-Order Graph Properties
Proc. 34th Computational Complexity Conference (CCC 2019).
K. Bringmann, M. Künnemann, K. Węgrzycki.
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max
Proc. 51st ACM Symposium on the Theory of Computing (STOC 2019). (arXiv version)
K. Bringmann, M. Künnemann, A. Nusser.
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability.
Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019). (arXiv version)
K. Bringmann, M. Künnemann, P. Wellnitz.
Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts.
Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019).
K. Bringmann, M. Künnemann, A. Nusser.
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance.
Proc. 35rd International Symposium on Computational Geometry (SoCG 2019). (arXiv version)
M. Künnemann.
On Nondeterministic Derandomization of Freivalds’ Algorithm: Consequences, Avenues and Algorithmic Progress.
Proc. 26th Annual European Symposium on Algorithms (ESA 2018), 2018. (arXiv version)
K. Bringmann, M. Künnemann.
Multivariate Fine-grained Complexity of Longest Common Subsequence.
Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), 2018. (arXiv version)
A. Abboud, A. Backurs, K. Bringmann, M. Künnemann.
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve.
Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS 2017), 2017. (arXiv version)
M. Künnemann, R. Paturi, S. Schneider.
On the fine-grained complexity of one-dimensional dynamic programming.
Proc. 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), 2017. (arXiv version)
L. Duraj, M. Künnemann, A. Polak.
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence
Proc. 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), 2017. (arXiv version)
B. Doerr, M. Künnemann.
Improved protocols and hardness results for the two-player cryptogenography problem.
Proc. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Article 150, 2016. (arXiv version)
K. Bringmann, M. Künnemann.
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping.
Proc. 56th IEEE Symposium on Foundations of Computer Science (FOCS 2015), pages 79 - 97, 2015. (arXiv version)
M. Künnemann, B. Manthey.
Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic.
Proc. 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), Part I, pages 859-871, 2015.
N. Chen, M. Hoefer, M. Künnemann, C. Lin, P. Miao.
Secretary Markets with Local Information.
Proc. 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), Part II, pages 552-563, 2015.
K. Bringmann, M. Künnemann.
Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds.
Proc. 26th International Symposium on Algorithms and Computation (ISAAC 2015), pages 517-528, 2015.
B. Doerr, M. Künnemann.
Tight Analysis of Randomized Rumor Spreading in Complete Graphs.
Proc. 11th Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2014), pages 82-91, 2014.
R. Curticapean, M. Künnemann.
A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems.
Proc. 21st European Symposium on Algorithms (ESA 2013), pages 349-360, 2013.
B. Doerr, M. Künnemann.
How the (1 + λ) Evolutionary Algorithm optimizes linear functions.
Proc. 15th Genetic and Evolutionary Computation Conference (GECCO 2013), pages 1589-1596, 2013. ACM.
B. Doerr, M. Künnemann.
Royal Road Functions and the (1 + λ) Evolutionary Algorithm: Almost no speed-up from larger offspring populations.
Proc. 2013 IEEE Congress on Evolutionary Computation (CEC 2013), pages 424-431, 2013. IEEE.
B. Doerr, M. Künnemann, M. Wahlström.
Dependent randomized rounding: The bipartite case.
In Proc. Workshop on Algorithm Engineering and Experiments (ALENEX 2011), pages 96-107, 2011. SIAM.
B. Doerr, M. Künnemann, M. Wahlström.
Randomized rounding for routing and covering problems: Experiments and improvements. (arXiv)
Proc. the 9th International Symposium on Experimental and Efficient Algorithms 2010 (SEA 2010), pages 190-201, 2010. Springer Verlag.
B. Doerr, T. Friedrich, M. Künnemann, T. Sauerwald.
Quasirandom rumor spreading: An experimental analysis. (arXiv)
Proc. Workshop on Algorithm Engineering and Experiments (ALENEX 2009), pages 145-153, 2009. SIAM.

Journal Articles

K. Bringmann, M. Künnemann, A. Nusser.
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance.
Journal of Computational Geometry (2021). (arXiv version)
K. Bringmann, M. Künnemann, A. Nusser.
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability.
ACM Transactions on Algorithms (2021). (arXiv version)
B. Doerr, M. Künnemann.
Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem.
IEEE Transactions on Information Theory (2020)
M. Künnemann, D. Moeller, R. Paturi, S. Schneider
Subquadratic Algorithms for Succinct Stable Matching.
Algorithmica (2019). (arXiv version). Preliminary results by D. Moeller, R. Paturi and S. Schneider have been presented at CSR'16.
L. Duraj, M. Künnemann, A. Polak.
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence.
Algorithmica (2019). (arXiv version)
N. Chen, M. Hoefer, M. Künnemann, C. Lin, P. Miao.
Secretary markets with local information.
Distributed Computing (in press).
K. Bringmann, M. Künnemann.
Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds.
International Journal of Computational Geometry & Applications (2017).
R. Curticapean, M. Künnemann.
A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems.
Algorithmica (2015).
B. Doerr, M. Künnemann.
Optimizing linear functions with the evolutionary algorithm - Different asymptotic runtimes for different instances.
Theoretical Computer Science (2015).
B. Doerr, T. Friedrich, M. Künnemann, T. Sauerwald.
Quasirandom rumor spreading: An experimental analysis.
Journal of Experimental Algorithmics (JEA) 16 (2011), Article 3.3.

Teaching

basic lecture Algorithms and Data Structures (Summer 2022)
core lecture Algorithms and Data Structures (Winter 2020) (with Karl Bringmann)
advanced lecture Fine-grained Complexity Theory (Summer 2019) (with Karl Bringmann)
advanced lecture Randomized and Approximation Algorithms (Winter 2018) (with Antonios Antoniadis)
seminar Selected Topics in Fine-grained Complexity Theory (Summer 2018) (with Karl Bringmann)
advanced lecture Fine-grained Complexity Theory (Winter 2017) (with Karl Bringmann)
co-organizer of seminar Reading Group in Algorithms (Winter 2014, Summer 2015, Winter 2015, Summer 2016) (with Ruben Becker and Kurt Mehlhorn)
assistant for lecture Approximation Algorithms and Hardness of Approximation (Summer 2014) (taught by Anna Adamaszek and Andreas Wiese)
co-organizer of seminar Beyond Worst-Case Analysis (Winter 2013) (with Martin Hoefer)

Academic Service

PC member for STOC 2023, IPEC 2022, CCC 2022, ESA 2021, WG 2021, STOC 2020, IPEC 2020, GECCO Theory Track (2016, 2015, 2014)

co-organizer of 1st IGAFIT Workshop for Algorithms Postdocs in Europe (AlgPiE by IGAFIT 2019) (with D. Das, T. Kociumaka, and Y. Maus)
co-organizer of 19th Max Planck Advanced Course on the Foundations of Computer Science (ADFOCS 2018) (with K. Bringmann and C. Croitoru)
co-organizer of 14th Max Planck Advanced Course on the Foundations of Computer Science (ADFOCS 2013) (with M. Wahlström)

Recent Positions

April 2022 - present
Professor (W2), TU Kaiserslautern, Germany
April 2021 - March 2021
Advanced Fellow, Institute for Theoretical Studies, ETH Zurich, Switzerland
January 2021 - April 2021
Senior Researcher, Max Planck Insitute for Informatics, Saarbrücken, Germany
April 2017 - January 2021
Postdoctoral Scholar, Max Planck Insitute for Informatics, Saarbrücken, Germany
September 2016 - February 2017
Postdoctoral Scholar, University of California, San Diego
Mentors: Russell Impagliazzo, Ramamohan Paturi

Education

August 2012 - August 2016:
Ph. D. student in Computer Science at the Universität des Saarlandes, and the Max-Planck-Institut für Informatik, Saarbrücken, Germany
October 2010 - September 2012:
M.Sc. in Computer Science at the Universität des Saarlandes, Saarbrücken, Germany
Title of Master's Thesis: A Quantization Framework for Smoothed Analysis on Euclidean Optimization Problems (supervisor: Prof. Dr. Markus Bläser)
October 2008 - October 2010:
B.Sc. in Computer Science at the Universität des Saarlandes, Saarbrücken, Germany
Title of Bachelor's Thesis: Stochastic Scheduling With Exponential Processing Times: Characterizing Optimal Policies (supervisor: Prof. Dr. Kurt Mehlhorn)