Last Year

%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 SETH-Based Lower Bounds for Subset Sum and Bicriteria Path : %G eng %U http://hdl.handle.net/21.11116/0000-0002-9E12-8 %R 10.1137/1.9781611975482.3 %D 2019 %B 30th Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2019-01-06 - 2019-01-09 %C San Diego, CA, USA %B Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms %E Chan, Timothy M. %P 41 - 57 %I SIAM %@ 978-1-61197-548-2

%0 Report %A Abdulaziz, Mohammad %A Mehlhorn, Kurt %A Nipkow, Tobias %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Trustworthy Graph Algorithms : %G eng %U http://hdl.handle.net/21.11116/0000-0005-4FA8-6 %U http://arxiv.org/abs/1907.04065 %D 2019 %X The goal of the LEDA project was to build an easy-to-use and extendable library of correct and efficient data structures, graph algorithms and geometric algorithms. We report on the use of formal program verification to achieve an even higher level of trustworthiness. Specifically, we report on an ongoing and largely finished verification of the blossom-shrinking algorithm for maximum cardinality matching. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Logic in Computer Science, cs.LO,Computer Science, Software Engineering, cs.SE

%0 Conference Proceedings %A Abdulaziz, Mohammad %A Mehlhorn, Kurt %A Nipkow, Tobias %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Trustworthy Graph Algorithms : %G eng %U http://hdl.handle.net/21.11116/0000-0005-4F89-9 %R 10.4230/LIPIcs.MFCS.2019.1 %U urn:nbn:de:0030-drops-109456 %D 2019 %B 44th International Symposium on Mathematical Foundations of Computer Science %Z date of event: 2019-08-26 - 2019-08-30 %C Aachen, Germany %B 44th International Symposium on Mathematical Foundations of Computer Science %E Rossmanith, Peter; Heggernes, Pinar; Katoen, Joost-Pieter %Z sequence number: 1 %I Schloss Dagstuhl %@ 978-3-95977-117-7 %B Leibniz International Proceedings in Informatics %N 138 %@ false %U http://drops.dagstuhl.de/opus/volltexte/2019/10945/http://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Journal Article %A Afshani, Peyman %A Agrawal, Manindra %A Doerr, Benjamin %A Doerr, Carola %A Larsen, Kasper Green %A Mehlhorn, Kurt %+ External Organizations External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T The Query Complexity of a Permutation-based Variant of Mastermind : %G eng %U http://hdl.handle.net/21.11116/0000-0002-FE83-C %R 10.1016/j.dam.2019.01.007 %7 2019 %D 2019 %J Discrete Applied Mathematics %V 260 %& 28 %P 28 - 50 %I North-Holland %C Amsterdam %@ false

%0 Journal Article %A Ahn, Hee-Kap %A Oh, E. %A Schlipf, Lena %A Stehn, Fabian %A Strash, Darren %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T On Romeo and Juliet Problems: Minimizing Distance-to-Sight : %G eng %U http://hdl.handle.net/21.11116/0000-0004-E582-6 %R 10.1016/j.comgeo.2019.07.003 %7 2019 %D 2019 %J Computational Geometry: Theory and Applications %V 84 %& 12 %P 12 - 21 %I Elsevier %C Amsterdam %@ false

%0 Journal Article %A Ahn, Hee-Kap %A Ahn, Taehoon %A Bae, Sang Won %A Choi, Jongmin %A Kim, Mincheol %A Oh, Eunjin %A Shin, Chan-Su %A Yoon, Sang Duk %+ External Organizations External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Minimum-width Annulus with Outliers: Circular, Square, and Rectangular Cases : %G eng %U http://hdl.handle.net/21.11116/0000-0003-4FD4-6 %R 10.1016/j.ipl.2019.01.004 %7 2019 %D 2019 %J Information Processing Letters %V 145 %& 16 %P 16 - 23 %I Elsevier %C Amsterdam %@ false

%0 Report %A Akrami, Hannaneh %A Mehlhorn, Kurt %A Odland, Tommy %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Ratio-Balanced Maximum Flows : %G eng %U http://hdl.handle.net/21.11116/0000-0003-B2FE-6 %U http://arxiv.org/abs/1902.11047 %D 2019 %X When a loan is approved for a person or company, the bank is subject to \emph{credit risk}; the risk that the lender defaults. To mitigate this risk, a bank will require some form of \emph{security}, which will be collected if the lender defaults. Accounts can be secured by several securities and a security can be used for several accounts. The goal is to fractionally assign the securities to the accounts so as to balance the risk. This situation can be modelled by a bipartite graph. We have a set $S$ of securities and a set $A$ of accounts. Each security has a \emph{value} $v_i$ and each account has an \emph{exposure} $e_j$. If a security $i$ can be used to secure an account $j$, we have an edge from $i$ to $j$. Let $f_{ij}$ be part of security $i$'s value used to secure account $j$. We are searching for a maximum flow that send at most $v_i$ units out of node $i \in S$ and at most $e_j$ units into node $j \in A$. Then $s_j = e_j - \sum_i f_{ij}$ is the unsecured part of account $j$. We are searching for the maximum flow that minimizes $\sum_j s_j^2/e_j$. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Journal Article %A Akrami, Hannaneh %A Mehlhorn, Kurt %A Odland, Tommy %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Ratio-Balanced Maximum Flows : %G eng %U http://hdl.handle.net/21.11116/0000-0004-8FF0-C %R 10.1016/j.ipl.2019.06.003 %7 2019 %D 2019 %J Information Processing Letters %V 150 %& 13 %P 13 - 17 %I Elsevier %@ false

%0 Journal Article %A Amiri, Saeed Akhoondian %A Kreutzer, Stephan %A Marx, Dániel %A Rabinovich, Roman %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Routing with Congestion in Acyclic Digraphs : %G eng %U http://hdl.handle.net/21.11116/0000-0004-B836-0 %R 10.1016/j.ipl.2019.105836 %7 2019 %D 2019 %J Information Processing Letters %V 151 %Z sequence number: 105836 %I Elsevier %@ false

%0 Conference Proceedings %A Amiri, Saeed Akhoondian %A Dudycz, Szymon %A Parham, Mahmoud %A Schmid, Stefan %A Wiederrecht, Sebastian %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T On Polynomial-Time Congestion-Free Software-Defined Network Updates : %G eng %U http://hdl.handle.net/21.11116/0000-0004-B83C-A %R 10.23919/IFIPNetworking.2019.8816833 %D 2019 %B IFIP Networking Conference %Z date of event: 2019-05-20 - 2019-05-22 %C Warsaw, Poland %B IFIP Networking Conference %I IEEE

%0 Journal Article %A Amiri, Saeed Akhoondian %A Schmid, Stefan %A Siebertz, Sebastian %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Distributed Dominating Set Approximations beyond Planar Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0004-8335-C %R 10.1145/3326170 %7 2019 %D 2019 %J ACM Transactions on Algorithms %V 15 %N 3 %Z sequence number: 39 %I ACM %C New York, NY %@ false

%0 Journal Article %A Antoniadis, Antonios %A Huang, Chien-Chung %A Ott, Sebastian %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State : %G eng %U http://hdl.handle.net/21.11116/0000-0004-AAC7-C %R 10.1007/s00453-019-00596-3 %7 2019 %D 2019 %J Algorithmica %V 81 %N 9 %& 3725 %P 3725 - 3745 %I Springer %C New York, NY %@ false

%0 Journal Article %A Antoniadis, Antonios %A Barcelo, Neal %A Nugent, Michael %A Pruhs, Kirk %A Scquizzato, Michele %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T A o(n)-Competitive Deterministic Algorithm for Online Matching on a Line : %G eng %U http://hdl.handle.net/21.11116/0000-0003-A7DA-B %R 10.1007/s00453-019-00565-w %7 2019 %D 2019 %J Algorithmica %V 81 %N 7 %& 2917 %P 2917 - 2933 %I Springer %C New York, NY %@ false

%0 Conference Proceedings %A Antoniadis, Antonios %A Fleszar, Krzysztof %A Hoeksma, Ruben %A Schewior, Kevin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T A PTAS for Euclidean TSP with Hyperplane Neighborhoods : %G eng %U http://hdl.handle.net/21.11116/0000-0002-9F3A-B %R 10.1137/1.9781611975482.67 %D 2019 %B 30th Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2019-01-06 - 2019-01-09 %C San Diego, CA, USA %B Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms %E Chan, Timothy M. %P 1089 - 1105 %I SIAM %@ 978-1-61197-548-2

%0 Conference Proceedings %A Antoniadis, Antonios %A Biermeier, Felix %A Cristi, Andrés %A Damerius, Christoph %A Hoeksma, Ruben %A Kaaser, Dominik %A Kling, Peter %A Nölke, ukas %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations External Organizations External Organizations External Organizations %T On the Complexity of Anchored Rectangle Packing : %G eng %U http://hdl.handle.net/21.11116/0000-0007-317F-4 %R 10.4230/LIPIcs.ESA.2019.8 %U urn:nbn:de:0030-drops-111297 %D 2019 %B 27th Annual European Symposium on Algorithms %Z date of event: 2019-09-09 - 2019-09-11 %C Munich/Garching, Germany %B 27th Annual European Symposium on Algorithms %E Bender, Michael A.; Svensson, Ola; German, Grzegorz %P 1 - 14 %Z sequence number: 268 %I Schloss Dagstuhl %@ 978-3-95977-124-5 %B Leibniz International Proceedings in Informatics %N 144 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2019/11129/https://creativecommons.org/licenses/by/3.0/legalcode

