[{"date_published":"2024-01-18T00:00:00Z","author":[{"last_name":"Hirvonen","first_name":"Juho","full_name":"Hirvonen, Juho"},{"first_name":"Laura","full_name":"Schmid, Laura","orcid":"0000-0002-6978-7329","last_name":"Schmid","id":"38B437DE-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"last_name":"Schmid","first_name":"Stefan","full_name":"Schmid, Stefan"}],"oa":1,"_id":"15006","type":"conference","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.OPODIS.2023.11","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2024","volume":286,"month":"01","quality_controlled":"1","publication_identifier":{"issn":["18688969"],"isbn":["9783959773089"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"article_processing_charge":"No","conference":{"location":"Tokyo, Japan","end_date":"2023-12-08","start_date":"2023-12-06","name":"OPODIS: Conference on Principles of Distributed Systems"},"file_date_updated":"2024-02-26T09:04:58Z","intvolume":"       286","article_number":"11","date_created":"2024-02-18T23:01:01Z","department":[{"_id":"KrCh"}],"acknowledgement":"This work was partially funded by the Academy of Finland, grant 314888, the European Research Council CoG 863818 (ForM-SMArt), and the Austrian Science Fund (FWF) project I 4800-N (ADVISE). LS was supported by the Stochastic Analysis and Application Research Center (SAARC) under National Research Foundation of Korea grant NRF-2019R1A5A1028324.","oa_version":"Published Version","publication_status":"published","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"day":"18","ec_funded":1,"abstract":[{"text":"Graphical games are a useful framework for modeling the interactions of (selfish) agents who are connected via an underlying topology and whose behaviors influence each other. They have wide applications ranging from computer science to economics and biology. Yet, even though an agent’s payoff only depends on the actions of their direct neighbors in graphical games, computing the Nash equilibria and making statements about the convergence time of \"natural\" local dynamics in particular can be highly challenging. In this work, we present a novel approach for classifying complexity of Nash equilibria in graphical games by establishing a connection to local graph algorithms, a subfield of distributed computing. In particular, we make the observation that the equilibria of graphical games are equivalent to locally verifiable labelings (LVL) in graphs; vertex labelings which are verifiable with constant-round local algorithms. This connection allows us to derive novel lower bounds on the convergence time to equilibrium of best-response dynamics in graphical games. Since we establish that distributed convergence can sometimes be provably slow, we also introduce and give bounds on an intuitive notion of \"time-constrained\" inefficiency of best responses. We exemplify how our results can be used in the implementation of mechanisms that ensure convergence of best responses to a Nash equilibrium. Our results thus also give insight into the convergence of strategy-proof algorithms for graphical games, which is still not well understood.","lang":"eng"}],"status":"public","license":"https://creativecommons.org/licenses/by/4.0/","date_updated":"2025-07-14T09:10:03Z","publication":"27th International Conference on Principles of Distributed Systems","external_id":{"arxiv":["2102.13457"]},"title":"On the convergence time in graphical games: A locality-sensitive approach","file":[{"file_name":"2024_LIPICs_Hirvonen.pdf","file_size":867363,"file_id":"15028","checksum":"4fc7eea6e4ba140b904781fc7df868ec","date_created":"2024-02-26T09:04:58Z","success":1,"date_updated":"2024-02-26T09:04:58Z","creator":"dernst","access_level":"open_access","content_type":"application/pdf","relation":"main_file"}],"scopus_import":"1","alternative_title":["LIPIcs"],"has_accepted_license":"1","project":[{"call_identifier":"H2020","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"citation":{"ama":"Hirvonen J, Schmid L, Chatterjee K, Schmid S. On the convergence time in graphical games: A locality-sensitive approach. In: <i>27th International Conference on Principles of Distributed Systems</i>. Vol 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11\">10.4230/LIPIcs.OPODIS.2023.11</a>","apa":"Hirvonen, J., Schmid, L., Chatterjee, K., &#38; Schmid, S. (2024). On the convergence time in graphical games: A locality-sensitive approach. In <i>27th International Conference on Principles of Distributed Systems</i> (Vol. 286). Tokyo, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.11</a>","mla":"Hirvonen, Juho, et al. “On the Convergence Time in Graphical Games: A Locality-Sensitive Approach.” <i>27th International Conference on Principles of Distributed Systems</i>, vol. 286, 11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11\">10.4230/LIPIcs.OPODIS.2023.11</a>.","short":"J. Hirvonen, L. Schmid, K. Chatterjee, S. Schmid, in:, 27th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ista":"Hirvonen J, Schmid L, Chatterjee K, Schmid S. 2024. On the convergence time in graphical games: A locality-sensitive approach. 27th International Conference on Principles of Distributed Systems. OPODIS: Conference on Principles of Distributed Systems, LIPIcs, vol. 286, 11.","ieee":"J. Hirvonen, L. Schmid, K. Chatterjee, and S. Schmid, “On the convergence time in graphical games: A locality-sensitive approach,” in <i>27th International Conference on Principles of Distributed Systems</i>, Tokyo, Japan, 2024, vol. 286.","chicago":"Hirvonen, Juho, Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid. “On the Convergence Time in Graphical Games: A Locality-Sensitive Approach.” In <i>27th International Conference on Principles of Distributed Systems</i>, Vol. 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.11</a>."},"arxiv":1},{"status":"public","date_updated":"2023-10-09T07:43:44Z","day":"01","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"oa_version":"Published Version","publication_status":"published","abstract":[{"text":"We introduce hypernode automata as a new specification formalism for hyperproperties of concurrent systems. They are finite automata with nodes labeled with hypernode logic formulas and transitions labeled with actions. A hypernode logic formula specifies relations between sequences of variable values in different system executions. Unlike HyperLTL, hypernode logic takes an asynchronous view on execution traces by constraining the values and the order of value changes of each variable without correlating the timing of the changes. Different execution traces are synchronized solely through the transitions of hypernode automata. Hypernode automata naturally combine asynchronicity at the node level with synchronicity at the transition level. We show that the model-checking problem for hypernode automata is decidable over action-labeled Kripke structures, whose actions induce transitions of the specification automata. For this reason, hypernode automaton is a suitable formalism for specifying and verifying asynchronous hyperproperties, such as declassifying observational determinism in multi-threaded programs.","lang":"eng"}],"ec_funded":1,"scopus_import":"1","has_accepted_license":"1","alternative_title":["LIPIcs"],"citation":{"chicago":"Bartocci, Ezio, Thomas A Henzinger, Dejan Nickovic, and Ana Oliveira da Costa. “Hypernode Automata.” In <i>34th International Conference on Concurrency Theory</i>, Vol. 279. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.21\">https://doi.org/10.4230/LIPIcs.CONCUR.2023.21</a>.","ieee":"E. Bartocci, T. A. Henzinger, D. Nickovic, and A. Oliveira da Costa, “Hypernode automata,” in <i>34th International Conference on Concurrency Theory</i>, Antwerp, Belgium, 2023, vol. 279.","short":"E. Bartocci, T.A. Henzinger, D. Nickovic, A. Oliveira da Costa, in:, 34th International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","mla":"Bartocci, Ezio, et al. “Hypernode Automata.” <i>34th International Conference on Concurrency Theory</i>, vol. 279, 21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.21\">10.4230/LIPIcs.CONCUR.2023.21</a>.","apa":"Bartocci, E., Henzinger, T. A., Nickovic, D., &#38; Oliveira da Costa, A. (2023). Hypernode automata. In <i>34th International Conference on Concurrency Theory</i> (Vol. 279). Antwerp, Belgium: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.21\">https://doi.org/10.4230/LIPIcs.CONCUR.2023.21</a>","ista":"Bartocci E, Henzinger TA, Nickovic D, Oliveira da Costa A. 2023. Hypernode automata. 34th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 279, 21.","ama":"Bartocci E, Henzinger TA, Nickovic D, Oliveira da Costa A. Hypernode automata. In: <i>34th International Conference on Concurrency Theory</i>. Vol 279. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.21\">10.4230/LIPIcs.CONCUR.2023.21</a>"},"arxiv":1,"project":[{"call_identifier":"H2020","grant_number":"101020093","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software"}],"publication":"34th International Conference on Concurrency Theory","file":[{"creator":"dernst","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_size":795790,"file_name":"2023_LIPcs_Bartocci.pdf","success":1,"date_updated":"2023-10-09T07:42:45Z","checksum":"215765e40454d806174ac0a223e8d6fa","date_created":"2023-10-09T07:42:45Z","file_id":"14413"}],"title":"Hypernode automata","external_id":{"arxiv":["2305.02836"]},"type":"conference","doi":"10.4230/LIPIcs.CONCUR.2023.21","language":[{"iso":"eng"}],"year":"2023","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2023-09-01T00:00:00Z","author":[{"full_name":"Bartocci, Ezio","first_name":"Ezio","last_name":"Bartocci"},{"orcid":"0000-0002-2985-7724","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","full_name":"Henzinger, Thomas A"},{"full_name":"Nickovic, Dejan","first_name":"Dejan","last_name":"Nickovic","id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Ana","full_name":"Oliveira da Costa, Ana","orcid":"0000-0002-8741-5799","id":"f347ec37-6676-11ee-b395-a888cb7b4fb4","last_name":"Oliveira da Costa"}],"_id":"14405","oa":1,"file_date_updated":"2023-10-09T07:42:45Z","conference":{"location":"Antwerp, Belgium","start_date":"2023-09-19","end_date":"2023-09-22","name":"CONCUR: Conference on Concurrency Theory"},"article_processing_charge":"Yes","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"intvolume":"       279","article_number":"21","date_created":"2023-10-08T22:01:16Z","acknowledgement":"This work was supported in part by the Austrian Science Fund (FWF) SFB project\r\nSpyCoDe F8502, by the FWF projects ZK-35 and W1255-N23, and by the ERC Advanced Grant\r\nVAMOS 101020093.","department":[{"_id":"ToHe"}],"volume":279,"month":"09","publication_identifier":{"isbn":["9783959772990"],"issn":["18688969"]},"quality_controlled":"1"},{"project":[{"name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982"},{"grant_number":"P33775 ","name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"arxiv":1,"citation":{"chicago":"Henzinger, Monika H, Paul Liu, Jan Vondrák, and Da Wei Zheng. “Faster Submodular Maximization for Several Classes of Matroids.” In <i>50th International Colloquium on Automata, Languages, and Programming</i>, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.74\">https://doi.org/10.4230/LIPIcs.ICALP.2023.74</a>.","ieee":"M. H. Henzinger, P. Liu, J. Vondrák, and D. W. Zheng, “Faster submodular maximization for several classes of matroids,” in <i>50th International Colloquium on Automata, Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261.","ista":"Henzinger MH, Liu P, Vondrák J, Zheng DW. 2023. Faster submodular maximization for several classes of matroids. 50th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 261, 74.","apa":"Henzinger, M. H., Liu, P., Vondrák, J., &#38; Zheng, D. W. (2023). Faster submodular maximization for several classes of matroids. In <i>50th International Colloquium on Automata, Languages, and Programming</i> (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.74\">https://doi.org/10.4230/LIPIcs.ICALP.2023.74</a>","mla":"Henzinger, Monika H., et al. “Faster Submodular Maximization for Several Classes of Matroids.” <i>50th International Colloquium on Automata, Languages, and Programming</i>, vol. 261, 74, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.74\">10.4230/LIPIcs.ICALP.2023.74</a>.","short":"M.H. Henzinger, P. Liu, J. Vondrák, D.W. Zheng, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","ama":"Henzinger MH, Liu P, Vondrák J, Zheng DW. Faster submodular maximization for several classes of matroids. In: <i>50th International Colloquium on Automata, Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.74\">10.4230/LIPIcs.ICALP.2023.74</a>"},"scopus_import":"1","alternative_title":["LIPIcs"],"has_accepted_license":"1","publication":"50th International Colloquium on Automata, Languages, and Programming","external_id":{"arxiv":["2305.00122"]},"file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","creator":"dernst","file_id":"14090","date_created":"2023-08-21T07:04:36Z","checksum":"a5eef225014e003efbfbe4830fdd23cb","date_updated":"2023-08-21T07:04:36Z","success":1,"file_name":"2023_LIPIcsICALP_HenzingerM.pdf","file_size":930943}],"title":"Faster submodular maximization for several classes of matroids","date_updated":"2023-08-21T07:05:47Z","status":"public","publication_status":"published","oa_version":"Published Version","day":"01","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ec_funded":1,"abstract":[{"text":"The maximization of submodular functions have found widespread application in areas such as machine learning, combinatorial optimization, and economics, where practitioners often wish to enforce various constraints; the matroid constraint has been investigated extensively due to its algorithmic properties and expressive power. Though tight approximation algorithms for general matroid constraints exist in theory, the running times of such algorithms typically scale quadratically, and are not practical for truly large scale settings. Recent progress has focused on fast algorithms for important classes of matroids given in explicit form. Currently, nearly-linear time algorithms only exist for graphic and partition matroids [Alina Ene and Huy L. Nguyen, 2019]. In this work, we develop algorithms for monotone submodular maximization constrained by graphic, transversal matroids, or laminar matroids in time near-linear in the size of their representation. Our algorithms achieve an optimal approximation of 1-1/e-ε and both generalize and accelerate the results of Ene and Nguyen [Alina Ene and Huy L. Nguyen, 2019]. In fact, the running time of our algorithm cannot be improved within the fast continuous greedy framework of Badanidiyuru and Vondrák [Ashwinkumar Badanidiyuru and Jan Vondrák, 2014].\r\nTo achieve near-linear running time, we make use of dynamic data structures that maintain bases with approximate maximum cardinality and weight under certain element updates. These data structures need to support a weight decrease operation and a novel Freeze operation that allows the algorithm to freeze elements (i.e. force to be contained) in its basis regardless of future data structure operations. For the laminar matroid, we present a new dynamic data structure using the top tree interface of Alstrup, Holm, de Lichtenberg, and Thorup [Stephen Alstrup et al., 2005] that maintains the maximum weight basis under insertions and deletions of elements in O(log n) time. This data structure needs to support certain subtree query and path update operations that are performed every insertion and deletion that are non-trivial to handle in conjunction. For the transversal matroid the Freeze operation corresponds to requiring the data structure to keep a certain set S of vertices matched, a property that we call S-stability. While there is a large body of work on dynamic matching algorithms, none are S-stable and maintain an approximate maximum weight matching under vertex updates. We give the first such algorithm for bipartite graphs with total running time linear (up to log factors) in the number of edges.","lang":"eng"}],"date_created":"2023-08-20T22:01:14Z","article_number":"74","acknowledgement":" Monika Henzinger: This project has received funding from the European Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant\r\nagreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project “Static and Dynamic Hierarchical Graph Decompositions”, I 5982-N, and project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024. Jan Vondrák: Supported by NSF Award 2127781.","department":[{"_id":"MoHe"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"article_processing_charge":"Yes","file_date_updated":"2023-08-21T07:04:36Z","conference":{"location":"Paderborn, Germany","name":"ICALP: International Colloquium on Automata, Languages, and Programming","start_date":"2023-07-10","end_date":"2023-07-14"},"intvolume":"       261","month":"07","quality_controlled":"1","publication_identifier":{"isbn":["9783959772785"],"issn":["18688969"]},"volume":261,"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.ICALP.2023.74","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2023","type":"conference","author":[{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"full_name":"Liu, Paul","first_name":"Paul","last_name":"Liu"},{"full_name":"Vondrák, Jan","first_name":"Jan","last_name":"Vondrák"},{"last_name":"Zheng","full_name":"Zheng, Da Wei","first_name":"Da Wei"}],"oa":1,"_id":"14086","date_published":"2023-07-01T00:00:00Z"},{"file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","creator":"asandaue","success":1,"date_updated":"2021-06-28T13:11:39Z","checksum":"22b11a719018b22ecba2471b51f2eb40","date_created":"2021-06-28T13:11:39Z","file_id":"9611","file_size":727817,"file_name":"2021_LIPIcs_Biswas.pdf"}],"title":"Counting cells of order-k voronoi tessellations in ℝ<sup>3</sup> with morse theory","publication":"Leibniz International Proceedings in Informatics","alternative_title":["LIPIcs"],"has_accepted_license":"1","scopus_import":"1","project":[{"name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"788183"},{"name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425","grant_number":"Z00342","call_identifier":"FWF"},{"grant_number":"I4887","_id":"0aa4bc98-070f-11eb-9043-e6fff9c6a316","name":"Discretization in Geometry and Dynamics"}],"citation":{"ama":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. Counting cells of order-k voronoi tessellations in ℝ<sup>3</sup> with morse theory. In: <i>Leibniz International Proceedings in Informatics</i>. Vol 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.16\">10.4230/LIPIcs.SoCG.2021.16</a>","apa":"Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., &#38; Saghafian, M. (2021). Counting cells of order-k voronoi tessellations in ℝ<sup>3</sup> with morse theory. In <i>Leibniz International Proceedings in Informatics</i> (Vol. 189). Online: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.16\">https://doi.org/10.4230/LIPIcs.SoCG.2021.16</a>","short":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, M. Saghafian, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","mla":"Biswas, Ranita, et al. “Counting Cells of Order-k Voronoi Tessellations in ℝ<sup>3</sup> with Morse Theory.” <i>Leibniz International Proceedings in Informatics</i>, vol. 189, 16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.16\">10.4230/LIPIcs.SoCG.2021.16</a>.","ista":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. 2021. Counting cells of order-k voronoi tessellations in ℝ<sup>3</sup> with morse theory. Leibniz International Proceedings in Informatics. SoCG: International Symposium on Computational Geometry, LIPIcs, vol. 189, 16.","ieee":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, and M. Saghafian, “Counting cells of order-k voronoi tessellations in ℝ<sup>3</sup> with morse theory,” in <i>Leibniz International Proceedings in Informatics</i>, Online, 2021, vol. 189.","chicago":"Biswas, Ranita, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian. “Counting Cells of Order-k Voronoi Tessellations in ℝ<sup>3</sup> with Morse Theory.” In <i>Leibniz International Proceedings in Informatics</i>, Vol. 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.16\">https://doi.org/10.4230/LIPIcs.SoCG.2021.16</a>."},"ec_funded":1,"abstract":[{"lang":"eng","text":"Generalizing Lee’s inductive argument for counting the cells of higher order Voronoi tessellations in ℝ² to ℝ³, we get precise relations in terms of Morse theoretic quantities for piecewise constant functions on planar arrangements. Specifically, we prove that for a generic set of n ≥ 5 points in ℝ³, the number of regions in the order-k Voronoi tessellation is N_{k-1} - binom(k,2)n + n, for 1 ≤ k ≤ n-1, in which N_{k-1} is the sum of Euler characteristics of these function’s first k-1 sublevel sets. We get similar expressions for the vertices, edges, and polygons of the order-k Voronoi tessellation."}],"publication_status":"published","oa_version":"Published Version","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"day":"02","status":"public","date_updated":"2023-02-23T14:02:28Z","volume":189,"quality_controlled":"1","publication_identifier":{"isbn":["9783959771849"],"issn":["18688969"]},"month":"06","intvolume":"       189","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","ddc":["516"],"article_processing_charge":"No","file_date_updated":"2021-06-28T13:11:39Z","conference":{"location":"Online","start_date":"2021-06-07","end_date":"2021-06-11","name":"SoCG: International Symposium on Computational Geometry"},"department":[{"_id":"HeEd"}],"date_created":"2021-06-27T22:01:48Z","article_number":"16","date_published":"2021-06-02T00:00:00Z","oa":1,"_id":"9604","author":[{"orcid":"0000-0002-5372-7890","id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","last_name":"Biswas","first_name":"Ranita","full_name":"Biswas, Ranita"},{"first_name":"Sebastiano","full_name":"Cultrera di Montesano, Sebastiano","orcid":"0000-0001-6249-0832","id":"34D2A09C-F248-11E8-B48F-1D18A9856A87","last_name":"Cultrera di Montesano"},{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"},{"last_name":"Saghafian","first_name":"Morteza","full_name":"Saghafian, Morteza"}],"type":"conference","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2021","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2021.16"},{"volume":189,"quality_controlled":"1","publication_identifier":{"isbn":["9783959771849"],"issn":["18688969"]},"month":"06","intvolume":"       189","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","ddc":["516"],"article_processing_charge":"No","conference":{"name":"SoCG: International Symposium on Computational Geometry","end_date":"2021-06-11","start_date":"2021-06-07","location":"Online"},"file_date_updated":"2021-06-28T12:40:47Z","acknowledgement":"The authors want to thank the reviewers for many helpful comments and suggestions.","department":[{"_id":"HeEd"}],"article_number":"27","date_created":"2021-06-27T22:01:49Z","date_published":"2021-06-02T00:00:00Z","oa":1,"_id":"9605","author":[{"full_name":"Corbet, René","first_name":"René","last_name":"Corbet"},{"last_name":"Kerber","full_name":"Kerber, Michael","first_name":"Michael"},{"last_name":"Lesnick","full_name":"Lesnick, Michael","first_name":"Michael"},{"first_name":"Georg F","full_name":"Osang, Georg F","orcid":"0000-0002-8882-5116","last_name":"Osang","id":"464B40D6-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2021","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2021.27","external_id":{"arxiv":["2103.07823"]},"related_material":{"link":[{"url":"https://arxiv.org/abs/2103.07823","relation":"extended_version"}],"record":[{"relation":"later_version","id":"12709","status":"public"}]},"title":"Computing the multicover bifiltration","file":[{"file_name":"2021_LIPIcs_Corbet.pdf","file_size":"1367983","date_created":"2021-06-28T12:40:47Z","file_id":"9610","checksum":"0de217501e7ba8b267d58deed0d51761","date_updated":"2021-06-28T12:40:47Z","success":1,"creator":"cziletti","access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"publication":"Leibniz International Proceedings in Informatics","alternative_title":["LIPIcs"],"has_accepted_license":"1","scopus_import":"1","arxiv":1,"citation":{"ieee":"R. Corbet, M. Kerber, M. Lesnick, and G. F. Osang, “Computing the multicover bifiltration,” in <i>Leibniz International Proceedings in Informatics</i>, Online, 2021, vol. 189.","chicago":"Corbet, René, Michael Kerber, Michael Lesnick, and Georg F Osang. “Computing the Multicover Bifiltration.” In <i>Leibniz International Proceedings in Informatics</i>, Vol. 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.27\">https://doi.org/10.4230/LIPIcs.SoCG.2021.27</a>.","ama":"Corbet R, Kerber M, Lesnick M, Osang GF. Computing the multicover bifiltration. In: <i>Leibniz International Proceedings in Informatics</i>. Vol 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.27\">10.4230/LIPIcs.SoCG.2021.27</a>","apa":"Corbet, R., Kerber, M., Lesnick, M., &#38; Osang, G. F. (2021). Computing the multicover bifiltration. In <i>Leibniz International Proceedings in Informatics</i> (Vol. 189). Online: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.27\">https://doi.org/10.4230/LIPIcs.SoCG.2021.27</a>","ista":"Corbet R, Kerber M, Lesnick M, Osang GF. 2021. Computing the multicover bifiltration. Leibniz International Proceedings in Informatics. SoCG: International Symposium on Computational Geometry, LIPIcs, vol. 189, 27.","short":"R. Corbet, M. Kerber, M. Lesnick, G.F. Osang, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","mla":"Corbet, René, et al. “Computing the Multicover Bifiltration.” <i>Leibniz International Proceedings in Informatics</i>, vol. 189, 27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.27\">10.4230/LIPIcs.SoCG.2021.27</a>."},"abstract":[{"lang":"eng","text":"Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness. "}],"oa_version":"Published Version","publication_status":"published","day":"02","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","date_updated":"2023-10-04T12:03:39Z"},{"author":[{"full_name":"Patakova, Zuzana","first_name":"Zuzana","orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87","last_name":"Patakova"}],"oa":1,"_id":"7989","date_published":"2020-06-01T00:00:00Z","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2020.61","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2020","type":"conference","month":"06","quality_controlled":"1","publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"volume":164,"article_number":"61:1-61:13","date_created":"2020-06-22T09:14:18Z","department":[{"_id":"UlWa"}],"ddc":["510"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","file_date_updated":"2020-07-14T12:48:06Z","conference":{"location":"Zürich, Switzerland","end_date":"2020-06-26","start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry"},"intvolume":"       164","publication_status":"published","oa_version":"Published Version","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"day":"01","abstract":[{"lang":"eng","text":"We prove general topological Radon-type theorems for sets in ℝ^d, smooth real manifolds or finite dimensional simplicial complexes. Combined with a recent result of Holmsen and Lee, it gives fractional Helly theorem, and consequently the existence of weak ε-nets as well as a (p,q)-theorem. More precisely: Let X be either ℝ^d, smooth real d-manifold, or a finite d-dimensional simplicial complex. Then if F is a finite, intersection-closed family of sets in X such that the ith reduced Betti number (with ℤ₂ coefficients) of any set in F is at most b for every non-negative integer i less or equal to k, then the Radon number of F is bounded in terms of b and X. Here k is the smallest integer larger or equal to d/2 - 1 if X = ℝ^d; k=d-1 if X is a smooth real d-manifold and not a surface, k=0 if X is a surface and k=d if X is a d-dimensional simplicial complex. Using the recent result of the author and Kalai, we manage to prove the following optimal bound on fractional Helly number for families of open sets in a surface: Let F be a finite family of open sets in a surface S such that the intersection of any subfamily of F is either empty, or path-connected. Then the fractional Helly number of F is at most three. This also settles a conjecture of Holmsen, Kim, and Lee about an existence of a (p,q)-theorem for open subsets of a surface."}],"date_updated":"2021-01-12T08:16:22Z","status":"public","publication":"36th International Symposium on Computational Geometry","external_id":{"arxiv":["1908.01677"]},"title":"Bounding radon number via Betti numbers","file":[{"date_updated":"2020-07-14T12:48:06Z","checksum":"d0996ca5f6eb32ce955ce782b4f2afbe","file_id":"8005","date_created":"2020-06-23T06:56:23Z","file_size":645421,"file_name":"2020_LIPIcsSoCG_Patakova_61.pdf","content_type":"application/pdf","relation":"main_file","access_level":"open_access","creator":"dernst"}],"citation":{"chicago":"Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” 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.61\">https://doi.org/10.4230/LIPIcs.SoCG.2020.61</a>.","ieee":"Z. Patakova, “Bounding radon number via Betti numbers,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","short":"Z. Patakova, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","apa":"Patakova, Z. (2020). Bounding radon number via Betti numbers. 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.61\">https://doi.org/10.4230/LIPIcs.SoCG.2020.61</a>","mla":"Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 61:1-61:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.61\">10.4230/LIPIcs.SoCG.2020.61</a>.","ista":"Patakova Z. 2020. Bounding radon number via Betti numbers. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 61:1-61:13.","ama":"Patakova Z. Bounding radon number via Betti numbers. 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.61\">10.4230/LIPIcs.SoCG.2020.61</a>"},"arxiv":1,"scopus_import":"1","alternative_title":["LIPIcs"],"has_accepted_license":"1"},{"date_updated":"2023-08-04T08:51:07Z","status":"public","abstract":[{"text":"Given a finite point set P in general position in the plane, a full triangulation is a maximal straight-line embedded plane graph on P. A partial triangulation on P is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge, removes a non-extreme point of degree 3, or adds a point in P ⧵ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The goal of this paper is to investigate the structure of this graph, with emphasis on its connectivity. For sets P of n points in general position, we show that the bistellar flip graph is (n-3)-connected, thereby answering, for sets in general position, an open questions raised in a book (by De Loera, Rambau, and Santos) and a survey (by Lee and Santos) on triangulations. This matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points and projecting the lower convex hull), where (n-3)-connectivity has been known since the late 1980s through the secondary polytope (Gelfand, Kapranov, Zelevinsky) and Balinski’s Theorem. Our methods also yield the following results (see the full version [Wagner and Welzl, 2020]): (i) The bistellar flip graph can be covered by graphs of polytopes of dimension n-3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n-3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations are regular iff the trivial subdivision has height n-3 in the partial order of partial subdivisions. (iv) There are arbitrarily large sets P with non-regular partial triangulations, while every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular partial triangulations (answering a question by F. Santos in the unexpected direction).","lang":"eng"}],"publication_status":"published","oa_version":"Published Version","day":"01","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"arxiv":1,"citation":{"chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips).” 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.67\">https://doi.org/10.4230/LIPIcs.SoCG.2020.67</a>.","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips),” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","apa":"Wagner, U., &#38; Welzl, E. (2020). Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). 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.67\">https://doi.org/10.4230/LIPIcs.SoCG.2020.67</a>","ista":"Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 67:1-67:16.","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips).” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 67:1-67:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.67\">10.4230/LIPIcs.SoCG.2020.67</a>.","short":"U. Wagner, E. Welzl, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). 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.67\">10.4230/LIPIcs.SoCG.2020.67</a>"},"alternative_title":["LIPIcs"],"has_accepted_license":"1","scopus_import":1,"related_material":{"record":[{"relation":"later_version","status":"public","id":"12129"}]},"external_id":{"arxiv":["2003.13557"]},"file":[{"file_id":"8003","date_created":"2020-06-23T06:37:27Z","checksum":"3f6925be5f3dcdb3b14cab92f410edf7","date_updated":"2020-07-14T12:48:06Z","file_name":"2020_LIPIcsSoCG_Wagner.pdf","file_size":793187,"access_level":"open_access","content_type":"application/pdf","relation":"main_file","creator":"dernst"}],"title":"Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips)","publication":"36th International Symposium on Computational Geometry","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2020","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2020.67","type":"conference","oa":1,"_id":"7990","author":[{"full_name":"Wagner, Uli","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","orcid":"0000-0002-1494-0568"},{"last_name":"Welzl","first_name":"Emo","full_name":"Welzl, Emo"}],"date_published":"2020-06-01T00:00:00Z","department":[{"_id":"UlWa"}],"date_created":"2020-06-22T09:14:19Z","article_number":"67:1 - 67:16","intvolume":"       164","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["510"],"article_processing_charge":"No","conference":{"location":"Zürich, Switzerland","end_date":"2020-06-26","start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry"},"file_date_updated":"2020-07-14T12:48:06Z","quality_controlled":"1","publication_identifier":{"isbn":["9783959771436"],"issn":["18688969"]},"month":"06","volume":164},{"project":[{"call_identifier":"FWF","grant_number":"P31312","name":"Algorithms for Embeddings and Homotopy Theory","_id":"26611F5C-B435-11E9-9278-68D0E5697425"}],"arxiv":1,"citation":{"ama":"Avvakumov S, Nivasch G. Homotopic curve shortening and the affine curve-shortening flow. 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.12\">10.4230/LIPIcs.SoCG.2020.12</a>","apa":"Avvakumov, S., &#38; Nivasch, G. (2020). Homotopic curve shortening and the affine curve-shortening flow. 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.12\">https://doi.org/10.4230/LIPIcs.SoCG.2020.12</a>","short":"S. Avvakumov, G. Nivasch, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ista":"Avvakumov S, Nivasch G. 2020. Homotopic curve shortening and the affine curve-shortening flow. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 12:1-12:15.","mla":"Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the Affine Curve-Shortening Flow.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.12\">10.4230/LIPIcs.SoCG.2020.12</a>.","ieee":"S. Avvakumov and G. Nivasch, “Homotopic curve shortening and the affine curve-shortening flow,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","chicago":"Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the Affine Curve-Shortening Flow.” 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.12\">https://doi.org/10.4230/LIPIcs.SoCG.2020.12</a>."},"alternative_title":["LIPIcs"],"has_accepted_license":"1","scopus_import":"1","external_id":{"arxiv":["1909.00263"]},"title":"Homotopic curve shortening and the affine curve-shortening flow","file":[{"file_id":"8007","checksum":"6872df6549142f709fb6354a1b2f2c06","date_created":"2020-06-23T11:13:49Z","date_updated":"2020-07-14T12:48:06Z","file_name":"2020_LIPIcsSoCG_Avvakumov.pdf","file_size":575896,"access_level":"open_access","content_type":"application/pdf","relation":"main_file","creator":"dernst"}],"publication":"36th International Symposium on Computational Geometry","date_updated":"2021-01-12T08:16:23Z","license":"https://creativecommons.org/licenses/by/3.0/","status":"public","abstract":[{"lang":"eng","text":"We define and study a discrete process that generalizes the convex-layer decomposition of a planar point set. Our process, which we call homotopic curve shortening (HCS), starts with a closed curve (which might self-intersect) in the presence of a set P⊂ ℝ² of point obstacles, and evolves in discrete steps, where each step consists of (1) taking shortcuts around the obstacles, and (2) reducing the curve to its shortest homotopic equivalent. We find experimentally that, if the initial curve is held fixed and P is chosen to be either a very fine regular grid or a uniformly random point set, then HCS behaves at the limit like the affine curve-shortening flow (ACSF). This connection between HCS and ACSF generalizes the link between \"grid peeling\" and the ACSF observed by Eppstein et al. (2017), which applied only to convex curves, and which was studied only for regular grids. We prove that HCS satisfies some properties analogous to those of ACSF: HCS is invariant under affine transformations, preserves convexity, and does not increase the total absolute curvature. Furthermore, the number of self-intersections of a curve, or intersections between two curves (appropriately defined), does not increase. Finally, if the initial curve is simple, then the number of inflection points (appropriately defined) does not increase."}],"oa_version":"Published Version","publication_status":"published","day":"01","tmp":{"image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode"},"department":[{"_id":"UlWa"}],"article_number":"12:1 - 12:15","date_created":"2020-06-22T09:14:19Z","intvolume":"       164","article_processing_charge":"No","ddc":["510"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:48:06Z","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2020-06-26","start_date":"2020-06-22","location":"Zürich, Switzerland"},"quality_controlled":"1","publication_identifier":{"isbn":["9783959771436"],"issn":["18688969"]},"month":"06","volume":164,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2020","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2020.12","type":"conference","oa":1,"_id":"7991","author":[{"first_name":"Sergey","full_name":"Avvakumov, Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","last_name":"Avvakumov"},{"last_name":"Nivasch","full_name":"Nivasch, Gabriel","first_name":"Gabriel"}],"date_published":"2020-06-01T00:00:00Z"},{"publication":"36th International Symposium on Computational Geometry","external_id":{"arxiv":["2003.13536"]},"file":[{"date_created":"2020-06-23T06:45:52Z","checksum":"ce1c9194139a664fb59d1efdfc88eaae","file_id":"8004","date_updated":"2020-07-14T12:48:06Z","file_name":"2020_LIPIcsSoCG_Patakova.pdf","file_size":750318,"access_level":"open_access","relation":"main_file","content_type":"application/pdf","creator":"dernst"}],"title":"Barycentric cuts through a convex body","citation":{"ama":"Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. 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.62\">10.4230/LIPIcs.SoCG.2020.62</a>","ista":"Patakova Z, Tancer M, Wagner U. 2020. Barycentric cuts through a convex body. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 62:1-62:16.","apa":"Patakova, Z., Tancer, M., &#38; Wagner, U. (2020). Barycentric cuts through a convex body. 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.62\">https://doi.org/10.4230/LIPIcs.SoCG.2020.62</a>","mla":"Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 62:1-62:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.62\">10.4230/LIPIcs.SoCG.2020.62</a>.","short":"Z. Patakova, M. Tancer, U. Wagner, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ieee":"Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex body,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","chicago":"Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through a Convex Body.” 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.62\">https://doi.org/10.4230/LIPIcs.SoCG.2020.62</a>."},"arxiv":1,"scopus_import":1,"alternative_title":["LIPIcs"],"has_accepted_license":"1","publication_status":"published","oa_version":"Published Version","day":"01","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"abstract":[{"lang":"eng","text":"Let K be a convex body in ℝⁿ (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K ∩ h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p₀ is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question. It follows from known results that for n ≥ 2, there are always at least three distinct barycentric cuts through the point p₀ ∈ K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p₀ are guaranteed if n ≥ 3."}],"date_updated":"2021-01-12T08:16:23Z","status":"public","month":"06","quality_controlled":"1","publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"volume":164,"article_number":"62:1 - 62:16","date_created":"2020-06-22T09:14:20Z","department":[{"_id":"UlWa"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["510"],"article_processing_charge":"No","file_date_updated":"2020-07-14T12:48:06Z","conference":{"location":"Zürich, Switzerland","start_date":"2020-06-22","end_date":"2020-06-26","name":"SoCG: Symposium on Computational Geometry"},"intvolume":"       164","author":[{"last_name":"Patakova","id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683","first_name":"Zuzana","full_name":"Patakova, Zuzana"},{"id":"38AC689C-F248-11E8-B48F-1D18A9856A87","last_name":"Tancer","orcid":"0000-0002-1191-6714","full_name":"Tancer, Martin","first_name":"Martin"},{"first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner"}],"oa":1,"_id":"7992","date_published":"2020-06-01T00:00:00Z","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2020.62","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2020","type":"conference"},{"ec_funded":1,"abstract":[{"text":"In the recent study of crossing numbers, drawings of graphs that can be extended to an arrangement of pseudolines (pseudolinear drawings) have played an important role as they are a natural combinatorial extension of rectilinear (or straight-line) drawings. A characterization of the pseudolinear drawings of K_n was found recently. We extend this characterization to all graphs, by describing the set of minimal forbidden subdrawings for pseudolinear drawings. Our characterization also leads to a polynomial-time algorithm to recognize pseudolinear drawings and construct the pseudolines when it is possible.","lang":"eng"}],"oa_version":"Published Version","publication_status":"published","day":"01","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"date_updated":"2023-02-23T13:22:12Z","status":"public","external_id":{"arxiv":["1804.09317"]},"title":"Extending drawings of graphs to arrangements of pseudolines","file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","creator":"dernst","checksum":"93571b76cf97d5b7c8aabaeaa694dd7e","date_created":"2020-06-23T11:06:23Z","file_id":"8006","date_updated":"2020-07-14T12:48:06Z","file_name":"2020_LIPIcsSoCG_Arroyo.pdf","file_size":592661}],"publication":"36th International Symposium on Computational Geometry","project":[{"call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"}],"citation":{"ieee":"A. M. Arroyo Guevara, J. Bensmail, and R. Bruce Richter, “Extending drawings of graphs to arrangements of pseudolines,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","chicago":"Arroyo Guevara, Alan M, Julien Bensmail, and R. Bruce Richter. “Extending Drawings of Graphs to Arrangements of Pseudolines.” 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.9\">https://doi.org/10.4230/LIPIcs.SoCG.2020.9</a>.","ama":"Arroyo Guevara AM, Bensmail J, Bruce Richter R. Extending drawings of graphs to arrangements of pseudolines. 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.9\">10.4230/LIPIcs.SoCG.2020.9</a>","short":"A.M. Arroyo Guevara, J. Bensmail, R. Bruce Richter, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ista":"Arroyo Guevara AM, Bensmail J, Bruce Richter R. 2020. Extending drawings of graphs to arrangements of pseudolines. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 9:1-9:14.","mla":"Arroyo Guevara, Alan M., et al. “Extending Drawings of Graphs to Arrangements of Pseudolines.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.9\">10.4230/LIPIcs.SoCG.2020.9</a>.","apa":"Arroyo Guevara, A. M., Bensmail, J., &#38; Bruce Richter, R. (2020). Extending drawings of graphs to arrangements of pseudolines. 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.9\">https://doi.org/10.4230/LIPIcs.SoCG.2020.9</a>"},"arxiv":1,"alternative_title":["LIPIcs"],"has_accepted_license":"1","scopus_import":"1","oa":1,"_id":"7994","author":[{"full_name":"Arroyo Guevara, Alan M","first_name":"Alan M","orcid":"0000-0003-2401-8670","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","last_name":"Arroyo Guevara"},{"last_name":"Bensmail","first_name":"Julien","full_name":"Bensmail, Julien"},{"full_name":"Bruce Richter, R.","first_name":"R.","last_name":"Bruce Richter"}],"date_published":"2020-06-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2020","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2020.9","type":"conference","quality_controlled":"1","publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"month":"06","volume":164,"department":[{"_id":"UlWa"}],"article_number":"9:1 - 9:14","date_created":"2020-06-22T09:14:21Z","intvolume":"       164","ddc":["510"],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:48:06Z","conference":{"location":"Zürich, Switzerland","start_date":"2020-06-22","end_date":"2020-06-26","name":"SoCG: Symposium on Computational Geometry"}},{"has_accepted_license":"1","alternative_title":["LIPIcs"],"scopus_import":"1","citation":{"ieee":"K. Chatterjee, R. Ibsen-Jensen, I. R. Jecker, and J. Svoboda, “Simplified game of life: Algorithms and complexity,” in <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, Prague, Czech Republic, 2020, vol. 170.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Ismael R Jecker, and Jakub Svoboda. “Simplified Game of Life: Algorithms and Complexity.” In <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.22\">https://doi.org/10.4230/LIPIcs.MFCS.2020.22</a>.","ama":"Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. Simplified game of life: Algorithms and complexity. In: <i>45th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.22\">10.4230/LIPIcs.MFCS.2020.22</a>","ista":"Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. 2020. Simplified game of life: Algorithms and complexity. 45th International Symposium on Mathematical Foundations of Computer Science. MFCS: Symposium on Mathematical Foundations of Computer Science, LIPIcs, vol. 170, 22:1-22:13.","short":"K. Chatterjee, R. Ibsen-Jensen, I.R. Jecker, J. Svoboda, in:, 45th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","apa":"Chatterjee, K., Ibsen-Jensen, R., Jecker, I. R., &#38; Svoboda, J. (2020). Simplified game of life: Algorithms and complexity. In <i>45th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 170). Prague, Czech Republic: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.22\">https://doi.org/10.4230/LIPIcs.MFCS.2020.22</a>","mla":"Chatterjee, Krishnendu, et al. “Simplified Game of Life: Algorithms and Complexity.” <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 170, 22:1-22:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.22\">10.4230/LIPIcs.MFCS.2020.22</a>."},"arxiv":1,"project":[{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003"},{"grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"}],"file":[{"creator":"dernst","relation":"main_file","content_type":"application/pdf","access_level":"open_access","file_size":491374,"file_name":"2020_LIPIcs_Chatterjee.pdf","date_updated":"2020-09-21T13:57:34Z","success":1,"checksum":"bbd7c4f55d45f2ff2a0a4ef0e10a77b1","date_created":"2020-09-21T13:57:34Z","file_id":"8550"}],"title":"Simplified game of life: Algorithms and complexity","external_id":{"arxiv":["2007.02894"]},"publication":"45th International Symposium on Mathematical Foundations of Computer Science","status":"public","date_updated":"2025-06-02T08:53:42Z","abstract":[{"text":"Game of Life is a simple and elegant model to study dynamical system over networks. The model consists of a graph where every vertex has one of two types, namely, dead or alive. A configuration is a mapping of the vertices to the types. An update rule describes how the type of a vertex is updated given the types of its neighbors. In every round, all vertices are updated synchronously, which leads to a configuration update. While in general, Game of Life allows a broad range of update rules, we focus on two simple families of update rules, namely, underpopulation and overpopulation, that model several interesting dynamics studied in the literature. In both settings, a dead vertex requires at least a desired number of live neighbors to become alive. For underpopulation (resp., overpopulation), a live vertex requires at least (resp. at most) a desired number of live neighbors to remain alive. We study the basic computation problems, e.g., configuration reachability, for these two families of rules. For underpopulation rules, we show that these problems can be solved in polynomial time, whereas for overpopulation rules they are PSPACE-complete.","lang":"eng"}],"ec_funded":1,"day":"18","tmp":{"image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode"},"oa_version":"Published Version","publication_status":"published","intvolume":"       170","file_date_updated":"2020-09-21T13:57:34Z","conference":{"name":"MFCS: Symposium on Mathematical Foundations of Computer Science","end_date":"2020-08-28","start_date":"2020-08-24","location":"Prague, Czech Republic"},"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"department":[{"_id":"KrCh"}],"acknowledgement":"Krishnendu Chatterjee: The research was partially supported by the Vienna Science and\r\nTechnology Fund (WWTF) Project ICT15-003.\r\nIsmaël Jecker: This project has received funding from the European Union’s Horizon 2020 research\r\nand innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411.","article_number":"22:1-22:13","date_created":"2020-09-20T22:01:36Z","volume":170,"publication_identifier":{"issn":["18688969"],"isbn":["9783959771597"]},"quality_controlled":"1","month":"08","type":"conference","year":"2020","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","doi":"10.4230/LIPIcs.MFCS.2020.22","language":[{"iso":"eng"}],"date_published":"2020-08-18T00:00:00Z","_id":"8533","oa":1,"author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus"},{"last_name":"Jecker","id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","first_name":"Ismael R","full_name":"Jecker, Ismael R"},{"orcid":"0000-0002-1419-3267","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","full_name":"Svoboda, Jakub","first_name":"Jakub"}]},{"publication_identifier":{"issn":["18688969"],"isbn":["9783959771597"]},"quality_controlled":"1","month":"08","volume":170,"acknowledgement":"Ismaël Jecker: This project has received funding from the European Union’s Horizon\r\n2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No.\r\n754411. Nicolas Mazzocchi: PhD fellowship FRIA from the F.R.S.-FNRS.","department":[{"_id":"KrCh"}],"date_created":"2020-09-20T22:01:36Z","article_number":"51:1-51:12","intvolume":"       170","conference":{"end_date":"2020-08-28","start_date":"2020-08-24","name":"MFCS: Symposium on Mathematical Foundations of Computer Science","location":"Prague, Czech Republic"},"file_date_updated":"2020-09-21T14:17:08Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","ddc":["000"],"_id":"8534","oa":1,"author":[{"id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","last_name":"Jecker","full_name":"Jecker, Ismael R","first_name":"Ismael R"},{"last_name":"Kupferman","first_name":"Orna","full_name":"Kupferman, Orna"},{"last_name":"Mazzocchi","first_name":"Nicolas","full_name":"Mazzocchi, Nicolas"}],"date_published":"2020-08-18T00:00:00Z","year":"2020","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","doi":"10.4230/LIPIcs.MFCS.2020.51","language":[{"iso":"eng"}],"type":"conference","title":"Unary prime languages","file":[{"creator":"dernst","relation":"main_file","content_type":"application/pdf","access_level":"open_access","file_size":597977,"file_name":"2020_LIPIcsMFCS_Jecker.pdf","date_updated":"2020-09-21T14:17:08Z","success":1,"checksum":"2dc9e2fad6becd4563aef3e27a473f70","date_created":"2020-09-21T14:17:08Z","file_id":"8552"}],"publication":"45th International Symposium on Mathematical Foundations of Computer Science","citation":{"short":"I.R. Jecker, O. Kupferman, N. Mazzocchi, in:, 45th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","mla":"Jecker, Ismael R., et al. “Unary Prime Languages.” <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 170, 51:1-51:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.51\">10.4230/LIPIcs.MFCS.2020.51</a>.","apa":"Jecker, I. R., Kupferman, O., &#38; Mazzocchi, N. (2020). Unary prime languages. In <i>45th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 170). Prague, Czech Republic: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.51\">https://doi.org/10.4230/LIPIcs.MFCS.2020.51</a>","ista":"Jecker IR, Kupferman O, Mazzocchi N. 2020. Unary prime languages. 45th International Symposium on Mathematical Foundations of Computer Science. MFCS: Symposium on Mathematical Foundations of Computer Science, LIPIcs, vol. 170, 51:1-51:12.","ama":"Jecker IR, Kupferman O, Mazzocchi N. Unary prime languages. In: <i>45th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.51\">10.4230/LIPIcs.MFCS.2020.51</a>","chicago":"Jecker, Ismael R, Orna Kupferman, and Nicolas Mazzocchi. “Unary Prime Languages.” In <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.51\">https://doi.org/10.4230/LIPIcs.MFCS.2020.51</a>.","ieee":"I. R. Jecker, O. Kupferman, and N. Mazzocchi, “Unary prime languages,” in <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, Prague, Czech Republic, 2020, vol. 170."},"project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411"}],"has_accepted_license":"1","alternative_title":["LIPIcs"],"scopus_import":"1","abstract":[{"lang":"eng","text":"A regular language L of finite words is composite if there are regular languages L₁,L₂,…,L_t such that L = ⋂_{i = 1}^t L_i and the index (number of states in a minimal DFA) of every language L_i is strictly smaller than the index of L. Otherwise, L is prime. Primality of regular languages was introduced and studied in [O. Kupferman and J. Mosheiff, 2015], where the complexity of deciding the primality of the language of a given DFA was left open, with a doubly-exponential gap between the upper and lower bounds. We study primality for unary regular languages, namely regular languages with a singleton alphabet. A unary language corresponds to a subset of ℕ, making the study of unary prime languages closer to that of primality in number theory. We show that the setting of languages is richer. In particular, while every composite number is the product of two smaller numbers, the number t of languages necessary to decompose a composite unary language induces a strict hierarchy. In addition, a primality witness for a unary language L, namely a word that is not in L but is in all products of languages that contain L and have an index smaller than L’s, may be of exponential length. Still, we are able to characterize compositionality by structural properties of a DFA for L, leading to a LogSpace algorithm for primality checking of unary DFAs."}],"ec_funded":1,"tmp":{"image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode"},"day":"18","publication_status":"published","oa_version":"Published Version","date_updated":"2021-01-12T08:19:56Z","status":"public"},{"project":[{"call_identifier":"FWF","grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize"}],"citation":{"ama":"Avni G, Henzinger TA. A survey of bidding games on graphs. In: <i>31st International Conference on Concurrency Theory</i>. Vol 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2020.2\">10.4230/LIPIcs.CONCUR.2020.2</a>","apa":"Avni, G., &#38; Henzinger, T. A. (2020). A survey of bidding games on graphs. In <i>31st International Conference on Concurrency Theory</i> (Vol. 171). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2020.2\">https://doi.org/10.4230/LIPIcs.CONCUR.2020.2</a>","ista":"Avni G, Henzinger TA. 2020. A survey of bidding games on graphs. 31st International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 171, 2.","mla":"Avni, Guy, and Thomas A. Henzinger. “A Survey of Bidding Games on Graphs.” <i>31st International Conference on Concurrency Theory</i>, vol. 171, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2020.2\">10.4230/LIPIcs.CONCUR.2020.2</a>.","short":"G. Avni, T.A. Henzinger, in:, 31st International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ieee":"G. Avni and T. A. Henzinger, “A survey of bidding games on graphs,” in <i>31st International Conference on Concurrency Theory</i>, Virtual, 2020, vol. 171.","chicago":"Avni, Guy, and Thomas A Henzinger. “A Survey of Bidding Games on Graphs.” In <i>31st International Conference on Concurrency Theory</i>, Vol. 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2020.2\">https://doi.org/10.4230/LIPIcs.CONCUR.2020.2</a>."},"alternative_title":["LIPIcs"],"has_accepted_license":"1","scopus_import":"1","file":[{"access_level":"open_access","content_type":"application/pdf","relation":"main_file","creator":"dernst","file_id":"8611","date_created":"2020-10-05T14:13:19Z","checksum":"8f33b098e73724e0ac817f764d8e1a2d","success":1,"date_updated":"2020-10-05T14:13:19Z","file_name":"2020_LIPIcsCONCUR_Avni.pdf","file_size":868510}],"title":"A survey of bidding games on graphs","publication":"31st International Conference on Concurrency Theory","date_updated":"2021-01-12T08:20:13Z","status":"public","abstract":[{"lang":"eng","text":"A graph game is a two-player zero-sum game in which the players move a token throughout a graph to produce an infinite path, which determines the winner or payoff of the game. In bidding games, both players have budgets, and in each turn, we hold an \"auction\" (bidding) to determine which player moves the token. In this survey, we consider several bidding mechanisms and study their effect on the properties of the game. Specifically, bidding games, and in particular bidding games of infinite duration, have an intriguing equivalence with random-turn games in which in each turn, the player who moves is chosen randomly. We show how minor changes in the bidding mechanism lead to unexpected differences in the equivalence with random-turn games."}],"publication_status":"published","oa_version":"Published Version","tmp":{"image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode"},"day":"06","acknowledgement":"We would like to thank all our collaborators Milad Aghajohari, Ventsislav Chonev, Rasmus Ibsen-Jensen, Ismäel Jecker, Petr Novotný, Josef Tkadlec, and Ðorđe Žikelić; we hope the collaboration was as fun and meaningful for you as it was for us.","department":[{"_id":"ToHe"}],"date_created":"2020-10-04T22:01:36Z","article_number":"2","intvolume":"       171","ddc":["000"],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-10-05T14:13:19Z","conference":{"location":"Virtual","name":"CONCUR: Conference on Concurrency Theory","start_date":"2020-09-01","end_date":"2020-09-04"},"quality_controlled":"1","publication_identifier":{"issn":["18688969"],"isbn":["9783959771603"]},"month":"08","volume":171,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2020","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.CONCUR.2020.2","type":"conference","oa":1,"_id":"8599","author":[{"full_name":"Avni, Guy","first_name":"Guy","orcid":"0000-0001-5588-8287","last_name":"Avni","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","full_name":"Henzinger, Thomas A","first_name":"Thomas A"}],"date_published":"2020-08-06T00:00:00Z"},{"title":"Multi-dimensional long-run average problems for vector addition systems with states","file":[{"relation":"main_file","content_type":"application/pdf","access_level":"open_access","creator":"dernst","date_updated":"2020-10-05T14:04:25Z","success":1,"file_id":"8610","checksum":"5039752f644c4b72b9361d21a5e31baf","date_created":"2020-10-05T14:04:25Z","file_size":601231,"file_name":"2020_LIPIcsCONCUR_Chatterjee.pdf"}],"external_id":{"arxiv":["2007.08917"]},"publication":"31st International Conference on Concurrency Theory","has_accepted_license":"1","alternative_title":["LIPIcs"],"scopus_import":"1","arxiv":1,"citation":{"mla":"Chatterjee, Krishnendu, et al. “Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States.” <i>31st International Conference on Concurrency Theory</i>, vol. 171, 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2020.23\">10.4230/LIPIcs.CONCUR.2020.23</a>.","apa":"Chatterjee, K., Henzinger, T. A., &#38; Otop, J. (2020). Multi-dimensional long-run average problems for vector addition systems with states. In <i>31st International Conference on Concurrency Theory</i> (Vol. 171). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2020.23\">https://doi.org/10.4230/LIPIcs.CONCUR.2020.23</a>","short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, 31st International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ista":"Chatterjee K, Henzinger TA, Otop J. 2020. Multi-dimensional long-run average problems for vector addition systems with states. 31st International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 171, 23.","ama":"Chatterjee K, Henzinger TA, Otop J. Multi-dimensional long-run average problems for vector addition systems with states. In: <i>31st International Conference on Concurrency Theory</i>. Vol 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2020.23\">10.4230/LIPIcs.CONCUR.2020.23</a>","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States.” In <i>31st International Conference on Concurrency Theory</i>, Vol. 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2020.23\">https://doi.org/10.4230/LIPIcs.CONCUR.2020.23</a>.","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, “Multi-dimensional long-run average problems for vector addition systems with states,” in <i>31st International Conference on Concurrency Theory</i>, Virtual, 2020, vol. 171."},"project":[{"name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","call_identifier":"FWF"},{"_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S11402-N23"},{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","call_identifier":"FWF","grant_number":"Z211"}],"abstract":[{"lang":"eng","text":"A vector addition system with states (VASS) consists of a finite set of states and counters. A transition changes the current state to the next state, and every counter is either incremented, or decremented, or left unchanged. A state and value for each counter is a configuration; and a computation is an infinite sequence of configurations with transitions between successive configurations. A probabilistic VASS consists of a VASS along with a probability distribution over the transitions for each state. Qualitative properties such as state and configuration reachability have been widely studied for VASS. In this work we consider multi-dimensional long-run average objectives for VASS and probabilistic VASS. For a counter, the cost of a configuration is the value of the counter; and the long-run average value of a computation for the counter is the long-run average of the costs of the configurations in the computation. The multi-dimensional long-run average problem given a VASS and a threshold value for each counter, asks whether there is a computation such that for each counter the long-run average value for the counter does not exceed the respective threshold. For probabilistic VASS, instead of the existence of a computation, we consider whether the expected long-run average value for each counter does not exceed the respective threshold. Our main results are as follows: we show that the multi-dimensional long-run average problem (a) is NP-complete for integer-valued VASS; (b) is undecidable for natural-valued VASS (i.e., nonnegative counters); and (c) can be solved in polynomial time for probabilistic integer-valued VASS, and probabilistic natural-valued VASS when all computations are non-terminating."}],"day":"06","tmp":{"image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode"},"publication_status":"published","oa_version":"Published Version","status":"public","date_updated":"2021-01-12T08:20:15Z","volume":171,"publication_identifier":{"isbn":["9783959771603"],"issn":["18688969"]},"quality_controlled":"1","month":"08","intvolume":"       171","conference":{"location":"Virtual","name":"CONCUR: Conference on Concurrency Theory","start_date":"2020-09-01","end_date":"2020-09-04"},"file_date_updated":"2020-10-05T14:04:25Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","ddc":["000"],"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"date_created":"2020-10-04T22:01:36Z","article_number":"23","date_published":"2020-08-06T00:00:00Z","_id":"8600","oa":1,"author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Otop, Jan","first_name":"Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","last_name":"Otop"}],"type":"conference","year":"2020","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","doi":"10.4230/LIPIcs.CONCUR.2020.23","language":[{"iso":"eng"}]},{"oa":1,"_id":"8703","author":[{"last_name":"Osang","id":"464B40D6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8882-5116","full_name":"Osang, Georg F","first_name":"Georg F"},{"first_name":"Mael","full_name":"Rouxel-Labbé, Mael","last_name":"Rouxel-Labbé"},{"last_name":"Teillaud","first_name":"Monique","full_name":"Teillaud, Monique"}],"date_published":"2020-08-26T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2020","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.ESA.2020.75","type":"conference","quality_controlled":"1","publication_identifier":{"isbn":["9783959771627"],"issn":["18688969"]},"month":"08","volume":173,"department":[{"_id":"HeEd"}],"article_number":"75","date_created":"2020-10-25T23:01:18Z","intvolume":"       173","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"article_processing_charge":"No","conference":{"location":"Virtual, Online; Pisa, Italy","end_date":"2020-09-09","start_date":"2020-09-07","name":"ESA: Annual European Symposium on Algorithms"},"file_date_updated":"2020-10-27T14:31:52Z","ec_funded":1,"abstract":[{"text":"Even though Delaunay originally introduced his famous triangulations in the case of infinite point sets with translational periodicity, a software that computes such triangulations in the general case is not yet available, to the best of our knowledge. Combining and generalizing previous work, we present a practical algorithm for computing such triangulations. The algorithm has been implemented and experiments show that its performance is as good as the one of the CGAL package, which is restricted to cubic periodicity. ","lang":"eng"}],"publication_status":"published","oa_version":"Published Version","tmp":{"image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode"},"day":"26","date_updated":"2023-09-07T13:29:00Z","status":"public","related_material":{"record":[{"relation":"dissertation_contains","id":"9056","status":"public"}]},"file":[{"creator":"cziletti","access_level":"open_access","content_type":"application/pdf","relation":"main_file","file_name":"2020_LIPIcs_Osang.pdf","file_size":733291,"file_id":"8712","date_created":"2020-10-27T14:31:52Z","checksum":"fe0f7c49a99ed870c671b911e10d5496","success":1,"date_updated":"2020-10-27T14:31:52Z"}],"title":"Generalizing CGAL periodic Delaunay triangulations","publication":"28th Annual European Symposium on Algorithms","project":[{"name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"788183"}],"citation":{"chicago":"Osang, Georg F, Mael Rouxel-Labbé, and Monique Teillaud. “Generalizing CGAL Periodic Delaunay Triangulations.” 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.75\">https://doi.org/10.4230/LIPIcs.ESA.2020.75</a>.","ieee":"G. F. Osang, M. Rouxel-Labbé, and M. Teillaud, “Generalizing CGAL periodic Delaunay triangulations,” in <i>28th Annual European Symposium on Algorithms</i>, Virtual, Online; Pisa, Italy, 2020, vol. 173.","apa":"Osang, G. F., Rouxel-Labbé, M., &#38; Teillaud, M. (2020). Generalizing CGAL periodic Delaunay triangulations. In <i>28th Annual European Symposium on Algorithms</i> (Vol. 173). Virtual, Online; Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.75\">https://doi.org/10.4230/LIPIcs.ESA.2020.75</a>","ista":"Osang GF, Rouxel-Labbé M, Teillaud M. 2020. Generalizing CGAL periodic Delaunay triangulations. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 75.","mla":"Osang, Georg F., et al. “Generalizing CGAL Periodic Delaunay Triangulations.” <i>28th Annual European Symposium on Algorithms</i>, vol. 173, 75, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.75\">10.4230/LIPIcs.ESA.2020.75</a>.","short":"G.F. Osang, M. Rouxel-Labbé, M. Teillaud, in:, 28th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ama":"Osang GF, Rouxel-Labbé M, Teillaud M. Generalizing CGAL periodic Delaunay triangulations. 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.75\">10.4230/LIPIcs.ESA.2020.75</a>"},"alternative_title":["LIPIcs"],"has_accepted_license":"1","scopus_import":"1"},{"author":[{"first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X"},{"first_name":"Alexander","full_name":"Fedorov, Alexander","last_name":"Fedorov"},{"last_name":"Koval","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","first_name":"Nikita","full_name":"Koval, Nikita"}],"oa":1,"_id":"7605","date_published":"2020-02-01T00:00:00Z","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.OPODIS.2019.15","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2020","type":"conference","month":"02","quality_controlled":"1","publication_identifier":{"isbn":["9783959771337"],"issn":["18688969"]},"volume":153,"date_created":"2020-03-22T23:00:46Z","department":[{"_id":"DaAl"}],"article_processing_charge":"No","ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:48:01Z","conference":{"location":"Neuchatal, Switzerland","start_date":"2019-12-17","end_date":"2019-12-19","name":"OPODIS: International Conference on Principles of Distributed Systems"},"intvolume":"       153","page":"15:1-15:16","oa_version":"Published Version","publication_status":"published","tmp":{"image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode"},"day":"01","abstract":[{"text":"Union-Find (or Disjoint-Set Union) is one of the fundamental problems in computer science; it has been well-studied from both theoretical and practical perspectives in the sequential case. Recently, there has been mounting interest in analyzing this problem in the concurrent scenario, and several asymptotically-efficient algorithms have been proposed. Yet, to date, there is very little known about the practical performance of concurrent Union-Find. This work addresses this gap. We evaluate and analyze the performance of several concurrent Union-Find algorithms and optimization strategies across a wide range of platforms (Intel, AMD, and ARM) and workloads (social, random, and road networks, as well as integrations into more complex algorithms). We first observe that, due to the limited computational cost, the number of induced cache misses is the critical determining factor for the performance of existing algorithms. We introduce new techniques to reduce this cost by storing node priorities implicitly and by using plain reads and writes in a way that does not affect the correctness of the algorithms. Finally, we show that Union-Find implementations are an interesting application for Transactional Memory (TM): one of the fastest algorithm variants we discovered is a sequential one that uses coarse-grained locking with the lock elision optimization to reduce synchronization cost and increase scalability. ","lang":"eng"}],"date_updated":"2023-02-23T13:12:12Z","status":"public","publication":"23rd International Conference on Principles of Distributed Systems","external_id":{"arxiv":["1911.06347"]},"file":[{"date_updated":"2020-07-14T12:48:01Z","date_created":"2020-03-23T09:22:48Z","file_id":"7609","checksum":"d66f07ecb609d9f02433e39f80a447e9","file_size":13074131,"file_name":"2019_LIPIcs_Alistarh.pdf","content_type":"application/pdf","relation":"main_file","access_level":"open_access","creator":"dernst"}],"title":"In search of the fastest concurrent union-find algorithm","citation":{"chicago":"Alistarh, Dan-Adrian, Alexander Fedorov, and Nikita Koval. “In Search of the Fastest Concurrent Union-Find Algorithm.” In <i>23rd International Conference on Principles of Distributed Systems</i>, 153:15:1-15:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2019.15\">https://doi.org/10.4230/LIPIcs.OPODIS.2019.15</a>.","ieee":"D.-A. Alistarh, A. Fedorov, and N. Koval, “In search of the fastest concurrent union-find algorithm,” in <i>23rd International Conference on Principles of Distributed Systems</i>, Neuchatal, Switzerland, 2020, vol. 153, p. 15:1-15:16.","apa":"Alistarh, D.-A., Fedorov, A., &#38; Koval, N. (2020). In search of the fastest concurrent union-find algorithm. In <i>23rd International Conference on Principles of Distributed Systems</i> (Vol. 153, p. 15:1-15:16). Neuchatal, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2019.15\">https://doi.org/10.4230/LIPIcs.OPODIS.2019.15</a>","ista":"Alistarh D-A, Fedorov A, Koval N. 2020. In search of the fastest concurrent union-find algorithm. 23rd International Conference on Principles of Distributed Systems. OPODIS: International Conference on Principles of Distributed Systems, LIPIcs, vol. 153, 15:1-15:16.","mla":"Alistarh, Dan-Adrian, et al. “In Search of the Fastest Concurrent Union-Find Algorithm.” <i>23rd International Conference on Principles of Distributed Systems</i>, vol. 153, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 15:1-15:16, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2019.15\">10.4230/LIPIcs.OPODIS.2019.15</a>.","short":"D.-A. Alistarh, A. Fedorov, N. Koval, in:, 23rd International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 15:1-15:16.","ama":"Alistarh D-A, Fedorov A, Koval N. In search of the fastest concurrent union-find algorithm. In: <i>23rd International Conference on Principles of Distributed Systems</i>. Vol 153. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020:15:1-15:16. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2019.15\">10.4230/LIPIcs.OPODIS.2019.15</a>"},"arxiv":1,"scopus_import":"1","alternative_title":["LIPIcs"],"has_accepted_license":"1"},{"citation":{"chicago":"Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.46\">https://doi.org/10.4230/LIPIcs.SoCG.2018.46</a>.","ieee":"K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99.","short":"K. Huszár, J. Spreer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","ista":"Huszár K, Spreer J, Wagner U. 2018. On the treewidth of triangulated 3-manifolds. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 46.","mla":"Huszár, Kristóf, et al. <i>On the Treewidth of Triangulated 3-Manifolds</i>. Vol. 99, 46, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.46\">10.4230/LIPIcs.SoCG.2018.46</a>.","apa":"Huszár, K., Spreer, J., &#38; Wagner, U. (2018). On the treewidth of triangulated 3-manifolds (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.46\">https://doi.org/10.4230/LIPIcs.SoCG.2018.46</a>","ama":"Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.46\">10.4230/LIPIcs.SoCG.2018.46</a>"},"arxiv":1,"scopus_import":1,"alternative_title":["LIPIcs"],"has_accepted_license":"1","external_id":{"arxiv":["1712.00434"]},"related_material":{"record":[{"status":"public","id":"7093","relation":"later_version"}]},"file":[{"file_name":"2018_LIPIcs_Huszar.pdf","file_size":642522,"date_created":"2018-12-17T15:32:38Z","checksum":"530d084116778135d5bffaa317479cac","file_id":"5713","date_updated":"2020-07-14T12:45:51Z","creator":"dernst","access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"title":"On the treewidth of triangulated 3-manifolds","date_updated":"2023-09-06T11:13:41Z","status":"public","publication_status":"published","oa_version":"Submitted Version","day":"01","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"abstract":[{"text":"In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how &quot;simple&quot; or &quot;thin&quot; a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth. In view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs). We derive these results from work of Agol and of Scharlemann and Thompson, by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 48(k+1) (resp. 4(3k+1)).","lang":"eng"}],"article_number":"46","date_created":"2018-12-11T11:45:37Z","acknowledgement":"Research of the second author was supported by the Einstein Foundation (project “Einstein Visiting Fellow Santos”) and by the Simons Foundation (“Simons Visiting Professors” program).","department":[{"_id":"UlWa"}],"article_processing_charge":"No","ddc":["516","000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:45:51Z","conference":{"start_date":"2018-06-11","end_date":"2018-06-14","name":"SoCG: Symposium on Computational Geometry","location":"Budapest, Hungary"},"intvolume":"        99","month":"06","quality_controlled":"1","publist_id":"7614","publication_identifier":{"issn":["18688969"]},"volume":99,"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2018.46","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2018","type":"conference","author":[{"first_name":"Kristóf","full_name":"Huszár, Kristóf","orcid":"0000-0002-5445-5057","id":"33C26278-F248-11E8-B48F-1D18A9856A87","last_name":"Huszár"},{"last_name":"Spreer","full_name":"Spreer, Jonathan","first_name":"Jonathan"},{"first_name":"Uli","full_name":"Wagner, Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"oa":1,"_id":"285","date_published":"2018-06-01T00:00:00Z"},{"scopus_import":1,"alternative_title":["LIPIcs"],"has_accepted_license":"1","pubrep_id":"1039","project":[{"_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S11402-N23","call_identifier":"FWF"},{"name":"Moderne Concurrency Paradigms","_id":"25F5A88A-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11402-N23"}],"citation":{"chicago":"Kragl, Bernhard, Shaz Qadeer, and Thomas A Henzinger. “Synchronizing the Asynchronous,” Vol. 118. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2018.21\">https://doi.org/10.4230/LIPIcs.CONCUR.2018.21</a>.","ieee":"B. Kragl, S. Qadeer, and T. A. Henzinger, “Synchronizing the asynchronous,” presented at the CONCUR: International Conference on Concurrency Theory, Beijing, China, 2018, vol. 118.","apa":"Kragl, B., Qadeer, S., &#38; Henzinger, T. A. (2018). Synchronizing the asynchronous (Vol. 118). Presented at the CONCUR: International Conference on Concurrency Theory, Beijing, China: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2018.21\">https://doi.org/10.4230/LIPIcs.CONCUR.2018.21</a>","ista":"Kragl B, Qadeer S, Henzinger TA. 2018. Synchronizing the asynchronous. CONCUR: International Conference on Concurrency Theory, LIPIcs, vol. 118, 21.","mla":"Kragl, Bernhard, et al. <i>Synchronizing the Asynchronous</i>. Vol. 118, 21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2018.21\">10.4230/LIPIcs.CONCUR.2018.21</a>.","short":"B. Kragl, S. Qadeer, T.A. Henzinger, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","ama":"Kragl B, Qadeer S, Henzinger TA. Synchronizing the asynchronous. In: Vol 118. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2018.21\">10.4230/LIPIcs.CONCUR.2018.21</a>"},"related_material":{"record":[{"id":"6426","status":"public","relation":"earlier_version"},{"id":"8332","status":"public","relation":"dissertation_contains"}]},"file":[{"relation":"main_file","content_type":"application/pdf","access_level":"open_access","creator":"system","date_updated":"2020-07-14T12:44:44Z","date_created":"2018-12-12T10:18:46Z","file_id":"5368","checksum":"c90895f4c5fafc18ddc54d1c8848077e","file_size":745438,"file_name":"IST-2018-853-v2+2_concur2018.pdf"}],"title":"Synchronizing the asynchronous","status":"public","date_updated":"2023-09-07T13:18:00Z","oa_version":"Published Version","publication_status":"published","day":"13","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"abstract":[{"text":"Synchronous programs are easy to specify because the side effects of an operation are finished by the time the invocation of the operation returns to the caller. Asynchronous programs, on the other hand, are difficult to specify because there are side effects due to pending computation scheduled as a result of the invocation of an operation. They are also difficult to verify because of the large number of possible interleavings of concurrent computation threads. We present synchronization, a new proof rule that simplifies the verification of asynchronous programs by introducing the fiction, for proof purposes, that asynchronous operations complete synchronously. Synchronization summarizes an asynchronous computation as immediate atomic effect. Modular verification is enabled via pending asynchronous calls in atomic summaries, and a complementary proof rule that eliminates pending asynchronous calls when components and their specifications are composed. We evaluate synchronization in the context of a multi-layer refinement verification methodology on a collection of benchmark programs.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"file_date_updated":"2020-07-14T12:44:44Z","conference":{"start_date":"2018-09-04","end_date":"2018-09-07","name":"CONCUR: International Conference on Concurrency Theory","location":"Beijing, China"},"intvolume":"       118","article_number":"21","date_created":"2018-12-11T11:44:48Z","department":[{"_id":"ToHe"}],"volume":118,"month":"08","quality_controlled":"1","publication_identifier":{"issn":["18688969"]},"publist_id":"7790","type":"conference","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.CONCUR.2018.21","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2018","date_published":"2018-08-13T00:00:00Z","author":[{"orcid":"0000-0001-7745-9117","last_name":"Kragl","id":"320FC952-F248-11E8-B48F-1D18A9856A87","full_name":"Kragl, Bernhard","first_name":"Bernhard"},{"first_name":"Shaz","full_name":"Qadeer, Shaz","last_name":"Qadeer"},{"first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"oa":1,"_id":"133"},{"type":"conference","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2017","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.STACS.2017.57","date_published":"2017-03-01T00:00:00Z","oa":1,"_id":"1174","author":[{"last_name":"Skórski","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","full_name":"Skórski, Maciej","first_name":"Maciej"}],"intvolume":"        66","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","conference":{"name":"STACS: Symposium on Theoretical Aspects of Computer Science","start_date":"2017-03-08","end_date":"2017-03-11","location":"Hannover, Germany"},"department":[{"_id":"KrPi"}],"date_created":"2018-12-11T11:50:32Z","article_number":"57","volume":66,"isi":1,"quality_controlled":"1","publication_identifier":{"issn":["18688969"]},"publist_id":"6180","month":"03","status":"public","date_updated":"2023-09-20T11:23:15Z","ec_funded":1,"abstract":[{"lang":"eng","text":"Security of cryptographic applications is typically defined by security games. The adversary, within certain resources, cannot win with probability much better than 0 (for unpredictability applications, like one-way functions) or much better than 1/2 (indistinguishability applications for instance encryption schemes). In so called squared-friendly applications the winning probability of the adversary, for different values of the application secret randomness, is not only close to 0 or 1/2 on average, but also concentrated in the sense that its second central moment is small. The class of squared-friendly applications, which contains all unpredictability applications and many indistinguishability applications, is particularly important for key derivation. Barak et al. observed that for square-friendly applications one can beat the &quot;RT-bound&quot;, extracting secure keys with significantly smaller entropy loss. In turn Dodis and Yu showed that in squared-friendly applications one can directly use a &quot;weak&quot; key, which has only high entropy, as a secure key. In this paper we give sharp lower bounds on square security assuming security for &quot;weak&quot; keys. We show that any application which is either (a) secure with weak keys or (b) allows for entropy savings for keys derived by universal hashing, must be square-friendly. Quantitatively, our lower bounds match the positive results of Dodis and Yu and Barak et al. (TCC\\'13, CRYPTO\\'11) Hence, they can be understood as a general characterization of squared-friendly applications. While the positive results on squared-friendly applications where derived by one clever application of the Cauchy-Schwarz Inequality, for tight lower bounds we need more machinery. In our approach we use convex optimization techniques and some theory of circular matrices."}],"publication_status":"published","oa_version":"Submitted Version","day":"01","alternative_title":["LIPIcs"],"scopus_import":"1","project":[{"call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"citation":{"ieee":"M. Skórski, “Lower bounds on key derivation for square-friendly applications,” presented at the STACS: Symposium on Theoretical Aspects of Computer Science, Hannover, Germany, 2017, vol. 66.","chicago":"Skórski, Maciej. “Lower Bounds on Key Derivation for Square-Friendly Applications,” Vol. 66. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2017.57\">https://doi.org/10.4230/LIPIcs.STACS.2017.57</a>.","ama":"Skórski M. Lower bounds on key derivation for square-friendly applications. In: Vol 66. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2017.57\">10.4230/LIPIcs.STACS.2017.57</a>","ista":"Skórski M. 2017. Lower bounds on key derivation for square-friendly applications. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 66, 57.","apa":"Skórski, M. (2017). Lower bounds on key derivation for square-friendly applications (Vol. 66). Presented at the STACS: Symposium on Theoretical Aspects of Computer Science, Hannover, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2017.57\">https://doi.org/10.4230/LIPIcs.STACS.2017.57</a>","mla":"Skórski, Maciej. <i>Lower Bounds on Key Derivation for Square-Friendly Applications</i>. Vol. 66, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2017.57\">10.4230/LIPIcs.STACS.2017.57</a>.","short":"M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017."},"external_id":{"isi":["000521077300057"]},"title":"Lower bounds on key derivation for square-friendly applications","main_file_link":[{"open_access":"1","url":"http://drops.dagstuhl.de/opus/volltexte/2017/6976"}]},{"department":[{"_id":"KrPi"}],"date_created":"2018-12-11T11:50:33Z","intvolume":"        67","conference":{"location":"Berkeley, CA, United States","name":"ITCS: Innovations in Theoretical Computer Science","start_date":"2017-01-09","end_date":"2017-01-11"},"file_date_updated":"2020-07-14T12:44:37Z","ddc":["005","600"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"6179","publication_identifier":{"issn":["18688969"]},"quality_controlled":"1","month":"01","volume":67,"year":"2017","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","doi":"10.4230/LIPIcs.ITCS.2017.38","language":[{"iso":"eng"}],"type":"conference","_id":"1175","oa":1,"author":[{"first_name":"Joel F","full_name":"Alwen, Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen"},{"last_name":"De Rezende","first_name":"Susanna","full_name":"De Rezende, Susanna"},{"last_name":"Nordstrom","first_name":"Jakob","full_name":"Nordstrom, Jakob"},{"last_name":"Vinyals","first_name":"Marc","full_name":"Vinyals, Marc"}],"date_published":"2017-01-01T00:00:00Z","citation":{"chicago":"Alwen, Joel F, Susanna De Rezende, Jakob Nordstrom, and Marc Vinyals. “Cumulative Space in Black-White Pebbling and Resolution.” edited by Christos Papadimitriou, 67:38:1-38-21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2017.38\">https://doi.org/10.4230/LIPIcs.ITCS.2017.38</a>.","ieee":"J. F. Alwen, S. De Rezende, J. Nordstrom, and M. Vinyals, “Cumulative space in black-white pebbling and resolution,” presented at the ITCS: Innovations in Theoretical Computer Science, Berkeley, CA, United States, 2017, vol. 67, p. 38:1-38-21.","apa":"Alwen, J. F., De Rezende, S., Nordstrom, J., &#38; Vinyals, M. (2017). Cumulative space in black-white pebbling and resolution. In C. Papadimitriou (Ed.) (Vol. 67, p. 38:1-38-21). Presented at the ITCS: Innovations in Theoretical Computer Science, Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2017.38\">https://doi.org/10.4230/LIPIcs.ITCS.2017.38</a>","ista":"Alwen JF, De Rezende S, Nordstrom J, Vinyals M. 2017. Cumulative space in black-white pebbling and resolution. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 67, 38:1-38-21.","mla":"Alwen, Joel F., et al. <i>Cumulative Space in Black-White Pebbling and Resolution</i>. Edited by Christos Papadimitriou, vol. 67, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 38:1-38-21, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2017.38\">10.4230/LIPIcs.ITCS.2017.38</a>.","short":"J.F. Alwen, S. De Rezende, J. Nordstrom, M. Vinyals, in:, C. Papadimitriou (Ed.), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 38:1-38-21.","ama":"Alwen JF, De Rezende S, Nordstrom J, Vinyals M. Cumulative space in black-white pebbling and resolution. In: Papadimitriou C, ed. Vol 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017:38:1-38-21. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2017.38\">10.4230/LIPIcs.ITCS.2017.38</a>"},"pubrep_id":"927","has_accepted_license":"1","alternative_title":["LIPIcs"],"editor":[{"full_name":"Papadimitriou, Christos","first_name":"Christos","last_name":"Papadimitriou"}],"scopus_import":1,"file":[{"date_updated":"2020-07-14T12:44:37Z","file_id":"5263","date_created":"2018-12-12T10:17:11Z","checksum":"dbc94810be07c2fb1945d5c2a6130e6c","file_size":557769,"file_name":"IST-2018-927-v1+1_LIPIcs-ITCS-2017-38.pdf","relation":"main_file","content_type":"application/pdf","access_level":"open_access","creator":"system"}],"title":"Cumulative space in black-white pebbling and resolution","date_updated":"2021-01-12T06:48:51Z","status":"public","abstract":[{"text":"We study space complexity and time-space trade-offs with a focus not on peak memory usage but on overall memory consumption throughout the computation.  Such a cumulative space measure was introduced for the computational model of parallel black pebbling by [Alwen and Serbinenko ’15] as a tool for obtaining results in cryptography. We consider instead the non- deterministic black-white pebble game and prove optimal cumulative space lower bounds and trade-offs, where in order to minimize pebbling time the space has to remain large during a significant fraction of the pebbling. We also initiate the study of cumulative space in proof complexity, an area where other space complexity measures have been extensively studied during the last 10–15 years. Using and extending the connection between proof complexity and pebble games in [Ben-Sasson and Nordström ’08, ’11] we obtain several strong cumulative space results for (even parallel versions of) the resolution proof system, and outline some possible future directions of study of this, in our opinion, natural and interesting space measure.","lang":"eng"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"day":"01","page":"38:1-38-21","publication_status":"published","oa_version":"Published Version"}]