--- _id: '552' 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).' alternative_title: - LIPIcs article_number: '39' article_processing_charge: No author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Alexander full_name: Svozil, Alexander last_name: Svozil citation: 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' 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. 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. 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.' 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. short: K. Chatterjee, M.H. Henzinger, A. Svozil, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. conference: end_date: 2017-08-25 location: Aalborg, Denmark name: 'MFCS: Mathematical Foundations of Computer Science (SG)' start_date: 2017-08-21 date_created: 2018-12-11T11:47:08Z date_published: 2017-11-01T00:00:00Z date_updated: 2023-02-14T10:06:46Z day: '01' ddc: - '004' department: - _id: KrCh doi: 10.4230/LIPIcs.MFCS.2017.39 ec_funded: 1 file: - access_level: open_access checksum: c67f4866ddbfd555afef1f63ae9a8fc7 content_type: application/pdf creator: system date_created: 2018-12-12T10:16:57Z date_updated: 2020-07-14T12:47:00Z file_id: '5248' file_name: IST-2018-923-v1+1_LIPIcs-MFCS-2017-39.pdf file_size: 610339 relation: main_file file_date_updated: 2020-07-14T12:47:00Z has_accepted_license: '1' intvolume: ' 83' language: - iso: eng license: https://creativecommons.org/licenses/by/3.0/ month: '11' oa: 1 oa_version: Published Version project: - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' publication: Leibniz International Proceedings in Informatics publication_identifier: isbn: - 978-395977046-0 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik publist_id: '7262' pubrep_id: '923' quality_controlled: '1' scopus_import: '1' status: public title: Faster algorithms for mean-payoff parity games tmp: 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) short: CC BY (3.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 83 year: '2017' ... --- _id: '553' 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. ' alternative_title: - LIPIcs article_number: '55' author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Kristofer full_name: Hansen, Kristofer last_name: Hansen - first_name: Rasmus full_name: Ibsen-Jensen, Rasmus id: 3B699956-F248-11E8-B48F-1D18A9856A87 last_name: Ibsen-Jensen orcid: 0000-0003-4783-0389 citation: 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' 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' 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. 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. 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.' 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. short: K. Chatterjee, K. Hansen, R. Ibsen-Jensen, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. conference: end_date: 2017-08-25 location: Aalborg, Denmark name: 'MFCS: Mathematical Foundations of Computer Science (SG)' start_date: 2017-08-21 date_created: 2018-12-11T11:47:08Z date_published: 2017-11-01T00:00:00Z date_updated: 2021-01-12T08:02:35Z day: '01' ddc: - '004' department: - _id: KrCh doi: 10.4230/LIPIcs.MFCS.2017.55 file: - access_level: open_access checksum: 7101facb56ade363205c695d72dbd173 content_type: application/pdf creator: system date_created: 2018-12-12T10:09:29Z date_updated: 2020-07-14T12:47:00Z file_id: '4753' file_name: IST-2018-922-v1+1_LIPIcs-MFCS-2017-55.pdf file_size: 549967 relation: main_file file_date_updated: 2020-07-14T12:47:00Z has_accepted_license: '1' intvolume: ' 83' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1506.02434 month: '11' oa: 1 oa_version: Published Version publication: Leibniz International Proceedings in Informatics publication_identifier: isbn: - 978-395977046-0 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik publist_id: '7261' pubrep_id: '922' quality_controlled: '1' scopus_import: 1 status: public title: Strategy complexity of concurrent safety games tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 83 year: '2017' ... --- _id: '560' 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. article_number: '0104' author: - first_name: Mate full_name: Gerencser, Mate id: 44ECEDF2-F248-11E8-B48F-1D18A9856A87 last_name: Gerencser - first_name: Arnulf full_name: Jentzen, Arnulf last_name: Jentzen - first_name: Diyora full_name: Salimova, Diyora last_name: Salimova citation: 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' 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.' 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.' 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.' short: 'M. Gerencser, A. Jentzen, D. Salimova, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 473 (2017).' date_created: 2018-12-11T11:47:11Z date_published: 2017-11-01T00:00:00Z date_updated: 2021-01-12T08:03:04Z day: '01' department: - _id: JaMa doi: 10.1098/rspa.2017.0104 ec_funded: 1 intvolume: ' 473' issue: '2207' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1702.03229 month: '11' oa: 1 oa_version: Submitted Version project: - _id: 25681D80-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '291734' name: International IST Postdoc Fellowship Programme publication: 'Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences' publication_identifier: issn: - '13645021' publication_status: published publisher: Royal Society of London publist_id: '7256' quality_controlled: '1' scopus_import: 1 status: public title: On stochastic differential equations with arbitrarily slow convergence rates for strong approximation in two space dimensions type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 473 year: '2017' ... --- _id: '567' 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" alternative_title: - Courant Lecture Notes article_processing_charge: No author: - first_name: László full_name: Erdös, László id: 4DBD5372-F248-11E8-B48F-1D18A9856A87 last_name: Erdös orcid: 0000-0001-5366-9603 - first_name: Horng full_name: Yau, Horng last_name: Yau citation: ama: Erdös L, Yau H. A Dynamical Approach to Random Matrix Theory. Vol 28. American Mathematical Society; 2017. doi:10.1090/cln/028 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 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. ieee: L. Erdös and H. Yau, A Dynamical Approach to Random Matrix Theory, vol. 28. American Mathematical Society, 2017. 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. short: L. Erdös, H. Yau, A Dynamical Approach to Random Matrix Theory, American Mathematical Society, 2017. date_created: 2018-12-11T11:47:13Z date_published: 2017-01-01T00:00:00Z date_updated: 2022-05-24T06:57:28Z day: '01' department: - _id: LaEr doi: 10.1090/cln/028 ec_funded: 1 intvolume: ' 28' language: - iso: eng month: '01' oa_version: None page: '226' project: - _id: 258DCDE6-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '338804' name: Random matrices, universality and disordered quantum systems publication_identifier: eisbn: - 978-1-4704-4194-4 isbn: - 9-781-4704-3648-3 publication_status: published publisher: American Mathematical Society publist_id: '7247' quality_controlled: '1' series_title: Courant Lecture Notes status: public title: A Dynamical Approach to Random Matrix Theory type: book user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 28 year: '2017' ... --- _id: '568' 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).' author: - first_name: Peter full_name: Franek, Peter id: 473294AE-F248-11E8-B48F-1D18A9856A87 last_name: Franek - first_name: Marek full_name: Krcál, Marek id: 33E21118-F248-11E8-B48F-1D18A9856A87 last_name: Krcál citation: 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 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 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. 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. 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. date_created: 2018-12-11T11:47:14Z date_published: 2017-01-01T00:00:00Z date_updated: 2021-01-12T08:03:12Z day: '01' department: - _id: UlWa - _id: HeEd doi: 10.4310/HHA.2017.v19.n2.a16 ec_funded: 1 intvolume: ' 19' issue: '2' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1507.04310 month: '01' oa: 1 oa_version: Submitted Version page: 313 - 342 project: - _id: 25681D80-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '291734' name: International IST Postdoc Fellowship Programme - _id: 2590DB08-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '701309' name: Atomic-Resolution Structures of Mitochondrial Respiratory Chain Supercomplexes (H2020) publication: Homology, Homotopy and Applications publication_identifier: issn: - '15320073' publication_status: published publisher: International Press publist_id: '7246' quality_controlled: '1' scopus_import: 1 status: public title: Persistence of zero sets type: journal_article user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87 volume: 19 year: '2017' ...