[{"day":"26","file":[{"date_created":"2018-12-12T11:53:22Z","file_name":"IST-2017-724-v1+1_DataRep_Project_Report_2017.pdf","date_updated":"2020-07-14T12:46:59Z","file_size":3460985,"creator":"system","file_id":"5483","checksum":"6321792dcfa82bf490f17615a9b22355","content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"year":"2017","date_published":"2017-06-26T00:00:00Z","date_created":"2018-12-12T11:39:24Z","publication_date":"2017-06-26","abstract":[{"text":"In this report the implementation of the institutional data repository IST DataRep at IST Austria will be covered: Starting with the research phase when requirements for a repository were established, the procedure of choosing a repository-software and its customization based on the results of user-testings will be discussed. Followed by reflections on the marketing strategies in regard of impact, and at the end sharing some experiences of one year operating IST DataRep.","lang":"eng"}],"month":"06","publisher":"IST Austria","oa":1,"main_file_link":[{"url":"https://repository.ist.ac.at/id/eprint/724.","open_access":"1"}],"extern":0,"citation":{"mla":"Petritsch, Barbara. Implementing the Institutional Data Repository IST DataRep. IST Austria, 2017.","apa":"Petritsch, B. (2017). Implementing the institutional data repository IST DataRep. IST Austria.","ama":"Petritsch B. Implementing the Institutional Data Repository IST DataRep. IST Austria; 2017.","short":"B. Petritsch, Implementing the Institutional Data Repository IST DataRep, IST Austria, 2017.","ieee":"B. Petritsch, Implementing the institutional data repository IST DataRep. IST Austria, 2017.","chicago":"Petritsch, Barbara. Implementing the Institutional Data Repository IST DataRep. IST Austria, 2017.","ista":"Petritsch B. 2017. Implementing the institutional data repository IST DataRep, IST Austria,p."},"date_updated":"2020-07-14T23:05:03Z","file_date_updated":"2020-07-14T12:46:59Z","title":"Implementing the institutional data repository IST DataRep","department":[{"_id":"E-Lib"}],"author":[{"first_name":"Barbara","id":"406048EC-F248-11E8-B48F-1D18A9856A87","last_name":"Petritsch","full_name":"Barbara Petritsch","orcid":"0000-0003-2724-4614"}],"_id":"5450","status":"public","pubrep_id":"724","type":"report"},{"oa_version":"Published Version","abstract":[{"text":"We present a new dynamic partial-order reduction method for stateless model checking of concurrent programs. A common approach for exploring program behaviors relies on enumerating the traces of the program, without storing the visited states (aka stateless exploration). As the number of distinct traces grows exponentially, dynamic partial-order reduction (DPOR) techniques have been successfully used to partition the space of traces into equivalence classes (Mazurkiewicz partitioning), with the goal of exploring only few representative traces from each class.\r\n\r\nWe introduce a new equivalence on traces under sequential consistency semantics, which we call the observation equivalence. Two traces are observationally equivalent if every read event observes the same write event in both traces. While the traditional Mazurkiewicz equivalence is control-centric, our new definition is data-centric. We show that our observation equivalence is coarser than the Mazurkiewicz equivalence, and in many cases even exponentially coarser. We devise a DPOR exploration of the trace space, called data-centric DPOR, based on the observation equivalence.","lang":"eng"}],"month":"12","intvolume":" 2","scopus_import":"1","main_file_link":[{"url":"https://dl.acm.org/doi/10.1145/3158119","open_access":"1"}],"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["2475-1421"]},"publication_status":"published","issue":"POPL","related_material":{"record":[{"status":"public","id":"5448","relation":"earlier_version"},{"id":"5456","status":"public","relation":"earlier_version"}]},"volume":2,"ec_funded":1,"_id":"10417","status":"public","type":"journal_article","article_type":"original","conference":{"start_date":"2018-01-07","location":"Los Angeles, CA, United States","end_date":"2018-01-13","name":"POPL: Programming Languages"},"date_updated":"2023-02-23T12:27:16Z","department":[{"_id":"KrCh"}],"acknowledgement":"The research was partly supported by Austrian Science Fund (FWF) Grant No P23499- N23, FWF\r\nNFN Grant No S11407-N23 (RiSE/SHiNE), ERC Start grant (279307: Graph Games), and Czech\r\nScience Foundation grant GBP202/12/G061.","publisher":"Association for Computing Machinery","quality_controlled":"1","oa":1,"day":"27","publication":"Proceedings of the ACM on Programming Languages","year":"2017","date_published":"2017-12-27T00:00:00Z","doi":"10.1145/3158119","date_created":"2021-12-05T23:01:49Z","article_number":"31","project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","citation":{"mla":"Chalupa, Marek, et al. “Data-Centric Dynamic Partial Order Reduction.” Proceedings of the ACM on Programming Languages, vol. 2, no. POPL, 31, Association for Computing Machinery, 2017, doi:10.1145/3158119.","apa":"Chalupa, M., Chatterjee, K., Pavlogiannis, A., Sinha, N., & Vaidya, K. (2017). Data-centric dynamic partial order reduction. Proceedings of the ACM on Programming Languages. Los Angeles, CA, United States: Association for Computing Machinery. https://doi.org/10.1145/3158119","ama":"Chalupa M, Chatterjee K, Pavlogiannis A, Sinha N, Vaidya K. Data-centric dynamic partial order reduction. Proceedings of the ACM on Programming Languages. 2017;2(POPL). doi:10.1145/3158119","ieee":"M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, and K. Vaidya, “Data-centric dynamic partial order reduction,” Proceedings of the ACM on Programming Languages, vol. 2, no. POPL. Association for Computing Machinery, 2017.","short":"M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, K. Vaidya, Proceedings of the ACM on Programming Languages 2 (2017).","chicago":"Chalupa, Marek, Krishnendu Chatterjee, Andreas Pavlogiannis, Nishant Sinha, and Kapil Vaidya. “Data-Centric Dynamic Partial Order Reduction.” Proceedings of the ACM on Programming Languages. Association for Computing Machinery, 2017. https://doi.org/10.1145/3158119.","ista":"Chalupa M, Chatterjee K, Pavlogiannis A, Sinha N, Vaidya K. 2017. Data-centric dynamic partial order reduction. Proceedings of the ACM on Programming Languages. 2(POPL), 31."},"title":"Data-centric dynamic partial order reduction","author":[{"full_name":"Chalupa, Marek","last_name":"Chalupa","first_name":"Marek"},{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722"},{"last_name":"Sinha","full_name":"Sinha, Nishant","first_name":"Nishant"},{"full_name":"Vaidya, Kapil","last_name":"Vaidya","first_name":"Kapil"}],"external_id":{"arxiv":["1610.01188"]},"article_processing_charge":"No"},{"page":"36","doi":"10.15479/AT:IST-2017-872-v1-1","related_material":{"record":[{"id":"10417","status":"public","relation":"later_version"},{"status":"public","id":"5448","relation":"earlier_version"}]},"date_published":"2017-10-23T00:00:00Z","date_created":"2018-12-12T11:39:26Z","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"year":"2017","publication_status":"published","file":[{"date_created":"2018-12-12T11:53:26Z","file_name":"IST-2017-872-v1+1_main.pdf","creator":"system","date_updated":"2020-07-14T12:46:59Z","file_size":910347,"checksum":"d2635c4cf013000f0a1b09e80f9e4ab7","file_id":"5487","access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"day":"23","language":[{"iso":"eng"}],"publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"oa":1,"month":"10","abstract":[{"text":"We present a new dynamic partial-order reduction method for stateless model checking of concurrent programs. A common approach for exploring program behaviors relies on enumerating the traces of the program, without storing the visited states (aka stateless exploration). As the number of distinct traces grows exponentially, dynamic partial-order reduction (DPOR) techniques have been successfully used to partition the space of traces into equivalence classes (Mazurkiewicz partitioning), with the goal of exploring only few representative traces from each class.\r\nWe introduce a new equivalence on traces under sequential consistency semantics, which we call the observation equivalence. Two traces are observationally equivalent if every read event observes the same write event in both traces. While the traditional Mazurkiewicz equivalence is control-centric, our new definition is data-centric. We show that our observation equivalence is coarser than the Mazurkiewicz equivalence, and in many cases even exponentially coarser. We devise a DPOR exploration of the trace space, called data-centric DPOR, based on the observation equivalence.\r\n1. For acyclic architectures, our algorithm is guaranteed to explore exactly one representative trace from each observation class, while spending polynomial time per class. Hence, our algorithm is optimal wrt the observation equivalence, and in several cases explores exponentially fewer traces than any enumerative method based on the Mazurkiewicz equivalence.\r\n2. For cyclic architectures, we consider an equivalence between traces which is finer than the observation equivalence; but coarser than the Mazurkiewicz equivalence, and in some cases is exponentially coarser. Our data-centric DPOR algorithm remains optimal under this trace equivalence. \r\nFinally, we perform a basic experimental comparison between the existing Mazurkiewicz-based DPOR and our data-centric DPOR on a set of academic benchmarks. Our results show a significant reduction in both running time and the number of explored equivalence classes.","lang":"eng"}],"oa_version":"Published Version","author":[{"first_name":"Marek","last_name":"Chalupa","full_name":"Chalupa, Marek"},{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas"},{"last_name":"Sinha","full_name":"Sinha, Nishant","first_name":"Nishant"},{"last_name":"Vaidya","full_name":"Vaidya, Kapil","first_name":"Kapil"}],"file_date_updated":"2020-07-14T12:46:59Z","department":[{"_id":"KrCh"}],"title":"Data-centric dynamic partial order reduction","citation":{"ista":"Chalupa M, Chatterjee K, Pavlogiannis A, Sinha N, Vaidya K. 2017. Data-centric dynamic partial order reduction, IST Austria, 36p.","chicago":"Chalupa, Marek, Krishnendu Chatterjee, Andreas Pavlogiannis, Nishant Sinha, and Kapil Vaidya. Data-Centric Dynamic Partial Order Reduction. IST Austria, 2017. https://doi.org/10.15479/AT:IST-2017-872-v1-1.","ieee":"M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, and K. Vaidya, Data-centric dynamic partial order reduction. IST Austria, 2017.","short":"M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, K. Vaidya, Data-Centric Dynamic Partial Order Reduction, IST Austria, 2017.","apa":"Chalupa, M., Chatterjee, K., Pavlogiannis, A., Sinha, N., & Vaidya, K. (2017). Data-centric dynamic partial order reduction. IST Austria. https://doi.org/10.15479/AT:IST-2017-872-v1-1","ama":"Chalupa M, Chatterjee K, Pavlogiannis A, Sinha N, Vaidya K. Data-Centric Dynamic Partial Order Reduction. IST Austria; 2017. doi:10.15479/AT:IST-2017-872-v1-1","mla":"Chalupa, Marek, et al. Data-Centric Dynamic Partial Order Reduction. IST Austria, 2017, doi:10.15479/AT:IST-2017-872-v1-1."},"date_updated":"2023-02-23T12:26:54Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"type":"technical_report","status":"public","pubrep_id":"872","_id":"5456"},{"oa_version":"Published Version","abstract":[{"text":"Evolutionary graph theory studies the evolutionary dynamics in a population structure given as a connected graph. Each node of the graph represents an individual of the population, and edges determine how offspring are placed. We consider the classical birth-death Moran process where there are two types of individuals, namely, the residents with fitness 1 and mutants with fitness r. The fitness indicates the reproductive strength. The evolutionary dynamics happens as follows: in the initial step, in a population of all resident individuals a mutant is introduced, and then at each step, an individual is chosen proportional to the fitness of its type to reproduce, and the offspring replaces a neighbor uniformly at random. The process stops when all individuals are either residents or mutants. The probability that all individuals in the end are mutants is called the fixation probability, which is a key factor in the rate of evolution. We consider the problem of approximating the fixation probability. The class of algorithms that is extremely relevant for approximation of the fixation probabilities is the Monte-Carlo simulation of the process. Previous results present a polynomial-time Monte-Carlo algorithm for undirected graphs when r is given in unary. First, we present a simple modification: instead of simulating each step, we discard ineffective steps, where no node changes type (i.e., either residents replace residents, or mutants replace mutants). Using the above simple modification and our result that the number of effective steps is concentrated around the expected number of effective steps, we present faster polynomial-time Monte-Carlo algorithms for undirected graphs. Our algorithms are always at least a factor O(n2/ log n) faster as compared to the previous algorithms, where n is the number of nodes, and is polynomial even if r is given in binary. We also present lower bounds showing that the upper bound on the expected number of effective steps we present is asymptotically tight for undirected graphs. ","lang":"eng"}],"intvolume":" 83","month":"11","alternative_title":["LIPIcs"],"scopus_import":1,"language":[{"iso":"eng"}],"file":[{"date_created":"2018-12-12T10:18:04Z","file_name":"IST-2018-924-v1+1_LIPIcs-MFCS-2017-61.pdf","creator":"system","date_updated":"2020-07-14T12:47:00Z","file_size":535077,"file_id":"5322","checksum":"2eed5224c0e4e259484a1d71acb8ba6a","access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"publication_status":"published","publication_identifier":{"isbn":["978-395977046-0"]},"license":"https://creativecommons.org/licenses/by/4.0/","volume":83,"_id":"551","pubrep_id":"924","status":"public","conference":{"name":"MFCS: Mathematical Foundations of Computer Science (SG)","location":"Aalborg, Denmark","end_date":"2017-08-25","start_date":"2017-08-21"},"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":["004"],"date_updated":"2021-01-12T08:02:34Z","file_date_updated":"2020-07-14T12:47:00Z","department":[{"_id":"KrCh"}],"oa":1,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication":"Leibniz International Proceedings in Informatics","day":"01","year":"2017","has_accepted_license":"1","date_created":"2018-12-11T11:47:08Z","date_published":"2017-11-01T00:00:00Z","doi":"10.4230/LIPIcs.MFCS.2017.61","article_number":"61","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ama":"Chatterjee K, Ibsen-Jensen R, Nowak M. Faster Monte Carlo algorithms for fixation probability of the Moran process on undirected graphs. In: Leibniz International Proceedings in Informatics. Vol 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.MFCS.2017.61","apa":"Chatterjee, K., Ibsen-Jensen, R., & Nowak, M. (2017). Faster Monte Carlo algorithms for fixation probability of the Moran process on undirected graphs. In Leibniz International Proceedings in Informatics (Vol. 83). Aalborg, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2017.61","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, “Faster Monte Carlo algorithms for fixation probability of the Moran process on undirected graphs,” in Leibniz International Proceedings in Informatics, Aalborg, Denmark, 2017, vol. 83.","mla":"Chatterjee, Krishnendu, et al. “Faster Monte Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs.” Leibniz International Proceedings in Informatics, vol. 83, 61, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.MFCS.2017.61.","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2017. Faster Monte Carlo algorithms for fixation probability of the Moran process on undirected graphs. Leibniz International Proceedings in Informatics. MFCS: Mathematical Foundations of Computer Science (SG), LIPIcs, vol. 83, 61.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. “Faster Monte Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs.” In Leibniz International Proceedings in Informatics, Vol. 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.MFCS.2017.61."},"title":"Faster Monte Carlo algorithms for fixation probability of the Moran process on undirected graphs","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"}],"publist_id":"7263"},{"volume":83,"license":"https://creativecommons.org/licenses/by/3.0/","ec_funded":1,"publication_identifier":{"isbn":["978-395977046-0"]},"publication_status":"published","file":[{"file_name":"IST-2018-923-v1+1_LIPIcs-MFCS-2017-39.pdf","date_created":"2018-12-12T10:16:57Z","creator":"system","file_size":610339,"date_updated":"2020-07-14T12:47:00Z","checksum":"c67f4866ddbfd555afef1f63ae9a8fc7","file_id":"5248","relation":"main_file","access_level":"open_access","content_type":"application/pdf"}],"language":[{"iso":"eng"}],"scopus_import":"1","alternative_title":["LIPIcs"],"month":"11","intvolume":" 83","abstract":[{"lang":"eng","text":"Graph games provide the foundation for modeling and synthesis of reactive processes. Such games are played over graphs where the vertices are controlled by two adversarial players. We consider graph games where the objective of the first player is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a meanpayoff condition). There are two variants of the problem, namely, the threshold problem where the quantitative goal is to ensure that the mean-payoff value is above a threshold, and the value problem where the quantitative goal is to ensure the optimal mean-payoff value; in both cases ensuring the qualitative parity objective. The previous best-known algorithms for game graphs with n vertices, m edges, parity objectives with d priorities, and maximal absolute reward value W for mean-payoff objectives, are as follows: O(nd+1 . m . w) for the threshold problem, and O(nd+2 · m · W) for the value problem. Our main contributions are faster algorithms, and the running times of our algorithms are as follows: O(nd-1 · m ·W) for the threshold problem, and O(nd · m · W · log(n · W)) for the value problem. For mean-payoff parity objectives with two priorities, our algorithms match the best-known bounds of the algorithms for mean-payoff games (without conjunction with parity objectives). Our results are relevant in synthesis of reactive systems with both functional requirement (given as a qualitative objective) and performance requirement (given as a quantitative objective)."}],"oa_version":"Published Version","department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:47:00Z","date_updated":"2023-02-14T10:06:46Z","ddc":["004"],"type":"conference","conference":{"name":"MFCS: Mathematical Foundations of Computer Science (SG)","location":"Aalborg, Denmark","end_date":"2017-08-25","start_date":"2017-08-21"},"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)"},"status":"public","pubrep_id":"923","_id":"552","date_published":"2017-11-01T00:00:00Z","doi":"10.4230/LIPIcs.MFCS.2017.39","date_created":"2018-12-11T11:47:08Z","has_accepted_license":"1","year":"2017","day":"01","publication":"Leibniz International Proceedings in Informatics","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"publist_id":"7262","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"},{"full_name":"Svozil, Alexander","last_name":"Svozil","first_name":"Alexander"}],"article_processing_charge":"No","title":"Faster algorithms for mean-payoff parity games","citation":{"short":"K. Chatterjee, M.H. Henzinger, A. Svozil, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ieee":"K. Chatterjee, M. H. Henzinger, and A. Svozil, “Faster algorithms for mean-payoff parity games,” in Leibniz International Proceedings in Informatics, Aalborg, Denmark, 2017, vol. 83.","ama":"Chatterjee K, Henzinger MH, Svozil A. Faster algorithms for mean-payoff parity games. In: Leibniz International Proceedings in Informatics. Vol 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.MFCS.2017.39","apa":"Chatterjee, K., Henzinger, M. H., & Svozil, A. (2017). Faster algorithms for mean-payoff parity games. In Leibniz International Proceedings in Informatics (Vol. 83). Aalborg, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2017.39","mla":"Chatterjee, Krishnendu, et al. “Faster Algorithms for Mean-Payoff Parity Games.” Leibniz International Proceedings in Informatics, vol. 83, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.MFCS.2017.39.","ista":"Chatterjee K, Henzinger MH, Svozil A. 2017. Faster algorithms for mean-payoff parity games. Leibniz International Proceedings in Informatics. MFCS: Mathematical Foundations of Computer Science (SG), LIPIcs, vol. 83, 39.","chicago":"Chatterjee, Krishnendu, Monika H Henzinger, and Alexander Svozil. “Faster Algorithms for Mean-Payoff Parity Games.” In Leibniz International Proceedings in Informatics, Vol. 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.MFCS.2017.39."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"article_number":"39"},{"_id":"553","status":"public","pubrep_id":"922","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":"Aalborg, Denmark","end_date":"2017-08-25","start_date":"2017-08-21","name":"MFCS: Mathematical Foundations of Computer Science (SG)"},"ddc":["004"],"date_updated":"2021-01-12T08:02:35Z","department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:47:00Z","oa_version":"Published Version","abstract":[{"lang":"eng","text":"We consider two player, zero-sum, finite-state concurrent reachability games, played for an infinite number of rounds, where in every round, each player simultaneously and independently of the other players chooses an action, whereafter the successor state is determined by a probability distribution given by the current state and the chosen actions. Player 1 wins iff a designated goal state is eventually visited. We are interested in the complexity of stationary strategies measured by their patience, which is defined as the inverse of the smallest non-zero probability employed. Our main results are as follows: We show that: (i) the optimal bound on the patience of optimal and -optimal strategies, for both players is doubly exponential; and (ii) even in games with a single non-absorbing state exponential (in the number of actions) patience is necessary. "}],"month":"11","intvolume":" 83","scopus_import":1,"alternative_title":["LIPIcs"],"main_file_link":[{"url":"https://arxiv.org/abs/1506.02434","open_access":"1"}],"file":[{"file_name":"IST-2018-922-v1+1_LIPIcs-MFCS-2017-55.pdf","date_created":"2018-12-12T10:09:29Z","file_size":549967,"date_updated":"2020-07-14T12:47:00Z","creator":"system","file_id":"4753","checksum":"7101facb56ade363205c695d72dbd173","content_type":"application/pdf","relation":"main_file","access_level":"open_access"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-395977046-0"]},"publication_status":"published","volume":83,"article_number":"55","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Chatterjee K, Hansen K, Ibsen-Jensen R. 2017. Strategy complexity of concurrent safety games. Leibniz International Proceedings in Informatics. MFCS: Mathematical Foundations of Computer Science (SG), LIPIcs, vol. 83, 55.","chicago":"Chatterjee, Krishnendu, Kristofer Hansen, and Rasmus Ibsen-Jensen. “Strategy Complexity of Concurrent Safety Games.” In Leibniz International Proceedings in Informatics, Vol. 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.MFCS.2017.55.","apa":"Chatterjee, K., Hansen, K., & Ibsen-Jensen, R. (2017). Strategy complexity of concurrent safety games. In Leibniz International Proceedings in Informatics (Vol. 83). Aalborg, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2017.55","ama":"Chatterjee K, Hansen K, Ibsen-Jensen R. Strategy complexity of concurrent safety games. In: Leibniz International Proceedings in Informatics. Vol 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.MFCS.2017.55","short":"K. Chatterjee, K. Hansen, R. Ibsen-Jensen, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ieee":"K. Chatterjee, K. Hansen, and R. Ibsen-Jensen, “Strategy complexity of concurrent safety games,” in Leibniz International Proceedings in Informatics, Aalborg, Denmark, 2017, vol. 83.","mla":"Chatterjee, Krishnendu, et al. “Strategy Complexity of Concurrent Safety Games.” Leibniz International Proceedings in Informatics, vol. 83, 55, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.MFCS.2017.55."},"title":"Strategy complexity of concurrent safety games","publist_id":"7261","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Hansen, Kristofer","last_name":"Hansen","first_name":"Kristofer"},{"full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"}],"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"day":"01","publication":"Leibniz International Proceedings in Informatics","has_accepted_license":"1","year":"2017","date_published":"2017-11-01T00:00:00Z","doi":"10.4230/LIPIcs.MFCS.2017.55","date_created":"2018-12-11T11:47:08Z"},{"title":"On stochastic differential equations with arbitrarily slow convergence rates for strong approximation in two space dimensions","publist_id":"7256","author":[{"full_name":"Gerencser, Mate","last_name":"Gerencser","id":"44ECEDF2-F248-11E8-B48F-1D18A9856A87","first_name":"Mate"},{"last_name":"Jentzen","full_name":"Jentzen, Arnulf","first_name":"Arnulf"},{"full_name":"Salimova, Diyora","last_name":"Salimova","first_name":"Diyora"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Gerencser, Mate, Arnulf Jentzen, and Diyora Salimova. “On Stochastic Differential Equations with Arbitrarily Slow Convergence Rates for Strong Approximation in Two Space Dimensions.” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. Royal Society of London, 2017. https://doi.org/10.1098/rspa.2017.0104.","ista":"Gerencser M, Jentzen A, Salimova D. 2017. On stochastic differential equations with arbitrarily slow convergence rates for strong approximation in two space dimensions. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 473(2207), 0104.","mla":"Gerencser, Mate, et al. “On Stochastic Differential Equations with Arbitrarily Slow Convergence Rates for Strong Approximation in Two Space Dimensions.” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 473, no. 2207, 0104, Royal Society of London, 2017, doi:10.1098/rspa.2017.0104.","ama":"Gerencser M, Jentzen A, Salimova D. On stochastic differential equations with arbitrarily slow convergence rates for strong approximation in two space dimensions. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2017;473(2207). doi:10.1098/rspa.2017.0104","apa":"Gerencser, M., Jentzen, A., & Salimova, D. (2017). On stochastic differential equations with arbitrarily slow convergence rates for strong approximation in two space dimensions. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. Royal Society of London. https://doi.org/10.1098/rspa.2017.0104","short":"M. Gerencser, A. Jentzen, D. Salimova, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 473 (2017).","ieee":"M. Gerencser, A. Jentzen, and D. Salimova, “On stochastic differential equations with arbitrarily slow convergence rates for strong approximation in two space dimensions,” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 473, no. 2207. Royal Society of London, 2017."},"project":[{"call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"}],"article_number":"0104","doi":"10.1098/rspa.2017.0104","date_published":"2017-11-01T00:00:00Z","date_created":"2018-12-11T11:47:11Z","day":"01","publication":"Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences","year":"2017","quality_controlled":"1","publisher":"Royal Society of London","oa":1,"department":[{"_id":"JaMa"}],"date_updated":"2021-01-12T08:03:04Z","status":"public","type":"journal_article","_id":"560","volume":473,"issue":"2207","ec_funded":1,"language":[{"iso":"eng"}],"publication_identifier":{"issn":["13645021"]},"publication_status":"published","month":"11","intvolume":" 473","scopus_import":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1702.03229"}],"oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"In a recent article (Jentzen et al. 2016 Commun. Math. Sci. 14, 1477–1500 (doi:10.4310/CMS.2016.v14. n6.a1)), it has been established that, for every arbitrarily slow convergence speed and every natural number d ? {4, 5, . . .}, there exist d-dimensional stochastic differential equations with infinitely often differentiable and globally bounded coefficients such that no approximation method based on finitely many observations of the driving Brownian motion can converge in absolute mean to the solution faster than the given speed of convergence. In this paper, we strengthen the above result by proving that this slow convergence phenomenon also arises in two (d = 2) and three (d = 3) space dimensions."}]},{"date_updated":"2022-05-24T06:57:28Z","department":[{"_id":"LaEr"}],"series_title":"Courant Lecture Notes","_id":"567","type":"book","status":"public","publication_status":"published","publication_identifier":{"eisbn":["978-1-4704-4194-4"],"isbn":["9-781-4704-3648-3"]},"language":[{"iso":"eng"}],"ec_funded":1,"volume":28,"abstract":[{"lang":"eng","text":"This book is a concise and self-contained introduction of recent techniques to prove local spectral universality for large random matrices. Random matrix theory is a fast expanding research area, and this book mainly focuses on the methods that the authors participated in developing over the past few years. Many other interesting topics are not included, and neither are several new developments within the framework of these methods. The authors have chosen instead to present key concepts that they believe are the core of these methods and should be relevant for future applications. They keep technicalities to a minimum to make the book accessible to graduate students. With this in mind, they include in this book the basic notions and tools for high-dimensional analysis, such as large deviation, entropy, Dirichlet form, and the logarithmic Sobolev inequality.\r\n"}],"oa_version":"None","alternative_title":["Courant Lecture Notes"],"intvolume":" 28","month":"01","citation":{"chicago":"Erdös, László, and Horng Yau. A Dynamical Approach to Random Matrix Theory. Vol. 28. Courant Lecture Notes. American Mathematical Society, 2017. https://doi.org/10.1090/cln/028.","ista":"Erdös L, Yau H. 2017. A Dynamical Approach to Random Matrix Theory, American Mathematical Society, 226p.","mla":"Erdös, László, and Horng Yau. A Dynamical Approach to Random Matrix Theory. Vol. 28, American Mathematical Society, 2017, doi:10.1090/cln/028.","ieee":"L. Erdös and H. Yau, A Dynamical Approach to Random Matrix Theory, vol. 28. American Mathematical Society, 2017.","short":"L. Erdös, H. Yau, A Dynamical Approach to Random Matrix Theory, American Mathematical Society, 2017.","apa":"Erdös, L., & Yau, H. (2017). A Dynamical Approach to Random Matrix Theory (Vol. 28). American Mathematical Society. https://doi.org/10.1090/cln/028","ama":"Erdös L, Yau H. A Dynamical Approach to Random Matrix Theory. Vol 28. American Mathematical Society; 2017. doi:10.1090/cln/028"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","author":[{"first_name":"László","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","last_name":"Erdös","full_name":"Erdös, László","orcid":"0000-0001-5366-9603"},{"full_name":"Yau, Horng","last_name":"Yau","first_name":"Horng"}],"publist_id":"7247","title":"A Dynamical Approach to Random Matrix Theory","project":[{"call_identifier":"FP7","_id":"258DCDE6-B435-11E9-9278-68D0E5697425","name":"Random matrices, universality and disordered quantum systems","grant_number":"338804"}],"year":"2017","day":"01","page":"226","date_created":"2018-12-11T11:47:13Z","doi":"10.1090/cln/028","date_published":"2017-01-01T00:00:00Z","quality_controlled":"1","publisher":"American Mathematical Society"},{"_id":"568","status":"public","type":"journal_article","date_updated":"2021-01-12T08:03:12Z","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"We study robust properties of zero sets of continuous maps f: X → ℝn. Formally, we analyze the family Z< r(f) := (g-1(0): ||g - f|| < r) of all zero sets of all continuous maps g closer to f than r in the max-norm. All of these sets are outside A := (x: |f(x)| ≥ r) and we claim that Z< r(f) is fully determined by A and an element of a certain cohomotopy group which (by a recent result) is computable whenever the dimension of X is at most 2n - 3. By considering all r > 0 simultaneously, the pointed cohomotopy groups form a persistence module-a structure leading to persistence diagrams as in the case of persistent homology or well groups. Eventually, we get a descriptor of persistent robust properties of zero sets that has better descriptive power (Theorem A) and better computability status (Theorem B) than the established well diagrams. Moreover, if we endow every point of each zero set with gradients of the perturbation, the robust description of the zero sets by elements of cohomotopy groups is in some sense the best possible (Theorem C)."}],"intvolume":" 19","month":"01","main_file_link":[{"url":"https://arxiv.org/abs/1507.04310","open_access":"1"}],"scopus_import":1,"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"issn":["15320073"]},"ec_funded":1,"volume":19,"issue":"2","project":[{"call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"},{"grant_number":"701309","name":"Atomic-Resolution Structures of Mitochondrial Respiratory Chain Supercomplexes (H2020)","_id":"2590DB08-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Franek, Peter, and Marek Krcál. “Persistence of Zero Sets.” Homology, Homotopy and Applications. International Press, 2017. https://doi.org/10.4310/HHA.2017.v19.n2.a16.","ista":"Franek P, Krcál M. 2017. Persistence of zero sets. Homology, Homotopy and Applications. 19(2), 313–342.","mla":"Franek, Peter, and Marek Krcál. “Persistence of Zero Sets.” Homology, Homotopy and Applications, vol. 19, no. 2, International Press, 2017, pp. 313–42, doi:10.4310/HHA.2017.v19.n2.a16.","short":"P. Franek, M. Krcál, Homology, Homotopy and Applications 19 (2017) 313–342.","ieee":"P. Franek and M. Krcál, “Persistence of zero sets,” Homology, Homotopy and Applications, vol. 19, no. 2. International Press, pp. 313–342, 2017.","apa":"Franek, P., & Krcál, M. (2017). Persistence of zero sets. Homology, Homotopy and Applications. International Press. https://doi.org/10.4310/HHA.2017.v19.n2.a16","ama":"Franek P, Krcál M. Persistence of zero sets. Homology, Homotopy and Applications. 2017;19(2):313-342. doi:10.4310/HHA.2017.v19.n2.a16"},"title":"Persistence of zero sets","author":[{"full_name":"Franek, Peter","last_name":"Franek","first_name":"Peter","id":"473294AE-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Krcál","full_name":"Krcál, Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87","first_name":"Marek"}],"publist_id":"7246","oa":1,"publisher":"International Press","quality_controlled":"1","publication":"Homology, Homotopy and Applications","day":"01","year":"2017","date_created":"2018-12-11T11:47:14Z","date_published":"2017-01-01T00:00:00Z","doi":"10.4310/HHA.2017.v19.n2.a16","page":"313 - 342"},{"date_updated":"2021-01-12T08:03:15Z","ddc":["576"],"file_date_updated":"2020-07-14T12:47:10Z","department":[{"_id":"CaGu"},{"_id":"JoBo"},{"_id":"NiBa"}],"_id":"570","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","pubrep_id":"918","publication_identifier":{"issn":["2050084X"]},"publication_status":"published","file":[{"date_created":"2018-12-12T10:14:42Z","file_name":"IST-2017-918-v1+1_elife-28921-figures-v3.pdf","creator":"system","date_updated":"2020-07-14T12:47:10Z","file_size":8453470,"checksum":"273ab17f33305e4eaafd911ff88e7c5b","file_id":"5096","access_level":"open_access","relation":"main_file","content_type":"application/pdf"},{"creator":"system","date_updated":"2020-07-14T12:47:10Z","file_size":1953221,"date_created":"2018-12-12T10:14:43Z","file_name":"IST-2017-918-v1+2_elife-28921-v3.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"b433f90576c7be597cd43367946f8e7f","file_id":"5097"}],"language":[{"iso":"eng"}],"volume":6,"ec_funded":1,"abstract":[{"lang":"eng","text":"Most phenotypes are determined by molecular systems composed of specifically interacting molecules. However, unlike for individual components, little is known about the distributions of mutational effects of molecular systems as a whole. We ask how the distribution of mutational effects of a transcriptional regulatory system differs from the distributions of its components, by first independently, and then simultaneously, mutating a transcription factor and the associated promoter it represses. We find that the system distribution exhibits increased phenotypic variation compared to individual component distributions - an effect arising from intermolecular epistasis between the transcription factor and its DNA-binding site. In large part, this epistasis can be qualitatively attributed to the structure of the transcriptional regulatory system and could therefore be a common feature in prokaryotes. Counter-intuitively, intermolecular epistasis can alleviate the constraints of individual components, thereby increasing phenotypic variation that selection could act on and facilitating adaptive evolution. "}],"oa_version":"Published Version","scopus_import":1,"month":"11","intvolume":" 6","citation":{"ista":"Lagator M, Sarikas S, Acar H, Bollback JP, Guet CC. 2017. Regulatory network structure determines patterns of intermolecular epistasis. eLife. 6, e28921.","chicago":"Lagator, Mato, Srdjan Sarikas, Hande Acar, Jonathan P Bollback, and Calin C Guet. “Regulatory Network Structure Determines Patterns of Intermolecular Epistasis.” ELife. eLife Sciences Publications, 2017. https://doi.org/10.7554/eLife.28921.","apa":"Lagator, M., Sarikas, S., Acar, H., Bollback, J. P., & Guet, C. C. (2017). Regulatory network structure determines patterns of intermolecular epistasis. ELife. eLife Sciences Publications. https://doi.org/10.7554/eLife.28921","ama":"Lagator M, Sarikas S, Acar H, Bollback JP, Guet CC. Regulatory network structure determines patterns of intermolecular epistasis. eLife. 2017;6. doi:10.7554/eLife.28921","ieee":"M. Lagator, S. Sarikas, H. Acar, J. P. Bollback, and C. C. Guet, “Regulatory network structure determines patterns of intermolecular epistasis,” eLife, vol. 6. eLife Sciences Publications, 2017.","short":"M. Lagator, S. Sarikas, H. Acar, J.P. Bollback, C.C. Guet, ELife 6 (2017).","mla":"Lagator, Mato, et al. “Regulatory Network Structure Determines Patterns of Intermolecular Epistasis.” ELife, vol. 6, e28921, eLife Sciences Publications, 2017, doi:10.7554/eLife.28921."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"345D25EC-F248-11E8-B48F-1D18A9856A87","first_name":"Mato","full_name":"Lagator, Mato","last_name":"Lagator"},{"full_name":"Sarikas, Srdjan","last_name":"Sarikas","id":"35F0286E-F248-11E8-B48F-1D18A9856A87","first_name":"Srdjan"},{"id":"2DDF136A-F248-11E8-B48F-1D18A9856A87","first_name":"Hande","last_name":"Acar","orcid":"0000-0003-1986-9753","full_name":"Acar, Hande"},{"id":"2C6FA9CC-F248-11E8-B48F-1D18A9856A87","first_name":"Jonathan P","last_name":"Bollback","orcid":"0000-0002-4624-4612","full_name":"Bollback, Jonathan P"},{"first_name":"Calin C","id":"47F8433E-F248-11E8-B48F-1D18A9856A87","full_name":"Guet, Calin C","orcid":"0000-0001-6220-2052","last_name":"Guet"}],"publist_id":"7244","title":"Regulatory network structure determines patterns of intermolecular epistasis","article_number":"e28921","project":[{"call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"},{"_id":"2578D616-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"648440","name":"Selective Barriers to Horizontal Gene Transfer"}],"has_accepted_license":"1","year":"2017","day":"13","publication":"eLife","doi":"10.7554/eLife.28921","date_published":"2017-11-13T00:00:00Z","date_created":"2018-12-11T11:47:14Z","publisher":"eLife Sciences Publications","quality_controlled":"1","oa":1}]