Publications

%0 Journal Article %A Amanatidis, Georgios %A Kleer, Pieter %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices : %G eng %U http://hdl.handle.net/21.11116/0000-000A-567A-D %R 10.1137/20M1352697 %7 2022 %D 2022 %J SIAM Journal on Discrete Mathematics %V 36 %N 1 %& 118 %P 118 - 146 %I The Society %C Philadelphia, Pa. %@ false

%0 Journal Article %A Bonifaci, Vincenzo %A Facca, Enrico %A Folz, Frederic %A Karrenbauer, Andreas %A Kolev, Pavel %A Mehlhorn, Kurt %A Morigi, Giovanna %A Shahkarami, Golnoosh %A Vermande, Quentin %+ External Organizations External Organizations 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 External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Physarum-inspired Multi-commodity Flow Dynamics : %G eng %U http://hdl.handle.net/21.11116/0000-000A-28A1-3 %R 10.1016/j.tcs.2022.02.001 %7 2022 %D 2022 %J Theoretical Computer Science %I Elsevier %C Amsterdam %@ false

%0 Journal Article %A Bringmann, Karl %A Fischer, Nick %A Hermelin, Danny %A Shabtay, Dvir %A Wellnitz, Philip %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Faster Minimization of Tardy Processing Time on a Single Machine : %G eng %U http://hdl.handle.net/21.11116/0000-0009-FAD4-E %R 10.1007/s00453-022-00928-w %7 2022 %D 2022 %J Algorithmica %I Springer %C New York %@ false %U https://rdcu.be/cG2A9

%0 Journal Article %A Croitoru, Cosmina %A Croitoru, Madalina %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Indepth Combinatorial Analysis of Admissible Sets for Abstract Argumentation : %G eng %U http://hdl.handle.net/21.11116/0000-000A-5D72-E %R 10.1007/s10472-022-09785-3 %7 2022 %D 2022 %J Annals of Mathematics and Artificial Intelligence %I Springer %C New York, NY %@ false

%0 Journal Article %A Cseh, Ágnes %A Faenza, Yuri %A Kavitha, Telikepalli %A Powers, Vladlena %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Understanding Popular Matchings via Stable Matchings : %G eng %U http://hdl.handle.net/21.11116/0000-000A-57C3-8 %R 10.1137/19M124770X %7 2022 %D 2022 %J SIAM Journal on Discrete Mathematics %V 36 %N 1 %& 188 %P 188 - 213 %I The Society %C Philadelphia, Pa. %@ false

%0 Journal Article %A Halperin, Dan %A Har-Peled, Sariel %A Mehlhorn, Kurt %A Oh, Eunjin %A Sharir, Micha %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T The Maximum-Level Vertex in an Arrangement of Lines : %G eng %U http://hdl.handle.net/21.11116/0000-0009-D020-7 %R 10.1007/s00454-021-00338-9 %7 2022 %D 2022 %J Discrete & Computational Geometry %V 67 %& 439 %P 439 - 461 %I Springer %C New York, NY %@ false %U https://rdcu.be/cFlQF

%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 Conference Proceedings %A An, Haozhe %A Gurumukhani, Mohit %A Impagliazzo, Russell %A Jaber, Michael %A Künnemann, Marvin %A Nina, Maria Paula Parga %+ External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T The Fine-Grained Complexity of Multi-Dimensional Ordering Properties : %G eng %U http://hdl.handle.net/21.11116/0000-0009-CBD6-1 %R 10.4230/LIPIcs.IPEC.2021.3 %U urn:nbn:de:0030-drops-153869 %D 2021 %B 16th International Symposium on Parameterized and Exact Computation %Z date of event: 2021-09-08 - 2021-09-10 %C Lisbon, Portugal %B 16th International Symposium on Parameterized and Exact Computation %E Golovach, Petr A.; Zehavi, Meirav %P 1 - 15 %Z sequence number: 3 %I Schloss Dagstuhl %@ 978-3-95977-216-7 %B Leibniz International Proceedings in Informatics %N 214 %U https://drops.dagstuhl.de/opus/volltexte/2021/15386/https://creativecommons.org/licenses/by/4.0/legalcode

%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 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 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 %+ 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 Nusser, Andr&#233; %+ 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 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 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 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 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 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 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 Bringmann, Karl %A Nusser, Andr&#233; %+ 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&#232;re, &#201;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 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 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 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 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 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&#225;niel %P 1797 - 1815 %I SIAM %@ 978-1-61197-646-5

%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&#225;niel %P 1777 - 1796 %I SIAM %@ 978-1-61197-646-5

%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 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 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 Singh, Jyotsna %A Spamann, Holger %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Simplify Your Law: Using Information Theory to Deduplicate Legal Documents : %G eng %U http://hdl.handle.net/21.11116/0000-000A-5E10-B %R 10.1109/ICDMW53433.2021.00083 %D 2021 %B 21st IEEE International Conference on Data Mining Workshops %Z date of event: 2021-12-07 - 2021-12-10 %C Virtual Conference %B 21st IEEE International Conference on Data Mining Workshops %E Xue, Bing; Pechenizkiy, Mykola; Koh, Yun Sing %P 631 - 638 %I IEEE %@ 978-1-6654-2428-8

%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 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 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 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 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 %+ 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 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 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 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 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 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 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 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 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 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 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 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

%0 Conference Proceedings %A Abboud, Amir %A Backurs, Arturs %A Bringmann, Karl %A K&#252;nnemann, Marvin %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Impossibility Results for Grammar-Compressed Linear Algebra : %G eng %U http://hdl.handle.net/21.11116/0000-0007-90DF-B %D 2020 %B 34th Conference on Neural Information Processing Systems %Z date of event: 2020-12-06 - 2020-12-12 %C Virtual Event %B Advances in Neural Information Processing Systems 33 %E Larochelle, H.; Ranzato, M.; Hadsell, R.; Balcan, M. F.; Lin, H. %I Curran Associates, Inc. %U https://proceedings.neurips.cc/paper/2020/hash/645e6bfdd05d1a69c5e47b20f0a91d46-Abstract.html

%0 Conference Proceedings %A Abboud, Amir %A Bringmann, Karl %A Hermelin, Danny %A Shabtay, Dvir %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Scheduling Lower Bounds via AND Subset Sum : %G eng %U http://hdl.handle.net/21.11116/0000-0007-2826-2 %R 10.4230/LIPIcs.ICALP.2020.4 %U urn:nbn:de:0030-drops-124119 %D 2020 %B 47th International Colloquium on Automata, Languages, and Programming %Z date of event: 2020-07-08 - 2020-07-11 %C Saarbr&#252;cken, Germany (Virtual Conference) %B 47th International Colloquium on Automata, Languages, and Programming %E Czumaj, Artur; Dawa, Anuj; Merelli, Emanuela %Z sequence number: 4 %I Schloss Dagstuhl %@ 978-3-95977-138-2 %B Leibniz International Proceedings in Informatics %N 168 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/12411/https://creativecommons.org/licenses/by/3.0/legalcode

%0 Journal Article %A Abboud, Amir %A Censor-Hillel, Keren %A Khoury, Seri %A Lenzen, Christoph %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fooling Views: A New Lower Bound Technique for Distributed Computations under Congestion : %G eng %U http://hdl.handle.net/21.11116/0000-0006-F28E-9 %R 10.1007/s00446-020-00373-4 %7 2020 %D 2020 %J Distributed Computing %V 33 %& 545 %P 545 - 559 %I Springer %C New York, NY %@ false

%0 Report %A Abboud, Amir %A Bringmann, Karl %A Hermelin, Danny %A Shabtay, Dvir %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Scheduling Lower Bounds via AND Subset Sum : %G eng %U http://hdl.handle.net/21.11116/0000-0007-2A52-E %U https://arxiv.org/abs/2003.07113 %D 2020 %X Given $N$ instances $(X_1,t_1),\ldots,(X_N,t_N)$ of Subset Sum, the AND Subset Sum problem asks to determine whether all of these instances are yes-instances; that is, whether each set of integers $X_i$ has a subset that sums up to the target integer $t_i$. We prove that this problem cannot be solved in time $\tilde{O}((N \cdot t_{max})^{1-\epsilon})$, for $t_{max}=\max_i t_i$ and any $\epsilon > 0$, assuming the $\forall \exists$ Strong Exponential Time Hypothesis ($\forall \exists$-SETH). We then use this result to exclude $\tilde{O}(n+P_{max} \cdot n^{1-\epsilon})$-time algorithms for several scheduling problems on $n$ jobs with maximum processing time $P_{max}$, based on $\forall \exists$-SETH. These include classical problems such as $1||\sum w_jU_j$, the problem of minimizing the total weight of tardy jobs on a single machine, and $P_2||\sum U_j$, the problem of minimizing the number of tardy jobs on two identical parallel machines. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Achlioptas, Dimitris %A Gouleakis, Themis %A Iliopoulos, Fotis %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Simple Local Computation Algorithms for the General Lov&#225;sz Local Lemma : %G eng %U http://hdl.handle.net/21.11116/0000-0007-8B6D-3 %R 10.1145/3350755.3400250 %D 2020 %B 32nd ACM Symposium on Parallelism in Algorithms and Architectures %Z date of event: 2020-07-15 - 2020-07-17 %C Virtual Event, USA %B SPAA '20 %P 1 - 10 %I ACM %@ 9781450369350

%0 Journal Article %A Agrawal, Akanksha %A Lokshtanov, Daniel %A Misra, Pranabendu %A Saurabh, Saket %A Zehavi, Meirav %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Polylogarithmic Approximation Algorithms for Weighted-F-deletion Problems : %G eng %U http://hdl.handle.net/21.11116/0000-0007-4903-4 %R 10.1145/3389338 %7 2020 %D 2020 %J ACM Transactions on Algorithms %V 16 %N 4 %Z sequence number: 51 %I ACM %C New York, NY %@ false

%0 Conference Proceedings %A Agrawal, Akanksha %A Kundu, Madhumita %A Sahu, Abhishek %A Saurabh, Saket %A Tale, Prafullkumar %+ External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Parameterized Complexity of MAXIMUM EDGE COLORABLE SUBGRAPH : %G eng %U http://hdl.handle.net/21.11116/0000-0007-D2A4-2 %R 10.1007/978-3-030-58150-3_50 %D 2020 %B 26th International Conference on Computing and Combinatorics %Z date of event: 2020-08-29 - 2020-08-31 %C Atlanta, GA, USA %B Computing and Combinatorics %E Kim, Donghyun; Uma, R. N.; Cai, Zhipeng; Lee, Dong Hoon %P 615 - 626 %I Springer %@ 978-3-030-58149-7 %B Lecture Notes in Computer Science %N 12273

%0 Conference Proceedings %A Alkema, Henk %A de Berg, Mark %A Kisfaludi-Bak, S&#225;ndor %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Euclidean TSP in Narrow Strips : %G eng %U http://hdl.handle.net/21.11116/0000-0007-76E5-2 %R 10.4230/LIPIcs.SoCG.2020.4 %U urn:nbn:de:0030-drops-121628 %D 2020 %B 36th International Symposium on Computational Geometry %Z date of event: 2020-06-23 - 2020-06-26 %C Z&#252;rich, Switzerland (Virtual Conference) %B 36th International Symposium on Computational Geometry %E Cabello, Sergio; Chen, Danny Z. %P 1 - 16 %Z sequence number: 4 %I Schloss Dagstuhl %@ 978-3-95977-143-6 %B Leibniz International Proceedings in Informatics %N 164 %U https://drops.dagstuhl.de/opus/volltexte/2020/12162/https://creativecommons.org/licenses/by/3.0/legalcode

