default search action
Marvin Künnemann
Person information
- affiliation: Karlsruhe Institute of Technology, USA
- affiliation (former): TU Kaiserslautern, Germany
- affiliation (former): Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
- affiliation (former): Saarland University, Saarbrücken, Germany
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [c39]Karl Bringmann, Ahmed Ghazy, Marvin Künnemann:
Exploring the Approximability Landscape of 3SUM. ESA 2024: 34:1-34:15 - [c38]Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen:
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. ITCS 2024: 22:1-22:25 - [c37]Marvin Künnemann, Mirza Redzic:
Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs. IPEC 2024: 9:1-9:18 - [c36]Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann:
The Time Complexity of Fully Sparse Matrix Multiplication. SODA 2024: 4670-4703 - [c35]Nick Fischer, Marvin Künnemann, Mirza Redzic:
The Effect of Sparsity on k-Dominating Set and Related First-Order Graph Properties. SODA 2024: 4704-4727 - [i30]Marvin Künnemann, Mirza Redzic:
Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs. CoRR abs/2409.08037 (2024) - 2023
- [c34]Egor Gorbachev
, Marvin Künnemann:
Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions d ≥ 4. SoCG 2023: 36:1-36:14 - [c33]Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, Karol Wegrzycki
Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality. ICALP 2023: 131:1-131:20 - [i29]Egor Gorbachev, Marvin Künnemann:
Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions d≥4. CoRR abs/2303.08612 (2023) - [i28]Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, Karol Wegrzycki:
Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality. CoRR abs/2305.01581 (2023) - [i27]Marvin Künnemann, Bodo Manthey, Rianne Veenstra:
Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise. CoRR abs/2308.00306 (2023) - [i26]Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann:
The Time Complexity of Fully Sparse Matrix Multiplication. CoRR abs/2309.06317 (2023) - [i25]Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen:
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. CoRR abs/2311.10204 (2023) - [i24]Nick Fischer, Marvin Künnemann, Mirza Redzic:
The Effect of Sparsity on k-Dominating Set and Related First-Order Graph Properties. CoRR abs/2312.14593 (2023) - 2022
- [j12]Haozhe An, Mohit Gurumukhani, Russell Impagliazzo
The Fine-Grained Complexity of Multi-Dimensional Ordering Properties. Algorithmica 84(11): 3156-3191 (2022) - [j11]Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, André Nusser:
Dynamic time warping under translation: Approximation guided by space-filling curves. J. Comput. Geom. 14(2): 83-107 (2022) - [c32]Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, André Nusser:
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves. SoCG 2022: 20:1-20:17 - [c31]Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, Zahra Parsaeian:
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs. SoCG 2022: 21:1-21:16 - [c30]Marvin Künnemann:
A tight (non-combinatorial) conditional lower bound for Klee's Measure Problem in 3D. FOCS 2022: 555-566 - [c29]Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann:
A Structural Investigation of the Approximability of Polynomial-Time Problems. ICALP 2022: 30:1-30:20 - [c28]Marvin Künnemann, André Nusser:
Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union. SODA 2022: 3181-3201 - [i23]Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, Zahra Parsaeian:
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs. CoRR abs/2203.03663 (2022) - [i22]Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, André Nusser:
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves. CoRR abs/2203.07898 (2022) - [i21]Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann:
A Structural Investigation of the Approximability of Polynomial-Time Problems. CoRR abs/2204.11681 (2022) - 2021
- [j10]Karl Bringmann, Marvin Künnemann, André Nusser:
Walking the dog fast in practice: Algorithm engineering of the Fréchet distance. J. Comput. Geom. 12(1): 70-108 (2021) - [j9]Karl Bringmann, Marvin Künnemann, André Nusser:
Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm. ACM Trans. Algorithms 17(3): 25:1-25:42 (2021) - [c27]Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann:
Fine-Grained Completeness for Optimization in P. APPROX-RANDOM 2021: 9:1-9:22 - [c26]Haozhe An, Mohit Gurumukhani, Russell Impagliazzo
The Fine-Grained Complexity of Multi-Dimensional Ordering Properties. IPEC 2021: 3:1-3:15 - [i20]Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann:
Fine-Grained Completeness for Optimization in P. CoRR abs/2107.01721 (2021) - [i19]Marvin Künnemann, André Nusser:
Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union. CoRR abs/2111.02544 (2021) - 2020
- [j8]Benjamin Doerr
Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem. IEEE Trans. Inf. Theory 66(9): 5729-5741 (2020) - [c25]Marvin Künnemann, Dániel Marx:
Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction. CCC 2020: 27:1-27:28 - [c24]Karl Bringmann, Marvin Künnemann, André Nusser:
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance Under Translation. ESA 2020: 25:1-25:17 - [c23]Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Impossibility Results for Grammar-Compressed Linear Algebra. NeurIPS 2020 - [i18]Marvin Künnemann, Dániel Marx:
Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction. CoRR abs/2005.11541 (2020) - [i17]Karl Bringmann, Marvin Künnemann, André Nusser:
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation. CoRR abs/2008.07510 (2020) - [i16]Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Impossibility Results for Grammar-Compressed Linear Algebra. CoRR abs/2010.14181 (2020)
2010 – 2019
- 2019
- [j7]Marvin Künnemann, Daniel Moeller, Ramamohan Paturi, Stefan Schneider
Subquadratic Algorithms for Succinct Stable Matching. Algorithmica 81(7): 2991-3024 (2019) - [j6]Lech Duraj
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence. Algorithmica 81(10): 3968-3992 (2019) - [j5]Ning Chen, Martin Hoefer, Marvin Künnemann, Chengyu Lin
Secretary markets with local information. Distributed Comput. 32(5): 361-378 (2019) - [c22]Karl Bringmann, Nick Fischer, Marvin Künnemann:
A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties. CCC 2019: 31:1-31:27 - [c21]Karl Bringmann, Marvin Künnemann, André Nusser:
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance. SoCG 2019: 17:1-17:21 - [c20]Karl Bringmann, Marvin Künnemann, Philip Wellnitz
Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts. SODA 2019: 1126-1145 - [c19]Karl Bringmann, Marvin Künnemann, André Nusser:
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability. SODA 2019: 2902-2921 - [c18]Karl Bringmann, Marvin Künnemann, Karol Wegrzycki
Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max. STOC 2019: 943-954 - [i15]Karl Bringmann, Marvin Künnemann, André Nusser:
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance. CoRR abs/1901.01504 (2019) - [i14]Karl Bringmann, Marvin Künnemann, Karol Wegrzycki:
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max. CoRR abs/1907.11078 (2019) - 2018
- [c17]Marvin Künnemann:
On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress. ESA 2018: 56:1-56:16 - [c16]Karl Bringmann, Marvin Künnemann:
Multivariate Fine-Grained Complexity of Longest Common Subsequence. SODA 2018: 1216-1235 - [i13]Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve. CoRR abs/1803.00796 (2018) - [i12]Karl Bringmann, Marvin Künnemann:
Multivariate Fine-Grained Complexity of Longest Common Subsequence. CoRR abs/1803.00938 (2018) - [i11]Marvin Künnemann:
On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress. CoRR abs/1806.09189 (2018) - [i10]Karl Bringmann, Marvin Künnemann, André Nusser:
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability. CoRR abs/1810.10982 (2018) - 2017
- [j4]Karl Bringmann, Marvin Künnemann:
Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds. Int. J. Comput. Geom. Appl. 27(1-2): 85-120 (2017) - [c15]Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. FOCS 2017: 192-203 - [c14]Marvin Künnemann, Ramamohan Paturi, Stefan Schneider:
On the Fine-Grained Complexity of One-Dimensional Dynamic Programming. ICALP 2017: 21:1-21:15 - [c13]Lech Duraj
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence. IPEC 2017: 15:1-15:13 - [i9]Marvin Künnemann, Ramamohan Paturi, Stefan Schneider:
On the Fine-grained Complexity of One-Dimensional Dynamic Programming. CoRR abs/1703.00941 (2017) - [i8]Lech Duraj, Marvin Künnemann, Adam Polak:
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence. CoRR abs/1709.10075 (2017) - 2016
- [b1]Marvin Künnemann:
Tight(er) bounds for similarity measures, smoothed approximation and broadcasting. Saarland University, Germany, 2016, pp. i-xi, 1-223 - [c12]Benjamin Doerr, Marvin Künnemann:
Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem. ICALP 2016: 150:1-150:13 - [i7]Benjamin Doerr, Marvin Künnemann:
Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem. CoRR abs/1603.06113 (2016) - 2015
- [j3]Radu Curticapean, Marvin Künnemann:
A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems. Algorithmica 73(3): 483-510 (2015) - [j2]Benjamin Doerr, Marvin Künnemann:
Optimizing linear functions with the (1+λ) evolutionary algorithm - Different asymptotic runtimes for different instances. Theor. Comput. Sci. 561: 3-23 (2015) - [c11]Karl Bringmann, Marvin Künnemann:
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. FOCS 2015: 79-97 - [c10]Ning Chen, Martin Hoefer, Marvin Künnemann, Chengyu Lin
Secretary Markets with Local Information. ICALP (2) 2015: 552-563 - [c9]Marvin Künnemann, Bodo Manthey:
Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic. ICALP (1) 2015: 859-871 - [c8]Karl Bringmann, Marvin Künnemann:
Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds. ISAAC 2015: 517-528 - [i6]Marvin Künnemann, Bodo Manthey:
On the Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP. CTW 2015: 1-4 - [i5]Karl Bringmann, Marvin Künnemann:
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. CoRR abs/1502.01063 (2015) - 2014
- [c7]Benjamin Doerr, Marvin Künnemann:
Tight Analysis of Randomized Rumor Spreading in Complete Graphs. ANALCO 2014: 82-91 - [i4]Karl Bringmann, Marvin Künnemann:
Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds. CoRR abs/1408.1340 (2014) - 2013
- [c6]Benjamin Doerr, Marvin Künnemann:
Royal road functions and the (1 + λ) evolutionary algorithm: Almost no speed-up from larger offspring populations. IEEE Congress on Evolutionary Computation 2013: 424-431 - [c5]Radu Curticapean, Marvin Künnemann:
A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems. ESA 2013: 349-360 - [c4]Benjamin Doerr, Marvin Künnemann:
How the (1+λ) evolutionary algorithm optimizes linear functions. GECCO 2013: 1589-1596 - [i3]Radu Curticapean, Marvin Künnemann:
A quantization framework for smoothed analysis on Euclidean optimization problems. CTW 2013: 71-74 - 2011
- [j1]Benjamin Doerr, Tobias Friedrich, Marvin Künnemann, Thomas Sauerwald:
Quasirandom rumor spreading: An experimental analysis. ACM J. Exp. Algorithmics 16 (2011) - [c3]Benjamin Doerr, Marvin Künnemann, Magnus Wahlström
Dependent Randomized Rounding: The Bipartite Case. ALENEX 2011: 96-106 - 2010
- [c2]Benjamin Doerr, Marvin Künnemann, Magnus Wahlström:
Randomized Rounding for Routing and Covering Problems: Experiments and Improvements. SEA 2010: 190-201 - [i2]Benjamin Doerr, Marvin Künnemann, Magnus Wahlström:
Randomized Rounding for Routing and Covering Problems: Experiments and Improvements. CoRR abs/1007.0372 (2010) - [i1]Benjamin Doerr, Tobias Friedrich, Marvin Künnemann, Thomas Sauerwald:
Quasirandom Rumor Spreading: An Experimental Analysis. CoRR abs/1012.5357 (2010)
2000 – 2009
- 2009
- [c1]Benjamin Doerr, Tobias Friedrich, Marvin Künnemann, Thomas Sauerwald:
Quasirandom Rumor Spreading: An Experimental Analysis. ALENEX 2009: 145-153
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-08 02:22 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: