Marvin Künnemann

99 papers A* 20A 14B 6C 2Journal 52Unranked 4

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Approximating Pareto Sum via Bounded Monotone Min-Plus Convolution. CoRR Geri Gokaj, Marvin Künnemann, Sabine Storandt, Carina Truschel
2026	J	`jnl`	Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection. CoRR Bartlomiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin, Marvin Künnemann, Xiao Mao, Mirza Redzic
2026	J	`jnl`	Computing L CoRR Sebastian Angrick, Kevin Buchin, Geri Gokaj, Marvin Künnemann
2026	J	`jnl`	Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts. CoRR Nick Fischer, Marvin Künnemann, Mirza Redzic
2026	A	`conf`	Engineering Dominating Patterns: A Fine-grained Case Study. ALENEX Jonathan Dransfeld, Marvin Künnemann, Mirza Redzic, Marcus Wunderlich
2025	A	`conf`	(Multivariate) k-SUM as Barrier to Succinct Computation. ESA Geri Gokaj, Marvin Künnemann, Sabine Storandt, Carina Truschel
2025	J	`jnl`	Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic. CoRR Geri Gokaj, Marvin Künnemann
2025	A	`conf`	Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Linear Integer Arithmetic. ITCS Geri Gokaj, Marvin Künnemann
2025	J	`jnl`	Coverability in VASS Revisited: Improving Rackoff's Bounds to Obtain Conditional Optimality. J. ACM Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, Karol Wegrzycki
2025	J	`jnl`	Engineering Dominating Patterns: A Fine-grained Case Study. CoRR Jonathan Dransfeld, Marvin Künnemann, Mirza Redzic, Marcus Wunderlich
2025	J	`jnl`	Fine-Grained Classification Of Detecting Dominating Patterns. CoRR Jonathan Dransfeld, Marvin Künnemann, Mirza Redzic
2025	A	`conf`	Fine-Grained Classification of Detecting Dominating Patterns. ESA Jonathan Dransfeld, Marvin Künnemann, Mirza Redzic
2025	J	`jnl`	Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise. Algorithmica Marvin Künnemann, Bodo Manthey, Rianne Veenstra
2025	A*	`conf`	The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs. ICALP Nick Fischer, Marvin Künnemann, Mirza Redzic, Julian Stieß
2025	J	`jnl`	The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs. CoRR Nick Fischer, Marvin Künnemann, Mirza Redzic, Julian Stieß
2024	A	`conf`	Exploring the Approximability Landscape of 3SUM. ESA Karl Bringmann, Ahmed Ghazy, Marvin Künnemann
2024	B	`conf`	Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs. IPEC Marvin Künnemann, Mirza Redzic
2024	J	`jnl`	Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs. CoRR Marvin Künnemann, Mirza Redzic
2024	J	`jnl`	On Extremal Properties of k-CNF: Capturing Threshold Functions. CoRR Mohit Gurumukhani, Marvin Künnemann, Ramamohan Paturi
2024	A*	`conf`	The Effect of Sparsity on SODA Nick Fischer, Marvin Künnemann, Mirza Redzic
2024	A	`conf`	The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. ITCS Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen
2024	J	`jnl`	The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. TheoretiCS Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen
2024	A*	`conf`	The Time Complexity of Fully Sparse Matrix Multiplication. SODA Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann
2023	A*	`conf`	Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions d ≥ 4. SoCG Egor Gorbachev, Marvin Künnemann
2023	J	`jnl`	Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions d≥4. CoRR Egor Gorbachev, Marvin Künnemann
2023	A*	`conf`	Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality. ICALP Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, Karol Wegrzycki
2023	J	`jnl`	Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality. CoRR Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, Karol Wegrzycki
2023	J	`jnl`	Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise. CoRR Marvin Künnemann, Bodo Manthey, Rianne Veenstra
2023	J	`jnl`	The Effect of Sparsity on k-Dominating Set and Related First-Order Graph Properties. CoRR Nick Fischer, Marvin Künnemann, Mirza Redzic
2023	J	`jnl`	The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. CoRR Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen
2023	J	`jnl`	The Time Complexity of Fully Sparse Matrix Multiplication. CoRR Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann
2022	A*	`conf`	A Structural Investigation of the Approximability of Polynomial-Time Problems. ICALP Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann
2022	J	`jnl`	A Structural Investigation of the Approximability of Polynomial-Time Problems. CoRR Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann
2022	A*	`conf`	A tight (non-combinatorial) conditional lower bound for Klee's Measure Problem in 3D. FOCS Marvin Künnemann
2022	A*	`conf`	Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves. SoCG Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, André Nusser
2022	J	`jnl`	Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves. CoRR Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, André Nusser
2022	J	`jnl`	Dynamic time warping under translation: Approximation guided by space-filling curves. J. Comput. Geom. Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, André Nusser
2022	A*	`conf`	Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union. SODA Marvin Künnemann, André Nusser
2022	J	`jnl`	The Fine-Grained Complexity of Multi-Dimensional Ordering Properties. Algorithmica Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann, Maria Paula Parga Nina
2022	A*	`conf`	Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs. SoCG Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, Zahra Parsaeian
2022	J	`jnl`	Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs. CoRR Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, Zahra Parsaeian
2021	J	`jnl`	Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm. ACM Trans. Algorithms Karl Bringmann, Marvin Künnemann, André Nusser
2021	—	`conf`	Fine-Grained Completeness for Optimization in P. APPROX-RANDOM Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann
2021	J	`jnl`	Fine-Grained Completeness for Optimization in P. CoRR Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann
2021	J	`jnl`	Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union. CoRR Marvin Künnemann, André Nusser
2021	B	`conf`	The Fine-Grained Complexity of Multi-Dimensional Ordering Properties. IPEC Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann, Maria Paula Parga Nina
2021	J	`jnl`	Walking the dog fast in practice: Algorithm engineering of the Fréchet distance. J. Comput. Geom. Karl Bringmann, Marvin Künnemann, André Nusser
2020	A	`conf`	Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction. CCC Marvin Künnemann, Dániel Marx
2020	J	`jnl`	Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction. CoRR Marvin Künnemann, Dániel Marx
2020	A*	`conf`	Impossibility Results for Grammar-Compressed Linear Algebra. NeurIPS Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
2020	J	`jnl`	Impossibility Results for Grammar-Compressed Linear Algebra. CoRR Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
2020	J	`jnl`	Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem. IEEE Trans. Inf. Theory Benjamin Doerr, Marvin Künnemann
2020	A	`conf`	When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance Under Translation. ESA Karl Bringmann, Marvin Künnemann, André Nusser
2020	J	`jnl`	When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation. CoRR Karl Bringmann, Marvin Künnemann, André Nusser
2019	A	`conf`	A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties. CCC Karl Bringmann, Nick Fischer, Marvin Künnemann
2019	J	`jnl`	Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max. CoRR Karl Bringmann, Marvin Künnemann, Karol Wegrzycki
2019	A*	`conf`	Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max. STOC Karl Bringmann, Marvin Künnemann, Karol Wegrzycki
2019	A*	`conf`	Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts. SODA Karl Bringmann, Marvin Künnemann, Philip Wellnitz
2019	A*	`conf`	Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability. SODA Karl Bringmann, Marvin Künnemann, André Nusser
2019	J	`jnl`	Secretary markets with local information. Distributed Comput. Ning Chen, Martin Hoefer, Marvin Künnemann, Chengyu Lin, Peihan Miao
2019	J	`jnl`	Subquadratic Algorithms for Succinct Stable Matching. Algorithmica Marvin Künnemann, Daniel Moeller, Ramamohan Paturi, Stefan Schneider
2019	J	`jnl`	Tight Conditional Lower Bounds for Longest Common Increasing Subsequence. Algorithmica Lech Duraj, Marvin Künnemann, Adam Polak
2019	A*	`conf`	Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance. SoCG Karl Bringmann, Marvin Künnemann, André Nusser
2019	J	`jnl`	Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance. CoRR Karl Bringmann, Marvin Künnemann, André Nusser
2018	J	`jnl`	Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve. CoRR Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
2018	J	`jnl`	Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability. CoRR Karl Bringmann, Marvin Künnemann, André Nusser
2018	A*	`conf`	Multivariate Fine-Grained Complexity of Longest Common Subsequence. SODA Karl Bringmann, Marvin Künnemann
2018	J	`jnl`	Multivariate Fine-Grained Complexity of Longest Common Subsequence. CoRR Karl Bringmann, Marvin Künnemann
2018	A	`conf`	On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress. ESA Marvin Künnemann
2018	J	`jnl`	On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress. CoRR Marvin Künnemann
2017	A*	`conf`	Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. FOCS Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
2017	J	`jnl`	Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds. Int. J. Comput. Geom. Appl. Karl Bringmann, Marvin Künnemann
2017	A*	`conf`	On the Fine-Grained Complexity of One-Dimensional Dynamic Programming. ICALP Marvin Künnemann, Ramamohan Paturi, Stefan Schneider
2017	J	`jnl`	On the Fine-grained Complexity of One-Dimensional Dynamic Programming. CoRR Marvin Künnemann, Ramamohan Paturi, Stefan Schneider
2017	B	`conf`	Tight Conditional Lower Bounds for Longest Common Increasing Subsequence. IPEC Lech Duraj, Marvin Künnemann, Adam Polak
2017	J	`jnl`	Tight Conditional Lower Bounds for Longest Common Increasing Subsequence. CoRR Lech Duraj, Marvin Künnemann, Adam Polak
2016	A*	`conf`	Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem. ICALP Benjamin Doerr, Marvin Künnemann
2016	J	`jnl`	Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem. CoRR Benjamin Doerr, Marvin Künnemann
2016	—	`—`	Tight(er) bounds for similarity measures, smoothed approximation and broadcasting. Marvin Künnemann
2015	J	`jnl`	A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems. Algorithmica Radu Curticapean, Marvin Künnemann
2015	B	`conf`	Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds. ISAAC Karl Bringmann, Marvin Künnemann
2015	C	`conf`	On the Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP. CTW Marvin Künnemann, Bodo Manthey
2015	J	`jnl`	Optimizing linear functions with the (1+λ) evolutionary algorithm - Different asymptotic runtimes for different instances. Theor. Comput. Sci. Benjamin Doerr, Marvin Künnemann
2015	A*	`conf`	Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. FOCS Karl Bringmann, Marvin Künnemann
2015	J	`jnl`	Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. CoRR Karl Bringmann, Marvin Künnemann
2015	—	`conf`	Secretary Markets with Local Information. ICALP (2) Ning Chen, Martin Hoefer, Marvin Künnemann, Chengyu Lin, Peihan Miao
2015	—	`conf`	Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic. ICALP (1) Marvin Künnemann, Bodo Manthey
2014	J	`jnl`	Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds. CoRR Karl Bringmann, Marvin Künnemann
2014	—	`conf`	Tight Analysis of Randomized Rumor Spreading in Complete Graphs. ANALCO Benjamin Doerr, Marvin Künnemann
2013	A	`conf`	A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems. ESA Radu Curticapean, Marvin Künnemann
2013	C	`conf`	A quantization framework for smoothed analysis on Euclidean optimization problems. CTW Radu Curticapean, Marvin Künnemann
2013	A	`conf`	How the (1+λ) evolutionary algorithm optimizes linear functions. GECCO Benjamin Doerr, Marvin Künnemann
2013	B	`conf`	Royal road functions and the (1 + λ) evolutionary algorithm: Almost no speed-up from larger offspring populations. IEEE Congress on Evolutionary Computation Benjamin Doerr, Marvin Künnemann
2011	A	`conf`	Dependent Randomized Rounding: The Bipartite Case. ALENEX Benjamin Doerr, Marvin Künnemann, Magnus Wahlström
2011	J	`jnl`	Quasirandom rumor spreading: An experimental analysis. ACM J. Exp. Algorithmics Benjamin Doerr, Tobias Friedrich, Marvin Künnemann, Thomas Sauerwald
2010	J	`jnl`	Quasirandom Rumor Spreading: An Experimental Analysis CoRR Benjamin Doerr, Tobias Friedrich, Marvin Künnemann, Thomas Sauerwald
2010	J	`jnl`	Randomized Rounding for Routing and Covering Problems: Experiments and Improvements CoRR Benjamin Doerr, Marvin Künnemann, Magnus Wahlström
2010	B	`conf`	Randomized Rounding for Routing and Covering Problems: Experiments and Improvements. SEA Benjamin Doerr, Marvin Künnemann, Magnus Wahlström
2009	A	`conf`	Quasirandom Rumor Spreading: An Experimental Analysis. ALENEX Benjamin Doerr, Tobias Friedrich, Marvin Künnemann, Thomas Sauerwald