[{"language":[{"iso":"eng"}],"doi":"10.23638/LMCS-13(3:23)2017","quality_controlled":"1","project":[{"_id":"25F5A88A-B435-11E9-9278-68D0E5697425","grant_number":"S11402-N23","call_identifier":"FWF","name":"Moderne Concurrency Paradigms"},{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","call_identifier":"FWF"},{"grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Reactive Modeling"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"call_identifier":"FWF","name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425"}],"tmp":{"short":"CC BY-ND (4.0)","image":"/image/cc_by_nd.png","name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode"},"oa":1,"month":"09","publication_identifier":{"issn":["18605974"]},"date_created":"2018-12-11T11:46:37Z","date_updated":"2023-02-23T12:26:25Z","volume":13,"author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A"},{"full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389"},{"full_name":"Otop, Jan","last_name":"Otop","first_name":"Jan"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"1610"},{"id":"5438","status":"public","relation":"earlier_version"}]},"publication_status":"published","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publisher":"International Federation of Computational Logic","year":"2017","license":"https://creativecommons.org/licenses/by-nd/4.0/","file_date_updated":"2020-07-14T12:46:33Z","publist_id":"7356","ec_funded":1,"date_published":"2017-09-13T00:00:00Z","publication":"Logical Methods in Computer Science","citation":{"apa":"Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., & Otop, J. (2017). Edit distance for pushdown automata. Logical Methods in Computer Science. International Federation of Computational Logic. https://doi.org/10.23638/LMCS-13(3:23)2017","ieee":"K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, “Edit distance for pushdown automata,” Logical Methods in Computer Science, vol. 13, no. 3. International Federation of Computational Logic, 2017.","ista":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2017. Edit distance for pushdown automata. Logical Methods in Computer Science. 13(3).","ama":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. Edit distance for pushdown automata. Logical Methods in Computer Science. 2017;13(3). doi:10.23638/LMCS-13(3:23)2017","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan Otop. “Edit Distance for Pushdown Automata.” Logical Methods in Computer Science. International Federation of Computational Logic, 2017. https://doi.org/10.23638/LMCS-13(3:23)2017.","short":"K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Logical Methods in Computer Science 13 (2017).","mla":"Chatterjee, Krishnendu, et al. “Edit Distance for Pushdown Automata.” Logical Methods in Computer Science, vol. 13, no. 3, International Federation of Computational Logic, 2017, doi:10.23638/LMCS-13(3:23)2017."},"day":"13","has_accepted_license":"1","scopus_import":1,"file":[{"creator":"system","file_size":279071,"content_type":"application/pdf","access_level":"open_access","file_name":"IST-2015-321-v1+1_main.pdf","checksum":"08041379ba408d40664f449eb5907a8f","date_created":"2018-12-12T10:14:37Z","date_updated":"2020-07-14T12:46:33Z","file_id":"5090","relation":"main_file"},{"creator":"system","file_size":279071,"content_type":"application/pdf","file_name":"IST-2018-955-v1+1_2017_Chatterjee_Edit_distance.pdf","access_level":"open_access","date_created":"2018-12-12T10:14:38Z","date_updated":"2020-07-14T12:46:33Z","checksum":"08041379ba408d40664f449eb5907a8f","file_id":"5091","relation":"main_file"}],"oa_version":"Published Version","pubrep_id":"955","ddc":["004"],"title":"Edit distance for pushdown automata","status":"public","intvolume":" 13","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"465","abstract":[{"lang":"eng","text":"The edit distance between two words w 1 , w 2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w 1 to w 2 . The edit distance generalizes to languages L 1 , L 2 , where the edit distance from L 1 to L 2 is the minimal number k such that for every word from L 1 there exists a word in L 2 with edit distance at most k . We study the edit distance computation problem between pushdown automata and their subclasses. The problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for the following problems: (1) deciding whether, for a given threshold k , the edit distance from a pushdown automaton to a finite automaton is at most k , and (2) deciding whether the edit distance from a pushdown automaton to a finite automaton is finite. "}],"issue":"3","type":"journal_article"},{"abstract":[{"text":"The fixation probability is the probability that a new mutant introduced in a homogeneous population eventually takes over the entire population. The fixation probability is a fundamental quantity of natural selection, and known to depend on the population structure. Amplifiers of natural selection are population structures which increase the fixation probability of advantageous mutants, as compared to the baseline case of well-mixed populations. In this work we focus on symmetric population structures represented as undirected graphs. In the regime of undirected graphs, the strongest amplifier known has been the Star graph, and the existence of undirected graphs with stronger amplification properties has remained open for over a decade. In this work we present the Comet and Comet-swarm families of undirected graphs. We show that for a range of fitness values of the mutants, the Comet and Cometswarm graphs have fixation probability strictly larger than the fixation probability of the Star graph, for fixed population size and at the limit of large populations, respectively. ","lang":"eng"}],"issue":"1","type":"journal_article","pubrep_id":"938","file":[{"file_size":1536783,"content_type":"application/pdf","creator":"system","access_level":"open_access","file_name":"IST-2018-938-v1+1_2017_Pavlogiannis_Amplification_on.pdf","checksum":"7d05cbdd914e194a019c0f91fb64e9a8","date_created":"2018-12-12T10:18:35Z","date_updated":"2020-07-14T12:46:36Z","relation":"main_file","file_id":"5357"}],"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"512","title":"Amplification on undirected population structures: Comets beat stars","status":"public","ddc":["004"],"intvolume":" 7","day":"06","has_accepted_license":"1","article_processing_charge":"No","scopus_import":1,"date_published":"2017-03-06T00:00:00Z","publication":"Scientific Reports","citation":{"ama":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. Amplification on undirected population structures: Comets beat stars. Scientific Reports. 2017;7(1). doi:10.1038/s41598-017-00107-w","apa":"Pavlogiannis, A., Tkadlec, J., Chatterjee, K., & Nowak, M. (2017). Amplification on undirected population structures: Comets beat stars. Scientific Reports. Nature Publishing Group. https://doi.org/10.1038/s41598-017-00107-w","ieee":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. Nowak, “Amplification on undirected population structures: Comets beat stars,” Scientific Reports, vol. 7, no. 1. Nature Publishing Group, 2017.","ista":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. 2017. Amplification on undirected population structures: Comets beat stars. Scientific Reports. 7(1), 82.","short":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Scientific Reports 7 (2017).","mla":"Pavlogiannis, Andreas, et al. “Amplification on Undirected Population Structures: Comets Beat Stars.” Scientific Reports, vol. 7, no. 1, 82, Nature Publishing Group, 2017, doi:10.1038/s41598-017-00107-w.","chicago":"Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin Nowak. “Amplification on Undirected Population Structures: Comets Beat Stars.” Scientific Reports. Nature Publishing Group, 2017. https://doi.org/10.1038/s41598-017-00107-w."},"file_date_updated":"2020-07-14T12:46:36Z","publist_id":"7307","ec_funded":1,"article_number":"82","author":[{"orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","first_name":"Andreas","full_name":"Pavlogiannis, Andreas"},{"full_name":"Tkadlec, Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1097-9684","first_name":"Josef","last_name":"Tkadlec"},{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5449"}]},"date_created":"2018-12-11T11:46:53Z","date_updated":"2023-02-23T12:26:57Z","volume":7,"year":"2017","publication_status":"published","department":[{"_id":"KrCh"}],"publisher":"Nature Publishing Group","month":"03","publication_identifier":{"issn":["20452322"]},"doi":"10.1038/s41598-017-00107-w","language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"call_identifier":"FWF","name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"}]},{"date_published":"2017-12-27T00:00:00Z","article_type":"original","citation":{"ista":"Chatterjee K, Choudhary B, Pavlogiannis A. 2017. Optimal Dyck reachability for data-dependence and Alias analysis. Proceedings of the ACM on Programming Languages. 2(POPL), 30.","apa":"Chatterjee, K., Choudhary, B., & Pavlogiannis, A. (2017). Optimal Dyck reachability for data-dependence and Alias analysis. Proceedings of the ACM on Programming Languages. Los Angeles, CA, United States: Association for Computing Machinery. https://doi.org/10.1145/3158118","ieee":"K. Chatterjee, B. Choudhary, and A. Pavlogiannis, “Optimal Dyck reachability for data-dependence and Alias analysis,” Proceedings of the ACM on Programming Languages, vol. 2, no. POPL. Association for Computing Machinery, 2017.","ama":"Chatterjee K, Choudhary B, Pavlogiannis A. Optimal Dyck reachability for data-dependence and Alias analysis. Proceedings of the ACM on Programming Languages. 2017;2(POPL). doi:10.1145/3158118","chicago":"Chatterjee, Krishnendu, Bhavya Choudhary, and Andreas Pavlogiannis. “Optimal Dyck Reachability for Data-Dependence and Alias Analysis.” Proceedings of the ACM on Programming Languages. Association for Computing Machinery, 2017. https://doi.org/10.1145/3158118.","mla":"Chatterjee, Krishnendu, et al. “Optimal Dyck Reachability for Data-Dependence and Alias Analysis.” Proceedings of the ACM on Programming Languages, vol. 2, no. POPL, 30, Association for Computing Machinery, 2017, doi:10.1145/3158118.","short":"K. Chatterjee, B. Choudhary, A. Pavlogiannis, Proceedings of the ACM on Programming Languages 2 (2017)."},"publication":"Proceedings of the ACM on Programming Languages","has_accepted_license":"1","article_processing_charge":"No","day":"27","scopus_import":"1","file":[{"file_name":"2017_ACMProgLang_Chatterjee.pdf","access_level":"open_access","creator":"cchlebak","content_type":"application/pdf","file_size":460188,"file_id":"10421","relation":"main_file","date_created":"2021-12-07T08:06:28Z","date_updated":"2021-12-07T08:06:28Z","success":1,"checksum":"faa3f7b3fe8aab84b50ed805c26a0ee5"}],"oa_version":"Published Version","intvolume":" 2","title":"Optimal Dyck reachability for data-dependence and Alias analysis","status":"public","ddc":["000"],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","_id":"10416","issue":"POPL","abstract":[{"text":"A fundamental algorithmic problem at the heart of static analysis is Dyck reachability. The input is a graph where the edges are labeled with different types of opening and closing parentheses, and the reachability information is computed via paths whose parentheses are properly matched. We present new results for Dyck reachability problems with applications to alias analysis and data-dependence analysis. Our main contributions, that include improved upper bounds as well as lower bounds that establish optimality guarantees, are as follows: First, we consider Dyck reachability on bidirected graphs, which is the standard way of performing field-sensitive points-to analysis. Given a bidirected graph with n nodes and m edges, we present: (i) an algorithm with worst-case running time O(m + n · α(n)), where α(n) is the inverse Ackermann function, improving the previously known O(n2) time bound; (ii) a matching lower bound that shows that our algorithm is optimal wrt to worst-case complexity; and (iii) an optimal average-case upper bound of O(m) time, improving the previously known O(m · logn) bound. Second, we consider the problem of context-sensitive data-dependence analysis, where the task is to obtain analysis summaries of library code in the presence of callbacks. Our algorithm preprocesses libraries in almost linear time, after which the contribution of the library in the complexity of the client analysis is only linear, and only wrt the number of call sites. Third, we prove that combinatorial algorithms for Dyck reachability on general graphs with truly sub-cubic bounds cannot be obtained without obtaining sub-cubic combinatorial algorithms for Boolean Matrix Multiplication, which is a long-standing open problem. Thus we establish that the existing combinatorial algorithms for Dyck reachability are (conditionally) optimal for general graphs. We also show that the same hardness holds for graphs of constant treewidth. Finally, we provide a prototype implementation of our algorithms for both alias analysis and data-dependence analysis. Our experimental evaluation demonstrates that the new algorithms significantly outperform all existing methods on the two problems, over real-world benchmarks.","lang":"eng"}],"type":"journal_article","language":[{"iso":"eng"}],"doi":"10.1145/3158118","conference":{"start_date":"2018-01-07","location":"Los Angeles, CA, United States","end_date":"2018-01-13","name":"POPL: Programming Languages"},"project":[{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"arxiv":["1910.00241"]},"oa":1,"publication_identifier":{"eissn":["2475-1421"]},"month":"12","volume":2,"date_updated":"2023-02-23T12:27:13Z","date_created":"2021-12-05T23:01:48Z","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5455"}]},"author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Bhavya","last_name":"Choudhary","full_name":"Choudhary, Bhavya"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","first_name":"Andreas","last_name":"Pavlogiannis","full_name":"Pavlogiannis, Andreas"}],"publisher":"Association for Computing Machinery","department":[{"_id":"KrCh"}],"publication_status":"published","year":"2017","acknowledgement":"The research was partly supported by Austrian Science Fund (FWF) Grant No P23499-N23, FWF NFN Grant No S11407-N23 (RiSE/SHiNE), and ERC Start grant (279307: Graph Games).\r\n","ec_funded":1,"file_date_updated":"2021-12-07T08:06:28Z","article_number":"30"},{"date_published":"2017-10-23T00:00:00Z","page":"37","citation":{"chicago":"Chatterjee, Krishnendu, Bhavya Choudhary, and Andreas Pavlogiannis. Optimal Dyck Reachability for Data-Dependence and Alias Analysis. IST Austria, 2017. https://doi.org/10.15479/AT:IST-2017-870-v1-1.","short":"K. Chatterjee, B. Choudhary, A. Pavlogiannis, Optimal Dyck Reachability for Data-Dependence and Alias Analysis, IST Austria, 2017.","mla":"Chatterjee, Krishnendu, et al. Optimal Dyck Reachability for Data-Dependence and Alias Analysis. IST Austria, 2017, doi:10.15479/AT:IST-2017-870-v1-1.","ieee":"K. Chatterjee, B. Choudhary, and A. Pavlogiannis, Optimal Dyck reachability for data-dependence and alias analysis. IST Austria, 2017.","apa":"Chatterjee, K., Choudhary, B., & Pavlogiannis, A. (2017). Optimal Dyck reachability for data-dependence and alias analysis. IST Austria. https://doi.org/10.15479/AT:IST-2017-870-v1-1","ista":"Chatterjee K, Choudhary B, Pavlogiannis A. 2017. Optimal Dyck reachability for data-dependence and alias analysis, IST Austria, 37p.","ama":"Chatterjee K, Choudhary B, Pavlogiannis A. Optimal Dyck Reachability for Data-Dependence and Alias Analysis. IST Austria; 2017. doi:10.15479/AT:IST-2017-870-v1-1"},"article_processing_charge":"No","has_accepted_license":"1","day":"23","file":[{"checksum":"177a84a46e3ac17e87b31534ad16a4c9","date_updated":"2020-07-14T12:46:59Z","date_created":"2018-12-12T11:54:02Z","file_id":"5524","relation":"main_file","creator":"system","content_type":"application/pdf","file_size":960491,"access_level":"open_access","file_name":"IST-2017-870-v1+1_main.pdf"}],"oa_version":"Published Version","pubrep_id":"870","status":"public","ddc":["000"],"title":"Optimal Dyck reachability for data-dependence and alias analysis","_id":"5455","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","abstract":[{"text":"A fundamental algorithmic problem at the heart of static analysis is Dyck reachability. The input is a graphwhere the edges are labeled with different types of opening and closing parentheses, and the reachabilityinformation is computed via paths whose parentheses are properly matched. We present new results for Dyckreachability problems with applications to alias analysis and data-dependence analysis. Our main contributions,that include improved upper bounds as well as lower bounds that establish optimality guarantees, are asfollows:First, we consider Dyck reachability on bidirected graphs, which is the standard way of performing field-sensitive points-to analysis. Given a bidirected graph withnnodes andmedges, we present: (i) an algorithmwith worst-case running timeO(m+n·α(n)), whereα(n)is the inverse Ackermann function, improving thepreviously knownO(n2)time bound; (ii) a matching lower bound that shows that our algorithm is optimalwrt to worst-case complexity; and (iii) an optimal average-case upper bound ofO(m)time, improving thepreviously knownO(m·logn)bound.Second, we consider the problem of context-sensitive data-dependence analysis, where the task is to obtainanalysis summaries of library code in the presence of callbacks. Our algorithm preprocesses libraries in almostlinear time, after which the contribution of the library in the complexity of the client analysis is only linear,and only wrt the number of call sites.Third, we prove that combinatorial algorithms for Dyck reachability on general graphs with truly sub-cubic bounds cannot be obtained without obtaining sub-cubic combinatorial algorithms for Boolean MatrixMultiplication, which is a long-standing open problem. Thus we establish that the existing combinatorialalgorithms for Dyck reachability are (conditionally) optimal for general graphs. We also show that the samehardness holds for graphs of constant treewidth.Finally, we provide a prototype implementation of our algorithms for both alias analysis and data-dependenceanalysis. Our experimental evaluation demonstrates that the new algorithms significantly outperform allexisting methods on the two problems, over real-world benchmarks.","lang":"eng"}],"alternative_title":["IST Austria Technical Report"],"type":"technical_report","language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2017-870-v1-1","oa":1,"publication_identifier":{"issn":["2664-1690"]},"month":"10","date_updated":"2023-02-21T15:54:10Z","date_created":"2018-12-12T11:39:26Z","related_material":{"record":[{"id":"10416","status":"public","relation":"later_version"}]},"author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"last_name":"Choudhary","first_name":"Bhavya","full_name":"Choudhary, Bhavya"},{"orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","first_name":"Andreas","full_name":"Pavlogiannis, Andreas"}],"publisher":"IST Austria","department":[{"_id":"KrCh"}],"publication_status":"published","year":"2017","file_date_updated":"2020-07-14T12:46:59Z"},{"extern":0,"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"}],"file_date_updated":"2020-07-14T12:46:59Z","type":"report","file":[{"creator":"system","file_size":3460985,"content_type":"application/pdf","access_level":"open_access","file_name":"IST-2017-724-v1+1_DataRep_Project_Report_2017.pdf","checksum":"6321792dcfa82bf490f17615a9b22355","date_updated":"2020-07-14T12:46:59Z","date_created":"2018-12-12T11:53:22Z","file_id":"5483","relation":"main_file"}],"date_updated":"2020-07-14T23:05:03Z","date_created":"2018-12-12T11:39:24Z","pubrep_id":"724","author":[{"full_name":"Barbara Petritsch","first_name":"Barbara","last_name":"Petritsch","id":"406048EC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2724-4614"}],"department":[{"_id":"E-Lib"}],"publisher":"IST Austria","status":"public","title":"Implementing the institutional data repository IST DataRep","year":"2017","_id":"5450","day":"26","month":"06","date_published":"2017-06-26T00:00:00Z","oa":1,"main_file_link":[{"url":"https://repository.ist.ac.at/id/eprint/724.","open_access":"1"}],"citation":{"mla":"Petritsch, Barbara. Implementing the Institutional Data Repository IST DataRep. IST Austria, 2017.","short":"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.","ama":"Petritsch B. Implementing the Institutional Data Repository IST DataRep. IST Austria; 2017.","ista":"Petritsch B. 2017. Implementing the institutional data repository IST DataRep, IST Austria,p.","ieee":"B. Petritsch, Implementing the institutional data repository IST DataRep. IST Austria, 2017.","apa":"Petritsch, B. (2017). Implementing the institutional data repository IST DataRep. IST Austria."},"publication_date":"2017-06-26"},{"oa_version":"Published Version","status":"public","title":"Data-centric dynamic partial order reduction","intvolume":" 2","_id":"10417","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","abstract":[{"lang":"eng","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."}],"issue":"POPL","type":"journal_article","date_published":"2017-12-27T00:00:00Z","article_type":"original","publication":"Proceedings of the ACM on Programming Languages","citation":{"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.","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.","short":"M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, K. Vaidya, Proceedings of the ACM on Programming Languages 2 (2017).","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.","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.","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"},"day":"27","article_processing_charge":"No","scopus_import":"1","date_updated":"2023-02-23T12:27:16Z","date_created":"2021-12-05T23:01:49Z","volume":2,"author":[{"last_name":"Chalupa","first_name":"Marek","full_name":"Chalupa, Marek"},{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Pavlogiannis","first_name":"Andreas","orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87","full_name":"Pavlogiannis, Andreas"},{"last_name":"Sinha","first_name":"Nishant","full_name":"Sinha, Nishant"},{"first_name":"Kapil","last_name":"Vaidya","full_name":"Vaidya, Kapil"}],"related_material":{"record":[{"id":"5448","relation":"earlier_version","status":"public"},{"id":"5456","status":"public","relation":"earlier_version"}]},"publication_status":"published","publisher":"Association for Computing Machinery","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.","year":"2017","ec_funded":1,"article_number":"31","language":[{"iso":"eng"}],"conference":{"location":"Los Angeles, CA, United States","start_date":"2018-01-07","end_date":"2018-01-13","name":"POPL: Programming Languages"},"doi":"10.1145/3158119","quality_controlled":"1","project":[{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"}],"oa":1,"external_id":{"arxiv":["1610.01188"]},"main_file_link":[{"open_access":"1","url":"https://dl.acm.org/doi/10.1145/3158119"}],"month":"12","publication_identifier":{"eissn":["2475-1421"]}},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"5456","year":"2017","department":[{"_id":"KrCh"}],"publisher":"IST Austria","ddc":["000"],"status":"public","title":"Data-centric dynamic partial order reduction","publication_status":"published","related_material":{"record":[{"status":"public","relation":"later_version","id":"10417"},{"status":"public","relation":"earlier_version","id":"5448"}]},"pubrep_id":"872","author":[{"first_name":"Marek","last_name":"Chalupa","full_name":"Chalupa, Marek"},{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Pavlogiannis, Andreas","first_name":"Andreas","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722"},{"last_name":"Sinha","first_name":"Nishant","full_name":"Sinha, Nishant"},{"full_name":"Vaidya, Kapil","last_name":"Vaidya","first_name":"Kapil"}],"oa_version":"Published Version","file":[{"date_created":"2018-12-12T11:53:26Z","date_updated":"2020-07-14T12:46:59Z","checksum":"d2635c4cf013000f0a1b09e80f9e4ab7","file_id":"5487","relation":"main_file","creator":"system","file_size":910347,"content_type":"application/pdf","file_name":"IST-2017-872-v1+1_main.pdf","access_level":"open_access"}],"date_updated":"2023-02-23T12:26:54Z","date_created":"2018-12-12T11:39:26Z","type":"technical_report","alternative_title":["IST Austria Technical Report"],"abstract":[{"lang":"eng","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."}],"file_date_updated":"2020-07-14T12:46:59Z","citation":{"ista":"Chalupa M, Chatterjee K, Pavlogiannis A, Sinha N, Vaidya K. 2017. Data-centric dynamic partial order reduction, IST Austria, 36p.","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","ieee":"M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, and K. Vaidya, Data-centric dynamic partial order reduction. IST Austria, 2017.","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","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.","mla":"Chalupa, Marek, et al. Data-Centric Dynamic Partial Order Reduction. IST Austria, 2017, doi:10.15479/AT:IST-2017-872-v1-1.","short":"M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, K. Vaidya, Data-Centric Dynamic Partial Order Reduction, IST Austria, 2017."},"oa":1,"page":"36","date_published":"2017-10-23T00:00:00Z","doi":"10.15479/AT:IST-2017-872-v1-1","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","month":"10","day":"23"},{"file_date_updated":"2020-07-14T12:47:00Z","publist_id":"7263","article_number":"61","date_updated":"2021-01-12T08:02:34Z","date_created":"2018-12-11T11:47:08Z","volume":83,"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","first_name":"Rasmus","last_name":"Ibsen-Jensen"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"}],"publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"KrCh"}],"year":"2017","month":"11","publication_identifier":{"isbn":["978-395977046-0"]},"language":[{"iso":"eng"}],"conference":{"location":"Aalborg, Denmark","start_date":"2017-08-21","end_date":"2017-08-25","name":"MFCS: Mathematical Foundations of Computer Science (SG)"},"doi":"10.4230/LIPIcs.MFCS.2017.61","quality_controlled":"1","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"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"}],"alternative_title":["LIPIcs"],"type":"conference","file":[{"checksum":"2eed5224c0e4e259484a1d71acb8ba6a","date_created":"2018-12-12T10:18:04Z","date_updated":"2020-07-14T12:47:00Z","file_id":"5322","relation":"main_file","creator":"system","content_type":"application/pdf","file_size":535077,"access_level":"open_access","file_name":"IST-2018-924-v1+1_LIPIcs-MFCS-2017-61.pdf"}],"oa_version":"Published Version","pubrep_id":"924","ddc":["004"],"status":"public","title":"Faster Monte Carlo algorithms for fixation probability of the Moran process on undirected graphs","intvolume":" 83","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"551","day":"01","has_accepted_license":"1","scopus_import":1,"date_published":"2017-11-01T00:00:00Z","publication":"Leibniz International Proceedings in Informatics","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","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.","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","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.","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","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.","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."}},{"article_number":"39","license":"https://creativecommons.org/licenses/by/3.0/","ec_funded":1,"publist_id":"7262","file_date_updated":"2020-07-14T12:47:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"KrCh"}],"publication_status":"published","year":"2017","volume":83,"date_created":"2018-12-11T11:47:08Z","date_updated":"2023-02-14T10:06:46Z","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger"},{"full_name":"Svozil, Alexander","first_name":"Alexander","last_name":"Svozil"}],"publication_identifier":{"isbn":["978-395977046-0"]},"month":"11","project":[{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory","call_identifier":"FWF"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","tmp":{"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)","image":"/images/cc_by.png"},"oa":1,"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.MFCS.2017.39","conference":{"end_date":"2017-08-25","start_date":"2017-08-21","location":"Aalborg, Denmark","name":"MFCS: Mathematical Foundations of Computer Science (SG)"},"alternative_title":["LIPIcs"],"type":"conference","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)."}],"intvolume":" 83","title":"Faster algorithms for mean-payoff parity games","ddc":["004"],"status":"public","_id":"552","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"date_updated":"2020-07-14T12:47:00Z","date_created":"2018-12-12T10:16:57Z","checksum":"c67f4866ddbfd555afef1f63ae9a8fc7","relation":"main_file","file_id":"5248","content_type":"application/pdf","file_size":610339,"creator":"system","file_name":"IST-2018-923-v1+1_LIPIcs-MFCS-2017-39.pdf","access_level":"open_access"}],"oa_version":"Published Version","pubrep_id":"923","scopus_import":"1","article_processing_charge":"No","has_accepted_license":"1","day":"01","citation":{"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.","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.","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","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","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.","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."},"publication":"Leibniz International Proceedings in Informatics","date_published":"2017-11-01T00:00:00Z"},{"alternative_title":["LIPIcs"],"type":"conference","abstract":[{"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. ","lang":"eng"}],"intvolume":" 83","ddc":["004"],"title":"Strategy complexity of concurrent safety games","status":"public","_id":"553","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file":[{"date_created":"2018-12-12T10:09:29Z","date_updated":"2020-07-14T12:47:00Z","checksum":"7101facb56ade363205c695d72dbd173","file_id":"4753","relation":"main_file","creator":"system","file_size":549967,"content_type":"application/pdf","file_name":"IST-2018-922-v1+1_LIPIcs-MFCS-2017-55.pdf","access_level":"open_access"}],"oa_version":"Published Version","pubrep_id":"922","scopus_import":1,"has_accepted_license":"1","day":"01","citation":{"short":"K. Chatterjee, K. Hansen, R. Ibsen-Jensen, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","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.","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.","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","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.","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","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."},"publication":"Leibniz International Proceedings in Informatics","date_published":"2017-11-01T00:00:00Z","article_number":"55","publist_id":"7261","file_date_updated":"2020-07-14T12:47:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"KrCh"}],"publication_status":"published","year":"2017","volume":83,"date_created":"2018-12-11T11:47:08Z","date_updated":"2021-01-12T08:02:35Z","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Hansen, Kristofer","first_name":"Kristofer","last_name":"Hansen"},{"last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus"}],"publication_identifier":{"isbn":["978-395977046-0"]},"month":"11","quality_controlled":"1","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"main_file_link":[{"url":"https://arxiv.org/abs/1506.02434","open_access":"1"}],"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.MFCS.2017.55","conference":{"location":"Aalborg, Denmark","start_date":"2017-08-21","end_date":"2017-08-25","name":"MFCS: Mathematical Foundations of Computer Science (SG)"}},{"month":"11","publication_identifier":{"issn":["13645021"]},"doi":"10.1098/rspa.2017.0104","language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1702.03229"}],"quality_controlled":"1","project":[{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"publist_id":"7256","ec_funded":1,"article_number":"0104","author":[{"last_name":"Gerencser","first_name":"Mate","id":"44ECEDF2-F248-11E8-B48F-1D18A9856A87","full_name":"Gerencser, Mate"},{"full_name":"Jentzen, Arnulf","last_name":"Jentzen","first_name":"Arnulf"},{"first_name":"Diyora","last_name":"Salimova","full_name":"Salimova, Diyora"}],"date_updated":"2021-01-12T08:03:04Z","date_created":"2018-12-11T11:47:11Z","volume":473,"year":"2017","publication_status":"published","department":[{"_id":"JaMa"}],"publisher":"Royal Society of London","day":"01","scopus_import":1,"date_published":"2017-11-01T00:00:00Z","publication":"Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences","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","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.","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","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.","short":"M. Gerencser, A. Jentzen, D. Salimova, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 473 (2017).","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.","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."},"abstract":[{"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.","lang":"eng"}],"issue":"2207","type":"journal_article","oa_version":"Submitted Version","_id":"560","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","title":"On stochastic differential equations with arbitrarily slow convergence rates for strong approximation in two space dimensions","intvolume":" 473"},{"year":"2017","publication_status":"published","publisher":"American Mathematical Society","department":[{"_id":"LaEr"}],"author":[{"full_name":"Erdös, László","first_name":"László","last_name":"Erdös","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5366-9603"},{"full_name":"Yau, Horng","last_name":"Yau","first_name":"Horng"}],"date_created":"2018-12-11T11:47:13Z","date_updated":"2022-05-24T06:57:28Z","volume":28,"ec_funded":1,"publist_id":"7247","quality_controlled":"1","project":[{"name":"Random matrices, universality and disordered quantum systems","call_identifier":"FP7","grant_number":"338804","_id":"258DCDE6-B435-11E9-9278-68D0E5697425"}],"doi":"10.1090/cln/028","language":[{"iso":"eng"}],"month":"01","publication_identifier":{"eisbn":["978-1-4704-4194-4"],"isbn":["9-781-4704-3648-3"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"567","status":"public","title":"A Dynamical Approach to Random Matrix Theory","intvolume":" 28","oa_version":"None","type":"book","alternative_title":["Courant Lecture Notes"],"abstract":[{"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","lang":"eng"}],"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.","short":"L. Erdös, H. Yau, A Dynamical Approach to Random Matrix Theory, American Mathematical Society, 2017.","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.","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","ista":"Erdös L, Yau H. 2017. A Dynamical Approach to Random Matrix Theory, American Mathematical Society, 226p.","ama":"Erdös L, Yau H. A Dynamical Approach to Random Matrix Theory. Vol 28. American Mathematical Society; 2017. doi:10.1090/cln/028"},"page":"226","date_published":"2017-01-01T00:00:00Z","series_title":"Courant Lecture Notes","day":"01","article_processing_charge":"No"},{"abstract":[{"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).","lang":"eng"}],"issue":"2","type":"journal_article","oa_version":"Submitted Version","_id":"568","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","status":"public","title":"Persistence of zero sets","intvolume":" 19","day":"01","scopus_import":1,"date_published":"2017-01-01T00:00:00Z","publication":"Homology, Homotopy and Applications","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.","short":"P. Franek, M. Krcál, Homology, Homotopy and Applications 19 (2017) 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.","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","ista":"Franek P, Krcál M. 2017. Persistence of zero sets. Homology, Homotopy and Applications. 19(2), 313–342.","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"},"page":"313 - 342","publist_id":"7246","ec_funded":1,"author":[{"id":"473294AE-F248-11E8-B48F-1D18A9856A87","first_name":"Peter","last_name":"Franek","full_name":"Franek, Peter"},{"id":"33E21118-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","last_name":"Krcál","full_name":"Krcál, Marek"}],"date_updated":"2021-01-12T08:03:12Z","date_created":"2018-12-11T11:47:14Z","volume":19,"year":"2017","publication_status":"published","publisher":"International Press","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"month":"01","publication_identifier":{"issn":["15320073"]},"doi":"10.4310/HHA.2017.v19.n2.a16","language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1507.04310"}],"quality_controlled":"1","project":[{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"},{"name":"Atomic-Resolution Structures of Mitochondrial Respiratory Chain Supercomplexes (H2020)","call_identifier":"H2020","_id":"2590DB08-B435-11E9-9278-68D0E5697425","grant_number":"701309"}]},{"article_number":"e28921","file_date_updated":"2020-07-14T12:47:10Z","ec_funded":1,"publist_id":"7244","publication_status":"published","publisher":"eLife Sciences Publications","department":[{"_id":"CaGu"},{"_id":"JoBo"},{"_id":"NiBa"}],"year":"2017","date_updated":"2021-01-12T08:03:15Z","date_created":"2018-12-11T11:47:14Z","volume":6,"author":[{"full_name":"Lagator, Mato","last_name":"Lagator","first_name":"Mato","id":"345D25EC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Sarikas, Srdjan","id":"35F0286E-F248-11E8-B48F-1D18A9856A87","first_name":"Srdjan","last_name":"Sarikas"},{"last_name":"Acar","first_name":"Hande","orcid":"0000-0003-1986-9753","id":"2DDF136A-F248-11E8-B48F-1D18A9856A87","full_name":"Acar, Hande"},{"full_name":"Bollback, Jonathan P","orcid":"0000-0002-4624-4612","id":"2C6FA9CC-F248-11E8-B48F-1D18A9856A87","last_name":"Bollback","first_name":"Jonathan P"},{"orcid":"0000-0001-6220-2052","id":"47F8433E-F248-11E8-B48F-1D18A9856A87","last_name":"Guet","first_name":"Calin C","full_name":"Guet, Calin C"}],"month":"11","publication_identifier":{"issn":["2050084X"]},"quality_controlled":"1","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7"},{"call_identifier":"H2020","name":"Selective Barriers to Horizontal Gene Transfer","grant_number":"648440","_id":"2578D616-B435-11E9-9278-68D0E5697425"}],"oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"language":[{"iso":"eng"}],"doi":"10.7554/eLife.28921","type":"journal_article","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. "}],"status":"public","title":"Regulatory network structure determines patterns of intermolecular epistasis","ddc":["576"],"intvolume":" 6","_id":"570","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","file":[{"access_level":"open_access","file_name":"IST-2017-918-v1+1_elife-28921-figures-v3.pdf","creator":"system","file_size":8453470,"content_type":"application/pdf","file_id":"5096","relation":"main_file","checksum":"273ab17f33305e4eaafd911ff88e7c5b","date_updated":"2020-07-14T12:47:10Z","date_created":"2018-12-12T10:14:42Z"},{"file_name":"IST-2017-918-v1+2_elife-28921-v3.pdf","access_level":"open_access","creator":"system","file_size":1953221,"content_type":"application/pdf","file_id":"5097","relation":"main_file","date_updated":"2020-07-14T12:47:10Z","date_created":"2018-12-12T10:14:43Z","checksum":"b433f90576c7be597cd43367946f8e7f"}],"pubrep_id":"918","scopus_import":1,"day":"13","has_accepted_license":"1","publication":"eLife","citation":{"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","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","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.","ista":"Lagator M, Sarikas S, Acar H, Bollback JP, Guet CC. 2017. Regulatory network structure determines patterns of intermolecular epistasis. eLife. 6, e28921.","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.","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."},"date_published":"2017-11-13T00:00:00Z"},{"scopus_import":1,"has_accepted_license":"1","day":"06","citation":{"ieee":"F. Spira et al., “Cytokinesis in vertebrate cells initiates by contraction of an equatorial actomyosin network composed of randomly oriented filaments,” eLife, vol. 6. eLife Sciences Publications, 2017.","apa":"Spira, F., Cuylen Haering, S., Mehta, S., Samwer, M., Reversat, A., Verma, A., … Gerlich, D. (2017). Cytokinesis in vertebrate cells initiates by contraction of an equatorial actomyosin network composed of randomly oriented filaments. ELife. eLife Sciences Publications. https://doi.org/10.7554/eLife.30867","ista":"Spira F, Cuylen Haering S, Mehta S, Samwer M, Reversat A, Verma A, Oldenbourg R, Sixt MK, Gerlich D. 2017. Cytokinesis in vertebrate cells initiates by contraction of an equatorial actomyosin network composed of randomly oriented filaments. eLife. 6, e30867.","ama":"Spira F, Cuylen Haering S, Mehta S, et al. Cytokinesis in vertebrate cells initiates by contraction of an equatorial actomyosin network composed of randomly oriented filaments. eLife. 2017;6. doi:10.7554/eLife.30867","chicago":"Spira, Felix, Sara Cuylen Haering, Shalin Mehta, Matthias Samwer, Anne Reversat, Amitabh Verma, Rudolf Oldenbourg, Michael K Sixt, and Daniel Gerlich. “Cytokinesis in Vertebrate Cells Initiates by Contraction of an Equatorial Actomyosin Network Composed of Randomly Oriented Filaments.” ELife. eLife Sciences Publications, 2017. https://doi.org/10.7554/eLife.30867.","short":"F. Spira, S. Cuylen Haering, S. Mehta, M. Samwer, A. Reversat, A. Verma, R. Oldenbourg, M.K. Sixt, D. Gerlich, ELife 6 (2017).","mla":"Spira, Felix, et al. “Cytokinesis in Vertebrate Cells Initiates by Contraction of an Equatorial Actomyosin Network Composed of Randomly Oriented Filaments.” ELife, vol. 6, e30867, eLife Sciences Publications, 2017, doi:10.7554/eLife.30867."},"publication":"eLife","date_published":"2017-11-06T00:00:00Z","type":"journal_article","abstract":[{"lang":"eng","text":"The actomyosin ring generates force to ingress the cytokinetic cleavage furrow in animal cells, yet its filament organization and the mechanism of contractility is not well understood. We quantified actin filament order in human cells using fluorescence polarization microscopy and found that cleavage furrow ingression initiates by contraction of an equatorial actin network with randomly oriented filaments. The network subsequently gradually reoriented actin filaments along the cell equator. This strictly depended on myosin II activity, suggesting local network reorganization by mechanical forces. Cortical laser microsurgery revealed that during cytokinesis progression, mechanical tension increased substantially along the direction of the cell equator, while the network contracted laterally along the pole-to-pole axis without a detectable increase in tension. Our data suggest that an asymmetric increase in cortical tension promotes filament reorientation along the cytokinetic cleavage furrow, which might have implications for diverse other biological processes involving actomyosin rings."}],"intvolume":" 6","ddc":["570"],"status":"public","title":"Cytokinesis in vertebrate cells initiates by contraction of an equatorial actomyosin network composed of randomly oriented filaments","_id":"569","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"access_level":"open_access","file_name":"IST-2017-919-v1+1_elife-30867-figures-v1.pdf","creator":"system","file_size":9666973,"content_type":"application/pdf","file_id":"4829","relation":"main_file","checksum":"ba09c1451153d39e4f4b7cee013e314c","date_updated":"2020-07-14T12:47:10Z","date_created":"2018-12-12T10:10:40Z"},{"relation":"main_file","file_id":"4830","checksum":"01eb51f1d6ad679947415a51c988e137","date_updated":"2020-07-14T12:47:10Z","date_created":"2018-12-12T10:10:41Z","access_level":"open_access","file_name":"IST-2017-919-v1+2_elife-30867-v1.pdf","content_type":"application/pdf","file_size":5951246,"creator":"system"}],"oa_version":"Published Version","pubrep_id":"919","publication_identifier":{"issn":["2050084X"]},"month":"11","quality_controlled":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"language":[{"iso":"eng"}],"doi":"10.7554/eLife.30867","article_number":"e30867","publist_id":"7245","file_date_updated":"2020-07-14T12:47:10Z","publisher":"eLife Sciences Publications","department":[{"_id":"MiSi"}],"publication_status":"published","year":"2017","volume":6,"date_updated":"2023-02-23T12:30:29Z","date_created":"2018-12-11T11:47:14Z","author":[{"first_name":"Felix","last_name":"Spira","full_name":"Spira, Felix"},{"first_name":"Sara","last_name":"Cuylen Haering","full_name":"Cuylen Haering, Sara"},{"full_name":"Mehta, Shalin","first_name":"Shalin","last_name":"Mehta"},{"last_name":"Samwer","first_name":"Matthias","full_name":"Samwer, Matthias"},{"full_name":"Reversat, Anne","orcid":"0000-0003-0666-8928","id":"35B76592-F248-11E8-B48F-1D18A9856A87","last_name":"Reversat","first_name":"Anne"},{"full_name":"Verma, Amitabh","first_name":"Amitabh","last_name":"Verma"},{"first_name":"Rudolf","last_name":"Oldenbourg","full_name":"Oldenbourg, Rudolf"},{"orcid":"0000-0002-6620-9179","id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","last_name":"Sixt","first_name":"Michael K","full_name":"Sixt, Michael K"},{"full_name":"Gerlich, Daniel","first_name":"Daniel","last_name":"Gerlich"}]},{"ec_funded":1,"publist_id":"7243","publisher":"Cell Press","department":[{"_id":"MiSi"}],"publication_status":"published","year":"2017","volume":171,"date_created":"2018-12-11T11:47:15Z","date_updated":"2021-01-12T08:03:15Z","author":[{"orcid":"0000-0001-6120-3723","id":"397A88EE-F248-11E8-B48F-1D18A9856A87","last_name":"Gärtner","first_name":"Florian R","full_name":"Gärtner, Florian R"},{"full_name":"Ahmad, Zerkah","last_name":"Ahmad","first_name":"Zerkah"},{"full_name":"Rosenberger, Gerhild","last_name":"Rosenberger","first_name":"Gerhild"},{"first_name":"Shuxia","last_name":"Fan","full_name":"Fan, Shuxia"},{"full_name":"Nicolai, Leo","last_name":"Nicolai","first_name":"Leo"},{"first_name":"Benjamin","last_name":"Busch","full_name":"Busch, Benjamin"},{"full_name":"Yavuz, Gökce","last_name":"Yavuz","first_name":"Gökce"},{"last_name":"Luckner","first_name":"Manja","full_name":"Luckner, Manja"},{"first_name":"Hellen","last_name":"Ishikawa Ankerhold","full_name":"Ishikawa Ankerhold, Hellen"},{"last_name":"Hennel","first_name":"Roman","full_name":"Hennel, Roman"},{"full_name":"Benechet, Alexandre","first_name":"Alexandre","last_name":"Benechet"},{"first_name":"Michael","last_name":"Lorenz","full_name":"Lorenz, Michael"},{"first_name":"Sue","last_name":"Chandraratne","full_name":"Chandraratne, Sue"},{"last_name":"Schubert","first_name":"Irene","full_name":"Schubert, Irene"},{"full_name":"Helmer, Sebastian","first_name":"Sebastian","last_name":"Helmer"},{"first_name":"Bianca","last_name":"Striednig","full_name":"Striednig, Bianca"},{"first_name":"Konstantin","last_name":"Stark","full_name":"Stark, Konstantin"},{"full_name":"Janko, Marek","first_name":"Marek","last_name":"Janko"},{"last_name":"Böttcher","first_name":"Ralph","full_name":"Böttcher, Ralph"},{"full_name":"Verschoor, Admar","last_name":"Verschoor","first_name":"Admar"},{"full_name":"Leon, Catherine","last_name":"Leon","first_name":"Catherine"},{"first_name":"Christian","last_name":"Gachet","full_name":"Gachet, Christian"},{"full_name":"Gudermann, Thomas","first_name":"Thomas","last_name":"Gudermann"},{"full_name":"Mederos Y Schnitzler, Michael","last_name":"Mederos Y Schnitzler","first_name":"Michael"},{"first_name":"Zachary","last_name":"Pincus","full_name":"Pincus, Zachary"},{"full_name":"Iannacone, Matteo","first_name":"Matteo","last_name":"Iannacone"},{"full_name":"Haas, Rainer","last_name":"Haas","first_name":"Rainer"},{"last_name":"Wanner","first_name":"Gerhard","full_name":"Wanner, Gerhard"},{"last_name":"Lauber","first_name":"Kirsten","full_name":"Lauber, Kirsten"},{"first_name":"Michael K","last_name":"Sixt","id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6620-9179","full_name":"Sixt, Michael K"},{"full_name":"Massberg, Steffen","last_name":"Massberg","first_name":"Steffen"}],"publication_identifier":{"issn":["00928674"]},"month":"11","project":[{"grant_number":"747687","_id":"260AA4E2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Mechanical Adaptation of Lamellipodial Actin Networks in Migrating Cells"}],"quality_controlled":"1","language":[{"iso":"eng"}],"doi":"10.1016/j.cell.2017.11.001","type":"journal_article","issue":"6","abstract":[{"text":"Blood platelets are critical for hemostasis and thrombosis and play diverse roles during immune responses. Despite these versatile tasks in mammalian biology, their skills on a cellular level are deemed limited, mainly consisting in rolling, adhesion, and aggregate formation. Here, we identify an unappreciated asset of platelets and show that adherent platelets use adhesion receptors to mechanically probe the adhesive substrate in their local microenvironment. When actomyosin-dependent traction forces overcome substrate resistance, platelets migrate and pile up the adhesive substrate together with any bound particulate material. They use this ability to act as cellular scavengers, scanning the vascular surface for potential invaders and collecting deposited bacteria. Microbe collection by migrating platelets boosts the activity of professional phagocytes, exacerbating inflammatory tissue injury in sepsis. This assigns platelets a central role in innate immune responses and identifies them as potential targets to dampen inflammatory tissue damage in clinical scenarios of severe systemic infection. In addition to their role in thrombosis and hemostasis, platelets can also migrate to sites of infection to help trap bacteria and clear the vascular surface.","lang":"eng"}],"intvolume":" 171","status":"public","title":"Migrating platelets are mechano scavengers that collect and bundle bacteria","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"571","oa_version":"None","scopus_import":1,"day":"30","page":"1368 - 1382","citation":{"ama":"Gärtner FR, Ahmad Z, Rosenberger G, et al. Migrating platelets are mechano scavengers that collect and bundle bacteria. Cell Press. 2017;171(6):1368-1382. doi:10.1016/j.cell.2017.11.001","apa":"Gärtner, F. R., Ahmad, Z., Rosenberger, G., Fan, S., Nicolai, L., Busch, B., … Massberg, S. (2017). Migrating platelets are mechano scavengers that collect and bundle bacteria. Cell Press. Cell Press. https://doi.org/10.1016/j.cell.2017.11.001","ieee":"F. R. Gärtner et al., “Migrating platelets are mechano scavengers that collect and bundle bacteria,” Cell Press, vol. 171, no. 6. Cell Press, pp. 1368–1382, 2017.","ista":"Gärtner FR, Ahmad Z, Rosenberger G, Fan S, Nicolai L, Busch B, Yavuz G, Luckner M, Ishikawa Ankerhold H, Hennel R, Benechet A, Lorenz M, Chandraratne S, Schubert I, Helmer S, Striednig B, Stark K, Janko M, Böttcher R, Verschoor A, Leon C, Gachet C, Gudermann T, Mederos Y Schnitzler M, Pincus Z, Iannacone M, Haas R, Wanner G, Lauber K, Sixt MK, Massberg S. 2017. Migrating platelets are mechano scavengers that collect and bundle bacteria. Cell Press. 171(6), 1368–1382.","short":"F.R. Gärtner, Z. Ahmad, G. Rosenberger, S. Fan, L. Nicolai, B. Busch, G. Yavuz, M. Luckner, H. Ishikawa Ankerhold, R. Hennel, A. Benechet, M. Lorenz, S. Chandraratne, I. Schubert, S. Helmer, B. Striednig, K. Stark, M. Janko, R. Böttcher, A. Verschoor, C. Leon, C. Gachet, T. Gudermann, M. Mederos Y Schnitzler, Z. Pincus, M. Iannacone, R. Haas, G. Wanner, K. Lauber, M.K. Sixt, S. Massberg, Cell Press 171 (2017) 1368–1382.","mla":"Gärtner, Florian R., et al. “Migrating Platelets Are Mechano Scavengers That Collect and Bundle Bacteria.” Cell Press, vol. 171, no. 6, Cell Press, 2017, pp. 1368–82, doi:10.1016/j.cell.2017.11.001.","chicago":"Gärtner, Florian R, Zerkah Ahmad, Gerhild Rosenberger, Shuxia Fan, Leo Nicolai, Benjamin Busch, Gökce Yavuz, et al. “Migrating Platelets Are Mechano Scavengers That Collect and Bundle Bacteria.” Cell Press. Cell Press, 2017. https://doi.org/10.1016/j.cell.2017.11.001."},"publication":"Cell Press","date_published":"2017-11-30T00:00:00Z"},{"article_number":"2587","publist_id":"7242","file_date_updated":"2020-07-14T12:47:10Z","year":"2017","publisher":"MDPI","department":[{"_id":"JiFr"}],"publication_status":"published","author":[{"last_name":"Olatunji","first_name":"Damilola","full_name":"Olatunji, Damilola"},{"full_name":"Geelen, Danny","first_name":"Danny","last_name":"Geelen"},{"orcid":"0000-0001-7241-2328","id":"362BF7FE-F248-11E8-B48F-1D18A9856A87","last_name":"Verstraeten","first_name":"Inge","full_name":"Verstraeten, Inge"}],"volume":18,"date_created":"2018-12-11T11:47:15Z","date_updated":"2021-01-12T08:03:16Z","month":"12","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"quality_controlled":"1","doi":"10.3390/ijms18122587","language":[{"iso":"eng"}],"type":"journal_article","issue":"12","abstract":[{"text":"In this review, we summarize the different biosynthesis-related pathways that contribute to the regulation of endogenous auxin in plants. We demonstrate that all known genes involved in auxin biosynthesis also have a role in root formation, from the initiation of a root meristem during embryogenesis to the generation of a functional root system with a primary root, secondary lateral root branches and adventitious roots. Furthermore, the versatile adaptation of root development in response to environmental challenges is mediated by both local and distant control of auxin biosynthesis. In conclusion, auxin homeostasis mediated by spatial and temporal regulation of auxin biosynthesis plays a central role in determining root architecture.","lang":"eng"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"572","intvolume":" 18","title":"Control of endogenous auxin levels in plant root development","ddc":["580"],"status":"public","pubrep_id":"917","file":[{"access_level":"open_access","file_name":"IST-2017-917-v1+1_ijms-18-02587.pdf","file_size":920962,"content_type":"application/pdf","creator":"system","relation":"main_file","file_id":"4718","checksum":"82d51f11e493f7eec02976d9a9a9805e","date_updated":"2020-07-14T12:47:10Z","date_created":"2018-12-12T10:08:55Z"}],"oa_version":"Published Version","scopus_import":"1","article_processing_charge":"No","has_accepted_license":"1","day":"01","citation":{"ama":"Olatunji D, Geelen D, Verstraeten I. Control of endogenous auxin levels in plant root development. International Journal of Molecular Sciences. 2017;18(12). doi:10.3390/ijms18122587","ieee":"D. Olatunji, D. Geelen, and I. Verstraeten, “Control of endogenous auxin levels in plant root development,” International Journal of Molecular Sciences, vol. 18, no. 12. MDPI, 2017.","apa":"Olatunji, D., Geelen, D., & Verstraeten, I. (2017). Control of endogenous auxin levels in plant root development. International Journal of Molecular Sciences. MDPI. https://doi.org/10.3390/ijms18122587","ista":"Olatunji D, Geelen D, Verstraeten I. 2017. Control of endogenous auxin levels in plant root development. International Journal of Molecular Sciences. 18(12), 2587.","short":"D. Olatunji, D. Geelen, I. Verstraeten, International Journal of Molecular Sciences 18 (2017).","mla":"Olatunji, Damilola, et al. “Control of Endogenous Auxin Levels in Plant Root Development.” International Journal of Molecular Sciences, vol. 18, no. 12, 2587, MDPI, 2017, doi:10.3390/ijms18122587.","chicago":"Olatunji, Damilola, Danny Geelen, and Inge Verstraeten. “Control of Endogenous Auxin Levels in Plant Root Development.” International Journal of Molecular Sciences. MDPI, 2017. https://doi.org/10.3390/ijms18122587."},"publication":"International Journal of Molecular Sciences","date_published":"2017-12-01T00:00:00Z"},{"has_accepted_license":"1","day":"14","scopus_import":1,"date_published":"2017-07-14T00:00:00Z","citation":{"short":"N. Camus, E. Yakaboylu, L. Fechner, M. Klaiber, M. Laux, Y. Mi, K. Hatsagortsyan, T. Pfeifer, C. Keitel, R. Moshammer, in:, American Physical Society, 2017.","mla":"Camus, Nicolas, et al. Experimental Evidence for Wigner’s Tunneling Time. Vol. 999, no. 1, 012004, American Physical Society, 2017, doi:10.1088/1742-6596/999/1/012004.","chicago":"Camus, Nicolas, Enderalp Yakaboylu, Lutz Fechner, Michael Klaiber, Martin Laux, Yonghao Mi, Karen Hatsagortsyan, Thomas Pfeifer, Cristoph Keitel, and Robert Moshammer. “Experimental Evidence for Wigner’s Tunneling Time,” Vol. 999. American Physical Society, 2017. https://doi.org/10.1088/1742-6596/999/1/012004.","ama":"Camus N, Yakaboylu E, Fechner L, et al. Experimental evidence for Wigner’s tunneling time. In: Vol 999. American Physical Society; 2017. doi:10.1088/1742-6596/999/1/012004","ieee":"N. Camus et al., “Experimental evidence for Wigner’s tunneling time,” presented at the Annual International Laser Physics Workshop LPHYS, Kazan, Russian Federation, 2017, vol. 999, no. 1.","apa":"Camus, N., Yakaboylu, E., Fechner, L., Klaiber, M., Laux, M., Mi, Y., … Moshammer, R. (2017). Experimental evidence for Wigner’s tunneling time (Vol. 999). Presented at the Annual International Laser Physics Workshop LPHYS, Kazan, Russian Federation: American Physical Society. https://doi.org/10.1088/1742-6596/999/1/012004","ista":"Camus N, Yakaboylu E, Fechner L, Klaiber M, Laux M, Mi Y, Hatsagortsyan K, Pfeifer T, Keitel C, Moshammer R. 2017. Experimental evidence for Wigner’s tunneling time. Annual International Laser Physics Workshop LPHYS, Journal of Physics: Conference Series, vol. 999, 012004."},"issue":"1","abstract":[{"lang":"eng","text":"Tunneling of a particle through a potential barrier remains one of the most remarkable quantum phenomena. Owing to advances in laser technology, electric fields comparable to those electrons experience in atoms are readily generated and open opportunities to dynamically investigate the process of electron tunneling through the potential barrier formed by the superposition of both laser and atomic fields. Attosecond-time and angstrom-space resolution of the strong laser-field technique allow to address fundamental questions related to tunneling, which are still open and debated: Which time is spent under the barrier and what momentum is picked up by the particle in the meantime? In this combined experimental and theoretical study we demonstrate that for strong-field ionization the leading quantum mechanical Wigner treatment for the time resolved description of tunneling is valid. We achieve a high sensitivity on the tunneling barrier and unambiguously isolate its effects by performing a differential study of two systems with almost identical tunneling geometry. Moreover, working with a low frequency laser, we essentially limit the non-adiabaticity of the process as a major source of uncertainty. The agreement between experiment and theory implies two substantial corrections with respect to the widely employed quasiclassical treatment: In addition to a non-vanishing longitudinal momentum along the laser field-direction we provide clear evidence for a non-zero tunneling time delay. This addresses also the fundamental question how the transition occurs from the tunnel barrier to free space classical evolution of the ejected electron."}],"alternative_title":["Journal of Physics: Conference Series"],"type":"conference","oa_version":"Published Version","file":[{"relation":"main_file","file_id":"5871","checksum":"6e70b525a84f6d5fb175c48e9f5cb59a","date_updated":"2020-07-14T12:46:00Z","date_created":"2019-01-22T08:34:10Z","access_level":"open_access","file_name":"2017_Physics_Camus.pdf","content_type":"application/pdf","file_size":949321,"creator":"dernst"}],"intvolume":" 999","ddc":["530"],"status":"public","title":"Experimental evidence for Wigner's tunneling time","_id":"313","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["17426588"]},"month":"07","language":[{"iso":"eng"}],"doi":"10.1088/1742-6596/999/1/012004","conference":{"start_date":"2017-08-17","location":"Kazan, Russian Federation","end_date":"2017-08-21","name":"Annual International Laser Physics Workshop LPHYS"},"quality_controlled":"1","external_id":{"arxiv":["1611.03701"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"publist_id":"7552","file_date_updated":"2020-07-14T12:46:00Z","article_number":"012004","volume":999,"date_created":"2018-12-11T11:45:46Z","date_updated":"2023-02-23T12:36:07Z","related_material":{"record":[{"status":"public","relation":"later_version","id":"6013"}]},"author":[{"full_name":"Camus, Nicolas","first_name":"Nicolas","last_name":"Camus"},{"full_name":"Yakaboylu, Enderalp","orcid":"0000-0001-5973-0874","id":"38CB71F6-F248-11E8-B48F-1D18A9856A87","last_name":"Yakaboylu","first_name":"Enderalp"},{"full_name":"Fechner, Lutz","last_name":"Fechner","first_name":"Lutz"},{"full_name":"Klaiber, Michael","first_name":"Michael","last_name":"Klaiber"},{"last_name":"Laux","first_name":"Martin","full_name":"Laux, Martin"},{"full_name":"Mi, Yonghao","last_name":"Mi","first_name":"Yonghao"},{"full_name":"Hatsagortsyan, Karen","last_name":"Hatsagortsyan","first_name":"Karen"},{"full_name":"Pfeifer, Thomas","first_name":"Thomas","last_name":"Pfeifer"},{"full_name":"Keitel, Cristoph","last_name":"Keitel","first_name":"Cristoph"},{"first_name":"Robert","last_name":"Moshammer","full_name":"Moshammer, Robert"}],"publisher":"American Physical Society","department":[{"_id":"MiLe"}],"publication_status":"published","year":"2017"},{"scopus_import":1,"day":"14","publication":"Physical Review Letters","citation":{"ama":"Camus N, Yakaboylu E, Fechner L, et al. Experimental evidence for quantum tunneling time. Physical Review Letters. 2017;119(2). doi:10.1103/PhysRevLett.119.023201","ista":"Camus N, Yakaboylu E, Fechner L, Klaiber M, Laux M, Mi Y, Hatsagortsyan KZ, Pfeifer T, Keitel CH, Moshammer R. 2017. Experimental evidence for quantum tunneling time. Physical Review Letters. 119(2), 023201.","apa":"Camus, N., Yakaboylu, E., Fechner, L., Klaiber, M., Laux, M., Mi, Y., … Moshammer, R. (2017). Experimental evidence for quantum tunneling time. Physical Review Letters. American Physical Society. https://doi.org/10.1103/PhysRevLett.119.023201","ieee":"N. Camus et al., “Experimental evidence for quantum tunneling time,” Physical Review Letters, vol. 119, no. 2. American Physical Society, 2017.","mla":"Camus, Nicolas, et al. “Experimental Evidence for Quantum Tunneling Time.” Physical Review Letters, vol. 119, no. 2, 023201, American Physical Society, 2017, doi:10.1103/PhysRevLett.119.023201.","short":"N. Camus, E. Yakaboylu, L. Fechner, M. Klaiber, M. Laux, Y. Mi, K.Z. Hatsagortsyan, T. Pfeifer, C.H. Keitel, R. Moshammer, Physical Review Letters 119 (2017).","chicago":"Camus, Nicolas, Enderalp Yakaboylu, Lutz Fechner, Michael Klaiber, Martin Laux, Yonghao Mi, Karen Z. Hatsagortsyan, Thomas Pfeifer, Christoph H. Keitel, and Robert Moshammer. “Experimental Evidence for Quantum Tunneling Time.” Physical Review Letters. American Physical Society, 2017. https://doi.org/10.1103/PhysRevLett.119.023201."},"date_published":"2017-07-14T00:00:00Z","type":"journal_article","abstract":[{"text":"The first hundred attoseconds of the electron dynamics during strong field tunneling ionization are investigated. We quantify theoretically how the electron’s classical trajectories in the continuum emerge from the tunneling process and test the results with those achieved in parallel from attoclock measurements. An especially high sensitivity on the tunneling barrier is accomplished here by comparing the momentum distributions of two atomic species of slightly deviating atomic potentials (argon and krypton) being ionized under absolutely identical conditions with near-infrared laser pulses (1300 nm). The agreement between experiment and theory provides clear evidence for a nonzero tunneling time delay and a nonvanishing longitudinal momentum of the electron at the “tunnel exit.”","lang":"eng"}],"issue":"2","status":"public","title":"Experimental evidence for quantum tunneling time","intvolume":" 119","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6013","oa_version":"Preprint","month":"07","publication_identifier":{"issn":["0031-9007"],"eissn":["1079-7114"]},"quality_controlled":"1","main_file_link":[{"url":"https://arxiv.org/abs/1611.03701","open_access":"1"}],"external_id":{"arxiv":["1611.03701"]},"oa":1,"language":[{"iso":"eng"}],"doi":"10.1103/PhysRevLett.119.023201","article_number":"023201","publication_status":"published","department":[{"_id":"MiLe"}],"publisher":"American Physical Society","year":"2017","date_updated":"2023-02-23T11:13:36Z","date_created":"2019-02-14T15:24:13Z","volume":119,"author":[{"full_name":"Camus, Nicolas","first_name":"Nicolas","last_name":"Camus"},{"full_name":"Yakaboylu, Enderalp","id":"38CB71F6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5973-0874","first_name":"Enderalp","last_name":"Yakaboylu"},{"last_name":"Fechner","first_name":"Lutz","full_name":"Fechner, Lutz"},{"full_name":"Klaiber, Michael","first_name":"Michael","last_name":"Klaiber"},{"first_name":"Martin","last_name":"Laux","full_name":"Laux, Martin"},{"full_name":"Mi, Yonghao","last_name":"Mi","first_name":"Yonghao"},{"last_name":"Hatsagortsyan","first_name":"Karen Z.","full_name":"Hatsagortsyan, Karen Z."},{"last_name":"Pfeifer","first_name":"Thomas","full_name":"Pfeifer, Thomas"},{"full_name":"Keitel, Christoph H.","last_name":"Keitel","first_name":"Christoph H."},{"first_name":"Robert","last_name":"Moshammer","full_name":"Moshammer, Robert"}],"related_material":{"record":[{"id":"313","status":"public","relation":"earlier_version"}]}},{"publist_id":"7200","ec_funded":1,"date_updated":"2021-01-12T08:05:53Z","date_created":"2018-12-11T11:47:27Z","volume":10677,"author":[{"last_name":"Brody","first_name":"Joshua","full_name":"Brody, Joshua"},{"last_name":"Dziembowski","first_name":"Stefan","full_name":"Dziembowski, Stefan"},{"last_name":"Faust","first_name":"Sebastian","full_name":"Faust, Sebastian"},{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"}],"publication_status":"published","editor":[{"full_name":"Kalai, Yael","last_name":"Kalai","first_name":"Yael"},{"last_name":"Reyzin","first_name":"Leonid","full_name":"Reyzin, Leonid"}],"department":[{"_id":"KrPi"}],"publisher":"Springer","year":"2017","month":"11","publication_identifier":{"isbn":["978-331970499-9"]},"language":[{"iso":"eng"}],"conference":{"location":"Baltimore, MD, United States","start_date":"2017-11-12","end_date":"2017-11-15","name":"TCC: Theory of Cryptography Conference"},"doi":"10.1007/978-3-319-70500-2_3","quality_controlled":"1","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks"}],"oa":1,"main_file_link":[{"url":"https://eprint.iacr.org/2016/536","open_access":"1"}],"abstract":[{"lang":"eng","text":"Position based cryptography (PBC), proposed in the seminal work of Chandran, Goyal, Moriarty, and Ostrovsky (SIAM J. Computing, 2014), aims at constructing cryptographic schemes in which the identity of the user is his geographic position. Chandran et al. construct PBC schemes for secure positioning and position-based key agreement in the bounded-storage model (Maurer, J. Cryptology, 1992). Apart from bounded memory, their security proofs need a strong additional restriction on the power of the adversary: he cannot compute joint functions of his inputs. Removing this assumption is left as an open problem. We show that an answer to this question would resolve a long standing open problem in multiparty communication complexity: finding a function that is hard to compute with low communication complexity in the simultaneous message model, but easy to compute in the fully adaptive model. On a more positive side: we also show some implications in the other direction, i.e.: we prove that lower bounds on the communication complexity of certain multiparty problems imply existence of PBC primitives. Using this result we then show two attractive ways to “bypass” our hardness result: the first uses the random oracle model, the second weakens the locality requirement in the bounded-storage model to online computability. The random oracle construction is arguably one of the simplest proposed so far in this area. Our results indicate that constructing improved provably secure protocols for PBC requires a better understanding of multiparty communication complexity. This is yet another example where negative results in one area (in our case: lower bounds in multiparty communication complexity) can be used to construct secure cryptographic schemes."}],"alternative_title":["LNCS"],"type":"conference","oa_version":"Submitted Version","title":"Position based cryptography and multiparty communication complexity","status":"public","intvolume":" 10677","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"605","day":"05","scopus_import":1,"date_published":"2017-11-05T00:00:00Z","page":"56 - 81","citation":{"chicago":"Brody, Joshua, Stefan Dziembowski, Sebastian Faust, and Krzysztof Z Pietrzak. “Position Based Cryptography and Multiparty Communication Complexity.” edited by Yael Kalai and Leonid Reyzin, 10677:56–81. Springer, 2017. https://doi.org/10.1007/978-3-319-70500-2_3.","mla":"Brody, Joshua, et al. Position Based Cryptography and Multiparty Communication Complexity. Edited by Yael Kalai and Leonid Reyzin, vol. 10677, Springer, 2017, pp. 56–81, doi:10.1007/978-3-319-70500-2_3.","short":"J. Brody, S. Dziembowski, S. Faust, K.Z. Pietrzak, in:, Y. Kalai, L. Reyzin (Eds.), Springer, 2017, pp. 56–81.","ista":"Brody J, Dziembowski S, Faust S, Pietrzak KZ. 2017. Position based cryptography and multiparty communication complexity. TCC: Theory of Cryptography Conference, LNCS, vol. 10677, 56–81.","apa":"Brody, J., Dziembowski, S., Faust, S., & Pietrzak, K. Z. (2017). Position based cryptography and multiparty communication complexity. In Y. Kalai & L. Reyzin (Eds.) (Vol. 10677, pp. 56–81). Presented at the TCC: Theory of Cryptography Conference, Baltimore, MD, United States: Springer. https://doi.org/10.1007/978-3-319-70500-2_3","ieee":"J. Brody, S. Dziembowski, S. Faust, and K. Z. Pietrzak, “Position based cryptography and multiparty communication complexity,” presented at the TCC: Theory of Cryptography Conference, Baltimore, MD, United States, 2017, vol. 10677, pp. 56–81.","ama":"Brody J, Dziembowski S, Faust S, Pietrzak KZ. Position based cryptography and multiparty communication complexity. In: Kalai Y, Reyzin L, eds. Vol 10677. Springer; 2017:56-81. doi:10.1007/978-3-319-70500-2_3"}}]