%0 Report %A Alkema, Henk %A de Berg, Mark %A Kisfaludi-Bak, S&#225;ndor %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Euclidean TSP in Narrow Strips : %G eng %U http://hdl.handle.net/21.11116/0000-0007-77A3-B %U https://arxiv.org/abs/2003.09948 %D 2020 %X We investigate how the complexity of Euclidean TSP for point sets $P$ inside the strip $(-\infty,+\infty)\times [0,\delta]$ depends on the strip width $\delta$. We obtain two main results. First, for the case where the points have distinct integer $x$-coordinates, we prove that a shortest bitonic tour (which can be computed in $O(n\log^2 n)$ time using an existing algorithm) is guaranteed to be a shortest tour overall when $\delta\leq 2\sqrt{2}$, a bound which is best possible. Second, we present an algorithm that is fixed-parameter tractable with respect to $\delta$. More precisely, our algorithm has running time $2^{O(\sqrt{\delta})} n^2$ for sparse point sets, where each $1\times\delta$ rectangle inside the strip contains $O(1)$ points. For random point sets, where the points are chosen uniformly at random from the rectangle~$[0,n]\times [0,\delta]$, it has an expected running time of $2^{O(\sqrt{\delta})} n^2 + O(n^3)$. %K Computer Science, Computational Geometry, cs.CG

%0 Journal Article %A Amanatidis, Georgios %A Kleer, Pieter %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences : %G eng %U http://hdl.handle.net/21.11116/0000-0006-DC7A-A %R 10.1002/rsa.20949 %7 2020 %D 2020 %J Random Structures and Algorithms %V 57 %N 3 %& 637 %P 637 - 657 %I Wiley %C New York, N.Y. %@ false

%0 Conference Proceedings %A Amiri, Saeed Akhoondian %A Popa, Alexandru %A Roghani, Mohammad %A Shahkarami, Golnoosh %A Soltani, Reza %A Vahidi, Hossein %+ External Organizations 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Complexity of Computing the Anti-Ramsey Numbers for Paths : %G eng %U http://hdl.handle.net/21.11116/0000-0007-9422-B %R 10.4230/LIPIcs.MFCS.2020.6 %U urn:nbn:de:0030-drops-126781 %D 2020 %B 45th International Symposium on Mathematical Foundations of Computer Science %Z date of event: 2020-08-25 - 2020-08-26 %C Prague, Czech Republic (Virtual Event) %B 45th International Symposium on Mathematical Foundations of Computer Science %E Esparza, Javier; Kr&#224;l', Daniel %Z sequence number: 6 %I Schloss Dagstuhl %@ 978-3-95977-159-7 %B Leibniz International Proceedings in Informatics %N 170 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/12678/https://creativecommons.org/licenses/by/3.0/legalcode

%0 Report %A Amiri, Saeed Akhoondian %A Wiederhake, Ben %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Distributed Distance-r Dominating Set on Sparse High-Girth Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0007-905B-0 %U https://arxiv.org/abs/1910.02794 %D 2020 %X The dominating set problem and its generalization, the distance-$r$ dominating set problem, are among the well-studied problems in the sequential settings. In distributed models of computation, unlike for domination, not much is known about distance-r domination. This is actually the case for other important closely-related covering problem, namely, the distance-$r$ independent set problem. By result of Kuhn et al. we know the distributed domination problem is hard on high girth graphs; we study the problem on a slightly restricted subclass of these graphs: graphs of bounded expansion with high girth, i.e. their girth should be at least $4r + 3$. We show that in such graphs, for every constant $r$, a simple greedy CONGEST algorithm provides a constant-factor approximation of the minimum distance-$r$ dominating set problem, in a constant number of rounds. More precisely, our constants are dependent to $r$, not to the size of the graph. This is the first algorithm that shows there are non-trivial constant factor approximations in constant number of rounds for any distance $r$-covering problem in distributed settings. To show the dependency on r is inevitable, we provide an unconditional lower bound showing the same problem is hard already on rings. We also show that our analysis of the algorithm is relatively tight, that is any significant improvement to the approximation factor requires new algorithmic ideas. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC,Computer Science, Discrete Mathematics, cs.DM,Mathematics, Combinatorics, math.CO

%0 Journal Article %A Amiri, Saeed Akhoondian %A Foerster, Klaus-Tycho %A Schmid, Stefan %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Walking Through Waypoints : %G eng %U http://hdl.handle.net/21.11116/0000-0007-EDEF-2 %R 10.1007/s00453-020-00672-z %7 2020 %D 2020 %J Algorithmica %V 82 %N 7 %& 1784 %P 1784 - 1812 %I Springer-Verlag %C New York %@ false

%0 Report %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-8B5D-5 %U https://arxiv.org/abs/2010.09106 %D 2020 %X This work provides several new insights on the robustness of Kearns' statistical query framework against challenging label-noise models. First, we build on a recent result by \cite{DBLP:journals/corr/abs-2006-04787} that showed noise tolerance of distribution-independently evolvable concept classes under Massart noise. Specifically, we extend their characterization to more general noise models, including the Tsybakov model which considerably generalizes the Massart condition by allowing the flipping probability to be arbitrarily close to $\frac{1}{2}$ for a subset of the domain. As a corollary, we employ an evolutionary algorithm by \cite{DBLP:conf/colt/KanadeVV10} to obtain the first polynomial time algorithm with arbitrarily small excess error for learning linear threshold functions over any spherically symmetric distribution in the presence of spherically symmetric Tsybakov noise. Moreover, we posit access to a stronger oracle, in which for every labeled example we additionally obtain its flipping probability. In this model, we show that every SQ learnable class admits an efficient learning algorithm with OPT + $\epsilon$ misclassification error for a broad class of noise models. This setting substantially generalizes the widely-studied problem of classification under RCN with known noise rate, and corresponds to a non-convex optimization problem even when the noise function -- i.e. the flipping probabilities of all points -- is known in advance. %K Statistics, Machine Learning, stat.ML,Computer Science, Learning, cs.LG

%0 Conference Proceedings %A Antoniadis, Antonios %A Gouleakis, Themis %A Kleer, Pieter %A Kolev, Pavel %+ 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 Secretary and Online Matching Problems with Machine Learned Advice : %G eng %U http://hdl.handle.net/21.11116/0000-0007-93CA-F %D 2020 %B 34th Conference on Neural Information Processing Systems %Z date of event: 2020-12-06 - 2020-12-12 %C Virtual Event %B Advances in Neural Information Processing Systems 33 %E Larochelle, H.; Ranzato, M.; Hadsell, R.; Balcan, M. F.; Lin, H. %I Curran Associates, Inc.

%0 Report %A Antoniadis, Antonios %A Kisfaludi-Bak, S&#225;ndor %A Laekhanukit, Bundit %A Vaz, Daniel %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T On the Approximability of the Traveling Salesman Problem with Line Neighborhoods : %G eng %U http://hdl.handle.net/21.11116/0000-0007-77AD-1 %U https://arxiv.org/abs/2008.12075 %D 2020 %X We study the variant of the Euclidean Traveling Salesman problem where instead of a set of points, we are given a set of lines as input, and the goal is to find the shortest tour that visits each line. The best known upper and lower bounds for the problem in $\mathbb{R}^d$, with $d\ge 3$, are $\mathrm{NP}$-hardness and an $O(\log^3 n)$-approximation algorithm which is based on a reduction to the group Steiner tree problem. We show that TSP with lines in $\mathbb{R}^d$ is APX-hard for any $d\ge 3$. More generally, this implies that TSP with $k$-dimensional flats does not admit a PTAS for any $1\le k \leq d-2$ unless $\mathrm{P}=\mathrm{NP}$, which gives a complete classification of the approximability of these problems, as there are known PTASes for $k=0$ (i.e., points) and $k=d-1$ (hyperplanes). We are able to give a stronger inapproximability factor for $d=O(\log n)$ by showing that TSP with lines does not admit a $(2-\epsilon)$-approximation in $d$ dimensions under the unique games conjecture. On the positive side, we leverage recent results on restricted variants of the group Steiner tree problem in order to give an $O(\log^2 n)$-approximation algorithm for the problem, albeit with a running time of $n^{O(\log\log n)}$. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Journal Article %A Antoniadis, Antonios %A Fleszar, Krzysztof %A Hoeksma, Ruben %A Schewior, Kevin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T A PTAS for Euclidean TSP with Hyperplane Neighborhoods : %G eng %U http://hdl.handle.net/21.11116/0000-0008-0723-9 %R 10.1145/3383466 %7 2020 %D 2020 %J ACM Transactions on Algorithms %V 16 %N 3 %Z sequence number: 38 %I ACM %C New York, NY %@ false

%0 Conference Proceedings %A Antoniadis, Antonios %A Garg, Naveen %A Kumar, Gunjan %A Kumar, Nikhil %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Parallel Machine Scheduling to Minimize Energy Consumption : %G eng %U http://hdl.handle.net/21.11116/0000-0006-F26A-2 %R 10.5555/3381089.3381257 %D 2020 %B 31st Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2020-01-05 - 2020-01-08 %C Salt Lake City, UT, USA %B Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms %E Chawla, Shuchi %P 2758 - 2769 %I SIAM %@ 978-1-61197-599-4

%0 Conference Proceedings %A Antoniadis, Antonios %A Coester, Christian %A Elias, Marek %A Polak, Adam %A Simon, Bertrand %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T Online Metric Algorithms with Untrusted Predictions : %G eng %U http://hdl.handle.net/21.11116/0000-0007-93BF-C %D 2020 %B 37th International Conference on Machine Learning %Z date of event: 2020-07-13 - 2020-07-18 %C Virtual Conference %B Proceedings of the 37th International Conference on Machine Learning %E Daum&#233;, Hal; Singh, Aarti %P 345 - 355 %I MLResearchPress %B Proceedings of Machine Learning Research %N 119 %@ false %U http://proceedings.mlr.press/v119/antoniadis20a/antoniadis20a.pdf

%0 Conference Proceedings %A Antoniadis, Antonios %A Cristi, Andr&#233;s %A Oosterwijk, Tim %A Sgouritsa, Alkmini %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T A General Framework for Energy-Efficient Cloud Computing Mechanisms : %G eng %U http://hdl.handle.net/21.11116/0000-0007-93A5-8 %U https://dl.acm.org/doi/10.5555/3398761.3398775 %D 2020 %B 19th International Conference on Autonomous Agents and MultiAgent Systems %Z date of event: 2020-05-09 - 2020-05-13 %C Auckland, New Zealand (Virtual) %B AAMAS'20 %E El Fallah Seghruchni, Amal; Sukthankr, Gita; An, Bo; Yorke-Smith, Neil %P 70 - 78 %I ACM %@ 978-1-4503-7518-4

%0 Report %A Antoniadis, Antonios %A Gouleakis, Themis %A Kleer, Pieter %A Kolev, Pavel %+ 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 Secretary and Online Matching Problems with Machine Learned Advice : %G eng %U http://hdl.handle.net/21.11116/0000-0007-8B7A-4 %U https://arxiv.org/abs/2006.01026 %D 2020 %X The classical analysis of online algorithms, due to its worst-case nature, can be quite pessimistic when the input instance at hand is far from worst-case. Often this is not an issue with machine learning approaches, which shine in exploiting patterns in past inputs in order to predict the future. However, such predictions, although usually accurate, can be arbitrarily poor. Inspired by a recent line of work, we augment three well-known online settings with machine learned predictions about the future, and develop algorithms that take them into account. In particular, we study the following online selection problems: (i) the classical secretary problem, (ii) online bipartite matching and (iii) the graphic matroid secretary problem. Our algorithms still come with a worst-case performance guarantee in the case that predictions are subpar while obtaining an improved competitive ratio (over the best-known classical online algorithm for each problem) when the predictions are sufficiently accurate. For each algorithm, we establish a trade-off between the competitive ratios obtained in the two respective cases. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Arunachalam, Srinivasan %A Chakraborty, Sourav %A Kouck&#253;, Michal %A Saurabh, Nitin %A de Wolf, Ronald %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Improved Bounds on Fourier Entropy and Min-entropy : %G eng %U http://hdl.handle.net/21.11116/0000-0006-97AB-F %R 10.4230/LIPIcs.STACS.2020.45 %U urn:nbn:de:0030-drops-119062 %D 2020 %B 37th International Symposium on Theoretical Aspects of Computer Science %Z date of event: 2020-03-10 - 2020-03-13 %C Montpellier, France %B 37th International Symposium on Theoretical Aspects of Computer Science %E Paul, Christophe; Bl&#228;ser, Markus %P 1 - 19 %Z sequence number: 45 %I Schloss Dagstuhl %@ 978-3-95977-140-5 %B Leibniz International Proceedings in Informatics %N 154 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/11906/

