Last Year

%0 Report %A Akrami, Hannaneh %A Ray Chaudhury, Bhaskar %A Mehlhorn, Kurt %A Shahkarami, Golnoosh %A Vermande, Quentin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Nash Social Welfare for 2-value Instances : %G eng %U http://hdl.handle.net/21.11116/0000-0008-DB45-4 %U https://arxiv.org/abs/2106.14816 %D 2021 %X We study the problem of allocating a set of indivisible goods among agents with 2-value additive valuations. Our goal is to find an allocation with maximum Nash social welfare, i.e., the geometric mean of the valuations of the agents. We give a polynomial-time algorithm to find a Nash social welfare maximizing allocation when the valuation functions are integrally 2-valued, i.e., each agent has a value either $1$ or $p$ for each good, for some positive integer $p$. We then extend our algorithm to find a better approximation factor for general 2-value instances. %K Computer Science, Computer Science and Game Theory, cs.GT

%0 Report %A Amanatidis, Georgios %A Kleer, Pieter %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Approximate Sampling and Counting of Graphs with Near-Regular Degree Intervals : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B839-8 %U https://arxiv.org/abs/2110.09068 %D 2021 %X The approximate uniform sampling of graphs with a given degree sequence is a well-known, extensively studied problem in theoretical computer science and has significant applications, e.g., in the analysis of social networks. In this work we study an extension of the problem, where degree intervals are specified rather than a single degree sequence. We are interested in sampling and counting graphs whose degree sequences satisfy the degree interval constraints. A natural scenario where this problem arises is in hypothesis testing on social networks that are only partially observed. In this work, we provide the first fully polynomial almost uniform sampler (FPAUS) as well as the first fully polynomial randomized approximation scheme (FPRAS) for sampling and counting, respectively, graphs with near-regular degree intervals, in which every node $i$ has a degree from an interval not too far away from a given $d \in \N$. In order to design our FPAUS, we rely on various state-of-the-art tools from Markov chain theory and combinatorics. In particular, we provide the first non-trivial algorithmic application of a breakthrough result of Liebenau and Wormald (2017) regarding an asymptotic formula for the number of graphs with a given near-regular degree sequence. Furthermore, we also make use of the recent breakthrough of Anari et al. (2019) on sampling a base of a matroid under a strongly log-concave probability distribution. As a more direct approach, we also study a natural Markov chain recently introduced by Rechner, Strowick and M\"uller-Hannemann (2018), based on three simple local operations: Switches, hinge flips, and additions/deletions of a single edge. We obtain the first theoretical results for this Markov chain by showing it is rapidly mixing for the case of near-regular degree intervals of size at most one. %K Computer Science, Discrete Mathematics, cs.DM,Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Combinatorics, math.CO

%0 Conference Proceedings %A Anagnostides, Ioannis %A Gouleakis, Themis %A Marashian, Ali %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Robust Learning under Strong Noise via SQs : %G eng %U http://hdl.handle.net/21.11116/0000-0007-DBCD-C %D 2021 %B 24th International Conference on Artificial Intelligence and Statistics %Z date of event: 2021-04-13 - 2021-04-15 %C Virtual Conference %B Proceedings of the Twenty Fourth International Conference on Artificial Intelligence and Statistics %I PMLR %B Proceedings of the Machine Learning Research

%0 Report %A Anagnostides, Ioannis %A Gouleakis, Themis %A Lenzen, Christoph %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Accelerated Distributed Laplacian Solvers via Shortcuts : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B83F-2 %U https://arxiv.org/abs/2109.05151 %D 2021 %X In this work we refine the analysis of the distributed Laplacian solver recently established by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS '21), via the Ghaffari-Haeupler framework (SODA '16) of low-congestion shortcuts. Specifically, if $\epsilon > 0$ represents the error of the solver, we derive two main results. First, for any $n$-node graph $G$ with hop-diameter $D$ and treewidth bounded by $k$, we show the existence of a Laplacian solver with round complexity $O(n^{o(1)}kD \log(1/\epsilon))$ in the CONGEST model. For graphs with bounded treewidth this circumvents the notorious $\Omega(\sqrt{n})$ lower bound for "global" problems in general graphs. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with very limited global power in the form of the recently introduced node-capacitated clique. In this model, we show the existence of a Laplacian solver with round complexity $O(n^{o(1)} \log(1/\epsilon))$. The unifying thread of these results is an application of accelerated distributed algorithms for a congested variant of the standard part-wise aggregation problem that we introduce. This primitive constitutes the primary building block for simulating "local" operations on low-congestion minors, and we believe that this framework could be more generally applicable. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC

%0 Report %A Antoniadis, Antonios %A Hoeksma, Ruben %A Kisfaludi-Bak, Sándor %A Schewior, Kevin %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Online Search for a Hyperplane in High-Dimensional Euclidean Space : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B814-1 %U https://arxiv.org/abs/2109.04340 %D 2021 %X We consider the online search problem in which a server starting at the origin of a $d$-dimensional Euclidean space has to find an arbitrary hyperplane. The best-possible competitive ratio and the length of the shortest curve from which each point on the $d$-dimensional unit sphere can be seen are within a constant factor of each other. We show that this length is in $\Omega(d)\cap O(d^{3/2})$. %K Computer Science, Computational Geometry, cs.CG,Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Axiotis, Kyriakos %A Backurs, Arturs %A Bringmann, Karl %A Jin, Ce %A Nakos, Vasileios %A Tzamos, Christos %A Wu, Hongxun %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Fast and Simple Modular Subset Sum : %G eng %U http://hdl.handle.net/21.11116/0000-0007-56CF-0 %R 10.1137/1.9781611976496.6 %D 2021 %B SIAM Symposium on Simplicity in Algorithms %Z date of event: 2021-01-11 - 2021-01-12 %C Alexandria, VA, USA (Virtual Conference) %B Symposium on Simplicity in Algorithms %E King, Valerie; Viet Le, Hung %P 57 - 67 %I SIAM %@ 978-1-61197-649-6

%0 Journal Article %A Becker, Ruben %A Forster, Sebastian %A Karrenbauer, Andreas %A Lenzen, Christoph %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E543-A %R 10.1137/19M1286955 %7 2021 %D 2021 %J SIAM Journal on Computing %V 50 %N 3 %& 815 %P 815 - 856 %I SIAM %C Philadelphia %@ false

%0 Journal Article %A Berendsohn, Benjamin Aram %A Kozma, László %A Marx, Dániel %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Finding and Counting Permutations via CSPs : %G eng %U http://hdl.handle.net/21.11116/0000-0008-3403-A %R 10.1007/s00453-021-00812-z %7 2021 %D 2021 %J Algorithmica %V 148 %I Springer %C New York, NY %@ false

%0 Conference Proceedings %A Bringmann, Karl %A Wellnitz, Philip %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T On Near-Linear-Time Algorithms for Dense Subset Sum : %G eng %U http://hdl.handle.net/21.11116/0000-0007-8C7E-F %R 10.1137/1.9781611976465.107 %D 2021 %B 32nd Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2021-01-10 - 2021-01-13 %C Alexandria, VA, USA (Virtual Conference) %B Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms %E Marx, Dániel %P 1777 - 1796 %I SIAM %@ 978-1-61197-646-5

%0 Conference Proceedings %A Bringmann, Karl %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Fine-Grained Perspective on Approximating Subset Sum and Partition : %G eng %U http://hdl.handle.net/21.11116/0000-0007-90DD-D %R 10.1137/1.9781611976465.108 %D 2021 %B 32nd Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2021-01-10 - 2021-01-13 %C Alexandria, VA, USA (Virtual Conference) %B Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms %E Marx, Dániel %P 1797 - 1815 %I SIAM %@ 978-1-61197-646-5

%0 Conference Proceedings %A Bringmann, Karl %A Nusser, André %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation : %G eng %U http://hdl.handle.net/21.11116/0000-0008-DB6F-6 %R 10.4230/LIPIcs.SoCG.2021.18 %U urn:nbn:de:0030-drops-138177 %D 2021 %B 37th International Symposium on Computational Geometry %Z date of event: 2021-06-07 - 2021-06-11 %C Buffalo, NY, USA (Virtual Conference) %B 37th International Symposium on Computational Geometry %E Buchin, Kevin; Colin de Verdière, Érich %P 1 - 17 %Z sequence number: 18 %I Schloss Dagstuhl %@ 978-3-95977-184-9 %B Leibniz International Proceedings in Informatics %N 189 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2021/13817/https://creativecommons.org/licenses/by/4.0/legalcode

%0 Conference Proceedings %A Bringmann, Karl %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fast n-Fold Boolean Convolution via Additive Combinatorics : %G eng %U http://hdl.handle.net/21.11116/0000-0008-DB8E-2 %R 10.4230/LIPIcs.ICALP.2021.41 %U urn:nbn:de:0030-drops-141108 %D 2021 %B 48th International Colloquium on Automata, Languages, and Programming %Z date of event: 2021-07-12 - 2020-07-16 %C Glasgow, UK (Virtual Conference) %B 48th International Colloquium on Automata, Languages, and Programming %E Bansal, Nikhil; Merelli, Emanuela; Worrell, James %P 1 - 17 %Z sequence number: 41 %I Schloss Dagstuhl %@ 978-3-95977-195-5 %B Leibniz International Proceedings in Informatics %N 198 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2021/14110/pdf/LIPIcs-ICALP-2021-41.pdfhttps://creativecommons.org/licenses/by/4.0/legalcode

%0 Conference Proceedings %A Bringmann, Karl %A Das, Debarati %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A Linear-Time n0.4-Approximation for Longest Common Subsequence : %G eng %U http://hdl.handle.net/21.11116/0000-0008-DB7B-8 %R 10.4230/LIPIcs.ICALP.2021.39 %U urn:nbn:de:0030-drops-141082 %D 2021 %B 48th International Colloquium on Automata, Languages, and Programming %Z date of event: 2021-07-12 - 2020-07-16 %C Glasgow, UK (Virtual Conference) %B 48th International Colloquium on Automata, Languages, and Programming %E Bansal, Nikhil; Merelli, Emanuela; Worrell, James %P 1 - 20 %Z sequence number: 39 %I Schloss Dagstuhl %@ 978-3-95977-195-5 %B Leibniz International Proceedings in Informatics %N 198 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2021/14108/https://creativecommons.org/licenses/by/4.0/legalcode

%0 Conference Proceedings %A Bringmann, Karl %A Slusallek, Jasper %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal : %G eng %U http://hdl.handle.net/21.11116/0000-0008-DB85-B %R 10.4230/LIPIcs.ICALP.2021.40 %U urn:nbn:de:0030-drops-141095 %D 2021 %B 48th International Colloquium on Automata, Languages, and Programming %Z date of event: 2021-07-12 - 2020-07-16 %C Glasgow, UK (Virtual Conference) %B 48th International Colloquium on Automata, Languages, and Programming %E Bansal, Nikhil; Merelli, Emanuela; Worrell, James %P 1 - 16 %Z sequence number: 40 %I Schloss Dagstuhl %@ 978-3-95977-195-5 %B Leibniz International Proceedings in Informatics %N 198 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2021/14109/https://creativecommons.org/licenses/by/4.0/legalcode

%0 Report %A Bringmann, Karl %A Nusser, André %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E242-E %U https://arxiv.org/abs/2101.07696 %D 2021 %X Computing the similarity of two point sets is a ubiquitous task in medical imaging, geometric shape comparison, trajectory analysis, and many more settings. Arguably the most basic distance measure for this task is the Hausdorff distance, which assigns to each point from one set the closest point in the other set and then evaluates the maximum distance of any assigned pair. A drawback is that this distance measure is not translational invariant, that is, comparing two objects just according to their shape while disregarding their position in space is impossible. Fortunately, there is a canonical translational invariant version, the Hausdorff distance under translation, which minimizes the Hausdorff distance over all translations of one of the point sets. For point sets of size $n$ and $m$, the Hausdorff distance under translation can be computed in time $\tilde O(nm)$ for the $L_1$ and $L_\infty$ norm [Chew, Kedem SWAT'92] and $\tilde O(nm (n+m))$ for the $L_2$ norm [Huttenlocher, Kedem, Sharir DCG'93]. As these bounds have not been improved for over 25 years, in this paper we approach the Hausdorff distance under translation from the perspective of fine-grained complexity theory. We show (i) a matching lower bound of $(nm)^{1-o(1)}$ for $L_1$ and $L_\infty$ assuming the Orthogonal Vectors Hypothesis and (ii) a matching lower bound of $n^{2-o(1)}$ for $L_2$ in the imbalanced case of $m = O(1)$ assuming the 3SUM Hypothesis. %K Computer Science, Computational Geometry, cs.CG,Computer Science, Computational Complexity, cs.CC

%0 Conference Proceedings %A Bringmann, Karl %A Fischer, Nick %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E23F-3 %R 10.1145/3406325.3451090 %D 2021 %B 53rd Annual ACM SIGACT Symposium on Theory of Computing %Z date of event: 2021-06-21 - 2021-06-25 %C Virtual, Italy %B STOC '21 %E Khuller, Samir; Vassilevska Williams, Virginia %P 1711 - 1724 %I ACM %@ 9781450380539

%0 Report %A Bringmann, Karl %A Fischer, Nick %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E263-9 %U https://arxiv.org/abs/2105.05984 %D 2021 %X Computing the convolution $A\star B$ of two length-$n$ vectors $A,B$ is an ubiquitous computational primitive. Applications range from string problems to Knapsack-type problems, and from 3SUM to All-Pairs Shortest Paths. These applications often come in the form of nonnegative convolution, where the entries of $A,B$ are nonnegative integers. The classical algorithm to compute $A\star B$ uses the Fast Fourier Transform and runs in time $O(n\log n)$. However, often $A$ and $B$ satisfy sparsity conditions, and hence one could hope for significant improvements. The ideal goal is an $O(k\log k)$-time algorithm, where $k$ is the number of non-zero elements in the output, i.e., the size of the support of $A\star B$. This problem is referred to as sparse nonnegative convolution, and has received considerable attention in the literature; the fastest algorithms to date run in time $O(k\log^2 n)$. The main result of this paper is the first $O(k\log k)$-time algorithm for sparse nonnegative convolution. Our algorithm is randomized and assumes that the length $n$ and the largest entry of $A$ and $B$ are subexponential in $k$. Surprisingly, we can phrase our algorithm as a reduction from the sparse case to the dense case of nonnegative convolution, showing that, under some mild assumptions, sparse nonnegative convolution is equivalent to dense nonnegative convolution for constant-error randomized algorithms. Specifically, if $D(n)$ is the time to convolve two nonnegative length-$n$ vectors with success probability $2/3$, and $S(k)$ is the time to convolve two nonnegative vectors with output size $k$ with success probability $2/3$, then $S(k)=O(D(k)+k(\log\log k)^2)$. Our approach uses a variety of new techniques in combination with some old machinery from linear sketching and structured linear algebra, as well as new insights on linear hashing, the most classical hash function. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC

%0 Report %A Bringmann, Karl %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fast n-fold Boolean Convolution via Additive Combinatorics : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E25B-3 %U https://arxiv.org/abs/2105.03968 %D 2021 %X We consider the problem of computing the Boolean convolution (with wraparound) of $n$~vectors of dimension $m$, or, equivalently, the problem of computing the sumset $A_1+A_2+\ldots+A_n$ for $A_1,\ldots,A_n \subseteq \mathbb{Z}_m$. Boolean convolution formalizes the frequent task of combining two subproblems, where the whole problem has a solution of size $k$ if for some $i$ the first subproblem has a solution of size~$i$ and the second subproblem has a solution of size $k-i$. Our problem formalizes a natural generalization, namely combining solutions of $n$ subproblems subject to a modular constraint. This simultaneously generalises Modular Subset Sum and Boolean Convolution (Sumset Computation). Although nearly optimal algorithms are known for special cases of this problem, not even tiny improvements are known for the general case. We almost resolve the computational complexity of this problem, shaving essentially a factor of $n$ from the running time of previous algorithms. Specifically, we present a \emph{deterministic} algorithm running in \emph{almost} linear time with respect to the input plus output size $k$. We also present a \emph{Las Vegas} algorithm running in \emph{nearly} linear expected time with respect to the input plus output size $k$. Previously, no deterministic or randomized $o(nk)$ algorithm was known. At the heart of our approach lies a careful usage of Kneser's theorem from Additive Combinatorics, and a new deterministic almost linear output-sensitive algorithm for non-negative sparse convolution. In total, our work builds a solid toolbox that could be of independent interest. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Report %A Bringmann, Karl %A Cohen-Addad, Vincent %A Das, Debarati %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T A Linear-Time n0.4-Approximation for Longest Common Subsequence : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E267-5 %U https://arxiv.org/abs/2106.08195 %D 2021 %X We consider the classic problem of computing the Longest Common Subsequence (LCS) of two strings of length $n$. While a simple quadratic algorithm has been known for the problem for more than 40 years, no faster algorithm has been found despite an extensive effort. The lack of progress on the problem has recently been explained by Abboud, Backurs, and Vassilevska Williams [FOCS'15] and Bringmann and K\"unnemann [FOCS'15] who proved that there is no subquadratic algorithm unless the Strong Exponential Time Hypothesis fails. This has led the community to look for subquadratic approximation algorithms for the problem. Yet, unlike the edit distance problem for which a constant-factor approximation in almost-linear time is known, very little progress has been made on LCS, making it a notoriously difficult problem also in the realm of approximation. For the general setting, only a naive $O(n^{\varepsilon/2})$-approximation algorithm with running time $\tilde{O}(n^{2-\varepsilon})$ has been known, for any constant $0 < \varepsilon \le 1$. Recently, a breakthrough result by Hajiaghayi, Seddighin, Seddighin, and Sun [SODA'19] provided a linear-time algorithm that yields a $O(n^{0.497956})$-approximation in expectation; improving upon the naive $O(\sqrt{n})$-approximation for the first time. In this paper, we provide an algorithm that in time $O(n^{2-\varepsilon})$ computes an $\tilde{O}(n^{2\varepsilon/5})$-approximation with high probability, for any $0 < \varepsilon \le 1$. Our result (1) gives an $\tilde{O}(n^{0.4})$-approximation in linear time, improving upon the bound of Hajiaghayi, Seddighin, Seddighin, and Sun, (2) provides an algorithm whose approximation scales with any subquadratic running time $O(n^{2-\varepsilon})$, improving upon the naive bound of $O(n^{\varepsilon/2})$ for any $\varepsilon$, and (3) instead of only in expectation, succeeds with high probability. %K Computer Science, Data Structures and Algorithms, cs.DS,

%0 Report %A Bringmann, Karl %A Slusallek, Jasper %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E25F-F %U https://arxiv.org/abs/2105.05062 %D 2021 %X The Subgraph Isomorphism problem is of considerable importance in computer science. We examine the problem when the pattern graph H is of bounded treewidth, as occurs in a variety of applications. This problem has a well-known algorithm via color-coding that runs in time $O(n^{tw(H)+1})$ [Alon, Yuster, Zwick'95], where $n$ is the number of vertices of the host graph $G$. While there are pattern graphs known for which Subgraph Isomorphism can be solved in an improved running time of $O(n^{tw(H)+1-\varepsilon})$ or even faster (e.g. for $k$-cliques), it is not known whether such improvements are possible for all patterns. The only known lower bound rules out time $n^{o(tw(H) / \log(tw(H)))}$ for any class of patterns of unbounded treewidth assuming the Exponential Time Hypothesis [Marx'07]. In this paper, we demonstrate the existence of maximally hard pattern graphs $H$ that require time $n^{tw(H)+1-o(1)}$. Specifically, under the Strong Exponential Time Hypothesis (SETH), a standard assumption from fine-grained complexity theory, we prove the following asymptotic statement for large treewidth $t$: For any $\varepsilon > 0$ there exists $t \ge 3$ and a pattern graph $H$ of treewidth $t$ such that Subgraph Isomorphism on pattern $H$ has no algorithm running in time $O(n^{t+1-\varepsilon})$. Under the more recent 3-uniform Hyperclique hypothesis, we even obtain tight lower bounds for each specific treewidth $t \ge 3$: For any $t \ge 3$ there exists a pattern graph $H$ of treewidth $t$ such that for any $\varepsilon>0$ Subgraph Isomorphism on pattern $H$ has no algorithm running in time $O(n^{t+1-\varepsilon})$. In addition to these main results, we explore (1) colored and uncolored problem variants (and why they are equivalent for most cases), (2) Subgraph Isomorphism for $tw < 3$, (3) Subgraph Isomorphism parameterized by pathwidth, and (4) a weighted problem variant. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC,

%0 Report %A Bringmann, Karl %A Cassis, Alejandro %A Fischer, Nick %A K&#252;nnemann, Marvin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Fine-Grained Completeness for Optimization in P : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E26A-2 %U https://arxiv.org/abs/2107.01721 %D 2021 %X We initiate the study of fine-grained completeness theorems for exact and approximate optimization in the polynomial-time regime. Inspired by the first completeness results for decision problems in P (Gao, Impagliazzo, Kolokolova, Williams, TALG 2019) as well as the classic class MaxSNP and MaxSNP-completeness for NP optimization problems (Papadimitriou, Yannakakis, JCSS 1991), we define polynomial-time analogues MaxSP and MinSP, which contain a number of natural optimization problems in P, including Maximum Inner Product, general forms of nearest neighbor search and optimization variants of the $k$-XOR problem. Specifically, we define MaxSP as the class of problems definable as $\max_{x_1,\dots,x_k} \#\{ (y_1,\dots,y_\ell) : \phi(x_1,\dots,x_k, y_1,\dots,y_\ell) \}$, where $\phi$ is a quantifier-free first-order property over a given relational structure (with MinSP defined analogously). On $m$-sized structures, we can solve each such problem in time $O(m^{k+\ell-1})$. Our results are: - We determine (a sparse variant of) the Maximum/Minimum Inner Product problem as complete under *deterministic* fine-grained reductions: A strongly subquadratic algorithm for Maximum/Minimum Inner Product would beat the baseline running time of $O(m^{k+\ell-1})$ for *all* problems in MaxSP/MinSP by a polynomial factor. - This completeness transfers to approximation: Maximum/Minimum Inner Product is also complete in the sense that a strongly subquadratic $c$-approximation would give a $(c+\varepsilon)$-approximation for all MaxSP/MinSP problems in time $O(m^{k+\ell-1-\delta})$, where $\varepsilon > 0$ can be chosen arbitrarily small. Combining our completeness with~(Chen, Williams, SODA 2019), we obtain the perhaps surprising consequence that refuting the OV Hypothesis is *equivalent* to giving a $O(1)$-approximation for all MinSP problems in faster-than-$O(m^{k+\ell-1})$ time. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC

%0 Journal Article %A Bringmann, Karl %A K&#252;nnemann, Marvin %A Nusser, Andr&#233; %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Discrete Fr&#233;chet Distance under Translation: Conditional Hardness and an Improved Algorithm : %G eng %U http://hdl.handle.net/21.11116/0000-0009-2A8B-C %R 10.1145/3460656 %7 2021 %D 2021 %J ACM Transactions on Algorithms %V 17 %N 3 %& 1 %P 1 - 42 %Z sequence number: 25 %I ACM %C New York, NY %@ false

%0 Conference Proceedings %A Bringmann, Karl %A Cassis, Alejandro %A Fischer, Nick %A K&#252;nnemann, Marvin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Fine-Grained Completeness for Optimization in P : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B411-8 %R 10.4230/LIPIcs.APPROX/RANDOM.2021.9 %U urn:nbn:de:0030-drops-147024 %D 2021 %B 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the 25th International Conference on Randomization and Computation %Z date of event: 2021-08-16 - 2021-08-18 %C Seattle, WA, USA %B Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques %E Wootters, Mary; Sanit&#224;, Laura %P 1 - 22 %Z sequence number: 9 %I Schloss Dagstuhl %@ 978-3-95977-207-5 %B Leibniz International Proceedings in Informatics %N 207 %@ false

%0 Report %A Bringmann, Karl %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B434-1 %U https://arxiv.org/abs/2107.13206 %D 2021 %X In the classical Subset Sum problem we are given a set $X$ and a target $t$, and the task is to decide whether there exists a subset of $X$ which sums to $t$. A recent line of research has resulted in $\tilde{O}(t)$-time algorithms, which are (near-)optimal under popular complexity-theoretic assumptions. On the other hand, the standard dynamic programming algorithm runs in time $O(n \cdot |\mathcal{S}(X,t)|)$, where $\mathcal{S}(X,t)$ is the set of all subset sums of $X$ that are smaller than $t$. Furthermore, all known pseudopolynomial algorithms actually solve a stronger task, since they actually compute the whole set $\mathcal{S}(X,t)$. As the aforementioned two running times are incomparable, in this paper we ask whether one can achieve the best of both worlds: running time $\tilde{O}(|\mathcal{S}(X,t)|)$. In particular, we ask whether $\mathcal{S}(X,t)$ can be computed in near-linear time in the output-size. Using a diverse toolkit containing techniques such as color coding, sparse recovery, and sumset estimates, we make considerable progress towards this question and design an algorithm running in time $\tilde{O}(|\mathcal{S}(X,t)|^{4/3})$. Central to our approach is the study of top-$k$-convolution, a natural problem of independent interest: given sparse polynomials with non-negative coefficients, compute the lowest $k$ non-zero monomials of their product. We design an algorithm running in time $\tilde{O}(k^{4/3})$, by a combination of sparse convolution and sumset estimates considered in Additive Combinatorics. Moreover, we provide evidence that going beyond some of the barriers we have faced requires either an algorithmic breakthrough or possibly new techniques from Additive Combinatorics on how to pass from information on restricted sumsets to information on unrestricted sumsets. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Discrete Mathematics, cs.DM

%0 Report %A Bringmann, Karl %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B42E-9 %U https://arxiv.org/abs/2110.10283 %D 2021 %X Fine-grained complexity theory is the area of theoretical computer science that proves conditional lower bounds based on the Strong Exponential Time Hypothesis and similar conjectures. This area has been thriving in the last decade, leading to conditionally best-possible algorithms for a wide variety of problems on graphs, strings, numbers etc. This article is an introduction to fine-grained lower bounds in computational geometry, with a focus on lower bounds for polynomial-time problems based on the Orthogonal Vectors Hypothesis. Specifically, we discuss conditional lower bounds for nearest neighbor search under the Euclidean distance and Fr\'echet distance. %K Computer Science, Computational Geometry, cs.CG,Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Bringmann, Karl %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B428-F %R 10.1007/978-3-030-80049-9_6 %D 2021 %B 17th Conference on Computability in Europe %Z date of event: 2021-07-05 - 2021-07-09 %C Ghent, Belgium (Virtual Event) %B Connecting with Computability %E De Mol, Liesbeth; Weiermann, Andreas; Manea, Florin; Fern&#225;ndez-Duque, David %P 60 - 70 %I Springer %@ 978-3-030-80048-2 %B Lecture Notes in Computer Science %N 12813

%0 Report %A Bringmann, Karl %A Driemel, Anne %A Nusser, Andr&#233; %A Psarros, Ioannis %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fr&#233;chet Distance : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B43F-6 %U https://arxiv.org/abs/2107.07792 %D 2021 %X We study the $c$-approximate near neighbor problem under the continuous Fr\'echet distance: Given a set of $n$ polygonal curves with $m$ vertices, a radius $\delta > 0$, and a parameter $k \leq m$, we want to preprocess the curves into a data structure that, given a query curve $q$ with $k$ vertices, either returns an input curve with Fr\'echet distance at most $c\cdot \delta$ to $q$, or returns that there exists no input curve with Fr\'echet distance at most $\delta$ to $q$. We focus on the case where the input and the queries are one-dimensional polygonal curves -- also called time series -- and we give a comprehensive analysis for this case. We obtain new upper bounds that provide different tradeoffs between approximation factor, preprocessing time, and query time. Our data structures improve upon the state of the art in several ways. We show that for any $0 < \varepsilon \leq 1$ an approximation factor of $(1+\varepsilon)$ can be achieved within the same asymptotic time bounds as the previously best result for $(2+\varepsilon)$. Moreover, we show that an approximation factor of $(2+\varepsilon)$ can be obtained by using preprocessing time and space $O(nm)$, which is linear in the input size, and query time in $O(\frac{1}{\varepsilon})^{k+2}$, where the previously best result used preprocessing time in $n \cdot O(\frac{m}{\varepsilon k})^k$ and query time in $O(1)^k$. We complement our upper bounds with matching conditional lower bounds based on the Orthogonal Vectors Hypothesis. Interestingly, some of our lower bounds already hold for any super-constant value of $k$. This is achieved by proving hardness of a one-sided sparse version of the Orthogonal Vectors problem as an intermediate problem, which we believe to be of independent interest. %K Computer Science, Computational Geometry, cs.CG,Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS

%0 Report %A Bringmann, Karl %A Fischer, Nick %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B454-D %U https://arxiv.org/abs/2107.07625 %D 2021 %X Computing the convolution $A\star B$ of two length-$n$ integer vectors $A,B$ is a core problem in several disciplines. It frequently comes up in algorithms for Knapsack, $k$-SUM, All-Pairs Shortest Paths, and string pattern matching problems. For these applications it typically suffices to compute convolutions of nonnegative vectors. This problem can be classically solved in time $O(n\log n)$ using the Fast Fourier Transform. However, often the involved vectors are sparse and hence one could hope for output-sensitive algorithms to compute nonnegative convolutions. This question was raised by Muthukrishnan and solved by Cole and Hariharan (STOC '02) by a randomized algorithm running in near-linear time in the (unknown) output-size $t$. Chan and Lewenstein (STOC '15) presented a deterministic algorithm with a $2^{O(\sqrt{\log t\cdot\log\log n})}$ overhead in running time and the additional assumption that a small superset of the output is given; this assumption was later removed by Bringmann and Nakos (ICALP '21). In this paper we present the first deterministic near-linear-time algorithm for computing sparse nonnegative convolutions. This immediately gives improved deterministic algorithms for the state-of-the-art of output-sensitive Subset Sum, block-mass pattern matching, $N$-fold Boolean convolution, and others, matching up to log-factors the fastest known randomized algorithms for these problems. Our algorithm is a blend of algebraic and combinatorial ideas and techniques. Additionally, we provide two fast Las Vegas algorithms for computing sparse nonnegative convolutions. In particular, we present a simple $O(t\log^2t)$ time algorithm, which is an accessible alternative to Cole and Hariharan's algorithm. We further refine this new algorithm to run in Las Vegas time $O(t\log t\cdot\log\log t)$, matching the running time of the dense case apart from the $\log\log t$ factor. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Report %A Bringmann, Karl %A Kapralov, Michael %A Makarov, Mikhail %A Nakos, Vasileios %A Yagudin, Amir %A Zandieh, Amir %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Sparse Fourier Transform by Traversing Cooley-Tukey FFT Computation Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B459-8 %U https://arxiv.org/abs/2107.07347 %D 2021 %X Computing the dominant Fourier coefficients of a vector is a common task in many fields, such as signal processing, learning theory, and computational complexity. In the Sparse Fast Fourier Transform (Sparse FFT) problem, one is given oracle access to a $d$-dimensional vector $x$ of size $N$, and is asked to compute the best $k$-term approximation of its Discrete Fourier Transform, quickly and using few samples of the input vector $x$. While the sample complexity of this problem is quite well understood, all previous approaches either suffer from an exponential dependence of runtime on the dimension $d$ or can only tolerate a trivial amount of noise. This is in sharp contrast with the classical FFT algorithm of Cooley and Tukey, which is stable and completely insensitive to the dimension of the input vector: its runtime is $O(N\log N)$ in any dimension $d$. In this work, we introduce a new high-dimensional Sparse FFT toolkit and use it to obtain new algorithms, both on the exact, as well as in the case of bounded $\ell_2$ noise. This toolkit includes i) a new strategy for exploring a pruned FFT computation tree that reduces the cost of filtering, ii) new structural properties of adaptive aliasing filters recently introduced by Kapralov, Velingker and Zandieh'SODA'19, and iii) a novel lazy estimation argument, suited to reducing the cost of estimation in FFT tree-traversal approaches. Our robust algorithm can be viewed as a highly optimized sparse, stable extension of the Cooley-Tukey FFT algorithm. Finally, we explain the barriers we have faced by proving a conditional quadratic lower bound on the running time of the well-studied non-equispaced Fourier transform problem. This resolves a natural and frequently asked question in computational Fourier transforms. Lastly, we provide a preliminary experimental evaluation comparing the runtime of our algorithm to FFTW and SFFT 2.0. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Charalampopoulos, Panagiotis %A Kociumaka, Tomasz %A Wellnitz, Philip %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Faster Approximate Pattern Matching: A Unified Approach : %G eng %U http://hdl.handle.net/21.11116/0000-0007-8C66-9 %R 10.1109/FOCS46700.2020 %D 2021 %B 61st Annual IEEE Symposium on Foundations of Computer Science %Z date of event: 2020-11-16 - 2020-11-19 %C Durham, NC, USA (Virtual Conference) %B FOCS 2020 %P 978 - 989 %I IEEE %@ 978-1-7281-9621-3

%0 Thesis %A Chaudhury, Bhaskar Ray %Y Mehlhorn, Kurt %A referee: Bringmann, Karl %A referee: Roughgarden, Tim %A referee: Moulin, Herve %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society International Max Planck Research School, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Finding fair and efficient allocations : %G eng %U http://hdl.handle.net/21.11116/0000-0009-9CC9-5 %R 10.22028/D291-34537 %U nbn:de:bsz:291--ds-345370 %I Universit&#228;t des Saarlandes %C Saarbr&#252;cken %D 2021 %P 173 p. %V phd %9 phd %U https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/31737

%0 Conference Proceedings %A Chaudhury, Bhaskar Ray %A Garg, Jugal %A Mehlhorn, Kurt %A Mehta, Ruta %A Misra, Pranabendu %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Improving EFX Guarantees through Rainbow Cycle Number : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B3F6-7 %R 10.1145/3465456.3467605 %D 2021 %B 22nd ACM Conference on Economics and Computation %Z date of event: 2021-07-18 - 2021-07-23 %C Budapest, Hungary (Virtual) %B EC '21 %E Bir&#243;, P&#233;ter; Chawla, Shuchi; Echenique, Federico; Sodomka, Eric %P 310 - 311 %I ACM %@ 978-1-4503-8554-1

%0 Conference Proceedings %A Cheraghchi, Mahdi %A Nakos, Vasileios %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time : %G eng %U http://hdl.handle.net/21.11116/0000-0007-56C6-9 %R 10.1109/FOCS46700.2020 %D 2021 %B 61st Annual IEEE Symposium on Foundations of Computer Science %Z date of event: 2020-11-16 - 2020-11-19 %C Durham, NC, USA (Virtual Conference) %B FOCS 2020 %P 1203 - 1213 %I IEEE %@ 978-1-7281-9621-3

%0 Conference Proceedings %A Coupette, Corinna %A Lenzen, Christoph %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Breezing Proof of the KMW Bound : %G eng %U http://hdl.handle.net/21.11116/0000-0007-7A44-4 %R 10.1137/1.9781611976496.21 %D 2021 %B SIAM Symposium on Simplicity in Algorithms %Z date of event: 2021-01-11 - 2021-01-12 %C Alexandria, VA, USA (Virtual Conference) %B Symposium on Simplicity in Algorithms %E King, Valerie; Viet Le, Hung %P 184 - 195 %I SIAM %@ 978-1-61197-649-6

%0 Journal Article %A Coupette, Corinna %A Beckedorf, Janis %A Hartung, Dirk %A Bommarito, Michael %A Katz, Daniel Martin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T Measuring Law Over Time: A Network Analytical Framework with an Application to Statutes and Regulations in the United States and Germany : %G eng %U http://hdl.handle.net/21.11116/0000-0008-D8FA-B %R 10.3389/fphy.2021.658463 %7 2021 %D 2021 %J Frontiers in Physics %V 9 %Z sequence number: 658463 %I Frontiers Media %C Lausanne %@ false

