BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Marvin Künnemann

Marvin Künnemann appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputational ComplexityComputational GeometryComputer Science and Game TheoryCryptography and SecurityDiscrete MathematicsSocial and Information Networks

Catalog footprint

What is connected

12works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2022arXiv

A Structural Investigation of the Approximability of Polynomial-Time Problems

We initiate the systematic study of a recently introduced polynomial-time analogue of MaxSNP, which includes a large number of well-studied problems (including Nearest and Furthest Neighbor in the Hamming metric, Maximum Inner Product, optimization variants of $k$-XOR and Maximum $k$-Cover). Specifically, MaxSP$_k$ denotes the class of $O(m^k)$-time problems of the form $\max_{x_1,\dots, x_k} \#\{y:ϕ(x_1,\dots,x_k,y)\}$ where $ϕ$ is a quantifier-free first-order property and $m$ denotes the size of the relational structure. Assuming central hypotheses about clique detection in hypergraphs and MAX3SAT, we show that for any MaxSP$_k$ problem definable by a quantifier-free $m$-edge graph formula $ϕ$, the best possible approximation guarantee in faster-than-exhaustive-search time $O(m^{k-δ})$ falls into one of four categories: * optimizable to exactness in time $O(m^{k-δ})$, * an (inefficient) approximation scheme, i.e., a $(1+ε)$-approximation in time $O(m^{k-f(ε)})$, * a (fixed) constant-factor approximation in time $O(m^{k-δ})$, or * an $m^ε$-approximation in time $O(m^{k-f(ε)})$. We obtain an almost complete characterization of these regimes, for MaxSP$_k$ as well as for an analogously defined minimization class MinSP$_k$. As our main technical contribution, we rule out approximation schemes for a large class of problems admitting constant-factor approximations, under the Sparse MAX3SAT hypothesis posed by (Alman, Vassilevska Williams'20). As general trends for the problems we consider, we find: (1) Exact optimizability has a simple algebraic characterization, (2) only few maximization problems do not admit a constant-factor approximation; these do not even have a subpolynomial-factor approximation, and (3) constant-factor approximation of minimization problems is equivalent to deciding whether the optimum is equal to 0.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves

The Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves $π, σ$ in $\mathbb{R}^d$, it provides a robust, outlier-insensitive alternative to the Fréchet distance. However, like the Fréchet distance, the DTW distance is not invariant under translations. Can we efficiently optimize the DTW distance of $π$ and $σ$ under arbitrary translations, to compare the curves' shape irrespective of their absolute location? There are surprisingly few works in this direction, which may be due to its computational intricacy: For the Euclidean norm, this problem contains as a special case the geometric median problem, which provably admits no exact algebraic algorithm (that is, no algorithm using only addition, multiplication, and $k$-th roots). We thus investigate exact algorithms for non-Euclidean norms as well as approximation algorithms for the Euclidean norm: - For the $L_1$ norm in $\mathbb{R}^d$, we provide an $\mathcal{O}(n^{2(d+1)})$-time algorithm, i.e., an exact polynomial-time algorithm for constant $d$. Here and below, $n$ bounds the curves' complexities. - For the Euclidean norm in $\mathbb{R}^2$, we show that a simple problem-specific insight leads to a $(1+\varepsilon)$-approximation in time $\mathcal{O}(n^3/\varepsilon^2)$. We then show how to obtain a subcubic $\widetilde{\mathcal{O}}(n^{2.5}/\varepsilon^2)$ time algorithm with significant new ideas; this time comes close to the well-known quadratic time barrier for computing DTW for fixed translations. Technically, the algorithm is obtained by speeding up repeated DTW distance estimations using a dynamic data structure for maintaining shortest paths in weighted planar digraphs. Crucially, we show how to traverse a candidate set of translations using space-filling curves in a way that incurs only few updates to the data structure.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs

We initiate the study of diameter computation in geometric intersection graphs from the fine-grained complexity perspective. A geometric intersection graph is a graph whose vertices correspond to some shapes in $d$-dimensional Euclidean space, such as balls, segments, or hypercubes, and whose edges correspond to pairs of intersecting shapes. The diameter of a graph is the largest distance realized by a pair of vertices in the graph. Computing the diameter in near-quadratic time is possible in several classes of intersection graphs [Chan and Skrepetos 2019], but it is not at all clear if these algorithms are optimal, especially since in the related class of planar graphs the diameter can be computed in $\widetilde{\mathcal{O}}(n^{5/3})$ time [Cabello 2019, Gawrychowski et al. 2021]. In this work we (conditionally) rule out sub-quadratic algorithms in several classes of intersection graphs, i.e., algorithms of running time $\mathcal{O}(n^{2-δ})$ for some $δ>0$. In particular, there are no sub-quadratic algorithms already for fat objects in small dimensions: unit balls in $\mathbb{R}^3$ or congruent equilateral triangles in $\mathbb{R}^2$. For unit segments and congruent equilateral triangles, we can even rule out strong sub-quadratic approximations already in $\mathbb{R}^2$. It seems that the hardness of approximation may also depend on dimensionality: for axis-parallel unit hypercubes in~$\mathbb{R}^{12}$, distinguishing between diameter 2 and 3 needs quadratic time (ruling out $(3/2-\varepsilon)$- approximations), whereas for axis-parallel unit squares, we give an algorithm that distinguishes between diameter $2$ and $3$ in near-linear time. Note that many of our lower bounds match the best known algorithms up to sub-polynomial factors.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction

To study the question under which circumstances small solutions can be found faster than by exhaustive search (and by how much), we study the fine-grained complexity of Boolean constraint satisfaction with size constraint exactly $k$. More precisely, we aim to determine, for any finite constraint family, the optimal running time $f(k)n^{g(k)}$ required to find satisfying assignments that set precisely $k$ of the $n$ variables to $1$. Under central hardness assumptions on detecting cliques in graphs and 3-uniform hypergraphs, we give an almost tight characterization of $g(k)$ into four regimes: (1) Brute force is essentially best-possible, i.e., $g(k) = (1\pm o(1))k$, (2) the best algorithms are as fast as current $k$-clique algorithms, i.e., $g(k)=(ω/3\pm o(1))k$, (3) the exponent has sublinear dependence on $k$ with $g(k) \in [Ω(\sqrt[3]{k}), O(\sqrt{k})]$, or (4) the problem is fixed-parameter tractable, i.e., $g(k) = O(1)$. This yields a more fine-grained perspective than a previous FPT/W[1]-hardness dichotomy (Marx, Computational Complexity 2005). Our most interesting technical contribution is a $f(k)n^{4\sqrt{k}}$-time algorithm for SubsetSum with precedence constraints parameterized by the target $k$ -- particularly the approach, based on generalizing a bound on the Frobenius coin problem to a setting with precedence constraints, might be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation

Consider the natural question of how to measure the similarity of curves in the plane by a quantity that is invariant under translations of the curves. Such a measure is justified whenever we aim to quantify the similarity of the curves' shapes rather than their positioning in the plane, e.g., to compare the similarity of handwritten characters. Perhaps the most natural such notion is the (discrete) Fréchet distance under translation. Unfortunately, the algorithmic literature on this problem yields a very pessimistic view: On polygonal curves with $n$ vertices, the fastest algorithm runs in time $O(n^{4.667})$ and cannot be improved below $n^{4-o(1)}$ unless the Strong Exponential Time Hypothesis fails. Can we still obtain an implementation that is efficient on realistic datasets? Spurred by the surprising performance of recent implementations for the Fréchet distance, we perform algorithm engineering for the Fréchet distance under translation. Our solution combines fast, but inexact tools from continuous optimization (specifically, branch-and-bound algorithms for global Lipschitz optimization) with exact, but expensive algorithms from computational geometry (specifically, problem-specific algorithms based on an arrangement construction). We combine these two ingredients to obtain an exact decision algorithm for the Fréchet distance under translation. For the related task of computing the distance value up to a desired precision, we engineer and compare different methods. On a benchmark set involving handwritten characters and route trajectories, our implementation answers a typical query for either task in the range of a few milliseconds up to a second on standard desktop hardware. We believe that our implementation will enable the use of the Fréchet distance under translation in applications, whereas previous approaches would have been computationally infeasible.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Tight Conditional Lower Bounds for Longest Common Increasing Subsequence