%0 Report %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-2A5B-5 %U https://arxiv.org/abs/2008.10577 %D 2020 %X We revisit the Subset Sum problem over the finite cyclic group $\mathbb{Z}_m$ for some given integer $m$. A series of recent works has provided asymptotically optimal algorithms for this problem under the Strong Exponential Time Hypothesis. Koiliaris and Xu (SODA'17, TALG'19) gave a deterministic algorithm running in time $\tilde{O}(m^{5/4})$, which was later improved to $O(m \log^7 m)$ randomized time by Axiotis et al. (SODA'19). In this work, we present two simple algorithms for the Modular Subset Sum problem running in near-linear time in $m$, both efficiently implementing Bellman's iteration over $\mathbb{Z}_m$. The first one is a randomized algorithm running in time $O(m\log^2 m)$, that is based solely on rolling hash and an elementary data-structure for prefix sums; to illustrate its simplicity we provide a short and efficient implementation of the algorithm in Python. Our second solution is a deterministic algorithm running in time $O(m\ \mathrm{polylog}\ m)$, that uses dynamic data structures for string manipulation. We further show that the techniques developed in this work can also lead to simple algorithms for the All Pairs Non-Decreasing Paths Problem (APNP) on undirected graphs, matching the asymptotically optimal running time of $\tilde{O}(n^2)$ provided in the recent work of Duan et al. (ICALP'19). %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Becker, Ruben %A Emek, Yuval %A Lenzen, Christoph %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Low Diameter Graph Decompositions by Approximate Distance Computation : %G eng %U http://hdl.handle.net/21.11116/0000-0005-A7A7-2 %R 10.4230/LIPIcs.ITCS.2020.50 %U urn:nbn:de:0030-drops-117355 %D 2020 %B 11th Innovations in Theoretical Computer Science Conference %Z date of event: 2020-01-12 - 2020-01-14 %C Seattle, WA, USA %B 11th Innovations in Theoretical Computer Science Conference %E Vidick, Thomas %Z sequence number: 50 %I Schloss Dagstuhl %@ 978-3-95977-134-4 %B Leibniz International Proceedings in Informatics %N 151 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/11735/https://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Journal Article %A Bil&#242;, Davide %A Gual&#224;, Luciano %A Leucci, Stefano %A Proietti, Guido %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Tracking Routes in Communication Networks : %G eng %U http://hdl.handle.net/21.11116/0000-0007-72EF-C %R 10.1016/j.tcs.2020.07.012 %7 2020 %D 2020 %J Theoretical Computer Science %V 844 %& 1 %P 1 - 15 %I Elsevier %C Amsterdam %@ false

%0 Report %A Bonifaci, Vincenzo %A Facca, Enrico %A Folz, Frederic %A Karrenbauer, Andreas %A Kolev, Pavel %A Mehlhorn, Kurt %A Morigi, Giovanna %A Shahkarami, Golnoosh %A Vermande, Quentin %+ External Organizations External Organizations 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 External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Physarum Multi-Commodity Flow Dynamics : %G eng %U http://hdl.handle.net/21.11116/0000-0007-2312-D %U https://arxiv.org/abs/2009.01498 %D 2020 %X In wet-lab experiments \cite{Nakagaki-Yamada-Toth,Tero-Takagi-etal}, the slime mold Physarum polycephalum has demonstrated its ability to solve shortest path problems and to design efficient networks, see Figure \ref{Wet-Lab Experiments} for illustrations. Physarum polycephalum is a slime mold in the Mycetozoa group. For the shortest path problem, a mathematical model for the evolution of the slime was proposed in \cite{Tero-Kobayashi-Nakagaki} and its biological relevance was argued. The model was shown to solve shortest path problems, first in computer simulations and then by mathematical proof. It was later shown that the slime mold dynamics can solve more general linear programs and that many variants of the dynamics have similar convergence behavior. In this paper, we introduce a dynamics for the network design problem. We formulate network design as the problem of constructing a network that efficiently supports a multi-commodity flow problem. We investigate the dynamics in computer simulations and analytically. The simulations show that the dynamics is able to construct efficient and elegant networks. In the theoretical part we show that the dynamics minimizes an objective combining the cost of the network and the cost of routing the demands through the network. We also give alternative characterization of the optimum solution. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Neural and Evolutionary Computing, cs.NE

%0 Conference Proceedings %A Brankovic, Milutin %A Buchin, Kevin %A Klaren, Koen %A Nusser, Andr&#233; %A Popov, Aleksandr %A Wong, Sampson %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warpin : %G eng %U http://hdl.handle.net/21.11116/0000-0007-9068-1 %R 0.1145/3397536.3422245 %D 2020 %B 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems %Z date of event: 2020-11-03 - 2020-11-06 %C Seattle, WA, USA (Online) %B 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems %E Lu, Chang-Tien; Wag, Fusheng; Trajcevski, Goce; Huang, Yan; Newsam, Shawn; Xiong, Li %P 99 - 110 %I ACM %@ 9781450380195

%0 Report %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 When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fr&#233;chet Distance under Translation : %G eng %U http://hdl.handle.net/21.11116/0000-0007-2A56-A %U https://arxiv.org/abs/2008.07510 %D 2020 %X 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\'echet 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\'echet distance, we perform algorithm engineering for the Fr\'echet 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\'echet 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\'echet distance under translation in applications, whereas previous approaches would have been computationally infeasible. %K Computer Science, Computational Geometry, cs.CG,Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Bringmann, Karl %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Top-k-convolution and the Quest for Near-linear Output-sensitive Subset Sum : %G eng %U http://hdl.handle.net/21.11116/0000-0007-299D-B %R 10.1145/3357713.3384308 %D 2020 %B 52nd Annual ACM SIGACT Symposium on Theory of Computing %Z date of event: 2020-06-22 - 2020-06-26 %C Chicago, IL, USA %B STOC '20 %E Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia %P 982 - 995 %I ACM %@ 978-1-4503-6979-4

%0 Conference Proceedings %A Bringmann, Karl %A Fischer, Nick %A Hermelin, Danny %A Shabtay, Dvir %A Wellnitz, Philip %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Faster Minimization of Tardy Processing Time on a Single Machine : %G eng %U http://hdl.handle.net/21.11116/0000-0007-287E-0 %R 10.4230/LIPIcs.ICALP.2020.19 %U urn:nbn:de:0030-drops-124269 %D 2020 %B 47th International Colloquium on Automata, Languages, and Programming %Z date of event: 2020-07-08 - 2020-07-11 %C Saarbr&#252;cken, Germany (Virtual Conference) %B 47th International Colloquium on Automata, Languages, and Programming %E Czumaj, Artur; Dawa, Anuj; Merelli, Emanuela %Z sequence number: 19 %I Schloss Dagstuhl %@ 978-3-95977-138-2 %B Leibniz International Proceedings in Informatics %N 168 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/12426/https://creativecommons.org/licenses/by/3.0/legalcode

%0 Conference Proceedings %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 When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fr&#233;chet Distance Under Translation : %G eng %U http://hdl.handle.net/21.11116/0000-0007-2791-9 %R 10.4230/LIPIcs.ESA.2020.25 %U urn:nbn:de:0030-drops-128912 %D 2020 %B 28th Annual European Symposium on Algorithms %Z date of event: 2020-09-07 - 2020-09-09 %C Pisa, Italy (Virtual Conference) %B 28th Annual European Symposium on Algorithms %E Grandoni, Fabrizio; Herman, Grzegorz; Sanders, Peter %Z sequence number: 25 %I Schloss Dagstuhl %@ 978-3-95977-162-7 %B Leibniz International Proceedings in Informatics %N 173 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/12891/https://creativecommons.org/licenses/by/3.0/legalcodehttps://gitlab.com/anusser/frechet_distance_under_translation

%0 Report %A Bringmann, Karl %A Fischer, Nick %A Hermelin, Danny %A Shabtay, Dvir %A Wellnitz, Philip %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Faster Minimization of Tardy Processing Time on a Single Machine : %G eng %U http://hdl.handle.net/21.11116/0000-0007-2A4E-4 %U https://arxiv.org/abs/2003.07104 %D 2020 %X This paper is concerned with the $1||\sum p_jU_j$ problem, the problem of minimizing the total processing time of tardy jobs on a single machine. This is not only a fundamental scheduling problem, but also a very important problem from a theoretical point of view as it generalizes the Subset Sum problem and is closely related to the 0/1-Knapsack problem. The problem is well-known to be NP-hard, but only in a weak sense, meaning it admits pseudo-polynomial time algorithms. The fastest known pseudo-polynomial time algorithm for the problem is the famous Lawler and Moore algorithm which runs in $O(P \cdot n)$ time, where $P$ is the total processing time of all $n$ jobs in the input. This algorithm has been developed in the late 60s, and has yet to be improved to date. In this paper we develop two new algorithms for $1||\sum p_jU_j$, each improving on Lawler and Moore's algorithm in a different scenario. Both algorithms rely on basic primitive operations between sets of integers and vectors of integers for the speedup in their running times. The second algorithm relies on fast polynomial multiplication as its main engine, while for the first algorithm we define a new "skewed" version of $(\max,\min)$-convolution which is interesting in its own right. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Journal Article %A Bringmann, Karl %A Gawrychowski, Pawe&#322; %A Mozes, Shay %A Weimann, Oren %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can) : %G eng %U http://hdl.handle.net/21.11116/0000-0007-2502-D %R 10.1145/3381878 %7 2020 %D 2020 %J ACM Transactions on Algorithms %V 16 %N 4 %Z sequence number: 48 %I ACM %C New York, NY %@ false

%0 Journal Article %A Bringmann, Karl %A Husfeldt, Thore %A Magnusson, M&#229;ns %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth : %G eng %U http://hdl.handle.net/21.11116/0000-0006-F289-E %R 10.1007/s00453-020-00680-z %7 2020 %D 2020 %J Algorithmica %V 82 %N 8 %& 2292 %P 2292 - 2315 %I Springer %C New York %@ false

%0 Report %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-8C97-1 %U https://arxiv.org/abs/2010.09096 %D 2020 %X In the Subset Sum problem we are given a set of $n$ positive integers $X$ and a target $t$ and are asked whether some subset of $X$ sums to $t$. Natural parameters for this problem that have been studied in the literature are $n$ and $t$ as well as the maximum input number $\rm{mx}_X$ and the sum of all input numbers $\Sigma_X$. In this paper we study the dense case of Subset Sum, where all these parameters are polynomial in $n$. In this regime, standard pseudo-polynomial algorithms solve Subset Sum in polynomial time $n^{O(1)}$. Our main question is: When can dense Subset Sum be solved in near-linear time $\tilde{O}(n)$? We provide an essentially complete dichotomy by designing improved algorithms and proving conditional lower bounds, thereby determining essentially all settings of the parameters $n,t,\rm{mx}_X,\Sigma_X$ for which dense Subset Sum is in time $\tilde{O}(n)$. For notational convenience we assume without loss of generality that $t \ge \rm{mx}_X$ (as larger numbers can be ignored) and $t \le \Sigma_X/2$ (using symmetry). Then our dichotomy reads as follows: - By reviving and improving an additive-combinatorics-based approach by Galil and Margalit [SICOMP'91], we show that Subset Sum is in near-linear time $\tilde{O}(n)$ if $t \gg \rm{mx}_X \Sigma_X/n^2$. - We prove a matching conditional lower bound: If Subset Sum is in near-linear time for any setting with $t \ll \rm{mx}_X \Sigma_X/n^2$, then the Strong Exponential Time Hypothesis and the Strong k-Sum Hypothesis fail. We also generalize our algorithm from sets to multi-sets, albeit with non-matching upper and lower bounds. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Discrete Mathematics, cs.DM

