Current Year

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

%0 Conference Proceedings %A 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