[{"quality_controlled":"1","type":"journal_article","status":"public","year":"2017","file_date_updated":"2020-07-14T12:48:08Z","publication_status":"published","has_accepted_license":"1","oa":1,"publication_identifier":{"issn":["0092-8674"]},"doi":"10.1016/j.cell.2017.07.038","_id":"803","publication":"Cell","date_created":"2018-12-11T11:48:35Z","scopus_import":"1","day":"24","tmp":{"name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode"},"article_processing_charge":"No","month":"08","file":[{"file_name":"2017_Cell_Samwer.pdf","date_updated":"2020-07-14T12:48:08Z","content_type":"application/pdf","file_size":17666637,"date_created":"2019-01-18T13:45:40Z","checksum":"64897b0c5373f22273f598e4672c60ff","relation":"main_file","creator":"dernst","file_id":"5852","access_level":"open_access"}],"volume":170,"intvolume":"       170","title":"DNA cross-bridging shapes a single nucleus from a set of mitotic chromosomes","page":"956 - 972","license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","issue":"5","publisher":"Cell Press","date_published":"2017-08-24T00:00:00Z","department":[{"_id":"CaHe"}],"date_updated":"2025-07-10T11:55:00Z","abstract":[{"text":"Eukaryotic cells store their chromosomes in a single nucleus. This is important to maintain genomic integrity, as chromosomes packaged into separate nuclei (micronuclei) are prone to massive DNA damage. During mitosis, higher eukaryotes disassemble their nucleus and release individualized chromosomes for segregation. How numerous chromosomes subsequently reform a single nucleus has remained unclear. Using image-based screening of human cells, we identified barrier-to-autointegration factor (BAF) as a key factor guiding membranes to form a single nucleus. Unexpectedly, nuclear assembly does not require BAF?s association with inner nuclear membrane proteins but instead relies on BAF?s ability to bridge distant DNA sites. Live-cell imaging and in vitro reconstitution showed that BAF enriches around the mitotic chromosome ensemble to induce a densely cross-bridged chromatin layer that is mechanically stiff and limits membranes to the surface. Our study reveals that BAF-mediated changes in chromosome mechanics underlie nuclear assembly with broad implications for proper genome function.","lang":"eng"}],"isi":1,"external_id":{"isi":["000408372400014"]},"ddc":["570"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Samwer, Matthias","last_name":"Samwer","first_name":"Matthias"},{"full_name":"Schneider, Maximilian","first_name":"Maximilian","last_name":"Schneider"},{"full_name":"Hoefler, Rudolf","last_name":"Hoefler","first_name":"Rudolf"},{"id":"309D50DA-F248-11E8-B48F-1D18A9856A87","last_name":"Schmalhorst","first_name":"Philipp S","orcid":"0000-0002-5795-0133","full_name":"Schmalhorst, Philipp S"},{"full_name":"Jude, Julian","first_name":"Julian","last_name":"Jude"},{"full_name":"Zuber, Johannes","first_name":"Johannes","last_name":"Zuber"},{"first_name":"Daniel","last_name":"Gerlic","full_name":"Gerlic, Daniel"}],"acknowledged_ssus":[{"_id":"Bio"}],"publist_id":"6848","citation":{"ista":"Samwer M, Schneider M, Hoefler R, Schmalhorst PS, Jude J, Zuber J, Gerlic D. 2017. DNA cross-bridging shapes a single nucleus from a set of mitotic chromosomes. Cell. 170(5), 956–972.","mla":"Samwer, Matthias, et al. “DNA Cross-Bridging Shapes a Single Nucleus from a Set of Mitotic Chromosomes.” <i>Cell</i>, vol. 170, no. 5, Cell Press, 2017, pp. 956–72, doi:<a href=\"https://doi.org/10.1016/j.cell.2017.07.038\">10.1016/j.cell.2017.07.038</a>.","ieee":"M. Samwer <i>et al.</i>, “DNA cross-bridging shapes a single nucleus from a set of mitotic chromosomes,” <i>Cell</i>, vol. 170, no. 5. Cell Press, pp. 956–972, 2017.","chicago":"Samwer, Matthias, Maximilian Schneider, Rudolf Hoefler, Philipp S Schmalhorst, Julian Jude, Johannes Zuber, and Daniel Gerlic. “DNA Cross-Bridging Shapes a Single Nucleus from a Set of Mitotic Chromosomes.” <i>Cell</i>. Cell Press, 2017. <a href=\"https://doi.org/10.1016/j.cell.2017.07.038\">https://doi.org/10.1016/j.cell.2017.07.038</a>.","short":"M. Samwer, M. Schneider, R. Hoefler, P.S. Schmalhorst, J. Jude, J. Zuber, D. Gerlic, Cell 170 (2017) 956–972.","ama":"Samwer M, Schneider M, Hoefler R, et al. DNA cross-bridging shapes a single nucleus from a set of mitotic chromosomes. <i>Cell</i>. 2017;170(5):956-972. doi:<a href=\"https://doi.org/10.1016/j.cell.2017.07.038\">10.1016/j.cell.2017.07.038</a>","apa":"Samwer, M., Schneider, M., Hoefler, R., Schmalhorst, P. S., Jude, J., Zuber, J., &#38; Gerlic, D. (2017). DNA cross-bridging shapes a single nucleus from a set of mitotic chromosomes. <i>Cell</i>. Cell Press. <a href=\"https://doi.org/10.1016/j.cell.2017.07.038\">https://doi.org/10.1016/j.cell.2017.07.038</a>"},"oa_version":"Published Version","language":[{"iso":"eng"}]},{"acknowledged_ssus":[{"_id":"ScienComp"}],"corr_author":"1","author":[{"id":"309D50DA-F248-11E8-B48F-1D18A9856A87","last_name":"Schmalhorst","first_name":"Philipp S","full_name":"Schmalhorst, Philipp S","orcid":"0000-0002-5795-0133"},{"last_name":"Deluweit","first_name":"Felix","full_name":"Deluweit, Felix"},{"last_name":"Scherrers","first_name":"Roger","full_name":"Scherrers, Roger"},{"full_name":"Heisenberg, Carl-Philipp J","orcid":"0000-0002-0912-4566","id":"39427864-F248-11E8-B48F-1D18A9856A87","last_name":"Heisenberg","first_name":"Carl-Philipp J"},{"id":"2F74BCDE-F248-11E8-B48F-1D18A9856A87","last_name":"Sikora","first_name":"Mateusz K","full_name":"Sikora, Mateusz K"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Submitted Version","language":[{"iso":"eng"}],"citation":{"apa":"Schmalhorst, P. S., Deluweit, F., Scherrers, R., Heisenberg, C.-P. J., &#38; Sikora, M. K. (2017). Overcoming the limitations of the MARTINI force field in simulations of polysaccharides. <i>Journal of Chemical Theory and Computation</i>. American Chemical Society. <a href=\"https://doi.org/10.1021/acs.jctc.7b00374\">https://doi.org/10.1021/acs.jctc.7b00374</a>","ama":"Schmalhorst PS, Deluweit F, Scherrers R, Heisenberg C-PJ, Sikora MK. Overcoming the limitations of the MARTINI force field in simulations of polysaccharides. <i>Journal of Chemical Theory and Computation</i>. 2017;13(10):5039-5053. doi:<a href=\"https://doi.org/10.1021/acs.jctc.7b00374\">10.1021/acs.jctc.7b00374</a>","short":"P.S. Schmalhorst, F. Deluweit, R. Scherrers, C.-P.J. Heisenberg, M.K. Sikora, Journal of Chemical Theory and Computation 13 (2017) 5039–5053.","chicago":"Schmalhorst, Philipp S, Felix Deluweit, Roger Scherrers, Carl-Philipp J Heisenberg, and Mateusz K Sikora. “Overcoming the Limitations of the MARTINI Force Field in Simulations of Polysaccharides.” <i>Journal of Chemical Theory and Computation</i>. American Chemical Society, 2017. <a href=\"https://doi.org/10.1021/acs.jctc.7b00374\">https://doi.org/10.1021/acs.jctc.7b00374</a>.","ieee":"P. S. Schmalhorst, F. Deluweit, R. Scherrers, C.-P. J. Heisenberg, and M. K. Sikora, “Overcoming the limitations of the MARTINI force field in simulations of polysaccharides,” <i>Journal of Chemical Theory and Computation</i>, vol. 13, no. 10. American Chemical Society, pp. 5039–5053, 2017.","mla":"Schmalhorst, Philipp S., et al. “Overcoming the Limitations of the MARTINI Force Field in Simulations of Polysaccharides.” <i>Journal of Chemical Theory and Computation</i>, vol. 13, no. 10, American Chemical Society, 2017, pp. 5039–53, doi:<a href=\"https://doi.org/10.1021/acs.jctc.7b00374\">10.1021/acs.jctc.7b00374</a>.","ista":"Schmalhorst PS, Deluweit F, Scherrers R, Heisenberg C-PJ, Sikora MK. 2017. Overcoming the limitations of the MARTINI force field in simulations of polysaccharides. Journal of Chemical Theory and Computation. 13(10), 5039–5053."},"publist_id":"6847","arxiv":1,"date_published":"2017-10-10T00:00:00Z","publisher":"American Chemical Society","issue":"10","isi":1,"external_id":{"isi":["000412965700036"],"arxiv":["1704.03773"]},"abstract":[{"text":"Polysaccharides (carbohydrates) are key regulators of a large number of cell biological processes. However, precise biochemical or genetic manipulation of these often complex structures is laborious and hampers experimental structure–function studies. Molecular Dynamics (MD) simulations provide a valuable alternative tool to generate and test hypotheses on saccharide function. Yet, currently used MD force fields often overestimate the aggregation propensity of polysaccharides, affecting the usability of those simulations. Here we tested MARTINI, a popular coarse-grained (CG) force field for biological macromolecules, for its ability to accurately represent molecular forces between saccharides. To this end, we calculated a thermodynamic solution property, the second virial coefficient of the osmotic pressure (B22). Comparison with light scattering experiments revealed a nonphysical aggregation of a prototypical polysaccharide in MARTINI, pointing at an imbalance of the nonbonded solute–solute, solute–water, and water–water interactions. This finding also applies to smaller oligosaccharides which were all found to aggregate in simulations even at moderate concentrations, well below their solubility limit. Finally, we explored the influence of the Lennard-Jones (LJ) interaction between saccharide molecules and propose a simple scaling of the LJ interaction strength that makes MARTINI more reliable for the simulation of saccharides.","lang":"eng"}],"department":[{"_id":"CaHe"}],"date_updated":"2025-06-04T09:49:02Z","day":"10","acknowledgement":"P.S.S. was supported by research fellowship 2811/1-1 from the German Research Foundation (DFG), and M.S. was supported by EMBO Long Term Fellowship ALTF 187-2013 and Grant GC65-32 from the  Interdisciplinary Centre for Mathematical and Computational Modelling (ICM), University of Warsaw, Poland. The authors thank Antje Potthast, Marek Cieplak, Tomasz Włodarski, and Damien Thompson for fruitful discussions and the IST Austria Scientific Computing Facility for support.","date_created":"2018-12-11T11:48:35Z","scopus_import":"1","publication":"Journal of Chemical Theory and Computation","title":"Overcoming the limitations of the MARTINI force field in simulations of polysaccharides","page":"5039 - 5053","intvolume":"        13","volume":13,"article_processing_charge":"No","month":"10","status":"public","type":"journal_article","year":"2017","publication_status":"published","quality_controlled":"1","publication_identifier":{"issn":["1549-9618"]},"doi":"10.1021/acs.jctc.7b00374","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1704.03773"}],"_id":"804","oa":1},{"intvolume":"       144","oa_version":"None","title":"The E2A splice variant E47 regulates the differentiation of projection neurons via p57(KIP2) during cortical development","language":[{"iso":"eng"}],"page":"3917 - 3931","publist_id":"6846","month":"10","article_processing_charge":"No","citation":{"ista":"Pfurr S, Chu Y, Bohrer C, Greulich F, Beattie RJ, Mammadzada K, Hils M, Arnold S, Taylor V, Schachtrup K, Uhlenhaut NH, Schachtrup C. 2017. The E2A splice variant E47 regulates the differentiation of projection neurons via p57(KIP2) during cortical development. Development. 144, 3917–3931.","mla":"Pfurr, Sabrina, et al. “The E2A Splice Variant E47 Regulates the Differentiation of Projection Neurons via P57(KIP2) during Cortical Development.” <i>Development</i>, vol. 144, Company of Biologists, 2017, pp. 3917–31, doi:<a href=\"https://doi.org/10.1242/dev.145698\">10.1242/dev.145698</a>.","ieee":"S. Pfurr <i>et al.</i>, “The E2A splice variant E47 regulates the differentiation of projection neurons via p57(KIP2) during cortical development,” <i>Development</i>, vol. 144. Company of Biologists, pp. 3917–3931, 2017.","chicago":"Pfurr, Sabrina, Yu Chu, Christian Bohrer, Franziska Greulich, Robert J Beattie, Könül Mammadzada, Miriam Hils, et al. “The E2A Splice Variant E47 Regulates the Differentiation of Projection Neurons via P57(KIP2) during Cortical Development.” <i>Development</i>. Company of Biologists, 2017. <a href=\"https://doi.org/10.1242/dev.145698\">https://doi.org/10.1242/dev.145698</a>.","short":"S. Pfurr, Y. Chu, C. Bohrer, F. Greulich, R.J. Beattie, K. Mammadzada, M. Hils, S. Arnold, V. Taylor, K. Schachtrup, N.H. Uhlenhaut, C. Schachtrup, Development 144 (2017) 3917–3931.","ama":"Pfurr S, Chu Y, Bohrer C, et al. The E2A splice variant E47 regulates the differentiation of projection neurons via p57(KIP2) during cortical development. <i>Development</i>. 2017;144:3917-3931. doi:<a href=\"https://doi.org/10.1242/dev.145698\">10.1242/dev.145698</a>","apa":"Pfurr, S., Chu, Y., Bohrer, C., Greulich, F., Beattie, R. J., Mammadzada, K., … Schachtrup, C. (2017). The E2A splice variant E47 regulates the differentiation of projection neurons via p57(KIP2) during cortical development. <i>Development</i>. Company of Biologists. <a href=\"https://doi.org/10.1242/dev.145698\">https://doi.org/10.1242/dev.145698</a>"},"volume":144,"date_created":"2018-12-11T11:48:36Z","scopus_import":"1","day":"31","publication":"Development","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"first_name":"Sabrina","last_name":"Pfurr","full_name":"Pfurr, Sabrina"},{"full_name":"Chu, Yu","first_name":"Yu","last_name":"Chu"},{"full_name":"Bohrer, Christian","first_name":"Christian","last_name":"Bohrer"},{"last_name":"Greulich","first_name":"Franziska","full_name":"Greulich, Franziska"},{"first_name":"Robert J","last_name":"Beattie","id":"2E26DF60-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8483-8753","full_name":"Beattie, Robert J"},{"full_name":"Mammadzada, Könül","first_name":"Könül","last_name":"Mammadzada"},{"last_name":"Hils","first_name":"Miriam","full_name":"Hils, Miriam"},{"full_name":"Arnold, Sebastian","last_name":"Arnold","first_name":"Sebastian"},{"full_name":"Taylor, Verdon","last_name":"Taylor","first_name":"Verdon"},{"full_name":"Schachtrup, Kristina","first_name":"Kristina","last_name":"Schachtrup"},{"full_name":"Uhlenhaut, N Henriette","first_name":"N Henriette","last_name":"Uhlenhaut"},{"first_name":"Christian","last_name":"Schachtrup","full_name":"Schachtrup, Christian"}],"doi":"10.1242/dev.145698","_id":"805","isi":1,"external_id":{"isi":["000414025600007"]},"department":[{"_id":"SiHi"}],"date_updated":"2023-09-26T16:20:09Z","abstract":[{"lang":"eng","text":"During corticogenesis, distinct classes of neurons are born from progenitor cells located in the ventricular and subventricular zones, from where they migrate towards the pial surface to assemble into highly organized layer-specific circuits. However, the precise and coordinated transcriptional network activity defining neuronal identity is still not understood. Here, we show that genetic depletion of the basic helix-loop-helix (bHLH) transcription factor E2A splice variant E47 increased the number of Tbr1-positive deep layer and Satb2-positive upper layer neurons at E14.5, while depletion of the alternatively spliced E12 variant did not affect layer-specific neurogenesis. While ChIP-Seq identified a big overlap for E12- and E47-specific binding sites in embryonic NSCs, including sites at the cyclin-dependent kinase inhibitor (CDKI) Cdkn1c gene locus, RNA-Seq revealed a unique transcriptional regulation by each splice variant. E47 activated the expression of the CDKI Cdkn1c through binding to a distal enhancer. Finally, overexpression of E47 in embryonic NSCs in vitro impaired neurite outgrowth and E47 overexpression in vivo by in utero electroporation disturbed proper layer-specific neurogenesis and upregulated p57(KIP2) expression. Overall, this study identified E2A target genes in embryonic NSCs and demonstrates that E47 regulates neuronal differentiation via p57(KIP2)."}],"date_published":"2017-10-31T00:00:00Z","quality_controlled":"1","type":"journal_article","status":"public","year":"2017","publication_status":"published","publisher":"Company of Biologists"},{"date_published":"2017-09-27T00:00:00Z","related_material":{"record":[{"id":"666","status":"public","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","status":"public","id":"2001"}]},"publisher":"Institute of Science and Technology Austria","degree_awarded":"PhD","ddc":["571","579"],"supervisor":[{"id":"3E6DB97A-F248-11E8-B48F-1D18A9856A87","last_name":"Bollenbach","first_name":"Mark Tobias","full_name":"Bollenbach, Mark Tobias","orcid":"0000-0003-4398-476X"}],"abstract":[{"text":"Antibiotics have diverse effects on bacteria, including massive changes in bacterial gene expression. Whereas the gene expression changes under many antibiotics have been measured, the temporal organization of these responses and their dependence on the bacterial growth rate are unclear. As described in Chapter 1, we quantified the temporal gene expression changes in the bacterium Escherichia coli in response to the sudden exposure to antibiotics using a fluorescent reporter library and a robotic system. Our data show temporally structured gene expression responses, with response times for individual genes ranging from tens of minutes to several hours. We observed that many stress response genes were activated in response to antibiotics. As certain stress responses cross-protect bacteria from other stressors, we then asked whether cellular responses to antibiotics have a similar protective role in Chapter 2. Indeed, we found that the trimethoprim-induced acid stress response protects bacteria from subsequent acid stress. We combined microfluidics with time-lapse imaging to monitor survival, intracellular pH, and acid stress response in single cells. This approach revealed that the variable expression of the acid resistance operon gadBC strongly correlates with single-cell survival time. Cells with higher gadBC expression following trimethoprim maintain higher intracellular pH and survive the acid stress longer. Overall, we provide a way to identify single-cell cross-protection between antibiotics and environmental stressors from temporal gene expression data, and show how antibiotics can increase bacterial fitness in changing environments. While gene expression changes to antibiotics show a clear temporal structure at the population-level, it is unclear whether this clear temporal order is followed by every single cell. Using dual-reporter strains described in Chapter 3, we measured gene expression dynamics of promoter pairs in the same cells using microfluidics and microscopy. Chapter 4 shows that the oxidative stress response and the DNA stress response showed little timing variability and a clear temporal order under the antibiotic nitrofurantoin. In contrast, the acid stress response under trimethoprim ran independently from all other activated response programs including the DNA stress response, which showed particularly high timing variability in this stress condition. In summary, this approach provides insight into the temporal organization of gene expression programs at the single-cell level and suggests dependencies between response programs and the underlying variability-introducing mechanisms. Altogether, this work advances our understanding of the diverse effects that antibiotics have on bacteria. These results were obtained by taking into account gene expression dynamics, which allowed us to identify general principles, molecular mechanisms, and dependencies between genes. Our findings may have implications for infectious disease treatments, and microbial communities in the human body and in nature. ","lang":"eng"}],"date_updated":"2026-04-08T14:21:57Z","department":[{"_id":"ToBo"}],"corr_author":"1","author":[{"first_name":"Karin","last_name":"Mitosch","id":"39B66846-F248-11E8-B48F-1D18A9856A87","full_name":"Mitosch, Karin"}],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","language":[{"iso":"eng"}],"oa_version":"Published Version","citation":{"apa":"Mitosch, K. (2017). <i>Timing, variability and cross-protection in bacteria – insights from dynamic gene expression responses to antibiotics</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:th_862\">https://doi.org/10.15479/AT:ISTA:th_862</a>","short":"K. Mitosch, Timing, Variability and Cross-Protection in Bacteria – Insights from Dynamic Gene Expression Responses to Antibiotics, Institute of Science and Technology Austria, 2017.","ama":"Mitosch K. Timing, variability and cross-protection in bacteria – insights from dynamic gene expression responses to antibiotics. 2017. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_862\">10.15479/AT:ISTA:th_862</a>","chicago":"Mitosch, Karin. “Timing, Variability and Cross-Protection in Bacteria – Insights from Dynamic Gene Expression Responses to Antibiotics.” Institute of Science and Technology Austria, 2017. <a href=\"https://doi.org/10.15479/AT:ISTA:th_862\">https://doi.org/10.15479/AT:ISTA:th_862</a>.","ieee":"K. Mitosch, “Timing, variability and cross-protection in bacteria – insights from dynamic gene expression responses to antibiotics,” Institute of Science and Technology Austria, 2017.","ista":"Mitosch K. 2017. Timing, variability and cross-protection in bacteria – insights from dynamic gene expression responses to antibiotics. Institute of Science and Technology Austria.","mla":"Mitosch, Karin. <i>Timing, Variability and Cross-Protection in Bacteria – Insights from Dynamic Gene Expression Responses to Antibiotics</i>. Institute of Science and Technology Austria, 2017, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_862\">10.15479/AT:ISTA:th_862</a>."},"publist_id":"6831","publication_status":"published","file_date_updated":"2020-07-14T12:48:09Z","year":"2017","status":"public","type":"dissertation","alternative_title":["ISTA Thesis"],"_id":"818","doi":"10.15479/AT:ISTA:th_862","publication_identifier":{"issn":["2663-337X"]},"oa":1,"has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","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)"},"pubrep_id":"862","day":"27","date_created":"2018-12-11T11:48:40Z","OA_place":"publisher","acknowledgement":"First of all, I would like to express great gratitude to my PhD supervisor Tobias Bollenbach. Through his open and trusting attitude I had the freedom to explore different scientific directions during this project, and follow the research lines of my interest. I am thankful for constructive and often extensive discussions and his support and commitment during the different stages of my PhD. I want to thank my committee members, Călin Guet, Terry Hwa and Nassos Typas for their interest and their valuable input to this project. Special thanks to Nassos for career guidance, and for accepting me in his lab. A big thank you goes to the past, present and affiliated members of the Bollenbach group: Guillaume Chevereau, Marjon de Vos, Marta Lukačišinová, Veronika Bierbaum, Qi Qin, Marcin Zagórski, Martin Lukačišin, Andreas Angermayr, Bor Kavčič, Julia Tischler, Dilay Ayhan, Jaroslav Ferenc, and Georg Rieckh. I enjoyed working and discussing with you very much and I will miss our lengthy group meetings, our inspiring journal clubs, and our common lunches. Special thanks to Bor for great mental and professional support during the hard months of thesis writing, and to Marta for very creative times during the beginning of our PhDs. May the ‘Bacterial Survival Guide’ decorate the walls of IST forever! A great thanks to my friend and collaborator Georg Rieckh for his enthusiasm and for getting so involved in these projects, for his endurance and for his company throughout the years. Thanks to the FriSBi crowd at IST Austria for interesting meetings and discussions. In particular I want to thank Magdalena Steinrück, and Anna Andersson for inspiring exchange, and enjoyable time together. Thanks to everybody who contributed to the cover for Cell Systems: The constructive input from Tobias Bollenbach, Bor Kavčič, Georg Rieckh, Marta Lukačišinová, and Sebastian Nozzi, and the professional implementation by the graphic designer Martina Markus from the University of Cologne. Thanks to all my office mates in the first floor Bertalanffy building throughout the years: for ensuring a pleasant working atmosphere, and for your company! In general, I want to thank all the people that make IST such a great environment, with the many possibilities to shape our own social and research environment. I want to thank my family for all kind of practical support during the years, and my second family in Argentina for their enthusiasm. Thanks to my brother Bernhard and my sister Martina for being great siblings, and to Helena and Valentin for the joy you brought to my life. My deep gratitude goes to Sebastian Nozzi, for constant support, patience, love and for believing in me. ","title":"Timing, variability and cross-protection in bacteria – insights from dynamic gene expression responses to antibiotics","page":"113","file":[{"date_created":"2019-04-05T08:48:51Z","checksum":"da3993c5f90f59a8e8623cc31ad501dd","relation":"source_file","creator":"dernst","file_id":"6210","access_level":"closed","file_name":"Thesis_KarinMitosch.docx","date_updated":"2020-07-14T12:48:09Z","content_type":"application/vnd.openxmlformats-officedocument.wordprocessingml.document","file_size":6331071},{"date_created":"2019-04-05T08:48:51Z","checksum":"24c3d9e51992f1b721f3df55aa13fcb8","relation":"main_file","file_id":"6211","creator":"dernst","access_level":"open_access","file_name":"Thesis_KarinMitosch.pdf","date_updated":"2020-07-14T12:48:09Z","content_type":"application/pdf","file_size":9289852}],"month":"09","article_processing_charge":"No"},{"_id":"819","doi":"10.15479/AT:ISTA:th_861","publication_identifier":{"issn":["2663-337X"]},"oa":1,"has_accepted_license":"1","publication_status":"published","year":"2017","file_date_updated":"2020-07-14T12:48:09Z","status":"public","type":"dissertation","alternative_title":["ISTA Thesis"],"title":"Disease defence in garden ants","page":"122","file":[{"relation":"source_file","creator":"dernst","file_id":"6199","date_created":"2019-04-05T07:53:04Z","checksum":"4993cdd5382295758ecc3ecbd2a9aaff","access_level":"closed","file_name":"2017_Thesis_Pull.docx","file_size":18580400,"content_type":"application/vnd.openxmlformats-officedocument.wordprocessingml.document","date_updated":"2020-07-14T12:48:09Z"},{"relation":"main_file","creator":"dernst","file_id":"6200","date_created":"2019-04-05T07:53:04Z","checksum":"ee2e3ebb5b53c154c866f5b052b25153","access_level":"open_access","file_name":"2017_Thesis_Pull.pdf","file_size":14400681,"content_type":"application/pdf","date_updated":"2020-07-14T12:48:09Z"}],"article_processing_charge":"No","month":"09","tmp":{"short":"CC BY (4.0)","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)"},"day":"26","pubrep_id":"861","OA_place":"publisher","acknowledgement":"ERC FP7 programme (grant agreement no. 240371)\r\nI have been supremely spoilt to work in a lab with such good resources and I must thank the wonderful Cremer group technicians, Anna, Barbara, Eva and Florian, for all of their help and keeping the lab up and running. You guys will probably be the most missed once I realise just how much work you have been saving me! For the same reason, I must say a big Dzi ę kuj ę Ci to Wonder Woman Wanda, for her tireless efforts feeding my colonies and cranking out thousands of petri dishes and sugar tubes. Again, you will be sorely missed now that I will have to take this task on myself. Of course, I will be eternally indebted to Prof. Sylvia Cremer for taking me under her wing and being a constant source of guidance and inspiration. You have given me the perfect balance of independence and supervision. I cannot thank you enough for creating such a great working environment and allowing me the freedom to follow my own research questions. I have had so many exceptional opportunities – attending and presenting at conferences all over the world, inviting me to write the ARE with you, going to workshops in Panama and Switzerland, and even organising our own PhD course – that I often think I must have had the best PhD in the world. You have taught me so much and made me a scientist. I sincerely hope we get the chance to work together again in the future. Thank you for everything. I must also thank my PhD Committee, Daria Siekhaus and Jacobus “Koos” Boomsma, for being very supportive throughout the duration of my PhD. ","date_created":"2018-12-11T11:48:40Z","ddc":["576","577","578","579","590","592"],"abstract":[{"lang":"eng","text":"Contagious diseases must transmit from infectious to susceptible hosts in order to reproduce. Whilst vectored pathogens can rely on intermediaries to find new hosts for them, many infectious pathogens require close contact or direct interaction between hosts for transmission. Hence, this means that conspecifics are often the main source of infection for most animals and so, in theory, animals should avoid conspecifics to reduce their risk of infection. Of course, in reality animals must interact with one another, as a bare minimum, to mate. However, being social provides many additional benefits and group living has become a taxonomically diverse and widespread trait. How then do social animals overcome the issue of increased disease? Over the last few decades, the social insects (ants, termites and some bees and wasps) have become a model system for studying disease in social animals. On paper, a social insect colony should be particularly susceptible to disease, given that they often contain thousands of potential hosts that are closely related and frequently interact, as well as exhibiting stable environmental conditions that encourage microbial growth. Yet, disease outbreaks appear to be rare and attempts to eradicate pest species using pathogens have failed time and again. Evolutionary biologists investigating this observation have discovered that the reduced disease susceptibility in social insects is, in part, due to collectively performed disease defences of the workers. These defences act like a “social immune system” for the colony, resulting in a per capita decrease in disease, termed social immunity. Our understanding of social immunity, and its importance in relation to the immunological defences of each insect, continues to grow, but there remain many open questions. In this thesis I have studied disease defence in garden ants. In the first data chapter, I use the invasive garden ant, Lasius neglectus, to investigate how colonies mitigate lethal infections and prevent them from spreading systemically. I find that ants have evolved ‘destructive disinfection’ – a behaviour that uses endogenously produced acidic poison to kill diseased brood and to prevent the pathogen from replicating. In the second experimental chapter, I continue to study the use of poison in invasive garden ant colonies, finding that it is sprayed prophylactically within the nest. However, this spraying has negative effects on developing pupae when they have had their cocoons artificially removed. Hence, I suggest that acidic nest sanitation may be maintaining larval cocoon spinning in this species. In the next experimental chapter, I investigated how colony founding black garden ant queens (Lasius niger) prevent disease when a co-foundress dies. I show that ant queens prophylactically perform undertaking behaviours, similar to those performed by the workers in mature nests. When a co-foundress was infected, these undertaking behaviours improved the survival of the healthy queen. In the final data chapter, I explored how immunocompetence (measured as antifungal activity) changes as incipient black garden ant colonies grow and mature, from the solitary queen phase to colonies with several hundred workers. Queen and worker antifungal activity varied throughout this time period, but despite social immunity, did not decrease as colonies matured. In addition to the above data chapters, this thesis includes two co-authored reviews. In the first, we examine the state of the art in the field of social immunity and how it might develop in the future. In the second, we identify several challenges and open questions in the study of disease defence in animals. We highlight how social insects offer a unique model to tackle some of these problems, as disease defence can be studied from the cell to the society. "}],"supervisor":[{"last_name":"Cremer","first_name":"Sylvia M","id":"2F64EC8C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2193-3868","full_name":"Cremer, Sylvia M"}],"date_updated":"2026-04-16T10:07:02Z","department":[{"_id":"SyCr"}],"date_published":"2017-09-26T00:00:00Z","related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"806"},{"status":"public","relation":"part_of_dissertation","id":"616"},{"relation":"part_of_dissertation","status":"public","id":"732"},{"id":"734","status":"public","relation":"part_of_dissertation"}]},"publisher":"Institute of Science and Technology Austria","degree_awarded":"PhD","language":[{"iso":"eng"}],"oa_version":"Published Version","citation":{"ista":"Pull C. 2017. Disease defence in garden ants. Institute of Science and Technology Austria.","mla":"Pull, Christopher. <i>Disease Defence in Garden Ants</i>. Institute of Science and Technology Austria, 2017, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_861\">10.15479/AT:ISTA:th_861</a>.","chicago":"Pull, Christopher. “Disease Defence in Garden Ants.” Institute of Science and Technology Austria, 2017. <a href=\"https://doi.org/10.15479/AT:ISTA:th_861\">https://doi.org/10.15479/AT:ISTA:th_861</a>.","ieee":"C. Pull, “Disease defence in garden ants,” Institute of Science and Technology Austria, 2017.","apa":"Pull, C. (2017). <i>Disease defence in garden ants</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:th_861\">https://doi.org/10.15479/AT:ISTA:th_861</a>","ama":"Pull C. Disease defence in garden ants. 2017. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_861\">10.15479/AT:ISTA:th_861</a>","short":"C. Pull, Disease Defence in Garden Ants, Institute of Science and Technology Austria, 2017."},"publist_id":"6830","corr_author":"1","author":[{"full_name":"Pull, Christopher","orcid":"0000-0003-1122-3982","id":"3C7F4840-F248-11E8-B48F-1D18A9856A87","first_name":"Christopher","last_name":"Pull"}],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd"},{"citation":{"ama":"Jesse F. The lac operon in the wild. 2017. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_857\">10.15479/AT:ISTA:th_857</a>","short":"F. Jesse, The Lac Operon in the Wild, Institute of Science and Technology Austria, 2017.","apa":"Jesse, F. (2017). <i>The lac operon in the wild</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:th_857\">https://doi.org/10.15479/AT:ISTA:th_857</a>","ista":"Jesse F. 2017. The lac operon in the wild. Institute of Science and Technology Austria.","mla":"Jesse, Fabienne. <i>The Lac Operon in the Wild</i>. Institute of Science and Technology Austria, 2017, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_857\">10.15479/AT:ISTA:th_857</a>.","ieee":"F. Jesse, “The lac operon in the wild,” Institute of Science and Technology Austria, 2017.","chicago":"Jesse, Fabienne. “The Lac Operon in the Wild.” Institute of Science and Technology Austria, 2017. <a href=\"https://doi.org/10.15479/AT:ISTA:th_857\">https://doi.org/10.15479/AT:ISTA:th_857</a>."},"publist_id":"6829","oa_version":"Published Version","language":[{"iso":"eng"}],"author":[{"first_name":"Fabienne","last_name":"Jesse","id":"4C8C26A4-F248-11E8-B48F-1D18A9856A87","full_name":"Jesse, Fabienne"}],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","corr_author":"1","supervisor":[{"orcid":"0000-0002-4624-4612","full_name":"Bollback, Jonathan P","id":"2C6FA9CC-F248-11E8-B48F-1D18A9856A87","first_name":"Jonathan P","last_name":"Bollback"}],"abstract":[{"lang":"eng","text":"The lac operon is a classic model system for bacterial gene regulation, and has been studied extensively in E. coli, a classic model organism. However, not much is known about E. coli’s ecology and life outside the laboratory, in particular in soil and water environments. The natural diversity of the lac operon outside the laboratory, its role in the ecology of E. coli and the selection pressures it is exposed to, are similarly unknown.\r\nIn Chapter Two of this thesis, I explore the genetic diversity, phylogenetic history and signatures of selection of the lac operon across 20 natural isolates of E. coli and divergent clades of Escherichia. I found that complete lac operons were present in all isolates examined, which in all but one case were functional. The lac operon phylogeny conformed to the whole-genome phylogeny of the divergent Escherichia clades, which excludes horizontal gene transfer as an explanation for the presence of functional lac operons in these clades. All lac operon genes showed a signature of purifying selection; this signature was strongest for the lacY gene. Lac operon genes of human and environmental isolates showed similar signatures of selection, except the lacZ gene, which showed a stronger signature of selection in environmental isolates.\r\nIn Chapter Three, I try to identify the natural genetic variation relevant for phenotype and fitness in the lac operon, comparing growth rate on lactose and LacZ activity of the lac operons of these wild isolates in a common genetic background. Sequence variation in the lac promoter region, upstream of the -10 and -35 RNA polymerase binding motif, predicted variation in LacZ activity at full induction, using a thermodynamic model of polymerase binding (Tugrul, 2016). However, neither variation in LacZ activity, nor RNA polymerase binding predicted by the model correlated with variation in growth rate. Lac operons of human and environmental isolates did not differ systematically in either growth rate on lactose or LacZ protein activity, suggesting that these lac operons have been exposed to similar selection pressures. We thus have no evidence that the phenotypic variation we measured is relevant for fitness.\r\nTo start assessing the effect of genomic background on the growth phenotype conferred by the lac operon, I compared growth on minimal medium with lactose between lac operon constructs and the corresponding original isolates, I found that maximal growth rate was determined by genomic background, with almost all backgrounds conferring higher growth rates than lab strain K12 MG1655. However, I found no evidence that the lactose concentration at which growth was half maximal depended on genomic background."}],"department":[{"_id":"JoBo"}],"date_updated":"2026-04-08T14:18:16Z","ddc":["576","577","579"],"publisher":"Institute of Science and Technology Austria","degree_awarded":"PhD","date_published":"2017-08-25T00:00:00Z","file":[{"file_name":"IST-2017-857-v1+1_thesis_fabienne.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:48:10Z","file_size":3417773,"date_created":"2018-12-12T10:17:00Z","checksum":"c62257a7bff0c5f39e1abffc6bfcca5c","relation":"main_file","creator":"system","file_id":"5252","access_level":"open_access"},{"access_level":"closed","checksum":"fc87d7d72fce52824a3ae7dcad0413a8","date_created":"2019-04-05T08:51:59Z","creator":"dernst","file_id":"6212","relation":"source_file","date_updated":"2020-07-14T12:48:10Z","content_type":"application/x-tex","file_size":215899,"file_name":"2017_thesis_Jesse_source.tex"}],"article_processing_charge":"No","month":"08","title":"The lac operon in the wild","page":"87","project":[{"_id":"2578D616-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Selective Barriers to Horizontal Gene Transfer","grant_number":"648440"}],"pubrep_id":"857","day":"25","tmp":{"short":"CC BY (4.0)","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)"},"OA_place":"publisher","date_created":"2018-12-11T11:48:41Z","ec_funded":1,"acknowledgement":"ERC H2020 programme (grant agreement no. 648440)\r\nThanks to Jon Bollback for giving me the chance to do this work, for sharing the ideas that lay at the basis of this work, for his honesty and openness, showing himself to me as a person and not just as a boss. Thanks to Nick Barton for his guidance at the last stage, reading and commenting extensively on several versions of this manuscript, and for his encouragement; thanks to both Jon and Nick for their kindness and patience. Thanks to Erik van Nimwegen and Calin Guet for their time and willingness to be in my thesis committee, and to Erik van Nimwegen especially for agreeing to enter my thesis committee at the last moment, and for his very sharp, helpful and relevant comments during and after the defense. Thanks to my collaborators and discussion partners: Anne Kupczok, for her guidance, ideas and discussions during the construction of the manuscript of Chapter Two, and her comments on the manuscript; Georg Rieckh for making me aware of the issue of parameter identifiability, suggesting how to solve it, and for his unfortunate idea to start the plasmid enterprise in the first place; Murat Tugrul for sharing his model, for his enthusiasm, and his comments on Chapter Three; Srdjan Sarikas for his collaboration on the Monod model fitting, fast forwarding the analysis to turbo speed and making beautiful figures, and making the discussion fun on top of it all; Vanessa Barone for her last minute comments, especially on Chapter Three, providing a sharp and very helpful experimentalist perspective at the last moment; Maros Pleska and Marjon de Vos for their comments on the manuscript of Chapter Two; Gasper Tkacik for his crucial input on the relation between growth rate and lactose concentration; Bor Kavcic for his input on growth rate modeling and error propagation. Thanks to the Bollback, Bollenbach, Barton, Guet and Tkacik group members for both pro- viding an inspiring and supportive scientific environment to work in, as well as a lot of warmth and colour to everyday life. And thanks to the friends I found here, to the people who were there for me and to the people who changed my life, making it stranger and more beautiful than I could have imagined, Maros, Vanessa, Tade, Suzi, Andrej, Peter, Tiago, Kristof, Karin, Irene, Misha, Mato, Guillaume and Zanin. ","oa":1,"has_accepted_license":"1","doi":"10.15479/AT:ISTA:th_857","publication_identifier":{"issn":["2663-337X"]},"_id":"820","alternative_title":["ISTA Thesis"],"status":"public","type":"dissertation","year":"2017","file_date_updated":"2020-07-14T12:48:10Z","publication_status":"published"},{"tmp":{"name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode","image":"/image/cc_by_nd.png","short":"CC BY-ND (4.0)"},"pubrep_id":"854","day":"09","date_created":"2018-12-11T11:48:41Z","acknowledgement":"First, I am thankful to my advisor, Krishnendu Chatterjee, for offering me the opportunity to\r\nmaterialize my scientific curiosity in a remarkably wide range of interesting topics, as well as for his constant availability and continuous support throughout my doctoral studies. I have had the privilege of collaborating with, discussing and getting inspired by all members of my committee: Thomas A. Henzinger, Ulrich Schmid and Martin A. Nowak. The role of the above four people has been very instrumental both to the research carried out for this dissertation, and to the researcher I evolved to in the process.\r\nI have greatly enjoyed my numerous brainstorming sessions with Rasmus Ibsen-Jensen, many\r\nof which led to results on low-treewidth graphs presented here.  I thank Alex Kößler for our\r\ndiscussions on modeling and analyzing real-time scheduling algorithms, Yaron Velner for our\r\ncollaboration on the Quantitative Interprocedural Analysis framework, and Nishant Sinha for our initial discussions on partial order reduction techniques in stateless model checking. I also thank Jan Otop, Ben Adlam, Bernhard Kragl and Josef Tkadlec for our fruitful collaborations on\r\ntopics outside the scope of this dissertation, as well as the interns Prateesh Goyal, Amir Kafshdar Goharshady, Samarth Mishra, Bhavya Choudhary and Marek Chalupa, with whom I have shared my excitement on various research topics. Together with my collaborators, I thank officemates and members of the Chatterjee and Henzinger groups throughout the years, Thorsten Tarrach, Ventsi Chonev, Roopsha Samanta, Przemek Daca, Mirco Giacobbe, Tanja Petrov, Ashutosh\r\nGupta,  Arjun Radhakrishna,  Petr Novontý,  Christian Hilbe,  Jakob Ruess,  Martin Chmelik,\r\nCezara Dragoi, Johannes Reiter, Andrey Kupriyanov, Guy Avni, Sasha Rubin, Jessica Davies, Hongfei Fu, Thomas Ferrère, Pavol Cerný, Ali Sezgin, Jan Kretínský, Sergiy Bogomolov, Hui\r\nKong, Benjamin Aminof, Duc-Hiep Chu, and Damien Zufferey.  Besides collaborations and office spaces, with many of the above people I have been fortunate to share numerous whiteboard\r\ndiscussions, as well as memorable long walks and amicable meals accompanied by stimulating\r\nconversations. I am highly indebted to Elisabeth Hacker for her continuous assistance in matters\r\nthat often exceeded her official duties, and who made my integration in Austria a smooth process.","OA_place":"publisher","ec_funded":1,"title":"Algorithmic advances in program analysis and their applications","page":"418","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"file":[{"file_name":"IST-2017-854-v1+1_Pavlogiannis_Thesis_PubRep.pdf","date_updated":"2020-07-14T12:48:10Z","content_type":"application/pdf","file_size":4103115,"checksum":"3a3ec003f6ee73f41f82a544d63dfc77","date_created":"2018-12-12T10:11:44Z","relation":"main_file","file_id":"4900","creator":"system","access_level":"open_access"},{"date_created":"2019-04-05T07:59:31Z","checksum":"bd2facc45ff8a2e20c5ed313c2ccaa83","creator":"dernst","file_id":"6201","relation":"source_file","access_level":"closed","file_name":"2017_thesis_Pavlogiannis.zip","date_updated":"2020-07-14T12:48:10Z","content_type":"application/zip","file_size":14744374}],"article_processing_charge":"No","month":"08","file_date_updated":"2020-07-14T12:48:10Z","year":"2017","publication_status":"published","type":"dissertation","status":"public","alternative_title":["ISTA Thesis"],"_id":"821","doi":"10.15479/AT:ISTA:th_854","publication_identifier":{"issn":["2663-337X"]},"oa":1,"has_accepted_license":"1","corr_author":"1","author":[{"last_name":"Pavlogiannis","first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas"}],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","language":[{"iso":"eng"}],"oa_version":"Published Version","citation":{"ista":"Pavlogiannis A. 2017. Algorithmic advances in program analysis and their applications. Institute of Science and Technology Austria.","mla":"Pavlogiannis, Andreas. <i>Algorithmic Advances in Program Analysis and Their Applications</i>. Institute of Science and Technology Austria, 2017, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_854\">10.15479/AT:ISTA:th_854</a>.","chicago":"Pavlogiannis, Andreas. “Algorithmic Advances in Program Analysis and Their Applications.” Institute of Science and Technology Austria, 2017. <a href=\"https://doi.org/10.15479/AT:ISTA:th_854\">https://doi.org/10.15479/AT:ISTA:th_854</a>.","ieee":"A. Pavlogiannis, “Algorithmic advances in program analysis and their applications,” Institute of Science and Technology Austria, 2017.","apa":"Pavlogiannis, A. (2017). <i>Algorithmic advances in program analysis and their applications</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:th_854\">https://doi.org/10.15479/AT:ISTA:th_854</a>","short":"A. Pavlogiannis, Algorithmic Advances in Program Analysis and Their Applications, Institute of Science and Technology Austria, 2017.","ama":"Pavlogiannis A. Algorithmic advances in program analysis and their applications. 2017. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_854\">10.15479/AT:ISTA:th_854</a>"},"publist_id":"6828","date_published":"2017-08-09T00:00:00Z","related_material":{"record":[{"id":"1602","relation":"part_of_dissertation","status":"public"},{"id":"1604","relation":"part_of_dissertation","status":"public"},{"status":"public","relation":"part_of_dissertation","id":"1437"},{"relation":"part_of_dissertation","status":"public","id":"1071"},{"id":"1607","relation":"part_of_dissertation","status":"public"},{"status":"public","relation":"part_of_dissertation","id":"1714"}]},"publisher":"Institute of Science and Technology Austria","license":"https://creativecommons.org/licenses/by-nd/4.0/","degree_awarded":"PhD","ddc":["000"],"supervisor":[{"last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"}],"abstract":[{"lang":"eng","text":"This dissertation focuses on algorithmic aspects of program verification, and presents modeling and complexity advances on several problems related to the\r\nstatic analysis of programs, the stateless model checking of concurrent programs, and the competitive analysis of real-time scheduling algorithms.\r\nOur contributions can be broadly grouped into five categories.\r\n\r\nOur first contribution is a set of new algorithms and data structures for the quantitative and data-flow analysis of programs, based on the graph-theoretic notion of treewidth.\r\nIt has been observed that the control-flow graphs of typical programs have special structure, and are characterized as graphs of small treewidth.\r\nWe utilize this structural property to provide faster algorithms for the quantitative and data-flow analysis of recursive and concurrent programs.\r\nIn most cases we make an algebraic treatment of the considered problem,\r\nwhere several interesting analyses, such as the reachability, shortest path, and certain kind of data-flow analysis problems follow as special cases. \r\nWe exploit the constant-treewidth property to obtain algorithmic improvements for on-demand versions of the problems, \r\nand provide data structures with various tradeoffs between the resources spent in the preprocessing and querying phase.\r\nWe also improve on the algorithmic complexity of quantitative problems outside the algebraic path framework,\r\nnamely of the minimum mean-payoff, minimum ratio, and minimum initial credit for energy problems.\r\n\r\n\r\nOur second contribution is a set of algorithms for Dyck reachability with applications to data-dependence analysis and alias analysis.\r\nIn particular, we develop an optimal algorithm for Dyck reachability on bidirected graphs, which are ubiquitous in context-insensitive, field-sensitive points-to analysis.\r\nAdditionally, we develop an efficient algorithm for context-sensitive data-dependence analysis via Dyck reachability,\r\nwhere the task is to obtain analysis summaries of library code in the presence of callbacks.\r\nOur algorithm preprocesses libraries in almost linear time, after which the contribution of the library in the complexity of the client analysis is (i)~linear in the number of call sites and (ii)~only logarithmic in the size of the whole library, as opposed to linear in the size of the whole library.\r\nFinally, we prove that Dyck reachability is Boolean Matrix Multiplication-hard in general, and the hardness also holds for graphs of constant treewidth.\r\nThis hardness result strongly indicates that there exist no combinatorial algorithms for Dyck reachability with truly subcubic complexity.\r\n\r\n\r\nOur third contribution is the formalization and algorithmic treatment of the Quantitative Interprocedural Analysis framework.\r\nIn this framework, the transitions of a recursive program are annotated as good, bad or neutral, and receive a weight which measures\r\nthe magnitude of their respective effect.\r\nThe Quantitative Interprocedural Analysis problem asks to determine whether there exists an infinite run of the program where the long-run ratio of the bad weights over the good weights is above a given threshold.\r\nWe illustrate how several quantitative problems related to static analysis of recursive programs can be instantiated in this framework,\r\nand present some case studies to this direction.\r\n\r\n\r\nOur fourth contribution is a new dynamic partial-order reduction for the stateless model checking of concurrent programs. Traditional approaches rely on the standard Mazurkiewicz equivalence between  traces, by means of partitioning the trace space into equivalence classes, and attempting to explore a few representatives from each class.\r\nWe present a new dynamic partial-order reduction method  called the Data-centric Partial Order Reduction (DC-DPOR).\r\nOur algorithm is based on a new equivalence between traces, called the observation equivalence.\r\nDC-DPOR explores a coarser partitioning of the trace space than any exploration method based on the standard Mazurkiewicz equivalence.\r\nDepending on the program, the new partitioning can be even exponentially coarser.\r\nAdditionally, DC-DPOR spends only polynomial time in each explored class.\r\n\r\n\r\nOur fifth contribution is the use of automata and game-theoretic verification techniques in the competitive analysis and synthesis of real-time scheduling algorithms for firm-deadline tasks.\r\nOn the analysis side, we leverage automata on infinite words to compute the competitive ratio of real-time schedulers subject to various environmental constraints.\r\nOn the synthesis side, we introduce a new instance of two-player mean-payoff partial-information games, and show\r\nhow the synthesis of an optimal real-time scheduler can be reduced to computing winning strategies in this new type of games."}],"date_updated":"2026-04-08T14:22:17Z","department":[{"_id":"KrCh"}]},{"type":"journal_article","status":"public","publication_status":"published","year":"2017","quality_controlled":"1","oa":1,"publication_identifier":{"issn":["0027-8424"]},"doi":"10.1073/pnas.1713372114","main_file_link":[{"open_access":"1","url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5635929/"}],"_id":"822","publication":"PNAS","day":"03","pmid":1,"date_created":"2018-12-11T11:48:41Z","ec_funded":1,"scopus_import":"1","volume":114,"month":"10","article_processing_charge":"No","page":"10666 - 10671","title":"Interaction networks, ecological stability, and collective antibiotic tolerance in polymicrobial infections","project":[{"name":"Optimality principles in responses to antibiotics","grant_number":"303507","call_identifier":"FP7","_id":"25E83C2C-B435-11E9-9278-68D0E5697425"},{"grant_number":"P27201-B22","name":"Revealing the mechanisms underlying drug interactions","call_identifier":"FWF","_id":"25E9AF9E-B435-11E9-9278-68D0E5697425"}],"intvolume":"       114","publisher":"National Academy of Sciences","issue":"40","date_published":"2017-10-03T00:00:00Z","abstract":[{"text":"Polymicrobial infections constitute small ecosystems that accommodate several bacterial species. Commonly, these bacteria are investigated in isolation. However, it is unknown to what extent the isolates interact and whether their interactions alter bacterial growth and ecosystem resilience in the presence and absence of antibiotics. We quantified the complete ecological interaction network for 72 bacterial isolates collected from 23 individuals diagnosed with polymicrobial urinary tract infections and found that most interactions cluster based on evolutionary relatedness. Statistical network analysis revealed that competitive and cooperative reciprocal interactions are enriched in the global network, while cooperative interactions are depleted in the individual host community networks. A population dynamics model parameterized by our measurements suggests that interactions restrict community stability, explaining the observed species diversity of these communities. We further show that the clinical isolates frequently protect each other from clinically relevant antibiotics. Together, these results highlight that ecological interactions are crucial for the growth and survival of bacteria in polymicrobial infection communities and affect their assembly and resilience. ","lang":"eng"}],"department":[{"_id":"ToBo"}],"date_updated":"2025-07-10T11:55:08Z","external_id":{"isi":["000412130500061"],"pmid":["28923953"]},"isi":1,"author":[{"id":"3111FFAC-F248-11E8-B48F-1D18A9856A87","last_name":"De Vos","first_name":"Marjon","full_name":"De Vos, Marjon"},{"orcid":"0000-0001-7896-7762","full_name":"Zagórski, Marcin P","last_name":"Zagórski","first_name":"Marcin P","id":"343DA0DC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Mcnally, Alan","first_name":"Alan","last_name":"Mcnally"},{"id":"3E6DB97A-F248-11E8-B48F-1D18A9856A87","last_name":"Bollenbach","first_name":"Mark Tobias","full_name":"Bollenbach, Mark Tobias","orcid":"0000-0003-4398-476X"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","citation":{"mla":"de Vos, Marjon, et al. “Interaction Networks, Ecological Stability, and Collective Antibiotic Tolerance in Polymicrobial Infections.” <i>PNAS</i>, vol. 114, no. 40, National Academy of Sciences, 2017, pp. 10666–71, doi:<a href=\"https://doi.org/10.1073/pnas.1713372114\">10.1073/pnas.1713372114</a>.","ista":"de Vos M, Zagórski MP, Mcnally A, Bollenbach MT. 2017. Interaction networks, ecological stability, and collective antibiotic tolerance in polymicrobial infections. PNAS. 114(40), 10666–10671.","chicago":"Vos, Marjon de, Marcin P Zagórski, Alan Mcnally, and Mark Tobias Bollenbach. “Interaction Networks, Ecological Stability, and Collective Antibiotic Tolerance in Polymicrobial Infections.” <i>PNAS</i>. National Academy of Sciences, 2017. <a href=\"https://doi.org/10.1073/pnas.1713372114\">https://doi.org/10.1073/pnas.1713372114</a>.","ieee":"M. de Vos, M. P. Zagórski, A. Mcnally, and M. T. Bollenbach, “Interaction networks, ecological stability, and collective antibiotic tolerance in polymicrobial infections,” <i>PNAS</i>, vol. 114, no. 40. National Academy of Sciences, pp. 10666–10671, 2017.","apa":"de Vos, M., Zagórski, M. P., Mcnally, A., &#38; Bollenbach, M. T. (2017). Interaction networks, ecological stability, and collective antibiotic tolerance in polymicrobial infections. <i>PNAS</i>. National Academy of Sciences. <a href=\"https://doi.org/10.1073/pnas.1713372114\">https://doi.org/10.1073/pnas.1713372114</a>","short":"M. de Vos, M.P. Zagórski, A. Mcnally, M.T. Bollenbach, PNAS 114 (2017) 10666–10671.","ama":"de Vos M, Zagórski MP, Mcnally A, Bollenbach MT. Interaction networks, ecological stability, and collective antibiotic tolerance in polymicrobial infections. <i>PNAS</i>. 2017;114(40):10666-10671. doi:<a href=\"https://doi.org/10.1073/pnas.1713372114\">10.1073/pnas.1713372114</a>"},"publist_id":"6827","oa_version":"Submitted Version","language":[{"iso":"eng"}]},{"publisher":"Cambridge University Press","arxiv":1,"date_published":"2017-08-18T00:00:00Z","abstract":[{"text":"In shear flows at transitional Reynolds numbers, localized patches of turbulence, known as puffs, coexist with the laminar flow. Recently, Avila et al. (Phys. Rev. Lett., vol. 110, 2013, 224502) discovered two spatially localized relative periodic solutions for pipe flow, which appeared in a saddle-node bifurcation at low Reynolds number. Combining slicing methods for continuous symmetry reduction with Poincaré sections for the first time in a shear flow setting, we compute and visualize the unstable manifold of the lower-branch solution and show that it extends towards the neighbourhood of the upper-branch solution. Surprisingly, this connection even persists far above the bifurcation point and appears to mediate the first stage of the puff generation: amplification of streamwise localized fluctuations. When the state-space trajectories on the unstable manifold reach the vicinity of the upper branch, corresponding fluctuations expand in space and eventually take the usual shape of a puff.","lang":"eng"}],"department":[{"_id":"BjHo"}],"date_updated":"2025-06-04T09:49:26Z","isi":1,"external_id":{"isi":["000408326300001"],"arxiv":["1703.10484"]},"author":[{"full_name":"Budanur, Nazmi B","orcid":"0000-0003-0423-5010","last_name":"Budanur","first_name":"Nazmi B","id":"3EA1010E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Hof, Björn","orcid":"0000-0003-2057-2754","id":"3A374330-F248-11E8-B48F-1D18A9856A87","first_name":"Björn","last_name":"Hof"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ieee":"N. B. Budanur and B. Hof, “Heteroclinic path to spatially localized chaos in pipe flow,” <i>Journal of Fluid Mechanics</i>, vol. 827. Cambridge University Press, 2017.","chicago":"Budanur, Nazmi B, and Björn Hof. “Heteroclinic Path to Spatially Localized Chaos in Pipe Flow.” <i>Journal of Fluid Mechanics</i>. Cambridge University Press, 2017. <a href=\"https://doi.org/10.1017/jfm.2017.516\">https://doi.org/10.1017/jfm.2017.516</a>.","mla":"Budanur, Nazmi B., and Björn Hof. “Heteroclinic Path to Spatially Localized Chaos in Pipe Flow.” <i>Journal of Fluid Mechanics</i>, vol. 827, R1, Cambridge University Press, 2017, doi:<a href=\"https://doi.org/10.1017/jfm.2017.516\">10.1017/jfm.2017.516</a>.","ista":"Budanur NB, Hof B. 2017. Heteroclinic path to spatially localized chaos in pipe flow. Journal of Fluid Mechanics. 827, R1.","short":"N.B. Budanur, B. Hof, Journal of Fluid Mechanics 827 (2017).","ama":"Budanur NB, Hof B. Heteroclinic path to spatially localized chaos in pipe flow. <i>Journal of Fluid Mechanics</i>. 2017;827. doi:<a href=\"https://doi.org/10.1017/jfm.2017.516\">10.1017/jfm.2017.516</a>","apa":"Budanur, N. B., &#38; Hof, B. (2017). Heteroclinic path to spatially localized chaos in pipe flow. <i>Journal of Fluid Mechanics</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/jfm.2017.516\">https://doi.org/10.1017/jfm.2017.516</a>"},"publist_id":"6824","oa_version":"Submitted Version","language":[{"iso":"eng"}],"type":"journal_article","status":"public","publication_status":"published","year":"2017","quality_controlled":"1","oa":1,"article_number":"R1","publication_identifier":{"issn":["0022-1120"]},"doi":"10.1017/jfm.2017.516","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1703.10484"}],"_id":"824","publication":"Journal of Fluid Mechanics","day":"18","date_created":"2018-12-11T11:48:42Z","scopus_import":"1","volume":827,"month":"08","article_processing_charge":"No","title":"Heteroclinic path to spatially localized chaos in pipe flow","intvolume":"       827"},{"abstract":[{"lang":"eng","text":"We present an efficient algorithm to compute Euler characteristic curves of gray scale images of arbitrary dimension. In various applications the Euler characteristic curve is used as a descriptor of an image. Our algorithm is the first streaming algorithm for Euler characteristic curves. The usage of streaming removes the necessity to store the entire image in RAM. Experiments show that our implementation handles terabyte scale images on commodity hardware. Due to lock-free parallelism, it scales well with the number of processor cores. Additionally, we put the concept of the Euler characteristic curve in the wider context of computational topology. In particular, we explain the connection with persistence diagrams."}],"department":[{"_id":"HeEd"}],"date_updated":"2025-06-04T09:54:22Z","external_id":{"arxiv":["1705.02045"],"isi":["000432085900032"]},"isi":1,"editor":[{"first_name":"Michael","last_name":"Felsberg","full_name":"Felsberg, Michael"},{"full_name":"Heyden, Anders","last_name":"Heyden","first_name":"Anders"},{"last_name":"Krüger","first_name":"Norbert","full_name":"Krüger, Norbert"}],"publisher":"Springer","conference":{"start_date":"2017-08-22","location":"Ystad, Sweden","end_date":"2017-08-24","name":"CAIP: Computer Analysis of Images and Patterns"},"arxiv":1,"date_published":"2017-07-28T00:00:00Z","citation":{"apa":"Heiss, T., &#38; Wagner, H. (2017). Streaming algorithm for Euler characteristic curves of multidimensional images. In M. Felsberg, A. Heyden, &#38; N. Krüger (Eds.) (Vol. 10424, pp. 397–409). Presented at the CAIP: Computer Analysis of Images and Patterns, Ystad, Sweden: Springer. <a href=\"https://doi.org/10.1007/978-3-319-64689-3_32\">https://doi.org/10.1007/978-3-319-64689-3_32</a>","ama":"Heiss T, Wagner H. Streaming algorithm for Euler characteristic curves of multidimensional images. In: Felsberg M, Heyden A, Krüger N, eds. Vol 10424. Springer; 2017:397-409. doi:<a href=\"https://doi.org/10.1007/978-3-319-64689-3_32\">10.1007/978-3-319-64689-3_32</a>","short":"T. Heiss, H. Wagner, in:, M. Felsberg, A. Heyden, N. Krüger (Eds.), Springer, 2017, pp. 397–409.","chicago":"Heiss, Teresa, and Hubert Wagner. “Streaming Algorithm for Euler Characteristic Curves of Multidimensional Images.” edited by Michael Felsberg, Anders Heyden, and Norbert Krüger, 10424:397–409. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-64689-3_32\">https://doi.org/10.1007/978-3-319-64689-3_32</a>.","ieee":"T. Heiss and H. Wagner, “Streaming algorithm for Euler characteristic curves of multidimensional images,” presented at the CAIP: Computer Analysis of Images and Patterns, Ystad, Sweden, 2017, vol. 10424, pp. 397–409.","ista":"Heiss T, Wagner H. 2017. Streaming algorithm for Euler characteristic curves of multidimensional images. CAIP: Computer Analysis of Images and Patterns, LNCS, vol. 10424, 397–409.","mla":"Heiss, Teresa, and Hubert Wagner. <i>Streaming Algorithm for Euler Characteristic Curves of Multidimensional Images</i>. Edited by Michael Felsberg et al., vol. 10424, Springer, 2017, pp. 397–409, doi:<a href=\"https://doi.org/10.1007/978-3-319-64689-3_32\">10.1007/978-3-319-64689-3_32</a>."},"publist_id":"6815","oa_version":"Submitted Version","language":[{"iso":"eng"}],"author":[{"id":"4879BB4E-F248-11E8-B48F-1D18A9856A87","first_name":"Teresa","last_name":"Heiss","full_name":"Heiss, Teresa","orcid":"0000-0002-1780-2689"},{"full_name":"Wagner, Hubert","id":"379CA8B8-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Hubert"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","oa":1,"publication_identifier":{"issn":["0302-9743"]},"doi":"10.1007/978-3-319-64689-3_32","_id":"833","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1705.02045"}],"alternative_title":["LNCS"],"type":"conference","status":"public","year":"2017","publication_status":"published","quality_controlled":"1","volume":10424,"month":"07","article_processing_charge":"No","title":"Streaming algorithm for Euler characteristic curves of multidimensional images","page":"397 - 409","intvolume":"     10424","day":"28","date_created":"2018-12-11T11:48:45Z","scopus_import":"1"},{"intvolume":"       198","project":[{"_id":"255D761E-B435-11E9-9278-68D0E5697425","name":"Topological Complex Systems","grant_number":"318493","call_identifier":"FP7"}],"page":"119 - 136","title":"Finding eigenvalues of self-maps with the Kronecker canonical form","article_processing_charge":"No","month":"07","volume":198,"scopus_import":"1","ec_funded":1,"date_created":"2018-12-11T11:48:46Z","day":"27","publication":"Special Sessions in Applications of Computer Algebra","_id":"836","doi":"10.1007/978-3-319-56932-1_8","publication_identifier":{"isbn":["978-331956930-7"]},"quality_controlled":"1","year":"2017","publication_status":"published","type":"conference","status":"public","alternative_title":["PROMS"],"language":[{"iso":"eng"}],"oa_version":"None","publist_id":"6812","citation":{"chicago":"Ethier, Marc, Grzegorz Jablonski, and Marian Mrozek. “Finding Eigenvalues of Self-Maps with the Kronecker Canonical Form.” In <i>Special Sessions in Applications of Computer Algebra</i>, 198:119–36. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-56932-1_8\">https://doi.org/10.1007/978-3-319-56932-1_8</a>.","ieee":"M. Ethier, G. Jablonski, and M. Mrozek, “Finding eigenvalues of self-maps with the Kronecker canonical form,” in <i>Special Sessions in Applications of Computer Algebra</i>, Kalamata, Greece, 2017, vol. 198, pp. 119–136.","ista":"Ethier M, Jablonski G, Mrozek M. 2017. Finding eigenvalues of self-maps with the Kronecker canonical form. Special Sessions in Applications of Computer Algebra. ACA: Applications of Computer Algebra, PROMS, vol. 198, 119–136.","mla":"Ethier, Marc, et al. “Finding Eigenvalues of Self-Maps with the Kronecker Canonical Form.” <i>Special Sessions in Applications of Computer Algebra</i>, vol. 198, Springer, 2017, pp. 119–36, doi:<a href=\"https://doi.org/10.1007/978-3-319-56932-1_8\">10.1007/978-3-319-56932-1_8</a>.","apa":"Ethier, M., Jablonski, G., &#38; Mrozek, M. (2017). Finding eigenvalues of self-maps with the Kronecker canonical form. In <i>Special Sessions in Applications of Computer Algebra</i> (Vol. 198, pp. 119–136). Kalamata, Greece: Springer. <a href=\"https://doi.org/10.1007/978-3-319-56932-1_8\">https://doi.org/10.1007/978-3-319-56932-1_8</a>","ama":"Ethier M, Jablonski G, Mrozek M. Finding eigenvalues of self-maps with the Kronecker canonical form. In: <i>Special Sessions in Applications of Computer Algebra</i>. Vol 198. Springer; 2017:119-136. doi:<a href=\"https://doi.org/10.1007/978-3-319-56932-1_8\">10.1007/978-3-319-56932-1_8</a>","short":"M. Ethier, G. Jablonski, M. Mrozek, in:, Special Sessions in Applications of Computer Algebra, Springer, 2017, pp. 119–136."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"first_name":"Marc","last_name":"Ethier","full_name":"Ethier, Marc"},{"first_name":"Grzegorz","last_name":"Jablonski","id":"4483EF78-F248-11E8-B48F-1D18A9856A87","full_name":"Jablonski, Grzegorz","orcid":"0000-0002-3536-9866"},{"last_name":"Mrozek","first_name":"Marian","full_name":"Mrozek, Marian"}],"isi":1,"external_id":{"isi":["000434088200008"]},"date_updated":"2025-04-15T08:37:55Z","department":[{"_id":"HeEd"}],"abstract":[{"text":"Recent research has examined how to study the topological features of a continuous self-map by means of the persistence of the eigenspaces, for given eigenvalues, of the endomorphism induced in homology over a field. This raised the question of how to select dynamically significant eigenvalues. The present paper aims to answer this question, giving an algorithm that computes the persistence of eigenspaces for every eigenvalue simultaneously, also expressing said eigenspaces as direct sums of “finite” and “singular” subspaces.","lang":"eng"}],"date_published":"2017-07-27T00:00:00Z","conference":{"name":"ACA: Applications of Computer Algebra","end_date":"2015-07-23","location":"Kalamata, Greece","start_date":"2015-07-20"},"publisher":"Springer"},{"publication_identifier":{"issn":["2663-337X"]},"doi":"10.15479/AT:ISTA:th_858","_id":"837","has_accepted_license":"1","oa":1,"status":"public","type":"dissertation","file_date_updated":"2020-07-14T12:48:12Z","publication_status":"published","year":"2017","alternative_title":["ISTA Thesis"],"title":"Reactivation of the hippocampal cognitive map in goal-directed spatial tasks","page":"93","month":"08","article_processing_charge":"No","file":[{"access_level":"closed","relation":"source_file","file_id":"6213","creator":"dernst","checksum":"f11925fbbce31e495124b6bc4f10573c","date_created":"2019-04-05T08:59:51Z","file_size":3589490,"content_type":"application/vnd.openxmlformats-officedocument.wordprocessingml.document","date_updated":"2020-07-14T12:48:12Z","file_name":"2017_Xu_Haibing_Thesis_Source.docx"},{"date_created":"2019-04-05T08:59:51Z","checksum":"ffb10749a537d615fab1ef0937ccb157","creator":"dernst","file_id":"6214","relation":"main_file","access_level":"open_access","file_name":"2017_Xu_Thesis_IST.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:48:12Z","file_size":11668613}],"OA_place":"publisher","date_created":"2018-12-11T11:48:46Z","acknowledgement":"I am very grateful for the opportunity I have had as a graduate student to explore and incredibly interesting branch of neuroscience, and for the people who made it possible. Firstly, I would like to offer my thanks to my supervisor Professor Jozsef Csicsvari for his great support, guidance and patience offered over the years. The door to his office was always open whenever I had questions. I have learned a lot from him about carefully designing experiments, asking interesting questions and how to integrate results into a broader picture. I also express my gratitude to the remarkable post- doc , Dr. Joseph O’Neill. He is a gre at scientific role model who is always willing to teach , and advice and talk through problems with his full attention. Many thanks to my wonderful “office mates” over the years and their support and encouragement, Alice Avernhe, Philipp Schönenberger, Desiree Dickerson, Karel Blahna, Charlotte Boccara, Igor Gridchyn, Peter Baracskay, Krisztián Kovács, Dámaris Rangel, Karola Käfer and Federico Stella. They were the ones in the lab for the many useful discussions about science and for making the laboratory such a nice and friendly place to work in. A special thank goes to Michael LoBianco and Jago Wallenschus for wonderful technical support. I would also like to thank Professor Peter Jonas and Professor David M Bannerman for being my qualifying exam and thesi s committee members despite their busy schedule. I am also very thankful to IST Austria for their support all throughout my PhD. ","day":"23","pubrep_id":"858","tmp":{"short":"CC BY (4.0)","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)"},"ddc":["571"],"department":[{"_id":"JoCs"}],"date_updated":"2026-06-18T18:56:25Z","supervisor":[{"id":"3FA14672-F248-11E8-B48F-1D18A9856A87","first_name":"Jozsef L","last_name":"Csicsvari","full_name":"Csicsvari, Jozsef L","orcid":"0000-0002-5193-4036"}],"abstract":[{"lang":"eng","text":"The hippocampus is a key brain region for memory and notably for spatial memory, and is needed for both spatial working and reference memories. Hippocampal place cells selectively discharge in specific locations of the environment to form mnemonic represen tations of space. Several behavioral protocols have been designed to test spatial memory which requires the experimental subject to utilize working memory and reference memory. However, less is known about how these memory traces are presented in the hippo campus, especially considering tasks that require both spatial working and long -term reference memory demand. The aim of my thesis was to elucidate how spatial working memory, reference memory, and the combination of both are represented in the hippocampus. In this thesis, using a radial eight -arm maze, I examined how the combined demand on these memories influenced place cell assemblies while reference memories were partially updated by changing some of the reward- arms. This was contrasted with task varian ts requiring working or reference memories only. Reference memory update led to gradual place field shifts towards the rewards on the switched arms. Cells developed enhanced firing in passes between newly -rewarded arms as compared to those containing an unchanged reward. The working memory task did not show such gradual changes. Place assemblies on occasions replayed trajectories of the maze; at decision points the next arm choice was preferentially replayed in tasks needing reference memory while in the pure working memory task the previously visited arm was replayed. Hence trajectory replay only reflected the decision of the animal in tasks needing reference memory update. At the reward locations, in all three tasks outbound trajectories of the current arm were preferentially replayed, showing the animals’ next path to the center. At reward locations trajectories were replayed preferentially in reverse temporal order. Moreover, in the center reverse replay was seen in the working memory task but in the other tasks forward replay was seen. Hence, the direction of reactivation was determined by the goal locations so that part of the trajectory which was closer to the goal was reactivated later in an HSE while places further away from the goal were reactivated earlier. Altogether my work demonstrated that reference memory update triggers several levels of reorganization of the hippocampal cognitive map which are not seen in simpler working memory demand s. Moreover, hippocampus is likely to be involved in spatial decisions through reactivating planned trajectories when reference memory recall is required for such a decision. "}],"date_published":"2017-08-23T00:00:00Z","degree_awarded":"PhD","publisher":"Institute of Science and Technology Austria","related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"5828"}]},"oa_version":"Published Version","language":[{"iso":"eng"}],"publist_id":"6811","citation":{"short":"H. Xu, Reactivation of the Hippocampal Cognitive Map in Goal-Directed Spatial Tasks, Institute of Science and Technology Austria, 2017.","ama":"Xu H. Reactivation of the hippocampal cognitive map in goal-directed spatial tasks. 2017. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_858\">10.15479/AT:ISTA:th_858</a>","apa":"Xu, H. (2017). <i>Reactivation of the hippocampal cognitive map in goal-directed spatial tasks</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:th_858\">https://doi.org/10.15479/AT:ISTA:th_858</a>","ista":"Xu H. 2017. Reactivation of the hippocampal cognitive map in goal-directed spatial tasks. Institute of Science and Technology Austria.","mla":"Xu, Haibing. <i>Reactivation of the Hippocampal Cognitive Map in Goal-Directed Spatial Tasks</i>. Institute of Science and Technology Austria, 2017, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_858\">10.15479/AT:ISTA:th_858</a>.","ieee":"H. Xu, “Reactivation of the hippocampal cognitive map in goal-directed spatial tasks,” Institute of Science and Technology Austria, 2017.","chicago":"Xu, Haibing. “Reactivation of the Hippocampal Cognitive Map in Goal-Directed Spatial Tasks.” Institute of Science and Technology Austria, 2017. <a href=\"https://doi.org/10.15479/AT:ISTA:th_858\">https://doi.org/10.15479/AT:ISTA:th_858</a>."},"corr_author":"1","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","author":[{"id":"310349D0-F248-11E8-B48F-1D18A9856A87","first_name":"Haibing","last_name":"Xu","full_name":"Xu, Haibing"}]},{"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","author":[{"full_name":"Rybar, Michal","id":"2B3E3DE8-F248-11E8-B48F-1D18A9856A87","last_name":"Rybar","first_name":"Michal"}],"corr_author":"1","publist_id":"6810","citation":{"chicago":"Rybar, Michal. “(The Exact Security of) Message Authentication Codes.” Institute of Science and Technology Austria, 2017. <a href=\"https://doi.org/10.15479/AT:ISTA:th_828\">https://doi.org/10.15479/AT:ISTA:th_828</a>.","ieee":"M. Rybar, “(The exact security of) Message authentication codes,” Institute of Science and Technology Austria, 2017.","mla":"Rybar, Michal. <i>(The Exact Security of) Message Authentication Codes</i>. Institute of Science and Technology Austria, 2017, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_828\">10.15479/AT:ISTA:th_828</a>.","ista":"Rybar M. 2017. (The exact security of) Message authentication codes. Institute of Science and Technology Austria.","apa":"Rybar, M. (2017). <i>(The exact security of) Message authentication codes</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:th_828\">https://doi.org/10.15479/AT:ISTA:th_828</a>","short":"M. Rybar, (The Exact Security of) Message Authentication Codes, Institute of Science and Technology Austria, 2017.","ama":"Rybar M. (The exact security of) Message authentication codes. 2017. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_828\">10.15479/AT:ISTA:th_828</a>"},"language":[{"iso":"eng"}],"oa_version":"Published Version","degree_awarded":"PhD","related_material":{"record":[{"relation":"part_of_dissertation","status":"public","id":"2082"},{"id":"6196","status":"public","relation":"part_of_dissertation"}]},"publisher":"Institute of Science and Technology Austria","date_published":"2017-06-26T00:00:00Z","date_updated":"2026-04-08T14:18:39Z","department":[{"_id":"KrPi"}],"abstract":[{"text":"In this thesis we discuss the exact security of message authentications codes HMAC , NMAC , and PMAC . NMAC is a mode of operation which turns a fixed input-length keyed hash function f into a variable input-length function. A practical single-key variant of NMAC called HMAC is a very popular and widely deployed message authentication code (MAC). PMAC is a block-cipher based mode of operation, which also happens to be the most famous fully parallel MAC. NMAC was introduced by Bellare, Canetti and Krawczyk Crypto’96, who proved it to be a secure pseudorandom function (PRF), and thus also a MAC, under two assumptions. Unfortunately, for many instantiations of HMAC one of them has been found to be wrong. To restore the provable guarantees for NMAC , Bellare [Crypto’06] showed its security without this assumption. PMAC was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a pseudorandom permutation over n -bit strings, PMAC constitutes a provably secure variable input-length PRF. For adversaries making q queries, each of length at most ` (in n -bit blocks), and of total length σ ≤ q` , the original paper proves an upper bound on the distinguishing advantage of O ( σ 2 / 2 n ), while the currently best bound is O ( qσ/ 2 n ). In this work we show that this bound is tight by giving an attack with advantage Ω( q 2 `/ 2 n ). In the PMAC construction one initially XORs a mask to every message block, where the mask for the i th block is computed as τ i := γ i · L , where L is a (secret) random value, and γ i is the i -th codeword of the Gray code. Our attack applies more generally to any sequence of γ i ’s which contains a large coset of a subgroup of GF (2 n ). As for NMAC , our first contribution is a simpler and uniform proof: If f is an ε -secure PRF (against q queries) and a δ - non-adaptively secure PRF (against q queries), then NMAC f is an ( ε + `qδ )-secure PRF against q queries of length at most ` blocks each. We also show that this ε + `qδ bound is basically tight by constructing an f for which an attack with advantage `qδ exists. Moreover, we analyze the PRF-security of a modification of NMAC called NI by An and Bellare that avoids the constant rekeying on multi-block messages in NMAC and allows for an information-theoretic analysis. We carry out such an analysis, obtaining a tight `q 2 / 2 c bound for this step, improving over the trivial bound of ` 2 q 2 / 2 c . Finally, we investigate, if the security of PMAC can be further improved by using τ i ’s that are k -wise independent, for k &gt; 1 (the original has k = 1). We observe that the security of PMAC will not increase in general if k = 2, and then prove that the security increases to O ( q 2 / 2 n ), if the k = 4. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether k = 3 is already sufficient to get this level of security is left as an open problem. Keywords: Message authentication codes, Pseudorandom functions, HMAC, PMAC. ","lang":"eng"}],"ddc":["000"],"date_created":"2018-12-11T11:48:46Z","OA_place":"publisher","day":"26","pubrep_id":"828","month":"06","article_processing_charge":"No","file":[{"date_created":"2018-12-12T10:10:13Z","checksum":"ff8639ec4bded6186f44c7bd3ee26804","file_id":"4799","creator":"system","relation":"main_file","access_level":"open_access","file_name":"IST-2017-828-v1+3_2017_Rybar_thesis.pdf","date_updated":"2020-07-14T12:48:12Z","content_type":"application/pdf","file_size":847400},{"file_size":26054879,"date_updated":"2020-07-14T12:48:12Z","content_type":"application/zip","file_name":"2017_Thesis_Rybar_source.zip","access_level":"closed","creator":"dernst","file_id":"6202","relation":"source_file","date_created":"2019-04-05T08:24:11Z","checksum":"3462101745ce8ad199c2d0f75dae4a7e"}],"title":"(The exact security of) Message authentication codes","page":"86","alternative_title":["ISTA Thesis"],"publication_status":"published","file_date_updated":"2020-07-14T12:48:12Z","year":"2017","type":"dissertation","status":"public","has_accepted_license":"1","oa":1,"_id":"838","doi":"10.15479/AT:ISTA:th_828","publication_identifier":{"issn":["2663-337X"]}},{"oa_version":"None","language":[{"iso":"eng"}],"title":"Computational topology for structural molecular biology","page":"1709 - 1735","citation":{"chicago":"Edelsbrunner, Herbert, and Patrice Koehl. “Computational Topology for Structural Molecular Biology.” In <i>Handbook of Discrete and Computational Geometry, Third Edition</i>, edited by Csaba Toth, Joseph O’Rourke, and Jacob Goodman, 1709–35. Handbook of Discrete and Computational Geometry. Taylor &#38; Francis, 2017. <a href=\"https://doi.org/10.1201/9781315119601\">https://doi.org/10.1201/9781315119601</a>.","ieee":"H. Edelsbrunner and P. Koehl, “Computational topology for structural molecular biology,” in <i>Handbook of Discrete and Computational Geometry, Third Edition</i>, C. Toth, J. O’Rourke, and J. Goodman, Eds. Taylor &#38; Francis, 2017, pp. 1709–1735.","ista":"Edelsbrunner H, Koehl P. 2017.Computational topology for structural molecular biology. In: Handbook of Discrete and Computational Geometry, Third Edition. , 1709–1735.","mla":"Edelsbrunner, Herbert, and Patrice Koehl. “Computational Topology for Structural Molecular Biology.” <i>Handbook of Discrete and Computational Geometry, Third Edition</i>, edited by Csaba Toth et al., Taylor &#38; Francis, 2017, pp. 1709–35, doi:<a href=\"https://doi.org/10.1201/9781315119601\">10.1201/9781315119601</a>.","apa":"Edelsbrunner, H., &#38; Koehl, P. (2017). Computational topology for structural molecular biology. In C. Toth, J. O’Rourke, &#38; J. Goodman (Eds.), <i>Handbook of Discrete and Computational Geometry, Third Edition</i> (pp. 1709–1735). Taylor &#38; Francis. <a href=\"https://doi.org/10.1201/9781315119601\">https://doi.org/10.1201/9781315119601</a>","short":"H. Edelsbrunner, P. Koehl, in:, C. Toth, J. O’Rourke, J. Goodman (Eds.), Handbook of Discrete and Computational Geometry, Third Edition, Taylor &#38; Francis, 2017, pp. 1709–1735.","ama":"Edelsbrunner H, Koehl P. Computational topology for structural molecular biology. In: Toth C, O’Rourke J, Goodman J, eds. <i>Handbook of Discrete and Computational Geometry, Third Edition</i>. Handbook of Discrete and Computational Geometry. Taylor &#38; Francis; 2017:1709-1735. doi:<a href=\"https://doi.org/10.1201/9781315119601\">10.1201/9781315119601</a>"},"publist_id":"7970","article_processing_charge":"No","month":"11","day":"09","date_created":"2018-12-11T11:44:32Z","scopus_import":"1","author":[{"orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Koehl","first_name":"Patrice","full_name":"Koehl, Patrice"}],"publication":"Handbook of Discrete and Computational Geometry, Third Edition","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","editor":[{"first_name":"Csaba","last_name":"Toth","full_name":"Toth, Csaba"},{"last_name":"O'Rourke","first_name":"Joseph","full_name":"O'Rourke, Joseph"},{"first_name":"Jacob","last_name":"Goodman","full_name":"Goodman, Jacob"}],"doi":"10.1201/9781315119601","publication_identifier":{"eisbn":["9781498711425"]},"_id":"84","abstract":[{"text":"The advent of high-throughput technologies and the concurrent advances in information sciences have led to a data revolution in biology. This revolution is most significant in molecular biology, with an increase in the number and scale of the “omics” projects over the last decade. Genomics projects, for example, have produced impressive advances in our knowledge of the information concealed into genomes, from the many genes that encode for the proteins that are responsible for most if not all cellular functions, to the noncoding regions that are now known to provide regulatory functions. Proteomics initiatives help to decipher the role of post-translation modifications on the protein structures and provide maps of protein-protein interactions, while functional genomics is the field that attempts to make use of the data produced by these projects to understand protein functions. The biggest challenge today is to assimilate the wealth of information provided by these initiatives into a conceptual framework that will help us decipher life. For example, the current views of the relationship between protein structure and function remain fragmented. We know of their sequences, more and more about their structures, we have information on their biological activities, but we have difficulties connecting this dotted line into an informed whole. We lack the experimental and computational tools for directly studying protein structure, function, and dynamics at the molecular and supra-molecular levels. In this chapter, we review some of the current developments in building the computational tools that are needed, focusing on the role that geometry and topology play in these efforts. One of our goals is to raise the general awareness about the importance of geometric methods in elucidating the mysterious foundations of our very existence. Another goal is the broadening of what we consider a geometric algorithm. There is plenty of valuable no-man’s-land between combinatorial and numerical algorithms, and it seems opportune to explore this land with a computational-geometric frame of mind.","lang":"eng"}],"department":[{"_id":"HeEd"}],"date_updated":"2023-10-16T11:15:22Z","type":"book_chapter","status":"public","year":"2017","publication_status":"published","date_published":"2017-11-09T00:00:00Z","quality_controlled":"1","series_title":"Handbook of Discrete and Computational Geometry","publisher":"Taylor & Francis"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"31E9F056-F248-11E8-B48F-1D18A9856A87","last_name":"Vukusic","first_name":"Lada","full_name":"Vukusic, Lada","orcid":"0000-0003-2424-8636"},{"full_name":"Kukucka, Josip","id":"3F5D8856-F248-11E8-B48F-1D18A9856A87","last_name":"Kukucka","first_name":"Josip"},{"full_name":"Watzinger, Hannes","id":"35DF8E50-F248-11E8-B48F-1D18A9856A87","first_name":"Hannes","last_name":"Watzinger"},{"full_name":"Katsaros, Georgios","orcid":"0000-0001-8342-202X","first_name":"Georgios","last_name":"Katsaros","id":"38DB5788-F248-11E8-B48F-1D18A9856A87"}],"corr_author":"1","acknowledged_ssus":[{"_id":"M-Shop"}],"publist_id":"6808","citation":{"short":"L. Vukušić, J. Kukucka, H. Watzinger, G. Katsaros, Nano Letters 17 (2017) 5706–5710.","ama":"Vukušić L, Kukucka J, Watzinger H, Katsaros G. Fast hole tunneling times in germanium hut wires probed by single-shot reflectometry. <i>Nano Letters</i>. 2017;17(9):5706-5710. doi:<a href=\"https://doi.org/10.1021/acs.nanolett.7b02627\">10.1021/acs.nanolett.7b02627</a>","apa":"Vukušić, L., Kukucka, J., Watzinger, H., &#38; Katsaros, G. (2017). Fast hole tunneling times in germanium hut wires probed by single-shot reflectometry. <i>Nano Letters</i>. American Chemical Society. <a href=\"https://doi.org/10.1021/acs.nanolett.7b02627\">https://doi.org/10.1021/acs.nanolett.7b02627</a>","ieee":"L. Vukušić, J. Kukucka, H. Watzinger, and G. Katsaros, “Fast hole tunneling times in germanium hut wires probed by single-shot reflectometry,” <i>Nano Letters</i>, vol. 17, no. 9. American Chemical Society, pp. 5706–5710, 2017.","chicago":"Vukušić, Lada, Josip Kukucka, Hannes Watzinger, and Georgios Katsaros. “Fast Hole Tunneling Times in Germanium Hut Wires Probed by Single-Shot Reflectometry.” <i>Nano Letters</i>. American Chemical Society, 2017. <a href=\"https://doi.org/10.1021/acs.nanolett.7b02627\">https://doi.org/10.1021/acs.nanolett.7b02627</a>.","mla":"Vukušić, Lada, et al. “Fast Hole Tunneling Times in Germanium Hut Wires Probed by Single-Shot Reflectometry.” <i>Nano Letters</i>, vol. 17, no. 9, American Chemical Society, 2017, pp. 5706–10, doi:<a href=\"https://doi.org/10.1021/acs.nanolett.7b02627\">10.1021/acs.nanolett.7b02627</a>.","ista":"Vukušić L, Kukucka J, Watzinger H, Katsaros G. 2017. Fast hole tunneling times in germanium hut wires probed by single-shot reflectometry. Nano Letters. 17(9), 5706–5710."},"language":[{"iso":"eng"}],"oa_version":"Published Version","issue":"9","related_material":{"record":[{"relation":"popular_science","id":"7977"},{"id":"7996","status":"public","relation":"dissertation_contains"},{"id":"69","relation":"dissertation_contains","status":"public"}]},"publisher":"American Chemical Society","date_published":"2017-08-10T00:00:00Z","date_updated":"2026-04-08T14:09:47Z","department":[{"_id":"GeKa"}],"abstract":[{"lang":"eng","text":"Heavy holes confined in quantum dots are predicted to be promising candidates for the realization of spin qubits with long coherence times. Here we focus on such heavy-hole states confined in germanium hut wires. By tuning the growth density of the latter we can realize a T-like structure between two neighboring wires. Such a structure allows the realization of a charge sensor, which is electrostatically and tunnel coupled to a quantum dot, with charge-transfer signals as high as 0.3 e. By integrating the T-like structure into a radiofrequency reflectometry setup, single-shot measurements allowing the extraction of hole tunneling times are performed. The extracted tunneling times of less than 10 μs are attributed to the small effective mass of Ge heavy-hole states and pave the way toward projective spin readout measurements."}],"ddc":["539"],"isi":1,"external_id":{"isi":["000411043500078"]},"publication":"Nano Letters","scopus_import":"1","date_created":"2018-12-11T11:48:47Z","ec_funded":1,"tmp":{"short":"CC BY (4.0)","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)"},"day":"10","pubrep_id":"865","article_processing_charge":"No","month":"08","volume":17,"file":[{"file_name":"IST-2017-865-v1+1_acs.nanolett.7b02627.pdf","file_size":2449546,"content_type":"application/pdf","date_updated":"2020-07-14T12:48:13Z","relation":"main_file","file_id":"4951","creator":"system","date_created":"2018-12-12T10:12:33Z","checksum":"761371a0129b2aa442424b9561450ece","access_level":"open_access"}],"intvolume":"        17","project":[{"_id":"25517E86-B435-11E9-9278-68D0E5697425","grant_number":"335497","name":"Towards Spin qubits and Majorana fermions in Germanium self assembled hut-wires","call_identifier":"FP7"}],"title":"Fast hole tunneling times in germanium hut wires probed by single-shot reflectometry","page":"5706 - 5710","quality_controlled":"1","file_date_updated":"2020-07-14T12:48:13Z","year":"2017","publication_status":"published","status":"public","type":"journal_article","has_accepted_license":"1","oa":1,"_id":"840","publication_identifier":{"issn":["1530-6984"]},"doi":"10.1021/acs.nanolett.7b02627"},{"citation":{"short":"A. Akopyan, V. Vysotsky, The American Mathematical Monthly 124 (2017) 588–596.","ama":"Akopyan A, Vysotsky V. On the lengths of curves passing through boundary points of a planar convex shape. <i>The American Mathematical Monthly</i>. 2017;124(7):588-596. doi:<a href=\"https://doi.org/10.4169/amer.math.monthly.124.7.588\">10.4169/amer.math.monthly.124.7.588</a>","apa":"Akopyan, A., &#38; Vysotsky, V. (2017). On the lengths of curves passing through boundary points of a planar convex shape. <i>The American Mathematical Monthly</i>. Mathematical Association of America. <a href=\"https://doi.org/10.4169/amer.math.monthly.124.7.588\">https://doi.org/10.4169/amer.math.monthly.124.7.588</a>","ieee":"A. Akopyan and V. Vysotsky, “On the lengths of curves passing through boundary points of a planar convex shape,” <i>The American Mathematical Monthly</i>, vol. 124, no. 7. Mathematical Association of America, pp. 588–596, 2017.","chicago":"Akopyan, Arseniy, and Vladislav Vysotsky. “On the Lengths of Curves Passing through Boundary Points of a Planar Convex Shape.” <i>The American Mathematical Monthly</i>. Mathematical Association of America, 2017. <a href=\"https://doi.org/10.4169/amer.math.monthly.124.7.588\">https://doi.org/10.4169/amer.math.monthly.124.7.588</a>.","mla":"Akopyan, Arseniy, and Vladislav Vysotsky. “On the Lengths of Curves Passing through Boundary Points of a Planar Convex Shape.” <i>The American Mathematical Monthly</i>, vol. 124, no. 7, Mathematical Association of America, 2017, pp. 588–96, doi:<a href=\"https://doi.org/10.4169/amer.math.monthly.124.7.588\">10.4169/amer.math.monthly.124.7.588</a>.","ista":"Akopyan A, Vysotsky V. 2017. On the lengths of curves passing through boundary points of a planar convex shape. The American Mathematical Monthly. 124(7), 588–596."},"publist_id":"6534","language":[{"iso":"eng"}],"oa_version":"Submitted Version","author":[{"last_name":"Akopyan","first_name":"Arseniy","id":"430D2C90-F248-11E8-B48F-1D18A9856A87","full_name":"Akopyan, Arseniy","orcid":"0000-0002-2548-617X"},{"full_name":"Vysotsky, Vladislav","last_name":"Vysotsky","first_name":"Vladislav"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We study the lengths of curves passing through a fixed number of points on the boundary of a convex shape in the plane. We show that, for any convex shape K, there exist four points on the boundary of K such that the length of any curve passing through these points is at least half of the perimeter of K. It is also shown that the same statement does not remain valid with the additional constraint that the points are extreme points of K. Moreover, the factor &amp;#xbd; cannot be achieved with any fixed number of extreme points. We conclude the paper with a few other inequalities related to the perimeter of a convex shape."}],"date_updated":"2025-07-10T12:01:35Z","department":[{"_id":"HeEd"}],"isi":1,"external_id":{"isi":["000413947300002"],"arxiv":["1605.07997"]},"publisher":"Mathematical Association of America","issue":"7","arxiv":1,"date_published":"2017-01-01T00:00:00Z","volume":124,"month":"01","article_processing_charge":"No","title":"On the lengths of curves passing through boundary points of a planar convex shape","page":"588 - 596","intvolume":"       124","project":[{"call_identifier":"FP7","grant_number":"291734","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"publication":"The American Mathematical Monthly","day":"01","scopus_import":"1","ec_funded":1,"date_created":"2018-12-11T11:49:09Z","article_type":"original","oa":1,"_id":"909","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1605.07997"}],"publication_identifier":{"issn":["0002-9890"]},"doi":"10.4169/amer.math.monthly.124.7.588","year":"2017","publication_status":"published","type":"journal_article","status":"public","quality_controlled":"1"},{"author":[{"id":"461468AE-F248-11E8-B48F-1D18A9856A87","first_name":"Sebastian","last_name":"Novak","orcid":"0000-0002-2519-824X","full_name":"Novak, Sebastian"},{"first_name":"Nicholas H","last_name":"Barton","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","corr_author":"1","citation":{"apa":"Novak, S., &#38; Barton, N. H. (2017). When does frequency-independent selection maintain genetic variation? <i>Genetics</i>. Genetics Society of America. <a href=\"https://doi.org/10.1534/genetics.117.300129\">https://doi.org/10.1534/genetics.117.300129</a>","ama":"Novak S, Barton NH. When does frequency-independent selection maintain genetic variation? <i>Genetics</i>. 2017;207(2):653-668. doi:<a href=\"https://doi.org/10.1534/genetics.117.300129\">10.1534/genetics.117.300129</a>","short":"S. Novak, N.H. Barton, Genetics 207 (2017) 653–668.","ista":"Novak S, Barton NH. 2017. When does frequency-independent selection maintain genetic variation? Genetics. 207(2), 653–668.","mla":"Novak, Sebastian, and Nicholas H. Barton. “When Does Frequency-Independent Selection Maintain Genetic Variation?” <i>Genetics</i>, vol. 207, no. 2, Genetics Society of America, 2017, pp. 653–68, doi:<a href=\"https://doi.org/10.1534/genetics.117.300129\">10.1534/genetics.117.300129</a>.","chicago":"Novak, Sebastian, and Nicholas H Barton. “When Does Frequency-Independent Selection Maintain Genetic Variation?” <i>Genetics</i>. Genetics Society of America, 2017. <a href=\"https://doi.org/10.1534/genetics.117.300129\">https://doi.org/10.1534/genetics.117.300129</a>.","ieee":"S. Novak and N. H. Barton, “When does frequency-independent selection maintain genetic variation?,” <i>Genetics</i>, vol. 207, no. 2. Genetics Society of America, pp. 653–668, 2017."},"publist_id":"6533","language":[{"iso":"eng"}],"oa_version":"Submitted Version","publisher":"Genetics Society of America","issue":"2","date_published":"2017-10-01T00:00:00Z","abstract":[{"lang":"eng","text":"Frequency-independent selection is generally considered as a force that acts to reduce the genetic variation in evolving populations, yet rigorous arguments for this idea are scarce. When selection fluctuates in time, it is unclear whether frequency-independent selection may maintain genetic polymorphism without invoking additional mechanisms. We show that constant frequency-independent selection with arbitrary epistasis on a well-mixed haploid population eliminates genetic variation if we assume linkage equilibrium between alleles. To this end, we introduce the notion of frequency-independent selection at the level of alleles, which is sufficient to prove our claim and contains the notion of frequency-independent selection on haploids. When selection and recombination are weak but of the same order, there may be strong linkage disequilibrium; numerical calculations show that stable equilibria are highly unlikely. Using the example of a diallelic two-locus model, we then demonstrate that frequency-independent selection that fluctuates in time can maintain stable polymorphism if linkage disequilibrium changes its sign periodically. We put our findings in the context of results from the existing literature and point out those scenarios in which the possible role of frequency-independent selection in maintaining genetic variation remains unclear.\r\n"}],"date_updated":"2025-04-15T08:22:21Z","department":[{"_id":"NiBa"}],"ddc":["576"],"external_id":{"isi":["000412232600019"]},"isi":1,"publication":"Genetics","day":"01","pubrep_id":"974","scopus_import":"1","ec_funded":1,"date_created":"2018-12-11T11:49:09Z","volume":207,"file":[{"access_level":"open_access","relation":"main_file","creator":"system","file_id":"5264","date_created":"2018-12-12T10:17:12Z","checksum":"f7c32dabf52e6d9e709d9203761e39fd","file_size":494268,"content_type":"application/pdf","date_updated":"2020-07-14T12:48:15Z","file_name":"IST-2018-974-v1+1_manuscript.pdf"}],"article_processing_charge":"No","month":"10","page":"653 - 668","title":"When does frequency-independent selection maintain genetic variation?","intvolume":"       207","project":[{"_id":"25B1EC9E-B435-11E9-9278-68D0E5697425","name":"Speed of Adaptation in Population Genetics and Evolutionary Computation","grant_number":"618091","call_identifier":"FP7"}],"publication_status":"published","file_date_updated":"2020-07-14T12:48:15Z","year":"2017","status":"public","type":"journal_article","quality_controlled":"1","oa":1,"has_accepted_license":"1","_id":"910","doi":"10.1534/genetics.117.300129"},{"quality_controlled":"1","publication_status":"published","year":"2017","file_date_updated":"2020-08-10T07:14:33Z","status":"public","type":"conference","has_accepted_license":"1","oa":1,"_id":"911","doi":"10.5244/c.31.85","publication_identifier":{"eisbn":["190172560X"]},"scopus_import":"1","date_created":"2018-12-11T11:49:09Z","ec_funded":1,"day":"01","month":"09","article_processing_charge":"No","file":[{"date_created":"2020-08-10T07:14:33Z","creator":"dernst","file_id":"8224","relation":"main_file","success":1,"access_level":"open_access","file_name":"2017_BMVC_Royer.pdf","content_type":"application/pdf","date_updated":"2020-08-10T07:14:33Z","file_size":1625363}],"project":[{"_id":"2532554C-B435-11E9-9278-68D0E5697425","name":"Lifelong Learning of Visual Scene Understanding","grant_number":"308036","call_identifier":"FP7"}],"page":"85.1-85.12","title":"Probabilistic image colorization","conference":{"name":"BMVC: British Machine Vision Conference","end_date":"2017-09-07","location":"London, United Kingdom","start_date":"2017-09-04"},"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"8390"}]},"publisher":"BMVA Press","date_published":"2017-09-01T00:00:00Z","arxiv":1,"date_updated":"2026-04-08T07:26:44Z","department":[{"_id":"ChLa"}],"abstract":[{"lang":"eng","text":"We develop a probabilistic technique for colorizing grayscale natural images. In light of the intrinsic uncertainty of this task, the proposed probabilistic framework has numerous desirable properties. In particular, our model is able to produce multiple plausible and vivid colorizations for a given grayscale image and is one of the first colorization models to provide a proper stochastic sampling scheme. Moreover, our training procedure is supported by a rigorous theoretical framework that does not require any ad hoc heuristics and allows for efficient modeling and learning of the joint pixel color distribution.We demonstrate strong quantitative and qualitative experimental results on the CIFAR-10 dataset and the challenging ILSVRC 2012 dataset."}],"ddc":["000"],"external_id":{"arxiv":["1705.04258"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Amélie","last_name":"Royer","id":"3811D890-F248-11E8-B48F-1D18A9856A87","full_name":"Royer, Amélie","orcid":"0000-0002-8407-0705"},{"full_name":"Kolesnikov, Alexander","id":"2D157DB6-F248-11E8-B48F-1D18A9856A87","last_name":"Kolesnikov","first_name":"Alexander"},{"orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph","last_name":"Lampert","first_name":"Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87"}],"corr_author":"1","publist_id":"6532","citation":{"apa":"Royer, A., Kolesnikov, A., &#38; Lampert, C. (2017). Probabilistic image colorization (p. 85.1-85.12). Presented at the BMVC: British Machine Vision Conference, London, United Kingdom: BMVA Press. <a href=\"https://doi.org/10.5244/c.31.85\">https://doi.org/10.5244/c.31.85</a>","ama":"Royer A, Kolesnikov A, Lampert C. Probabilistic image colorization. In: BMVA Press; 2017:85.1-85.12. doi:<a href=\"https://doi.org/10.5244/c.31.85\">10.5244/c.31.85</a>","short":"A. Royer, A. Kolesnikov, C. Lampert, in:, BMVA Press, 2017, p. 85.1-85.12.","chicago":"Royer, Amélie, Alexander Kolesnikov, and Christoph Lampert. “Probabilistic Image Colorization,” 85.1-85.12. BMVA Press, 2017. <a href=\"https://doi.org/10.5244/c.31.85\">https://doi.org/10.5244/c.31.85</a>.","ieee":"A. Royer, A. Kolesnikov, and C. Lampert, “Probabilistic image colorization,” presented at the BMVC: British Machine Vision Conference, London, United Kingdom, 2017, p. 85.1-85.12.","ista":"Royer A, Kolesnikov A, Lampert C. 2017. Probabilistic image colorization. BMVC: British Machine Vision Conference, 85.1-85.12.","mla":"Royer, Amélie, et al. <i>Probabilistic Image Colorization</i>. BMVA Press, 2017, p. 85.1-85.12, doi:<a href=\"https://doi.org/10.5244/c.31.85\">10.5244/c.31.85</a>."},"language":[{"iso":"eng"}],"oa_version":"Published Version"},{"publication_identifier":{"isbn":["978-153860457-1"]},"doi":"10.1109/CVPR.2017.530","_id":"915","has_accepted_license":"1","oa":1,"quality_controlled":"1","status":"public","type":"conference","publication_status":"published","year":"2017","file_date_updated":"2020-07-14T12:48:15Z","project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"intvolume":"      2017","page":"4990-4999","title":"A message passing algorithm for the minimum cost multicut problem","article_processing_charge":"No","month":"07","file":[{"file_size":883264,"date_updated":"2020-07-14T12:48:15Z","content_type":"application/pdf","file_name":"Swoboda_A_Message_Passing_CVPR_2017_paper.pdf","access_level":"open_access","creator":"dernst","file_id":"5849","relation":"main_file","checksum":"7e51dacefa693574581a32da3eff63dc","date_created":"2019-01-18T12:52:46Z"}],"volume":2017,"date_created":"2018-12-11T11:49:11Z","ec_funded":1,"scopus_import":"1","day":"01","external_id":{"isi":["000418371405009"]},"isi":1,"ddc":["000"],"department":[{"_id":"VlKo"}],"date_updated":"2024-11-04T13:52:34Z","abstract":[{"text":"We propose a dual decomposition and linear program relaxation of the NP-hard minimum cost multicut problem. Unlike other polyhedral relaxations of the multicut polytope, it is amenable to efficient optimization by message passing. Like other polyhedral relaxations, it can be tightened efficiently by cutting planes.  We define an algorithm that alternates between message passing and efficient separation of cycle- and odd-wheel inequalities. This algorithm is more efficient than state-of-the-art algorithms based on linear programming, including algorithms written in the framework of leading commercial software, as we show in experiments with large instances of the problem from applications in computer vision, biomedical image analysis and data mining.","lang":"eng"}],"date_published":"2017-07-01T00:00:00Z","conference":{"location":"Honolulu, HA, United States","start_date":"2017-07-21","end_date":"2017-07-26","name":"CVPR: Computer Vision and Pattern Recognition"},"publisher":"IEEE","oa_version":"Submitted Version","language":[{"iso":"eng"}],"publist_id":"6526","citation":{"apa":"Swoboda, P., &#38; Andres, B. (2017). A message passing algorithm for the minimum cost multicut problem (Vol. 2017, pp. 4990–4999). Presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States: IEEE. <a href=\"https://doi.org/10.1109/CVPR.2017.530\">https://doi.org/10.1109/CVPR.2017.530</a>","ama":"Swoboda P, Andres B. A message passing algorithm for the minimum cost multicut problem. In: Vol 2017. IEEE; 2017:4990-4999. doi:<a href=\"https://doi.org/10.1109/CVPR.2017.530\">10.1109/CVPR.2017.530</a>","short":"P. Swoboda, B. Andres, in:, IEEE, 2017, pp. 4990–4999.","mla":"Swoboda, Paul, and Bjoern Andres. <i>A Message Passing Algorithm for the Minimum Cost Multicut Problem</i>. Vol. 2017, IEEE, 2017, pp. 4990–99, doi:<a href=\"https://doi.org/10.1109/CVPR.2017.530\">10.1109/CVPR.2017.530</a>.","ista":"Swoboda P, Andres B. 2017. A message passing algorithm for the minimum cost multicut problem. CVPR: Computer Vision and Pattern Recognition vol. 2017, 4990–4999.","chicago":"Swoboda, Paul, and Bjoern Andres. “A Message Passing Algorithm for the Minimum Cost Multicut Problem,” 2017:4990–99. IEEE, 2017. <a href=\"https://doi.org/10.1109/CVPR.2017.530\">https://doi.org/10.1109/CVPR.2017.530</a>.","ieee":"P. Swoboda and B. Andres, “A message passing algorithm for the minimum cost multicut problem,” presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States, 2017, vol. 2017, pp. 4990–4999."},"corr_author":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"id":"446560C6-F248-11E8-B48F-1D18A9856A87","first_name":"Paul","last_name":"Swoboda","full_name":"Swoboda, Paul"},{"full_name":"Andres, Bjoern","first_name":"Bjoern","last_name":"Andres"}]},{"scopus_import":"1","ec_funded":1,"date_created":"2018-12-11T11:49:11Z","day":"01","intvolume":"      2017","project":[{"call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"page":"7062-7071","title":"A study of lagrangean decompositions and dual ascent solvers for graph matching","article_processing_charge":"No","month":"01","volume":2017,"file":[{"file_name":"2017_CVPR_Swoboda2.pdf","file_size":944332,"content_type":"application/pdf","date_updated":"2020-07-14T12:48:15Z","creator":"dernst","file_id":"5848","relation":"main_file","checksum":"e38a2740daad1ea178465843b5072906","date_created":"2019-01-18T12:49:38Z","access_level":"open_access"}],"quality_controlled":"1","publication_status":"published","file_date_updated":"2020-07-14T12:48:15Z","year":"2017","status":"public","type":"conference","_id":"916","publication_identifier":{"isbn":["978-153860457-1"]},"doi":"10.1109/CVPR.2017.747","has_accepted_license":"1","oa":1,"corr_author":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"first_name":"Paul","last_name":"Swoboda","id":"446560C6-F248-11E8-B48F-1D18A9856A87","full_name":"Swoboda, Paul"},{"full_name":"Rother, Carsten","last_name":"Rother","first_name":"Carsten"},{"first_name":"Carsten","last_name":"Abu Alhaija","full_name":"Abu Alhaija, Carsten"},{"last_name":"Kainmueller","first_name":"Dagmar","full_name":"Kainmueller, Dagmar"},{"full_name":"Savchynskyy, Bogdan","last_name":"Savchynskyy","first_name":"Bogdan"}],"language":[{"iso":"eng"}],"oa_version":"Submitted Version","publist_id":"6525","citation":{"ieee":"P. Swoboda, C. Rother, C. Abu Alhaija, D. Kainmueller, and B. Savchynskyy, “A study of lagrangean decompositions and dual ascent solvers for graph matching,” presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States, 2017, vol. 2017, pp. 7062–7071.","chicago":"Swoboda, Paul, Carsten Rother, Carsten Abu Alhaija, Dagmar Kainmueller, and Bogdan Savchynskyy. “A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching,” 2017:7062–71. IEEE, 2017. <a href=\"https://doi.org/10.1109/CVPR.2017.747\">https://doi.org/10.1109/CVPR.2017.747</a>.","mla":"Swoboda, Paul, et al. <i>A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching</i>. Vol. 2017, IEEE, 2017, pp. 7062–71, doi:<a href=\"https://doi.org/10.1109/CVPR.2017.747\">10.1109/CVPR.2017.747</a>.","ista":"Swoboda P, Rother C, Abu Alhaija C, Kainmueller D, Savchynskyy B. 2017. A study of lagrangean decompositions and dual ascent solvers for graph matching. CVPR: Computer Vision and Pattern Recognition vol. 2017, 7062–7071.","ama":"Swoboda P, Rother C, Abu Alhaija C, Kainmueller D, Savchynskyy B. A study of lagrangean decompositions and dual ascent solvers for graph matching. In: Vol 2017. IEEE; 2017:7062-7071. doi:<a href=\"https://doi.org/10.1109/CVPR.2017.747\">10.1109/CVPR.2017.747</a>","short":"P. Swoboda, C. Rother, C. Abu Alhaija, D. Kainmueller, B. Savchynskyy, in:, IEEE, 2017, pp. 7062–7071.","apa":"Swoboda, P., Rother, C., Abu Alhaija, C., Kainmueller, D., &#38; Savchynskyy, B. (2017). A study of lagrangean decompositions and dual ascent solvers for graph matching (Vol. 2017, pp. 7062–7071). Presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States: IEEE. <a href=\"https://doi.org/10.1109/CVPR.2017.747\">https://doi.org/10.1109/CVPR.2017.747</a>"},"date_published":"2017-01-01T00:00:00Z","conference":{"start_date":"2017-07-21","location":"Honolulu, HA, United States","name":"CVPR: Computer Vision and Pattern Recognition","end_date":"2017-07-26"},"publisher":"IEEE","ddc":["000"],"external_id":{"isi":["000418371407018"]},"isi":1,"date_updated":"2024-11-04T13:52:34Z","department":[{"_id":"VlKo"}],"abstract":[{"lang":"eng","text":"We study the quadratic assignment problem, in computer vision also known as graph matching. Two leading solvers for this problem optimize the Lagrange decomposition duals with sub-gradient and dual ascent (also known as message passing) updates. We explore this direction further and propose several additional Lagrangean relaxations of the graph matching problem along with corresponding algorithms, which are all based on a common dual ascent framework. Our extensive empirical evaluation gives several theoretical insights and suggests a new state-of-the-art anytime solver for the considered problem. Our improvement over state-of-the-art is particularly visible on a new dataset with large-scale sparse problem instances containing more than 500 graph nodes each."}]}]