%0 Journal Article %A Ballard, Grey %A Ikenmeyer, Christian %A Landsberg, J. M. %A Ryder, Nick %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T The Geometry of Rank Decompositions of Matrix Multiplication II: 3 x 3 Matrices : %G eng %U http://hdl.handle.net/21.11116/0000-0002-AB17-4 %R 10.1016/j.jpaa.2018.10.014 %7 2018 %D 2019 %J Journal of Pure and Applied Algebra %O J. Pure Appl. Algebra %V 223 %N 8 %& 3205 %P 3205 - 3224 %I North-Holland %C Amsterdam %@ false

%0 Conference Proceedings %A Balliu, Alkida %A Hirvonen, Juho %A Lenzen, Christoph %A Olivetti, Dennis %A Suomela, Jukka %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Locality of Not-so-Weak Coloring : %G eng %U http://hdl.handle.net/21.11116/0000-0005-1BF2-C %R 10.1007/978-3-030-24922-9_3 %D 2019 %B 26th International Colloquium on Structural Information and Communication Complexity %Z date of event: 2019-07-01 - 2019-07-04 %C L’Aquila, Italy %B Structural Information and Communication Complexity %E Censor-Hillel, Keren; Flammini, Michele %P 37 - 51 %I Springer %@ 978-3-030-24921-2 978-3-030-24922-9 %B Lecture Notes in Computer Science %N 11639

%0 Report %A Balliu, Alkida %A Hirvonen, Juho %A Lenzen, Christoph %A Olivetti, Dennis %A Suomela, Jukka %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Locality of Not-So-Weak Coloring : %G eng %U http://hdl.handle.net/21.11116/0000-0003-B39F-0 %U http://arxiv.org/abs/1904.05627 %D 2019 %X Many graph problems are locally checkable: a solution is globally feasible if it looks valid in all constant-radius neighborhoods. This idea is formalized in the concept of locally checkable labelings (LCLs), introduced by Naor and Stockmeyer (1995). Recently, Chang et al. (2016) showed that in bounded-degree graphs, every LCL problem belongs to one of the following classes: - "Easy": solvable in $O(\log^* n)$ rounds with both deterministic and randomized distributed algorithms. - "Hard": requires at least $\Omega(\log n)$ rounds with deterministic and $\Omega(\log \log n)$ rounds with randomized distributed algorithms. Hence for any parameterized LCL problem, when we move from local problems towards global problems, there is some point at which complexity suddenly jumps from easy to hard. For example, for vertex coloring in $d$-regular graphs it is now known that this jump is at precisely $d$ colors: coloring with $d+1$ colors is easy, while coloring with $d$ colors is hard. However, it is currently poorly understood where this jump takes place when one looks at defective colorings. To study this question, we define $k$-partial $c$-coloring as follows: nodes are labeled with numbers between $1$ and $c$, and every node is incident to at least $k$ properly colored edges. It is known that $1$-partial $2$-coloring (a.k.a. weak $2$-coloring) is easy for any $d \ge 1$. As our main result, we show that $k$-partial $2$-coloring becomes hard as soon as $k \ge 2$, no matter how large a $d$ we have. We also show that this is fundamentally different from $k$-partial $3$-coloring: no matter which $k \ge 3$ we choose, the problem is always hard for $d = k$ but it becomes easy when $d \gg k$. The same was known previously for partial $c$-coloring with $c \ge 4$, but the case of $c < 4$ was open. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC,Computer Science, Computational Complexity, cs.CC

%0 Conference Proceedings %A Ban, Frank %A Bhattiprolu, Vijay %A Bringmann, Karl %A Kolev, Pavel %A Lee, Euiwoong %A Woodruff, David %+ 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 A PTAS for l_p-Low Rank Approximation : %G eng %U http://hdl.handle.net/21.11116/0000-0002-9E0E-E %R 10.1137/1.9781611975482.47 %D 2019 %B 30th Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2019-01-06 - 2019-01-09 %C San Diego, CA, USA %B Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms %E Chan, Timothy M. %P 747 - 766 %I SIAM %@ 978-1-61197-548-2

%0 Journal Article %A Becchetti, Luca %A Clementi, Andrea %A Natale, Emanuele %A Pasquale, Francesco %A Posta, Gustavo %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Self-Stabilizing Repeated Balls-into-Bins : %G eng %U http://hdl.handle.net/21.11116/0000-0002-F6C1-E %R 10.1007/s00446-017-0320-4 %7 2017 %D 2019 %J Distributed Computing %V 32 %N 1 %& 59 %P 59 - 68 %I Springer International %C Berlin %@ false

%0 Journal Article %A Becker, Ruben %A Bonifaci, Vincenzo %A Karrenbauer, Andreas %A Kolev, Pavel %A Mehlhorn, Kurt %+ Algorithms and Complexity, 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Two Results on Slime Mold Computations : %G eng %U http://hdl.handle.net/21.11116/0000-0002-A3AE-2 %R 10.1016/j.tcs.2018.08.027 %7 2018 %D 2019 %X In this paper, we present two results on slime mold computations. The first one treats a biologically-grounded model, originally proposed by biologists analyzing the behavior of the slime mold Physarum polycephalum. This primitive organism was empirically shown by Nakagaki et al. to solve shortest path problems in wet-lab experiments (Nature'00). We show that the proposed simple mathematical model actually generalizes to a much wider class of problems, namely undirected linear programs with a non-negative cost vector. For our second result, we consider the discretization of a biologically-inspired model. This model is a directed variant of the biologically-grounded one and was never claimed to describe the behavior of a biological system. Straszak and Vishnoi showed that it can $\epsilon$-approximately solve flow problems (SODA'16) and even general linear programs with positive cost vector (ITCS'16) within a finite number of steps. We give a refined convergence analysis that improves the dependence on $\epsilon$ from polynomial to logarithmic and simultaneously allows to choose a step size that is independent of $\epsilon$. Furthermore, we show that the dynamics can be initialized with a more general set of (infeasible) starting points. %K Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Dynamical Systems, math.DS,Mathematics, Optimization and Control, math.OC, Physics, Biological Physics, physics.bio-ph %J Theoretical Computer Science %V 773 %& 79 %P 79 - 106 %I Elsevier %C Amsterdam %@ false

%0 Report %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-1C65-B %U http://arxiv.org/abs/1909.09002 %D 2019 %X In many models for large-scale computation, decomposition of the problem is key to efficient algorithms. For distance-related graph problems, it is often crucial that such a decomposition results in clusters of small diameter, while the probability that an edge is cut by the decomposition scales linearly with the length of the edge. There is a large body of literature on low diameter graph decomposition with small edge cutting probabilities, with all existing techniques heavily building on single source shortest paths (SSSP) computations. Unfortunately, in many theoretical models for large-scale computations, the SSSP task constitutes a complexity bottleneck. Therefore, it is desirable to replace exact SSSP computations with approximate ones. However this imposes a fundamental challenge since the existing constructions of such decompositions inherently rely on the subtractive form of the triangle inequality. The current paper overcomes this obstacle by developing a technique termed blurry ball growing. By combining this technique with a clever algorithmic idea of Miller et al. (SPAA 13), we obtain a construction of low diameter decompositions with small edge cutting probabilities which replaces exact SSSP computations by (a small number of) approximate ones. The utility of our approach is showcased by deriving efficient algorithms that work in the Congest, PRAM, and semi-streaming models of computation. As an application, we obtain metric tree embedding algorithms in the vein of Bartal (FOCS 96) whose computational complexities in these models are optimal up to polylogarithmic factors. Our embeddings have the additional useful property that the tree can be mapped back to the original graph such that each edge is "used" only O(log n) times, which is of interest for capacitated problems and simulating Congest algorithms on the tree into which the graph is embedded. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC

%0 Conference Proceedings %A Becker, Ruben %A Emek, Yuval %A Ghaffari, Mohsen %A Lenzen, C. %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Distributed Algorithms for Low Stretch Spanning Trees : %G eng %U http://hdl.handle.net/21.11116/0000-0005-1C52-0 %R 10.4230/LIPIcs.DISC.2019.4 %U urn:nbn:de:0030-drops-113116 %D 2019 %B 33rd International Symposiumon Distributed Computing %Z date of event: 2019-10-14 - 2019-10-18 %C Budapest, Hungary %B 33rd International Symposiumon Distributed Computing %E Suomela, Jukka %P 1 - 14 %Z sequence number: 4 %I Schloss Dagstuhl %@ 978-3-95977-126-9 %B Leibniz International Proceedings in Informatics %N 146 %@ false %U http://drops.dagstuhl.de/opus/volltexte/2019/11311http://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Journal Article %A Bei, Xiaohui %A Garg, Jugal %A Hoefer, Martin %A Mehlhorn, Kurt %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Earning and Utility Limits in Fisher Markets : %G eng %U http://hdl.handle.net/21.11116/0000-0005-4F7A-B %R 10.1145/3340234 %7 2019 %D 2019 %J ACM Transactions on Economics and Computation %O TEAC %V 7 %N 2 %Z sequence number: 10 %I ACM %C New York, NY