%0 Journal Article %A Bund, Johannes %A Fugger, Matthias %A Lenzen, Christoph %A Medina, Moti %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Synchronizer-Free Digital Link Controller : %G eng %U http://hdl.handle.net/21.11116/0000-0007-35FE-0 %R 10.1109/TCSI.2020.2989552 %7 2020 %D 2020 %J IEEE Transactions on Circuits and Systems / I, Regular Papers %V 27 %N 10 %& 3562 %P 3562 - 3573 %I Institute of Electrical and Electronics Engineers %C Piscataway, NJ %@ false

%0 Report %A Bund, Johannes %A F&#252;gger, Matthias %A Lenzen, Christoph %A Medina, Moti %A Rosenbaum, Will %+ 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 PALS: Plesiochronous and Locally Synchronous Systems : %G eng %U http://hdl.handle.net/21.11116/0000-0007-475C-3 %U https://arxiv.org/abs/2003.05542 %D 2020 %X Consider an arbitrary network of communicating modules on a chip, each requiring a local signal telling it when to execute a computational step. There are three common solutions to generating such a local clock signal: (i) by deriving it from a single, central clock source, (ii) by local, free-running oscillators, or (iii) by handshaking between neighboring modules. Conceptually, each of these solutions is the result of a perceived dichotomy in which (sub)systems are either clocked or fully asynchronous, suggesting that the designer's choice is limited to deciding where to draw the line between synchronous and asynchronous design. In contrast, we take the view that the better question to ask is how synchronous the system can and should be. Based on a distributed clock synchronization algorithm, we present a novel design providing modules with local clocks whose frequency bounds are almost as good as those of corresponding free-running oscillators, yet neighboring modules are guaranteed to have a phase offset substantially smaller than one clock cycle. Concretely, parameters obtained from a 15nm ASIC implementation running at 2GHz yield mathematical worst-case bounds of 30ps on phase offset for a 32x32 node grid network. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC

%0 Conference Proceedings %A Bund, Johannes %A F&#252;gger, Matthias %A Lenzen, Christoph %A Medina, Moti %A Rosenbaum, Will %+ 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 PALS: Plesiochronous and Locally Synchronous Systems : %G eng %U http://hdl.handle.net/21.11116/0000-0007-46B8-B %R 10.1109/ASYNC49171.2020.00013 %D 2020 %B 26th IEEE International Symposium on Asynchronous Circuits and Systems %Z date of event: 2020-05-17 - 2020-05-20 %C Salt Lake City, UT, USA %B 26th IEEE International Symposium on Asynchronous Circuits and Systems %P 36 - 43 %I IEEE %@ 978-1-7281-5495-4

%0 Journal Article %A Bund, Johannes %A Lenzen, Christoph %A Medina, Moti %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Optimal Metastability-Containing Sorting via Parallel Prefix Computation : %G eng %U http://hdl.handle.net/21.11116/0000-0005-9E7F-C %R 10.1109/TC.2019.2939818 %7 2020 %D 2020 %J IEEE Transactions on Computers %V 69 %N 2 %& 198 %P 198 - 211 %I IEEE %C Piscataway, NJ %@ false

%0 Journal Article %A Chalermsook, Parinya %A Cygan, Marek %A Kortsarz, Guy %A Laekhanukit, Bundit %A Manurangsi, Pasin %A Nanongkai, Danupon %A Trevisan, Luca %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More : %G eng %U http://hdl.handle.net/21.11116/0000-0007-1D05-4 %R 10.1137/18M1166869 %7 2020 %D 2020 %J SIAM Journal on Computing %V 49 %N 4 %& 772 %P 772 - 810 %I SIAM %C Philadelphia, PA %@ false

%0 Report %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-8C63-C %U https://arxiv.org/abs/2004.08350 %D 2020 %X Approximate pattern matching is a natural and well-studied problem on strings: Given a text $T$, a pattern $P$, and a threshold $k$, find (the starting positions of) all substrings of $T$ that are at distance at most $k$ from $P$. We consider the two most fundamental string metrics: the Hamming distance and the edit distance. Under the Hamming distance, we search for substrings of $T$ that have at most $k$ mismatches with $P$, while under the edit distance, we search for substrings of $T$ that can be transformed to $P$ with at most $k$ edits. Exact occurrences of $P$ in $T$ have a very simple structure: If we assume for simplicity that $|T| \le 3|P|/2$ and trim $T$ so that $P$ occurs both as a prefix and as a suffix of $T$, then both $P$ and $T$ are periodic with a common period. However, an analogous characterization for the structure of occurrences with up to $k$ mismatches was proved only recently by Bringmann et al. [SODA'19]: Either there are $O(k^2)$ $k$-mismatch occurrences of $P$ in $T$, or both $P$ and $T$ are at Hamming distance $O(k)$ from strings with a common period $O(m/k)$. We tighten this characterization by showing that there are $O(k)$ $k$-mismatch occurrences in the case when the pattern is not (approximately) periodic, and we lift it to the edit distance setting, where we tightly bound the number of $k$-edit occurrences by $O(k^2)$ in the non-periodic case. Our proofs are constructive and let us obtain a unified framework for approximate pattern matching for both considered distances. We showcase the generality of our framework with results for the fully-compressed setting (where $T$ and $P$ are given as a straight-line program) and for the dynamic setting (where we extend a data structure of Gawrychowski et al. [SODA'18]). %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Journal Article %A Chitnis, Rajesh H. %A Feldmann, Andreas E. %A HajiAghayi, MohammadTaghi %A Marx, Daniel %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) : %G eng %U http://hdl.handle.net/21.11116/0000-0006-E002-A %R 10.1137/18M122371X %7 2020 %D 2020 %J SIAM Journal on Computing %V 49 %N 2 %& 318 %P 318 - 364 %I Society for Industrial and Applied Mathematics. %C Philadelphia %@ false

%0 Conference Proceedings %A Christodoulou, George %A Gkatzelis, Vasilis %A Latifian, Mohamad %A Sgouritsa, Alkmini %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Resource-Aware Protocols for Network Cost-Sharing Games : %G eng %U http://hdl.handle.net/21.11116/0000-0007-938C-5 %R 10.1145/3391403.3399528 %D 2020 %B 21st ACM Conference on Economics and Computation %Z date of event: 2020-07-13 - 2020-07-17 %C Virtual Event, Hungary %B EC '20 %E Bir&#243;, P&#233;ter; Hartline, Jason %P 81 - 107 %I ACM %@ 9781450379755

%0 Report %A Cohen-Addad, Vincent %A Klein, Philip N. %A Marx, D&#225;niel %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting : %G eng %U http://hdl.handle.net/21.11116/0000-0007-495A-3 %U https://arxiv.org/abs/2009.00188 %D 2020 %X Redistricting is the problem of dividing a state into a number $k$ of regions, called districts. Voters in each district elect a representative. The primary criteria are: each district is connected, district populations are equal (or nearly equal), and districts are "compact". There are multiple competing definitions of compactness, usually minimizing some quantity. One measure that has been recently promoted by Duchin and others is number of cut edges. In redistricting, one is given atomic regions out of which each district must be built. The populations of the atomic regions are given. Consider the graph with one vertex per atomic region (with weight equal to the region's population) and an edge between atomic regions that share a boundary. A districting plan is a partition of vertices into $k$ parts, each connnected, of nearly equal weight. The districts are considered compact to the extent that the plan minimizes the number of edges crossing between different parts. Consider two problems: find the most compact districting plan, and sample districting plans under a compactness constraint uniformly at random. Both problems are NP-hard so we restrict the input graph to have branchwidth at most $w$. (A planar graph's branchwidth is bounded by its diameter.) If both $k$ and $w$ are bounded by constants, the problems are solvable in polynomial time. Assume vertices have weight~1. One would like algorithms whose running times are of the form $O(f(k,w) n^c)$ for some constant $c$ independent of $k$ and $w$, in which case the problems are said to be fixed-parameter tractable with respect to $k$ and $w$). We show that, under a complexity-theoretic assumption, no such algorithms exist. However, we do give algorithms with running time $O(c^wn^{k+1})$. Thus if the diameter of the graph is moderately small and the number of districts is very small, our algorithm is useable. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Report %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-46DC-3 %U https://arxiv.org/abs/2002.06005 %D 2020 %X In their seminal paper from 2004, Kuhn, Moscibroda, and Wattenhofer (KMW) proved a hardness result for several fundamental graph problems in the LOCAL model: For any (randomized) algorithm, there are input graphs with $n$ nodes and maximum degree $\Delta$ on which $\Omega(\min\{\sqrt{\log n/\log \log n},\log \Delta/\log \log \Delta\})$ (expected) communication rounds are required to obtain polylogarithmic approximations to a minimum vertex cover, minimum dominating set, or maximum matching. Via reduction, this hardness extends to symmetry breaking tasks like finding maximal independent sets or maximal matchings. Today, more than $15$ years later, there is still no proof of this result that is easy on the reader. Setting out to change this, in this work, we provide a fully self-contained and $\mathit{simple}$ proof of the KMW lower bound. The key argument is algorithmic, and it relies on an invariant that can be readily verified from the generation rules of the lower bound graphs. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC,Computer Science, Computational Complexity, cs.CC,Computer Science, Discrete Mathematics, cs.DM,Computer Science, Data Structures and Algorithms, cs.DS

%0 Report %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-0007-4689-0 %D 2020 %X Computational design of menu systems has been solved in limited cases such as the linear menu (list) as an assignment task, where commands are assigned to menu positions while optimizing for for users selection performance and distance of associated items. We show that this approach falls short with larger, hierarchically organized menu systems, where one must also take into account how users navigate hierarchical structures. This paper presents a novel integer programming formulation that models hierarchical menus as a combination of the exact set covering problem and the assignment problem. It organizes commands into ordered groups of ordered groups via a novel objective function based on information foraging theory. It minimizes, on the one hand, the time required to select a command whose location is known from previous usage and, on the other, the time wasted in irrelevant parts of the menu while searching for commands whose location is not known. The convergence of these two factors yields usable, well-ordered command hierarchies from a single model. In generated menus, the lead (first) elements of a group or tab are good indicators of the remaining contents, thereby facilitating the search process. In a controlled usability evaluation, the performance of computationally designed menus was 25 faster than existing commercial designs with respect to selection time. The algorithm is efficient for large, representative instances of the problem. We further show applications in personalization and adaptation of menu systems. %K Computer Science, Human-Computer Interaction, cs.HC,Mathematics, Optimization and Control, math.OC

%0 Book Section %A de Berg, Mark %A Kisfaludi-Bak, S&#225;ndor %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0007-76CB-0 %R 10.1007/978-3-030-42071-0_5 %D 2020 %B Treewidth, Kernels, and Algorithms %E Fomin, Fedor V.; Kratsch, Stefan; van Leeuwen, Erik Jan %P 31 - 48 %I Springer %C Berlin %@ 978-3-030-42070-3 %S Lecture Notes in Computer Science %N 12160

