[{"_id":"10418","status":"public","type":"journal_article","article_type":"original","conference":{"end_date":"2018-01-13","location":"Los Angeles, CA, United States","start_date":"2018-01-07","name":"POPL: Programming Languages"},"date_updated":"2021-12-07T08:04:14Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"oa_version":"Published Version","abstract":[{"text":"We present a new proof rule for proving almost-sure termination of probabilistic programs, including those that contain demonic non-determinism. An important question for a probabilistic program is whether the probability mass of all its diverging runs is zero, that is that it terminates \"almost surely\". Proving that can be hard, and this paper presents a new method for doing so. It applies directly to the program's source code, even if the program contains demonic choice. Like others, we use variant functions (a.k.a. \"super-martingales\") that are real-valued and decrease randomly on each loop iteration; but our key innovation is that the amount as well as the probability of the decrease are parametric. We prove the soundness of the new rule, indicate where its applicability goes beyond existing rules, and explain its connection to classical results on denumerable (non-demonic) Markov chains.","lang":"eng"}],"month":"12","intvolume":" 2","scopus_import":"1","main_file_link":[{"url":"https://dl.acm.org/doi/10.1145/3158121","open_access":"1"}],"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["2475-1421"]},"publication_status":"published","issue":"POPL","volume":2,"article_number":"33","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","citation":{"mla":"Mciver, Annabelle, et al. “A New Proof Rule for Almost-Sure Termination.” Proceedings of the ACM on Programming Languages, vol. 2, no. POPL, 33, Association for Computing Machinery, 2017, doi:10.1145/3158121.","short":"A. Mciver, C. Morgan, B.L. Kaminski, J.P. Katoen, Proceedings of the ACM on Programming Languages 2 (2017).","ieee":"A. Mciver, C. Morgan, B. L. Kaminski, and J. P. Katoen, “A new proof rule for almost-sure termination,” Proceedings of the ACM on Programming Languages, vol. 2, no. POPL. Association for Computing Machinery, 2017.","ama":"Mciver A, Morgan C, Kaminski BL, Katoen JP. A new proof rule for almost-sure termination. Proceedings of the ACM on Programming Languages. 2017;2(POPL). doi:10.1145/3158121","apa":"Mciver, A., Morgan, C., Kaminski, B. L., & Katoen, J. P. (2017). A new proof rule for almost-sure termination. Proceedings of the ACM on Programming Languages. Los Angeles, CA, United States: Association for Computing Machinery. https://doi.org/10.1145/3158121","chicago":"Mciver, Annabelle, Carroll Morgan, Benjamin Lucien Kaminski, and Joost P Katoen. “A New Proof Rule for Almost-Sure Termination.” Proceedings of the ACM on Programming Languages. Association for Computing Machinery, 2017. https://doi.org/10.1145/3158121.","ista":"Mciver A, Morgan C, Kaminski BL, Katoen JP. 2017. A new proof rule for almost-sure termination. Proceedings of the ACM on Programming Languages. 2(POPL), 33."},"title":"A new proof rule for almost-sure termination","author":[{"last_name":"Mciver","full_name":"Mciver, Annabelle","first_name":"Annabelle"},{"first_name":"Carroll","last_name":"Morgan","full_name":"Morgan, Carroll"},{"first_name":"Benjamin Lucien","last_name":"Kaminski","full_name":"Kaminski, Benjamin Lucien"},{"id":"4524F760-F248-11E8-B48F-1D18A9856A87","first_name":"Joost P","last_name":"Katoen","full_name":"Katoen, Joost P"}],"article_processing_charge":"No","external_id":{"arxiv":["1711.03588"]},"acknowledgement":"McIver and Morgan are grateful to David Basin and the Information Security Group at ETH Zürich for hosting a six-month stay in Switzerland, during part of which this work began. And thanks particularly to Andreas Lochbihler, who shared with us the probabilistic termination problem that led to it. They acknowledge the support of ARC grant DP140101119. Part of this work was carried out during the Workshop on Probabilistic Programming Semantics\r\nat McGill University’s Bellairs Research Institute on Barbados organised by Alexandra Silva and\r\nPrakash Panangaden. Kaminski and Katoen are grateful to Sebastian Junges for spotting a flaw in §5.4.","publisher":"Association for Computing Machinery","quality_controlled":"1","oa":1,"day":"07","publication":"Proceedings of the ACM on Programming Languages","year":"2017","date_published":"2017-12-07T00:00:00Z","doi":"10.1145/3158121","date_created":"2021-12-05T23:01:49Z"},{"_id":"1112","status":"public","type":"conference","conference":{"end_date":"2017-01-15","location":"Copenhagen, Denmark","start_date":"2017-01-12","name":"FOGA: Foundations of Genetic Algorithms"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:48:22Z","citation":{"mla":"Paixao, Tiago, and Jorge Pérez Heredia. “An Application of Stochastic Differential Equations to Evolutionary Algorithms.” Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, ACM, 2017, pp. 3–11, doi:10.1145/3040718.3040729.","apa":"Paixao, T., & Pérez Heredia, J. (2017). An application of stochastic differential equations to evolutionary algorithms. In Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (pp. 3–11). Copenhagen, Denmark: ACM. https://doi.org/10.1145/3040718.3040729","ama":"Paixao T, Pérez Heredia J. An application of stochastic differential equations to evolutionary algorithms. In: Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. ACM; 2017:3-11. doi:10.1145/3040718.3040729","ieee":"T. Paixao and J. Pérez Heredia, “An application of stochastic differential equations to evolutionary algorithms,” in Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, Copenhagen, Denmark, 2017, pp. 3–11.","short":"T. Paixao, J. Pérez Heredia, in:, Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, ACM, 2017, pp. 3–11.","chicago":"Paixao, Tiago, and Jorge Pérez Heredia. “An Application of Stochastic Differential Equations to Evolutionary Algorithms.” In Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, 3–11. ACM, 2017. https://doi.org/10.1145/3040718.3040729.","ista":"Paixao T, Pérez Heredia J. 2017. An application of stochastic differential equations to evolutionary algorithms. Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. FOGA: Foundations of Genetic Algorithms, 3–11."},"department":[{"_id":"NiBa"}],"title":"An application of stochastic differential equations to evolutionary algorithms","publist_id":"6255","author":[{"first_name":"Tiago","id":"2C5658E6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2361-3953","full_name":"Paixao, Tiago","last_name":"Paixao"},{"full_name":"Pérez Heredia, Jorge","last_name":"Pérez Heredia","first_name":"Jorge"}],"oa_version":"None","abstract":[{"lang":"eng","text":"There has been renewed interest in modelling the behaviour of evolutionary algorithms by more traditional mathematical objects, such as ordinary differential equations or Markov chains. The advantage is that the analysis becomes greatly facilitated due to the existence of well established methods. However, this typically comes at the cost of disregarding information about the process. Here, we introduce the use of stochastic differential equations (SDEs) for the study of EAs. SDEs can produce simple analytical results for the dynamics of stochastic processes, unlike Markov chains which can produce rigorous but unwieldy expressions about the dynamics. On the other hand, unlike ordinary differential equations (ODEs), they do not discard information about the stochasticity of the process. We show that these are especially suitable for the analysis of fixed budget scenarios and present analogs of the additive and multiplicative drift theorems for SDEs. We exemplify the use of these methods for two model algorithms ((1+1) EA and RLS) on two canonical problems(OneMax and LeadingOnes)."}],"month":"01","scopus_import":1,"quality_controlled":"1","publisher":"ACM","day":"12","publication":"Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms","language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-145034651-1"]},"year":"2017","publication_status":"published","doi":"10.1145/3040718.3040729","date_published":"2017-01-12T00:00:00Z","date_created":"2018-12-11T11:50:12Z","page":"3 - 11"},{"date_published":"2017-01-01T00:00:00Z","doi":"10.4230/LIPIcs.ITCS.2017.38","date_created":"2018-12-11T11:50:33Z","page":"38:1-38-21","day":"01","has_accepted_license":"1","year":"2017","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"title":"Cumulative space in black-white pebbling and resolution","editor":[{"first_name":"Christos","full_name":"Papadimitriou, Christos","last_name":"Papadimitriou"}],"author":[{"full_name":"Alwen, Joel F","last_name":"Alwen","first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Susanna","last_name":"De Rezende","full_name":"De Rezende, Susanna"},{"first_name":"Jakob","last_name":"Nordstrom","full_name":"Nordstrom, Jakob"},{"full_name":"Vinyals, Marc","last_name":"Vinyals","first_name":"Marc"}],"publist_id":"6179","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"apa":"Alwen, J. F., De Rezende, S., Nordstrom, J., & Vinyals, M. (2017). Cumulative space in black-white pebbling and resolution. In C. Papadimitriou (Ed.) (Vol. 67, p. 38:1-38-21). Presented at the ITCS: Innovations in Theoretical Computer Science, Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITCS.2017.38","ama":"Alwen JF, De Rezende S, Nordstrom J, Vinyals M. Cumulative space in black-white pebbling and resolution. In: Papadimitriou C, ed. Vol 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017:38:1-38-21. doi:10.4230/LIPIcs.ITCS.2017.38","short":"J.F. Alwen, S. De Rezende, J. Nordstrom, M. Vinyals, in:, C. Papadimitriou (Ed.), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 38:1-38-21.","ieee":"J. F. Alwen, S. De Rezende, J. Nordstrom, and M. Vinyals, “Cumulative space in black-white pebbling and resolution,” presented at the ITCS: Innovations in Theoretical Computer Science, Berkeley, CA, United States, 2017, vol. 67, p. 38:1-38-21.","mla":"Alwen, Joel F., et al. Cumulative Space in Black-White Pebbling and Resolution. Edited by Christos Papadimitriou, vol. 67, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 38:1-38-21, doi:10.4230/LIPIcs.ITCS.2017.38.","ista":"Alwen JF, De Rezende S, Nordstrom J, Vinyals M. 2017. Cumulative space in black-white pebbling and resolution. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 67, 38:1-38-21.","chicago":"Alwen, Joel F, Susanna De Rezende, Jakob Nordstrom, and Marc Vinyals. “Cumulative Space in Black-White Pebbling and Resolution.” edited by Christos Papadimitriou, 67:38:1-38-21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.ITCS.2017.38."},"volume":67,"file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"5263","checksum":"dbc94810be07c2fb1945d5c2a6130e6c","creator":"system","date_updated":"2020-07-14T12:44:37Z","file_size":557769,"date_created":"2018-12-12T10:17:11Z","file_name":"IST-2018-927-v1+1_LIPIcs-ITCS-2017-38.pdf"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["18688969"]},"publication_status":"published","month":"01","intvolume":" 67","scopus_import":1,"alternative_title":["LIPIcs"],"oa_version":"Published Version","abstract":[{"text":"We study space complexity and time-space trade-offs with a focus not on peak memory usage but on overall memory consumption throughout the computation. Such a cumulative space measure was introduced for the computational model of parallel black pebbling by [Alwen and Serbinenko ’15] as a tool for obtaining results in cryptography. We consider instead the non- deterministic black-white pebble game and prove optimal cumulative space lower bounds and trade-offs, where in order to minimize pebbling time the space has to remain large during a significant fraction of the pebbling. We also initiate the study of cumulative space in proof complexity, an area where other space complexity measures have been extensively studied during the last 10–15 years. Using and extending the connection between proof complexity and pebble games in [Ben-Sasson and Nordström ’08, ’11] we obtain several strong cumulative space results for (even parallel versions of) the resolution proof system, and outline some possible future directions of study of this, in our opinion, natural and interesting space measure.","lang":"eng"}],"department":[{"_id":"KrPi"}],"file_date_updated":"2020-07-14T12:44:37Z","ddc":["005","600"],"date_updated":"2021-01-12T06:48:51Z","status":"public","pubrep_id":"927","type":"conference","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"name":"ITCS: Innovations in Theoretical Computer Science","location":"Berkeley, CA, United States","end_date":"2017-01-11","start_date":"2017-01-09"},"_id":"1175"},{"department":[{"_id":"NiBa"}],"date_updated":"2021-01-12T06:48:58Z","type":"journal_article","status":"public","_id":"1191","issue":"3","volume":79,"ec_funded":1,"publication_status":"published","language":[{"iso":"eng"}],"scopus_import":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1607.00944"}],"month":"03","intvolume":" 79","abstract":[{"text":"Variation in genotypes may be responsible for differences in dispersal rates, directional biases, and growth rates of individuals. These traits may favor certain genotypes and enhance their spatiotemporal spreading into areas occupied by the less advantageous genotypes. We study how these factors influence the speed of spreading in the case of two competing genotypes under the assumption that spatial variation of the total population is small compared to the spatial variation of the frequencies of the genotypes in the population. In that case, the dynamics of the frequency of one of the genotypes is approximately described by a generalized Fisher–Kolmogorov–Petrovskii–Piskunov (F–KPP) equation. This generalized F–KPP equation with (nonlinear) frequency-dependent diffusion and advection terms admits traveling wave solutions that characterize the invasion of the dominant genotype. Our existence results generalize the classical theory for traveling waves for the F–KPP with constant coefficients. Moreover, in the particular case of the quadratic (monostable) nonlinear growth–decay rate in the generalized F–KPP we study in detail the influence of the variance in diffusion and mean displacement rates of the two genotypes on the minimal wave propagation speed.","lang":"eng"}],"oa_version":"Preprint","publist_id":"6160","author":[{"full_name":"Kollár, Richard","last_name":"Kollár","first_name":"Richard"},{"last_name":"Novak","full_name":"Novak, Sebastian","id":"461468AE-F248-11E8-B48F-1D18A9856A87","first_name":"Sebastian"}],"title":"Existence of traveling waves for the generalized F–KPP equation","citation":{"chicago":"Kollár, Richard, and Sebastian Novak. “Existence of Traveling Waves for the Generalized F–KPP Equation.” Bulletin of Mathematical Biology. Springer, 2017. https://doi.org/10.1007/s11538-016-0244-3.","ista":"Kollár R, Novak S. 2017. Existence of traveling waves for the generalized F–KPP equation. Bulletin of Mathematical Biology. 79(3), 525–559.","mla":"Kollár, Richard, and Sebastian Novak. “Existence of Traveling Waves for the Generalized F–KPP Equation.” Bulletin of Mathematical Biology, vol. 79, no. 3, Springer, 2017, pp. 525–59, doi:10.1007/s11538-016-0244-3.","ama":"Kollár R, Novak S. Existence of traveling waves for the generalized F–KPP equation. Bulletin of Mathematical Biology. 2017;79(3):525-559. doi:10.1007/s11538-016-0244-3","apa":"Kollár, R., & Novak, S. (2017). Existence of traveling waves for the generalized F–KPP equation. Bulletin of Mathematical Biology. Springer. https://doi.org/10.1007/s11538-016-0244-3","short":"R. Kollár, S. Novak, Bulletin of Mathematical Biology 79 (2017) 525–559.","ieee":"R. Kollár and S. Novak, “Existence of traveling waves for the generalized F–KPP equation,” Bulletin of Mathematical Biology, vol. 79, no. 3. Springer, pp. 525–559, 2017."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","project":[{"call_identifier":"FP7","_id":"25B1EC9E-B435-11E9-9278-68D0E5697425","name":"Speed of Adaptation in Population Genetics and Evolutionary Computation","grant_number":"618091"},{"_id":"25B07788-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"250152","name":"Limits to selection in biology and in evolutionary computation"}],"page":"525-559","date_published":"2017-03-01T00:00:00Z","doi":"10.1007/s11538-016-0244-3","date_created":"2018-12-11T11:50:38Z","year":"2017","day":"01","publication":"Bulletin of Mathematical Biology","quality_controlled":"1","publisher":"Springer","oa":1,"acknowledgement":"We thank Nick Barton, Katarína Bod’ová, and Sr\r\n-\r\ndan Sarikas for constructive feed-\r\nback and support. Furthermore, we would like to express our deep gratitude to the anonymous referees (one\r\nof whom, Jimmy Garnier, agreed to reveal his identity) and the editor Max Souza, for very helpful and\r\ndetailed comments and suggestions that significantly helped us to improve the manuscript. This project has\r\nreceived funding from the European Union’s Seventh Framework Programme for research, technological\r\ndevelopment and demonstration under Grant Agreement 618091 Speed of Adaptation in Population Genet-\r\nics and Evolutionary Computation (SAGE) and the European Research Council (ERC) Grant No. 250152\r\n(SN), from the Scientific Grant Agency of the Slovak Republic under the Grant 1/0459/13 and by the Slovak\r\nResearch and Development Agency under the Contract No. APVV-14-0378 (RK). RK would also like to\r\nthank IST Austria for its hospitality during the work on this project."},{"page":"636-655","doi":"10.1007/s10955-016-1672-z","date_published":"2017-05-01T00:00:00Z","date_created":"2018-12-11T11:50:44Z","has_accepted_license":"1","year":"2017","day":"01","publication":"Journal of Statistical Physics","publisher":"Springer","quality_controlled":"1","oa":1,"acknowledgement":"This work was supported by the family of late G. Robinson, Jr. and NSF Grant DMS-1211827. ","publist_id":"6136","author":[{"id":"3EA1010E-F248-11E8-B48F-1D18A9856A87","first_name":"Nazmi B","full_name":"Budanur, Nazmi B","orcid":"0000-0003-0423-5010","last_name":"Budanur"},{"full_name":"Cvitanović, Predrag","last_name":"Cvitanović","first_name":"Predrag"}],"title":"Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system","citation":{"mla":"Budanur, Nazmi B., and Predrag Cvitanović. “Unstable Manifolds of Relative Periodic Orbits in the Symmetry Reduced State Space of the Kuramoto–Sivashinsky System.” Journal of Statistical Physics, vol. 167, no. 3–4, Springer, 2017, pp. 636–55, doi:10.1007/s10955-016-1672-z.","ieee":"N. B. Budanur and P. Cvitanović, “Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system,” Journal of Statistical Physics, vol. 167, no. 3–4. Springer, pp. 636–655, 2017.","short":"N.B. Budanur, P. Cvitanović, Journal of Statistical Physics 167 (2017) 636–655.","ama":"Budanur NB, Cvitanović P. Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system. Journal of Statistical Physics. 2017;167(3-4):636-655. doi:10.1007/s10955-016-1672-z","apa":"Budanur, N. B., & Cvitanović, P. (2017). Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system. Journal of Statistical Physics. Springer. https://doi.org/10.1007/s10955-016-1672-z","chicago":"Budanur, Nazmi B, and Predrag Cvitanović. “Unstable Manifolds of Relative Periodic Orbits in the Symmetry Reduced State Space of the Kuramoto–Sivashinsky System.” Journal of Statistical Physics. Springer, 2017. https://doi.org/10.1007/s10955-016-1672-z.","ista":"Budanur NB, Cvitanović P. 2017. Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system. Journal of Statistical Physics. 167(3–4), 636–655."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","volume":167,"issue":"3-4","publication_status":"published","file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"3e971d09eb167761aa0888ed415b0056","file_id":"5319","creator":"system","date_updated":"2020-07-14T12:44:39Z","file_size":2820207,"date_created":"2018-12-12T10:18:01Z","file_name":"IST-2017-782-v1+1_BudCvi15.pdf"}],"language":[{"iso":"eng"}],"scopus_import":1,"month":"05","intvolume":" 167","abstract":[{"text":"Systems such as fluid flows in channels and pipes or the complex Ginzburg–Landau system, defined over periodic domains, exhibit both continuous symmetries, translational and rotational, as well as discrete symmetries under spatial reflections or complex conjugation. The simplest, and very common symmetry of this type is the equivariance of the defining equations under the orthogonal group O(2). We formulate a novel symmetry reduction scheme for such systems by combining the method of slices with invariant polynomial methods, and show how it works by applying it to the Kuramoto–Sivashinsky system in one spatial dimension. As an example, we track a relative periodic orbit through a sequence of bifurcations to the onset of chaos. Within the symmetry-reduced state space we are able to compute and visualize the unstable manifolds of relative periodic orbits, their torus bifurcations, a transition to chaos via torus breakdown, and heteroclinic connections between various relative periodic orbits. It would be very hard to carry through such analysis in the full state space, without a symmetry reduction such as the one we present here.","lang":"eng"}],"oa_version":"Submitted Version","department":[{"_id":"BjHo"}],"file_date_updated":"2020-07-14T12:44:39Z","date_updated":"2021-01-12T06:49:07Z","ddc":["530"],"type":"journal_article","status":"public","pubrep_id":"782","_id":"1211"},{"department":[{"_id":"UlWa"}],"file_date_updated":"2019-10-24T10:54:37Z","ddc":["510"],"date_updated":"2023-02-23T10:05:57Z","status":"public","type":"journal_article","article_type":"original","_id":"1113","ec_funded":1,"related_material":{"record":[{"relation":"earlier_version","id":"1164","status":"public"},{"id":"1595","status":"public","relation":"earlier_version"}]},"issue":"1","volume":21,"language":[{"iso":"eng"}],"file":[{"creator":"dernst","date_updated":"2019-10-24T10:54:37Z","file_size":573623,"date_created":"2019-10-24T10:54:37Z","file_name":"2017_JournalGraphAlgorithms_Fulek.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"6967","success":1}],"publication_status":"published","intvolume":" 21","month":"01","scopus_import":1,"oa_version":"Published Version","abstract":[{"text":"A drawing of a graph G is radial if the vertices of G are placed on concentric circles C 1 , . . . , C k with common center c , and edges are drawn radially : every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Toth.","lang":"eng"}],"title":"Hanani-Tutte for radial planarity","article_processing_charge":"No","external_id":{"arxiv":["1608.08662"]},"publist_id":"6254","author":[{"orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav"},{"full_name":"Pelsmajer, Michael","last_name":"Pelsmajer","first_name":"Michael"},{"full_name":"Schaefer, Marcus","last_name":"Schaefer","first_name":"Marcus"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte for Radial Planarity.” Journal of Graph Algorithms and Applications. Brown University, 2017. https://doi.org/10.7155/jgaa.00408.","ista":"Fulek R, Pelsmajer M, Schaefer M. 2017. Hanani-Tutte for radial planarity. Journal of Graph Algorithms and Applications. 21(1), 135–154.","mla":"Fulek, Radoslav, et al. “Hanani-Tutte for Radial Planarity.” Journal of Graph Algorithms and Applications, vol. 21, no. 1, Brown University, 2017, pp. 135–54, doi:10.7155/jgaa.00408.","short":"R. Fulek, M. Pelsmajer, M. Schaefer, Journal of Graph Algorithms and Applications 21 (2017) 135–154.","ieee":"R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity,” Journal of Graph Algorithms and Applications, vol. 21, no. 1. Brown University, pp. 135–154, 2017.","ama":"Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity. Journal of Graph Algorithms and Applications. 2017;21(1):135-154. doi:10.7155/jgaa.00408","apa":"Fulek, R., Pelsmajer, M., & Schaefer, M. (2017). Hanani-Tutte for radial planarity. Journal of Graph Algorithms and Applications. Brown University. https://doi.org/10.7155/jgaa.00408"},"project":[{"grant_number":"291734","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"date_created":"2018-12-11T11:50:13Z","date_published":"2017-01-01T00:00:00Z","doi":"10.7155/jgaa.00408","page":"135 - 154","publication":"Journal of Graph Algorithms and Applications","day":"01","year":"2017","has_accepted_license":"1","oa":1,"quality_controlled":"1","publisher":"Brown University"},{"month":"11","quality_controlled":"1","publisher":"Royal Society of Chemistry","oa_version":"None","abstract":[{"text":"Complex I (NADH:ubiquinone oxidoreductase) plays a central role in cellular energy generation, contributing to the proton motive force used to produce ATP. It couples the transfer of two electrons between NADH and quinone to translocation of four protons across the membrane. It is the largest protein assembly of bacterial and mitochondrial respiratory chains, composed, in mammals, of up to 45 subunits with a total molecular weight of ∼1 MDa. Bacterial enzyme is about half the size, providing the important “minimal” model of complex I. The l-shaped complex consists of a hydrophilic arm, where electron transfer occurs, and a membrane arm, where proton translocation takes place. Previously, we have solved the crystal structures of the hydrophilic domain of complex I from Thermus thermophilus and of the membrane domain from Escherichia coli, followed by the atomic structure of intact, entire complex I from T. thermophilus. Recently, we have solved by cryo-EM a first complete atomic structure of mammalian (ovine) mitochondrial complex I. Core subunits are well conserved from the bacterial version, whilst supernumerary subunits form an interlinked, stabilizing shell around the core. Subunits containing additional cofactors, including Zn ion, NADPH and phosphopantetheine, probably have regulatory roles. Dysfunction of mitochondrial complex I is implicated in many human neurodegenerative diseases. The structure of mammalian enzyme provides many insights into complex I mechanism, assembly, maturation and dysfunction, allowing detailed molecular analysis of disease-causing mutations.","lang":"eng"}],"date_published":"2017-11-29T00:00:00Z","doi":"10.1039/9781788010405-00025","date_created":"2018-12-11T11:46:30Z","page":"25 - 59","day":"29","language":[{"iso":"eng"}],"publication":"Mechanisms of primary energy transduction in biology ","publication_identifier":{"isbn":["978-1-78262-865-1"]},"year":"2017","publication_status":"published","status":"public","type":"book_chapter","_id":"444","series_title":"Mechanisms of Primary Energy Transduction in Biology ","editor":[{"last_name":"Wikström","full_name":"Wikström, Mårten","first_name":"Mårten"}],"department":[{"_id":"LeSa"}],"title":"Structure of respiratory complex I: “Minimal” bacterial and “de luxe” mammalian versions","author":[{"orcid":"0000-0002-0977-7989","full_name":"Sazanov, Leonid A","last_name":"Sazanov","id":"338D39FE-F248-11E8-B48F-1D18A9856A87","first_name":"Leonid A"}],"publist_id":"7379","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T07:56:59Z","citation":{"short":"L.A. Sazanov, in:, M. Wikström (Ed.), Mechanisms of Primary Energy Transduction in Biology , Royal Society of Chemistry, 2017, pp. 25–59.","ieee":"L. A. Sazanov, “Structure of respiratory complex I: ‘Minimal’ bacterial and ‘de luxe’ mammalian versions,” in Mechanisms of primary energy transduction in biology , M. Wikström, Ed. Royal Society of Chemistry, 2017, pp. 25–59.","ama":"Sazanov LA. Structure of respiratory complex I: “Minimal” bacterial and “de luxe” mammalian versions. In: Wikström M, ed. Mechanisms of Primary Energy Transduction in Biology . Mechanisms of Primary Energy Transduction in Biology . Royal Society of Chemistry; 2017:25-59. doi:10.1039/9781788010405-00025","apa":"Sazanov, L. A. (2017). Structure of respiratory complex I: “Minimal” bacterial and “de luxe” mammalian versions. In M. Wikström (Ed.), Mechanisms of primary energy transduction in biology (pp. 25–59). Royal Society of Chemistry. https://doi.org/10.1039/9781788010405-00025","mla":"Sazanov, Leonid A. “Structure of Respiratory Complex I: ‘Minimal’ Bacterial and ‘de Luxe’ Mammalian Versions.” Mechanisms of Primary Energy Transduction in Biology , edited by Mårten Wikström, Royal Society of Chemistry, 2017, pp. 25–59, doi:10.1039/9781788010405-00025.","ista":"Sazanov LA. 2017.Structure of respiratory complex I: “Minimal” bacterial and “de luxe” mammalian versions. In: Mechanisms of primary energy transduction in biology . , 25–59.","chicago":"Sazanov, Leonid A. “Structure of Respiratory Complex I: ‘Minimal’ Bacterial and ‘de Luxe’ Mammalian Versions.” In Mechanisms of Primary Energy Transduction in Biology , edited by Mårten Wikström, 25–59. Mechanisms of Primary Energy Transduction in Biology . Royal Society of Chemistry, 2017. https://doi.org/10.1039/9781788010405-00025."}},{"oa":1,"quality_controlled":"1","publisher":"Biophysical Society","acknowledgement":"The plasmid for full-length kinesin-1 was a gift from G. Holzwarth and J. Macosko with permission from J. Howard. We thank I. Lueke and N. I. Cade for technical assistance. G.P. thanks the Francis Crick Institute, and in particular the Surrey and Salbreux groups, for their hospitality during his sabbatical stay, as well as Imperial College London for making it possible. This work was supported by the Francis Crick Institute, which receives its core funding from Cancer Research UK (FC001163), the United Kingdom Medical Research Council (FC001163), and the Wellcome Trust (FC001163), and by Imperial College London. J.R. was also supported by a Sir Henry Wellcome Postdoctoral Fellowship (100145/Z/12/Z) and T.S. by the European Research Council (Advanced Grant, project 323042). ","date_created":"2018-12-11T11:46:33Z","date_published":"2017-11-07T00:00:00Z","doi":"10.1016/j.bpj.2017.09.006","page":"2055 - 2067","publication":"Biophysical Journal","day":"07","year":"2017","has_accepted_license":"1","title":"Ensembles of bidirectional kinesin Cin8 produce additive forces in both directions of movement","article_processing_charge":"No","author":[{"full_name":"Fallesen, Todd","last_name":"Fallesen","first_name":"Todd"},{"full_name":"Roostalu, Johanna","last_name":"Roostalu","first_name":"Johanna"},{"orcid":"0000-0001-6335-9748","full_name":"Düllberg, Christian F","last_name":"Düllberg","first_name":"Christian F","id":"459064DC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pruessner, Gunnar","last_name":"Pruessner","first_name":"Gunnar"},{"last_name":"Surrey","full_name":"Surrey, Thomas","first_name":"Thomas"}],"publist_id":"7369","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"apa":"Fallesen, T., Roostalu, J., Düllberg, C. F., Pruessner, G., & Surrey, T. (2017). Ensembles of bidirectional kinesin Cin8 produce additive forces in both directions of movement. Biophysical Journal. Biophysical Society. https://doi.org/10.1016/j.bpj.2017.09.006","ama":"Fallesen T, Roostalu J, Düllberg CF, Pruessner G, Surrey T. Ensembles of bidirectional kinesin Cin8 produce additive forces in both directions of movement. Biophysical Journal. 2017;113(9):2055-2067. doi:10.1016/j.bpj.2017.09.006","ieee":"T. Fallesen, J. Roostalu, C. F. Düllberg, G. Pruessner, and T. Surrey, “Ensembles of bidirectional kinesin Cin8 produce additive forces in both directions of movement,” Biophysical Journal, vol. 113, no. 9. Biophysical Society, pp. 2055–2067, 2017.","short":"T. Fallesen, J. Roostalu, C.F. Düllberg, G. Pruessner, T. Surrey, Biophysical Journal 113 (2017) 2055–2067.","mla":"Fallesen, Todd, et al. “Ensembles of Bidirectional Kinesin Cin8 Produce Additive Forces in Both Directions of Movement.” Biophysical Journal, vol. 113, no. 9, Biophysical Society, 2017, pp. 2055–67, doi:10.1016/j.bpj.2017.09.006.","ista":"Fallesen T, Roostalu J, Düllberg CF, Pruessner G, Surrey T. 2017. Ensembles of bidirectional kinesin Cin8 produce additive forces in both directions of movement. Biophysical Journal. 113(9), 2055–2067.","chicago":"Fallesen, Todd, Johanna Roostalu, Christian F Düllberg, Gunnar Pruessner, and Thomas Surrey. “Ensembles of Bidirectional Kinesin Cin8 Produce Additive Forces in Both Directions of Movement.” Biophysical Journal. Biophysical Society, 2017. https://doi.org/10.1016/j.bpj.2017.09.006."},"intvolume":" 113","month":"11","oa_version":"Published Version","abstract":[{"lang":"eng","text":"Most kinesin motors move in only one direction along microtubules. Members of the kinesin-5 subfamily were initially described as unidirectional plus-end-directed motors and shown to produce piconewton forces. However, some fungal kinesin-5 motors are bidirectional. The force production of a bidirectional kinesin-5 has not yet been measured. Therefore, it remains unknown whether the mechanism of the unconventional minus-end-directed motility differs fundamentally from that of plus-end-directed stepping. Using force spectroscopy, we have measured here the forces that ensembles of purified budding yeast kinesin-5 Cin8 produce in microtubule gliding assays in both plus- and minus-end direction. Correlation analysis of pause forces demonstrated that individual Cin8 molecules produce additive forces in both directions of movement. In ensembles, Cin8 motors were able to produce single-motor forces up to a magnitude of ∼1.5 pN. Hence, these properties appear to be conserved within the kinesin-5 subfamily. Force production was largely independent of the directionality of movement, indicating similarities between the motility mechanisms for both directions. These results provide constraints for the development of models for the bidirectional motility mechanism of fission yeast kinesin-5 and provide insight into the function of this mitotic motor."}],"volume":113,"issue":"9","language":[{"iso":"eng"}],"file":[{"file_size":977192,"date_updated":"2020-07-14T12:46:31Z","creator":"system","file_name":"IST-2018-965-v1+1_2017_Duellberg_Ensembles_of.pdf","date_created":"2018-12-12T10:14:03Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","checksum":"99a2474088e20ac74b1882c4fbbb45b1","file_id":"5052"}],"publication_status":"published","pubrep_id":"965","status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","type":"journal_article","_id":"453","file_date_updated":"2020-07-14T12:46:31Z","department":[{"_id":"MaLo"}],"ddc":["570"],"date_updated":"2021-01-12T07:59:28Z"},{"publication_identifier":{"issn":["1860-5974"]},"publication_status":"published","file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"12d469ae69b80361333d7dead965cf5d","file_id":"5010","creator":"system","date_updated":"2020-07-14T12:46:32Z","file_size":582940,"date_created":"2018-12-12T10:13:27Z","file_name":"IST-2018-956-v1+1_2017_Chatterjee_Improved_algorithms.pdf"}],"language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"earlier_version","id":"1661","status":"public"}]},"issue":"3","volume":13,"license":"https://creativecommons.org/licenses/by-nd/4.0/","ec_funded":1,"abstract":[{"text":"The computation of the winning set for parity objectives and for Streett objectives in graphs as well as in game graphs are central problems in computer-aided verification, with application to the verification of closed systems with strong fairness conditions, the verification of open systems, checking interface compatibility, well-formedness of specifications, and the synthesis of reactive systems. We show how to compute the winning set on n vertices for (1) parity-3 (aka one-pair Streett) objectives in game graphs in time O(n5/2) and for (2) k-pair Streett objectives in graphs in time O(n2+nklogn). For both problems this gives faster algorithms for dense graphs and represents the first improvement in asymptotic running time in 15 years.","lang":"eng"}],"oa_version":"Published Version","scopus_import":"1","month":"09","intvolume":" 13","date_updated":"2023-02-23T10:08:55Z","ddc":["004"],"department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:32Z","_id":"464","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode","image":"/image/cc_by_nd.png","name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","short":"CC BY-ND (4.0)"},"status":"public","pubrep_id":"956","has_accepted_license":"1","year":"2017","day":"26","publication":"Logical Methods in Computer Science","date_published":"2017-09-26T00:00:00Z","doi":"10.23638/LMCS-13(3:26)2017","date_created":"2018-12-11T11:46:37Z","quality_controlled":"1","publisher":"International Federation of Computational Logic","oa":1,"citation":{"ista":"Chatterjee K, Henzinger MH, Loitzenbauer V. 2017. Improved algorithms for parity and Streett objectives. Logical Methods in Computer Science. 13(3), 26.","chicago":"Chatterjee, Krishnendu, Monika H Henzinger, and Veronika Loitzenbauer. “Improved Algorithms for Parity and Streett Objectives.” Logical Methods in Computer Science. International Federation of Computational Logic, 2017. https://doi.org/10.23638/LMCS-13(3:26)2017.","short":"K. Chatterjee, M.H. Henzinger, V. Loitzenbauer, Logical Methods in Computer Science 13 (2017).","ieee":"K. Chatterjee, M. H. Henzinger, and V. Loitzenbauer, “Improved algorithms for parity and Streett objectives,” Logical Methods in Computer Science, vol. 13, no. 3. International Federation of Computational Logic, 2017.","ama":"Chatterjee K, Henzinger MH, Loitzenbauer V. Improved algorithms for parity and Streett objectives. Logical Methods in Computer Science. 2017;13(3). doi:10.23638/LMCS-13(3:26)2017","apa":"Chatterjee, K., Henzinger, M. H., & Loitzenbauer, V. (2017). Improved algorithms for parity and Streett objectives. Logical Methods in Computer Science. International Federation of Computational Logic. https://doi.org/10.23638/LMCS-13(3:26)2017","mla":"Chatterjee, Krishnendu, et al. “Improved Algorithms for Parity and Streett Objectives.” Logical Methods in Computer Science, vol. 13, no. 3, 26, International Federation of Computational Logic, 2017, doi:10.23638/LMCS-13(3:26)2017."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"7357","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"},{"first_name":"Veronika","full_name":"Loitzenbauer, Veronika","last_name":"Loitzenbauer"}],"external_id":{"arxiv":["1410.0833"]},"article_processing_charge":"No","title":"Improved algorithms for parity and Streett objectives","article_number":"26","project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"grant_number":"S11407","name":"Game Theory","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"}]},{"date_updated":"2023-02-23T12:20:26Z","ddc":["006"],"department":[{"_id":"ChWo"}],"file_date_updated":"2020-07-14T12:46:34Z","_id":"470","type":"journal_article","article_type":"original","status":"public","publication_identifier":{"issn":["07300301"]},"publication_status":"published","file":[{"file_id":"7359","checksum":"82a3b2bfeee4ddef16ecc21675d1a48a","access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2020-01-24T09:32:35Z","file_name":"wavepackets_final.pdf","creator":"wojtan","date_updated":"2020-07-14T12:46:34Z","file_size":13131683}],"language":[{"iso":"eng"}],"issue":"4","volume":36,"ec_funded":1,"abstract":[{"lang":"eng","text":"This paper presents a method for simulating water surface waves as a displacement field on a 2D domain. Our method relies on Lagrangian particles that carry packets of water wave energy; each packet carries information about an entire group of wave trains, as opposed to only a single wave crest. Our approach is unconditionally stable and can simulate high resolution geometric details. This approach also presents a straightforward interface for artistic control, because it is essentially a particle system with intuitive parameters like wavelength and amplitude. Our implementation parallelizes well and runs in real time for moderately challenging scenarios."}],"acknowledged_ssus":[{"_id":"ScienComp"}],"oa_version":"Published Version","scopus_import":1,"month":"07","intvolume":" 36","citation":{"ieee":"S. Jeschke and C. Wojtan, “Water wave packets,” ACM Transactions on Graphics, vol. 36, no. 4. ACM, 2017.","short":"S. Jeschke, C. Wojtan, ACM Transactions on Graphics 36 (2017).","apa":"Jeschke, S., & Wojtan, C. (2017). Water wave packets. ACM Transactions on Graphics. ACM. https://doi.org/10.1145/3072959.3073678","ama":"Jeschke S, Wojtan C. Water wave packets. ACM Transactions on Graphics. 2017;36(4). doi:10.1145/3072959.3073678","mla":"Jeschke, Stefan, and Chris Wojtan. “Water Wave Packets.” ACM Transactions on Graphics, vol. 36, no. 4, 103, ACM, 2017, doi:10.1145/3072959.3073678.","ista":"Jeschke S, Wojtan C. 2017. Water wave packets. ACM Transactions on Graphics. 36(4), 103.","chicago":"Jeschke, Stefan, and Chris Wojtan. “Water Wave Packets.” ACM Transactions on Graphics. ACM, 2017. https://doi.org/10.1145/3072959.3073678."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"44D6411A-F248-11E8-B48F-1D18A9856A87","first_name":"Stefan","full_name":"Jeschke, Stefan","last_name":"Jeschke"},{"id":"3C61F1D2-F248-11E8-B48F-1D18A9856A87","first_name":"Christopher J","last_name":"Wojtan","orcid":"0000-0001-6646-5546","full_name":"Wojtan, Christopher J"}],"publist_id":"7350","article_processing_charge":"Yes (in subscription journal)","title":"Water wave packets","article_number":"103","project":[{"name":"Efficient Simulation of Natural Phenomena at Extremely Large Scales","grant_number":"638176","_id":"2533E772-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"has_accepted_license":"1","year":"2017","day":"01","publication":"ACM Transactions on Graphics","date_published":"2017-07-01T00:00:00Z","doi":"10.1145/3072959.3073678","date_created":"2018-12-11T11:46:39Z","quality_controlled":"1","publisher":"ACM","oa":1}]