%0 Conference Proceedings %A Coupette, Corinna %A Vreeken, Jilles %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Graph Similarity Description: How Are These Graphs Similar? : %G eng %U http://hdl.handle.net/21.11116/0000-0009-652C-5 %R 10.1145/3447548.3467257 %D 2021 %B 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining %Z date of event: 2021-08-14 - 2021-08-18 %C Virtual Event, Singapore %B KDD '21 %E Zhu, Fieda; Ooi, Beng, Chin; Miao, Chunyan; Cong, Gao; Tang, Jiliang; Derr, Tyler %P 185 - 195 %I ACM %@ 978-1-4503-8332-5

%0 Journal Article %A Cruciani, Emilio %A Natale, Emanuele %A Nusser, Andr&#233; %A Scornavacca, Giacomo %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks : %G eng %U http://hdl.handle.net/21.11116/0000-0008-BA11-3 %R 10.1007/s00446-021-00396-5 %7 2021 %D 2021 %J Distributed Computing %V Early Access %I Springer International %C Berlin %@ false

%0 Journal Article %A Darwish, Omar %A Elmasry, Amr %A Katajainen, Jyrki %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Memory-Adjustable Navigation Piles with Applications to Sorting and Convex Hulls : %G eng %U http://hdl.handle.net/21.11116/0000-0008-D8F2-3 %R 10.1145/3452938 %7 2021 %D 2021 %J ACM Transactions on Algorithms %V 17 %N 2 %Z sequence number: 18 %I ACM %C New York, NY %@ false

%0 Journal Article %A Dayama, Niraj Ramesh %A Shiripour, Morteza %A Oulasvirta, Antti %A Ivanko, Evgeny %A Karrenbauer, Andreas %+ External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Foraging-based Optimization of Menu Systems : %G eng %U http://hdl.handle.net/21.11116/0000-0008-9D57-6 %R 10.1016/j.ijhcs.2021.102624 %7 2021 %D 2021 %J International Journal of Human-Computer Studies %V 151 %Z sequence number: 102624 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A de Berg, Mark %A Kisfaludi-Bak, S&#225;ndor %A Monemizadeh, Morteza %A Theocharous, Leonidas %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Clique-Based Separators for Geometric Intersection Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B811-4 %R 10.4230/LIPIcs.ISAAC.2021.22 %U urn:nbn:de:0030-drops-154556 %D 2021 %B 32nd International Symposium on Algorithms and Computation %Z date of event: 2021-12-06 - 2021-12-08 %C Fukuoka, Japan %B 32nd International Symposium on Algorithms and Computation %E Ahn, Hee-Kap; Sadakane, Kunihiko %P 1 - 15 %Z sequence number: 22 %I Schloss Dagstuhl %@ 978-3-95977-214-3 %B Leibniz International Proceedings in Informatics %N 212 %@ false

%0 Journal Article %A D&#246;rfler, Julian %A Roth, Marc %A Schmitt, Johannes %A Wellnitz, Philip %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness : %G eng %U http://hdl.handle.net/21.11116/0000-0009-A583-8 %R 10.1007/s00453-021-00894-9 %7 2021 %D 2021 %J Algorithmica %I Springer-Verlag %C New York %@ false

%0 Journal Article %A Driemel, Anne %A Nusser, Andr&#233; %A Phillips, Jeff M. %A Psarros, Ioannis %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T The VC Dimension of Metric Balls under Fr&#233;chet and Hausdorff Distances : %G eng %U http://hdl.handle.net/21.11116/0000-0009-414C-9 %R 10.1007/s00454-021-00318-z %7 2021 %D 2021 %J Discrete & Computational Geometry %I Springer %C New York, NY %@ false

%0 Journal Article %A Dyer, Martin %A Greenhill, Catherine %A Kleer, Pieter %A Ross, James %A Stougie, Leen %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Sampling Hypergraphs with Given Degrees : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B820-3 %R 10.1016/j.disc.2021.112566 %7 2021 %D 2021 %J Discrete Mathematics %V 344 %N 11 %Z sequence number: 112566 %I Elsevier %C Amsterdam %@ false

%0 Journal Article %A Feit, Anna Maria %A Nancel, Mathieu %A John, Maximilian %A Karrenbauer, Andreas %A Weir, Daryl %A Oulasvirta, Antti %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T AZERTY Am&#233;lior&#233;: Computational Design on a National Scale : %G eng %U http://hdl.handle.net/21.11116/0000-0007-E78E-5 %R 10.1145/3382035 %7 2021 %D 2021 %K {F}r\'{e}chet %J Communications of the ACM %V 64 %N 2 %& 48 %P 48 - 58 %I Association for Computing Machinery, Inc. %C New York %@ false

%0 Journal Article %A Folz, Frederic %A Mehlhorn, Kurt %A Morigi, Giovanna %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Interplay of Periodic Dynamics and Noise: Insights from a Simple Adaptive System : %G eng %U http://hdl.handle.net/21.11116/0000-0009-9D3F-1 %R 10.1103/PhysRevE.104.054215 %7 2021 %D 2021 %J Physical Review E %O Phys. Rev. E %V 104 %N 5 %Z sequence number: 054215 %I American Physical Society %C Melville, NY %@ false

%0 Journal Article %A Fomin, Fedor V. %A Golovach, Petr A. %A Lochet, William %A Misra, Pranabendu %A Saket, Saurabh %A Sharma, Roohani %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Parameterized Complexity of Directed Spanner Problems : %G eng %U http://hdl.handle.net/21.11116/0000-0009-BAB8-6 %R 10.1007/s00453-021-00911-x %7 2021 %D 2021 %J Algorithmica %I Springer-Verlag %C New York %@ false

%0 Journal Article %A F&#252;gger, Matthias %A Kinali, Attila %A Lenzen, Christoph %A Wiederhake, Ben %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fast All-Digital Clock Frequency Adaptation Circuit for Voltage Droop Tolerance : %G eng %U http://hdl.handle.net/21.11116/0000-0009-201C-4 %R 10.1109/TCAD.2021.3097599 %7 2021 %D 2021 %J IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems %I IEEE %C Piscataway, NJ %@ false

%0 Report %A Giliberti, Jeff %A Karrenbauer, Andreas %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Improved Online Algorithm for Fractional Knapsack in the Random Order Model : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B637-C %U https://arxiv.org/abs/2109.04428 %D 2021 %X The fractional knapsack problem is one of the classical problems in combinatorial optimization, which is well understood in the offline setting. However, the corresponding online setting has been handled only briefly in the theoretical computer science literature so far, although it appears in several applications. Even the previously best known guarantee for the competitive ratio was worse than the best known for the integral problem in the popular random order model. We show that there is an algorithm for the online fractional knapsack problem that admits a competitive ratio of 4.39. Our result significantly improves over the previously best known competitive ratio of 9.37 and surpasses the current best 6.65-competitive algorithm for the integral case. Moreover, our algorithm is deterministic in contrast to the randomized algorithms achieving the results mentioned above. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Grohe, Martin %A Neuen, Daniel %A Wiebking, Daniel %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Isomorphism Testing for Graphs Excluding Small Minors : %G eng %U http://hdl.handle.net/21.11116/0000-0007-9947-D %R 10.1109/FOCS46700.2020.00064 %D 2021 %B 61st Annual IEEE Symposium on Foundations of Computer Science %Z date of event: 2020-11-16 - 2020-11-19 %C Durham, NC, USA (Virtual Conference) %B FOCS 2020 %P 625 - 636 %I IEEE %@ 978-1-7281-9621-3