%0 Journal Article %A de Berg, Mark %A Bodlaender, Hans L. %A Kisfaludi-Bak, S&#225;ndor %A Marx, D&#225;niel %A van der Zanden, Tom C. %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T A Framework for Exponential-Time-Hypothesis-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0007-A582-B %R 10.1137/20M1320870 %7 2020 %D 2020 %J SIAM Journal on Computing %V 49 %N 6 %& 1291 %P 1291 - 1331 %I SIAM %C Philadelphia, PA %@ false

%0 Report %A Diakonikolas, Ilias %A Gouleakis, Themis %A Kane, Daniel M. %A Peebles, John %A Price, Eric %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Optimal Testing of Discrete Distributions with High Probability : %G eng %U http://hdl.handle.net/21.11116/0000-0007-8B62-E %U https://arxiv.org/abs/2009.06540 %D 2020 %X We study the problem of testing discrete distributions with a focus on the high probability regime. Specifically, given samples from one or more discrete distributions, a property $\mathcal{P}$, and parameters $0< \epsilon, \delta <1$, we want to distinguish {\em with probability at least $1-\delta$} whether these distributions satisfy $\mathcal{P}$ or are $\epsilon$-far from $\mathcal{P}$ in total variation distance. Most prior work in distribution testing studied the constant confidence case (corresponding to $\delta = \Omega(1)$), and provided sample-optimal testers for a range of properties. While one can always boost the confidence probability of any such tester by black-box amplification, this generic boosting method typically leads to sub-optimal sample bounds. Here we study the following broad question: For a given property $\mathcal{P}$, can we {\em characterize} the sample complexity of testing $\mathcal{P}$ as a function of all relevant problem parameters, including the error probability $\delta$? Prior to this work, uniformity testing was the only statistical task whose sample complexity had been characterized in this setting. As our main results, we provide the first algorithms for closeness and independence testing that are sample-optimal, within constant factors, as a function of all relevant parameters. We also show matching information-theoretic lower bounds on the sample complexity of these problems. Our techniques naturally extend to give optimal testers for related problems. To illustrate the generality of our methods, we give optimal algorithms for testing collections of distributions and testing closeness with unequal sized samples. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Learning, cs.LG,Mathematics, Statistics, math.ST,Statistics, Machine Learning, stat.ML,Statistics, Statistics Theory, stat.TH

%0 Journal Article %A Doerr, Benjamin %A K&#252;nnemann, Marvin %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem : %G eng %U http://hdl.handle.net/21.11116/0000-0006-FAC1-6 %R 10.1109/TIT.2020.2978385 %7 2020 %D 2020 %J IEEE Transactions on Information Theory %V 66 %N 9 %& 5729 %P 5729 - 5741 %I IEEE %C Piscataway, NJ %@ false

%0 Report %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-0007-9152-8 %U https://arxiv.org/abs/2006.12021 %D 2020 %X There is a well-known connection between hypergraphs and bipartite graphs, obtained by treating the incidence matrix of the hypergraph as the biadjacency matrix of a bipartite graph. We use this connection to describe and analyse a rejection sampling algorithm for sampling simple uniform hypergraphs with a given degree sequence. Our algorithm uses, as a black box, an algorithm $\mathcal{A}$ for sampling bipartite graphs with given degrees, uniformly or nearly uniformly, in (expected) polynomial time. The expected runtime of the hypergraph sampling algorithm depends on the (expected) runtime of the bipartite graph sampling algorithm $\mathcal{A}$, and the probability that a uniformly random bipartite graph with given degrees corresponds to a simple hypergraph. We give some conditions on the hypergraph degree sequence which guarantee that this probability is bounded below by a constant. %K Computer Science, Discrete Mathematics, cs.DM

%0 Journal Article %A Facca, Enrico %A Karrenbauer, Andreas %A Kolev, Pavel %A Mehlhorn, Kurt %+ 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 Convergence of the Non-Uniform Directed Physarum Model : %G eng %U http://hdl.handle.net/21.11116/0000-0006-97B9-F %R 10.1016/j.tcs.2020.01.034 %7 2020 %D 2020 %J Theoretical Computer Science %V 816 %& 184 %P 184 - 194 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A Faenza, Yuri %A Kavitha, Telikepalli %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Quasi-popular Matchings, Optimality, and Extended Formulations : %G eng %U http://hdl.handle.net/21.11116/0000-0006-F26C-0 %R 10.5555/3381089.3381109 %D 2020 %B 31st Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2020-01-05 - 2020-01-08 %C Salt Lake City, UT, USA %B Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms %E Chawla, Shuchi %P 325 - 344 %I SIAM %@ 978-1-61197-599-4

%0 Journal Article %A Fischer, Nick %A Ikenmeyer, Christian %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T The Computational Complexity of Plethysm Coefficients : %G eng %U http://hdl.handle.net/21.11116/0000-0007-72D0-D %R 10.1007/s00037-020-00198-4 %7 2020 %D 2020 %J Computational Complexity %V 29 %N 2 %Z sequence number: 8 %I Springer %C New York,NY

%0 Conference Proceedings %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-0007-9373-1 %R 10.4230/LIPIcs.IPEC.2020.12 %U urn:nbn:de:0030-drops-133156 %D 2020 %B 15th International Symposium on Parameterized and Exact Computation %Z date of event: 2020-12-14 - 2020-12-18 %C Hong Kong, China (Virtual Conference) %B 15th International Symposium on Parameterized and Exact Computation %E Cao, Yixin; Pilipczuk, Marcin %Z sequence number: 12 %I Schloss Dagstuhl %@ 978-3-95977-172-6 %B Leibniz International Proceedings in Informatics %N 180 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/13315/https://creativecommons.org/licenses/by/3.0/legalcode

%0 Conference Proceedings %A Fomin, Fedor V. %A Golovach, Petr %A Misra, Pranabendu %A Ramanujan, M. S. %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T On the Complexity of Recovering Incidence Matrices : %G eng %U http://hdl.handle.net/21.11116/0000-0007-D2B0-4 %R 10.4230/LIPIcs.ESA.2020.50 %U urn:nbn:de:0030-drops-129164 %D 2020 %B 28th Annual European Symposium on Algorithms %Z date of event: 2020-09-07 - 2020-09-09 %C Pisa, Italy (Virtual Conference) %B 28th Annual European Symposium on Algorithms %E Grandoni, Fabrizio; Herman, Grzegorz; Sanders, Peter %Z sequence number: 50 %I Schloss Dagstuhl %@ 978-3-95977-162-7 %B Leibniz International Proceedings in Informatics %N 173 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/12916/https://creativecommons.org/licenses/by/3.0/legalcode

%0 Conference Proceedings %A Forster, Sebastian %A Nanongkai, Danupon %A Yang, Liu %A Saranurak, Thatchaphol %A Yingchareonthawornchai, Sorrachai %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms : %G eng %U http://hdl.handle.net/21.11116/0000-0006-F274-6 %R 10.5555/3381089.3381215 %D 2020 %B 31st Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2020-01-05 - 2020-01-08 %C Salt Lake City, UT, USA %B Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms %E Chawla, Shuchi %P 2046 - 2065 %I SIAM %@ 978-1-61197-599-4

%0 Conference Proceedings %A G&#246;ke, Alexander %A Marx, D&#225;niel %A Mnich, Matthias %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Hitting Long Directed Cycles Is Fixed-Parameter Tractable : %G eng %U http://hdl.handle.net/21.11116/0000-0007-491E-7 %R 10.4230/LIPIcs.ICALP.2020.59 %U urn:nbn:de:0030-drops-124664 %D 2020 %B 47th International Colloquium on Automata, Languages, and Programming %Z date of event: 2020-07-08 - 2020-07-11 %C Saarbr&#252;cken, Germany (Virtual Conference) %B 47th International Colloquium on Automata, Languages, and Programming %E Czumaj, Artur; Dawa, Anuj; Merelli, Emanuela %Z sequence number: 59 %I Schloss Dagstuhl %@ 978-3-95977-138-2 %B Leibniz International Proceedings in Informatics %N 168 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/12466/https://creativecommons.org/licenses/by/3.0/legalcode

%0 Report %A G&#246;ke, Alexander %A Marx, D&#225;niel %A Mnich, Matthias %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set : %G eng %U http://hdl.handle.net/21.11116/0000-0007-4920-3 %U https://arxiv.org/abs/2003.02483 %D 2020 %X The Directed Feedback Vertex Set (DFVS) problem takes as input a directed graph~$G$ and seeks a smallest vertex set~$S$ that hits all cycles in $G$. This is one of Karp's 21 $\mathsf{NP}$-complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. [STOC 2008, J. ACM 2008] showed its fixed-parameter tractability via a $4^kk! n^{\mathcal{O}(1)}$-time algorithm, where $k = |S|$. Here we show fixed-parameter tractability of two generalizations of DFVS: - Find a smallest vertex set $S$ such that every strong component of $G - S$ has size at most~$s$: we give an algorithm solving this problem in time $4^k(ks+k+s)!\cdot n^{\mathcal{O}(1)}$. This generalizes an algorithm by Xiao [JCSS 2017] for the undirected version of the problem. - Find a smallest vertex set $S$ such that every non-trivial strong component of $G - S$ is 1-out-regular: we give an algorithm solving this problem in time $2^{\mathcal{O}(k^3)}\cdot n^{\mathcal{O}(1)}$. We also solve the corresponding arc versions of these problems by fixed-parameter algorithms. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Report %A G&#246;ke, Alexander %A Marx, D&#225;niel %A Mnich, Matthias %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Hitting Long Directed Cycles is Fixed-Parameter Tractable : %G eng %U http://hdl.handle.net/21.11116/0000-0007-4923-0 %U https://arxiv.org/abs/2003.05267 %D 2020 %X In the Directed Long Cycle Hitting Set} problem we are given a directed graph $G$, and the task is to find a set $S$ of at most $k$ vertices/arcs such that $G-S$ has no cycle of length longer than $\ell$. We show that the problem can be solved in time $2^{\mathcal O(\ell k^3\log k + k^5\log k\log\ell)}\cdot n^{\mathcal O(1)}$, that is, it is fixed-parameter tractable (FPT) parameterized by $k$ and $\ell$. This algorithm can be seen as a far-reaching generalization of the fixed-parameter tractability of {\sc Mixed Graph Feedback Vertex Set} [Bonsma and Lokshtanov WADS 2011], which is already a common generalization of the fixed-parameter tractability of (undirected) {\sc Feedback Vertex Set} and the {\sc Directed Feedback Vertex Set} problems, two classic results in parameterized algorithms. The algorithm requires significant insights into the structure of graphs without directed cycles length longer than $\ell$ and can be seen as an exact version of the approximation algorithm following from the Erd{\H{o}}s-P{\'o}sa property for long cycles in directed graphs proved by Kreutzer and Kawarabayashi [STOC 2015]. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Report %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-9943-1 %U https://arxiv.org/abs/2004.07671 %D 2020 %X We prove that there is a graph isomorphism test running in time $n^{\operatorname{polylog}(h)}$ on $n$-vertex graphs excluding some $h$-vertex graph as a minor. Previously known bounds were $n^{\operatorname{poly}(h)}$ (Ponomarenko, 1988) and $n^{\operatorname{polylog}(n)}$ (Babai, STOC 2016). For the algorithm we combine recent advances in the group-theoretic graph isomorphism machinery with new graph-theoretic arguments. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Discrete Mathematics, cs.DM,Mathematics, Combinatorics, math.CO

%0 Conference Proceedings %A Gunda, Spoorthy %A Jain, Pallavi %A Lokshtanov, Daniel %A Saurabh, Saket %A Tale, Prafullkumar %+ External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T On the Parameterized Approximability of Contraction to Classes of Chordal Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0007-874F-9 %R 10.4230/LIPIcs.APPROX/RANDOM.2020.51 %U urn:nbn:de:0030-drops-126545 %D 2020 %B 23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems / 24th International Conference on Randomization and Computation %Z date of event: 2020-08-17 - 2020-08-19 %C Virtual Conference %B Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques %E Byrka, Jaros&#322;av; Meka, Raghu %P 1 - 19 %Z sequence number: 51 %I Schloss Dagstuhl %@ 978-3-95977-164-1 %B Leibniz International Proceedings in Informatics %N 176 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/12654/

