[{"intvolume":"       187","isi":1,"conference":{"location":"Saarbrücken, Germany","start_date":"2021-03-16","name":"STACS: Symposium on Theoretical Aspects of Computer Science","end_date":"2021-03-19"},"month":"03","date_created":"2021-09-27T14:33:15Z","article_number":"44","status":"public","volume":187,"file_date_updated":"2021-10-01T09:55:00Z","publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","publication":"38th International Symposium on Theoretical Aspects of Computer Science","title":"A Ramsey theorem for finite monoids","_id":"10055","ddc":["000"],"oa":1,"project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"abstract":[{"text":"Repeated idempotent elements are commonly used to characterise iterable behaviours in abstract models of computation. Therefore, given a monoid M, it is natural to ask how long a sequence of elements of M needs to be to ensure the presence of consecutive idempotent factors. This question is formalised through the notion of the Ramsey function R_M associated to M, obtained by mapping every k ∈ ℕ to the minimal integer R_M(k) such that every word u ∈ M^* of length R_M(k) contains k consecutive non-empty factors that correspond to the same idempotent element of M. In this work, we study the behaviour of the Ramsey function R_M by investigating the regular 𝒟-length of M, defined as the largest size L(M) of a submonoid of M isomorphic to the set of natural numbers {1,2, …, L(M)} equipped with the max operation. We show that the regular 𝒟-length of M determines the degree of R_M, by proving that k^L(M) ≤ R_M(k) ≤ (k|M|⁴)^L(M). To allow applications of this result, we provide the value of the regular 𝒟-length of diverse monoids. In particular, we prove that the full monoid of n × n Boolean matrices, which is used to express transition monoids of non-deterministic automata, has a regular 𝒟-length of (n²+n+2)/2.","lang":"eng"}],"publication_status":"published","citation":{"apa":"Jecker, I. R. (2021). A Ramsey theorem for finite monoids. In <i>38th International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 187). Saarbrücken, Germany: Schloss Dagstuhl - Leibniz Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.44\">https://doi.org/10.4230/LIPIcs.STACS.2021.44</a>","mla":"Jecker, Ismael R. “A Ramsey Theorem for Finite Monoids.” <i>38th International Symposium on Theoretical Aspects of Computer Science</i>, vol. 187, 44, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.44\">10.4230/LIPIcs.STACS.2021.44</a>.","ieee":"I. R. Jecker, “A Ramsey theorem for finite monoids,” in <i>38th International Symposium on Theoretical Aspects of Computer Science</i>, Saarbrücken, Germany, 2021, vol. 187.","ama":"Jecker IR. A Ramsey theorem for finite monoids. In: <i>38th International Symposium on Theoretical Aspects of Computer Science</i>. Vol 187. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.44\">10.4230/LIPIcs.STACS.2021.44</a>","short":"I.R. Jecker, in:, 38th International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.","chicago":"Jecker, Ismael R. “A Ramsey Theorem for Finite Monoids.” In <i>38th International Symposium on Theoretical Aspects of Computer Science</i>, Vol. 187. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.44\">https://doi.org/10.4230/LIPIcs.STACS.2021.44</a>.","ista":"Jecker IR. 2021. A Ramsey theorem for finite monoids. 38th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 187, 44."},"author":[{"full_name":"Jecker, Ismael R","id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","last_name":"Jecker","first_name":"Ismael R"}],"quality_controlled":"1","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"year":"2021","alternative_title":["LIPIcs"],"scopus_import":"1","publication_identifier":{"isbn":["978-3-9597-7180-1"],"issn":["1868-8969"]},"file":[{"access_level":"open_access","checksum":"17432a05733f408de300e17e390a90e4","file_name":"2021_LIPIcs_Jecker.pdf","file_id":"10063","date_updated":"2021-10-01T09:55:00Z","success":1,"file_size":720250,"creator":"cchlebak","content_type":"application/pdf","date_created":"2021-10-01T09:55:00Z","relation":"main_file"}],"external_id":{"isi":["000635691700044"]},"date_published":"2021-03-10T00:00:00Z","ec_funded":1,"has_accepted_license":"1","department":[{"_id":"KrCh"}],"doi":"10.4230/LIPIcs.STACS.2021.44","language":[{"iso":"eng"}],"acknowledgement":"This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411. I wish to thank Michaël Cadilhac, Emmanuel Filiot and Charles Paperman for their valuable insights concerning Green’s relations.","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","article_processing_charge":"No","oa_version":"Published Version","date_updated":"2023-08-14T07:03:23Z","type":"conference","day":"10"},{"alternative_title":["LIPIcs"],"scopus_import":"1","publication_identifier":{"isbn":["978-3-9597-7207-5"],"issn":["1868-8969"]},"arxiv":1,"file":[{"relation":"main_file","date_created":"2021-10-06T13:51:54Z","creator":"cchlebak","content_type":"application/pdf","file_size":804472,"success":1,"date_updated":"2021-10-06T13:51:54Z","file_id":"10098","file_name":"2021_LIPIcs_Harris.pdf","checksum":"9d2544d53aa5b01565c6891d97a4d765","access_level":"open_access"}],"external_id":{"arxiv":["2008.05569"]},"date_published":"2021-09-15T00:00:00Z","ec_funded":1,"has_accepted_license":"1","department":[{"_id":"VlKo"}],"doi":"10.4230/LIPIcs.APPROX/RANDOM.2021.31","language":[{"iso":"eng"}],"acknowledgement":"Fotis Iliopoulos: This material is based upon work directly supported by the IAS Fund for Math and indirectly supported by the National Science Foundation Grant No. CCF-1900460. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. This work is also supported by the National Science Foundation Grant No. CCF-1815328.\r\nVladimir Kolmogorov: Supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"Yes","oa_version":"Published Version","type":"conference","date_updated":"2022-03-18T10:08:25Z","day":"15","intvolume":"       207","month":"09","conference":{"end_date":"2021-08-18","name":"APPROX/RANDOM: Approximation Algorithms for Combinatorial Optimization Problems/ Randomization and Computation","start_date":"2021-08-16","location":"Virtual"},"date_created":"2021-10-03T22:01:22Z","status":"public","article_number":"31","volume":207,"file_date_updated":"2021-10-06T13:51:54Z","publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","publication":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","title":"A new notion of commutativity for the algorithmic Lovász Local Lemma","_id":"10072","ddc":["000"],"oa":1,"project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"abstract":[{"text":"The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combinatorics which can be used to establish the existence of objects that satisfy certain properties. The breakthrough paper of Moser and Tardos and follow-up works revealed that the LLL has intimate connections with a class of stochastic local search algorithms for finding such desirable objects. In particular, it can be seen as a sufficient condition for this type of algorithms to converge fast. Besides conditions for existence of and fast convergence to desirable objects, one may naturally ask further questions regarding properties of these algorithms. For instance, \"are they parallelizable?\", \"how many solutions can they output?\", \"what is the expected \"weight\" of a solution?\", etc. These questions and more have been answered for a class of LLL-inspired algorithms called commutative. In this paper we introduce a new, very natural and more general notion of commutativity (essentially matrix commutativity) which allows us to show a number of new refined properties of LLL-inspired local search algorithms with significantly simpler proofs.","lang":"eng"}],"publication_status":"published","citation":{"apa":"Harris, D. G., Iliopoulos, F., &#38; Kolmogorov, V. (2021). A new notion of commutativity for the algorithmic Lovász Local Lemma. In <i>Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques</i> (Vol. 207). Virtual: Schloss Dagstuhl - Leibniz Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31\">https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31</a>","mla":"Harris, David G., et al. “A New Notion of Commutativity for the Algorithmic Lovász Local Lemma.” <i>Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques</i>, vol. 207, 31, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31\">10.4230/LIPIcs.APPROX/RANDOM.2021.31</a>.","short":"D.G. Harris, F. Iliopoulos, V. Kolmogorov, in:, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.","chicago":"Harris, David G., Fotis Iliopoulos, and Vladimir Kolmogorov. “A New Notion of Commutativity for the Algorithmic Lovász Local Lemma.” In <i>Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques</i>, Vol. 207. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31\">https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31</a>.","ista":"Harris DG, Iliopoulos F, Kolmogorov V. 2021. A new notion of commutativity for the algorithmic Lovász Local Lemma. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX/RANDOM: Approximation Algorithms for Combinatorial Optimization Problems/ Randomization and Computation, LIPIcs, vol. 207, 31.","ieee":"D. G. Harris, F. Iliopoulos, and V. Kolmogorov, “A new notion of commutativity for the algorithmic Lovász Local Lemma,” in <i>Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques</i>, Virtual, 2021, vol. 207.","ama":"Harris DG, Iliopoulos F, Kolmogorov V. A new notion of commutativity for the algorithmic Lovász Local Lemma. In: <i>Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques</i>. Vol 207. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31\">10.4230/LIPIcs.APPROX/RANDOM.2021.31</a>"},"quality_controlled":"1","author":[{"first_name":"David G.","last_name":"Harris","full_name":"Harris, David G."},{"first_name":"Fotis","last_name":"Iliopoulos","full_name":"Iliopoulos, Fotis"},{"last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir"}],"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"year":"2021"},{"quality_controlled":"1","author":[{"last_name":"Guha","first_name":"Shibashis","full_name":"Guha, Shibashis"},{"id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","full_name":"Jecker, Ismael R","first_name":"Ismael R","last_name":"Jecker"},{"first_name":"Karoliina","last_name":"Lehtinen","full_name":"Lehtinen, Karoliina"},{"first_name":"Martin","last_name":"Zimmermann","full_name":"Zimmermann, Martin"}],"citation":{"ista":"Guha S, Jecker IR, Lehtinen K, Zimmermann M. 2021. A bit of nondeterminism makes pushdown automata expressive and succinct. 46th International Symposium on Mathematical Foundations of Computer Science. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 202, 53.","chicago":"Guha, Shibashis, Ismael R Jecker, Karoliina Lehtinen, and Martin Zimmermann. “A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct.” In <i>46th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 202. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2021.53\">https://doi.org/10.4230/LIPIcs.MFCS.2021.53</a>.","short":"S. Guha, I.R. Jecker, K. Lehtinen, M. Zimmermann, in:, 46th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.","ama":"Guha S, Jecker IR, Lehtinen K, Zimmermann M. A bit of nondeterminism makes pushdown automata expressive and succinct. In: <i>46th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 202. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2021.53\">10.4230/LIPIcs.MFCS.2021.53</a>","ieee":"S. Guha, I. R. Jecker, K. Lehtinen, and M. Zimmermann, “A bit of nondeterminism makes pushdown automata expressive and succinct,” in <i>46th International Symposium on Mathematical Foundations of Computer Science</i>, Tallinn, Estonia, 2021, vol. 202.","apa":"Guha, S., Jecker, I. R., Lehtinen, K., &#38; Zimmermann, M. (2021). A bit of nondeterminism makes pushdown automata expressive and succinct. In <i>46th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 202). Tallinn, Estonia: Schloss Dagstuhl - Leibniz Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2021.53\">https://doi.org/10.4230/LIPIcs.MFCS.2021.53</a>","mla":"Guha, Shibashis, et al. “A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct.” <i>46th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 202, 53, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2021.53\">10.4230/LIPIcs.MFCS.2021.53</a>."},"year":"2021","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"oa":1,"ddc":["000"],"_id":"10075","publication":"46th International Symposium on Mathematical Foundations of Computer Science","title":"A bit of nondeterminism makes pushdown automata expressive and succinct","publication_status":"published","abstract":[{"lang":"eng","text":"We study the expressiveness and succinctness of good-for-games pushdown automata (GFG-PDA) over finite words, that is, pushdown automata whose nondeterminism can be resolved based on the run constructed so far, but independently of the remainder of the input word. We prove that GFG-PDA recognise more languages than deterministic PDA (DPDA) but not all context-free languages (CFL). This class is orthogonal to unambiguous CFL. We further show that GFG-PDA can be exponentially more succinct than DPDA, while PDA can be double-exponentially more succinct than GFG-PDA. We also study GFGness in visibly pushdown automata (VPA), which enjoy better closure properties than PDA, and for which we show GFGness to be ExpTime-complete. GFG-VPA can be exponentially more succinct than deterministic VPA, while VPA can be exponentially more succinct than GFG-VPA. Both of these lower bounds are tight. Finally, we study the complexity of resolving nondeterminism in GFG-PDA. Every GFG-PDA has a positional resolver, a function that resolves nondeterminism and that is only dependant on the current configuration. Pushdown transducers are sufficient to implement the resolvers of GFG-VPA, but not those of GFG-PDA. GFG-PDA with finite-state resolvers are determinisable."}],"project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"}],"volume":202,"publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","file_date_updated":"2021-10-06T12:44:05Z","intvolume":"       202","article_number":"53","status":"public","date_created":"2021-10-03T22:01:23Z","month":"08","conference":{"start_date":"2021-08-23","location":"Tallinn, Estonia","name":"MFCS: Mathematical Foundations of Computer Science","end_date":"2021-08-27"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","day":"18","date_updated":"2022-05-13T08:21:56Z","type":"conference","oa_version":"Published Version","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.MFCS.2021.53","department":[{"_id":"KrCh"}],"has_accepted_license":"1","ec_funded":1,"acknowledgement":"Ismaël Jecker: Funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 754411. Karoliina Lehtinen: Funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 892704.","date_published":"2021-08-18T00:00:00Z","external_id":{"arxiv":["2105.02611"]},"file":[{"date_created":"2021-10-06T12:44:05Z","relation":"main_file","creator":"cchlebak","content_type":"application/pdf","file_size":825567,"date_updated":"2021-10-06T12:44:05Z","file_id":"10097","success":1,"access_level":"open_access","checksum":"f4d407d43a97330c3fb11e6a7a6fbfb2","file_name":"2021_LIPIcs_Guha.pdf"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-9597-7201-3"]},"scopus_import":"1","alternative_title":["LIPIcs"],"arxiv":1},{"external_id":{"arxiv":["2003.01697"]},"file":[{"file_name":"2021_LIPIcsDISC_BChatterjee.pdf","checksum":"76546df112a0ba1166c864d33d7834e2","access_level":"open_access","success":1,"file_id":"10276","date_updated":"2021-11-12T09:23:22Z","creator":"cchlebak","content_type":"application/pdf","file_size":795860,"relation":"main_file","date_created":"2021-11-12T09:23:22Z"}],"date_published":"2021-10-04T00:00:00Z","arxiv":1,"scopus_import":"1","publication_identifier":{"isbn":["9-783-9597-7210-5"],"issn":["1868-8969"]},"alternative_title":["LIPIcs"],"day":"04","oa_version":"Published Version","date_updated":"2021-11-12T09:42:55Z","type":"conference","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","article_processing_charge":"No","acknowledgement":"This work was partially funded by National Supercomputing Mission, Govt. of India under the project “Concurrent and Distributed Programming primitives and algorithms for Temporal Graphs”(DST/NSM/R&D_Exascale/2021/16).\r\n","department":[{"_id":"DaAl"}],"has_accepted_license":"1","doi":"10.4230/LIPIcs.DISC.2021.52","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","file_date_updated":"2021-11-12T09:23:22Z","volume":209,"status":"public","article_number":"52","month":"10","conference":{"start_date":"2021-10-04","location":"Freiburg, Germany","end_date":"2021-10-08","name":"DISC: Distributed Computing"},"date_created":"2021-11-07T23:01:23Z","intvolume":"       209","year":"2021","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"quality_controlled":"1","author":[{"id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Bapi","first_name":"Bapi","last_name":"Chatterjee"},{"last_name":"Peri","first_name":"Sathya","full_name":"Peri, Sathya"},{"first_name":"Muktikanta","last_name":"Sa","full_name":"Sa, Muktikanta"}],"citation":{"mla":"Chatterjee, Bapi, et al. “Brief Announcement: Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 52, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">10.4230/LIPIcs.DISC.2021.52</a>.","apa":"Chatterjee, B., Peri, S., &#38; Sa, M. (2021). Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">https://doi.org/10.4230/LIPIcs.DISC.2021.52</a>","ista":"Chatterjee B, Peri S, Sa M. 2021. Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. 35th International Symposium on Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 52.","chicago":"Chatterjee, Bapi, Sathya Peri, and Muktikanta Sa. “Brief Announcement: Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds.” In <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">https://doi.org/10.4230/LIPIcs.DISC.2021.52</a>.","short":"B. Chatterjee, S. Peri, M. Sa, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.","ama":"Chatterjee B, Peri S, Sa M. Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">10.4230/LIPIcs.DISC.2021.52</a>","ieee":"B. Chatterjee, S. Peri, and M. Sa, “Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds,” in <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209."},"abstract":[{"text":"This paper reports a new concurrent graph data structure that supports updates of both edges and vertices and queries: Breadth-first search, Single-source shortest-path, and Betweenness centrality. The operations are provably linearizable and non-blocking.","lang":"eng"}],"publication_status":"published","_id":"10216","oa":1,"ddc":["000"],"title":"Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds","publication":"35th International Symposium on Distributed Computing"},{"date_updated":"2022-08-19T07:23:28Z","type":"conference","oa_version":"Published Version","day":"04","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"Dan Alistarh: Supported in part by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). Giorgi Nadiradze: Supported in part by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). The authors would like to thank the DISC anonymous reviewers for their useful\r\nfeedback and comments.","ec_funded":1,"doi":"10.4230/LIPIcs.DISC.2021.4","language":[{"iso":"eng"}],"has_accepted_license":"1","department":[{"_id":"DaAl"}],"date_published":"2021-10-04T00:00:00Z","file":[{"file_id":"10277","date_updated":"2021-11-12T09:33:26Z","success":1,"access_level":"open_access","file_name":"2021_LIPIcsDISC_Alistarh.pdf","checksum":"b4cdc6668c899a601c5e6a96b8ca54d9","date_created":"2021-11-12T09:33:26Z","relation":"main_file","file_size":706791,"creator":"cchlebak","content_type":"application/pdf"}],"alternative_title":["LIPIcs"],"publication_identifier":{"issn":["1868-8969"],"isbn":["9-783-9597-7210-5"]},"scopus_import":"1","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"year":"2021","citation":{"ista":"Alistarh D-A, Gelashvili R, Nadiradze G. 2021. Lower bounds for shared-memory leader election under bounded write contention. 35th International Symposium on Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 4.","short":"D.-A. Alistarh, R. Gelashvili, G. Nadiradze, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.","chicago":"Alistarh, Dan-Adrian, Rati Gelashvili, and Giorgi Nadiradze. “Lower Bounds for Shared-Memory Leader Election under Bounded Write Contention.” In <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.4\">https://doi.org/10.4230/LIPIcs.DISC.2021.4</a>.","ieee":"D.-A. Alistarh, R. Gelashvili, and G. Nadiradze, “Lower bounds for shared-memory leader election under bounded write contention,” in <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209.","ama":"Alistarh D-A, Gelashvili R, Nadiradze G. Lower bounds for shared-memory leader election under bounded write contention. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.4\">10.4230/LIPIcs.DISC.2021.4</a>","mla":"Alistarh, Dan-Adrian, et al. “Lower Bounds for Shared-Memory Leader Election under Bounded Write Contention.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 4, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.4\">10.4230/LIPIcs.DISC.2021.4</a>.","apa":"Alistarh, D.-A., Gelashvili, R., &#38; Nadiradze, G. (2021). Lower bounds for shared-memory leader election under bounded write contention. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.4\">https://doi.org/10.4230/LIPIcs.DISC.2021.4</a>"},"author":[{"first_name":"Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X"},{"full_name":"Gelashvili, Rati","first_name":"Rati","last_name":"Gelashvili"},{"last_name":"Nadiradze","first_name":"Giorgi","full_name":"Nadiradze, Giorgi","id":"3279A00C-F248-11E8-B48F-1D18A9856A87"}],"quality_controlled":"1","project":[{"grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"publication_status":"published","abstract":[{"lang":"eng","text":"This paper gives tight logarithmic lower bounds on the solo step complexity of leader election in an asynchronous shared-memory model with single-writer multi-reader (SWMR) registers, for both deterministic and randomized obstruction-free algorithms. The approach extends to lower bounds for deterministic and randomized obstruction-free algorithms using multi-writer registers under bounded write concurrency, showing a trade-off between the solo step complexity of a leader election algorithm, and the worst-case number of stalls incurred by a processor in an execution."}],"title":"Lower bounds for shared-memory leader election under bounded write contention","publication":"35th International Symposium on Distributed Computing","ddc":["000"],"oa":1,"_id":"10217","file_date_updated":"2021-11-12T09:33:26Z","publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","volume":209,"date_created":"2021-11-07T23:01:23Z","month":"10","conference":{"location":"Freiburg, Germany","start_date":"2021-10-04","end_date":"2021-10-08","name":"DISC: Distributed Computing"},"status":"public","article_number":"4","intvolume":"       209"},{"volume":209,"file_date_updated":"2021-11-12T08:16:44Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","intvolume":"       209","date_created":"2021-11-07T23:01:24Z","conference":{"location":"Freiburg, Germany","start_date":"2021-10-04","name":"DISC: Distributed Computing ","end_date":"2021-10-08"},"month":"10","status":"public","article_number":"43","citation":{"mla":"Alistarh, Dan-Adrian, et al. “Brief Announcement: Fast Graphical Population Protocols.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.43\">10.4230/LIPIcs.DISC.2021.43</a>.","apa":"Alistarh, D.-A., Gelashvili, R., &#38; Rybicki, J. (2021). Brief announcement: Fast graphical population protocols. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.43\">https://doi.org/10.4230/LIPIcs.DISC.2021.43</a>","ista":"Alistarh D-A, Gelashvili R, Rybicki J. 2021. Brief announcement: Fast graphical population protocols. 35th International Symposium on Distributed Computing. DISC: Distributed Computing , LIPIcs, vol. 209, 43.","short":"D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","chicago":"Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Brief Announcement: Fast Graphical Population Protocols.” In <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.43\">https://doi.org/10.4230/LIPIcs.DISC.2021.43</a>.","ama":"Alistarh D-A, Gelashvili R, Rybicki J. Brief announcement: Fast graphical population protocols. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.43\">10.4230/LIPIcs.DISC.2021.43</a>","ieee":"D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Brief announcement: Fast graphical population protocols,” in <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209."},"quality_controlled":"1","author":[{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh"},{"full_name":"Gelashvili, Rati","last_name":"Gelashvili","first_name":"Rati"},{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel","last_name":"Rybicki","first_name":"Joel"}],"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"year":"2021","title":"Brief announcement: Fast graphical population protocols","publication":"35th International Symposium on Distributed Computing","oa":1,"ddc":["000"],"_id":"10218","project":[{"grant_number":"840605","name":"Coordination in constrained and natural distributed systems","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"publication_status":"published","abstract":[{"text":"Let G be a graph on n nodes. In the stochastic population protocol model, a collection of n indistinguishable, resource-limited nodes collectively solve tasks via pairwise interactions. In each interaction, two randomly chosen neighbors first read each other’s states, and then update their local states. A rich line of research has established tight upper and lower bounds on the complexity of fundamental tasks, such as majority and leader election, in this model, when G is a clique. Specifically, in the clique, these tasks can be solved fast, i.e., in n polylog n pairwise interactions, with high probability, using at most polylog n states per node. In this work, we consider the more general setting where G is an arbitrary graph, and present a technique for simulating protocols designed for fully-connected networks in any connected regular graph. Our main result is a simulation that is efficient on many interesting graph families: roughly, the simulation overhead is polylogarithmic in the number of nodes, and quadratic in the conductance of the graph. As an example, this implies that, in any regular graph with conductance φ, both leader election and exact majority can be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability, using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast and space-efficient population protocols for leader election and exact majority on graphs with good expansion properties.","lang":"eng"}],"date_published":"2021-10-04T00:00:00Z","external_id":{"arxiv":["2102.08808"]},"file":[{"file_size":534219,"creator":"cchlebak","content_type":"application/pdf","relation":"main_file","date_created":"2021-11-12T08:16:44Z","file_name":"2021_LIPIcsDISC_Alistarh.pdf","checksum":"fd2a690f6856d21247e9aa952b0e2885","access_level":"open_access","success":1,"date_updated":"2021-11-12T08:16:44Z","file_id":"10274"}],"alternative_title":["LIPIcs"],"publication_identifier":{"issn":["1868-8969"],"isbn":["9-783-9597-7210-5"]},"scopus_import":"1","arxiv":1,"article_processing_charge":"No","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","date_updated":"2023-02-21T09:24:08Z","type":"conference","oa_version":"Published Version","day":"04","ec_funded":1,"doi":"10.4230/LIPIcs.DISC.2021.43","language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"has_accepted_license":"1","acknowledgement":"This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 840605."},{"citation":{"ista":"Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. 2021. Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. 35th International Symposium on Distributed Computing. DISC: Distributed Computing , LIPIcs, vol. 209, 58.","short":"J. Korhonen, A. Paz, J. Rybicki, S. Schmid, J. Suomela, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.","chicago":"Korhonen, Janne, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela. “Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model.” In <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.58\">https://doi.org/10.4230/LIPIcs.DISC.2021.58</a>.","ama":"Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.58\">10.4230/LIPIcs.DISC.2021.58</a>","ieee":"J. Korhonen, A. Paz, J. Rybicki, S. Schmid, and J. Suomela, “Brief announcement: Sinkless orientation is hard also in the supported LOCAL model,” in <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209.","mla":"Korhonen, Janne, et al. “Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 58, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.58\">10.4230/LIPIcs.DISC.2021.58</a>.","apa":"Korhonen, J., Paz, A., Rybicki, J., Schmid, S., &#38; Suomela, J. (2021). Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.58\">https://doi.org/10.4230/LIPIcs.DISC.2021.58</a>"},"quality_controlled":"1","author":[{"first_name":"Janne","last_name":"Korhonen","full_name":"Korhonen, Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425"},{"first_name":"Ami","last_name":"Paz","full_name":"Paz, Ami"},{"first_name":"Joel","last_name":"Rybicki","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel"},{"full_name":"Schmid, Stefan","first_name":"Stefan","last_name":"Schmid"},{"first_name":"Jukka","last_name":"Suomela","full_name":"Suomela, Jukka"}],"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"year":"2021","publication":"35th International Symposium on Distributed Computing","title":"Brief announcement: Sinkless orientation is hard also in the supported LOCAL model","ddc":["000"],"oa":1,"_id":"10219","project":[{"grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"publication_status":"published","abstract":[{"lang":"eng","text":"We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is Ω(log n)."}],"volume":209,"file_date_updated":"2021-11-12T08:27:42Z","publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","intvolume":"       209","date_created":"2021-11-07T23:01:24Z","month":"10","conference":{"start_date":"2021-10-04","location":"Freiburg, Germany","name":"DISC: Distributed Computing ","end_date":"2021-10-08"},"article_number":"58","status":"public","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","article_processing_charge":"No","date_updated":"2021-11-12T09:37:18Z","type":"conference","oa_version":"Published Version","day":"04","ec_funded":1,"doi":"10.4230/LIPIcs.DISC.2021.58","language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"has_accepted_license":"1","acknowledgement":"Janne H. Korhonen: Project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). Ami Paz: We acknowledge the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N. Stefan Schmid: Research supported by the Austrian Science Fund (FWF) project ADVISE, I 4800-N, 2020-2023.\r\n","date_published":"2021-10-04T00:00:00Z","file":[{"file_size":474242,"creator":"cchlebak","content_type":"application/pdf","date_created":"2021-11-12T08:27:42Z","relation":"main_file","access_level":"open_access","file_name":"2021_LIPIcsDISC_Korhonen.pdf","checksum":"c43188dc2070bbd2bf5fd6fdaf9ce36d","file_id":"10275","date_updated":"2021-11-12T08:27:42Z","success":1}],"external_id":{"arxiv":["2108.02655"]},"alternative_title":["LIPIcs"],"publication_identifier":{"isbn":["9-783-9597-7210-5"],"issn":["1868-8969"]},"scopus_import":"1","arxiv":1},{"oa_version":"Published Version","type":"conference","date_updated":"2022-01-17T10:39:40Z","day":"29","article_processing_charge":"No","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","has_accepted_license":"1","department":[{"_id":"KrCh"}],"doi":"10.4230/LIPIcs.FSTTCS.2021.42","language":[{"iso":"eng"}],"file":[{"success":1,"date_updated":"2022-01-17T10:36:08Z","file_id":"10633","checksum":"71141acdeffa9056f24d6dbef952d254","file_name":"2021_LIPIcs_Chatterjee.pdf","access_level":"open_access","relation":"main_file","date_created":"2022-01-17T10:36:08Z","file_size":891566,"content_type":"application/pdf","creator":"cchlebak"}],"date_published":"2021-11-29T00:00:00Z","alternative_title":["LIPIcs"],"scopus_import":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-9597-7215-0"]},"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"year":"2021","citation":{"ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, “Quantitative verification on product graphs of small treewidth,” in <i>41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Virtual, 2021, vol. 213.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Quantitative verification on product graphs of small treewidth. In: <i>41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>. Vol 213. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2021.42\">10.4230/LIPIcs.FSTTCS.2021.42</a>","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2021. Quantitative verification on product graphs of small treewidth. 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 213, 42.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, in:, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. “Quantitative Verification on Product Graphs of Small Treewidth.” In <i>41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Vol. 213. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2021.42\">https://doi.org/10.4230/LIPIcs.FSTTCS.2021.42</a>.","mla":"Chatterjee, Krishnendu, et al. “Quantitative Verification on Product Graphs of Small Treewidth.” <i>41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, vol. 213, 42, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2021.42\">10.4230/LIPIcs.FSTTCS.2021.42</a>.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2021). Quantitative verification on product graphs of small treewidth. In <i>41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i> (Vol. 213). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2021.42\">https://doi.org/10.4230/LIPIcs.FSTTCS.2021.42</a>"},"author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen","first_name":"Rasmus"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","first_name":"Andreas","last_name":"Pavlogiannis"}],"quality_controlled":"1","abstract":[{"lang":"eng","text":"Product graphs arise naturally in formal verification and program analysis. For example, the analysis of two concurrent threads requires the product of two component control-flow graphs, and for language inclusion of deterministic automata the product of two automata is constructed. In many cases, the component graphs have constant treewidth, e.g., when the input contains control-flow graphs of programs. We consider the algorithmic analysis of products of two constant-treewidth graphs with respect to three classic specification languages, namely, (a) algebraic properties, (b) mean-payoff properties, and (c) initial credit for energy properties.\r\nOur main contributions are as follows. Consider a graph G that is the product of two constant-treewidth graphs of size n each. First, given an idempotent semiring, we present an algorithm that computes the semiring transitive closure of G in time Õ(n⁴). Since the output has size Θ(n⁴), our algorithm is optimal (up to polylog factors). Second, given a mean-payoff objective, we present an O(n³)-time algorithm for deciding whether the value of a starting state is non-negative, improving the previously known O(n⁴) bound. Third, given an initial credit for energy objective, we present an O(n⁵)-time algorithm for computing the minimum initial credit for all nodes of G, improving the previously known O(n⁸) bound. At the heart of our approach lies an algorithm for the efficient construction of strongly-balanced tree decompositions of constant-treewidth graphs. Given a constant-treewidth graph G' of n nodes and a positive integer λ, our algorithm constructs a binary tree decomposition of G' of width O(λ) with the property that the size of each subtree decreases geometrically with rate (1/2 + 2^{-λ})."}],"publication_status":"published","publication":"41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","title":"Quantitative verification on product graphs of small treewidth","_id":"10629","oa":1,"ddc":["000"],"file_date_updated":"2022-01-17T10:36:08Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":213,"conference":{"start_date":"2021-12-15","location":"Virtual","name":"FSTTCS: Foundations of Software Technology and Theoretical Computer Science","end_date":"2021-12-17"},"month":"11","date_created":"2022-01-16T23:01:28Z","status":"public","article_number":"42","intvolume":"       213"},{"title":"On the complexity of intersection non-emptiness for star-free language classes","publication":"41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","ddc":["000"],"oa":1,"_id":"10630","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"}],"publication_status":"published","abstract":[{"lang":"eng","text":"In the Intersection Non-emptiness problem, we are given a list of finite automata A_1, A_2,… , A_m over a common alphabet Σ as input, and the goal is to determine whether some string w ∈ Σ^* lies in the intersection of the languages accepted by the automata in the list. We analyze the complexity of the Intersection Non-emptiness problem under the promise that all input automata accept a language in some level of the dot-depth hierarchy, or some level of the Straubing-Thérien hierarchy. Automata accepting languages from the lowest levels of these hierarchies arise naturally in the context of model checking. We identify a dichotomy in the dot-depth hierarchy by showing that the problem is already NP-complete when all input automata accept languages of the levels B_0 or B_{1/2} and already PSPACE-hard when all automata accept a language from the level B_1. Conversely, we identify a tetrachotomy in the Straubing-Thérien hierarchy. More precisely, we show that the problem is in AC^0 when restricted to level L_0; complete for L or NL, depending on the input representation, when restricted to languages in the level L_{1/2}; NP-complete when the input is given as DFAs accepting a language in L_1 or L_{3/2}; and finally, PSPACE-complete when the input automata accept languages in level L_2 or higher. Moreover, we show that the proof technique used to show containment in NP for DFAs accepting languages in L_1 or L_{3/2} does not generalize to the context of NFAs. To prove this, we identify a family of languages that provide an exponential separation between the state complexity of general NFAs and that of partially ordered NFAs. To the best of our knowledge, this is the first superpolynomial separation between these two models of computation."}],"citation":{"mla":"Arrighi, Emmanuel, et al. “On the Complexity of Intersection Non-Emptiness for Star-Free Language Classes.” <i>41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, vol. 213, 34, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2021.34\">10.4230/LIPIcs.FSTTCS.2021.34</a>.","apa":"Arrighi, E., Fernau, H., Hoffmann, S., Holzer, M., Jecker, I. R., De Oliveira Oliveira, M., &#38; Wolf, P. (2021). On the complexity of intersection non-emptiness for star-free language classes. In <i>41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i> (Vol. 213). Virtual: Schloss Dagstuhl - Leibniz Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2021.34\">https://doi.org/10.4230/LIPIcs.FSTTCS.2021.34</a>","ieee":"E. Arrighi <i>et al.</i>, “On the complexity of intersection non-emptiness for star-free language classes,” in <i>41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Virtual, 2021, vol. 213.","ama":"Arrighi E, Fernau H, Hoffmann S, et al. On the complexity of intersection non-emptiness for star-free language classes. In: <i>41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>. Vol 213. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2021.34\">10.4230/LIPIcs.FSTTCS.2021.34</a>","ista":"Arrighi E, Fernau H, Hoffmann S, Holzer M, Jecker IR, De Oliveira Oliveira M, Wolf P. 2021. On the complexity of intersection non-emptiness for star-free language classes. 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 213, 34.","chicago":"Arrighi, Emmanuel, Henning Fernau, Stefan Hoffmann, Markus Holzer, Ismael R Jecker, Mateus De Oliveira Oliveira, and Petra Wolf. “On the Complexity of Intersection Non-Emptiness for Star-Free Language Classes.” In <i>41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Vol. 213. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2021.34\">https://doi.org/10.4230/LIPIcs.FSTTCS.2021.34</a>.","short":"E. Arrighi, H. Fernau, S. Hoffmann, M. Holzer, I.R. Jecker, M. De Oliveira Oliveira, P. Wolf, in:, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021."},"quality_controlled":"1","author":[{"first_name":"Emmanuel","last_name":"Arrighi","full_name":"Arrighi, Emmanuel"},{"full_name":"Fernau, Henning","last_name":"Fernau","first_name":"Henning"},{"full_name":"Hoffmann, Stefan","first_name":"Stefan","last_name":"Hoffmann"},{"last_name":"Holzer","first_name":"Markus","full_name":"Holzer, Markus"},{"last_name":"Jecker","first_name":"Ismael R","id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","full_name":"Jecker, Ismael R"},{"full_name":"De Oliveira Oliveira, Mateus","first_name":"Mateus","last_name":"De Oliveira Oliveira"},{"full_name":"Wolf, Petra","last_name":"Wolf","first_name":"Petra"}],"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"year":"2021","intvolume":"       213","date_created":"2022-01-16T23:01:29Z","month":"11","conference":{"location":"Virtual","start_date":"2021-12-15","name":"FSTTCS: Foundations of Software Technology and Theoretical Computer Science","end_date":"2021-12-17"},"status":"public","article_number":"34","volume":213,"file_date_updated":"2022-01-17T10:49:03Z","publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","ec_funded":1,"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.FSTTCS.2021.34","has_accepted_license":"1","department":[{"_id":"KrCh"}],"acknowledgement":"We like to thank Lukas Fleischer and Michael Wehar for our discussions. This work started at the Schloss Dagstuhl Event 20483 Moderne Aspekte der Komplexitätstheorie in der Automatentheorie https://www.dagstuhl.de/20483.\r\n","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","article_processing_charge":"No","date_updated":"2022-01-17T10:56:19Z","type":"conference","oa_version":"Published Version","day":"29","alternative_title":["LIPIcs"],"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-9597-7215-0"]},"scopus_import":"1","arxiv":1,"date_published":"2021-11-29T00:00:00Z","file":[{"date_created":"2022-01-17T10:49:03Z","relation":"main_file","file_size":844224,"creator":"cchlebak","content_type":"application/pdf","file_id":"10634","date_updated":"2022-01-17T10:49:03Z","success":1,"access_level":"open_access","file_name":"2021_LIPIcs_Arrighi.pdf","checksum":"d5a82ba893c3bc5da5914edbb3efb92b"}],"external_id":{"arxiv":["2110.01279"]}},{"publication_identifier":{"isbn":["978-3-95977-184-9"],"issn":["1868-8969"]},"alternative_title":["LIPIcs"],"page":"17:1-17:16","date_published":"2021-06-02T00:00:00Z","file":[{"date_created":"2021-06-02T10:22:33Z","relation":"main_file","file_size":1972902,"creator":"mwintrae","content_type":"application/pdf","file_id":"9442","date_updated":"2021-06-02T10:22:33Z","success":1,"access_level":"open_access","file_name":"LIPIcs-SoCG-2021-17.pdf","checksum":"c322aa48d5d35a35877896cc565705b6"}],"doi":"10.4230/LIPIcs.SoCG.2021.17","language":[{"iso":"eng"}],"department":[{"_id":"HeEd"}],"has_accepted_license":"1","ec_funded":1,"acknowledgement":"We thank Dominique Attali, Guilherme de Fonseca, Arijit Ghosh, Vincent Pilaud and Aurélien Alvarez for their comments and suggestions. We also acknowledge the reviewers.","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","article_processing_charge":"No","day":"02","date_updated":"2023-10-10T07:34:34Z","type":"conference","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","oa_version":"Published Version","place":"Dagstuhl, Germany","intvolume":"       189","status":"public","date_created":"2021-06-02T10:10:55Z","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2021-06-11","location":"Virtual","start_date":"2021-06-07"},"month":"06","volume":189,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2021-06-02T10:22:33Z","related_material":{"record":[{"id":"12960","status":"public","relation":"later_version"}]},"ddc":["005","516","514"],"oa":1,"_id":"9441","title":"Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations","publication":"37th International Symposium on Computational Geometry (SoCG 2021)","publication_status":"published","abstract":[{"text":"Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. submanifolds of ℝ^d defined as the zero set of some multivariate multivalued smooth function f: ℝ^d → ℝ^{d-n}, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M is to consider its Piecewise-Linear (PL) approximation M̂ based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ = 1/D (and unavoidably exponential in n). Since it is known that for δ = Ω (d^{2.5}), M̂ is O(D²)-close and isotopic to M, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M̂ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art. ","lang":"eng"}],"project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","author":[{"full_name":"Boissonnat, Jean-Daniel","last_name":"Boissonnat","first_name":"Jean-Daniel"},{"full_name":"Kachanovich, Siargey","first_name":"Siargey","last_name":"Kachanovich"},{"last_name":"Wintraecken","first_name":"Mathijs","full_name":"Wintraecken, Mathijs","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87"}],"citation":{"apa":"Boissonnat, J.-D., Kachanovich, S., &#38; Wintraecken, M. (2021). Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. In <i>37th International Symposium on Computational Geometry (SoCG 2021)</i> (Vol. 189, p. 17:1-17:16). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.17\">https://doi.org/10.4230/LIPIcs.SoCG.2021.17</a>","mla":"Boissonnat, Jean-Daniel, et al. “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn Triangulations.” <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>, vol. 189, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 17:1-17:16, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.17\">10.4230/LIPIcs.SoCG.2021.17</a>.","ista":"Boissonnat J-D, Kachanovich S, Wintraecken M. 2021. Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. 37th International Symposium on Computational Geometry (SoCG 2021). SoCG: Symposium on Computational GeometryLeibniz International Proceedings in Informatics (LIPIcs), LIPIcs, vol. 189, 17:1-17:16.","chicago":"Boissonnat, Jean-Daniel, Siargey Kachanovich, and Mathijs Wintraecken. “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn Triangulations.” In <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>, 189:17:1-17:16. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.17\">https://doi.org/10.4230/LIPIcs.SoCG.2021.17</a>.","short":"J.-D. Boissonnat, S. Kachanovich, M. Wintraecken, in:, 37th International Symposium on Computational Geometry (SoCG 2021), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2021, p. 17:1-17:16.","ieee":"J.-D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations,” in <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>, Virtual, 2021, vol. 189, p. 17:1-17:16.","ama":"Boissonnat J-D, Kachanovich S, Wintraecken M. Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. In: <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>. Vol 189. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021:17:1-17:16. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.17\">10.4230/LIPIcs.SoCG.2021.17</a>"},"year":"2021","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"}},{"arxiv":1,"alternative_title":["LIPIcs"],"scopus_import":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772044"]},"external_id":{"arxiv":["2106.14756"]},"date_published":"2021-08-31T00:00:00Z","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.ESA.2021.42","oa_version":"Published Version","date_updated":"2023-02-14T08:28:56Z","type":"conference","day":"31","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","conference":{"end_date":"2021-09-08","name":"ESA: Annual European Symposium on Algorithms","location":"Lisbon, Portual","start_date":"2021-09-06"},"month":"08","date_created":"2022-08-12T07:04:44Z","status":"public","article_number":"42","intvolume":"       204","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":204,"abstract":[{"lang":"eng","text":"Differentially private algorithms protect individuals in data analysis scenarios by ensuring that there is only a weak correlation between the existence of the user in the data and the result of the analysis. Dynamic graph algorithms maintain the solution to a problem (e.g., a matching) on an evolving input, i.e., a graph where nodes or edges are inserted or deleted over time. They output the value of the solution after each update operation, i.e., continuously. We study (event-level and user-level) differentially private algorithms for graph problems under continual observation, i.e., differentially private dynamic graph algorithms. We present event-level private algorithms for partially dynamic counting-based problems such as triangle count that improve the additive error by a polynomial factor (in the length T of the update sequence) on the state of the art, resulting in the first algorithms with additive error polylogarithmic in T.\r\nWe also give ε-differentially private and partially dynamic algorithms for minimum spanning tree, minimum cut, densest subgraph, and maximum matching. The additive error of our improved MST algorithm is O(W log^{3/2}T / ε), where W is the maximum weight of any edge, which, as we show, is tight up to a (√{log T} / ε)-factor. For the other problems, we present a partially-dynamic algorithm with multiplicative error (1+β) for any constant β > 0 and additive error O(W log(nW) log(T) / (ε β)). Finally, we show that the additive error for a broad class of dynamic graph algorithms with user-level privacy must be linear in the value of the output solution’s range."}],"publication_status":"published","title":"Differentially private algorithms for graphs under continual observation","publication":"29th Annual European Symposium on Algorithms","_id":"11814","oa":1,"year":"2021","main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.ESA.2021.42","open_access":"1"}],"citation":{"mla":"Fichtenberger, Hendrik, et al. “Differentially Private Algorithms for Graphs under Continual Observation.” <i>29th Annual European Symposium on Algorithms</i>, vol. 204, 42, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2021.42\">10.4230/LIPIcs.ESA.2021.42</a>.","apa":"Fichtenberger, H., Henzinger, M. H., &#38; Ost, W. (2021). Differentially private algorithms for graphs under continual observation. In <i>29th Annual European Symposium on Algorithms</i> (Vol. 204). Lisbon, Portual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2021.42\">https://doi.org/10.4230/LIPIcs.ESA.2021.42</a>","ama":"Fichtenberger H, Henzinger MH, Ost W. Differentially private algorithms for graphs under continual observation. In: <i>29th Annual European Symposium on Algorithms</i>. Vol 204. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2021.42\">10.4230/LIPIcs.ESA.2021.42</a>","ieee":"H. Fichtenberger, M. H. Henzinger, and W. Ost, “Differentially private algorithms for graphs under continual observation,” in <i>29th Annual European Symposium on Algorithms</i>, Lisbon, Portual, 2021, vol. 204.","chicago":"Fichtenberger, Hendrik, Monika H Henzinger, and Wolfgang Ost. “Differentially Private Algorithms for Graphs under Continual Observation.” In <i>29th Annual European Symposium on Algorithms</i>, Vol. 204. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2021.42\">https://doi.org/10.4230/LIPIcs.ESA.2021.42</a>.","short":"H. Fichtenberger, M.H. Henzinger, W. Ost, in:, 29th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","ista":"Fichtenberger H, Henzinger MH, Ost W. 2021. Differentially private algorithms for graphs under continual observation. 29th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 204, 42."},"author":[{"last_name":"Fichtenberger","first_name":"Hendrik","full_name":"Fichtenberger, Hendrik"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H"},{"last_name":"Ost","first_name":"Wolfgang","full_name":"Ost, Wolfgang"}],"extern":"1","quality_controlled":"1"},{"oa_version":"Published Version","series_title":"LIPIcs","type":"conference","date_updated":"2023-02-23T13:41:40Z","day":"03","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"Vitaly Aksenov: Government of Russian Federation (Grant 08-08).\r\nDan Alistarh: ERC Starting Grant 805223 ScaleML.","ec_funded":1,"department":[{"_id":"DaAl"}],"has_accepted_license":"1","license":"https://creativecommons.org/licenses/by/3.0/","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.DISC.2020.3","file":[{"date_created":"2021-03-11T12:33:35Z","relation":"main_file","content_type":"application/pdf","creator":"dernst","file_size":740358,"date_updated":"2021-03-11T12:33:35Z","file_id":"9237","success":1,"access_level":"open_access","checksum":"a626a9c47df52b6f6d97edd910dae4ba","file_name":"2020_LIPIcs_Aksenov.pdf"}],"external_id":{"arxiv":["2008.01009"]},"date_published":"2020-08-03T00:00:00Z","page":"3:1-3:18","arxiv":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771689"]},"tmp":{"short":"CC BY (3.0)","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","image":"/images/cc_by.png"},"year":"2020","citation":{"ista":"Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. 2020. The splay-list: A distribution-adaptive concurrent skip-list. 34th International Symposium on Distributed Computing. DISC: Symposium on Distributed ComputingLIPIcs vol. 179, 3:1-3:18.","chicago":"Aksenov, Vitaly, Dan-Adrian Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” In <i>34th International Symposium on Distributed Computing</i>, 179:3:1-3:18. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2020.3\">https://doi.org/10.4230/LIPIcs.DISC.2020.3</a>.","short":"V. Aksenov, D.-A. Alistarh, A. Drozdova, A. Mohtashami, in:, 34th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 3:1-3:18.","ama":"Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. The splay-list: A distribution-adaptive concurrent skip-list. In: <i>34th International Symposium on Distributed Computing</i>. Vol 179. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020:3:1-3:18. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2020.3\">10.4230/LIPIcs.DISC.2020.3</a>","ieee":"V. Aksenov, D.-A. Alistarh, A. Drozdova, and A. Mohtashami, “The splay-list: A distribution-adaptive concurrent skip-list,” in <i>34th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2020, vol. 179, p. 3:1-3:18.","mla":"Aksenov, Vitaly, et al. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” <i>34th International Symposium on Distributed Computing</i>, vol. 179, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 3:1-3:18, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2020.3\">10.4230/LIPIcs.DISC.2020.3</a>.","apa":"Aksenov, V., Alistarh, D.-A., Drozdova, A., &#38; Mohtashami, A. (2020). The splay-list: A distribution-adaptive concurrent skip-list. In <i>34th International Symposium on Distributed Computing</i> (Vol. 179, p. 3:1-3:18). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2020.3\">https://doi.org/10.4230/LIPIcs.DISC.2020.3</a>"},"quality_controlled":"1","author":[{"last_name":"Aksenov","first_name":"Vitaly","full_name":"Aksenov, Vitaly"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","first_name":"Dan-Adrian"},{"full_name":"Drozdova, Alexandra","first_name":"Alexandra","last_name":"Drozdova"},{"first_name":"Amirkeivan","last_name":"Mohtashami","full_name":"Mohtashami, Amirkeivan"}],"project":[{"grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"abstract":[{"text":"The design and implementation of efficient concurrent data structures have\r\nseen significant attention. However, most of this work has focused on\r\nconcurrent data structures providing good \\emph{worst-case} guarantees. In real\r\nworkloads, objects are often accessed at different rates, since access\r\ndistributions may be non-uniform. Efficient distribution-adaptive data\r\nstructures are known in the sequential case, e.g. the splay-trees; however,\r\nthey often are hard to translate efficiently in the concurrent case.\r\n  In this paper, we investigate distribution-adaptive concurrent data\r\nstructures and propose a new design called the splay-list. At a high level, the\r\nsplay-list is similar to a standard skip-list, with the key distinction that\r\nthe height of each element adapts dynamically to its access rate: popular\r\nelements ``move up,'' whereas rarely-accessed elements decrease in height. We\r\nshow that the splay-list provides order-optimal amortized complexity bounds for\r\na subset of operations while being amenable to efficient concurrent\r\nimplementation. Experimental results show that the splay-list can leverage\r\ndistribution-adaptivity to improve on the performance of classic concurrent\r\ndesigns, and can outperform the only previously-known distribution-adaptive\r\ndesign in certain settings.","lang":"eng"}],"publication_status":"published","publication":"34th International Symposium on Distributed Computing","title":"The splay-list: A distribution-adaptive concurrent skip-list","_id":"8725","oa":1,"ddc":["000"],"file_date_updated":"2021-03-11T12:33:35Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":179,"month":"08","conference":{"end_date":"2020-10-16","name":"DISC: Symposium on Distributed Computing","location":"Freiburg, Germany","start_date":"2020-10-12"},"date_created":"2020-11-05T15:26:17Z","status":"public","intvolume":"       179"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","type":"conference","date_updated":"2021-01-12T08:13:12Z","oa_version":"Published Version","day":"15","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.CSL.2020.20","department":[{"_id":"ToHe"}],"has_accepted_license":"1","date_published":"2020-01-15T00:00:00Z","file":[{"creator":"bkragl","content_type":"application/pdf","file_size":617206,"relation":"main_file","date_created":"2020-01-21T11:21:04Z","file_name":"main.pdf","checksum":"b9a691d658d075c6369d3304d17fb818","access_level":"open_access","file_id":"7349","date_updated":"2020-07-14T12:47:56Z"}],"external_id":{"arxiv":["1910.06097"]},"alternative_title":["LIPIcs"],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771320"]},"scopus_import":1,"arxiv":1,"citation":{"chicago":"Ferrere, Thomas, Thomas A Henzinger, and Bernhard Kragl. “Monitoring Event Frequencies.” In <i>28th EACSL Annual Conference on Computer Science Logic</i>, Vol. 152. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.CSL.2020.20\">https://doi.org/10.4230/LIPIcs.CSL.2020.20</a>.","short":"T. Ferrere, T.A. Henzinger, B. Kragl, in:, 28th EACSL Annual Conference on Computer Science Logic, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ista":"Ferrere T, Henzinger TA, Kragl B. 2020. Monitoring event frequencies. 28th EACSL Annual Conference on Computer Science Logic. CSL: Computer Science Logic, LIPIcs, vol. 152, 20.","ieee":"T. Ferrere, T. A. Henzinger, and B. Kragl, “Monitoring event frequencies,” in <i>28th EACSL Annual Conference on Computer Science Logic</i>, Barcelona, Spain, 2020, vol. 152.","ama":"Ferrere T, Henzinger TA, Kragl B. Monitoring event frequencies. In: <i>28th EACSL Annual Conference on Computer Science Logic</i>. Vol 152. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CSL.2020.20\">10.4230/LIPIcs.CSL.2020.20</a>","mla":"Ferrere, Thomas, et al. “Monitoring Event Frequencies.” <i>28th EACSL Annual Conference on Computer Science Logic</i>, vol. 152, 20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CSL.2020.20\">10.4230/LIPIcs.CSL.2020.20</a>.","apa":"Ferrere, T., Henzinger, T. A., &#38; Kragl, B. (2020). Monitoring event frequencies. In <i>28th EACSL Annual Conference on Computer Science Logic</i> (Vol. 152). Barcelona, Spain: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CSL.2020.20\">https://doi.org/10.4230/LIPIcs.CSL.2020.20</a>"},"quality_controlled":"1","author":[{"id":"40960E6E-F248-11E8-B48F-1D18A9856A87","full_name":"Ferrere, Thomas","orcid":"0000-0001-5199-3143","first_name":"Thomas","last_name":"Ferrere"},{"last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kragl","first_name":"Bernhard","id":"320FC952-F248-11E8-B48F-1D18A9856A87","full_name":"Kragl, Bernhard","orcid":"0000-0001-7745-9117"}],"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"year":"2020","publication":"28th EACSL Annual Conference on Computer Science Logic","title":"Monitoring event frequencies","ddc":["000"],"oa":1,"_id":"7348","project":[{"_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S11402-N23"},{"call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","grant_number":"Z211"}],"publication_status":"published","abstract":[{"text":"The monitoring of event frequencies can be used to recognize behavioral anomalies, to identify trends, and to deduce or discard hypotheses about the underlying system. For example, the performance of a web server may be monitored based on the ratio of the total count of requests from the least and most active clients. Exact frequency monitoring, however, can be prohibitively expensive; in the above example it would require as many counters as there are clients. In this paper, we propose the efficient probabilistic monitoring of common frequency properties, including the mode (i.e., the most common event) and the median of an event sequence. We define a logic to express composite frequency properties as a combination of atomic frequency properties. Our main contribution is an algorithm that, under suitable probabilistic assumptions, can be used to monitor these important frequency properties with four counters, independent of the number of different events. Our algorithm samples longer and longer subwords of an infinite event sequence. We prove the almost-sure convergence of our algorithm by generalizing ergodic theory from increasing-length prefixes to increasing-length subwords of an infinite sequence. A similar algorithm could be used to learn a connected Markov chain of a given structure from observing its outputs, to arbitrary precision, for a given confidence. ","lang":"eng"}],"volume":152,"file_date_updated":"2020-07-14T12:47:56Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","intvolume":"       152","date_created":"2020-01-21T11:22:21Z","conference":{"name":"CSL: Computer Science Logic","end_date":"2020-01-16","location":"Barcelona, Spain","start_date":"2020-01-13"},"month":"01","status":"public","article_number":"20"},{"alternative_title":["LIPIcs"],"scopus_import":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-143-6"]},"file":[{"file_id":"7969","date_updated":"2020-07-14T12:48:06Z","file_name":"2020_LIPIcsSoCG_Boissonnat.pdf","checksum":"38cbfa4f5d484d267a35d44d210df044","access_level":"open_access","relation":"main_file","date_created":"2020-06-17T10:13:34Z","file_size":1009739,"creator":"dernst","content_type":"application/pdf"}],"date_published":"2020-06-01T00:00:00Z","ec_funded":1,"department":[{"_id":"HeEd"}],"has_accepted_license":"1","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2020.20","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","oa_version":"Published Version","date_updated":"2023-08-02T06:49:16Z","type":"conference","day":"01","intvolume":"       164","month":"06","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2020-06-26","start_date":"2020-06-22","location":"Zürich, Switzerland"},"date_created":"2020-06-09T07:24:11Z","status":"public","article_number":"20:1-20:18","volume":164,"file_date_updated":"2020-07-14T12:48:06Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication":"36th International Symposium on Computational Geometry","title":"The topological correctness of PL-approximations of isomanifolds","_id":"7952","ddc":["510"],"related_material":{"record":[{"relation":"later_version","status":"public","id":"9649"}]},"oa":1,"project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"abstract":[{"text":"Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued smooth function f: ℝ^d → ℝ^(d-n). A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently fine triangulation 𝒯. This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary. ","lang":"eng"}],"publication_status":"published","citation":{"mla":"Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness of PL-Approximations of Isomanifolds.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 20:1-20:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.20\">10.4230/LIPIcs.SoCG.2020.20</a>.","apa":"Boissonnat, J.-D., &#38; Wintraecken, M. (2020). The topological correctness of PL-approximations of isomanifolds. In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.20\">https://doi.org/10.4230/LIPIcs.SoCG.2020.20</a>","ista":"Boissonnat J-D, Wintraecken M. 2020. The topological correctness of PL-approximations of isomanifolds. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 20:1-20:18.","short":"J.-D. Boissonnat, M. Wintraecken, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","chicago":"Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness of PL-Approximations of Isomanifolds.” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.20\">https://doi.org/10.4230/LIPIcs.SoCG.2020.20</a>.","ama":"Boissonnat J-D, Wintraecken M. The topological correctness of PL-approximations of isomanifolds. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.20\">10.4230/LIPIcs.SoCG.2020.20</a>","ieee":"J.-D. Boissonnat and M. Wintraecken, “The topological correctness of PL-approximations of isomanifolds,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164."},"author":[{"full_name":"Boissonnat, Jean-Daniel","first_name":"Jean-Daniel","last_name":"Boissonnat"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs","first_name":"Mathijs","last_name":"Wintraecken"}],"quality_controlled":"1","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"year":"2020"},{"doi":"10.4230/LIPIcs.ESA.2020.58","language":[{"iso":"eng"}],"day":"26","date_updated":"2023-02-14T08:57:55Z","type":"conference","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","arxiv":1,"publication_identifier":{"isbn":["9783959771627"],"issn":["1868-8969"]},"scopus_import":"1","alternative_title":["LIPIcs"],"date_published":"2020-08-26T00:00:00Z","external_id":{"arxiv":["2004.09099"]},"publication_status":"published","abstract":[{"text":"In recent years, significant advances have been made in the design and analysis of fully dynamic maximal matching algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. In this paper, we attempt to bridge the gap between theory and practice that is currently observed for the fully dynamic maximal matching problem. We engineer several algorithms and empirically study those algorithms on an extensive set of dynamic instances.","lang":"eng"}],"oa":1,"_id":"11816","publication":"8th Annual European Symposium on Algorithms","title":"Dynamic matching algorithms in practice","year":"2020","quality_controlled":"1","extern":"1","author":[{"first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Shahbaz","first_name":"Khan","full_name":"Shahbaz, Khan"},{"full_name":"Paul, Richard","first_name":"Richard","last_name":"Paul"},{"last_name":"Schulz","first_name":"Christian","full_name":"Schulz, Christian"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.ESA.2020.58"}],"citation":{"ama":"Henzinger MH, Shahbaz K, Paul R, Schulz C. Dynamic matching algorithms in practice. In: <i>8th Annual European Symposium on Algorithms</i>. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.58\">10.4230/LIPIcs.ESA.2020.58</a>","ieee":"M. H. Henzinger, K. Shahbaz, R. Paul, and C. Schulz, “Dynamic matching algorithms in practice,” in <i>8th Annual European Symposium on Algorithms</i>, Pisa, Italy, 2020, vol. 173.","short":"M.H. Henzinger, K. Shahbaz, R. Paul, C. Schulz, in:, 8th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","chicago":"Henzinger, Monika H, Khan Shahbaz, Richard Paul, and Christian Schulz. “Dynamic Matching Algorithms in Practice.” In <i>8th Annual European Symposium on Algorithms</i>, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.58\">https://doi.org/10.4230/LIPIcs.ESA.2020.58</a>.","ista":"Henzinger MH, Shahbaz K, Paul R, Schulz C. 2020. Dynamic matching algorithms in practice. 8th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 58.","apa":"Henzinger, M. H., Shahbaz, K., Paul, R., &#38; Schulz, C. (2020). Dynamic matching algorithms in practice. In <i>8th Annual European Symposium on Algorithms</i> (Vol. 173). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.58\">https://doi.org/10.4230/LIPIcs.ESA.2020.58</a>","mla":"Henzinger, Monika H., et al. “Dynamic Matching Algorithms in Practice.” <i>8th Annual European Symposium on Algorithms</i>, vol. 173, 58, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.58\">10.4230/LIPIcs.ESA.2020.58</a>."},"status":"public","article_number":"58","date_created":"2022-08-12T07:13:25Z","conference":{"location":"Pisa, Italy","start_date":"2020-09-07","name":"ESA: Annual European Symposium on Algorithms","end_date":"2020-09-09"},"month":"08","intvolume":"       173","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":173},{"volume":173,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","intvolume":"       173","date_created":"2022-08-12T07:22:55Z","month":"08","conference":{"start_date":"2020-09-07","location":"Pisa, Italy","end_date":"2020-09-09","name":"ESA: Annual European Symposium on Algorithms"},"status":"public","article_number":"57","main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.ESA.2020.57","open_access":"1"}],"citation":{"ama":"Henzinger MH, Kale S. Fully-dynamic coresets. In: <i>28th Annual European Symposium on Algorithms</i>. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.57\">10.4230/LIPIcs.ESA.2020.57</a>","ieee":"M. H. Henzinger and S. Kale, “Fully-dynamic coresets,” in <i>28th Annual European Symposium on Algorithms</i>, Pisa, Italy, 2020, vol. 173.","chicago":"Henzinger, Monika H, and Sagar Kale. “Fully-Dynamic Coresets.” In <i>28th Annual European Symposium on Algorithms</i>, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.57\">https://doi.org/10.4230/LIPIcs.ESA.2020.57</a>.","short":"M.H. Henzinger, S. Kale, in:, 28th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ista":"Henzinger MH, Kale S. 2020. Fully-dynamic coresets. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 57.","apa":"Henzinger, M. H., &#38; Kale, S. (2020). Fully-dynamic coresets. In <i>28th Annual European Symposium on Algorithms</i> (Vol. 173). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.57\">https://doi.org/10.4230/LIPIcs.ESA.2020.57</a>","mla":"Henzinger, Monika H., and Sagar Kale. “Fully-Dynamic Coresets.” <i>28th Annual European Symposium on Algorithms</i>, vol. 173, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.57\">10.4230/LIPIcs.ESA.2020.57</a>."},"quality_controlled":"1","extern":"1","author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger"},{"full_name":"Kale, Sagar","first_name":"Sagar","last_name":"Kale"}],"year":"2020","publication":"28th Annual European Symposium on Algorithms","title":"Fully-dynamic coresets","oa":1,"_id":"11818","publication_status":"published","abstract":[{"lang":"eng","text":"With input sizes becoming massive, coresets - small yet representative summary of the input - are relevant more than ever. A weighted set C_w that is a subset of the input is an ε-coreset if the cost of any feasible solution S with respect to C_w is within [1±ε] of the cost of S with respect to the original input. We give a very general technique to compute coresets in the fully-dynamic setting where input points can be added or deleted. Given a static (i.e., not dynamic) ε-coreset-construction algorithm that runs in time t(n, ε, λ) and computes a coreset of size s(n, ε, λ), where n is the number of input points and 1-λ is the success probability, we give a fully-dynamic algorithm that computes an ε-coreset with worst-case update time O((log n) ⋅ t(s(n, ε/log n, λ/n), ε/log n, λ/n)) (this bound is stated informally), where the success probability is 1-λ. Our technique is a fully-dynamic analog of the merge-and-reduce technique, which is due to Har-Peled and Mazumdar [Har-Peled and Mazumdar, 2004] and is based on a technique of Bentley and Saxe [Jon Louis Bentley and James B. Saxe, 1980], that applies to the insertion-only setting where points can only be added. Although, our space usage is O(n), our technique works in the presence of an adaptive adversary, and we show that Ω(n) space is required when adversary is adaptive.\r\nAs a concrete implication of our technique, using the result of Braverman et al. [{Braverman} et al., 2016], we get fully-dynamic ε-coreset-construction algorithms for k-median and k-means with worst-case update time O(ε^{-2} k² log⁵ n log³ k) and coreset size O(ε^{-2} k log n log² k) ignoring log log n and log(1/ε) factors and assuming that ε = Ω(1/poly(n)) and λ = Ω(1/poly(n)) (which are very weak assumptions made only to make these bounds easy to parse). This results in the first fully-dynamic constant-approximation algorithms for k-median and k-means with update times O(poly(k, log n, ε^{-1})). Specifically, the dependence on k is only quadratic, and the bounds are worst-case. The best previous bound for both problems was amortized O(nlog n) by Cohen-Addad et al. [Cohen-Addad et al., 2019] via randomized O(1)-coresets in O(n) space.\r\nWe also show that under the OMv conjecture [Monika Henzinger et al., 2015], a fully-dynamic (4 - δ)-approximation algorithm for k-means must either have an amortized update time of Ω(k^{1-γ}) or amortized query time of Ω(k^{2 - γ}), where γ > 0 is a constant."}],"date_published":"2020-08-26T00:00:00Z","external_id":{"arxiv":["2004.14891"]},"alternative_title":["LIPIcs"],"publication_identifier":{"isbn":["9783959771627"],"issn":["1868-8969"]},"scopus_import":"1","arxiv":1,"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-14T09:29:51Z","type":"conference","oa_version":"Published Version","day":"26","doi":"10.4230/LIPIcs.ESA.2020.57","language":[{"iso":"eng"}]},{"day":"26","date_updated":"2023-02-14T09:39:18Z","type":"conference","oa_version":"Published Version","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.4230/LIPIcs.ESA.2020.59","language":[{"iso":"eng"}],"date_published":"2020-08-26T00:00:00Z","external_id":{"arxiv":["2002.06948"]},"arxiv":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771627"]},"scopus_import":"1","alternative_title":["LIPIcs"],"year":"2020","quality_controlled":"1","extern":"1","author":[{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Noe, Alexander","last_name":"Noe","first_name":"Alexander"},{"last_name":"Schulz","first_name":"Christian","full_name":"Schulz, Christian"},{"full_name":"Strash, Darren","last_name":"Strash","first_name":"Darren"}],"main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.ESA.2020.59","open_access":"1"}],"citation":{"ista":"Henzinger MH, Noe A, Schulz C, Strash D. 2020. Finding all global minimum cuts in practice. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 59.","short":"M.H. Henzinger, A. Noe, C. Schulz, D. Strash, in:, 28th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","chicago":"Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash. “Finding All Global Minimum Cuts in Practice.” In <i>28th Annual European Symposium on Algorithms</i>, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.59\">https://doi.org/10.4230/LIPIcs.ESA.2020.59</a>.","ama":"Henzinger MH, Noe A, Schulz C, Strash D. Finding all global minimum cuts in practice. In: <i>28th Annual European Symposium on Algorithms</i>. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.59\">10.4230/LIPIcs.ESA.2020.59</a>","ieee":"M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Finding all global minimum cuts in practice,” in <i>28th Annual European Symposium on Algorithms</i>, Pisa, Italy, 2020, vol. 173.","mla":"Henzinger, Monika H., et al. “Finding All Global Minimum Cuts in Practice.” <i>28th Annual European Symposium on Algorithms</i>, vol. 173, 59, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.59\">10.4230/LIPIcs.ESA.2020.59</a>.","apa":"Henzinger, M. H., Noe, A., Schulz, C., &#38; Strash, D. (2020). Finding all global minimum cuts in practice. In <i>28th Annual European Symposium on Algorithms</i> (Vol. 173). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.59\">https://doi.org/10.4230/LIPIcs.ESA.2020.59</a>"},"publication_status":"published","abstract":[{"text":"We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph to a small equivalent instance and then finds all minimum cuts using an optimized version of the algorithm of Nagamochi, Nakao and Ibaraki. In shared memory we are able to find all minimum cuts of graphs with up to billions of edges and millions of minimum cuts in a few minutes. We also give a new linear time algorithm to find the most balanced minimum cuts given as input the representation of all minimum cuts.","lang":"eng"}],"oa":1,"_id":"11819","publication":"28th Annual European Symposium on Algorithms","title":"Finding all global minimum cuts in practice","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":173,"article_number":"59","status":"public","date_created":"2022-08-12T07:27:42Z","month":"08","conference":{"name":"ESA: Annual European Symposium on Algorithms","end_date":"2020-09-09","location":"Pisa, Italy","start_date":"2020-09-07"},"intvolume":"       173"},{"intvolume":"       160","month":"06","conference":{"location":"Pisa, Italy","start_date":"2020-09-07","name":"SEA: Symposium on Experimental Algorithms","end_date":"2020-09-09"},"date_created":"2022-08-12T07:32:53Z","status":"public","article_number":"14","volume":160,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","title":"Faster fully dynamic transitive closure in practice","publication":"18th International Symposium on Experimental Algorithms","_id":"11822","oa":1,"abstract":[{"text":"The fully dynamic transitive closure problem asks to maintain reachability information in a directed graph between arbitrary pairs of vertices, while the graph undergoes a sequence of edge insertions and deletions. The problem has been thoroughly investigated in theory and many specialized algorithms for solving it have been proposed in the last decades. In two large studies [Frigioni ea, 2001; Krommidas and Zaroliagis, 2008], a number of these algorithms have been evaluated experimentally against simple, static algorithms for graph traversal, showing the competitiveness and even superiority of the simple algorithms in practice, except for very dense random graphs or very high ratios of queries. A major drawback of those studies is that only small and mostly randomly generated graphs are considered.\r\nIn this paper, we engineer new algorithms to maintain all-pairs reachability information which are simple and space-efficient. Moreover, we perform an extensive experimental evaluation on both generated and real-world instances that are several orders of magnitude larger than those in the previous studies. Our results indicate that our new algorithms outperform all state-of-the-art algorithms on all types of input considerably in practice.","lang":"eng"}],"publication_status":"published","citation":{"short":"K. Hanauer, M.H. Henzinger, C. Schulz, in:, 18th International Symposium on Experimental Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","chicago":"Hanauer, Kathrin, Monika H Henzinger, and Christian Schulz. “Faster Fully Dynamic Transitive Closure in Practice.” In <i>18th International Symposium on Experimental Algorithms</i>, Vol. 160. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SEA.2020.14\">https://doi.org/10.4230/LIPIcs.SEA.2020.14</a>.","ista":"Hanauer K, Henzinger MH, Schulz C. 2020. Faster fully dynamic transitive closure in practice. 18th International Symposium on Experimental Algorithms. SEA: Symposium on Experimental Algorithms, LIPIcs, vol. 160, 14.","ieee":"K. Hanauer, M. H. Henzinger, and C. Schulz, “Faster fully dynamic transitive closure in practice,” in <i>18th International Symposium on Experimental Algorithms</i>, Pisa, Italy, 2020, vol. 160.","ama":"Hanauer K, Henzinger MH, Schulz C. Faster fully dynamic transitive closure in practice. In: <i>18th International Symposium on Experimental Algorithms</i>. Vol 160. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SEA.2020.14\">10.4230/LIPIcs.SEA.2020.14</a>","mla":"Hanauer, Kathrin, et al. “Faster Fully Dynamic Transitive Closure in Practice.” <i>18th International Symposium on Experimental Algorithms</i>, vol. 160, 14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SEA.2020.14\">10.4230/LIPIcs.SEA.2020.14</a>.","apa":"Hanauer, K., Henzinger, M. H., &#38; Schulz, C. (2020). Faster fully dynamic transitive closure in practice. In <i>18th International Symposium on Experimental Algorithms</i> (Vol. 160). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SEA.2020.14\">https://doi.org/10.4230/LIPIcs.SEA.2020.14</a>"},"main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.SEA.2020.14","open_access":"1"}],"author":[{"last_name":"Hanauer","first_name":"Kathrin","full_name":"Hanauer, Kathrin"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H"},{"last_name":"Schulz","first_name":"Christian","full_name":"Schulz, Christian"}],"quality_controlled":"1","extern":"1","year":"2020","alternative_title":["LIPIcs"],"scopus_import":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771481"]},"arxiv":1,"external_id":{"arxiv":["2002.00813"]},"date_published":"2020-06-12T00:00:00Z","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SEA.2020.14","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","oa_version":"Published Version","date_updated":"2023-02-14T09:58:42Z","type":"conference","day":"12"},{"oa_version":"Published Version","date_updated":"2023-02-14T10:00:58Z","type":"conference","day":"08","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","doi":"10.4230/LIPIcs.SoCG.2020.51","language":[{"iso":"eng"}],"external_id":{"arxiv":["2003.02605"]},"date_published":"2020-06-08T00:00:00Z","arxiv":1,"alternative_title":["LIPIcs"],"scopus_import":"1","publication_identifier":{"isbn":["9783959771436"],"issn":["1868-8969"]},"year":"2020","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.SoCG.2020.51"}],"citation":{"ieee":"M. H. Henzinger, S. Neumann, and A. Wiese, “Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles,” in <i>36th International Symposium on Computational Geometry</i>, Zurich, Switzerland, 2020, vol. 164.","ama":"Henzinger MH, Neumann S, Wiese A. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.51\">10.4230/LIPIcs.SoCG.2020.51</a>","ista":"Henzinger MH, Neumann S, Wiese A. 2020. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 51.","short":"M.H. Henzinger, S. Neumann, A. Wiese, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","chicago":"Henzinger, Monika H, Stefan Neumann, and Andreas Wiese. “Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles.” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.51\">https://doi.org/10.4230/LIPIcs.SoCG.2020.51</a>.","apa":"Henzinger, M. H., Neumann, S., &#38; Wiese, A. (2020). Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zurich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.51\">https://doi.org/10.4230/LIPIcs.SoCG.2020.51</a>","mla":"Henzinger, Monika H., et al. “Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 51, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.51\">10.4230/LIPIcs.SoCG.2020.51</a>."},"extern":"1","quality_controlled":"1","author":[{"last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"full_name":"Neumann, Stefan","last_name":"Neumann","first_name":"Stefan"},{"full_name":"Wiese, Andreas","first_name":"Andreas","last_name":"Wiese"}],"abstract":[{"text":"Independent set is a fundamental problem in combinatorial optimization. While in general graphs the problem is essentially inapproximable, for many important graph classes there are approximation algorithms known in the offline setting. These graph classes include interval graphs and geometric intersection graphs, where vertices correspond to intervals/geometric objects and an edge indicates that the two corresponding objects intersect.\r\nWe present dynamic approximation algorithms for independent set of intervals, hypercubes and hyperrectangles in d dimensions. They work in the fully dynamic model where each update inserts or deletes a geometric object. All our algorithms are deterministic and have worst-case update times that are polylogarithmic for constant d and ε>0, assuming that the coordinates of all input objects are in [0, N]^d and each of their edges has length at least 1. We obtain the following results:\r\n- For weighted intervals, we maintain a (1+ε)-approximate solution.\r\n- For d-dimensional hypercubes we maintain a (1+ε)2^d-approximate solution in the unweighted case and a O(2^d)-approximate solution in the weighted case. Also, we show that for maintaining an unweighted (1+ε)-approximate solution one needs polynomial update time for d ≥ 2 if the ETH holds.\r\n- For weighted d-dimensional hyperrectangles we present a dynamic algorithm with approximation ratio (1+ε)log^{d-1}N.","lang":"eng"}],"publication_status":"published","title":"Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles","publication":"36th International Symposium on Computational Geometry","_id":"11824","oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":164,"conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2020-06-26","location":"Zurich, Switzerland","start_date":"2020-06-23"},"month":"06","date_created":"2022-08-12T07:46:44Z","status":"public","article_number":"51","intvolume":"       164"},{"oa":1,"_id":"11825","title":"Constant-time dynamic (Δ+1)-coloring","publication":"37th International Symposium on Theoretical Aspects of Computer Science","publication_status":"published","abstract":[{"lang":"eng","text":"We give a fully dynamic (Las-Vegas style) algorithm with constant expected amortized time per update that maintains a proper (Δ+1)-vertex coloring of a graph with maximum degree at most Δ. This improves upon the previous O(log Δ)-time algorithm by Bhattacharya et al. (SODA 2018). Our algorithm uses an approach based on assigning random ranks to vertices and does not need to maintain a hierarchical graph decomposition. We show that our result does not only have optimal running time, but is also optimal in the sense that already deciding whether a Δ-coloring exists in a dynamically changing graph with maximum degree at most Δ takes Ω(log n) time per operation."}],"quality_controlled":"1","author":[{"first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"full_name":"Peng, Pan","last_name":"Peng","first_name":"Pan"}],"extern":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.STACS.2020.53"}],"citation":{"chicago":"Henzinger, Monika H, and Pan Peng. “Constant-Time Dynamic (Δ+1)-Coloring.” In <i>37th International Symposium on Theoretical Aspects of Computer Science</i>, Vol. 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2020.53\">https://doi.org/10.4230/LIPIcs.STACS.2020.53</a>.","short":"M.H. Henzinger, P. Peng, in:, 37th International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ista":"Henzinger MH, Peng P. 2020. Constant-time dynamic (Δ+1)-coloring. 37th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 154, 53.","ama":"Henzinger MH, Peng P. Constant-time dynamic (Δ+1)-coloring. In: <i>37th International Symposium on Theoretical Aspects of Computer Science</i>. Vol 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2020.53\">10.4230/LIPIcs.STACS.2020.53</a>","ieee":"M. H. Henzinger and P. Peng, “Constant-time dynamic (Δ+1)-coloring,” in <i>37th International Symposium on Theoretical Aspects of Computer Science</i>, Montpellier, France, 2020, vol. 154.","mla":"Henzinger, Monika H., and Pan Peng. “Constant-Time Dynamic (Δ+1)-Coloring.” <i>37th International Symposium on Theoretical Aspects of Computer Science</i>, vol. 154, 53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2020.53\">10.4230/LIPIcs.STACS.2020.53</a>.","apa":"Henzinger, M. H., &#38; Peng, P. (2020). Constant-time dynamic (Δ+1)-coloring. In <i>37th International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 154). Montpellier, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2020.53\">https://doi.org/10.4230/LIPIcs.STACS.2020.53</a>"},"year":"2020","intvolume":"       154","status":"public","article_number":"53","date_created":"2022-08-12T07:53:05Z","conference":{"name":"STACS: Symposium on Theoretical Aspects of Computer Science","end_date":"2020-03-13","start_date":"2020-03-10","location":"Montpellier, France"},"month":"03","volume":154,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","doi":"10.4230/LIPIcs.STACS.2020.53","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","day":"04","type":"conference","date_updated":"2023-02-14T10:03:43Z","oa_version":"Published Version","publication_identifier":{"isbn":["9783959771405"],"issn":["1868-8969"]},"scopus_import":"1","alternative_title":["LIPIcs"],"arxiv":1,"date_published":"2020-03-04T00:00:00Z","external_id":{"arxiv":["1907.04745"]}}]