[{"file_date_updated":"2020-07-14T12:44:37Z","publist_id":"6179","license":"https://creativecommons.org/licenses/by/4.0/","author":[{"first_name":"Joel F","last_name":"Alwen","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F"},{"full_name":"De Rezende, Susanna","last_name":"De Rezende","first_name":"Susanna"},{"full_name":"Nordstrom, Jakob","last_name":"Nordstrom","first_name":"Jakob"},{"full_name":"Vinyals, Marc","last_name":"Vinyals","first_name":"Marc"}],"date_updated":"2021-01-12T06:48:51Z","date_created":"2018-12-11T11:50:33Z","volume":67,"year":"2017","publication_status":"published","editor":[{"last_name":"Papadimitriou","first_name":"Christos","full_name":"Papadimitriou, Christos"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"KrPi"}],"month":"01","publication_identifier":{"issn":["18688969"]},"conference":{"location":"Berkeley, CA, United States","start_date":"2017-01-09","end_date":"2017-01-11","name":"ITCS: Innovations in Theoretical Computer Science"},"doi":"10.4230/LIPIcs.ITCS.2017.38","language":[{"iso":"eng"}],"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","abstract":[{"lang":"eng","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."}],"type":"conference","alternative_title":["LIPIcs"],"pubrep_id":"927","file":[{"creator":"system","file_size":557769,"content_type":"application/pdf","file_name":"IST-2018-927-v1+1_LIPIcs-ITCS-2017-38.pdf","access_level":"open_access","date_updated":"2020-07-14T12:44:37Z","date_created":"2018-12-12T10:17:11Z","checksum":"dbc94810be07c2fb1945d5c2a6130e6c","file_id":"5263","relation":"main_file"}],"oa_version":"Published Version","_id":"1175","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["005","600"],"status":"public","title":"Cumulative space in black-white pebbling and resolution","intvolume":" 67","day":"01","has_accepted_license":"1","scopus_import":1,"date_published":"2017-01-01T00:00:00Z","citation":{"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","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.","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.","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","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.","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.","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."},"page":"38:1-38-21"},{"month":"03","doi":"10.1007/s11538-016-0244-3","language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1607.00944","open_access":"1"}],"quality_controlled":"1","project":[{"name":"Speed of Adaptation in Population Genetics and Evolutionary Computation","call_identifier":"FP7","_id":"25B1EC9E-B435-11E9-9278-68D0E5697425","grant_number":"618091"},{"_id":"25B07788-B435-11E9-9278-68D0E5697425","grant_number":"250152","name":"Limits to selection in biology and in evolutionary computation","call_identifier":"FP7"}],"publist_id":"6160","ec_funded":1,"author":[{"first_name":"Richard","last_name":"Kollár","full_name":"Kollár, Richard"},{"full_name":"Novak, Sebastian","id":"461468AE-F248-11E8-B48F-1D18A9856A87","last_name":"Novak","first_name":"Sebastian"}],"date_created":"2018-12-11T11:50:38Z","date_updated":"2021-01-12T06:48:58Z","volume":79,"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.","year":"2017","publication_status":"published","department":[{"_id":"NiBa"}],"publisher":"Springer","day":"01","scopus_import":1,"date_published":"2017-03-01T00:00:00Z","publication":"Bulletin of Mathematical Biology","citation":{"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","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.","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","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.","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.","short":"R. Kollár, S. Novak, Bulletin of Mathematical Biology 79 (2017) 525–559.","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."},"page":"525-559","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"}],"issue":"3","type":"journal_article","oa_version":"Preprint","_id":"1191","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","title":"Existence of traveling waves for the generalized F–KPP equation","status":"public","intvolume":" 79"},{"doi":"10.1007/s10955-016-1672-z","language":[{"iso":"eng"}],"oa":1,"quality_controlled":"1","month":"05","author":[{"full_name":"Budanur, Nazmi B","id":"3EA1010E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-0423-5010","first_name":"Nazmi B","last_name":"Budanur"},{"full_name":"Cvitanović, Predrag","first_name":"Predrag","last_name":"Cvitanović"}],"volume":167,"date_updated":"2021-01-12T06:49:07Z","date_created":"2018-12-11T11:50:44Z","year":"2017","acknowledgement":"This work was supported by the family of late G. Robinson, Jr. and NSF Grant DMS-1211827. ","publisher":"Springer","department":[{"_id":"BjHo"}],"publication_status":"published","publist_id":"6136","file_date_updated":"2020-07-14T12:44:39Z","date_published":"2017-05-01T00:00:00Z","citation":{"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.","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","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.","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","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.","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.","short":"N.B. Budanur, P. Cvitanović, Journal of Statistical Physics 167 (2017) 636–655."},"publication":"Journal of Statistical Physics","page":"636-655","has_accepted_license":"1","day":"01","scopus_import":1,"pubrep_id":"782","oa_version":"Submitted Version","file":[{"relation":"main_file","file_id":"5319","date_created":"2018-12-12T10:18:01Z","date_updated":"2020-07-14T12:44:39Z","checksum":"3e971d09eb167761aa0888ed415b0056","file_name":"IST-2017-782-v1+1_BudCvi15.pdf","access_level":"open_access","content_type":"application/pdf","file_size":2820207,"creator":"system"}],"_id":"1211","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","intvolume":" 167","status":"public","title":"Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system","ddc":["530"],"issue":"3-4","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"}],"type":"journal_article"},{"file":[{"success":1,"date_updated":"2019-10-24T10:54:37Z","date_created":"2019-10-24T10:54:37Z","relation":"main_file","file_id":"6967","file_size":573623,"content_type":"application/pdf","creator":"dernst","access_level":"open_access","file_name":"2017_JournalGraphAlgorithms_Fulek.pdf"}],"oa_version":"Published Version","title":"Hanani-Tutte for radial planarity","status":"public","ddc":["510"],"intvolume":" 21","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"1113","abstract":[{"lang":"eng","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."}],"issue":"1","type":"journal_article","date_published":"2017-01-01T00:00:00Z","article_type":"original","page":"135 - 154","publication":"Journal of Graph Algorithms and Applications","citation":{"short":"R. Fulek, M. Pelsmajer, M. Schaefer, Journal of Graph Algorithms and Applications 21 (2017) 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.","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.","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","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.","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","ista":"Fulek R, Pelsmajer M, Schaefer M. 2017. Hanani-Tutte for radial planarity. Journal of Graph Algorithms and Applications. 21(1), 135–154."},"day":"01","article_processing_charge":"No","has_accepted_license":"1","scopus_import":1,"date_updated":"2023-02-23T10:05:57Z","date_created":"2018-12-11T11:50:13Z","volume":21,"author":[{"last_name":"Fulek","first_name":"Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav"},{"full_name":"Pelsmajer, Michael","first_name":"Michael","last_name":"Pelsmajer"},{"full_name":"Schaefer, Marcus","last_name":"Schaefer","first_name":"Marcus"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"1164"},{"id":"1595","relation":"earlier_version","status":"public"}]},"publication_status":"published","publisher":"Brown University","department":[{"_id":"UlWa"}],"year":"2017","file_date_updated":"2019-10-24T10:54:37Z","publist_id":"6254","ec_funded":1,"language":[{"iso":"eng"}],"doi":"10.7155/jgaa.00408","quality_controlled":"1","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"oa":1,"external_id":{"arxiv":["1608.08662"]},"month":"01"},{"publication_status":"published","status":"public","title":"Structure of respiratory complex I: “Minimal” bacterial and “de luxe” mammalian versions","department":[{"_id":"LeSa"}],"editor":[{"full_name":"Wikström, Mårten","first_name":"Mårten","last_name":"Wikström"}],"publisher":"Royal Society of Chemistry","year":"2017","_id":"444","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T07:56:59Z","date_created":"2018-12-11T11:46:30Z","oa_version":"None","author":[{"orcid":"0000-0002-0977-7989","id":"338D39FE-F248-11E8-B48F-1D18A9856A87","last_name":"Sazanov","first_name":"Leonid A","full_name":"Sazanov, Leonid A"}],"type":"book_chapter","abstract":[{"lang":"eng","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."}],"publist_id":"7379","quality_controlled":"1","page":"25 - 59","publication":"Mechanisms of primary energy transduction in biology ","citation":{"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","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.","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.","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","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.","short":"L.A. Sazanov, in:, M. Wikström (Ed.), Mechanisms of Primary Energy Transduction in Biology , Royal Society of Chemistry, 2017, pp. 25–59.","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."},"language":[{"iso":"eng"}],"date_published":"2017-11-29T00:00:00Z","doi":"10.1039/9781788010405-00025","series_title":"Mechanisms of Primary Energy Transduction in Biology ","day":"29","month":"11","publication_identifier":{"isbn":["978-1-78262-865-1"]}}]