%0 Report %A Kamkari, Hamidreza %A Karrenbauer, Andreas %A Sharifi, Mohammadamin %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Physarum Inspired Dynamics to Solve Semi-Definite Programs : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B656-9 %U https://arxiv.org/abs/2111.02291 %D 2021 %X Physarum Polycephalum is a Slime mold that can solve the shortest path problem. A mathematical model based on the Physarum's behavior, known as the Physarum Directed Dynamics, can solve positive linear programs. In this paper, we will propose a Physarum based dynamic based on the previous work and introduce a new way to solve positive Semi-Definite Programming (SDP) problems, which are more general than positive linear programs. Empirical results suggest that this extension of the dynamic can solve the positive SDP showing that the nature-inspired algorithm can solve one of the hardest problems in the polynomial domain. In this work, we will formulate an accurate algorithm to solve positive and some non-negative SDPs and formally prove some key characteristics of this solver thus inspiring future work to try and refine this method. %K Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Optimization and Control, math.OC

%0 Journal Article %A Kleer, Pieter %A Sch&#228;fer, Guido %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Computation and Efficiency of Potential Function Minimizers of Combinatorial Congestion Games : %G eng %U http://hdl.handle.net/21.11116/0000-0006-F285-2 %R 10.1007/s10107-020-01546-6 %7 2020 %D 2021 %J Mathematical Programming %V 190 %N 1 %& 523 %P 523 - 560 %I Springer %C New York, NY

%0 Report %A Kleer, Pieter %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Sampling from the Gibbs Distribution in Congestion Games : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E54C-1 %U https://arxiv.org/abs/2105.12982 %D 2021 %X Logit dynamics is a form of randomized game dynamics where players have a bias towards strategic deviations that give a higher improvement in cost. It is used extensively in practice. In congestion (or potential) games, the dynamics converges to the so-called Gibbs distribution over the set of all strategy profiles, when interpreted as a Markov chain. In general, logit dynamics might converge slowly to the Gibbs distribution, but beyond that, not much is known about their algorithmic aspects, nor that of the Gibbs distribution. In this work, we are interested in the following two questions for congestion games: i) Is there an efficient algorithm for sampling from the Gibbs distribution? ii) If yes, do there also exist natural randomized dynamics that converges quickly to the Gibbs distribution? We first study these questions in extension parallel congestion games, a well-studied special case of symmetric network congestion games. As our main result, we show that there is a simple variation on the logit dynamics (in which we in addition are allowed to randomly interchange the strategies of two players) that converges quickly to the Gibbs distribution in such games. This answers both questions above affirmatively. We also address the first question for the class of so-called capacitated $k$-uniform congestion games. To prove our results, we rely on the recent breakthrough work of Anari, Liu, Oveis-Gharan and Vinzant (2019) concerning the approximate sampling of the base of a matroid according to strongly log-concave probability distribution. %K Computer Science, Computer Science and Game Theory, cs.GT,Computer Science, Discrete Mathematics, cs.DM,Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Kleer, Pieter %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Sampling from the Gibbs Distribution in Congestion Games : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B3F8-5 %R 10.1145/3465456.3467597 %D 2021 %B 22nd ACM Conference on Economics and Computation %Z date of event: 2021-07-18 - 2021-07-23 %C Budapest, Hungary (Virtual) %B EC '21 %E Bir&#243;, P&#233;ter; Chawla, Shuchi; Echenique, Federico; Sodomka, Eric %P 679 - 680 %I ACM %@ 978-1-4503-8554-1

%0 Report %A Kleer, Pieter %A Simon, Hans Ulrich %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Primal and Dual Combinatorial Dimensions : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B834-D %U https://arxiv.org/abs/2108.10037 %D 2021 %X We give tight bounds on the relation between the primal and dual of various combinatorial dimensions, such as the pseudo-dimension and fat-shattering dimension, for multi-valued function classes. These dimensional notions play an important role in the area of learning theory. We first review some (folklore) results that bound the dual dimension of a function class in terms of its primal, and after that give (almost) matching lower bounds. In particular, we give an appropriate generalization to multi-valued function classes of a well-known bound due to Assouad (1983), that relates the primal and dual VC-dimension of a binary function class. %K Mathematics, Combinatorics, math.CO,Computer Science, Discrete Mathematics, cs.DM,Computer Science, Learning, cs.LG

%0 Report %A K&#252;nnemann, Marvin %A Nusser, Andr&#233; %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B462-D %U https://arxiv.org/abs/2111.02544 %D 2021 %X We revisit the classical problem of determining the largest copy of a simple polygon $P$ that can be placed into a simple polygon $Q$. Despite significant effort, known algorithms require high polynomial running times. (Barequet and Har-Peled, 2001) give a lower bound of $n^{2-o(1)}$ under the 3SUM conjecture when $P$ and $Q$ are (convex) polygons with $\Theta(n)$ vertices each. This leaves open whether we can establish (1) hardness beyond quadratic time and (2) any superlinear bound for constant-sized $P$ or $Q$. In this paper, we affirmatively answer these questions under the $k$SUM conjecture, proving natural hardness results that increase with each degree of freedom (scaling, $x$-translation, $y$-translation, rotation): (1) Finding the largest copy of $P$ that can be $x$-translated into $Q$ requires time $n^{2-o(1)}$ under the 3SUM conjecture. (2) Finding the largest copy of $P$ that can be arbitrarily translated into $Q$ requires time $n^{2-o(1)}$ under the 4SUM conjecture. (3) The above lower bounds are almost tight when one of the polygons is of constant size: we obtain an $\tilde O((pq)^{2.5})$-time algorithm for orthogonal polygons $P,Q$ with $p$ and $q$ vertices, respectively. (4) Finding the largest copy of $P$ that can be arbitrarily rotated and translated into $Q$ requires time $n^{3-o(1)}$ under the 5SUM conjecture. We are not aware of any other such natural $($degree of freedom $+ 1)$-SUM hardness for a geometric optimization problem. %K Computer Science, Computational Geometry, cs.CG,Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Lenzen, Christoph %A Vahidi, Hossein %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Approximate Minimum Directed Spanning Trees Under Congestion : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E553-8 %R 10.1007/978-3-030-79527-6_20 %D 2021 %B 28th International Colloquium on Structural Information and Communication Complexity %Z date of event: 2021-06-28 - 2021-07-01 %C Wroc&#322;aw, Poland (Online) %B Structural Information and Communication Complexity %E Jurdzi&#324;ski, Tomasz; Schmid, Stefan %P 352 - 369 %I Springer %@ 978-3-030-79526-9 %B Lecture Notes in Computer Science %N 12810

%0 Conference Proceedings %A Lokshtanov, Daniel %A Misra, Pranabendu %A Ramanujan, M. S. %A Saurabh, Saket %A Zehavi, Meirav %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T FPT-approximation for FPT Problems : %G eng %U http://hdl.handle.net/21.11116/0000-0007-D2AE-8 %R 10.1137/1.9781611976465.14 %D 2021 %B 32nd Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2021-01-10 - 2021-01-13 %C Alexandria, VA, USA (Virtual Conference) %B Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms %E Marx, D&#225;niel %P 199 - 218 %I SIAM %@ 978-1-61197-646-5

%0 Journal Article %A Lokshtanov, Daniel %A Misra, Pranabendu %A Mukherjee, Joydeep %A Panolan, Fahad %A Philip, Geevarghese %A Saurabh, Saket %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T 2-Approximating Feedback Vertex Set in Tournaments : %G eng %U http://hdl.handle.net/21.11116/0000-0008-D8F8-D %R 10.1145/3446969 %7 2021 %D 2021 %J ACM Transactions on Algorithms %V 17 %N 2 %Z sequence number: 11 %I ACM %C New York, NY %@ false