%0 Journal Article %A Beyersdorff, Olaf %A Chew, Leroy %A Sreenivasaiah, Karteek %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Game Characterisation of Tree-like Q-Resolution Size : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-5F80-F %R 10.1016/j.jcss.2016.11.011 %7 2017 %D 2019 %J Journal of Computer and System Sciences %V 104 %& 82 %P 82 - 101 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A Bhargava, Vishwas %A Bl&#228;ser, Markus %A Jindal, Gorav %A Pandey, Anurag %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials : %G eng %U http://hdl.handle.net/21.11116/0000-0002-ABAD-B %R 10.1137/1.9781611975482.41 %D 2019 %B 30th Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2019-01-06 - 2019-01-09 %C San Diego, CA, USA %B Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms %E Chan, Timothy M. %P 647 - 661 %I SIAM %@ 978-1-61197-548-2

%0 Report %A Bl&#228;ser, Markus %A Ikenmeyer, Christian %A Lysikov, Vladimir %A Pandey, Anurag %A Schreyer, Frank-Olaf %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory : %G eng %U http://hdl.handle.net/21.11116/0000-0005-1D77-6 %U http://arxiv.org/abs/1911.02534 %D 2019 %X We study the variety membership testing problem in the case when the variety is given as an orbit closure and the ambient space is the set of all 3-tensors. The first variety that we consider is the slice rank variety, which consists of all 3-tensors of slice rank at most $r$. We show that the membership testing problem for the slice rank variety is $\NP$-hard. While the slice rank variety is a union of orbit closures, we define another variety, the minrank variety, expressible as a single orbit closure. Our next result is the $\NP$-hardness of membership testing in the minrank variety, hence we establish the $\NP$-hardness of the orbit closure containment problem for 3-tensors. Algebraic natural proofs were recently introduced by Forbes, Shpilka and Volk and independently by Grochow, Kumar, Saks and Saraf. Bl\"aser et al. gave a version of an algebraic natural proof barrier for the matrix completion problem which relies on $\coNP \subseteq \exists \BPP$. It implied that constructing equations for the corresponding variety should be hard. We generalize their approach to work with any family of varieties for which the membership problem is $\NP$-hard and for which we can efficiently generate a dense subset. Therefore, a similar barrier holds for the slice rank and the minrank varieties, too. This allows us to set up the slice rank and the minrank varieties as a test-bed for geometric complexity theory (GCT). We determine the stabilizers of the tensors that generate the orbit closures of the two varieties and prove that these tensors are almost characterized by their symmetries. We prove several nontrivial equations for both the varieties using different GCT methods. Many equations also work in the regime where membership testing in the slice rank or minrank varieties is $\NP$-hard. We view this as a promising sign that the GCT approach might indeed be successful. %K Computer Science, Computational Complexity, cs.CC,Mathematics, Algebraic Geometry, math.AG,Mathematics, Representation Theory, math.RT

%0 Journal Article %A Boczkowski, Lucas %A Korman, Amos %A Natale, Emanuele %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits : %G eng %U http://hdl.handle.net/21.11116/0000-0003-B2F2-2 %R 10.1007/s00446-018-0330-x %7 2018 %D 2019 %J Distributed Computing %V 32 %N 3 %& 173 %P 173 - 191 %I Springer International %C Berlin %@ false

%0 Journal Article %A Borassi, Michele %A Natale, Emanuele %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation : %G eng %U http://hdl.handle.net/21.11116/0000-0003-7A10-2 %R 10.1145/3284359 %7 2019 %D 2019 %J Journal of Experimental Algorithmics %V 24 %N 1 %Z sequence number: 1.2 %I ACM %C New York, NY %@ false

%0 Journal Article %A Bressan, Marco %A Leucci, Stefano %A Panconesi, Alessandro %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Motivo: Fast Motif Counting via Succinct Color Coding and Adaptive Sampling : %G eng %U http://hdl.handle.net/21.11116/0000-0005-6A05-F %R 10.14778/3342263.3342640 %7 2019 %D 2019 %J Proccedings of the VLDB Endowment %V 12 %N 11 %& 1651 %P 1651 - 1663 %I ACM %C New York, NY %@ false

%0 Journal Article %A Bringmann, Karl %A Grandoni, Fabrizio %A Saha, Barna %A Vassilevska Williams, Virginia %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product : %G eng %U http://hdl.handle.net/21.11116/0000-0003-A7E4-F %R 10.1137/17M112720X %7 2019 %D 2019 %J SIAM Journal on Computing %V 48 %N 2 %& 481 %P 481 - 512 %I SIAM %C Philadelphia, PA %@ false

%0 Conference Proceedings %A Bringmann, Karl %A Kisfaludi-Bak, S&#225;ndor %A Pilipczuk, Michal %A van Leeuwen, Erik Jan %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T On Geometric Set Cover for Orthants : %G eng %U http://hdl.handle.net/21.11116/0000-0005-2040-E %R 10.4230/LIPIcs.ESA.2019.26 %U urn:nbn:de:0030-drops-111476 %D 2019 %B 27th Annual European Symposium on Algorithms %Z date of event: 2019-09-09 - 2019-09-11 %C Munich/Garching, Germany %B 27th Annual European Symposium on Algorithms %E Bender, Michael A.; Svensson, Ola; German, Grzegorz %P 1 - 18 %Z sequence number: 26 %I Schloss Dagstuhl %@ 978-3-95977-124-5 %B Leibniz International Proceedings in Informatics %N 144 %@ false %U http://drops.dagstuhl.de/opus/volltexte/2019/11147/http://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Conference Proceedings %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-0002-9CFE-1 %R 10.4230/LIPIcs.IPEC.2018.4 %U urn:nbn:de:0030-drops-102050 %D 2019 %B 13th International Symposium on Parameterized and Exact Computation %Z date of event: 2018-08-20 - 2018-08-24 %C Helsinki, Finland %B 13th International Symposium on Parameterized and Exact Computation %E Paul, Christophe; Pilipczuk, Michal %P 1 - 13 %Z sequence number: 4 %I Schloss Dagstuhl %@ 978-3-95977-084-2 %B Leibniz International Proceedings in Informatics %N 115 %U http://drops.dagstuhl.de/opus/volltexte/2019/10205/http://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Journal Article %A Bringmann, Karl %A Keusch, Ralph %A Lengler, Johannes %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Geometric Inhomogeneous Random Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0003-0B00-1 %R 10.1016/j.tcs.2018.08.014 %7 2018 %D 2019 %J Theoretical Computer Science %V 760 %& 35 %P 35 - 54 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A Bringmann, Karl %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fine-Grained Complexity Theory (Tutorial) : %G eng %U http://hdl.handle.net/21.11116/0000-0003-B36E-8 %R 10.4230/LIPIcs.STACS.2019.4 %D 2019 %B 36th Symposium on Theoretical Aspects of Computer Science %Z date of event: 2019-03-13 - 2019-03-16 %C Berlin, Germany %B 36th Symposium on Theoretical Aspects of Computer Science %E Niedermeier, Rolf; Paul, Christophe %P 1 - 7 %Z sequence number: 4 %I Schloss Dagstuhl %@ 978-3-95977-100-9 %B Leibniz International Proceedings in Informatics %N 126 %U http://drops.dagstuhl.de/opus/volltexte/2019/10243/http://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Conference Proceedings %A Bringmann, Karl %A K&#252;nnemann, Marvin %A W&#281;grzycki, Karol %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max : %G eng %U http://hdl.handle.net/21.11116/0000-0002-FC7A-A %R 10.1145/3313276.3316373 %D 2019 %B 51st Annual ACM Symposium on the Theory of Computing %Z date of event: 2019-06-23 - 2019-06-26 %C Phoenix, AZ, USA %B STOC'19 %E Charikar, Moses; Cohen, Edith %P 943 - 954 %I ACM %@ 978-1-4503-6705-9

