[{"_id":"688","scopus_import":1,"license":"https://creativecommons.org/licenses/by/4.0/","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner"},{"full_name":"Wagner, Hubert","first_name":"Hubert","last_name":"Wagner","id":"379CA8B8-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","department":[{"_id":"HeEd"},{"_id":"UlWa"}],"date_created":"2018-12-11T11:47:56Z","pubrep_id":"895","title":"Topological data analysis with Bregman divergences","alternative_title":["LIPIcs"],"intvolume":"        77","page":"391-3916","quality_controlled":"1","file_date_updated":"2020-07-14T12:47:42Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_updated":"2021-01-12T08:09:26Z","year":"2017","citation":{"mla":"Edelsbrunner, Herbert, and Hubert Wagner. <i>Topological Data Analysis with Bregman Divergences</i>. Vol. 77, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 391–3916, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.39\">10.4230/LIPIcs.SoCG.2017.39</a>.","short":"H. Edelsbrunner, H. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 391–3916.","ista":"Edelsbrunner H, Wagner H. 2017. Topological data analysis with Bregman divergences. Symposium on Computational Geometry, SoCG, LIPIcs, vol. 77, 391–3916.","apa":"Edelsbrunner, H., &#38; 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. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.39\">https://doi.org/10.4230/LIPIcs.SoCG.2017.39</a>","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:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.39\">10.4230/LIPIcs.SoCG.2017.39</a>","chicago":"Edelsbrunner, Herbert, and Hubert Wagner. “Topological Data Analysis with Bregman Divergences,” 77:391–3916. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.39\">https://doi.org/10.4230/LIPIcs.SoCG.2017.39</a>.","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."},"doi":"10.4230/LIPIcs.SoCG.2017.39","day":"01","abstract":[{"lang":"eng","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. "}],"volume":77,"ddc":["514","516"],"has_accepted_license":"1","oa_version":"Published Version","month":"06","language":[{"iso":"eng"}],"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","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"date_published":"2017-06-01T00:00:00Z","type":"conference","publication_identifier":{"issn":["18688969"]},"oa":1,"publist_id":"7021","file":[{"file_id":"4856","creator":"system","access_level":"open_access","relation":"main_file","date_updated":"2020-07-14T12:47:42Z","content_type":"application/pdf","file_name":"IST-2017-895-v1+1_LIPIcs-SoCG-2017-39.pdf","date_created":"2018-12-12T10:11:03Z","file_size":990546,"checksum":"067ab0cb3f962bae6c3af6bf0094e0f3"}],"status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87"},{"file_date_updated":"2020-07-14T12:47:46Z","ec_funded":1,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","author":[{"last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","full_name":"Skórski, Maciej","last_name":"Skórski","first_name":"Maciej"}],"scopus_import":1,"_id":"697","intvolume":"        80","alternative_title":["LIPIcs"],"title":"Non uniform attacks against pseudoentropy","pubrep_id":"893","department":[{"_id":"KrPi"}],"date_created":"2018-12-11T11:47:59Z","publication_status":"published","ddc":["005"],"volume":80,"citation":{"apa":"Pietrzak, K. Z., &#38; 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. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2017.39\">https://doi.org/10.4230/LIPIcs.ICALP.2017.39</a>","ama":"Pietrzak KZ, Skórski M. Non uniform attacks against pseudoentropy. In: Vol 80. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2017.39\">10.4230/LIPIcs.ICALP.2017.39</a>","chicago":"Pietrzak, Krzysztof Z, and Maciej Skórski. “Non Uniform Attacks against Pseudoentropy,” Vol. 80. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2017.39\">https://doi.org/10.4230/LIPIcs.ICALP.2017.39</a>.","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.","mla":"Pietrzak, Krzysztof Z., and Maciej Skórski. <i>Non Uniform Attacks against Pseudoentropy</i>. Vol. 80, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2017.39\">10.4230/LIPIcs.ICALP.2017.39</a>.","short":"K.Z. Pietrzak, M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ista":"Pietrzak KZ, Skórski M. 2017. Non uniform attacks against pseudoentropy. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 80, 39."},"year":"2017","date_updated":"2021-01-12T08:11:15Z","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"}],"day":"01","doi":"10.4230/LIPIcs.ICALP.2017.39","language":[{"iso":"eng"}],"conference":{"start_date":"2017-07-10","name":"ICALP: International Colloquium on Automata, Languages, and Programming","end_date":"2017-07-14","location":"Warsaw, Poland"},"has_accepted_license":"1","article_number":"39","month":"07","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"oa_version":"Published Version","status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file":[{"access_level":"open_access","relation":"main_file","creator":"system","file_id":"4701","file_size":601004,"checksum":"e95618a001692f1af2d68f5fde43bc1f","date_created":"2018-12-12T10:08:40Z","content_type":"application/pdf","file_name":"IST-2017-893-v1+1_LIPIcs-ICALP-2017-39.pdf","date_updated":"2020-07-14T12:47:46Z"}],"type":"conference","date_published":"2017-07-01T00:00:00Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1,"publist_id":"7003","publication_identifier":{"issn":["18688969"]}},{"file":[{"date_created":"2018-12-12T10:13:10Z","checksum":"89225c7dcec2c93838458c9102858985","file_size":604813,"date_updated":"2020-07-14T12:47:49Z","content_type":"application/pdf","file_name":"IST-2017-888-v1+1_LIPIcs-APPROX-RANDOM-2017-20.pdf","access_level":"open_access","relation":"main_file","file_id":"4991","creator":"system"}],"status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"type":"conference","date_published":"2017-08-01T00:00:00Z","publication_identifier":{"issn":["18688969"]},"publist_id":"6979","oa":1,"language":[{"iso":"eng"}],"conference":{"location":"Berkeley, USA","end_date":"2017-08-18","name":"20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX","start_date":"2017-08-18"},"has_accepted_license":"1","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"oa_version":"Published Version","article_number":"20","month":"08","volume":81,"ddc":["005","600"],"citation":{"short":"M. Obremski, M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Obremski, Maciej, and Maciej Skórski. <i>Renyi Entropy Estimation Revisited</i>. Vol. 81, 20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20\">10.4230/LIPIcs.APPROX-RANDOM.2017.20</a>.","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.","apa":"Obremski, M., &#38; 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. <a href=\"https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20\">https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20</a>","ama":"Obremski M, Skórski M. Renyi entropy estimation revisited. In: Vol 81. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20\">10.4230/LIPIcs.APPROX-RANDOM.2017.20</a>","chicago":"Obremski, Maciej, and Maciej Skórski. “Renyi Entropy Estimation Revisited,” Vol. 81. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20\">https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20</a>.","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."},"year":"2017","date_updated":"2021-01-12T08:11:50Z","day":"01","doi":"10.4230/LIPIcs.APPROX-RANDOM.2017.20","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&gt;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&gt;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. "}],"ec_funded":1,"quality_controlled":"1","file_date_updated":"2020-07-14T12:47:49Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","scopus_import":1,"_id":"710","author":[{"full_name":"Obremski, Maciej","last_name":"Obremski","first_name":"Maciej"},{"last_name":"Skórski","first_name":"Maciej","full_name":"Skórski, Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD"}],"date_created":"2018-12-11T11:48:04Z","department":[{"_id":"KrPi"}],"publication_status":"published","intvolume":"        81","alternative_title":["LIPIcs"],"title":"Renyi entropy estimation revisited","pubrep_id":"888"},{"has_accepted_license":"1","oa_version":"Published Version","month":"08","article_number":"5","language":[{"iso":"eng"}],"conference":{"end_date":"2017-09-08","location":"Berlin, Germany","start_date":"2017-09-05","name":"28th International Conference on Concurrency Theory, CONCUR"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"date_published":"2017-08-01T00:00:00Z","type":"conference","publication_identifier":{"issn":["18688969"]},"publist_id":"6976","oa":1,"file":[{"file_id":"4661","creator":"system","access_level":"open_access","relation":"main_file","date_updated":"2020-07-14T12:47:49Z","file_name":"IST-2017-886-v1+1_LIPIcs-CONCUR-2017-5.pdf","content_type":"application/pdf","date_created":"2018-12-12T10:08:02Z","file_size":570294,"checksum":"d2bda4783821a6358333fe27f11f4737"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","_id":"711","scopus_import":1,"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Otop, Jan","first_name":"Jan","last_name":"Otop"}],"publication_status":"published","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"date_created":"2018-12-11T11:48:04Z","title":"Bidirectional nested weighted automata","pubrep_id":"886","alternative_title":["LIPIcs"],"intvolume":"        85","quality_controlled":"1","file_date_updated":"2020-07-14T12:47:49Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_updated":"2021-01-12T08:11:53Z","year":"2017","citation":{"apa":"Chatterjee, K., Henzinger, T. A., &#38; 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. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2017.5\">https://doi.org/10.4230/LIPIcs.CONCUR.2017.5</a>","ama":"Chatterjee K, Henzinger TA, Otop J. Bidirectional nested weighted automata. In: Vol 85. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2017.5\">10.4230/LIPIcs.CONCUR.2017.5</a>","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.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Bidirectional Nested Weighted Automata,” Vol. 85. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2017.5\">https://doi.org/10.4230/LIPIcs.CONCUR.2017.5</a>.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Chatterjee, Krishnendu, et al. <i>Bidirectional Nested Weighted Automata</i>. Vol. 85, 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2017.5\">10.4230/LIPIcs.CONCUR.2017.5</a>.","ista":"Chatterjee K, Henzinger TA, Otop J. 2017. Bidirectional nested weighted automata. 28th International Conference on Concurrency Theory, CONCUR, LIPIcs, vol. 85, 5."},"doi":"10.4230/LIPIcs.CONCUR.2017.5","day":"01","abstract":[{"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.","lang":"eng"}],"volume":85,"ddc":["004","005"]},{"language":[{"iso":"eng"}],"conference":{"location":"Aalborg, Denmark","end_date":"2017-08-25","start_date":"2017-08-21","name":"MFCS: Mathematical Foundations of Computer Science (SG)"},"has_accepted_license":"1","month":"06","article_number":"37","oa_version":"Published Version","project":[{"name":"Moderne Concurrency Paradigms","grant_number":"S11402-N23","call_identifier":"FWF","_id":"25F5A88A-B435-11E9-9278-68D0E5697425"}],"related_material":{"record":[{"status":"public","id":"6005","relation":"later_version"}]},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"date_updated":"2020-07-14T12:48:18Z","file_name":"IST-2017-829-v1+1_mfcs-cr.pdf","content_type":"application/pdf","date_created":"2018-12-12T10:14:10Z","file_size":369730,"checksum":"f55eaf7f3c36ea07801112acfedd17d5","file_id":"5059","creator":"system","access_level":"open_access","relation":"main_file"}],"date_published":"2017-06-01T00:00:00Z","type":"conference","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"publist_id":"6438","oa":1,"publication_identifier":{"issn":["18688969"]},"file_date_updated":"2020-07-14T12:48:18Z","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","author":[{"orcid":"0000-0001-5588-8287","full_name":"Avni, Guy","first_name":"Guy","last_name":"Avni","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Shibashis","last_name":"Guha","full_name":"Guha, Shibashis"},{"last_name":"Kupferman","first_name":"Orna","full_name":"Kupferman, Orna"}],"_id":"963","scopus_import":1,"title":"Timed network games with clocks","pubrep_id":"829","alternative_title":["LIPIcs"],"intvolume":"        83","publication_status":"published","date_created":"2018-12-11T11:49:26Z","department":[{"_id":"ToHe"}],"ddc":["004"],"volume":83,"date_updated":"2023-02-23T12:35:50Z","year":"2017","citation":{"mla":"Avni, Guy, et al. <i>Timed Network Games with Clocks</i>. Vol. 83, 37, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2017.37\">10.4230/LIPIcs.MFCS.2017.37</a>.","short":"G. Avni, S. Guha, O. Kupferman, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ista":"Avni G, Guha S, Kupferman O. 2017. Timed network games with clocks. MFCS: Mathematical Foundations of Computer Science (SG), LIPIcs, vol. 83, 37.","apa":"Avni, G., Guha, S., &#38; 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. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2017.37\">https://doi.org/10.4230/LIPIcs.MFCS.2017.37</a>","ama":"Avni G, Guha S, Kupferman O. Timed network games with clocks. In: Vol 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2017.37\">10.4230/LIPIcs.MFCS.2017.37</a>","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.","chicago":"Avni, Guy, Shibashis Guha, and Orna Kupferman. “Timed Network Games with Clocks,” Vol. 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2017.37\">https://doi.org/10.4230/LIPIcs.MFCS.2017.37</a>."},"abstract":[{"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. ","lang":"eng"}],"doi":"10.4230/LIPIcs.MFCS.2017.37","day":"01"}]