We consider the canonical generalization of the well-studied Longest Increasing Subsequence problem to multiple sequences, called $k$-LCIS: Given $k$ integer sequences $X_1,\dots,X_k$ of length at most $n$, the task is to determine the length of the longest common subsequence of $X_1,\dots,X_k$ that is also strictly increasing. Especially for the case of $k=2$ (called LCIS for short), several algorithms have been proposed that require quadratic time in the worst case. Assuming the Strong Exponential Time Hypothesis (SETH), we prove a tight lower bound, specifically, that no algorithm solves LCIS in (strongly) subquadratic time. Interestingly, the proof makes no use of normalization tricks common to hardness proofs for similar problems such as LCS. We further strengthen this lower bound (1) to rule out $O((nL)^{1-\varepsilon})$ time algorithms for LCIS, where $L$ denotes the solution size, (2) to rule out $O(n^{k-\varepsilon})$ time algorithms for $k$-LCIS, and (3) to follow already from weaker variants of SETH. We obtain the same conditional lower bounds for the related Longest Common Weakly Increasing Subsequence problem.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

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

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 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. To ease the design of new protocols, we prove an equivalent formulation of the cryptogenography problem as solitaire vector splitting game. Via an automated game tree search, we find good strategies for this game. We then translate the splits that occurred in this strategy into inequalities relating position values and use an LP solver to find an optimal solution for these inequalities. This gives slightly better game values, but more importantly, it gives a more compact representation of the protocol and a way to easily verify the claimed quality of the protocol. These improved bounds, as well as the large sizes and depths of the improved protocols we find, suggests that finding good protocols for the cryptogenography problem as well as understanding their structure are harder than what the simple problem formulation suggests.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Subquadratic Algorithms for Succinct Stable Matching

We consider the stable matching problem when the preference lists are not given explicitly but are represented in a succinct way and ask whether the problem becomes computationally easier and investigate other implications. We give subquadratic algorithms for finding a stable matching in special cases of natural succinct representations of the problem, the $d$-attribute, $d$-list, geometric, and single-peaked models. We also present algorithms for verifying a stable matching in the same models. We further show that for $d = ω(\log n)$ both finding and verifying a stable matching in the $d$-attribute and $d$-dimensional geometric models requires quadratic time assuming the Strong Exponential Time Hypothesis. This suggests that these succinct models are not significantly simpler computationally than the general case for sufficiently large $d$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping

Classic similarity measures of strings are longest common subsequence and Levenshtein distance (i.e., the classic edit distance). A classic similarity measure of curves is dynamic time warping. These measures can be computed by simple $O(n^2)$ dynamic programming algorithms, and despite much effort no algorithms with significantly better running time are known. We prove that, even restricted to binary strings or one-dimensional curves, respectively, these measures do not have strongly subquadratic time algorithms, i.e., no algorithms with running time $O(n^{2-\varepsilon})$ for any $\varepsilon > 0$, unless the Strong Exponential Time Hypothesis fails. We generalize the result to edit distance for arbitrary fixed costs of the four operations (deletion in one of the two strings, matching, substitution), by identifying trivial cases that can be solved in constant time, and proving quadratic-time hardness on binary strings for all other cost choices. This improves and generalizes the known hardness result for Levenshtein distance [Backurs, Indyk STOC'15] by the restriction to binary strings and the generalization to arbitrary costs, and adds important problems to a recent line of research showing conditional lower bounds for a growing number of quadratic time problems. As our main technical contribution, we introduce a framework for proving quadratic-time hardness of similarity measures. To apply the framework it suffices to construct a single gadget, which encapsulates all the expressive power necessary to emulate a reduction from satisfiability. Finally, we prove quadratic-time hardness for longest palindromic subsequence and longest tandem subsequence via reductions from longest common subsequence, showing that conditional lower bounds based on the Strong Exponential Time Hypothesis also apply to string problems that are not necessarily similarity measures.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds

The Fréchet distance is a well-studied and very popular measure of similarity of two curves. The best known algorithms have quadratic time complexity, which has recently been shown to be optimal assuming the Strong Exponential Time Hypothesis (SETH) [Bringmann FOCS'14]. To overcome the worst-case quadratic time barrier, restricted classes of curves have been studied that attempt to capture realistic input curves. The most popular such class are c-packed curves, for which the Fréchet distance has a $(1+ε)$-approximation in time $\tilde{O}(c n /ε)$ [Driemel et al. DCG'12]. In dimension $d \ge 5$ this cannot be improved to $O((cn/\sqrtε)^{1-δ})$ for any $δ> 0$ unless SETH fails [Bringmann FOCS'14]. In this paper, exploiting properties that prevent stronger lower bounds, we present an improved algorithm with runtime $\tilde{O}(cn/\sqrtε)$. This is optimal in high dimensions apart from lower order factors unless SETH fails. Our main new ingredients are as follows: For filling the classical free-space diagram we project short subcurves onto a line, which yields one-dimensional separated curves with roughly the same pairwise distances between vertices. Then we tackle this special case in near-linear time by carefully extending a greedy algorithm for the Fréchet distance of one-dimensional separated curves.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Quasirandom Rumor Spreading: An Experimental Analysis

We empirically analyze two versions of the well-known "randomized rumor spreading" protocol to disseminate a piece of information in networks. In the classical model, in each round each informed node informs a random neighbor. In the recently proposed quasirandom variant, each node has a (cyclic) list of its neighbors. Once informed, it starts at a random position of the list, but from then on informs its neighbors in the order of the list. While for sparse random graphs a better performance of the quasirandom model could be proven, all other results show that, independent of the structure of the lists, the same asymptotic performance guarantees hold as for the classical model. In this work, we compare the two models experimentally. This not only shows that the quasirandom model generally is faster, but also that the runtime is more concentrated around the mean. This is surprising given that much fewer random bits are used in the quasirandom process. These advantages are also observed in a lossy communication model, where each transmission does not reach its target with a certain probability, and in an asynchronous model, where nodes send at random times drawn from an exponential distribution. We also show that typically the particular structure of the lists has little influence on the efficiency.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Randomized Rounding for Routing and Covering Problems: Experiments and Improvements

Following previous theoretical work by Srinivasan (FOCS 2001) and the first author (STACS 2006) and a first experimental evaluation on random instances (ALENEX 2009), we investigate how the recently developed different approaches to generate randomized roundings satisfying disjoint cardinality constraints behave when used in two classical algorithmic problems, namely low-congestion routing in networks and max-coverage problems in hypergraphs. We generally find that all randomized rounding algorithms work well, much better than what is guaranteed by existing theoretical work. The derandomized versions produce again significantly better rounding errors, with running times still negligible compared to the one for solving the corresponding LP. It thus seems worth preferring them over the randomized variants. The data created in these experiments lets us propose and investigate the following new ideas. For the low-congestion routing problems, we suggest to solve a second LP, which yields the same congestion, but aims at producing a solution that is easier to round. Experiments show that this reduces the rounding errors considerably, both in combination with randomized and derandomized rounding. For the max-coverage instances, we generally observe that the greedy heuristics also performs very good. We develop a strengthened method of derandomized rounding, and a simple greedy/rounding hybrid approach using greedy and LP-based rounding elements, and observe that both these improvements yield again better solutions than both earlier approaches on their own. For unit disk max-domination, we also develop a PTAS. Contrary to all other algorithms investigated, it performs not much better in experiments than in theory; thus, unless extremely good solutions are to be obtained with huge computational resources, greedy, LP-based rounding or hybrid approaches are preferable.

0 citations0 reviewsNo code linkedOpen access