%0 Report %A Bringmann, Karl %A K&#252;nnemann, Marvin %A W&#281;grzycki, Karol %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max : %G eng %U http://hdl.handle.net/21.11116/0000-0005-3D73-6 %U http://arxiv.org/abs/1907.11078 %D 2019 %X Zwick's $(1+\varepsilon)$-approximation algorithm for the All Pairs Shortest Path (APSP) problem runs in time $\widetilde{O}(\frac{n^\omega}{\varepsilon} \log{W})$, where $\omega \le 2.373$ is the exponent of matrix multiplication and $W$ denotes the largest weight. This can be used to approximate several graph characteristics including the diameter, radius, median, minimum-weight triangle, and minimum-weight cycle in the same time bound. Since Zwick's algorithm uses the scaling technique, it has a factor $\log W$ in the running time. In this paper, we study whether APSP and related problems admit approximation schemes avoiding the scaling technique. That is, the number of arithmetic operations should be independent of $W$; this is called strongly polynomial. Our main results are as follows. - We design approximation schemes in strongly polynomial time $O(\frac{n^\omega}{\varepsilon} \text{polylog}(\frac{n}{\varepsilon}))$ for APSP on undirected graphs as well as for the graph characteristics diameter, radius, median, minimum-weight triangle, and minimum-weight cycle on directed or undirected graphs. - For APSP on directed graphs we design an approximation scheme in strongly polynomial time $O(n^{\frac{\omega + 3}{2}} \varepsilon^{-1} \text{polylog}(\frac{n}{\varepsilon}))$. This is significantly faster than the best exact algorithm. - We explain why our approximation scheme for APSP on directed graphs has a worse exponent than $\omega$: Any improvement over our exponent $\frac{\omega + 3}{2}$ would improve the best known algorithm for Min-Max Product In fact, we prove that approximating directed APSP and exactly computing the Min-Max Product are equivalent. %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 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 %T A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of &#8707;k&#8704;-Quantified First-Order Graph Properties : %G eng %U http://hdl.handle.net/21.11116/0000-0005-1FAF-5 %R 10.4230/LIPIcs.CCC.2019.31 %U urn:nbn:de:0030-drops-108533 %D 2019 %B 34th Computational Complexity Conference %Z date of event: 2019-07-18 - 2019-07-20 %C New Brunswick, NJ, USA %B 34th Computational Complexity Conference %E Shpilka, Amir %P 1 - 27 %Z sequence number: 31 %I Schloss Dagstuhl %@ 978-3-95977-116-0 %B Leibniz International Proceedings in Informatics %N 137 %@ false %U http://drops.dagstuhl.de/opus/volltexte/2019/10853/http://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Conference Proceedings %A Bringmann, Karl %A K&#252;nnemann, Marvin %A Wellnitz, Philip %+ 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 Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts : %G eng %U http://hdl.handle.net/21.11116/0000-0002-9E1F-B %R 10.1137/1.9781611975482.69 %D 2019 %B 30th Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2019-01-06 - 2019-01-09 %C San Diego, CA, USA %B Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms %E Chan, Timothy M. %P 1126 - 1145 %I SIAM %@ 978-1-61197-548-2

%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 Walking the Dog Fast in Practice: Algorithm Engineering of the Fr&#233;chet Distance : %G eng %U http://hdl.handle.net/21.11116/0000-0005-3D76-3 %U http://arxiv.org/abs/1901.01504 %D 2019 %X The Fr\'echet distance provides a natural and intuitive measure for the popular task of computing the similarity of two (polygonal) curves. While a simple algorithm computes it in near-quadratic time, a strongly subquadratic algorithm cannot exist unless the Strong Exponential Time Hypothesis fails. Still, fast practical implementations of the Fr\'echet distance, in particular for realistic input curves, are highly desirable. This has even lead to a designated competition, the ACM SIGSPATIAL GIS Cup 2017: Here, the challenge was to implement a near-neighbor data structure under the Fr\'echet distance. The bottleneck of the top three implementations turned out to be precisely the decision procedure for the Fr\'echet distance. In this work, we present a fast, certifying implementation for deciding the Fr\'echet distance, in order to (1) complement its pessimistic worst-case hardness by an empirical analysis on realistic input data and to (2) improve the state of the art for the GIS Cup challenge. We experimentally evaluate our implementation on a large benchmark consisting of several data sets (including handwritten characters and GPS trajectories). Compared to the winning implementation of the GIS Cup, we obtain running time improvements of up to more than two orders of magnitude for the decision procedure and of up to a factor of 30 for queries to the near-neighbor data structure. %K Computer Science, Computational Geometry, cs.CG

%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 Walking the Dog Fast in Practice: Algorithm Engineering of the Fr&#233;chet Distance : %G eng %U http://hdl.handle.net/21.11116/0000-0003-65C1-1 %R 10.4230/LIPIcs.SoCG.2019.17 %U urn:nbn:de:0030-drops-104219 %D 2019 %B 35th International Symposium on Computational Geometry %Z date of event: 2019-06-18 - 2019-06-21 %C Portland, OR, USA %B 35th International Symposium on Computational Geometry %E Barequet, Gill; Wang, Yusu %P 1 - 21 %Z sequence number: 17 %I Schloss Dagstuhl %@ 978-3-95977-104-7 %B Leibniz International Proceedings in Informatics %N 129 %@ false %U http://drops.dagstuhl.de/opus/volltexte/2019/10421/http://drops.dagstuhl.de/doku/urheberrecht1.html

%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 Fr&#233;chet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability : %G eng %U http://hdl.handle.net/21.11116/0000-0002-9E29-F %R 10.1137/1.9781611975482.180 %D 2019 %B 30th Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2019-01-06 - 2019-01-09 %C San Diego, CA, USA %B Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms %E Chan, Timothy M. %P 2902 - 2921 %I SIAM %@ 978-1-61197-548-2

%0 Conference Proceedings %A Bringmann, Karl %A Ray Chaudhury, Bhaskar %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Polyline Simplification has Cubic Complexity : %G eng %U http://hdl.handle.net/21.11116/0000-0003-65C8-A %R 10.4230/LIPIcs.SoCG.2019.18 %U urn:nbn:de:0030-drops-104224 %D 2019 %B 35th International Symposium on Computational Geometry %Z date of event: 2019-06-18 - 2019-06-21 %C Portland, OR, USA %B 35th International Symposium on Computational Geometry %E Barequet, Gill; Wang, Yusu %P 1 - 16 %Z sequence number: 18 %I Schloss Dagstuhl %@ 978-3-95977-104-7 %B Leibniz International Proceedings in Informatics %N 129 %U http://drops.dagstuhl.de/opus/volltexte/2019/10422/http://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Conference Proceedings %A Buchin, Kevin %A Driemel, Anne %A van de L'Isle, Natasja %A Nusser, Andr&#233; %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T klcluster: Center-based Clustering of Trajectories : %G eng %U http://hdl.handle.net/21.11116/0000-0005-8705-D %R 10.1145/3347146.3359111 %D 2019 %B 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems %Z date of event: 2019-11-05 - 2019-11-08 %C Chicago, IL, USA %B 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems %E Banaei-Kashani, Farnoush; Trajcevski, Goce; G&#252;ting, Ralf Hartmut; Kulik, Lars; Newsam, Shawn %P 496 - 499 %I ACM %@ 978-1-4503-6909-1

%0 Report %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-1C6B-5 %U http://arxiv.org/abs/1911.00267 %D 2019 %X Friedrichs et al. (TC 2018) showed that metastability can be contained when sorting inputs arising from time-to-digital converters, i.e., measurement values can be correctly sorted without resolving metastability using synchronizers first. However, this work left open whether this can be done by small circuits. We show that this is indeed possible, by providing a circuit that sorts Gray code inputs (possibly containing a metastable bit) and has asymptotically optimal depth and size. Our solution utilizes the parallel prefix computation (PPC) framework (JACM 1980). We improve this construction by bounding its fan-out by an arbitrary $f \geq 3$, without affecting depth and increasing circuit size by a small constant factor only. Thus, we obtain the first PPC circuits with asymptotically optimal size, constant fan-out, and optimal depth. To show that applying the PPC framework to the sorting task is feasible, we prove that the latter can, despite potential metastability, be decomposed such that the core operation is associative. We obtain asymptotically optimal metastability-containing sorting networks. We complement these results with simulations, independently verifying the correctness as well as small size and delay of our circuits. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC,Computer Science, Architecture, cs.AR

%0 Conference Proceedings %A Bund, Johannes %A Lenzen, Christoph %A Rosenbaum, Will %+ 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 Fault Tolerant Gradient Clock Synchronization : %G eng %U http://hdl.handle.net/21.11116/0000-0005-1BE3-D %R 10.1145/3293611.3331637 %D 2019 %B ACM Symposium on Principles of Distributed Computing %Z date of event: 2019-07-29 - 2019-08-02 %C Toronto, Canada %B PODC'19 %P 357 - 365 %I ACM %@ 978-1-4503-6217-7

%0 Report %A Bund, Johannes %A Lenzen, Christoph %A Rosenbaum, Will %+ 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 Fault Tolerant Gradient Clock Synchronization : %G eng %U http://hdl.handle.net/21.11116/0000-0003-0CD6-F %U http://arxiv.org/abs/1902.08042 %D 2019 %X Synchronizing clocks in distributed systems is well-understood, both in terms of fault-tolerance in fully connected systems and the dependence of local and global worst-case skews (i.e., maximum clock difference between neighbors and arbitrary pairs of nodes, respectively) on the diameter of fault-free systems. However, so far nothing non-trivial is known about the local skew that can be achieved in topologies that are not fully connected even under a single Byzantine fault. Put simply, in this work we show that the most powerful known techniques for fault-tolerant and gradient clock synchronization are compatible, in the sense that the best of both worlds can be achieved simultaneously. Concretely, we combine the Lynch-Welch algorithm [Welch1988] for synchronizing a clique of $n$ nodes despite up to $f<n/3$ Byzantine faults with the gradient clock synchronization (GCS) algorithm by Lenzen et al. [Lenzen2010] in order to render the latter resilient to faults. As this is not possible on general graphs, we augment an input graph $\mathcal{G}$ by replacing each node by $3f+1$ fully connected copies, which execute an instance of the Lynch-Welch algorithm. We then interpret these clusters as supernodes executing the GCS algorithm, where for each cluster its correct nodes' Lynch-Welch clocks provide estimates of the logical clock of the supernode in the GCS algorithm. By connecting clusters corresponding to neighbors in $\mathcal{G}$ in a fully bipartite manner, supernodes can inform each other about (estimates of) their logical clock values. This way, we achieve asymptotically optimal local skew, granted that no cluster contains more than $f$ faulty nodes, at factor $O(f)$ and $O(f^2)$ overheads in terms of nodes and edges, respectively. Note that tolerating $f$ faulty neighbors trivially requires degree larger than $f$, so this is asymptotically optimal as well. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC,Computer Science, Data Structures and Algorithms, cs.DS