%0 Journal Article %A Madathil, Jayakrishnan %A Sharma, Roohani %A Zehavi, Meirav %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A Sub-exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs : %G eng %U http://hdl.handle.net/21.11116/0000-0008-2C54-9 %R 10.1007/s00453-021-00806-x %7 2021 %D 2021 %J Algorithmica %I Springer %C New York, NY %@ false

%0 Journal Article %A Nittala, Aditya Shekhar %A Karrenbauer, Andreas %A Khan, Arshad %A Kraus, Tobias %A Steimle, J&#252;rgen %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Computational Design and Optimization of Electro-physiological Sensors : %G eng %U http://hdl.handle.net/21.11116/0000-0009-7E62-C %R 10.1038/s41467-021-26442-1 %7 2021 %D 2021 %J Nature Communications %O Nat. Commun. %V 12 %N 1 %Z sequence number: 6351 %I Nature Publishing Group %C London %@ false

%0 Thesis %A Pandey, Anurag %Y Bl&#228;ser, Markus %A referee: Ikenmeyer, Christian %A referee: Mahajan, Meena %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society International Max Planck Research School, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Variety Membership Testing in Algebraic Complexity Theory : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E9F5-D %R 10.22028/D291-34244 %I Universit&#228;t des Saarlandes %C Saarbr&#252;cken %D 2021 %P 128 p. %V phd %9 phd %U https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/31479

%0 Conference Proceedings %A Ray Chaudhury, Bhaskar %A Garg, Jugal %A McGlaughlin, Peter %A Mehta, Ruta %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Competitive Allocation of a Mixed Manna : %G eng %U http://hdl.handle.net/21.11116/0000-0007-9365-1 %R 10.1137/1.9781611976465.85 %D 2021 %B 32nd Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2021-01-10 - 2021-01-13 %C Alexandria, VA, USA (Virtual Conference) %B Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms %E Marx, D&#225;niel %P 1405 - 1424 %I SIAM %@ 978-1-61197-646-5

%0 Conference Proceedings %A Ray Chaudhury, Bhaskar %A Garg, Jugal %A Mehta, Ruta %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Fair and Efficient Allocations under Subadditive Valuations : %G eng %U http://hdl.handle.net/21.11116/0000-0007-9370-4 %U https://ojs.aaai.org/index.php/AAAI/article/view/16665 %D 2021 %B Thirty-Fifth AAAI Conference on Artificial Intelligence %Z date of event: 2021-02-02 - 2021-02-09 %C Virtual Conference %B AAAI Technical Track on Game Theory and Economic Paradigms %P 5269 - 5276 %I AAAI %@ 978-1-57735-866-4 %U https://ojs.aaai.org/index.php/AAAI/article/view/16665

%0 Report %A Ray Chaudhury, Bhaskar %A Garg, Jugal %A Mehlhorn, Kurt %A Mehta, Ruta %A Misra, Pranabendu %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Improving EFX Guarantees through Rainbow Cycle Number : %G eng %U http://hdl.handle.net/21.11116/0000-0008-DB40-9 %U https://arxiv.org/abs/2103.01628 %D 2021 %X We study the problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations. Envy-freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of EFX allocations has not been settled and is one of the most important problems in fair division. Towards resolving this problem, many impressive results show the existence of its relaxations, e.g., the existence of $0.618$-EFX allocations, and the existence of EFX at most $n-1$ unallocated goods. The latter result was recently improved for three agents, in which the two unallocated goods are allocated through an involved procedure. Reducing the number of unallocated goods for arbitrary number of agents is a systematic way to settle the big question. In this paper, we develop a new approach, and show that for every $\varepsilon \in (0,1/2]$, there always exists a $(1-\varepsilon)$-EFX allocation with sublinear number of unallocated goods and high Nash welfare. For this, we reduce the EFX problem to a novel problem in extremal graph theory. We introduce the notion of rainbow cycle number $R(\cdot)$. For all $d \in \mathbb{N}$, $R(d)$ is the largest $k$ such that there exists a $k$-partite digraph $G =(\cup_{i \in [k]} V_i, E)$, in which 1) each part has at most $d$ vertices, i.e., $\lvert V_i \rvert \leq d$ for all $i \in [k]$, 2) for any two parts $V_i$ and $V_j$, each vertex in $V_i$ has an incoming edge from some vertex in $V_j$ and vice-versa, and 3) there exists no cycle in $G$ that contains at most one vertex from each part. We show that any upper bound on $R(d)$ directly translates to a sublinear bound on the number of unallocated goods. We establish a polynomial upper bound on $R(d)$, yielding our main result. Furthermore, our approach is constructive, which also gives a polynomial-time algorithm for finding such an allocation. %K Computer Science, Computer Science and Game Theory, cs.GT,Computer Science, Data Structures and Algorithms, cs.DS

%0 Journal Article %A Ray Chaudhury, Bhaskar %A Kavitha, Telikepalli %A Mehlhorn, Kurt %A Sgouritsa, Alkmini %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A Little Charity Guarantees Almost Envy-Freeness : %G eng %U http://hdl.handle.net/21.11116/0000-0009-2B38-9 %R 10.1137/20M1359134 %7 2021 %D 2021 %J SIAM Journal on Computing %V 50 %N 4 %& 1336 %P 1336 - 1358 %I SIAM %C Philadelphia, PA %@ false

%0 Conference Proceedings %A Roth, Marc %A Schmitt, Johannes %A Wellnitz, Philip %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Counting Small Induced Subgraphs Satisfying Monotone Properties : %G eng %U http://hdl.handle.net/21.11116/0000-0007-8C5E-3 %R 10.1109/FOCS46700.2020 %D 2021 %B 61st Annual IEEE Symposium on Foundations of Computer Science %Z date of event: 2020-11-16 - 2020-11-19 %C Durham, NC, USA (Virtual Conference) %B FOCS 2020 %P 1356 - 1367 %I IEEE %@ 978-1-7281-9621-3

%0 Conference Proceedings %A Roth, Marc %A Schmitt, Johannes %A Wellnitz, Philip %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders : %G eng %U http://hdl.handle.net/21.11116/0000-0009-AFBF-C %R 10.4230/LIPIcs.ICALP.2021.108 %U urn:nbn:de:0030-drops-141778 %D 2021 %B 48th International Colloquium on Automata, Languages, and Programming %Z date of event: 2021-07-12 - 2020-07-16 %C Glasgow, UK (Virtual Conference) %B 48th International Colloquium on Automata, Languages, and Programming %E Bansal, Nikhil; Merelli, Emanuela; Worrell, James %P 1 - 16 %Z sequence number: 108 %I Schloss Dagstuhl %@ 978-3-95977-195-5 %B Leibniz International Proceedings in Informatics %N 198 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2021/14177/

%0 Conference Proceedings %A Vitting Klinkby, Kristine %A Misra, Pranabendu %A Saurabh, Saket %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Strong Connectivity Augmentation is FPT : %G eng %U http://hdl.handle.net/21.11116/0000-0007-D2A6-0 %R 10.1137/1.9781611976465.15 %D 2021 %B 32nd Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2021-01-10 - 2021-01-13 %C Alexandria, VA, USA (Virtual Conference) %B Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms %E Marx, D&#225;niel %P 219 - 234 %I SIAM %@ 978-1-61197-646-5