%0 Report %A Halperin, Dan %A Har-Peled, Sariel %A Mehlhorn, Kurt %A Oh, Eunjin %A Sharir, Micha %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T The Maximum-Level Vertex in an Arrangement of Lines : %G eng %U http://hdl.handle.net/21.11116/0000-0006-AFB1-D %U http://arxiv.org/abs/2003.00518 %D 2020 %X Let $L$ be a set of $n$ lines in the plane, not necessarily in general position. We present an efficient algorithm for finding all the vertices of the arrangement $A(L)$ of maximum level, where the level of a vertex $v$ is the number of lines of $L$ that pass strictly below $v$. The problem, posed in Exercise~8.13 in de Berg etal [BCKO08], appears to be much harder than it seems, as this vertex might not be on the upper envelope of the lines. We first assume that all the lines of $L$ are distinct, and distinguish between two cases, depending on whether or not the upper envelope of $L$ contains a bounded edge. In the former case, we show that the number of lines of $L$ that pass above any maximum level vertex $v_0$ is only $O(\log n)$. In the latter case, we establish a similar property that holds after we remove some of the lines that are incident to the single vertex of the upper envelope. We present algorithms that run, in both cases, in optimal $O(n\log n)$ time. We then consider the case where the lines of $L$ are not necessarily distinct. This setup is more challenging, and the best we have is an algorithm that computes all the maximum-level vertices in time $O(n^{4/3}\log^{3}n)$. Finally, we consider a related combinatorial question for degenerate arrangements, where many lines may intersect in a single point, but all the lines are distinct: We bound the complexity of the weighted $k$-level in such an arrangement, where the weight of a vertex is the number of lines that pass through the vertex. We show that the bound in this case is $O(n^{4/3})$, which matches the corresponding bound for non-degenerate arrangements, and we use this bound in the analysis of one of our algorithms. %K Computer Science, Computational Geometry, cs.CG

%0 Journal Article %A Jain, Pallavi %A Kanesh, Lawqueen %A Misra, Pranabendu %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized : %G eng %U http://hdl.handle.net/21.11116/0000-0006-90BA-5 %R 10.1007/s00224-019-09964-6 %7 2020 %D 2020 %J Theory of Computing Systems %V 64 %& 1067 %P 1067 - 1093 %I Springer %C New York, NY %@ false

%0 Thesis %A John, Maximilian %Y Karrenbauer, Andreas %A referee: Mehlhorn, Kurt %+ 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 %T Of Keyboards and Beyond : Optimization in Human-Computer Interaction %U http://hdl.handle.net/21.11116/0000-0007-7152-D %R 10.22028/D291-30635 %I Universit&#228;t des Saarlandes %C Saarbr&#252;cken %D 2020 %P 91 p. %V phd %9 phd %U https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/28954

%0 Conference Proceedings %A Karrenbauer, Andreas %A Kovalevskaya, Elizaveta %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Reading Articles Online : %G eng %U http://hdl.handle.net/21.11116/0000-0007-E787-C %R 10.1007/978-3-030-64843-5_43 %D 2020 %B 14th Annual International Conference on Combinatorial Optimization and Application %Z date of event: 2020-12-11 - 2020-12-13 %C Dallas, TX, USA (Virtual Conference) %B Combinatorial Optimization and Applications %E Wu, Weili; Zhang, Zhongnan %P 639 - 654 %I Springer %@ 978-3-030-64842-8 %B Lecture Notes in Computer Science %N 12577

%0 Journal Article %A Karrenbauer, Andreas %A Kolev, Pavel %A Mehlhorn, Kurt %+ 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 Convergence of the Non-Uniform Physarum Dynamics : %G eng %U http://hdl.handle.net/21.11116/0000-0006-97C1-5 %R 10.1016/j.tcs.2020.02.032 %7 2020 %D 2020 %J Theoretical Computer Science %V 816 %& 260 %P 260 - 269 %I Elsevier %C Amsterdam %@ false

%0 Journal Article %A Katz, Daniel Martin %A Coupette, Corinna %A Beckedorf, Janis %A Hartung, Dirk %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Complex Societies and the Growth of the Law : %G eng %U http://hdl.handle.net/21.11116/0000-0007-5C0B-7 %R 10.1038/s41598-020-73623-x %7 2020 %D 2020 %J Scientific Reports %O Sci. Rep. %V 10 %Z sequence number: 18737 %I Nature Publishing Group %C London, UK %@ false

%0 Report %A Kisfaludi-Bak, S&#225;ndor %A Nederlof, Jesper %A W&#281;grzycki, Karol %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Gap-ETH-Tight Approximation Scheme for Euclidean TSP : %G eng %U http://hdl.handle.net/21.11116/0000-0007-7774-1 %U https://arxiv.org/abs/2011.03778 %D 2020 %X We revisit the classic task of finding the shortest tour of $n$ points in $d$-dimensional Euclidean space, for any fixed constant $d \geq 2$. We determine the optimal dependence on $\varepsilon$ in the running time of an algorithm that computes a $(1+\varepsilon)$-approximate tour, under a plausible assumption. Specifically, we give an algorithm that runs in $2^{\mathcal{O}(1/\varepsilon^{d-1})} n\log n$ time. This improves the previously smallest dependence on $\varepsilon$ in the running time $(1/\varepsilon)^{\mathcal{O}(1/\varepsilon^{d-1})}n \log n$ of the algorithm by Rao and Smith (STOC 1998). We also show that a $2^{o(1/\varepsilon^{d-1})}\text{poly}(n)$ algorithm would violate the Gap-Exponential Time Hypothesis (Gap-ETH). Our new algorithm builds upon the celebrated quadtree-based methods initially proposed by Arora (J. ACM 1998), but it adds a simple new idea that we call \emph{sparsity-sensitive patching}. On a high level this lets the granularity with which we simplify the tour depend on how sparse it is locally. Our approach is (arguably) simpler than the one by Rao and Smith since it can work without geometric spanners. We demonstrate the technique extends easily to other problems, by showing as an example that it also yields a Gap-ETH-tight approximation scheme for Rectilinear Steiner Tree. %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 Kisfaludi-Bak, S&#225;ndor %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Hyperbolic Intersection Graphs and (Quasi)-Polynomial Time : %G eng %U http://hdl.handle.net/21.11116/0000-0007-76EB-C %R 10.1137/1.9781611975994.100 %D 2020 %B 31st Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2020-01-05 - 2020-01-08 %C Salt Lake City, UT, USA %B Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms %E Chawla, Shuchi %P 1621 - 1638 %I SIAM %@ 978-1-61197-599-4

%0 Journal Article %A Kisfaludi-Bak, S&#225;ndor %A Nederlof, Jesper %A van Leeuwen, Erik Jan %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces : %G eng %U http://hdl.handle.net/21.11116/0000-0007-7796-A %R 10.1145/3371389 %7 2020 %D 2020 %J ACM Transactions on Algorithms %V 16 %N 3 %Z sequence number: 28 %I ACM %C New York, NY %@ false

%0 Conference Proceedings %A Kisfaludi-Bak, S&#225;ndor %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Quasi-Polynomial Algorithm for Well-Spaced Hyperbolic TSP : %G eng %U http://hdl.handle.net/21.11116/0000-0007-76E8-F %R 10.4230/LIPIcs.SoCG.2020.55 %U urn:nbn:de:0030-drops-122135 %D 2020 %B 36th International Symposium on Computational Geometry %Z date of event: 2020-06-23 - 2020-06-26 %C Z&#252;rich, Switzerland (Virtual Conference) %B 36th International Symposium on Computational Geometry %E Cabello, Sergio; Chen, Danny Z. %P 1 - 15 %Z sequence number: 55 %I Schloss Dagstuhl %@ 978-3-95977-143-6 %B Leibniz International Proceedings in Informatics %N 164 %U https://drops.dagstuhl.de/opus/volltexte/2020/12213/https://creativecommons.org/licenses/by/3.0/legalcode

%0 Journal Article %A Kleer, Pieter %A Patel, Viresh %A Stroh, Fabian %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Switch-Based Markov Chains for Sampling Hamiltonian Cycles in Dense Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0007-914C-0 %R 10.37236/9503 %7 2020 %D 2020 %J The Electronic Journal of Combinatorics %V 27 %N 4 %Z sequence number: P4.29 %I N.J. Calkin and H.S. Wilf %C Atlanta, Ga. %@ false %U https://doi.org/10.37236/9503

%0 Report %A Kleer, Pieter %A Sch&#228;fer, Guido %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Topological Price of Anarchy Bounds for Clustering Games on Networks : %G eng %U http://hdl.handle.net/21.11116/0000-0007-915F-B %R 10.1007/978-3-030-35389-6_18 %U https://arxiv.org/abs/2011.09717 %D 2020 %X We consider clustering games in which the players are embedded in a network and want to coordinate (or anti-coordinate) their strategy with their neighbors. The goal of a player is to choose a strategy that maximizes her utility given the strategies of her neighbors. Recent studies show that even very basic variants of these games exhibit a large Price of Anarchy: A large inefficiency between the total utility generated in centralized outcomes and equilibrium outcomes in which players selfishly try to maximize their utility. Our main goal is to understand how structural properties of the network topology impact the inefficiency of these games. We derive topological bounds on the Price of Anarchy for different classes of clustering games. These topological bounds provide a more informative assessment of the inefficiency of these games than the corresponding (worst-case) Price of Anarchy bounds. As one of our main results, we derive (tight) bounds on the Price of Anarchy for clustering games on Erd\H{o}s-R\'enyi random graphs (where every possible edge in the network is present with a fixed probability), which, depending on the graph density, stand in stark contrast to the known Price of Anarchy bounds. %K Computer Science, Computer Science and Game Theory, cs.GT

%0 Conference Proceedings %A K&#252;nnemann, Marvin %A Marx, D&#225;niel %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction : %G eng %U http://hdl.handle.net/21.11116/0000-0007-491C-9 %R 10.4230/LIPIcs.CCC.2020.27 %U urn:nbn:de:0030-drops-125791 %D 2020 %B 35th Computational Complexity Conference %Z date of event: 2020-07-28 - 2020-07-31 %C Saarbr&#252;cken, Germany (Virtual Conference) %B 35th Computational Complexity Conference %E Saraf, Shubhangi %Z sequence number: 27 %I Schlos Dagstuhl %@ 978-3-95977-156-6 %B Leibniz International Proceedings in Informatics %N 169 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/12579/https://creativecommons.org/licenses/by/3.0/legalcode

%0 Report %A K&#252;nnemann, Marvin %A Marx, D&#225;niel %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction : %G eng %U http://hdl.handle.net/21.11116/0000-0007-492E-5 %U https://arxiv.org/abs/2005.11541 %D 2020 %X 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)=(\omega/3\pm o(1))k$, (3) the exponent has sublinear dependence on $k$ with $g(k) \in [\Omega(\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. %K Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS

%0 Report %A Lenzen, Christoph %A Wiederhake, Ben %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T TRIX: Low-Skew Pulse Propagation for Fault-Tolerant Hardware : %G eng %U http://hdl.handle.net/21.11116/0000-0007-904F-E %U https://arxiv.org/abs/2010.01415 %D 2020 %X The vast majority of hardware architectures use a carefully timed reference signal to clock their computational logic. However, standard distribution solutions are not fault-tolerant. In this work, we present a simple grid structure as a more reliable clock propagation method and study it by means of simulation experiments. Fault-tolerance is achieved by forwarding clock pulses on arrival of the second of three incoming signals from the previous layer. A key question is how well neighboring grid nodes are synchronized, even without faults. Analyzing the clock skew under typical-case conditions is highly challenging. Because the forwarding mechanism involves taking the median, standard probabilistic tools fail, even when modeling link delays just by unbiased coin flips. Our statistical approach provides substantial evidence that this system performs surprisingly well. Specifically, in an "infinitely wide" grid of height~$H$, the delay at a pre-selected node exhibits a standard deviation of $O(H^{1/4})$ ($\approx 2.7$ link delay uncertainties for $H=2000$) and skew between adjacent nodes of $o(\log \log H)$ ($\approx 0.77$ link delay uncertainties for $H=2000$). We conclude that the proposed system is a very promising clock distribution method. This leads to the open problem of a stochastic explanation of the tight concentration of delays and skews. More generally, we believe that understanding our very simple abstraction of the system is of mathematical interest in its own right. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC

%0 Conference Proceedings %A Lenzen, Christoph %A Wiederhake, Ben %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Brief Announcement: TRIX: Low-Skew Pulse Propagation for Fault-Tolerant Hardware : %G eng %U http://hdl.handle.net/21.11116/0000-0007-9058-3 %R 10.1007/978-3-030-64348-5_23 %D 2020 %B 22nd International Symposium on Stabilization, Safety, and Security of Distributed Systems %Z date of event: 2020-11-18 - 2020-11-21 %C Austin, TX, USA (Virtual Event) %B Stabilization, Safety, and Security of Distributed Systems %E Devismes, St&#233;phane; Mittal, Neeraj %P 295 - 300 %I Springer %@ 978-3-030-64347-8 %B Lecture Notes in Computer Science %N 12514

%0 Journal Article %A Liu, Weiqiang %A Lombardi, Fabrizio %A Shulte, Michael %A Miller, David J. %A Xiang, Zhen %A Kesidis, George %A Oulasvirta, Antti %A Dayama, Niraj Ramesh %A Shiripour, Morteza %A John, Maximilian %A Karrenbauer, Andreas %A Allerhand, Adam %+ External Organizations External Organizations External Organizations External Organizations External Organizations External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Scanning the Issue : %G eng %U http://hdl.handle.net/21.11116/0000-0007-4670-C %R 10.1109/JPROC.2020.2975522 %7 2020 %D 2020 %J Proceedings of the IEEE %O Proc. IEEE %V 108 %N 3 %& 400 %P 400 - 401 %I IEEE %C New York, NY %@ false

%0 Journal Article %A Li, Yi %A Nakos, Vasileios %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Sublinear-Time Algorithms for Compressive Phase Retrieval : %G eng %U http://hdl.handle.net/21.11116/0000-0007-567C-E %R 10.1109/TIT.2020.3020701 %7 2020 %D 2020 %J IEEE Transactions on Information Theory %V 66 %N 11 %& 7302 %P 7302 - 7310 %I IEEE %C Piscataway, NJ %@ false

%0 Conference Proceedings %A Li, Yi %A Nakos, Vasileios %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Deterministic Sparse Fourier Transform with an &#8467;_{&#8734;} Guarantee : %G eng %U http://hdl.handle.net/21.11116/0000-0007-56A6-D %R 10.4230/LIPIcs.ICALP.2020.77 %U urn:nbn:de:0030-drops-124844 %D 2020 %B 47th International Colloquium on Automata, Languages, and Programming %Z date of event: 2020-07-08 - 2020-07-11 %C Saarbr&#252;cken, Germany (Virtual Conference) %B 47th International Colloquium on Automata, Languages, and Programming %E Czumaj, Artur; Dawa, Anuj; Merelli, Emanuela %Z sequence number: 77 %I Schloss Dagstuhl %@ 978-3-95977-138-2 %B Leibniz International Proceedings in Informatics %N 168 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/12484/

%0 Conference Proceedings %A Lochet, William %A Lokshtanov, Daniel %A Misra, Pranabendu %A Saurabh, Saket %A Sharma, Roohani %A Zehavi, Meirav %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Fault Tolerant Subgraphs with Applications in Kernelization : %G eng %U http://hdl.handle.net/21.11116/0000-0007-D2A8-E %R 10.4230/LIPIcs.ITCS.2020.47 %U urn:nbn:de:0030-drops-117326 %D 2020 %B 11th Innovations in Theoretical Computer Science Conference %Z date of event: 2020-01-12 - 2020-01-14 %C Seattle, WA, USA %B 11th Innovations in Theoretical Computer Science Conference %E Vidick, Thomas %Z sequence number: 47 %I Schloss Dagstuhl %@ 978-3-95977-134-4 %B Leibniz International Proceedings in Informatics %N 151 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/11732https://creativecommons.org/licenses/by/3.0/legalcode