%0 Journal Article %A B&#252;rgisser, Peter %A Ikenmeyer, Christian %A Panova, Greta %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T No Occurrence Obstructions in Geometric Complexity Theory : %G eng %U http://hdl.handle.net/21.11116/0000-0002-72B9-D %R 10.1090/jams/908 %7 2018 %D 2019 %J Journal of the American Mathematical Society %O J. Amer. Math. Soc. %V 32 %& 163 %P 163 - 193 %I The Society %C Providence, R.I. %@ false

%0 Conference Proceedings %A Chalermsook, Parinya %A Schmid, Andreas %A Uniyal, Sumedha %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A Tight Extremal Bound on the Lov&#225;sz Cactus Number in Planar Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0002-E5D6-A %R 10.4230/LIPIcs.STACS.2019.19 %D 2019 %B 36th Symposium on Theoretical Aspects of Computer Science %Z date of event: 2019-03-13 - 2019-03-16 %C Berlin, Germany %B 36th Symposium on Theoretical Aspects of Computer Science %E Niedermeier, Rolf; Paul, Christophe %P 1 - 14 %Z sequence number: 19 %I Schloss Dagstuhl %@ 978-3-95977-100-9 %B Leibniz International Proceedings in Informatics %N 126 %U http://drops.dagstuhl.de/doku/urheberrecht1.htmlhttp://drops.dagstuhl.de/opus/volltexte/2019/10258/

%0 Journal Article %A Chandran, L. Sunil %A Issac, Davis %A Zhou, Sanming %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Hadwiger's Conjecture for Squares of 2-Trees : %G eng %U http://hdl.handle.net/21.11116/0000-0002-9E5B-7 %R 10.1016/j.ejc.2018.10.003 %7 2018 %D 2019 %J European Journal of Combinatorics %V 76 %& 159 %P 159 - 174 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A Chen, Lin %A Eberle, Franziska %A Megow, Nicole %A Schewior, Kevin %A Stein, Clifford %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A General Framework for Handling Commitment in Online Admission Control : %G eng %U http://hdl.handle.net/21.11116/0000-0002-F4CC-5 %D 2019 %B 20th Conference on Integer Programming and Combinatorial Optimization %Z date of event: 2019-05-22 - 2019-05-24 %C Ann Arbor, MI, USA %B Integer Programming and Combinatorial Optimization %I Springer

%0 Journal Article %A Chen, Ning %A Hoefer, Martin %A K&#252;nnemann, Marvin %A Lin, Chengyu %A Miao, Peihan %+ 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 Secretary Markets with Local Information : %G eng %U http://hdl.handle.net/21.11116/0000-0002-A90C-3 %R 10.1007/s00446-018-0327-5 %7 2019 %D 2019 %J Distributed Computing %V 32 %N 5 %& 361 %P 361 - 378 %I Springer International %C Berlin %@ false

%0 Conference Proceedings %A Cheung, Yun Kuen %A Hoefer, Martin %A Nakhe, Paresh %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Tracing Equilibrium in Dynamic Markets via Distributed Adaptation : %G eng %U http://hdl.handle.net/21.11116/0000-0002-E5FE-E %U http://dl.acm.org/citation.cfm?id=3306127.3331825 %D 2019 %B 18th International Conference on Autonomous Agents and Multiagent Systems %Z date of event: 2019-05-13 - 2019-05-17 %C Montreal, Canada %B AAMAS'19 %P 1225 - 1233 %I ACM %@ 978-1-4503-6309-9

%0 Journal Article %A Chiantini, Luca %A Ikenmeyer, Christian %A Landsberg, J. M. %A Ottaviani, Giorgio %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T The Geometry of Rank Decompositions of Matrix Multiplication I: 2x2 Matrices : %G eng %U http://hdl.handle.net/21.11116/0000-0002-AB12-9 %R 10.1080/10586458.2017.1403981 %7 2017 %D 2019 %J Experimental Mathematics %V 28 %N 3 %& 322 %P 322 - 327 %I Taylor & Francis %C Boston, MA %@ false

%0 Journal Article %A Choudhary, Aruni %A Kerber, Michael %A Raghvendra, Sharat %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Polynomial-Sized Topological Approximations Using the Permutahedron : %G eng %U http://hdl.handle.net/21.11116/0000-0002-E5B6-E %R 10.1007/s00454-017-9951-2 %7 2017 %D 2019 %J Discrete & Computational Geometry %V 61 %N 1 %& 42 %P 42 - 80 %I Springer %C New York, NY %@ false

%0 Conference Proceedings %A Choudhary, Aruni %A Kerber, Michael %A Raghvendra, Sharath %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Improved Topological Approximations by Digitization : %G eng %U http://hdl.handle.net/21.11116/0000-0002-E5BC-8 %R 10.1137/1.9781611975482.166 %D 2019 %B 30th Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2019-01-06 - 2019-01-09 %C San Diego, CA, USA %B Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms %E Chan, Timothy M. %P 2675 - 2688 %I SIAM %@ 978-1-61197-548-2

%0 Journal Article %A Choudhary, Aruni %A Ghosh, Arijit %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Delaunay Simplices in Diagonally Distorted Lattices : %G eng %U http://hdl.handle.net/21.11116/0000-0002-E5C1-1 %D 2019 %J Computational Geometry: Theory and Applications %I Elsevier %C Amsterdam %@ false

%0 Journal Article %A Christodoulou, George %A Sgouritsa, Alkmini %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Designing Networks with Good Equilibria under Uncertainty : %G eng %U http://hdl.handle.net/21.11116/0000-0002-AEC7-A %R 10.1137/16M1096694 %7 2019 %D 2019 %J SIAM Journal on Computing %V 48 %N 4 %& 1364 %P 1364 - 1396 %I SIAM %C Philadelphia, PA %@ false

%0 Journal Article %A Correa, Jos&#233; %A Foncea, Patricio %A Hoeksma, Ruben %A Oosterwijk, Tim %A Vredeveld, Tjark %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Recent Developments in Prophet Inequalities : %G eng %U http://hdl.handle.net/21.11116/0000-0002-9E6F-1 %7 2019 %D 2019 %J ACM SIGecom Exchanges %V 17 %N 1 %& 60 %P 60 - 61 %I ACM %C New York, NY %@ false %U http://www.sigecom.org/exchanges/volume_17/1/CORREA.pdf

%0 Conference Proceedings %A Cruciani, Emilio %A Natale, Emanuele %A Scornavacca, Giacomo %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Distributed Community Detection via Metastability of the 2-Choices Dynamics : %G eng %U http://hdl.handle.net/21.11116/0000-0002-A985-9 %R 10.1609/aaai.v33i01.33016046 %D 2019 %B Thirty-Third AAAI Conference on Artificial Intelligence %Z date of event: 2019-01-27 - 2019-02-01 %C Honolulu, HI, USA %B Thirty-Third AAAI Conference on Artificial Intelligence %P 6046 - 6053 %I AAAI %@ 978-1-57735-809-1

