[{"oa_version":"Published Version","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"}],"intvolume":" 286","month":"01","alternative_title":["LIPIcs"],"scopus_import":"1","language":[{"iso":"eng"}],"file":[{"checksum":"4fc7eea6e4ba140b904781fc7df868ec","file_id":"15028","success":1,"access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2024-02-26T09:04:58Z","file_name":"2024_LIPICs_Hirvonen.pdf","creator":"dernst","date_updated":"2024-02-26T09:04:58Z","file_size":867363}],"publication_status":"published","publication_identifier":{"isbn":["9783959773089"],"issn":["18688969"]},"ec_funded":1,"volume":286,"_id":"15006","status":"public","conference":{"name":"OPODIS: Conference on Principles of Distributed Systems","location":"Tokyo, Japan","end_date":"2023-12-08","start_date":"2023-12-06"},"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)"},"type":"conference","ddc":["000"],"date_updated":"2024-02-26T09:16:12Z","department":[{"_id":"KrCh"}],"file_date_updated":"2024-02-26T09:04:58Z","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":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","publication":"27th International Conference on Principles of Distributed Systems","day":"18","year":"2024","has_accepted_license":"1","date_created":"2024-02-18T23:01:01Z","doi":"10.4230/LIPIcs.OPODIS.2023.11","date_published":"2024-01-18T00:00:00Z","article_number":"11","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Hirvonen, Juho, et al. “On the Convergence Time in Graphical Games: A Locality-Sensitive Approach.” 27th International Conference on Principles of Distributed Systems, vol. 286, 11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.OPODIS.2023.11.","ieee":"J. Hirvonen, L. Schmid, K. Chatterjee, and S. Schmid, “On the convergence time in graphical games: A locality-sensitive approach,” in 27th International Conference on Principles of Distributed Systems, Tokyo, Japan, 2024, vol. 286.","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.","ama":"Hirvonen J, Schmid L, Chatterjee K, Schmid S. On the convergence time in graphical games: A locality-sensitive approach. In: 27th International Conference on Principles of Distributed Systems. Vol 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.OPODIS.2023.11","apa":"Hirvonen, J., Schmid, L., Chatterjee, K., & Schmid, S. (2024). On the convergence time in graphical games: A locality-sensitive approach. In 27th International Conference on Principles of Distributed Systems (Vol. 286). Tokyo, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2023.11","chicago":"Hirvonen, Juho, Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid. “On the Convergence Time in Graphical Games: A Locality-Sensitive Approach.” In 27th International Conference on Principles of Distributed Systems, Vol. 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.OPODIS.2023.11.","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."},"title":"On the convergence time in graphical games: A locality-sensitive approach","external_id":{"arxiv":["2102.13457"]},"article_processing_charge":"No","author":[{"full_name":"Hirvonen, Juho","last_name":"Hirvonen","first_name":"Juho"},{"last_name":"Schmid","full_name":"Schmid, Laura","orcid":"0000-0002-6978-7329","id":"38B437DE-F248-11E8-B48F-1D18A9856A87","first_name":"Laura"},{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"first_name":"Stefan","full_name":"Schmid, Stefan","last_name":"Schmid"}]},{"_id":"14086","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)"},"conference":{"end_date":"2023-07-14","location":"Paderborn, Germany","start_date":"2023-07-10","name":"ICALP: International Colloquium on Automata, Languages, and Programming"},"type":"conference","status":"public","date_updated":"2023-08-21T07:05:47Z","ddc":["000"],"file_date_updated":"2023-08-21T07:04:36Z","department":[{"_id":"MoHe"}],"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"}],"oa_version":"Published Version","alternative_title":["LIPIcs"],"scopus_import":"1","intvolume":" 261","month":"07","publication_status":"published","publication_identifier":{"issn":["18688969"],"isbn":["9783959772785"]},"language":[{"iso":"eng"}],"file":[{"file_name":"2023_LIPIcsICALP_HenzingerM.pdf","date_created":"2023-08-21T07:04:36Z","creator":"dernst","file_size":930943,"date_updated":"2023-08-21T07:04:36Z","success":1,"file_id":"14090","checksum":"a5eef225014e003efbfbe4830fdd23cb","relation":"main_file","access_level":"open_access","content_type":"application/pdf"}],"ec_funded":1,"volume":261,"article_number":"74","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","grant_number":"101019564"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775 "}],"citation":{"chicago":"Henzinger, Monika H, Paul Liu, Jan Vondrák, and Da Wei Zheng. “Faster Submodular Maximization for Several Classes of Matroids.” In 50th International Colloquium on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.74.","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.","mla":"Henzinger, Monika H., et al. “Faster Submodular Maximization for Several Classes of Matroids.” 50th International Colloquium on Automata, Languages, and Programming, vol. 261, 74, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.74.","ieee":"M. H. Henzinger, P. Liu, J. Vondrák, and D. W. Zheng, “Faster submodular maximization for several classes of matroids,” in 50th International Colloquium on Automata, Languages, and Programming, Paderborn, Germany, 2023, vol. 261.","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: 50th International Colloquium on Automata, Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.74","apa":"Henzinger, M. H., Liu, P., Vondrák, J., & Zheng, D. W. (2023). Faster submodular maximization for several classes of matroids. In 50th International Colloquium on Automata, Languages, and Programming (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.74"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["2305.00122"]},"article_processing_charge":"Yes","author":[{"last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"},{"first_name":"Paul","last_name":"Liu","full_name":"Liu, Paul"},{"last_name":"Vondrák","full_name":"Vondrák, Jan","first_name":"Jan"},{"full_name":"Zheng, Da Wei","last_name":"Zheng","first_name":"Da Wei"}],"title":"Faster submodular maximization for several classes of matroids","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.","oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","year":"2023","has_accepted_license":"1","publication":"50th International Colloquium on Automata, Languages, and Programming","day":"01","date_created":"2023-08-20T22:01:14Z","date_published":"2023-07-01T00:00:00Z","doi":"10.4230/LIPIcs.ICALP.2023.74"},{"project":[{"call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093","name":"Vigilant Algorithmic Monitoring of Software"}],"article_number":"21","title":"Hypernode automata","author":[{"first_name":"Ezio","full_name":"Bartocci, Ezio","last_name":"Bartocci"},{"last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Nickovic","full_name":"Nickovic, Dejan","id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87","first_name":"Dejan"},{"last_name":"Oliveira da Costa","full_name":"Oliveira da Costa, Ana","orcid":"0000-0002-8741-5799","id":"f347ec37-6676-11ee-b395-a888cb7b4fb4","first_name":"Ana"}],"article_processing_charge":"Yes","external_id":{"arxiv":["2305.02836"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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.","chicago":"Bartocci, Ezio, Thomas A Henzinger, Dejan Nickovic, and Ana Oliveira da Costa. “Hypernode Automata.” In 34th International Conference on Concurrency Theory, Vol. 279. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.CONCUR.2023.21.","apa":"Bartocci, E., Henzinger, T. A., Nickovic, D., & Oliveira da Costa, A. (2023). Hypernode automata. In 34th International Conference on Concurrency Theory (Vol. 279). Antwerp, Belgium: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2023.21","ama":"Bartocci E, Henzinger TA, Nickovic D, Oliveira da Costa A. Hypernode automata. In: 34th International Conference on Concurrency Theory. Vol 279. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.CONCUR.2023.21","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.","ieee":"E. Bartocci, T. A. Henzinger, D. Nickovic, and A. Oliveira da Costa, “Hypernode automata,” in 34th International Conference on Concurrency Theory, Antwerp, Belgium, 2023, vol. 279.","mla":"Bartocci, Ezio, et al. “Hypernode Automata.” 34th International Conference on Concurrency Theory, vol. 279, 21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.CONCUR.2023.21."},"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"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.","date_published":"2023-09-01T00:00:00Z","doi":"10.4230/LIPIcs.CONCUR.2023.21","date_created":"2023-10-08T22:01:16Z","day":"01","publication":"34th International Conference on Concurrency Theory","has_accepted_license":"1","year":"2023","status":"public","type":"conference","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)"},"conference":{"end_date":"2023-09-22","location":"Antwerp, Belgium","start_date":"2023-09-19","name":"CONCUR: Conference on Concurrency Theory"},"_id":"14405","department":[{"_id":"ToHe"}],"file_date_updated":"2023-10-09T07:42:45Z","ddc":["000"],"date_updated":"2023-10-09T07:43:44Z","month":"09","intvolume":" 279","alternative_title":["LIPIcs"],"scopus_import":"1","oa_version":"Published Version","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"}],"volume":279,"ec_funded":1,"file":[{"date_created":"2023-10-09T07:42:45Z","file_name":"2023_LIPcs_Bartocci.pdf","date_updated":"2023-10-09T07:42:45Z","file_size":795790,"creator":"dernst","checksum":"215765e40454d806174ac0a223e8d6fa","file_id":"14413","success":1,"content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["18688969"],"isbn":["9783959772990"]},"publication_status":"published"},{"ddc":["516"],"date_updated":"2023-02-23T14:02:28Z","file_date_updated":"2021-06-28T13:11:39Z","department":[{"_id":"HeEd"}],"_id":"9604","status":"public","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)"},"conference":{"end_date":"2021-06-11","location":"Online","start_date":"2021-06-07","name":"SoCG: International Symposium on Computational Geometry"},"type":"conference","language":[{"iso":"eng"}],"file":[{"creator":"asandaue","file_size":727817,"date_updated":"2021-06-28T13:11:39Z","file_name":"2021_LIPIcs_Biswas.pdf","date_created":"2021-06-28T13:11:39Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","success":1,"file_id":"9611","checksum":"22b11a719018b22ecba2471b51f2eb40"}],"publication_status":"published","publication_identifier":{"isbn":["9783959771849"],"issn":["18688969"]},"ec_funded":1,"volume":189,"oa_version":"Published Version","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."}],"intvolume":" 189","month":"06","scopus_import":"1","alternative_title":["LIPIcs"],"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","citation":{"mla":"Biswas, Ranita, et al. “Counting Cells of Order-k Voronoi Tessellations in ℝ3 with Morse Theory.” Leibniz International Proceedings in Informatics, vol. 189, 16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.SoCG.2021.16.","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.","ieee":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, and M. Saghafian, “Counting cells of order-k voronoi tessellations in ℝ3 with morse theory,” in Leibniz International Proceedings in Informatics, Online, 2021, vol. 189.","apa":"Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., & Saghafian, M. (2021). Counting cells of order-k voronoi tessellations in ℝ3 with morse theory. In Leibniz International Proceedings in Informatics (Vol. 189). Online: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2021.16","ama":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. Counting cells of order-k voronoi tessellations in ℝ3 with morse theory. In: Leibniz International Proceedings in Informatics. Vol 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.SoCG.2021.16","chicago":"Biswas, Ranita, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian. “Counting Cells of Order-k Voronoi Tessellations in ℝ3 with Morse Theory.” In Leibniz International Proceedings in Informatics, Vol. 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.SoCG.2021.16.","ista":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. 2021. Counting cells of order-k voronoi tessellations in ℝ3 with morse theory. Leibniz International Proceedings in Informatics. SoCG: International Symposium on Computational Geometry, LIPIcs, vol. 189, 16."},"title":"Counting cells of order-k voronoi tessellations in ℝ3 with morse theory","article_processing_charge":"No","author":[{"last_name":"Biswas","orcid":"0000-0002-5372-7890","full_name":"Biswas, Ranita","id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","first_name":"Ranita"},{"id":"34D2A09C-F248-11E8-B48F-1D18A9856A87","first_name":"Sebastiano","orcid":"0000-0001-6249-0832","full_name":"Cultrera di Montesano, Sebastiano","last_name":"Cultrera di Montesano"},{"last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert"},{"first_name":"Morteza","full_name":"Saghafian, Morteza","last_name":"Saghafian"}],"article_number":"16","project":[{"_id":"266A2E9E-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Alpha Shape Theory Extended","grant_number":"788183"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z00342","name":"The Wittgenstein Prize"},{"_id":"0aa4bc98-070f-11eb-9043-e6fff9c6a316","grant_number":"I4887","name":"Discretization in Geometry and Dynamics"}],"publication":"Leibniz International Proceedings in Informatics","day":"02","year":"2021","has_accepted_license":"1","date_created":"2021-06-27T22:01:48Z","doi":"10.4230/LIPIcs.SoCG.2021.16","date_published":"2021-06-02T00:00:00Z","oa":1,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik"},{"article_number":"27","citation":{"chicago":"Corbet, René, Michael Kerber, Michael Lesnick, and Georg F Osang. “Computing the Multicover Bifiltration.” In Leibniz International Proceedings in Informatics, Vol. 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.SoCG.2021.27.","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.","mla":"Corbet, René, et al. “Computing the Multicover Bifiltration.” Leibniz International Proceedings in Informatics, vol. 189, 27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.SoCG.2021.27.","apa":"Corbet, R., Kerber, M., Lesnick, M., & Osang, G. F. (2021). Computing the multicover bifiltration. In Leibniz International Proceedings in Informatics (Vol. 189). Online: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2021.27","ama":"Corbet R, Kerber M, Lesnick M, Osang GF. Computing the multicover bifiltration. In: Leibniz International Proceedings in Informatics. Vol 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.SoCG.2021.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.","ieee":"R. Corbet, M. Kerber, M. Lesnick, and G. F. Osang, “Computing the multicover bifiltration,” in Leibniz International Proceedings in Informatics, Online, 2021, vol. 189."},"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","external_id":{"arxiv":["2103.07823"]},"article_processing_charge":"No","author":[{"first_name":"René","last_name":"Corbet","full_name":"Corbet, René"},{"full_name":"Kerber, Michael","last_name":"Kerber","first_name":"Michael"},{"first_name":"Michael","last_name":"Lesnick","full_name":"Lesnick, Michael"},{"first_name":"Georg F","id":"464B40D6-F248-11E8-B48F-1D18A9856A87","last_name":"Osang","orcid":"0000-0002-8882-5116","full_name":"Osang, Georg F"}],"title":"Computing the multicover bifiltration","acknowledgement":"The authors want to thank the reviewers for many helpful comments and suggestions.","oa":1,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2021","has_accepted_license":"1","publication":"Leibniz International Proceedings in Informatics","day":"02","date_created":"2021-06-27T22:01:49Z","date_published":"2021-06-02T00:00:00Z","doi":"10.4230/LIPIcs.SoCG.2021.27","_id":"9605","conference":{"name":"SoCG: International Symposium on Computational Geometry","start_date":"2021-06-07","location":"Online","end_date":"2021-06-11"},"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)"},"type":"conference","status":"public","date_updated":"2023-10-04T12:03:39Z","ddc":["516"],"file_date_updated":"2021-06-28T12:40:47Z","department":[{"_id":"HeEd"}],"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","scopus_import":"1","alternative_title":["LIPIcs"],"intvolume":" 189","month":"06","publication_status":"published","publication_identifier":{"issn":["18688969"],"isbn":["9783959771849"]},"language":[{"iso":"eng"}],"file":[{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"9610","checksum":"0de217501e7ba8b267d58deed0d51761","success":1,"date_updated":"2021-06-28T12:40:47Z","file_size":"1367983","creator":"cziletti","date_created":"2021-06-28T12:40:47Z","file_name":"2021_LIPIcs_Corbet.pdf"}],"related_material":{"link":[{"url":"https://arxiv.org/abs/2103.07823","relation":"extended_version"}],"record":[{"status":"public","id":"12709","relation":"later_version"}]},"volume":189},{"page":"15:1-15:16","date_created":"2020-03-22T23:00:46Z","doi":"10.4230/LIPIcs.OPODIS.2019.15","date_published":"2020-02-01T00:00:00Z","year":"2020","has_accepted_license":"1","publication":"23rd International Conference on Principles of Distributed Systems","day":"01","oa":1,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","external_id":{"arxiv":["1911.06347"]},"article_processing_charge":"No","author":[{"first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh"},{"full_name":"Fedorov, Alexander","last_name":"Fedorov","first_name":"Alexander"},{"full_name":"Koval, Nikita","last_name":"Koval","first_name":"Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87"}],"title":"In search of the fastest concurrent union-find algorithm","citation":{"mla":"Alistarh, Dan-Adrian, et al. “In Search of the Fastest Concurrent Union-Find Algorithm.” 23rd International Conference on Principles of Distributed Systems, vol. 153, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 15:1-15:16, doi:10.4230/LIPIcs.OPODIS.2019.15.","ieee":"D.-A. Alistarh, A. Fedorov, and N. Koval, “In search of the fastest concurrent union-find algorithm,” in 23rd International Conference on Principles of Distributed Systems, Neuchatal, Switzerland, 2020, vol. 153, p. 15:1-15:16.","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: 23rd International Conference on Principles of Distributed Systems. Vol 153. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020:15:1-15:16. doi:10.4230/LIPIcs.OPODIS.2019.15","apa":"Alistarh, D.-A., Fedorov, A., & Koval, N. (2020). In search of the fastest concurrent union-find algorithm. In 23rd International Conference on Principles of Distributed Systems (Vol. 153, p. 15:1-15:16). Neuchatal, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2019.15","chicago":"Alistarh, Dan-Adrian, Alexander Fedorov, and Nikita Koval. “In Search of the Fastest Concurrent Union-Find Algorithm.” In 23rd International Conference on Principles of Distributed Systems, 153:15:1-15:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.OPODIS.2019.15.","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."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","license":"https://creativecommons.org/licenses/by/3.0/","volume":153,"publication_status":"published","publication_identifier":{"isbn":["9783959771337"],"issn":["18688969"]},"language":[{"iso":"eng"}],"file":[{"file_id":"7609","checksum":"d66f07ecb609d9f02433e39f80a447e9","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"2019_LIPIcs_Alistarh.pdf","date_created":"2020-03-23T09:22:48Z","creator":"dernst","file_size":13074131,"date_updated":"2020-07-14T12:48:01Z"}],"alternative_title":["LIPIcs"],"scopus_import":"1","intvolume":" 153","month":"02","abstract":[{"lang":"eng","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. "}],"oa_version":"Published Version","file_date_updated":"2020-07-14T12:48:01Z","department":[{"_id":"DaAl"}],"date_updated":"2023-02-23T13:12:12Z","ddc":["000"],"tmp":{"short":"CC BY (3.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"conference":{"name":"OPODIS: International Conference on Principles of Distributed Systems","start_date":"2019-12-17","end_date":"2019-12-19","location":"Neuchatal, Switzerland"},"type":"conference","status":"public","_id":"7605"},{"article_number":"12:1 - 12:15","project":[{"name":"Algorithms for Embeddings and Homotopy Theory","grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"citation":{"short":"S. Avvakumov, G. Nivasch, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ieee":"S. Avvakumov and G. Nivasch, “Homotopic curve shortening and the affine curve-shortening flow,” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","apa":"Avvakumov, S., & Nivasch, G. (2020). Homotopic curve shortening and the affine curve-shortening flow. In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.12","ama":"Avvakumov S, Nivasch G. Homotopic curve shortening and the affine curve-shortening flow. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.12","mla":"Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the Affine Curve-Shortening Flow.” 36th International Symposium on Computational Geometry, vol. 164, 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.12.","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.","chicago":"Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the Affine Curve-Shortening Flow.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.12."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","external_id":{"arxiv":["1909.00263"]},"author":[{"full_name":"Avvakumov, Sergey","last_name":"Avvakumov","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey"},{"last_name":"Nivasch","full_name":"Nivasch, Gabriel","first_name":"Gabriel"}],"title":"Homotopic curve shortening and the affine curve-shortening flow","oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","year":"2020","has_accepted_license":"1","publication":"36th International Symposium on Computational Geometry","day":"01","date_created":"2020-06-22T09:14:19Z","doi":"10.4230/LIPIcs.SoCG.2020.12","date_published":"2020-06-01T00:00:00Z","_id":"7991","tmp":{"short":"CC BY (3.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"conference":{"name":"SoCG: Symposium on Computational Geometry","location":"Zürich, Switzerland","end_date":"2020-06-26","start_date":"2020-06-22"},"type":"conference","status":"public","date_updated":"2021-01-12T08:16:23Z","ddc":["510"],"department":[{"_id":"UlWa"}],"file_date_updated":"2020-07-14T12:48:06Z","abstract":[{"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.","lang":"eng"}],"oa_version":"Published Version","alternative_title":["LIPIcs"],"scopus_import":"1","intvolume":" 164","month":"06","publication_status":"published","publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"language":[{"iso":"eng"}],"file":[{"creator":"dernst","file_size":575896,"date_updated":"2020-07-14T12:48:06Z","file_name":"2020_LIPIcsSoCG_Avvakumov.pdf","date_created":"2020-06-23T11:13:49Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","checksum":"6872df6549142f709fb6354a1b2f2c06","file_id":"8007"}],"volume":164},{"department":[{"_id":"UlWa"}],"file_date_updated":"2020-07-14T12:48:06Z","ddc":["510"],"date_updated":"2021-01-12T08:16:22Z","status":"public","type":"conference","conference":{"start_date":"2020-06-22","location":"Zürich, Switzerland","end_date":"2020-06-26","name":"SoCG: Symposium on Computational Geometry"},"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)"},"_id":"7989","volume":164,"file":[{"file_name":"2020_LIPIcsSoCG_Patakova_61.pdf","date_created":"2020-06-23T06:56:23Z","creator":"dernst","file_size":645421,"date_updated":"2020-07-14T12:48:06Z","checksum":"d0996ca5f6eb32ce955ce782b4f2afbe","file_id":"8005","relation":"main_file","access_level":"open_access","content_type":"application/pdf"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9783959771436"],"issn":["18688969"]},"publication_status":"published","month":"06","intvolume":" 164","scopus_import":"1","alternative_title":["LIPIcs"],"oa_version":"Published Version","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."}],"title":"Bounding radon number via Betti numbers","author":[{"id":"48B57058-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","last_name":"Patakova","full_name":"Patakova, Zuzana","orcid":"0000-0002-3975-1683"}],"article_processing_charge":"No","external_id":{"arxiv":["1908.01677"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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.","chicago":"Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.61.","ama":"Patakova Z. Bounding radon number via Betti numbers. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.61","apa":"Patakova, Z. (2020). Bounding radon number via Betti numbers. In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.61","ieee":"Z. Patakova, “Bounding radon number via Betti numbers,” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","short":"Z. Patakova, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","mla":"Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” 36th International Symposium on Computational Geometry, vol. 164, 61:1-61:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.61."},"article_number":"61:1-61:13","date_published":"2020-06-01T00:00:00Z","doi":"10.4230/LIPIcs.SoCG.2020.61","date_created":"2020-06-22T09:14:18Z","day":"01","publication":"36th International Symposium on Computational Geometry","has_accepted_license":"1","year":"2020","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through a Convex Body.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.62.","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.","mla":"Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” 36th International Symposium on Computational Geometry, vol. 164, 62:1-62:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.62.","ama":"Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.62","apa":"Patakova, Z., Tancer, M., & Wagner, U. (2020). Barycentric cuts through a convex body. In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.62","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 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164."},"title":"Barycentric cuts through a convex body","author":[{"last_name":"Patakova","full_name":"Patakova, Zuzana","orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana"},{"first_name":"Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1191-6714","full_name":"Tancer, Martin","last_name":"Tancer"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli"}],"article_processing_charge":"No","external_id":{"arxiv":["2003.13536"]},"article_number":"62:1 - 62:16","day":"01","publication":"36th International Symposium on Computational Geometry","has_accepted_license":"1","year":"2020","date_published":"2020-06-01T00:00:00Z","doi":"10.4230/LIPIcs.SoCG.2020.62","date_created":"2020-06-22T09:14:20Z","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"ddc":["510"],"date_updated":"2021-01-12T08:16:23Z","department":[{"_id":"UlWa"}],"file_date_updated":"2020-07-14T12:48:06Z","_id":"7992","status":"public","type":"conference","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)"},"conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2020-06-26","location":"Zürich, Switzerland","start_date":"2020-06-22"},"file":[{"file_name":"2020_LIPIcsSoCG_Patakova.pdf","date_created":"2020-06-23T06:45:52Z","file_size":750318,"date_updated":"2020-07-14T12:48:06Z","creator":"dernst","checksum":"ce1c9194139a664fb59d1efdfc88eaae","file_id":"8004","content_type":"application/pdf","relation":"main_file","access_level":"open_access"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"publication_status":"published","volume":164,"oa_version":"Published Version","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."}],"month":"06","intvolume":" 164","alternative_title":["LIPIcs"],"scopus_import":1},{"project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"article_number":"9:1 - 9:14","title":"Extending drawings of graphs to arrangements of pseudolines","article_processing_charge":"No","external_id":{"arxiv":["1804.09317"]},"author":[{"last_name":"Arroyo Guevara","orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M","first_name":"Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Julien","full_name":"Bensmail, Julien","last_name":"Bensmail"},{"last_name":"Bruce Richter","full_name":"Bruce Richter, R.","first_name":"R."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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.","chicago":"Arroyo Guevara, Alan M, Julien Bensmail, and R. Bruce Richter. “Extending Drawings of Graphs to Arrangements of Pseudolines.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.9.","ieee":"A. M. Arroyo Guevara, J. Bensmail, and R. Bruce Richter, “Extending drawings of graphs to arrangements of pseudolines,” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","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.","apa":"Arroyo Guevara, A. M., Bensmail, J., & Bruce Richter, R. (2020). Extending drawings of graphs to arrangements of pseudolines. In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.9","ama":"Arroyo Guevara AM, Bensmail J, Bruce Richter R. Extending drawings of graphs to arrangements of pseudolines. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.9","mla":"Arroyo Guevara, Alan M., et al. “Extending Drawings of Graphs to Arrangements of Pseudolines.” 36th International Symposium on Computational Geometry, vol. 164, 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.9."},"oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","date_created":"2020-06-22T09:14:21Z","date_published":"2020-06-01T00:00:00Z","doi":"10.4230/LIPIcs.SoCG.2020.9","publication":"36th International Symposium on Computational Geometry","day":"01","year":"2020","has_accepted_license":"1","status":"public","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)"},"conference":{"location":"Zürich, Switzerland","end_date":"2020-06-26","start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry"},"type":"conference","_id":"7994","file_date_updated":"2020-07-14T12:48:06Z","department":[{"_id":"UlWa"}],"ddc":["510"],"date_updated":"2023-02-23T13:22:12Z","intvolume":" 164","month":"06","alternative_title":["LIPIcs"],"scopus_import":"1","oa_version":"Published Version","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"}],"ec_funded":1,"volume":164,"language":[{"iso":"eng"}],"file":[{"file_id":"8006","checksum":"93571b76cf97d5b7c8aabaeaa694dd7e","access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2020-06-23T11:06:23Z","file_name":"2020_LIPIcsSoCG_Arroyo.pdf","creator":"dernst","date_updated":"2020-07-14T12:48:06Z","file_size":592661}],"publication_status":"published","publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]}},{"_id":"8600","status":"public","tmp":{"short":"CC BY (3.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"conference":{"end_date":"2020-09-04","location":"Virtual","start_date":"2020-09-01","name":"CONCUR: Conference on Concurrency Theory"},"type":"conference","ddc":["000"],"date_updated":"2021-01-12T08:20:15Z","file_date_updated":"2020-10-05T14:04:25Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"oa_version":"Published Version","abstract":[{"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.","lang":"eng"}],"intvolume":" 171","month":"08","scopus_import":"1","alternative_title":["LIPIcs"],"language":[{"iso":"eng"}],"file":[{"success":1,"file_id":"8610","checksum":"5039752f644c4b72b9361d21a5e31baf","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_name":"2020_LIPIcsCONCUR_Chatterjee.pdf","date_created":"2020-10-05T14:04:25Z","file_size":601231,"date_updated":"2020-10-05T14:04:25Z","creator":"dernst"}],"publication_status":"published","publication_identifier":{"issn":["18688969"],"isbn":["9783959771603"]},"volume":171,"article_number":"23","project":[{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"grant_number":"S11402-N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","grant_number":"Z211"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, “Multi-dimensional long-run average problems for vector addition systems with states,” in 31st International Conference on Concurrency Theory, Virtual, 2020, vol. 171.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, 31st International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","apa":"Chatterjee, K., Henzinger, T. A., & Otop, J. (2020). Multi-dimensional long-run average problems for vector addition systems with states. In 31st International Conference on Concurrency Theory (Vol. 171). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2020.23","ama":"Chatterjee K, Henzinger TA, Otop J. Multi-dimensional long-run average problems for vector addition systems with states. In: 31st International Conference on Concurrency Theory. Vol 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.CONCUR.2020.23","mla":"Chatterjee, Krishnendu, et al. “Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States.” 31st International Conference on Concurrency Theory, vol. 171, 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.CONCUR.2020.23.","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.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States.” In 31st International Conference on Concurrency Theory, Vol. 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.CONCUR.2020.23."},"title":"Multi-dimensional long-run average problems for vector addition systems with states","article_processing_charge":"No","external_id":{"arxiv":["2007.08917"]},"author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724"},{"first_name":"Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","last_name":"Otop"}],"oa":1,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication":"31st International Conference on Concurrency Theory","day":"06","year":"2020","has_accepted_license":"1","date_created":"2020-10-04T22:01:36Z","doi":"10.4230/LIPIcs.CONCUR.2020.23","date_published":"2020-08-06T00:00:00Z"},{"volume":171,"publication_status":"published","publication_identifier":{"isbn":["9783959771603"],"issn":["18688969"]},"language":[{"iso":"eng"}],"file":[{"file_name":"2020_LIPIcsCONCUR_Avni.pdf","date_created":"2020-10-05T14:13:19Z","creator":"dernst","file_size":868510,"date_updated":"2020-10-05T14:13:19Z","success":1,"checksum":"8f33b098e73724e0ac817f764d8e1a2d","file_id":"8611","relation":"main_file","access_level":"open_access","content_type":"application/pdf"}],"alternative_title":["LIPIcs"],"scopus_import":"1","intvolume":" 171","month":"08","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."}],"oa_version":"Published Version","department":[{"_id":"ToHe"}],"file_date_updated":"2020-10-05T14:13:19Z","date_updated":"2021-01-12T08:20:13Z","ddc":["000"],"tmp":{"short":"CC BY (3.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"conference":{"start_date":"2020-09-01","location":"Virtual","end_date":"2020-09-04","name":"CONCUR: Conference on Concurrency Theory"},"type":"conference","status":"public","_id":"8599","date_created":"2020-10-04T22:01:36Z","date_published":"2020-08-06T00:00:00Z","doi":"10.4230/LIPIcs.CONCUR.2020.2","year":"2020","has_accepted_license":"1","publication":"31st International Conference on Concurrency Theory","day":"06","oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","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.","article_processing_charge":"No","author":[{"last_name":"Avni","full_name":"Avni, Guy","orcid":"0000-0001-5588-8287","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","first_name":"Guy"},{"orcid":"0000-0002-2985-7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A"}],"title":"A survey of bidding games on graphs","citation":{"chicago":"Avni, Guy, and Thomas A Henzinger. “A Survey of Bidding Games on Graphs.” In 31st International Conference on Concurrency Theory, Vol. 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.CONCUR.2020.2.","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.” 31st International Conference on Concurrency Theory, vol. 171, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.CONCUR.2020.2.","ieee":"G. Avni and T. A. Henzinger, “A survey of bidding games on graphs,” in 31st International Conference on Concurrency Theory, Virtual, 2020, vol. 171.","short":"G. Avni, T.A. Henzinger, in:, 31st International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ama":"Avni G, Henzinger TA. A survey of bidding games on graphs. In: 31st International Conference on Concurrency Theory. Vol 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.CONCUR.2020.2","apa":"Avni, G., & Henzinger, T. A. (2020). A survey of bidding games on graphs. In 31st International Conference on Concurrency Theory (Vol. 171). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2020.2"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z211","name":"The Wittgenstein Prize"}],"article_number":"2"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Chatterjee, Krishnendu, et al. “Simplified Game of Life: Algorithms and Complexity.” 45th International Symposium on Mathematical Foundations of Computer Science, vol. 170, 22:1-22:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.MFCS.2020.22.","apa":"Chatterjee, K., Ibsen-Jensen, R., Jecker, I. R., & Svoboda, J. (2020). Simplified game of life: Algorithms and complexity. In 45th International Symposium on Mathematical Foundations of Computer Science (Vol. 170). Prague, Czech Republic: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2020.22","ama":"Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. Simplified game of life: Algorithms and complexity. In: 45th International Symposium on Mathematical Foundations of Computer Science. Vol 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.MFCS.2020.22","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.","ieee":"K. Chatterjee, R. Ibsen-Jensen, I. R. Jecker, and J. Svoboda, “Simplified game of life: Algorithms and complexity,” in 45th International Symposium on Mathematical Foundations of Computer Science, 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 45th International Symposium on Mathematical Foundations of Computer Science, Vol. 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.MFCS.2020.22.","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."},"title":"Simplified game of life: Algorithms and complexity","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen"},{"id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","first_name":"Ismael R","full_name":"Jecker, Ismael R","last_name":"Jecker"},{"first_name":"Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","full_name":"Svoboda, Jakub","last_name":"Svoboda"}],"external_id":{"arxiv":["2007.02894"]},"article_processing_charge":"No","article_number":"22:1-22:13","project":[{"grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425"},{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411"}],"day":"18","publication":"45th International Symposium on Mathematical Foundations of Computer Science","has_accepted_license":"1","year":"2020","date_published":"2020-08-18T00:00:00Z","doi":"10.4230/LIPIcs.MFCS.2020.22","date_created":"2020-09-20T22:01:36Z","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.","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","oa":1,"ddc":["000"],"date_updated":"2021-01-12T08:19:55Z","file_date_updated":"2020-09-21T13:57:34Z","department":[{"_id":"KrCh"}],"_id":"8533","status":"public","type":"conference","tmp":{"short":"CC BY (3.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"conference":{"name":"MFCS: Symposium on Mathematical Foundations of Computer Science","location":"Prague, Czech Republic","end_date":"2020-08-28","start_date":"2020-08-24"},"file":[{"success":1,"file_id":"8550","checksum":"bbd7c4f55d45f2ff2a0a4ef0e10a77b1","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_name":"2020_LIPIcs_Chatterjee.pdf","date_created":"2020-09-21T13:57:34Z","file_size":491374,"date_updated":"2020-09-21T13:57:34Z","creator":"dernst"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9783959771597"],"issn":["18688969"]},"publication_status":"published","volume":170,"ec_funded":1,"oa_version":"Published Version","abstract":[{"lang":"eng","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."}],"month":"08","intvolume":" 170","scopus_import":"1","alternative_title":["LIPIcs"]},{"volume":170,"ec_funded":1,"file":[{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"2dc9e2fad6becd4563aef3e27a473f70","file_id":"8552","success":1,"date_updated":"2020-09-21T14:17:08Z","file_size":597977,"creator":"dernst","date_created":"2020-09-21T14:17:08Z","file_name":"2020_LIPIcsMFCS_Jecker.pdf"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["18688969"],"isbn":["9783959771597"]},"publication_status":"published","month":"08","intvolume":" 170","alternative_title":["LIPIcs"],"scopus_import":"1","oa_version":"Published Version","abstract":[{"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.","lang":"eng"}],"file_date_updated":"2020-09-21T14:17:08Z","department":[{"_id":"KrCh"}],"ddc":["000"],"date_updated":"2021-01-12T08:19:56Z","status":"public","type":"conference","conference":{"location":"Prague, Czech Republic","end_date":"2020-08-28","start_date":"2020-08-24","name":"MFCS: Symposium on Mathematical Foundations of Computer Science"},"tmp":{"short":"CC BY (3.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"_id":"8534","date_published":"2020-08-18T00:00:00Z","doi":"10.4230/LIPIcs.MFCS.2020.51","date_created":"2020-09-20T22:01:36Z","day":"18","publication":"45th International Symposium on Mathematical Foundations of Computer Science","has_accepted_license":"1","year":"2020","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","oa":1,"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.","title":"Unary prime languages","author":[{"first_name":"Ismael R","id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","full_name":"Jecker, Ismael R","last_name":"Jecker"},{"last_name":"Kupferman","full_name":"Kupferman, Orna","first_name":"Orna"},{"first_name":"Nicolas","last_name":"Mazzocchi","full_name":"Mazzocchi, Nicolas"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Jecker, Ismael R., et al. “Unary Prime Languages.” 45th International Symposium on Mathematical Foundations of Computer Science, vol. 170, 51:1-51:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.MFCS.2020.51.","ieee":"I. R. Jecker, O. Kupferman, and N. Mazzocchi, “Unary prime languages,” in 45th International Symposium on Mathematical Foundations of Computer Science, Prague, Czech Republic, 2020, vol. 170.","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.","ama":"Jecker IR, Kupferman O, Mazzocchi N. Unary prime languages. In: 45th International Symposium on Mathematical Foundations of Computer Science. Vol 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.MFCS.2020.51","apa":"Jecker, I. R., Kupferman, O., & Mazzocchi, N. (2020). Unary prime languages. In 45th International Symposium on Mathematical Foundations of Computer Science (Vol. 170). Prague, Czech Republic: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2020.51","chicago":"Jecker, Ismael R, Orna Kupferman, and Nicolas Mazzocchi. “Unary Prime Languages.” In 45th International Symposium on Mathematical Foundations of Computer Science, Vol. 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.MFCS.2020.51.","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."},"project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"article_number":"51:1-51:12"},{"oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","date_created":"2020-06-22T09:14:19Z","doi":"10.4230/LIPIcs.SoCG.2020.67","date_published":"2020-06-01T00:00:00Z","year":"2020","has_accepted_license":"1","publication":"36th International Symposium on Computational Geometry","day":"01","article_number":"67:1 - 67:16","article_processing_charge":"No","external_id":{"arxiv":["2003.13557"]},"author":[{"last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Welzl, Emo","last_name":"Welzl","first_name":"Emo"}],"title":"Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips)","citation":{"ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips),” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","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: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.67","apa":"Wagner, U., & Welzl, E. (2020). Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.67","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips).” 36th International Symposium on Computational Geometry, vol. 164, 67:1-67:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.67.","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.","chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips).” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.67."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LIPIcs"],"scopus_import":1,"intvolume":" 164","month":"06","abstract":[{"lang":"eng","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)."}],"oa_version":"Published Version","related_material":{"record":[{"id":"12129","status":"public","relation":"later_version"}]},"volume":164,"publication_status":"published","publication_identifier":{"isbn":["9783959771436"],"issn":["18688969"]},"language":[{"iso":"eng"}],"file":[{"date_created":"2020-06-23T06:37:27Z","file_name":"2020_LIPIcsSoCG_Wagner.pdf","date_updated":"2020-07-14T12:48:06Z","file_size":793187,"creator":"dernst","checksum":"3f6925be5f3dcdb3b14cab92f410edf7","file_id":"8003","content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2020-06-26","location":"Zürich, Switzerland","start_date":"2020-06-22"},"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)"},"type":"conference","status":"public","_id":"7990","department":[{"_id":"UlWa"}],"file_date_updated":"2020-07-14T12:48:06Z","date_updated":"2023-08-04T08:51:07Z","ddc":["510"]},{"date_published":"2020-08-26T00:00:00Z","doi":"10.4230/LIPIcs.ESA.2020.75","date_created":"2020-10-25T23:01:18Z","day":"26","publication":"28th Annual European Symposium on Algorithms","has_accepted_license":"1","year":"2020","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"title":"Generalizing CGAL periodic Delaunay triangulations","author":[{"last_name":"Osang","orcid":"0000-0002-8882-5116","full_name":"Osang, Georg F","first_name":"Georg F","id":"464B40D6-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Rouxel-Labbé, Mael","last_name":"Rouxel-Labbé","first_name":"Mael"},{"last_name":"Teillaud","full_name":"Teillaud, Monique","first_name":"Monique"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Osang, Georg F., et al. “Generalizing CGAL Periodic Delaunay Triangulations.” 28th Annual European Symposium on Algorithms, vol. 173, 75, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.ESA.2020.75.","short":"G.F. Osang, M. Rouxel-Labbé, M. Teillaud, in:, 28th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ieee":"G. F. Osang, M. Rouxel-Labbé, and M. Teillaud, “Generalizing CGAL periodic Delaunay triangulations,” in 28th Annual European Symposium on Algorithms, Virtual, Online; Pisa, Italy, 2020, vol. 173.","apa":"Osang, G. F., Rouxel-Labbé, M., & Teillaud, M. (2020). Generalizing CGAL periodic Delaunay triangulations. In 28th Annual European Symposium on Algorithms (Vol. 173). Virtual, Online; Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2020.75","ama":"Osang GF, Rouxel-Labbé M, Teillaud M. Generalizing CGAL periodic Delaunay triangulations. In: 28th Annual European Symposium on Algorithms. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.ESA.2020.75","chicago":"Osang, Georg F, Mael Rouxel-Labbé, and Monique Teillaud. “Generalizing CGAL Periodic Delaunay Triangulations.” In 28th Annual European Symposium on Algorithms, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.ESA.2020.75.","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."},"project":[{"_id":"266A2E9E-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Alpha Shape Theory Extended","grant_number":"788183"}],"article_number":"75","volume":173,"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"9056"}]},"ec_funded":1,"file":[{"date_updated":"2020-10-27T14:31:52Z","file_size":733291,"creator":"cziletti","date_created":"2020-10-27T14:31:52Z","file_name":"2020_LIPIcs_Osang.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"fe0f7c49a99ed870c671b911e10d5496","file_id":"8712","success":1}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["18688969"],"isbn":["9783959771627"]},"publication_status":"published","month":"08","intvolume":" 173","scopus_import":"1","alternative_title":["LIPIcs"],"oa_version":"Published Version","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"}],"department":[{"_id":"HeEd"}],"file_date_updated":"2020-10-27T14:31:52Z","ddc":["000"],"date_updated":"2023-09-07T13:29:00Z","status":"public","type":"conference","tmp":{"short":"CC BY (3.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"conference":{"location":"Virtual, Online; Pisa, Italy","end_date":"2020-09-09","start_date":"2020-09-07","name":"ESA: Annual European Symposium on Algorithms"},"_id":"8703"},{"oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how "simple" or "thin" 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))."}],"month":"06","intvolume":" 99","alternative_title":["LIPIcs"],"scopus_import":1,"file":[{"date_updated":"2020-07-14T12:45:51Z","file_size":642522,"creator":"dernst","date_created":"2018-12-17T15:32:38Z","file_name":"2018_LIPIcs_Huszar.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"530d084116778135d5bffaa317479cac","file_id":"5713"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["18688969"]},"publication_status":"published","volume":99,"related_material":{"record":[{"id":"7093","status":"public","relation":"later_version"}]},"_id":"285","status":"public","type":"conference","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)"},"conference":{"end_date":"2018-06-14","location":"Budapest, Hungary","start_date":"2018-06-11","name":"SoCG: Symposium on Computational Geometry"},"ddc":["516","000"],"date_updated":"2023-09-06T11:13:41Z","file_date_updated":"2020-07-14T12:45:51Z","department":[{"_id":"UlWa"}],"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).","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"day":"01","has_accepted_license":"1","year":"2018","doi":"10.4230/LIPIcs.SoCG.2018.46","date_published":"2018-06-01T00:00:00Z","date_created":"2018-12-11T11:45:37Z","article_number":"46","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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. https://doi.org/10.4230/LIPIcs.SoCG.2018.46.","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. On the Treewidth of Triangulated 3-Manifolds. Vol. 99, 46, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPIcs.SoCG.2018.46.","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.","apa":"Huszár, K., Spreer, J., & 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. https://doi.org/10.4230/LIPIcs.SoCG.2018.46","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:10.4230/LIPIcs.SoCG.2018.46"},"title":"On the treewidth of triangulated 3-manifolds","publist_id":"7614","author":[{"last_name":"Huszár","orcid":"0000-0002-5445-5057","full_name":"Huszár, Kristóf","first_name":"Kristóf","id":"33C26278-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Spreer, Jonathan","last_name":"Spreer","first_name":"Jonathan"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner"}],"external_id":{"arxiv":["1712.00434"]},"article_processing_charge":"No"},{"month":"08","intvolume":" 118","alternative_title":["LIPIcs"],"scopus_import":1,"oa_version":"Published Version","abstract":[{"lang":"eng","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."}],"volume":118,"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"6426"},{"id":"8332","status":"public","relation":"dissertation_contains"}]},"file":[{"checksum":"c90895f4c5fafc18ddc54d1c8848077e","file_id":"5368","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_name":"IST-2018-853-v2+2_concur2018.pdf","date_created":"2018-12-12T10:18:46Z","file_size":745438,"date_updated":"2020-07-14T12:44:44Z","creator":"system"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["18688969"]},"publication_status":"published","status":"public","pubrep_id":"1039","type":"conference","conference":{"start_date":"2018-09-04","end_date":"2018-09-07","location":"Beijing, China","name":"CONCUR: International Conference on Concurrency Theory"},"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)"},"_id":"133","department":[{"_id":"ToHe"}],"file_date_updated":"2020-07-14T12:44:44Z","ddc":["000"],"date_updated":"2023-09-07T13:18:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","oa":1,"doi":"10.4230/LIPIcs.CONCUR.2018.21","date_published":"2018-08-13T00:00:00Z","date_created":"2018-12-11T11:44:48Z","day":"13","has_accepted_license":"1","year":"2018","project":[{"_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S11402-N23"},{"_id":"25F5A88A-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11402-N23","name":"Moderne Concurrency Paradigms"}],"article_number":"21","title":"Synchronizing the asynchronous","publist_id":"7790","author":[{"id":"320FC952-F248-11E8-B48F-1D18A9856A87","first_name":"Bernhard","full_name":"Kragl, Bernhard","orcid":"0000-0001-7745-9117","last_name":"Kragl"},{"full_name":"Qadeer, Shaz","last_name":"Qadeer","first_name":"Shaz"},{"orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Kragl B, Qadeer S, Henzinger TA. 2018. Synchronizing the asynchronous. CONCUR: International Conference on Concurrency Theory, LIPIcs, vol. 118, 21.","chicago":"Kragl, Bernhard, Shaz Qadeer, and Thomas A Henzinger. “Synchronizing the Asynchronous,” Vol. 118. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.CONCUR.2018.21.","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.","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:10.4230/LIPIcs.CONCUR.2018.21","apa":"Kragl, B., Qadeer, S., & 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. https://doi.org/10.4230/LIPIcs.CONCUR.2018.21","mla":"Kragl, Bernhard, et al. Synchronizing the Asynchronous. Vol. 118, 21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPIcs.CONCUR.2018.21."}},{"author":[{"first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","last_name":"Alwen"},{"first_name":"Susanna","last_name":"De Rezende","full_name":"De Rezende, Susanna"},{"first_name":"Jakob","last_name":"Nordstrom","full_name":"Nordstrom, Jakob"},{"last_name":"Vinyals","full_name":"Vinyals, Marc","first_name":"Marc"}],"publist_id":"6179","title":"Cumulative space in black-white pebbling and resolution","editor":[{"last_name":"Papadimitriou","full_name":"Papadimitriou, Christos","first_name":"Christos"}],"citation":{"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:10.4230/LIPIcs.ITCS.2017.38","apa":"Alwen, J. F., De Rezende, S., Nordstrom, J., & 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. https://doi.org/10.4230/LIPIcs.ITCS.2017.38","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.","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.","mla":"Alwen, Joel F., et al. Cumulative Space in Black-White Pebbling and Resolution. Edited by Christos Papadimitriou, vol. 67, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 38:1-38-21, doi:10.4230/LIPIcs.ITCS.2017.38.","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.","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. https://doi.org/10.4230/LIPIcs.ITCS.2017.38."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","oa":1,"page":"38:1-38-21","date_published":"2017-01-01T00:00:00Z","doi":"10.4230/LIPIcs.ITCS.2017.38","date_created":"2018-12-11T11:50:33Z","has_accepted_license":"1","year":"2017","day":"01","type":"conference","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)"},"conference":{"location":"Berkeley, CA, United States","end_date":"2017-01-11","start_date":"2017-01-09","name":"ITCS: Innovations in Theoretical Computer Science"},"status":"public","pubrep_id":"927","_id":"1175","file_date_updated":"2020-07-14T12:44:37Z","department":[{"_id":"KrPi"}],"date_updated":"2021-01-12T06:48:51Z","ddc":["005","600"],"alternative_title":["LIPIcs"],"scopus_import":1,"month":"01","intvolume":" 67","abstract":[{"lang":"eng","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."}],"oa_version":"Published Version","volume":67,"publication_identifier":{"issn":["18688969"]},"publication_status":"published","file":[{"file_name":"IST-2018-927-v1+1_LIPIcs-ITCS-2017-38.pdf","date_created":"2018-12-12T10:17:11Z","creator":"system","file_size":557769,"date_updated":"2020-07-14T12:44:37Z","checksum":"dbc94810be07c2fb1945d5c2a6130e6c","file_id":"5263","relation":"main_file","access_level":"open_access","content_type":"application/pdf"}],"language":[{"iso":"eng"}]},{"status":"public","pubrep_id":"895","type":"conference","conference":{"name":"Symposium on Computational Geometry, SoCG","start_date":"2017-07-04","end_date":"2017-07-07","location":"Brisbane, Australia"},"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)"},"_id":"688","department":[{"_id":"HeEd"},{"_id":"UlWa"}],"file_date_updated":"2020-07-14T12:47:42Z","ddc":["514","516"],"date_updated":"2021-01-12T08:09:26Z","month":"06","intvolume":" 77","alternative_title":["LIPIcs"],"scopus_import":1,"oa_version":"Published Version","abstract":[{"text":"We show that the framework of topological data analysis can be extended from metrics to general Bregman divergences, widening the scope of possible applications. Examples are the Kullback - Leibler divergence, which is commonly used for comparing text and images, and the Itakura - Saito divergence, popular for speech and sound. In particular, we prove that appropriately generalized čech and Delaunay (alpha) complexes capture the correct homotopy type, namely that of the corresponding union of Bregman balls. Consequently, their filtrations give the correct persistence diagram, namely the one generated by the uniformly growing Bregman balls. Moreover, we show that unlike the metric setting, the filtration of Vietoris-Rips complexes may fail to approximate the persistence diagram. We propose algorithms to compute the thus generalized čech, Vietoris-Rips and Delaunay complexes and experimentally test their efficiency. Lastly, we explain their surprisingly good performance by making a connection with discrete Morse theory. ","lang":"eng"}],"volume":77,"file":[{"checksum":"067ab0cb3f962bae6c3af6bf0094e0f3","file_id":"4856","access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2018-12-12T10:11:03Z","file_name":"IST-2017-895-v1+1_LIPIcs-SoCG-2017-39.pdf","creator":"system","date_updated":"2020-07-14T12:47:42Z","file_size":990546}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["18688969"]},"publication_status":"published","title":"Topological data analysis with Bregman divergences","publist_id":"7021","author":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"id":"379CA8B8-F248-11E8-B48F-1D18A9856A87","first_name":"Hubert","last_name":"Wagner","full_name":"Wagner, Hubert"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Edelsbrunner H, Wagner H. 2017. Topological data analysis with Bregman divergences. Symposium on Computational Geometry, SoCG, LIPIcs, vol. 77, 391–3916.","chicago":"Edelsbrunner, Herbert, and Hubert Wagner. “Topological Data Analysis with Bregman Divergences,” 77:391–3916. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.SoCG.2017.39.","apa":"Edelsbrunner, H., & Wagner, H. (2017). Topological data analysis with Bregman divergences (Vol. 77, pp. 391–3916). Presented at the Symposium on Computational Geometry, SoCG, Brisbane, Australia: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2017.39","ama":"Edelsbrunner H, Wagner H. Topological data analysis with Bregman divergences. In: Vol 77. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017:391-3916. doi:10.4230/LIPIcs.SoCG.2017.39","ieee":"H. Edelsbrunner and H. Wagner, “Topological data analysis with Bregman divergences,” presented at the Symposium on Computational Geometry, SoCG, Brisbane, Australia, 2017, vol. 77, pp. 391–3916.","short":"H. Edelsbrunner, H. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 391–3916.","mla":"Edelsbrunner, Herbert, and Hubert Wagner. Topological Data Analysis with Bregman Divergences. Vol. 77, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 391–3916, doi:10.4230/LIPIcs.SoCG.2017.39."},"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"doi":"10.4230/LIPIcs.SoCG.2017.39","date_published":"2017-06-01T00:00:00Z","date_created":"2018-12-11T11:47:56Z","page":"391-3916","day":"01","has_accepted_license":"1","year":"2017"},{"title":"Non uniform attacks against pseudoentropy","author":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"},{"full_name":"Skórski, Maciej","last_name":"Skórski","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","first_name":"Maciej"}],"publist_id":"7003","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"apa":"Pietrzak, K. Z., & Skórski, M. (2017). Non uniform attacks against pseudoentropy (Vol. 80). Presented at the ICALP: International Colloquium on Automata, Languages, and Programming, Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2017.39","ama":"Pietrzak KZ, Skórski M. Non uniform attacks against pseudoentropy. In: Vol 80. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.ICALP.2017.39","ieee":"K. Z. Pietrzak and M. Skórski, “Non uniform attacks against pseudoentropy,” presented at the ICALP: International Colloquium on Automata, Languages, and Programming, Warsaw, Poland, 2017, vol. 80.","short":"K.Z. Pietrzak, M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Pietrzak, Krzysztof Z., and Maciej Skórski. Non Uniform Attacks against Pseudoentropy. Vol. 80, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.ICALP.2017.39.","ista":"Pietrzak KZ, Skórski M. 2017. Non uniform attacks against pseudoentropy. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 80, 39.","chicago":"Pietrzak, Krzysztof Z, and Maciej Skórski. “Non Uniform Attacks against Pseudoentropy,” Vol. 80. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.ICALP.2017.39."},"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"article_number":"39","date_published":"2017-07-01T00:00:00Z","doi":"10.4230/LIPIcs.ICALP.2017.39","date_created":"2018-12-11T11:47:59Z","day":"01","has_accepted_license":"1","year":"2017","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","oa":1,"department":[{"_id":"KrPi"}],"file_date_updated":"2020-07-14T12:47:46Z","ddc":["005"],"date_updated":"2021-01-12T08:11:15Z","status":"public","pubrep_id":"893","type":"conference","conference":{"start_date":"2017-07-10","location":"Warsaw, Poland","end_date":"2017-07-14","name":"ICALP: International Colloquium on Automata, Languages, and Programming"},"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)"},"_id":"697","volume":80,"ec_funded":1,"file":[{"checksum":"e95618a001692f1af2d68f5fde43bc1f","file_id":"4701","access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2018-12-12T10:08:40Z","file_name":"IST-2017-893-v1+1_LIPIcs-ICALP-2017-39.pdf","creator":"system","date_updated":"2020-07-14T12:47:46Z","file_size":601004}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["18688969"]},"publication_status":"published","month":"07","intvolume":" 80","alternative_title":["LIPIcs"],"scopus_import":1,"oa_version":"Published Version","abstract":[{"text":"De, Trevisan and Tulsiani [CRYPTO 2010] show that every distribution over n-bit strings which has constant statistical distance to uniform (e.g., the output of a pseudorandom generator mapping n-1 to n bit strings), can be distinguished from the uniform distribution with advantage epsilon by a circuit of size O( 2^n epsilon^2). We generalize this result, showing that a distribution which has less than k bits of min-entropy, can be distinguished from any distribution with k bits of delta-smooth min-entropy with advantage epsilon by a circuit of size O(2^k epsilon^2/delta^2). As a special case, this implies that any distribution with support at most 2^k (e.g., the output of a pseudoentropy generator mapping k to n bit strings) can be distinguished from any given distribution with min-entropy k+1 with advantage epsilon by a circuit of size O(2^k epsilon^2). Our result thus shows that pseudoentropy distributions face basically the same non-uniform attacks as pseudorandom distributions. ","lang":"eng"}]},{"date_updated":"2021-01-12T08:11:50Z","ddc":["005","600"],"department":[{"_id":"KrPi"}],"file_date_updated":"2020-07-14T12:47:49Z","_id":"710","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)"},"conference":{"name":"20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX","end_date":"2017-08-18","location":"Berkeley, USA","start_date":"2017-08-18"},"type":"conference","pubrep_id":"888","status":"public","publication_status":"published","publication_identifier":{"issn":["18688969"]},"language":[{"iso":"eng"}],"file":[{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_id":"4991","checksum":"89225c7dcec2c93838458c9102858985","creator":"system","file_size":604813,"date_updated":"2020-07-14T12:47:49Z","file_name":"IST-2017-888-v1+1_LIPIcs-APPROX-RANDOM-2017-20.pdf","date_created":"2018-12-12T10:13:10Z"}],"ec_funded":1,"volume":81,"abstract":[{"lang":"eng","text":"We revisit the problem of estimating entropy of discrete distributions from independent samples, studied recently by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015), improving their upper and lower bounds on the necessary sample size n. For estimating Renyi entropy of order alpha, up to constant accuracy and error probability, we show the following * Upper bounds n = O(1) 2^{(1-1/alpha)H_alpha} for integer alpha>1, as the worst case over distributions with Renyi entropy equal to H_alpha. * Lower bounds n = Omega(1) K^{1-1/alpha} for any real alpha>1, with the constant being an inverse polynomial of the accuracy, as the worst case over all distributions on K elements. Our upper bounds essentially replace the alphabet size by a factor exponential in the entropy, which offers improvements especially in low or medium entropy regimes (interesting for example in anomaly detection). As for the lower bounds, our proof explicitly shows how the complexity depends on both alphabet and accuracy, partially solving the open problem posted in previous works. The argument for upper bounds derives a clean identity for the variance of falling-power sum of a multinomial distribution. Our approach for lower bounds utilizes convex optimization to find a distribution with possibly worse estimation performance, and may be of independent interest as a tool to work with Le Cam’s two point method. "}],"oa_version":"Published Version","alternative_title":["LIPIcs"],"scopus_import":1,"intvolume":" 81","month":"08","citation":{"mla":"Obremski, Maciej, and Maciej Skórski. Renyi Entropy Estimation Revisited. Vol. 81, 20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.APPROX-RANDOM.2017.20.","ieee":"M. Obremski and M. Skórski, “Renyi entropy estimation revisited,” presented at the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, Berkeley, USA, 2017, vol. 81.","short":"M. Obremski, M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ama":"Obremski M, Skórski M. Renyi entropy estimation revisited. In: Vol 81. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.APPROX-RANDOM.2017.20","apa":"Obremski, M., & Skórski, M. (2017). Renyi entropy estimation revisited (Vol. 81). Presented at the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, Berkeley, USA: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20","chicago":"Obremski, Maciej, and Maciej Skórski. “Renyi Entropy Estimation Revisited,” Vol. 81. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20.","ista":"Obremski M, Skórski M. 2017. Renyi entropy estimation revisited. 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, LIPIcs, vol. 81, 20."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publist_id":"6979","author":[{"first_name":"Maciej","full_name":"Obremski, Maciej","last_name":"Obremski"},{"id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","first_name":"Maciej","full_name":"Skórski, Maciej","last_name":"Skórski"}],"title":"Renyi entropy estimation revisited","article_number":"20","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"year":"2017","has_accepted_license":"1","day":"01","date_created":"2018-12-11T11:48:04Z","doi":"10.4230/LIPIcs.APPROX-RANDOM.2017.20","date_published":"2017-08-01T00:00:00Z","oa":1,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik"},{"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","oa":1,"doi":"10.4230/LIPIcs.CONCUR.2017.5","date_published":"2017-08-01T00:00:00Z","date_created":"2018-12-11T11:48:04Z","day":"01","has_accepted_license":"1","year":"2017","article_number":"5","title":"Bidirectional nested weighted automata","publist_id":"6976","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Otop","full_name":"Otop, Jan","first_name":"Jan"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ama":"Chatterjee K, Henzinger TA, Otop J. Bidirectional nested weighted automata. In: Vol 85. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.CONCUR.2017.5","apa":"Chatterjee, K., Henzinger, T. A., & Otop, J. (2017). Bidirectional nested weighted automata (Vol. 85). Presented at the 28th International Conference on Concurrency Theory, CONCUR, Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2017.5","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, “Bidirectional nested weighted automata,” presented at the 28th International Conference on Concurrency Theory, CONCUR, Berlin, Germany, 2017, vol. 85.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Chatterjee, Krishnendu, et al. Bidirectional Nested Weighted Automata. Vol. 85, 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.CONCUR.2017.5.","ista":"Chatterjee K, Henzinger TA, Otop J. 2017. Bidirectional nested weighted automata. 28th International Conference on Concurrency Theory, CONCUR, LIPIcs, vol. 85, 5.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Bidirectional Nested Weighted Automata,” Vol. 85. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.CONCUR.2017.5."},"month":"08","intvolume":" 85","alternative_title":["LIPIcs"],"scopus_import":1,"oa_version":"Published Version","abstract":[{"lang":"eng","text":"Nested weighted automata (NWA) present a robust and convenient automata-theoretic formalism for quantitative specifications. Previous works have considered NWA that processed input words only in the forward direction. It is natural to allow the automata to process input words backwards as well, for example, to measure the maximal or average time between a response and the preceding request. We therefore introduce and study bidirectional NWA that can process input words in both directions. First, we show that bidirectional NWA can express interesting quantitative properties that are not expressible by forward-only NWA. Second, for the fundamental decision problems of emptiness and universality, we establish decidability and complexity results for the new framework which match the best-known results for the special case of forward-only NWA. Thus, for NWA, the increased expressiveness of bidirectionality is achieved at no additional computational complexity. This is in stark contrast to the unweighted case, where bidirectional finite automata are no more expressive but exponentially more succinct than their forward-only counterparts."}],"volume":85,"file":[{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"d2bda4783821a6358333fe27f11f4737","file_id":"4661","date_updated":"2020-07-14T12:47:49Z","file_size":570294,"creator":"system","date_created":"2018-12-12T10:08:02Z","file_name":"IST-2017-886-v1+1_LIPIcs-CONCUR-2017-5.pdf"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["18688969"]},"publication_status":"published","status":"public","pubrep_id":"886","type":"conference","conference":{"name":"28th International Conference on Concurrency Theory, CONCUR","end_date":"2017-09-08","location":"Berlin, Germany","start_date":"2017-09-05"},"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)"},"_id":"711","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"file_date_updated":"2020-07-14T12:47:49Z","ddc":["004","005"],"date_updated":"2021-01-12T08:11:53Z"},{"scopus_import":1,"alternative_title":["LIPIcs"],"month":"06","intvolume":" 83","abstract":[{"lang":"eng","text":"Network games are widely used as a model for selfish resource-allocation problems. In the classical model, each player selects a path connecting her source and target vertex. The cost of traversing an edge depends on the number of players that traverse it. Thus, it abstracts the fact that different users may use a resource at different times and for different durations, which plays an important role in defining the costs of the users in reality. For example, when transmitting packets in a communication network, routing traffic in a road network, or processing a task in a production system, the traversal of the network involves an inherent delay, and so sharing and congestion of resources crucially depends on time. We study timed network games , which add a time component to network games. Each vertex v in the network is associated with a cost function, mapping the load on v to the price that a player pays for staying in v for one time unit with this load. In addition, each edge has a guard, describing time intervals in which the edge can be traversed, forcing the players to spend time on vertices. Unlike earlier work that add a time component to network games, the time in our model is continuous and cannot be discretized. In particular, players have uncountably many strategies, and a game may have uncountably many pure Nash equilibria. We study properties of timed network games with cost-sharing or congestion cost functions: their stability, equilibrium inefficiency, and complexity. In particular, we show that the answer to the question whether we can restrict attention to boundary strategies, namely ones in which edges are traversed only at the boundaries of guards, is mixed. "}],"oa_version":"Published Version","related_material":{"record":[{"relation":"later_version","status":"public","id":"6005"}]},"volume":83,"publication_identifier":{"issn":["18688969"]},"publication_status":"published","file":[{"date_created":"2018-12-12T10:14:10Z","file_name":"IST-2017-829-v1+1_mfcs-cr.pdf","date_updated":"2020-07-14T12:48:18Z","file_size":369730,"creator":"system","file_id":"5059","checksum":"f55eaf7f3c36ea07801112acfedd17d5","content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"language":[{"iso":"eng"}],"type":"conference","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)"},"conference":{"name":"MFCS: Mathematical Foundations of Computer Science (SG)","start_date":"2017-08-21","location":"Aalborg, Denmark","end_date":"2017-08-25"},"status":"public","pubrep_id":"829","_id":"963","file_date_updated":"2020-07-14T12:48:18Z","department":[{"_id":"ToHe"}],"date_updated":"2023-02-23T12:35:50Z","ddc":["004"],"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"doi":"10.4230/LIPIcs.MFCS.2017.37","date_published":"2017-06-01T00:00:00Z","date_created":"2018-12-11T11:49:26Z","has_accepted_license":"1","year":"2017","day":"01","project":[{"_id":"25F5A88A-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Moderne Concurrency Paradigms","grant_number":"S11402-N23"}],"article_number":"37","author":[{"first_name":"Guy","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","last_name":"Avni","full_name":"Avni, Guy","orcid":"0000-0001-5588-8287"},{"last_name":"Guha","full_name":"Guha, Shibashis","first_name":"Shibashis"},{"full_name":"Kupferman, Orna","last_name":"Kupferman","first_name":"Orna"}],"publist_id":"6438","title":"Timed network games with clocks","citation":{"ama":"Avni G, Guha S, Kupferman O. Timed network games with clocks. In: Vol 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.MFCS.2017.37","apa":"Avni, G., Guha, S., & Kupferman, O. (2017). Timed network games with clocks (Vol. 83). Presented at the MFCS: Mathematical Foundations of Computer Science (SG), Aalborg, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2017.37","short":"G. Avni, S. Guha, O. Kupferman, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ieee":"G. Avni, S. Guha, and O. Kupferman, “Timed network games with clocks,” presented at the MFCS: Mathematical Foundations of Computer Science (SG), Aalborg, Denmark, 2017, vol. 83.","mla":"Avni, Guy, et al. Timed Network Games with Clocks. Vol. 83, 37, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.MFCS.2017.37.","ista":"Avni G, Guha S, Kupferman O. 2017. Timed network games with clocks. MFCS: Mathematical Foundations of Computer Science (SG), LIPIcs, vol. 83, 37.","chicago":"Avni, Guy, Shibashis Guha, and Orna Kupferman. “Timed Network Games with Clocks,” Vol. 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.MFCS.2017.37."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"title":"Lower bounds on key derivation for square-friendly applications","author":[{"last_name":"Skórski","full_name":"Skórski, Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","first_name":"Maciej"}],"publist_id":"6180","article_processing_charge":"No","external_id":{"isi":["000521077300057"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"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.","chicago":"Skórski, Maciej. “Lower Bounds on Key Derivation for Square-Friendly Applications,” Vol. 66. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.STACS.2017.57.","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.","short":"M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","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:10.4230/LIPIcs.STACS.2017.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. https://doi.org/10.4230/LIPIcs.STACS.2017.57","mla":"Skórski, Maciej. Lower Bounds on Key Derivation for Square-Friendly Applications. Vol. 66, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.STACS.2017.57."},"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"article_number":"57","doi":"10.4230/LIPIcs.STACS.2017.57","date_published":"2017-03-01T00:00:00Z","date_created":"2018-12-11T11:50:32Z","day":"01","isi":1,"year":"2017","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"department":[{"_id":"KrPi"}],"date_updated":"2023-09-20T11:23:15Z","status":"public","type":"conference","conference":{"name":"STACS: Symposium on Theoretical Aspects of Computer Science","end_date":"2017-03-11","location":"Hannover, Germany","start_date":"2017-03-08"},"_id":"1174","volume":66,"ec_funded":1,"language":[{"iso":"eng"}],"publication_identifier":{"issn":["18688969"]},"publication_status":"published","month":"03","intvolume":" 66","scopus_import":"1","alternative_title":["LIPIcs"],"main_file_link":[{"open_access":"1","url":"http://drops.dagstuhl.de/opus/volltexte/2017/6976"}],"oa_version":"Submitted Version","abstract":[{"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 "RT-bound", extracting secure keys with significantly smaller entropy loss. In turn Dodis and Yu showed that in squared-friendly applications one can directly use a "weak" key, which has only high entropy, as a secure key. In this paper we give sharp lower bounds on square security assuming security for "weak" 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.","lang":"eng"}]}]