%0 Conference Proceedings %A Lokshtanov, Daniel %A Misra, Pranabendu %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 %T A (2 + &#949;)-Factor Approximation Algorithm for Split Vertex Deletion : %G eng %U http://hdl.handle.net/21.11116/0000-0007-8EF5-5 %R 10.4230/LIPIcs.ICALP.2020.80 %U urn:nbn:de:0030-drops-124879 %D 2020 %B 47th International Colloquium on Automata, Languages, and Programming %Z date of event: 2020-07-08 - 2020-07-11 %C Saarbr&#252;cken, Germany (Virtual Conference) %B 47th International Colloquium on Automata, Languages, and Programming %E Czumaj, Artur; Dawa, Anuj; Merelli, Emanuela %Z sequence number: 80 %I Schloss Dagstuhl %@ 978-3-95977-138-2 %B Leibniz International Proceedings in Informatics %N 168 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/12487/https://creativecommons.org/licenses/by/3.0/legalcode

%0 Conference Proceedings %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-0006-F276-4 %R 10.5555/3381089.3381150 %D 2020 %B 31st Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2020-01-05 - 2020-01-08 %C Salt Lake City, UT, USA %B Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms %E Chawla, Shuchi %P 1010 - 1018 %I SIAM %@ 978-1-61197-599-4

%0 Conference Proceedings %A Lokshtanov, Daniel %A Misra, Pranabendu %A Pilipczuk, Micha&#322; %A Saurabh, Saket %A Zehavi, Meirav %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T An Exponential Time Parameterized Algorithm for Planar Disjoint Paths : %G eng %U http://hdl.handle.net/21.11116/0000-0007-D2AA-C %R 10.1145/3357713.3384250 %D 2020 %B 52nd Annual ACM SIGACT Symposium on Theory of Computing %Z date of event: 2020-06-22 - 2020-06-26 %C Chicago, IL, USA %B STOC '20 %E Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia %P 1307 - 1316 %I ACM %@ 978-1-4503-6979-4

%0 Report %A Marx, D&#225;niel %A Sandeep, R. B. %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Incompressibility of H-free Edge Modification Problems: Towards a Dichotomy : %G eng %U http://hdl.handle.net/21.11116/0000-0007-492A-9 %U https://arxiv.org/abs/2004.11761 %D 2020 %X Given a graph $G$ and an integer $k$, the $H$-free Edge Editing problem is to find whether there exists at most $k$ pairs of vertices in $G$ such that changing the adjacency of the pairs in $G$ results in a graph without any induced copy of $H$. The existence of polynomial kernels for $H$-free Edge Editing received significant attention in the parameterized complexity literature. Nontrivial polynomial kernels are known to exist for some graphs $H$ with at most 4 vertices, but starting from 5 vertices, polynomial kernels are known only if $H$ is either complete or empty. This suggests the conjecture that there is no other $H$ with at least 5 vertices were $H$-free Edge Editing admits a polynomial kernel. Towards this goal, we obtain a set $\mathcal{H}$ of nine 5-vertex graphs such that if for every $H\in\mathcal{H}$, $H$-free Edge Editing is incompressible and the complexity assumption $NP \not\subseteq coNP/poly$ holds, then $H$-free Edge Editing is incompressible for every graph $H$ with at least five vertices that is neither complete nor empty. That is, proving incompressibility for these nine graphs would give a complete classification of the kernelization complexity of $H$-free Edge Editing for every $H$ with at least 5 vertices. We obtain similar result also for $H$-free Edge Deletion. Here the picture is more complicated due to the existence of another infinite family of graphs $H$ where the problem is trivial (graphs with exactly one edge). We obtain a larger set $\mathcal{H}$ of nineteen graphs whose incompressibility would give a complete classification of the kernelization complexity of $H$-free Edge Deletion for every graph $H$ with at least 5 vertices. Analogous results follow also for the $H$-free Edge Completion problem by simple complementation. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Book Section %A Marx, D&#225;niel %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Four Shorts Stories on Surprising Algorithmic Uses of Treewidth : %G eng %U http://hdl.handle.net/21.11116/0000-0007-4911-4 %R 10.1007/978-3-030-42071-0_10 %D 2020 %B Treewidth, Kernels, and Algorithms %E Fomin, Fedor V.; Kratsch, Stefan; van Leeuwen, Erik Jan %P 129 - 144 %I Springer %C Berlin %@ 978-3-030-42070-3 %S Lecture Notes in Computer Science %N 12160

%0 Report %A Marx, D&#225;niel %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Four Short Stories on Surprising Algorithmic Uses of Treewidth : %G eng %U http://hdl.handle.net/21.11116/0000-0007-4950-D %U https://arxiv.org/abs/2008.07968 %D 2020 %X This article briefly describes four algorithmic problems where the notion of treewidth is very useful. Even though the problems themselves have nothing to do with treewidth, it turns out that combining known results on treewidth allows us to easily describe very clean and high-level algorithms. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Misra, Pranabendu %A Panolan, Fahad %A Rai, Ashutosh %A Saket, Saurabh %A Sharma, Roohani %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T Quick Separation in Chordal and Split Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0007-9380-1 %R 10.4230/LIPIcs.MFCS.2020.70 %U urn:nbn:de:0030-drops-127391 %D 2020 %B 45th International Symposium on Mathematical Foundations of Computer Science %Z date of event: 2020-08-25 - 2020-08-26 %C Prague, Czech Republic (Virtual Event) %B 45th International Symposium on Mathematical Foundations of Computer Science %E Esparza, Javier; Kr&#224;l', Daniel %Z sequence number: 70 %I Schloss Dagstuhl %@ 978-3-95977-159-7 %B Leibniz International Proceedings in Informatics %N 170 %@ false %U https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12739https://creativecommons.org/licenses/by/3.0/legalcode

%0 Journal Article %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Nearly Optimal Sparse Polynomial Multiplication : %G eng %U http://hdl.handle.net/21.11116/0000-0007-567A-0 %R 10.1109/TIT.2020.2989385 %7 2020 %D 2020 %J IEEE Transactions on Information Theory %V 66 %N 11 %& 7231 %P 7231 - 7236 %I IEEE %C Piscataway, NJ %@ false

%0 Conference Proceedings %A Neuen, Daniel %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Hypergraph Isomorphism for Groups with Restricted Composition Factors : %G eng %U http://hdl.handle.net/21.11116/0000-0007-6DCA-C %R 10.4230/LIPIcs.ICALP.2020.88 %U urn:nbn:de:0030-drops-124959 %D 2020 %B 47th International Colloquium on Automata, Languages, and Programming %Z date of event: 2020-07-08 - 2020-07-11 %C Saarbr&#252;cken, Germany (Virtual Conference) %B 47th International Colloquium on Automata, Languages, and Programming %E Czumaj, Artur; Dawa, Anuj; Merelli, Emanuela %Z sequence number: 88 %I Schloss Dagstuhl %@ 978-3-95977-138-2 %B Leibniz International Proceedings in Informatics %N 168 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/12495/https://creativecommons.org/licenses/by/3.0/legalcode

%0 Journal Article %A Oh, Eunjin %A Ahn, Hee-Kap %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon : %G eng %U http://hdl.handle.net/21.11116/0000-0006-8E04-6 %R 10.1007/s00454-019-00063-4 %7 2019 %D 2020 %J Discrete & Computational Geometry %V 63 %N 2 %& 418 %P 418 - 454 %I Springer %@ false

%0 Journal Article %A Oulasvirta, Antti %A Dayama, Niraj Ramesh %A Shiripour, Morteza %A John, Maximilian %A Karrenbauer, Andreas %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Combinatorial Optimization of Graphical User Interface Designs : %G eng %U http://hdl.handle.net/21.11116/0000-0006-99BA-C %R 10.1109/JPROC.2020.2969687 %7 2020 %D 2020 %J Proceedings of the IEEE %O Proc. IEEE %V 108 %N 3 %& 434 %P 434 - 464 %I IEEE %C New York, N.Y. %@ false

%0 Report %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-9369-D %U https://arxiv.org/abs/2005.06511 %D 2020 %X We study the problem of allocating a set of indivisible goods among agents with subadditive valuations in a fair and efficient manner. Envy-Freeness up to any good (EFX) is the most compelling notion of fairness in the context of indivisible goods. Although the existence of EFX is not known beyond the simple case of two agents with subadditive valuations, some good approximations of EFX are known to exist, namely $\tfrac{1}{2}$-EFX allocation and EFX allocations with bounded charity. Nash welfare (the geometric mean of agents' valuations) is one of the most commonly used measures of efficiency. In case of additive valuations, an allocation that maximizes Nash welfare also satisfies fairness properties like Envy-Free up to one good (EF1). Although there is substantial work on approximating Nash welfare when agents have additive valuations, very little is known when agents have subadditive valuations. In this paper, we design a polynomial-time algorithm that outputs an allocation that satisfies either of the two approximations of EFX as well as achieves an $\mathcal{O}(n)$ approximation to the Nash welfare. Our result also improves the current best-known approximation of $\mathcal{O}(n \log n)$ and $\mathcal{O}(m)$ to Nash welfare when agents have submodular and subadditive valuations, respectively. Furthermore, our technique also gives an $\mathcal{O}(n)$ approximation to a family of welfare measures, $p$-mean of valuations for $p\in (-\infty, 1]$, thereby also matching asymptotically the current best known approximation ratio for special cases like $p =-\infty$ while also retaining the fairness properties. %K Computer Science, Computer Science and Game Theory, cs.GT,

%0 Conference Proceedings %A Ray Chaudhury, Bhaskar %A Garg, Jugal %A Mehlhorn, Kurt %+ 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 EFX Exists for Three Agents : %G eng %U http://hdl.handle.net/21.11116/0000-0007-223A-2 %R 10.1145/3391403.3399511 %D 2020 %B 21st ACM Conference on Economics and Computation %Z date of event: 2020-07-13 - 2020-07-17 %C Virtual Event, Hungary %B EC '20 %E Bir&#243;, P&#233;ter; Hartline, Jason %P 1 - 19 %I ACM %@ 978-1-4503-7975-5

%0 Report %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-9361-5 %U https://arxiv.org/abs/2008.02753 %D 2020 %X We study the fair division problem of allocating a mixed manna under additively separable piecewise linear concave (SPLC) utilities. A mixed manna contains goods that everyone likes and bads that everyone dislikes, as well as items that some like and others dislike. The seminal work of Bogomolnaia et al. [Econometrica'17] argue why allocating a mixed manna is genuinely more complicated than a good or a bad manna, and why competitive equilibrium is the best mechanism. They also provide the existence of equilibrium and establish its peculiar properties (e.g., non-convex and disconnected set of equilibria even under linear utilities), but leave the problem of computing an equilibrium open. This problem remained unresolved even for only bad manna under linear utilities. Our main result is a simplex-like algorithm based on Lemke's scheme for computing a competitive allocation of a mixed manna under SPLC utilities, a strict generalization of linear. Experimental results on randomly generated instances suggest that our algorithm will be fast in practice. The problem is known to be PPAD-hard for the case of good manna, and we also show a similar result for the case of bad manna. Given these PPAD-hardness results, designing such an algorithm is the only non-brute-force (non-enumerative) option known, e.g., the classic Lemke-Howson algorithm (1964) for computing a Nash equilibrium in a 2-player game is still one of the most widely used algorithms in practice. Our algorithm also yields several new structural properties as simple corollaries. We obtain a (constructive) proof of existence for a far more general setting, membership of the problem in PPAD, rational-valued solution, and odd number of solutions property. The last property also settles the conjecture of Bogomolnaia et al. in the affirmative. %K Computer Science, Computer Science and Game Theory, cs.GT,Computer Science, Computational Complexity, cs.CC,Computer Science, Discrete Mathematics, cs.DM,Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Multiagent Systems, cs.MA

%0 Report %A Ray Chaudhury, Bhaskar %A Garg, Jugal %A Mehlhorn, Kurt %+ 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 EFX exists for three agents : %G eng %U http://hdl.handle.net/21.11116/0000-0006-AF99-9 %U http://arxiv.org/abs/2002.05119 %D 2020 %X We study the problem of distributing a set of indivisible items among agents with additive valuations in a $\mathit{fair}$ manner. The fairness notion under consideration is Envy-freeness up to any item (EFX). Despite significant efforts by many researchers for several years, the existence of EFX allocations has not been settled beyond the simple case of two agents. In this paper, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture by Caragiannis et al. by showing an instance with three agents for which there is a partial EFX allocation (some items are not allocated) with higher Nash welfare than that of any complete EFX allocation. %K Computer Science, Computer Science and Game Theory, cs.GT,

%0 Conference Proceedings %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-0006-AF89-B %R 10.1137/1.9781611975994.162 %D 2020 %B 31st Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2020-01-05 - 2020-01-08 %C Salt Lake City, UT, USA %B Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms %E Chawla, Shuchi %P 2658 - 2672 %I SIAM %@ 978-1-61197-599-4

%0 Conference Proceedings %A Rosenbaum, Will %A Suomela, Jukka %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems Share on : %G eng %U http://hdl.handle.net/21.11116/0000-0007-9A54-D %R 10.1145/3382734.3405721 %D 2020 %B 39th Symposium on Principles of Distributed Computing %Z date of event: 2020-08-03 - 2020-08-07 %C Virtual Event, Italy %B PODC '20 %P 89 - 98 %I ACM %@ 9781450375825}

%0 Report %A Rosenbaum, Will %A Suomela, Jukka %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems : %G eng %U http://hdl.handle.net/21.11116/0000-0007-98C0-4 %U https://arxiv.org/abs/1907.08160 %D 2020 %X Consider a graph problem that is locally checkable but not locally solvable: given a solution we can check that it is feasible by verifying all constant-radius neighborhoods, but to find a solution each node needs to explore the input graph at least up to distance $\Omega(\log n)$ in order to produce its output. We consider the complexity of such problems from the perspective of volume: how large a subgraph does a node need to see in order to produce its output. We study locally checkable graph problems on bounded-degree graphs. We give a number of constructions that exhibit tradeoffs between deterministic distance, randomized distance, deterministic volume, and randomized volume: - If the deterministic distance is linear, it is also known that randomized distance is near-linear. In contrast, we show that there are problems with linear deterministic volume but only logarithmic randomized volume. - We prove a volume hierarchy theorem for randomized complexity: among problems with linear deterministic volume complexity, there are infinitely many distinct randomized volume complexity classes between $\Omega(\log n)$ and $O(n)$. This hierarchy persists even when restricting to problems whose randomized and deterministic distance complexities are $\Theta(\log n)$. - Similar hierarchies exist for polynomial distance complexities: for any $k, \ell \in N$ with $k \leq \ell$, there are problems whose randomized and deterministic distance complexities are $\Theta(n^{1/\ell})$, randomized volume complexities are $\Theta(n^{1/k})$, and whose deterministic volume complexities are $\Theta(n)$. Additionally, we consider connections between our volume model and massively parallel computation (MPC). We give a general simulation argument that any volume-efficient algorithm can be transformed into a space-efficient MPC algorithm. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC

%0 Conference Proceedings %A Roth, Marc %A Wellnitz, Philip %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory : %G eng %U http://hdl.handle.net/21.11116/0000-0005-8665-2 %R 10.1137/1.9781611975994.133 %D 2020 %B 31st Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2020-01-05 - 2020-01-08 %C Salt Lake City, UT, USA %B Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms %E Chawla, Shuchi %P 2161 - 2180 %I SIAM %@ 978-1-61197-599-4

%0 Report %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-0007-8CA1-5 %U https://arxiv.org/abs/2011.03433 %D 2020 %X Given a graph property $\Phi$, we consider the problem $\mathtt{EdgeSub}(\Phi)$, where the input is a pair of a graph $G$ and a positive integer $k$, and the task is to decide whether $G$ contains a $k$-edge subgraph that satisfies $\Phi$. Specifically, we study the parameterized complexity of $\mathtt{EdgeSub}(\Phi)$ and of its counting problem $\#\mathtt{EdgeSub}(\Phi)$ with respect to both approximate and exact counting. We obtain a complete picture for minor-closed properties $\Phi$: the decision problem $\mathtt{EdgeSub}(\Phi)$ always admits an FPT algorithm and the counting problem $\#\mathtt{EdgeSub}(\Phi)$ always admits an FPTRAS. For exact counting, we present an exhaustive and explicit criterion on the property $\Phi$ which, if satisfied, yields fixed-parameter tractability and otherwise $\#\mathsf{W[1]}$-hardness. Additionally, most of our hardness results come with an almost tight conditional lower bound under the so-called Exponential Time Hypothesis, ruling out algorithms for $\#\mathtt{EdgeSub}(\Phi)$ that run in time $f(k)\cdot|G|^{o(k/\log k)}$ for any computable function $f$. As a main technical result, we gain a complete understanding of the coefficients of toroidal grids and selected Cayley graph expanders in the homomorphism basis of $\#\mathtt{EdgeSub}(\Phi)$. This allows us to establish hardness of exact counting using the Complexity Monotonicity framework due to Curticapean, Dell and Marx (STOC'17). Our methods can also be applied to a parameterized variant of the Tutte Polynomial $T^k_G$ of a graph $G$, to which many known combinatorial interpretations of values of the (classical) Tutte Polynomial can be extended. As an example, $T^k_G(2,1)$ corresponds to the number of $k$-forests in the graph $G$. Our techniques allow us to completely understand the parametrized complexity of computing the evaluation of $T^k_G$ at every pair of rational coordinates $(x,y)$. %K Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS

%0 Report %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-8C60-F %U https://arxiv.org/abs/2004.06595 %D 2020 %X Given a graph property $\Phi$, the problem $\#\mathsf{IndSub}(\Phi)$ asks, on input a graph $G$ and a positive integer $k$, to compute the number of induced subgraphs of size $k$ in $G$ that satisfy $\Phi$. The search for explicit criteria on $\Phi$ ensuring that $\#\mathsf{IndSub}(\Phi)$ is hard was initiated by Jerrum and Meeks [J. Comput. Syst. Sci. 15] and is part of the major line of research on counting small patterns in graphs. However, apart from an implicit result due to Curticapean, Dell and Marx [STOC 17] proving that a full classification into "easy" and "hard" properties is possible and some partial results on edge-monotone properties due to Meeks [Discret. Appl. Math. 16] and D\"orfler et al. [MFCS 19], not much is known. In this work, we fully answer and explicitly classify the case of monotone, that is subgraph-closed, properties: We show that for any non-trivial monotone property $\Phi$, the problem $\#\mathsf{IndSub}(\Phi)$ cannot be solved in time $f(k)\cdot |V(G)|^{o(k/ {\log^{1/2}(k)})}$ for any function $f$, unless the Exponential Time Hypothesis fails. By this, we establish that any significant improvement over the brute-force approach is unlikely; in the language of parameterized complexity, we also obtain a $\#\mathsf{W}[1]$-completeness result. %K Computer Science, Computational Complexity, cs.CC