%0 Journal Article %A Daescu, Ovidiu %A Friedrichs, Stephan %A Malik, Hemant %A Polishchuk, Valentin %A Schmidt, Christiane %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Altitude Terrain Guarding and Guarding Uni-monotone Polygons : %G eng %U http://hdl.handle.net/21.11116/0000-0004-E572-9 %R 10.1016/j.comgeo.2019.07.004 %7 2019 %D 2019 %J Computational Geometry: Theory and Applications %V 84 %& 22 %P 22 - 35 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A Dell, Holger %A Roth, Marc %A Wellnitz, Philip %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Counting Answers to Existential Questions : %G eng %U http://hdl.handle.net/21.11116/0000-0005-8653-6 %R 10.4230/LIPIcs.ICALP.2019.113 %U urn:nbn:de:0030-drops-106894 %D 2019 %B 46th International Colloquium on Automata, Languages, and Programming %Z date of event: 2019-07-09 - 2019-07-12 %C Patras, Greece %B 46th International Colloquium on Automata, Languages, and Programming %E Baier, Christel; Chaztigiannakis, Ioannis; Flocchini, Paola; Leonardi, Stefano %Z sequence number: 113 %I Schloss Dagstuhl %@ 978-3-95977-109-2 %B Leibniz International Proceedings in Informatics %N 132 %U https://doi.org/10.4230/LIPIcs.ICALP.2019.113https://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Conference Proceedings %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-0005-85DB-E %R 10.4230/LIPIcs.MFCS.2019.26 %U urn:nbn:de:0030-drops-109703 %D 2019 %B 44th International Symposium on Mathematical Foundations of Computer Science %Z date of event: 2019-08-26 - 2019-08-30 %C Aachen, Germany %B 44th International Symposium on Mathematical Foundations of Computer Science %E Rossmanith, Peter; Heggernes, Pinar; Katoen, Joost-Pieter %Z sequence number: 26 %I Schloss Dagstuhl %@ 978-3-95977-117-7 %B Leibniz International Proceedings in Informatics %N 138 %@ false %U http://drops.dagstuhl.de/opus/volltexte/2019/10970/https://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Report %A D&#246;rfler, Julian %A Ikenmeyer, Christian %A Panova, Greta %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T On Geometric Complexity Theory: Multiplicity Obstructions are Stronger than Occurrence Obstructions : %G eng %U http://hdl.handle.net/21.11116/0000-0003-B393-C %U http://arxiv.org/abs/1901.04576 %D 2019 %X Geometric Complexity Theory as initiated by Mulmuley and Sohoni in two papers (SIAM J Comput 2001, 2008) aims to separate algebraic complexity classes via representation theoretic multiplicities in coordinate rings of specific group varieties. The papers also conjecture that the vanishing behavior of these multiplicities would be sufficient to separate complexity classes (so-called occurrence obstructions). The existence of such strong occurrence obstructions has been recently disproven in 2016 in two successive papers, Ikenmeyer-Panova (Adv. Math.) and B\"urgisser-Ikenmeyer-Panova (J. AMS). This raises the question whether separating group varieties via representation theoretic multiplicities is stronger than separating them via occurrences. This paper provides for the first time a setting where separating with multiplicities can be achieved, while the separation with occurrences is provably impossible. Our setting is surprisingly simple and natural: We study the variety of products of homogeneous linear forms (the so-called Chow variety) and the variety of polynomials of bounded border Waring rank (i.e. a higher secant variety of the Veronese variety). As a side result we prove a slight generalization of Hermite's reciprocity theorem, which proves Foulkes' conjecture for a new infinite family of cases. %K Computer Science, Computational Complexity, cs.CC,Mathematics, Algebraic Geometry, math.AG,Mathematics, Combinatorics, math.CO,Mathematics, Representation Theory, math.RT,

%0 Journal Article %A Duraj, Lech %A K&#252;nnemann, Marvin %A Polak, Adam %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Tight Conditional Lower Bounds for Longest Common Increasing Subsequence : %G eng %U http://hdl.handle.net/21.11116/0000-0002-A906-9 %R 10.1007/s00453-018-0485-7 %7 2018 %D 2019 %J Algorithmica %V 81 %N 10 %& 3968 %P 3968 - 3992 %I Springer %C New York, NY %@ false

%0 Report %A Eden, Talya %A Ron, Dana %A Rosenbaum, Will %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T The Arboricity Captures the Complexity of Sampling Edges : %G eng %U http://hdl.handle.net/21.11116/0000-0003-0CD0-5 %U http://arxiv.org/abs/1902.08086 %D 2019 %X In this paper, we revisit the problem of sampling edges in an unknown graph $G = (V, E)$ from a distribution that is (pointwise) almost uniform over $E$. We consider the case where there is some a priori upper bound on the arboriciy of $G$. Given query access to a graph $G$ over $n$ vertices and of average degree $d$ and arboricity at most $\alpha$, we design an algorithm that performs $O\!\left(\frac{\alpha}{d} \cdot \frac{\log^3 n}{\varepsilon}\right)$ queries in expectation and returns an edge in the graph such that every edge $e \in E$ is sampled with probability $(1 \pm \varepsilon)/m$. The algorithm performs two types of queries: degree queries and neighbor queries. We show that the upper bound is tight (up to poly-logarithmic factors and the dependence in $\varepsilon$), as $\Omega\!\left(\frac{\alpha}{d} \right)$ queries are necessary for the easier task of sampling edges from any distribution over $E$ that is close to uniform in total variational distance. We also prove that even if $G$ is a tree (i.e., $\alpha = 1$ so that $\frac{\alpha}{d}=\Theta(1)$), $\Omega\left(\frac{\log n}{\log\log n}\right)$ queries are necessary to sample an edge from any distribution that is pointwise close to uniform, thus establishing that a $\mathrm{poly}(\log n)$ factor is necessary for constant $\alpha$. Finally we show how our algorithm can be applied to obtain a new result on approximately counting subgraphs, based on the recent work of Assadi, Kapralov, and Khanna (ITCS, 2019). %K Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS

%0 Report %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-0005-1DBA-A %U http://arxiv.org/abs/1906.07781 %D 2019 %X The directed Physarum dynamics is known to solve positive linear programs: minimize $c^T x$ subject to $Ax = b$ and $x \ge 0$ for a positive cost vector $c$. The directed Physarum dynamics evolves a positive vector $x$ according to the dynamics $\dot{x} = q(x) - x$. Here $q(x)$ is the solution to $Af = b$ that minimizes the "energy" $\sum_i c_i f_i^2/x_i$. In this paper, we study the non-uniform directed dynamics $\dot{x} = D(q(x) - x)$, where $D$ is a positive diagonal matrix. The non-uniform dynamics is more complex than the uniform dynamics (with $D$ being the identity matrix), as it allows each component of $x$ to react with different speed to the differences between $q(x)$ and $x$. Our contribution is to show that the non-uniform directed dynamics solves positive linear programs. %K Mathematics, Dynamical Systems, math.DS,Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Optimization and Control, math.OC

%0 Journal Article %A Fraigniaud, Pierre %A Natale, Emanuele %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Noisy Rumor Spreading and Plurality Consensus : %G eng %U http://hdl.handle.net/21.11116/0000-0002-6CD7-3 %R 10.1007/s00446-018-0335-5 %7 2018 %D 2019 %J Distributed Computing %V 32 %N 4 %& 257 %P 257 - 276 %I Springer International %C Berlin %@ false

%0 Conference Proceedings %A Funke, Stefan %A Rupp, Tobias %A Nusser, Andr&#233; %A Storandt, Sabine %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T PATHFINDER: Storage and Indexing of Massive Trajectory Sets : %G eng %U http://hdl.handle.net/21.11116/0000-0005-870C-6 %R 10.1145/3340964.3340978 %D 2019 %B 16th International Symposium onSpatial and Temporal Databases %Z date of event: 2019-08-19 - 2019-08-21 %C Vienna, Austria %B SSTD'19 %E Aref, Walid G.; Bertolotto, Michela; Bouros, Pnagiotis; Jensen, Christian S.; Mahmood, Ahmed; N&#248;rv&#229;g, Kjetil; Sacharidis, Dimitris; Sarwat, Mohamed %P 90 - 99 %I ACM %@ 978-1-4503-6280-1

%0 Conference Proceedings %A Geissmann, Barbara %A Leucci, Stefano %A Liu, Chih-Hung %A Penna, Paolo %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Optimal Sorting with Persistent Comparison Errors : %G eng %U http://hdl.handle.net/21.11116/0000-0007-3186-A %R 10.4230/LIPIcs.ESA.2019.49 %U urn:nbn:de:0030-drops-111706 %D 2019 %B 27th Annual European Symposium on Algorithms %Z date of event: 2019-09-09 - 2019-09-11 %C Munich/Garching, Germany %B 27th Annual European Symposium on Algorithms %E Bender, Michael A.; Svensson, Ola; German, Grzegorz %P 1 - 14 %Z sequence number: 49 %I Schloss Dagstuhl %@ 978-3-95977-124-5 %B Leibniz International Proceedings in Informatics %N 144 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2019/11170/https://creativecommons.org/licenses/by/3.0/legalcode

%0 Journal Article %A Gonczarowski, Yannai A. %A Nisan, Noam %A Ostrovsky, Rafail %A Rosenbaum, Will %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Stable Marriage Requires Communication : %G eng %U http://hdl.handle.net/21.11116/0000-0005-88FD-5 %R 10.1016/j.geb.2018.10.013 %7 2019 %D 2019 %J Games and Economic Behavior %V 118 %& 626 %P 626 - 646 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A Grandoni, Fabrizio %A Laekhanukit, Bundit %A Li, Shi %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T O(log 2 k/ log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm : %G eng %U http://hdl.handle.net/21.11116/0000-0003-1625-B %R 10.1145/3313276.3316349 %D 2019 %B 51st Annual ACM Symposium on the Theory of Computing %Z date of event: 2019-06-23 - 2019-06-26 %C Phoenix, AZ, USA %B STOC'19 %P 253 - 264 %I ACM %@ 978-1-4503-6705-9

%0 Journal Article %A Heydrich, Sandy %A Wiese, Andreas %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Faster Approximation Schemes for the Two-dimensional Knapsack Problem : %G eng %U http://hdl.handle.net/21.11116/0000-0005-6A94-D %R 10.1145/3338512 %7 2019 %D 2019 %J ACM Transactions on Algorithms %V 15 %N 4 %Z sequence number: 47 %I ACM %C New York, NY %@ false

