Homepage
Marvin Künnemann
Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Campus E1 4, Room 325
66123 Saarbrücken
Germany
Email:
Get my email address via email
Phone: +49 681 9325 1025
- fine-grained complexity, hardness within P
- algorithm engineering
- probabilistic analysis of algorithms
- smoothed analysis
- randomized communication protocols
Refereed Conference Proceedings
- 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). To appear. (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 Fré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
-
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.
- PC member for WG 2021, STOC 2020, IPEC 2020, GECCO Theory Track (2016, 2015, 2014)
- April 2017 - present
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
- 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)