[{"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","publication_status":"published","publisher":"Association for Computing Machinery","department":[{"_id":"KrCh"}],"author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"last_name":"Choudhary","first_name":"Bhavya","full_name":"Choudhary, Bhavya"},{"full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis","first_name":"Andreas","orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5455"}]},"date_updated":"2023-02-23T12:27:13Z","date_created":"2021-12-05T23:01:48Z","volume":2,"article_number":"30","file_date_updated":"2021-12-07T08:06:28Z","ec_funded":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,"external_id":{"arxiv":["1910.00241"]},"quality_controlled":"1","project":[{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering"}],"conference":{"end_date":"2018-01-13","location":"Los Angeles, CA, United States","start_date":"2018-01-07","name":"POPL: Programming Languages"},"doi":"10.1145/3158118","language":[{"iso":"eng"}],"month":"12","publication_identifier":{"eissn":["2475-1421"]},"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","_id":"10416","title":"Optimal Dyck reachability for data-dependence and Alias analysis","status":"public","ddc":["000"],"intvolume":" 2","file":[{"file_size":460188,"content_type":"application/pdf","creator":"cchlebak","file_name":"2017_ACMProgLang_Chatterjee.pdf","access_level":"open_access","date_updated":"2021-12-07T08:06:28Z","date_created":"2021-12-07T08:06:28Z","checksum":"faa3f7b3fe8aab84b50ed805c26a0ee5","success":1,"relation":"main_file","file_id":"10421"}],"oa_version":"Published Version","type":"journal_article","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"}],"issue":"POPL","publication":"Proceedings of the ACM on Programming Languages","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.","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.","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","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)."},"article_type":"original","date_published":"2017-12-27T00:00:00Z","scopus_import":"1","day":"27","has_accepted_license":"1","article_processing_charge":"No"},{"year":"2017","publication_status":"published","publisher":"IST Austria","department":[{"_id":"KrCh"}],"author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Choudhary, Bhavya","first_name":"Bhavya","last_name":"Choudhary"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","first_name":"Andreas","last_name":"Pavlogiannis","full_name":"Pavlogiannis, Andreas"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"10416"}]},"date_updated":"2023-02-21T15:54:10Z","date_created":"2018-12-12T11:39:26Z","file_date_updated":"2020-07-14T12:46:59Z","oa":1,"doi":"10.15479/AT:IST-2017-870-v1-1","language":[{"iso":"eng"}],"month":"10","publication_identifier":{"issn":["2664-1690"]},"_id":"5455","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","ddc":["000"],"title":"Optimal Dyck reachability for data-dependence and alias analysis","status":"public","pubrep_id":"870","file":[{"content_type":"application/pdf","file_size":960491,"creator":"system","file_name":"IST-2017-870-v1+1_main.pdf","access_level":"open_access","date_created":"2018-12-12T11:54:02Z","date_updated":"2020-07-14T12:46:59Z","checksum":"177a84a46e3ac17e87b31534ad16a4c9","relation":"main_file","file_id":"5524"}],"oa_version":"Published Version","type":"technical_report","alternative_title":["IST Austria Technical Report"],"abstract":[{"lang":"eng","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."}],"citation":{"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.","short":"K. Chatterjee, B. Choudhary, A. Pavlogiannis, Optimal Dyck Reachability for Data-Dependence and Alias Analysis, IST Austria, 2017.","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.","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","ista":"Chatterjee K, Choudhary B, Pavlogiannis A. 2017. Optimal Dyck reachability for data-dependence and alias analysis, IST Austria, 37p.","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","ieee":"K. Chatterjee, B. Choudhary, and A. Pavlogiannis, Optimal Dyck reachability for data-dependence and alias analysis. IST Austria, 2017."},"page":"37","date_published":"2017-10-23T00:00:00Z","day":"23","article_processing_charge":"No","has_accepted_license":"1"},{"publication_status":"published","publisher":"Association for Computing Machinery","department":[{"_id":"KrCh"}],"year":"2017","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.","date_updated":"2023-02-23T12:27:16Z","date_created":"2021-12-05T23:01:49Z","volume":2,"author":[{"first_name":"Marek","last_name":"Chalupa","full_name":"Chalupa, Marek"},{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"first_name":"Andreas","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas"},{"full_name":"Sinha, Nishant","first_name":"Nishant","last_name":"Sinha"},{"last_name":"Vaidya","first_name":"Kapil","full_name":"Vaidya, Kapil"}],"related_material":{"record":[{"id":"5448","relation":"earlier_version","status":"public"},{"status":"public","relation":"earlier_version","id":"5456"}]},"article_number":"31","ec_funded":1,"quality_controlled":"1","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"oa":1,"main_file_link":[{"url":"https://dl.acm.org/doi/10.1145/3158119","open_access":"1"}],"external_id":{"arxiv":["1610.01188"]},"language":[{"iso":"eng"}],"conference":{"end_date":"2018-01-13","start_date":"2018-01-07","location":"Los Angeles, CA, United States","name":"POPL: Programming Languages"},"doi":"10.1145/3158119","month":"12","publication_identifier":{"eissn":["2475-1421"]},"title":"Data-centric dynamic partial order reduction","status":"public","intvolume":" 2","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","_id":"10417","oa_version":"Published Version","type":"journal_article","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","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.","short":"M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, K. Vaidya, Proceedings of the ACM on Programming Languages 2 (2017).","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.","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","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.","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"},"date_published":"2017-12-27T00:00:00Z","scopus_import":"1","day":"27","article_processing_charge":"No"},{"oa":1,"citation":{"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.","short":"M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, K. Vaidya, Data-Centric Dynamic Partial Order Reduction, IST Austria, 2017.","mla":"Chalupa, Marek, et al. Data-Centric Dynamic Partial Order Reduction. IST Austria, 2017, doi:10.15479/AT:IST-2017-872-v1-1.","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.","ista":"Chalupa M, Chatterjee K, Pavlogiannis A, Sinha N, Vaidya K. 2017. Data-centric dynamic partial order reduction, IST Austria, 36p.","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"},"page":"36","date_published":"2017-10-23T00:00:00Z","doi":"10.15479/AT:IST-2017-872-v1-1","language":[{"iso":"eng"}],"month":"10","day":"23","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"_id":"5456","year":"2017","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"publication_status":"published","status":"public","title":"Data-centric dynamic partial order reduction","publisher":"IST Austria","department":[{"_id":"KrCh"}],"author":[{"full_name":"Chalupa, Marek","first_name":"Marek","last_name":"Chalupa"},{"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","orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","first_name":"Andreas"},{"full_name":"Sinha, Nishant","last_name":"Sinha","first_name":"Nishant"},{"first_name":"Kapil","last_name":"Vaidya","full_name":"Vaidya, Kapil"}],"pubrep_id":"872","related_material":{"record":[{"status":"public","relation":"later_version","id":"10417"},{"id":"5448","relation":"earlier_version","status":"public"}]},"date_created":"2018-12-12T11:39:26Z","date_updated":"2023-02-23T12:26:54Z","oa_version":"Published Version","file":[{"checksum":"d2635c4cf013000f0a1b09e80f9e4ab7","date_created":"2018-12-12T11:53:26Z","date_updated":"2020-07-14T12:46:59Z","file_id":"5487","relation":"main_file","creator":"system","file_size":910347,"content_type":"application/pdf","access_level":"open_access","file_name":"IST-2017-872-v1+1_main.pdf"}],"type":"technical_report","alternative_title":["IST Austria Technical Report"],"abstract":[{"text":"We present a new dynamic partial-order reduction method for stateless model checking of concurrent programs. A common approach for exploring program behaviors relies on enumerating the traces of the program, without storing the visited states (aka stateless exploration). As the number of distinct traces grows exponentially, dynamic partial-order reduction (DPOR) techniques have been successfully used to partition the space of traces into equivalence classes (Mazurkiewicz partitioning), with the goal of exploring only few representative traces from each class.\r\nWe introduce a new equivalence on traces under sequential consistency semantics, which we call the observation equivalence. Two traces are observationally equivalent if every read event observes the same write event in both traces. While the traditional Mazurkiewicz equivalence is control-centric, our new definition is data-centric. We show that our observation equivalence is coarser than the Mazurkiewicz equivalence, and in many cases even exponentially coarser. We devise a DPOR exploration of the trace space, called data-centric DPOR, based on the observation equivalence.\r\n1. For acyclic architectures, our algorithm is guaranteed to explore exactly one representative trace from each observation class, while spending polynomial time per class. Hence, our algorithm is optimal wrt the observation equivalence, and in several cases explores exponentially fewer traces than any enumerative method based on the Mazurkiewicz equivalence.\r\n2. For cyclic architectures, we consider an equivalence between traces which is finer than the observation equivalence; but coarser than the Mazurkiewicz equivalence, and in some cases is exponentially coarser. Our data-centric DPOR algorithm remains optimal under this trace equivalence. \r\nFinally, we perform a basic experimental comparison between the existing Mazurkiewicz-based DPOR and our data-centric DPOR on a set of academic benchmarks. Our results show a significant reduction in both running time and the number of explored equivalence classes.","lang":"eng"}],"file_date_updated":"2020-07-14T12:46:59Z"},{"status":"public","ddc":["004"],"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","oa_version":"Published Version","file":[{"date_created":"2018-12-12T10:18:04Z","date_updated":"2020-07-14T12:47:00Z","checksum":"2eed5224c0e4e259484a1d71acb8ba6a","file_id":"5322","relation":"main_file","creator":"system","file_size":535077,"content_type":"application/pdf","file_name":"IST-2018-924-v1+1_LIPIcs-MFCS-2017-61.pdf","access_level":"open_access"}],"pubrep_id":"924","alternative_title":["LIPIcs"],"type":"conference","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"}],"publication":"Leibniz International Proceedings in Informatics","citation":{"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.","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","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","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.","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.","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017."},"date_published":"2017-11-01T00:00:00Z","scopus_import":1,"day":"01","has_accepted_license":"1","publication_status":"published","department":[{"_id":"KrCh"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2017","date_updated":"2021-01-12T08:02:34Z","date_created":"2018-12-11T11:47:08Z","volume":83,"author":[{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"article_number":"61","file_date_updated":"2020-07-14T12:47:00Z","publist_id":"7263","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"}],"conference":{"end_date":"2017-08-25","start_date":"2017-08-21","location":"Aalborg, Denmark","name":"MFCS: Mathematical Foundations of Computer Science (SG)"},"doi":"10.4230/LIPIcs.MFCS.2017.61","month":"11","publication_identifier":{"isbn":["978-395977046-0"]}}]