%0 Conference Proceedings %A Ibrahim, Yusra %A Riedewald, Mirek %A Weikum, Gerhard %A Zeinalipour-Yazti, Demetrios %+ Databases and Information Systems, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Databases and Information Systems, MPI for Informatics, Max Planck Society Databases and Information Systems, MPI for Informatics, Max Planck Society %T Bridging Quantities in Tables and Text : %G eng %U http://hdl.handle.net/21.11116/0000-0003-01AB-B %R 10.1109/ICDE.2019.00094 %D 2019 %B 35th IEEE International Conference on Data Engineering %Z date of event: 2019-04-08 - 2019-04-12 %C Macau, China %B ICDE 2019 %P 1010 - 1021 %I IEEE %@ 978-1-5386-7474-1

%0 Journal Article %A Ikenmeyer, Christian %A Komarath, Balagopal %A Lenzen, Christoph %A Lysikov, Vladimir %A Mokhov, Andrey %A Sreenivasaiah, Karteek %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T On the Complexity of Hazard-free Circuits : %G eng %U http://hdl.handle.net/21.11116/0000-0004-8D51-2 %R 10.1145/3320123 %7 2019 %D 2019 %J Journal of the ACM %V 66 %N 4 %Z sequence number: 25 %I ACM %C New York, NY %@ false

%0 Thesis %A Issac, Davis %Y Karrenbauer, Andreas %A referee: Mehlhorn, Kurt %A referee: Chandran, L. Sunil %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T On some covering, partition and connectivity problems in graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0004-D665-9 %R 10.22028/D291-29620 %I Universit&#228;t des Saarlandes %C Saarbr&#252;cken %D 2019 %P 191 p. %V phd %9 phd %X We look at some graph problems related to covering, partition, and connectivity. First, we study the problems of covering and partitioning edges with bicliques, especially from the viewpoint of parameterized complexity. For the partition problem, we develop much more efficient algorithms than the ones previously known. In contrast, for the cover problem, our lower bounds show that the known algorithms are probably optimal. Next, we move on to graph coloring, which is probably the most extensively studied partition problem in graphs. Hadwiger&#8217;s conjecture is a long-standing open problem related to vertex coloring. We prove the conjecture for a special class of graphs, namely squares of 2-trees, and show that square graphs are important in connection with Hadwiger&#8217;s conjecture. Then, we study a coloring problem that has been emerging recently, called rainbow coloring. This problem lies in the intersection of coloring and connectivity. We study different variants of rainbow coloring and present bounds and complexity results on them. Finally, we move on to another parameter related to connectivity called spanning tree congestion (STC). We give tight bounds for STC in general graphs and random graphs. While proving the results on %U https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/28007

%0 Conference Proceedings %A Jindal, Gorav %A Bl&#228;ser, Markus %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T On the Complexity of Symmetric Polynomials : %G eng %U http://hdl.handle.net/21.11116/0000-0002-ABCC-8 %R 10.4230/LIPIcs.ITCS.2019.47 %U urn:nbn:de:0030-drops-101402 %D 2019 %B 10th Innovations in Theoretical Computer Science %Z date of event: 2019-01-10 - 2019-01-12 %C San Diego, CA, USA %B 10th Innovations in Theoretical Computer Science %E Blum, Avrim %P 1 - 14 %Z sequence number: 47 %I Schloss Dagstuhl %@ 978-3-95977-095-8 %B Leibniz International Proceedings in Informatics %N 124 %U http://drops.dagstuhl.de/opus/volltexte/2018/10140/http://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Conference Proceedings %A John, Maximilian %A Karrenbauer, Andreas %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Dynamic Sparsification for Quadratic Assignment Problems : %G eng %U http://hdl.handle.net/21.11116/0000-0005-1DA8-E %R 10.1007/978-3-030-22629-9_17 %D 2019 %B 18th International Conference on Mathematical Optimization Theory and Operations Research %Z date of event: 2019-07-08 - 2019-07-12 %C Ekaterinburg, Russia %B Mathematical Optimization Theory and Operations Research %E Khachay, Michael; Kochetov, Yury; Pardalos, Panos %P 232 - 264 %I Springer %B Lecture Notes in Computer Science %N 11548

%0 Report %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-0002-F39F-9 %U http://arxiv.org/abs/1901.07231 %D 2019 %X Let $c \in \mathbb{Z}^m_{> 0}$, $A \in \mathbb{Z}^{n\times m}$, and $b \in \mathbb{Z}^n$. We show under fairly general conditions that the non-uniform Physarum dynamics \[ \dot{x}_e = a_e(x,t) \left(|q_e| - x_e\right) \] converges to the optimum solution $x^*$ of the weighted basis pursuit problem minimize $c^T x$ subject to $A f = b$ and $|f| \le x$. Here, $f$ and $x$ are $m$-vectors of real variables, $q$ minimizes the energy $\sum_e (c_e/x_e) q_e^2$ subject to the constraints $A q = b$ and $\mathrm{supp}(q) \subseteq \mathrm{supp}(x)$, and $a_e(x,t) > 0$ is the reactivity of edge $e$ to the difference $|q_e| - x_e$ at time $t$ and in state $x$. Previously convergence was only shown for the uniform case $a_e(x,t) = 1$ for all $e$, $x$, and $t$. We also show convergence for the dynamics \[ \dot{x}_e = x_e \cdot \left( g_e \left(\frac{|q_e|}{x_e}\right) - 1\right),\] where $g_e$ is an increasing differentiable function with $g_e(1) = 1$. Previously convergence was only shown for the special case of the shortest path problem on a graph consisting of two nodes connected by parallel edges. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Journal Article %A Khanchandani, Pankaj %A Lenzen, Christoph %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Self-Stabilizing Byzantine Clock Synchronization with Optimal Precision : %G eng %U http://hdl.handle.net/21.11116/0000-0000-73AC-D %R 10.1007/s00224-017-9840-3 %7 2018-01-20 %D 2019 %J Theory of Computing Systems %V 63 %N 2 %& 261 %P 261 - 305 %I Springer %C New York, NY %@ false

%0 Conference Proceedings %A Kinali, Attila %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Physical Sine-to-Square Converter Noise Model : %G eng %U http://hdl.handle.net/21.11116/0000-0002-AC39-D %R 10.1109/FCS.2018.8597525 %D 2019 %B IEEE International Frequency Control Symposium %Z date of event: 2018-05-21 - 2018-05-24 %C Olympic Valley, CA, USA %B IEEE International Frequency Control Symposium %P 383 - 388 %I IEEE %@ 978-1-5386-3214-7

%0 Journal Article %A K&#252;nnemann, Marvin %A Moeller, Daniel %A Paturi, Ramamohan %A Schneider, Stefan %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Subquadratic Algorithms for Succinct Stable Matching : %G eng %U http://hdl.handle.net/21.11116/0000-0003-A7E0-3 %R 10.1007/s00453-019-00564-x %7 2019 %D 2019 %J Algorithmica %V 81 %N 7 %& 2991 %P 2991 - 3024 %I Springer %C New York, NY %@ false

%0 Journal Article %A Lenzen, Christoph %A Rybicki, Joel %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Self-Stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus : %G eng %U http://hdl.handle.net/21.11116/0000-0004-7CF6-C %R 10.1145/3339471 %7 2019 %D 2019 %J Journal of the ACM %V 66 %N 5 %Z sequence number: 32 %I ACM %C New York, NY %@ false

%0 Report %A Lenzen, Christoph %A Parter, Merav %A Yogev, Eylon %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Parallel Balanced Allocations: The Heavily Loaded Case : %G eng %U http://hdl.handle.net/21.11116/0000-0003-B3A4-9 %U http://arxiv.org/abs/1904.07532 %D 2019 %X We study parallel algorithms for the classical balls-into-bins problem, in which $m$ balls acting in parallel as separate agents are placed into $n$ bins. Algorithms operate in synchronous rounds, in each of which balls and bins exchange messages once. The goal is to minimize the maximal load over all bins using a small number of rounds and few messages. While the case of $m=n$ balls has been extensively studied, little is known about the heavily loaded case. In this work, we consider parallel algorithms for this somewhat neglected regime of $m\gg n$. The naive solution of allocating each ball to a bin chosen uniformly and independently at random results in maximal load $m/n+\Theta(\sqrt{m/n\cdot \log n})$ (for $m\geq n \log n$) w.h.p. In contrast, for the sequential setting Berenbrink et al (SIAM J. Comput 2006) showed that letting each ball join the least loaded bin of two randomly selected bins reduces the maximal load to $m/n+O(\log\log m)$ w.h.p. To date, no parallel variant of such a result is known. We present a simple parallel threshold algorithm that obtains a maximal load of $m/n+O(1)$ w.h.p. within $O(\log\log (m/n)+\log^* n)$ rounds. The algorithm is symmetric (balls and bins all "look the same"), and balls send $O(1)$ messages in expectation per round. The additive term of $O(\log^* n)$ in the complexity is known to be tight for such algorithms (Lenzen and Wattenhofer Distributed Computing 2016). We also prove that our analysis is tight, i.e., algorithms of the type we provide must run for $\Omega(\min\{\log\log (m/n),n\})$ rounds w.h.p. Finally, we give a simple asymmetric algorithm (i.e., balls are aware of a common labeling of the bins) that achieves a maximal load of $m/n + O(1)$ in a constant number of rounds w.h.p. Again, balls send only a single message per round, and bins receive $(1+o(1))m/n+O(\log n)$ messages w.h.p. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC

%0 Conference Proceedings %A Lenzen, Christoph %A Parter, Merav %A Yogev, Eylon %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Parallel Balanced Allocations: The Heavily Loaded Case : %G eng %U http://hdl.handle.net/21.11116/0000-0003-6593-5 %R 10.1145/3323165.3323203 %D 2019 %B 31st ACM Symposium on Parallelism in Algorithms and Architectures %Z date of event: 2019-06-22 - 2019-06-24 %C Phoenix, AZ, USA %B SPAA'19 %P 313 - 322 %I ACM %@ 978-1-4503-6184-2

%0 Journal Article %A Lenzen, Christoph %A Rybicki, Joel %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Near-Optimal Self-stabilising Counting and Firing Squads : %G eng %U http://hdl.handle.net/21.11116/0000-0004-7AD6-2 %R 10.1007/s00446-018-0342-6 %7 2018 %D 2019 %J Distributed Computing %V 32 %N 4 %& 339 %P 339 - 360 %I Springer International %C Berlin %@ false

%0 Journal Article %A Lenzen, Christoph %A Patt-Shamir, Boaz %A Peleg, David %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Distributed Distance Computation and Routing with Small Messages : %G eng %U http://hdl.handle.net/21.11116/0000-0002-6CD1-9 %R 10.1007/s00446-018-0326-6 %7 2018 %D 2019 %J Distributed Computing %V 32 %N 2 %& 133 %P 133 - 157 %I Springer International %C Berlin %@ false

%0 Conference Proceedings %A Leucci, Stefano %A Liu, Chih-Hung %A Meierhans, Simon %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Resilient Dictionaries for Randomly Unreliable Memory : %G eng %U http://hdl.handle.net/21.11116/0000-0007-318A-6 %R 10.4230/LIPIcs.ESA.2019.70 %U urn:nbn:de:0030-drops-111911 %D 2019 %B 27th Annual European Symposium on Algorithms %Z date of event: 2019-09-09 - 2019-09-11 %C Munich/Garching, Germany %B 27th Annual European Symposium on Algorithms %E Bender, Michael A.; Svensson, Ola; German, Grzegorz %P 1 - 16 %Z sequence number: 70 %I Schloss Dagstuhl %@ 978-3-95977-124-5 %B Leibniz International Proceedings in Informatics %N 144 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2019/11191/https://creativecommons.org/licenses/by/3.0/legalcode

%0 Report %A Miller, Avery %A Patt-Shamir, Boaz %A Rosenbaum, Will %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing : %G eng %U http://hdl.handle.net/21.11116/0000-0003-0CD3-2 %U http://arxiv.org/abs/1902.08069 %D 2019 %X We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate $0\le\rho\le1$ and burstiness $\sigma\ge0$. In this model, we analyze the size of buffers required to avoid overflows in the basic case of a path. Our main results characterize the space required by the average rate and the number of distinct destinations: we show that $O(k d^{1/k})$ space suffice, where $d$ is the number of distinct destinations and $k=\lfloor 1/\rho \rfloor$; and we show that $\Omega(\frac 1 k d^{1/k})$ space is necessary. For directed trees, we describe an algorithm whose buffer space requirement is at most $1 + d' + \sigma$ where $d'$ is the maximum number of destinations on any root-leaf path. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC

%0 Conference Proceedings %A Miller, Avery %A Patt-Shamir, Boaz %A Rosenbaum, Will %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing : %G eng %U http://hdl.handle.net/21.11116/0000-0007-1D09-0 %R 10.1145/3293611.3331614 %D 2019 %B ACM Symposium on Principles of Distributed Computing %Z date of event: 2019-07-29 - 2019-08-02 %C Toronto, Canada %B PODC'19 %P 117 - 126 %I ACM %@ 978-1-4503-6217-7

%0 Conference Proceedings %A Oh, Eunjin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Optimal Algorithm for Geodesic Nearest-point Voronoi Diagrams in Simple Polygons : %G eng %U http://hdl.handle.net/21.11116/0000-0002-AA78-8 %R 10.1137/1.9781611975482.25 %D 2019 %B 30th Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2019-01-06 - 2019-01-09 %C San Diego, CA, USA %B Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms %E Chan, Timothy M. %P 391 - 409 %I SIAM %@ 978-1-61197-548-2

%0 Journal Article %A Oh, Eunjin %A Ahn, Hee-Kap %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Computing the Center Region and its Variants : %G eng %U http://hdl.handle.net/21.11116/0000-0004-E587-1 %R 10.1016/j.tcs.2018.06.026 %7 2019 %D 2019 %J Theoretical Computer Science %V 789 %& 2 %P 2 - 12 %I Elsevier %C Amsterdam %@ false

%0 Journal Article %A Oh, Eunjin %A Ahn, Hee-Kap %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-Off Algorithms : %G eng %U http://hdl.handle.net/21.11116/0000-0003-A7DE-7 %R 10.1007/s00453-019-00558-9 %7 2019 %D 2019 %J Algorithmica %V 81 %N 7 %& 2829 %P 2829 - 2856 %I Springer %C New York, NY %@ false

%0 Journal Article %A Oh, Eunjin %A Ahn, Hee-Kap %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Assigning Weights to Minimize the Covering Radius in the Plane : %G eng %U http://hdl.handle.net/21.11116/0000-0003-C34C-C %R 10.1016/j.comgeo.2018.10.007 %7 2019 %D 2019 %J Computational Geometry: Theory and Applications %V 81 %& 22 %P 22 - 32 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A Patt-Shamir, Boaz %A Rosenbaum, Will %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Space-Optimal Packet Routing on Trees : %G eng %U http://hdl.handle.net/21.11116/0000-0004-AAD1-0 %R 10.1109/INFOCOM.2019.8737596 %D 2019 %B IEEE Conference on Computer Communications %Z date of event: 2019-04-29 - 2019-05-02 %C Paris, France %B IEEE Conference on Computer Communications %P 1036 - 1044 %I IEEE %@ 978-1-7281-0515-4

%0 Report %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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Little Charity Guarantees Almost Envy-Freeness : %G eng %U http://hdl.handle.net/21.11116/0000-0005-4FB8-4 %U http://arxiv.org/abs/1907.04596 %D 2019 %X Fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute $m$ goods to $n$ agents in a "fair" manner, where every agent has a valuation for each subset of goods. We assume general valuations. Envy-freeness is the most extensively studied notion of fairness. However, envy-free allocations do not always exist when goods are indivisible. The notion of fairness we consider here is "envy-freeness up to any good" (EFX) where no agent envies another agent after the removal of any single good from the other agent's bundle. It is not known if such an allocation always exists even when $n=3$. We show there is always a partition of the set of goods into $n+1$ subsets $(X_1,\ldots,X_n,P)$ where for $i \in [n]$, $X_i$ is the bundle allocated to agent $i$ and the set $P$ is unallocated (or donated to charity) such that we have$\colon$ 1) envy-freeness up to any good, 2) no agent values $P$ higher than her own bundle, and 3) fewer than $n$ goods go to charity, i.e., $|P| < n$ (typically $m \gg n$). Our proof is constructive. When agents have additive valuations and $\lvert P \rvert$ is large (i.e., when $|P|$ is close to $n$), our allocation also has a good maximin share (MMS) guarantee. Moreover, a minor variant of our algorithm also shows the existence of an allocation which is $4/7$ groupwise maximin share (GMMS): this is a notion of fairness stronger than MMS. This improves upon the current best bound of $1/2$ known for an approximate GMMS allocation. %K Computer Science, Computer Science and Game Theory, cs.GT

%0 Book %A Sanders, Peter %A Mehlhorn, Kurt %A Dietzfelbinger, Martin %A Dementiev, Roman %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Sequential and Parallel Algorithms and Data Structures : The Basic Toolbox %G eng %U http://hdl.handle.net/21.11116/0000-0005-3D79-0 %R 10.1007/978-3-030-25209-0 %@ 978-3-030-25208-3 %@ 978-3-030-25209-0 %I Springer %C Cham %D 2019 %P 434 p.

%0 Journal Article %A Schroeder, Pascal %A Kacem, Imed %A Schmidt, G&#252;nter %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Optimal Online Algorithms for the Portfolio Selection Problem, Bi-Directional Trading and -Search with Interrelated Prices : %G eng %U http://hdl.handle.net/21.11116/0000-0004-7AEC-A %R 10.1051/ro/2018064 %7 2019 %D 2019 %J RAIRO - Operations Research %V 53 %N 2 %& 559 %P 559 - 576 %I EDP Sciences %C Les Ulis, France %@ false