MKMarvin Künnemann

Marvin Künnemann

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Marvin Künnemann has a total of 38 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection

    by Bartłomiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin, Marvin Künnemann, Xiao Mao, Mirza Redžić

  • Open Access

    Coverability in VASS Revisited: Improving Rackoff’s Bounds to Obtain Conditional Optimality

    by Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, Karol Węgrzycki

    Seminal results establish that the coverability problem for Vector Addition Systems with States (VASS) is in EXPSPACE (Rackoff, ’78) and is EXPSPACE -hard already under unary encodings (Lipton, ’76). More precisely, Rosier and Yen later utilise Rackoff’s bounding technique to show that if coverability holds then there is a run of length at most \(n^{2^{\mathcal {O}(d \log (d))}}\) , where d is the dimension and n is the size of the given unary VASS. Earlier, Lipton showed that there exist instances of coverability in d -dimensional unary VASS that are only witnessed by runs of length at least \(n^{2^{\Omega (d)}}\) . Our first result closes this gap. We improve the upper bound by removing the twice-exponentiated \(\log (d)\) factor, thus matching Lipton’s lower bound. This closes the corresponding gap for the exact space required to decide coverability. This also yields a deterministic \(n^{2^{\mathcal {O}(d)}}\) -time algorithm for coverability. Our second result is a matching lower bound, that there does not exist a deterministic \(n^{2^{o(d)}}\) -time algorithm, conditioned upon the exponential time hypothesis. When analysing coverability, a standard proof technique is to consider VASS with bounded counters. Bounded VASS make for an interesting and popular model due to strong connections with timed automata. Withal, we study a natural setting where the counter bound is linear in the size of the VASS. Here the trivial exhaustive search algorithm runs in \(\mathcal {O}(n^{d+1})\) time. We give evidence to this being near-optimal. We prove that in dimension one this trivial algorithm is conditionally optimal, by showing that \(n^{2-o(1)}\) time is required under the k -cycle hypothesis. In general, for any fixed dimension d ≥ 4, we show that \(n^{d-2-o(1)}\) time is required under the 3-uniform hyperclique hypothesis.


  • Open Access

    Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise

    by Marvin Künnemann, Bodo Manthey, Rianne Veenstra

    The 2-opt heuristic is a very simple local search heuristic for the traveling salesperson problem. In practice it usually converges quickly to solutions within a few percentages of optimality. In contrast to this, its running-time is exponential and its approximation performance is poor in the worst case. Englert, Röglin, and Vöcking (Algorithmica, 2014) provided a smoothed analysis in the so-called one-step model in order to explain the performance of 2-opt on d-dimensional Euclidean instances, both in terms of running-time and in terms of approximation ratio. However, translating their results to the classical model of smoothed analysis, where points are perturbed by Gaussian distributions with standard deviation sigma, yields only weak bounds. We prove bounds that are polynomial in n and 1/sigma for the smoothed running-time with Gaussian perturbations. In addition, our analysis for Euclidean distances is much simpler than the existing smoothed analysis. Furthermore, we prove a smoothed approximation ratio of O(log(1/sigma)). This bound is almost tight, as we also provide a lower bound of Omega(log n/ loglog n) for sigma = O(1/sqrt n). Our main technical novelty here is that, different from existing smoothed analyses, we do not separately analyze objective values of the global and local optimum on all inputs (which only allows for a bound of O(1/sigma)), but simultaneously bound them on the same input.

  • The Fine-Grained Complexity of Multi-Dimensional Ordering Properties

    by Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann, Maria Paula Parga Nina


  • Open Access

    Impossibility Results for Grammar-Compressed Linear Algebra

    by Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann

    To handle vast amounts of data, it is natural and popular to compress vectors and matrices. When we compress a vector from size $N$ down to size $n \ll N$, it certainly makes it easier to store and transmit efficiently, but does it also make it easier to process? In this paper we consider lossless compression schemes, and ask if we can run our computations on the compressed data as efficiently as if the original data was that small. That is, if an operation has time complexity $T(\rm{inputsize})$, can we perform it on the compressed representation in time $T(n)$ rather than $T(N)$? We consider the most basic linear algebra operations: inner product, matrix-vector multiplication, and matrix multiplication. In particular, given two compressed vectors, can we compute their inner product in time $O(n)$? Or perhaps we must decompress first and then multiply, spending $\Omega(N)$ time? The answer depends on the compression scheme. While for simple ones such as Run-Length-Encoding (RLE) the inner product can be done in $O(n)$ time, we prove that this is impossible for compressions from a richer class: essentially $n^2$ or even larger runtimes are needed in the worst case (under complexity assumptions). This is the class of grammar-compressions containing most popular methods such as the Lempel-Ziv family. These schemes are more compressing than the simple RLE, but alas, we prove that performing computations on them is much harder.

  • Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem

    by Benjamin Doerr, Marvin Kunnemann

    The cryptogenography problem, introduced by Brody, Jakobsen, Scheder, and Winkler (ITCS 2014), is to collaboratively leak a piece of information known to only one member of a group (i) without revealing who was the origin of this information and (ii) without any private communication, neither during the process nor before. Despite several deep structural results, even the smallest case of leaking one bit of information present at one of two players is not well understood. Brody et al. gave a 2-round protocol enabling the two players to succeed with probability 1/3 and showed the hardness result that no protocol can give a success probability of more than 3/8. In this work, we show that neither bound is tight. Our new hardness result, obtained by a different application of the concavity method used also in the previous work, states that a success probability of better than 0.3672 is not possible. Using both theoretical and numerical approaches, we improve the lower bound to 0.3384, that is, give a protocol leading to this success probability. Unfortunately, already our smallest protocol beating the previous 1/3 success probability takes up 16 rounds of communication. The protocol leading to the bound of 0.3384 even in a compact representation consists of 18248 game states. These numbers suggest that the task of finding good protocols for the cryptogenography problem as well as understanding their structure is harder than what the simple problem formulation suggests.


  • Open Access

    Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max

    by Karl Bringmann, Marvin Künnemann, Karol Węgrzycki

    Zwick's $(1+\varepsilon)$-approximation algorithm for the All Pairs Shortest Path (APSP) problem runs in time $\widetilde{O}(\frac{n^\omega}{\varepsilon} \log{W})$, where $\omega \le 2.373$ is the exponent of matrix multiplication and $W$ denotes the largest weight. This can be used to approximate several graph characteristics including the diameter, radius, median, minimum-weight triangle, and minimum-weight cycle in the same time bound. Since Zwick's algorithm uses the scaling technique, it has a factor $\log W$ in the running time. In this paper, we study whether APSP and related problems admit approximation schemes avoiding the scaling technique. That is, the number of arithmetic operations should be independent of $W$; this is called strongly polynomial. Our main results are as follows. - We design approximation schemes in strongly polynomial time $O(\frac{n^\omega}{\varepsilon} \text{polylog}(\frac{n}{\varepsilon}))$ for APSP on undirected graphs as well as for the graph characteristics diameter, radius, median, minimum-weight triangle, and minimum-weight cycle on directed or undirected graphs. - For APSP on directed graphs we design an approximation scheme in strongly polynomial time $O(n^{\frac{\omega + 3}{2}} \varepsilon^{-1} \text{polylog}(\frac{n}{\varepsilon}))$. This is significantly faster than the best exact algorithm. - We explain why our approximation scheme for APSP on directed graphs has a worse exponent than $\omega$: Any improvement over our exponent $\frac{\omega + 3}{2}$ would improve the best known algorithm for Min-Max Product In fact, we prove that approximating directed APSP and exactly computing the Min-Max Product are equivalent.

  • Subquadratic Algorithms for Succinct Stable Matching

    by Marvin Künnemann, Daniel Moeller, Ramamohan Paturi, Stefan Schneider


  • Open Access

    Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance

    by Karl Bringmann, Marvin Künnemann, André Nusser

    The Fr\'echet distance provides a natural and intuitive measure for the popular task of computing the similarity of two (polygonal) curves. While a simple algorithm computes it in near-quadratic time, a strongly subquadratic algorithm cannot exist unless the Strong Exponential Time Hypothesis fails. Still, fast practical implementations of the Fr\'echet distance, in particular for realistic input curves, are highly desirable. This has even lead to a designated competition, the ACM SIGSPATIAL GIS Cup 2017: Here, the challenge was to implement a near-neighbor data structure under the Fr\'echet distance. The bottleneck of the top three implementations turned out to be precisely the decision procedure for the Fr\'echet distance. In this work, we present a fast, certifying implementation for deciding the Fr\'echet distance, in order to (1) complement its pessimistic worst-case hardness by an empirical analysis on realistic input data and to (2) improve the state of the art for the GIS Cup challenge. We experimentally evaluate our implementation on a large benchmark consisting of several data sets (including handwritten characters and GPS trajectories). Compared to the winning implementation of the GIS Cup, we obtain running time improvements of up to more than two orders of magnitude for the decision procedure and of up to a factor of 30 for queries to the near-neighbor data structure.


  • Open Access

    Tight Conditional Lower Bounds for Longest Common Increasing Subsequence

    by Lech Duraj, Marvin Künnemann, Adam Polak