[{"date_published":"2017-09-27T00:00:00Z","page":"113","citation":{"apa":"Mitosch, K. (2017). Timing, variability and cross-protection in bacteria – insights from dynamic gene expression responses to antibiotics. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_862","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.","ama":"Mitosch K. Timing, variability and cross-protection in bacteria – insights from dynamic gene expression responses to antibiotics. 2017. doi:10.15479/AT:ISTA:th_862","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. https://doi.org/10.15479/AT:ISTA:th_862.","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.","mla":"Mitosch, Karin. Timing, Variability and Cross-Protection in Bacteria – Insights from Dynamic Gene Expression Responses to Antibiotics. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_862."},"day":"27","article_processing_charge":"No","has_accepted_license":"1","oa_version":"Published Version","file":[{"creator":"dernst","content_type":"application/vnd.openxmlformats-officedocument.wordprocessingml.document","file_size":6331071,"access_level":"closed","file_name":"Thesis_KarinMitosch.docx","checksum":"da3993c5f90f59a8e8623cc31ad501dd","date_created":"2019-04-05T08:48:51Z","date_updated":"2020-07-14T12:48:09Z","file_id":"6210","relation":"source_file"},{"file_id":"6211","relation":"main_file","date_updated":"2020-07-14T12:48:09Z","date_created":"2019-04-05T08:48:51Z","checksum":"24c3d9e51992f1b721f3df55aa13fcb8","file_name":"Thesis_KarinMitosch.pdf","access_level":"open_access","creator":"dernst","content_type":"application/pdf","file_size":9289852}],"pubrep_id":"862","title":"Timing, variability and cross-protection in bacteria – insights from dynamic gene expression responses to antibiotics","status":"public","ddc":["571","579"],"_id":"818","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","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"}],"alternative_title":["ISTA Thesis"],"type":"dissertation","supervisor":[{"full_name":"Bollenbach, Mark Tobias","id":"3E6DB97A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4398-476X","first_name":"Mark Tobias","last_name":"Bollenbach"}],"degree_awarded":"PhD","language":[{"iso":"eng"}],"doi":"10.15479/AT:ISTA:th_862","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"month":"09","publication_identifier":{"issn":["2663-337X"]},"date_created":"2018-12-11T11:48:40Z","date_updated":"2023-09-07T12:00:26Z","author":[{"last_name":"Mitosch","first_name":"Karin","id":"39B66846-F248-11E8-B48F-1D18A9856A87","full_name":"Mitosch, Karin"}],"related_material":{"record":[{"id":"2001","relation":"part_of_dissertation","status":"public"},{"id":"666","relation":"part_of_dissertation","status":"public"}]},"publication_status":"published","publisher":"Institute of Science and Technology Austria","department":[{"_id":"ToBo"}],"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. ","year":"2017","license":"https://creativecommons.org/licenses/by/4.0/","file_date_updated":"2020-07-14T12:48:09Z","publist_id":"6831"},{"date_published":"2017-04-26T00:00:00Z","publication":"Cell Systems","citation":{"ieee":"K. Mitosch, G. Rieckh, and M. T. Bollenbach, “Noisy response to antibiotic stress predicts subsequent single cell survival in an acidic environment,” Cell Systems, vol. 4, no. 4. Cell Press, pp. 393–403, 2017.","apa":"Mitosch, K., Rieckh, G., & Bollenbach, M. T. (2017). Noisy response to antibiotic stress predicts subsequent single cell survival in an acidic environment. Cell Systems. Cell Press. https://doi.org/10.1016/j.cels.2017.03.001","ista":"Mitosch K, Rieckh G, Bollenbach MT. 2017. Noisy response to antibiotic stress predicts subsequent single cell survival in an acidic environment. Cell Systems. 4(4), 393–403.","ama":"Mitosch K, Rieckh G, Bollenbach MT. Noisy response to antibiotic stress predicts subsequent single cell survival in an acidic environment. Cell Systems. 2017;4(4):393-403. doi:10.1016/j.cels.2017.03.001","chicago":"Mitosch, Karin, Georg Rieckh, and Mark Tobias Bollenbach. “Noisy Response to Antibiotic Stress Predicts Subsequent Single Cell Survival in an Acidic Environment.” Cell Systems. Cell Press, 2017. https://doi.org/10.1016/j.cels.2017.03.001.","short":"K. Mitosch, G. Rieckh, M.T. Bollenbach, Cell Systems 4 (2017) 393–403.","mla":"Mitosch, Karin, et al. “Noisy Response to Antibiotic Stress Predicts Subsequent Single Cell Survival in an Acidic Environment.” Cell Systems, vol. 4, no. 4, Cell Press, 2017, pp. 393–403, doi:10.1016/j.cels.2017.03.001."},"page":"393 - 403","day":"26","has_accepted_license":"1","article_processing_charge":"Yes (in subscription journal)","scopus_import":1,"pubrep_id":"901","oa_version":"Published Version","file":[{"access_level":"open_access","file_name":"IST-2017-901-v1+1_1-s2.0-S2405471217300868-main.pdf","creator":"system","content_type":"application/pdf","file_size":2438660,"file_id":"5041","relation":"main_file","checksum":"04ff20011c3d9a601c514aa999a5fe1a","date_updated":"2020-07-14T12:47:35Z","date_created":"2018-12-12T10:13:54Z"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"666","ddc":["576","610"],"title":"Noisy response to antibiotic stress predicts subsequent single cell survival in an acidic environment","status":"public","intvolume":" 4","abstract":[{"text":"Antibiotics elicit drastic changes in microbial gene expression, including the induction of stress response genes. While certain stress responses are known to “cross-protect” bacteria from other stressors, it is unclear whether cellular responses to antibiotics have a similar protective role. By measuring the genome-wide transcriptional response dynamics of Escherichia coli to four antibiotics, we found that trimethoprim induces a rapid acid stress response that protects bacteria from subsequent exposure to acid. Combining microfluidics with time-lapse imaging to monitor survival and acid stress response in single cells revealed that the noisy expression of the acid resistance operon gadBC correlates with single-cell survival. Cells with higher gadBC expression following trimethoprim maintain higher intracellular pH and survive the acid stress longer. The seemingly random single-cell survival under acid stress can therefore be predicted from gadBC expression and rationalized in terms of GadB/C molecular function. Overall, we provide a roadmap for identifying the molecular mechanisms of single-cell cross-protection between antibiotics and other stressors.","lang":"eng"}],"issue":"4","type":"journal_article","doi":"10.1016/j.cels.2017.03.001","language":[{"iso":"eng"}],"oa":1,"tmp":{"name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png"},"quality_controlled":"1","project":[{"_id":"25E83C2C-B435-11E9-9278-68D0E5697425","grant_number":"303507","name":"Optimality principles in responses to antibiotics","call_identifier":"FP7"},{"_id":"25E9AF9E-B435-11E9-9278-68D0E5697425","grant_number":"P27201-B22","call_identifier":"FWF","name":"Revealing the mechanisms underlying drug interactions"},{"name":"Revealing the fundamental limits of cell growth","grant_number":"RGP0042/2013","_id":"25EB3A80-B435-11E9-9278-68D0E5697425"}],"month":"04","publication_identifier":{"issn":["24054712"]},"author":[{"full_name":"Mitosch, Karin","first_name":"Karin","last_name":"Mitosch","id":"39B66846-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Rieckh, Georg","id":"34DA8BD6-F248-11E8-B48F-1D18A9856A87","last_name":"Rieckh","first_name":"Georg"},{"orcid":"0000-0003-4398-476X","id":"3E6DB97A-F248-11E8-B48F-1D18A9856A87","last_name":"Bollenbach","first_name":"Tobias","full_name":"Bollenbach, Tobias"}],"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"818"}]},"date_updated":"2023-09-07T12:00:25Z","date_created":"2018-12-11T11:47:48Z","volume":4,"year":"2017","publication_status":"published","department":[{"_id":"ToBo"},{"_id":"GaTk"}],"publisher":"Cell Press","file_date_updated":"2020-07-14T12:47:35Z","ec_funded":1,"publist_id":"7061","license":"https://creativecommons.org/licenses/by-nc-nd/4.0/"},{"ec_funded":1,"publist_id":"6828","file_date_updated":"2020-07-14T12:48:10Z","license":"https://creativecommons.org/licenses/by-nd/4.0/","year":"2017","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.","publisher":"Institute of Science and Technology Austria","department":[{"_id":"KrCh"}],"publication_status":"published","related_material":{"record":[{"id":"1071","relation":"part_of_dissertation","status":"public"},{"status":"public","relation":"part_of_dissertation","id":"1437"},{"status":"public","relation":"part_of_dissertation","id":"1602"},{"id":"1604","status":"public","relation":"part_of_dissertation"},{"id":"1607","relation":"part_of_dissertation","status":"public"},{"id":"1714","status":"public","relation":"part_of_dissertation"}]},"author":[{"full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","first_name":"Andreas"}],"date_updated":"2023-09-07T12:01:59Z","date_created":"2018-12-11T11:48:41Z","publication_identifier":{"issn":["2663-337X"]},"month":"08","tmp":{"short":"CC BY-ND (4.0)","image":"/image/cc_by_nd.png","name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode"},"oa":1,"project":[{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"doi":"10.15479/AT:ISTA:th_854","language":[{"iso":"eng"}],"supervisor":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"}],"degree_awarded":"PhD","type":"dissertation","alternative_title":["ISTA Thesis"],"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."}],"_id":"821","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","title":"Algorithmic advances in program analysis and their applications","status":"public","ddc":["000"],"pubrep_id":"854","oa_version":"Published Version","file":[{"file_size":4103115,"content_type":"application/pdf","creator":"system","file_name":"IST-2017-854-v1+1_Pavlogiannis_Thesis_PubRep.pdf","access_level":"open_access","date_updated":"2020-07-14T12:48:10Z","date_created":"2018-12-12T10:11:44Z","checksum":"3a3ec003f6ee73f41f82a544d63dfc77","relation":"main_file","file_id":"4900"},{"file_id":"6201","relation":"source_file","checksum":"bd2facc45ff8a2e20c5ed313c2ccaa83","date_created":"2019-04-05T07:59:31Z","date_updated":"2020-07-14T12:48:10Z","access_level":"closed","file_name":"2017_thesis_Pavlogiannis.zip","creator":"dernst","content_type":"application/zip","file_size":14744374}],"article_processing_charge":"No","has_accepted_license":"1","day":"09","citation":{"mla":"Pavlogiannis, Andreas. Algorithmic Advances in Program Analysis and Their Applications. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_854.","short":"A. Pavlogiannis, Algorithmic Advances in Program Analysis and Their Applications, Institute of Science and Technology Austria, 2017.","chicago":"Pavlogiannis, Andreas. “Algorithmic Advances in Program Analysis and Their Applications.” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_854.","ama":"Pavlogiannis A. Algorithmic advances in program analysis and their applications. 2017. doi:10.15479/AT:ISTA:th_854","ista":"Pavlogiannis A. 2017. Algorithmic advances in program analysis and their applications. Institute of Science and Technology Austria.","ieee":"A. Pavlogiannis, “Algorithmic advances in program analysis and their applications,” Institute of Science and Technology Austria, 2017.","apa":"Pavlogiannis, A. (2017). Algorithmic advances in program analysis and their applications. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_854"},"page":"418","date_published":"2017-08-09T00:00:00Z"},{"type":"dissertation","alternative_title":["ISTA Thesis"],"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."}],"_id":"820","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","ddc":["576","577","579"],"title":"The lac operon in the wild","status":"public","pubrep_id":"857","oa_version":"Published Version","file":[{"file_size":3417773,"content_type":"application/pdf","creator":"system","file_name":"IST-2017-857-v1+1_thesis_fabienne.pdf","access_level":"open_access","date_created":"2018-12-12T10:17:00Z","date_updated":"2020-07-14T12:48:10Z","checksum":"c62257a7bff0c5f39e1abffc6bfcca5c","relation":"main_file","file_id":"5252"},{"creator":"dernst","file_size":215899,"content_type":"application/x-tex","access_level":"closed","file_name":"2017_thesis_Jesse_source.tex","checksum":"fc87d7d72fce52824a3ae7dcad0413a8","date_created":"2019-04-05T08:51:59Z","date_updated":"2020-07-14T12:48:10Z","file_id":"6212","relation":"source_file"}],"article_processing_charge":"No","has_accepted_license":"1","day":"25","citation":{"ama":"Jesse F. The lac operon in the wild. 2017. doi:10.15479/AT:ISTA:th_857","ista":"Jesse F. 2017. The lac operon in the wild. Institute of Science and Technology Austria.","ieee":"F. Jesse, “The lac operon in the wild,” Institute of Science and Technology Austria, 2017.","apa":"Jesse, F. (2017). The lac operon in the wild. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_857","mla":"Jesse, Fabienne. The Lac Operon in the Wild. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_857.","short":"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. https://doi.org/10.15479/AT:ISTA:th_857."},"page":"87","date_published":"2017-08-25T00:00:00Z","publist_id":"6829","ec_funded":1,"file_date_updated":"2020-07-14T12:48:10Z","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. ","year":"2017","department":[{"_id":"JoBo"}],"publisher":"Institute of Science and Technology Austria","publication_status":"published","author":[{"full_name":"Jesse, Fabienne","id":"4C8C26A4-F248-11E8-B48F-1D18A9856A87","last_name":"Jesse","first_name":"Fabienne"}],"date_updated":"2023-09-07T12:01:21Z","date_created":"2018-12-11T11:48:41Z","publication_identifier":{"issn":["2663-337X"]},"month":"08","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"project":[{"_id":"2578D616-B435-11E9-9278-68D0E5697425","grant_number":"648440","name":"Selective Barriers to Horizontal Gene Transfer","call_identifier":"H2020"}],"doi":"10.15479/AT:ISTA:th_857","language":[{"iso":"eng"}],"degree_awarded":"PhD","supervisor":[{"id":"2C6FA9CC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4624-4612","first_name":"Jonathan P","last_name":"Bollback","full_name":"Bollback, Jonathan P"}]},{"file":[{"creator":"system","content_type":"application/pdf","file_size":847400,"access_level":"open_access","file_name":"IST-2017-828-v1+3_2017_Rybar_thesis.pdf","checksum":"ff8639ec4bded6186f44c7bd3ee26804","date_updated":"2020-07-14T12:48:12Z","date_created":"2018-12-12T10:10:13Z","file_id":"4799","relation":"main_file"},{"content_type":"application/zip","file_size":26054879,"creator":"dernst","file_name":"2017_Thesis_Rybar_source.zip","access_level":"closed","date_updated":"2020-07-14T12:48:12Z","date_created":"2019-04-05T08:24:11Z","checksum":"3462101745ce8ad199c2d0f75dae4a7e","relation":"source_file","file_id":"6202"}],"oa_version":"Published Version","pubrep_id":"828","status":"public","title":"(The exact security of) Message authentication codes","ddc":["000"],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"838","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 > 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"}],"alternative_title":["ISTA Thesis"],"type":"dissertation","date_published":"2017-06-26T00:00:00Z","page":"86","citation":{"chicago":"Rybar, Michal. “(The Exact Security of) Message Authentication Codes.” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_828.","short":"M. Rybar, (The Exact Security of) Message Authentication Codes, Institute of Science and Technology Austria, 2017.","mla":"Rybar, Michal. (The Exact Security of) Message Authentication Codes. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_828.","ieee":"M. Rybar, “(The exact security of) Message authentication codes,” Institute of Science and Technology Austria, 2017.","apa":"Rybar, M. (2017). (The exact security of) Message authentication codes. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_828","ista":"Rybar M. 2017. (The exact security of) Message authentication codes. Institute of Science and Technology Austria.","ama":"Rybar M. (The exact security of) Message authentication codes. 2017. doi:10.15479/AT:ISTA:th_828"},"day":"26","article_processing_charge":"No","has_accepted_license":"1","date_updated":"2023-09-07T12:02:28Z","date_created":"2018-12-11T11:48:46Z","author":[{"full_name":"Rybar, Michal","last_name":"Rybar","first_name":"Michal","id":"2B3E3DE8-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"id":"2082","status":"public","relation":"part_of_dissertation"},{"status":"public","relation":"part_of_dissertation","id":"6196"}]},"publication_status":"published","department":[{"_id":"KrPi"}],"publisher":"Institute of Science and Technology Austria","year":"2017","file_date_updated":"2020-07-14T12:48:12Z","publist_id":"6810","degree_awarded":"PhD","language":[{"iso":"eng"}],"doi":"10.15479/AT:ISTA:th_828","oa":1,"month":"06","publication_identifier":{"issn":["2663-337X"]}},{"day":"03","has_accepted_license":"1","publication":"IACR Transactions on Symmetric Cryptology","citation":{"chicago":"Gazi, Peter, Krzysztof Z Pietrzak, and Michal Rybar. “The Exact Security of PMAC.” IACR Transactions on Symmetric Cryptology. Ruhr University Bochum, 2017. https://doi.org/10.13154/TOSC.V2016.I2.145-161.","short":"P. Gazi, K.Z. Pietrzak, M. Rybar, IACR Transactions on Symmetric Cryptology 2016 (2017) 145–161.","mla":"Gazi, Peter, et al. “The Exact Security of PMAC.” IACR Transactions on Symmetric Cryptology, vol. 2016, no. 2, Ruhr University Bochum, 2017, pp. 145–61, doi:10.13154/TOSC.V2016.I2.145-161.","ieee":"P. Gazi, K. Z. Pietrzak, and M. Rybar, “The exact security of PMAC,” IACR Transactions on Symmetric Cryptology, vol. 2016, no. 2. Ruhr University Bochum, pp. 145–161, 2017.","apa":"Gazi, P., Pietrzak, K. Z., & Rybar, M. (2017). The exact security of PMAC. IACR Transactions on Symmetric Cryptology. Ruhr University Bochum. https://doi.org/10.13154/TOSC.V2016.I2.145-161","ista":"Gazi P, Pietrzak KZ, Rybar M. 2017. The exact security of PMAC. IACR Transactions on Symmetric Cryptology. 2016(2), 145–161.","ama":"Gazi P, Pietrzak KZ, Rybar M. The exact security of PMAC. IACR Transactions on Symmetric Cryptology. 2017;2016(2):145-161. doi:10.13154/TOSC.V2016.I2.145-161"},"page":"145-161","date_published":"2017-02-03T00:00:00Z","type":"journal_article","abstract":[{"text":"PMAC is a simple and parallel block-cipher mode of operation, which was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a (pseudo)random permutation over n-bit strings, PMAC constitutes a provably secure variable input-length (pseudo)random function. For adversaries making q queries, each of length at most l (in n-bit blocks), and of total length σ ≤ ql, the original paper proves an upper bound on the distinguishing advantage of Ο(σ2/2n), while the currently best bound is Ο (qσ/2n).In this work we show that this bound is tight by giving an attack with advantage Ω (q2l/2n). In the PMAC construction one initially XORs a mask to every message block, where the mask for the ith 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(2n). We then investigate if the security of PMAC can be further improved by using τi’s that are k-wise independent, for k > 1 (the original distribution is only 1-wise independent). We observe that the security of PMAC will not increase in general, even if the masks are chosen from a 2-wise independent distribution, and then prove that the security increases to O(q<2/2n), if the τi are 4-wise independent. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether 3-wise independence is already sufficient to get this level of security is left as an open problem.","lang":"eng"}],"issue":"2","_id":"6196","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","title":"The exact security of PMAC","ddc":["000"],"intvolume":" 2016","oa_version":"Published Version","file":[{"creator":"dernst","content_type":"application/pdf","file_size":597335,"access_level":"open_access","file_name":"2017_IACR_Gazi.pdf","checksum":"f23161d685dd957ae8d7274132999684","date_created":"2019-04-04T13:53:58Z","date_updated":"2020-07-14T12:47:24Z","file_id":"6197","relation":"main_file"}],"month":"02","publication_identifier":{"eissn":["2519-173X"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","project":[{"grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"doi":"10.13154/TOSC.V2016.I2.145-161","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:47:24Z","ec_funded":1,"year":"2017","publication_status":"published","publisher":"Ruhr University Bochum","department":[{"_id":"KrPi"}],"author":[{"last_name":"Gazi","first_name":"Peter","id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","full_name":"Gazi, Peter"},{"full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","last_name":"Pietrzak"},{"full_name":"Rybar, Michal","first_name":"Michal","last_name":"Rybar","id":"2B3E3DE8-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"id":"838","status":"public","relation":"dissertation_contains"}]},"date_created":"2019-04-04T13:48:23Z","date_updated":"2023-09-07T12:02:27Z","volume":2016},{"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"degree_awarded":"PhD","supervisor":[{"first_name":"Jozsef L","last_name":"Csicsvari","id":"3FA14672-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5193-4036","full_name":"Csicsvari, Jozsef L"}],"language":[{"iso":"eng"}],"doi":"10.15479/AT:ISTA:th_858","month":"08","publication_identifier":{"issn":["2663-337X"]},"publication_status":"published","publisher":"Institute of Science and Technology Austria","department":[{"_id":"JoCs"}],"year":"2017","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. ","date_updated":"2023-09-07T12:06:38Z","date_created":"2018-12-11T11:48:46Z","author":[{"id":"310349D0-F248-11E8-B48F-1D18A9856A87","first_name":"Haibing","last_name":"Xu","full_name":"Xu, Haibing"}],"related_material":{"record":[{"id":"5828","status":"public","relation":"part_of_dissertation"}]},"file_date_updated":"2020-07-14T12:48:12Z","publist_id":"6811","page":"93","citation":{"mla":"Xu, Haibing. Reactivation of the Hippocampal Cognitive Map in Goal-Directed Spatial Tasks. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_858.","short":"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. https://doi.org/10.15479/AT:ISTA:th_858.","ama":"Xu H. Reactivation of the hippocampal cognitive map in goal-directed spatial tasks. 2017. doi:10.15479/AT:ISTA:th_858","ista":"Xu H. 2017. Reactivation of the hippocampal cognitive map in goal-directed spatial tasks. Institute of Science and Technology Austria.","apa":"Xu, H. (2017). Reactivation of the hippocampal cognitive map in goal-directed spatial tasks. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_858","ieee":"H. Xu, “Reactivation of the hippocampal cognitive map in goal-directed spatial tasks,” Institute of Science and Technology Austria, 2017."},"date_published":"2017-08-23T00:00:00Z","day":"23","has_accepted_license":"1","article_processing_charge":"No","title":"Reactivation of the hippocampal cognitive map in goal-directed spatial tasks","ddc":["571"],"status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"837","oa_version":"Published Version","file":[{"access_level":"closed","file_name":"2017_Xu_Haibing_Thesis_Source.docx","creator":"dernst","content_type":"application/vnd.openxmlformats-officedocument.wordprocessingml.document","file_size":3589490,"file_id":"6213","relation":"source_file","checksum":"f11925fbbce31e495124b6bc4f10573c","date_created":"2019-04-05T08:59:51Z","date_updated":"2020-07-14T12:48:12Z"},{"file_name":"2017_Xu_Thesis_IST.pdf","access_level":"open_access","content_type":"application/pdf","file_size":11668613,"creator":"dernst","relation":"main_file","file_id":"6214","date_created":"2019-04-05T08:59:51Z","date_updated":"2020-07-14T12:48:12Z","checksum":"ffb10749a537d615fab1ef0937ccb157"}],"pubrep_id":"858","alternative_title":["ISTA Thesis"],"type":"dissertation","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. "}]},{"publication_identifier":{"issn":["2663-337X"]},"month":"06","oa":1,"language":[{"iso":"eng"}],"supervisor":[{"last_name":"Friml","first_name":"Jiří","orcid":"0000-0002-8302-7596","id":"4159519E-F248-11E8-B48F-1D18A9856A87","full_name":"Friml, Jiří"}],"degree_awarded":"PhD","doi":"10.15479/AT:ISTA:th_842","publist_id":"6483","file_date_updated":"2020-07-14T12:48:15Z","department":[{"_id":"JiFr"}],"publisher":"Institute of Science and Technology Austria","publication_status":"published","year":"2017","date_updated":"2023-09-07T12:06:09Z","date_created":"2018-12-11T11:49:18Z","related_material":{"record":[{"id":"1591","relation":"part_of_dissertation","status":"public"}]},"author":[{"full_name":"Adamowski, Maciek","last_name":"Adamowski","first_name":"Maciek","orcid":"0000-0001-6463-5257","id":"45F536D2-F248-11E8-B48F-1D18A9856A87"}],"article_processing_charge":"No","has_accepted_license":"1","day":"02","page":"117","citation":{"ama":"Adamowski M. Investigations into cell polarity and trafficking in the plant model Arabidopsis thaliana . 2017. doi:10.15479/AT:ISTA:th_842","ista":"Adamowski M. 2017. Investigations into cell polarity and trafficking in the plant model Arabidopsis thaliana . Institute of Science and Technology Austria.","apa":"Adamowski, M. (2017). Investigations into cell polarity and trafficking in the plant model Arabidopsis thaliana . Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_842","ieee":"M. Adamowski, “Investigations into cell polarity and trafficking in the plant model Arabidopsis thaliana ,” Institute of Science and Technology Austria, 2017.","mla":"Adamowski, Maciek. Investigations into Cell Polarity and Trafficking in the Plant Model Arabidopsis Thaliana . Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_842.","short":"M. Adamowski, Investigations into Cell Polarity and Trafficking in the Plant Model Arabidopsis Thaliana , Institute of Science and Technology Austria, 2017.","chicago":"Adamowski, Maciek. “Investigations into Cell Polarity and Trafficking in the Plant Model Arabidopsis Thaliana .” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_842."},"date_published":"2017-06-02T00:00:00Z","alternative_title":["ISTA Thesis"],"type":"dissertation","abstract":[{"lang":"eng","text":"The thesis encompasses several topics of plant cell biology which were studied in the model plant Arabidopsis thaliana. Chapter 1 concerns the plant hormone auxin and its polar transport through cells and tissues. The highly controlled, directional transport of auxin is facilitated by plasma membrane-localized transporters. Transporters from the PIN family direct auxin transport due to their polarized localizations at cell membranes. Substantial effort has been put into research on cellular trafficking of PIN proteins, which is thought to underlie their polar distribution. I participated in a forward genetic screen aimed at identifying novel regulators of PIN polarity. The screen yielded several genes which may be involved in PIN polarity regulation or participate in polar auxin transport by other means. Chapter 2 focuses on the endomembrane system, with particular attention to clathrin-mediated endocytosis. The project started with identification of several proteins that interact with clathrin light chains. Among them, I focused on two putative homologues of auxilin, which in non-plant systems is an endocytotic factor known for uncoating clathrin-coated vesicles in the final step of endocytosis. The body of my work consisted of an in-depth characterization of transgenic A. thaliana lines overexpressing these putative auxilins in an inducible manner. Overexpression of these proteins leads to an inhibition of endocytosis, as documented by imaging of cargoes and clathrin-related endocytic machinery. An extension of this work is an investigation into a concept of homeostatic regulation acting between distinct transport processes in the endomembrane system. With auxilin overexpressing lines, where endocytosis is blocked specifically, I made observations on the mutual relationship between two opposite trafficking processes of secretion and endocytosis. In Chapter 3, I analyze cortical microtubule arrays and their relationship to auxin signaling and polarized growth in elongating cells. In plants, microtubules are organized into arrays just below the plasma membrane, and it is thought that their function is to guide membrane-docked cellulose synthase complexes. These, in turn, influence cell wall structure and cell shape by directed deposition of cellulose fibres. In elongating cells, cortical microtubule arrays are able to reorient in relation to long cell axis, and these reorientations have been linked to cell growth and to signaling of growth-regulating factors such as auxin or light. In this chapter, I am addressing the causal relationship between microtubule array reorientation, growth, and auxin signaling. I arrive at a model where array reorientation is not guided by auxin directly, but instead is only controlled by growth, which, in turn, is regulated by auxin."}],"status":"public","title":"Investigations into cell polarity and trafficking in the plant model Arabidopsis thaliana ","ddc":["581","583","580"],"_id":"938","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa_version":"Published Version","file":[{"file_id":"6215","relation":"source_file","checksum":"193425764d9aaaed3ac57062a867b315","date_updated":"2020-07-14T12:48:15Z","date_created":"2019-04-05T09:03:20Z","access_level":"closed","file_name":"2017_Adamowski-Thesis_Source.docx","creator":"dernst","file_size":46903863,"content_type":"application/vnd.openxmlformats-officedocument.wordprocessingml.document"},{"content_type":"application/pdf","file_size":8698888,"creator":"dernst","access_level":"open_access","file_name":"2017_Adamowski-Thesis.pdf","checksum":"df5ab01be81f821e1b958596a1ec8d21","date_updated":"2020-07-14T12:48:15Z","date_created":"2019-04-05T09:03:19Z","relation":"main_file","file_id":"6216"}],"pubrep_id":"842"},{"publist_id":"6407","ec_funded":1,"file_date_updated":"2020-07-14T12:48:18Z","department":[{"_id":"VlKo"}],"publisher":"Institute of Science and Technology Austria","publication_status":"published","acknowledgement":"FP7/2007-2013/ERC grant agreement no 616160","year":"2017","date_updated":"2023-09-07T12:05:41Z","date_created":"2018-12-11T11:49:35Z","author":[{"full_name":"Rolinek, Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","last_name":"Rolinek","first_name":"Michal"}],"publication_identifier":{"issn":["2663-337X"]},"month":"05","project":[{"grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"oa":1,"language":[{"iso":"eng"}],"supervisor":[{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"}],"degree_awarded":"PhD","doi":"10.15479/AT:ISTA:th_815","alternative_title":["ISTA Thesis"],"type":"dissertation","abstract":[{"lang":"eng","text":"An instance of the Constraint Satisfaction Problem (CSP) is given by a finite set of\r\nvariables, a finite domain of labels, and a set of constraints, each constraint acting on\r\na subset of the variables. The goal is to find an assignment of labels to its variables\r\nthat satisfies all constraints (or decide whether one exists). If we allow more general\r\n“soft” constraints, which come with (possibly infinite) costs of particular assignments,\r\nwe obtain instances from a richer class called Valued Constraint Satisfaction Problem\r\n(VCSP). There the goal is to find an assignment with minimum total cost.\r\nIn this thesis, we focus (assuming that P\r\n6\r\n=\r\nNP) on classifying computational com-\r\nplexity of CSPs and VCSPs under certain restricting conditions. Two results are the core\r\ncontent of the work. In one of them, we consider VCSPs parametrized by a constraint\r\nlanguage, that is the set of “soft” constraints allowed to form the instances, and finish\r\nthe complexity classification modulo (missing pieces of) complexity classification for\r\nanalogously parametrized CSP. The other result is a generalization of Edmonds’ perfect\r\nmatching algorithm. This generalization contributes to complexity classfications in two\r\nways. First, it gives a new (largest known) polynomial-time solvable class of Boolean\r\nCSPs in which every variable may appear in at most two constraints and second, it\r\nsettles full classification of Boolean CSPs with planar drawing (again parametrized by a\r\nconstraint language)."}],"ddc":["004"],"title":"Complexity of constraint satisfaction","status":"public","_id":"992","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa_version":"Published Version","file":[{"date_updated":"2020-07-14T12:48:18Z","date_created":"2018-12-12T10:07:55Z","checksum":"81761fb939acb7585c36629f765b4373","relation":"main_file","file_id":"4654","file_size":786145,"content_type":"application/pdf","creator":"system","file_name":"IST-2017-815-v1+3_final_blank_signature_maybe_pdfa.pdf","access_level":"open_access"},{"file_name":"2017_Thesis_Rolinek_source.zip","access_level":"closed","creator":"dernst","content_type":"application/zip","file_size":5936337,"file_id":"6208","relation":"source_file","date_created":"2019-04-05T08:43:24Z","date_updated":"2020-07-14T12:48:18Z","checksum":"2b2d7e1d6c1c79a9795a7aa0f860baf3"}],"pubrep_id":"815","has_accepted_license":"1","article_processing_charge":"No","day":"01","page":"97","citation":{"apa":"Rolinek, M. (2017). Complexity of constraint satisfaction. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_815","ieee":"M. Rolinek, “Complexity of constraint satisfaction,” Institute of Science and Technology Austria, 2017.","ista":"Rolinek M. 2017. Complexity of constraint satisfaction. Institute of Science and Technology Austria.","ama":"Rolinek M. Complexity of constraint satisfaction. 2017. doi:10.15479/AT:ISTA:th_815","chicago":"Rolinek, Michal. “Complexity of Constraint Satisfaction.” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_815.","short":"M. Rolinek, Complexity of Constraint Satisfaction, Institute of Science and Technology Austria, 2017.","mla":"Rolinek, Michal. Complexity of Constraint Satisfaction. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_815."},"date_published":"2017-05-01T00:00:00Z"},{"date_published":"2017-09-01T00:00:00Z","citation":{"ista":"Edelsbrunner H, Nikitenko A, Reitzner M. 2017. Expected sizes of poisson Delaunay mosaics and their discrete Morse functions. Advances in Applied Probability. 49(3), 745–767.","apa":"Edelsbrunner, H., Nikitenko, A., & Reitzner, M. (2017). Expected sizes of poisson Delaunay mosaics and their discrete Morse functions. Advances in Applied Probability. Cambridge University Press. https://doi.org/10.1017/apr.2017.20","ieee":"H. Edelsbrunner, A. Nikitenko, and M. Reitzner, “Expected sizes of poisson Delaunay mosaics and their discrete Morse functions,” Advances in Applied Probability, vol. 49, no. 3. Cambridge University Press, pp. 745–767, 2017.","ama":"Edelsbrunner H, Nikitenko A, Reitzner M. Expected sizes of poisson Delaunay mosaics and their discrete Morse functions. Advances in Applied Probability. 2017;49(3):745-767. doi:10.1017/apr.2017.20","chicago":"Edelsbrunner, Herbert, Anton Nikitenko, and Matthias Reitzner. “Expected Sizes of Poisson Delaunay Mosaics and Their Discrete Morse Functions.” Advances in Applied Probability. Cambridge University Press, 2017. https://doi.org/10.1017/apr.2017.20.","mla":"Edelsbrunner, Herbert, et al. “Expected Sizes of Poisson Delaunay Mosaics and Their Discrete Morse Functions.” Advances in Applied Probability, vol. 49, no. 3, Cambridge University Press, 2017, pp. 745–67, doi:10.1017/apr.2017.20.","short":"H. Edelsbrunner, A. Nikitenko, M. Reitzner, Advances in Applied Probability 49 (2017) 745–767."},"publication":"Advances in Applied Probability","page":"745 - 767","day":"01","scopus_import":1,"oa_version":"Preprint","_id":"718","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 49","status":"public","title":"Expected sizes of poisson Delaunay mosaics and their discrete Morse functions","issue":"3","abstract":[{"lang":"eng","text":"Mapping every simplex in the Delaunay mosaic of a discrete point set to the radius of the smallest empty circumsphere gives a generalized discrete Morse function. Choosing the points from a Poisson point process in ℝ n , we study the expected number of simplices in the Delaunay mosaic as well as the expected number of critical simplices and nonsingular intervals in the corresponding generalized discrete gradient. Observing connections with other probabilistic models, we obtain precise expressions for the expected numbers in low dimensions. In particular, we obtain the expected numbers of simplices in the Poisson–Delaunay mosaic in dimensions n ≤ 4."}],"type":"journal_article","doi":"10.1017/apr.2017.20","language":[{"iso":"eng"}],"external_id":{"arxiv":["1607.05915"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1607.05915"}],"oa":1,"project":[{"call_identifier":"FP7","name":"Topological Complex Systems","_id":"255D761E-B435-11E9-9278-68D0E5697425","grant_number":"318493"},{"name":"Persistence and stability of geometric complexes","call_identifier":"FWF","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35"}],"quality_controlled":"1","publication_identifier":{"issn":["00018678"]},"month":"09","related_material":{"record":[{"id":"6287","relation":"dissertation_contains","status":"public"}]},"author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert"},{"full_name":"Nikitenko, Anton","id":"3E4FF1BA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-0659-3201","first_name":"Anton","last_name":"Nikitenko"},{"last_name":"Reitzner","first_name":"Matthias","full_name":"Reitzner, Matthias"}],"volume":49,"date_created":"2018-12-11T11:48:07Z","date_updated":"2023-09-07T12:07:12Z","year":"2017","department":[{"_id":"HeEd"}],"publisher":"Cambridge University Press","publication_status":"published","publist_id":"6962","ec_funded":1},{"publication_status":"published","publisher":"Springer","department":[{"_id":"KrPi"}],"year":"2017","date_updated":"2023-09-07T12:30:22Z","date_created":"2018-12-11T11:47:10Z","volume":10625,"author":[{"id":"40297222-F248-11E8-B48F-1D18A9856A87","last_name":"Abusalah","first_name":"Hamza M","full_name":"Abusalah, Hamza M"},{"last_name":"Alwen","first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F"},{"last_name":"Cohen","first_name":"Bram","full_name":"Cohen, Bram"},{"full_name":"Khilko, Danylo","first_name":"Danylo","last_name":"Khilko"},{"full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Reyzin, Leonid","first_name":"Leonid","last_name":"Reyzin"}],"related_material":{"record":[{"id":"83","status":"public","relation":"dissertation_contains"}]},"ec_funded":1,"publist_id":"7257","quality_controlled":"1","project":[{"grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"main_file_link":[{"url":"https://eprint.iacr.org/2017/893.pdf","open_access":"1"}],"oa":1,"language":[{"iso":"eng"}],"conference":{"start_date":"2017-12-03","location":"Hong Kong, China","end_date":"2017-12-07","name":"ASIACRYPT: Theory and Applications of Cryptology and Information Security"},"doi":"10.1007/978-3-319-70697-9_13","month":"11","publication_identifier":{"isbn":["978-331970696-2"]},"status":"public","title":"Beyond Hellman’s time-memory trade-offs with applications to proofs of space","intvolume":" 10625","_id":"559","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Submitted Version","alternative_title":["LNCS"],"type":"conference","abstract":[{"text":"Proofs of space (PoS) were suggested as more ecological and economical alternative to proofs of work, which are currently used in blockchain designs like Bitcoin. The existing PoS are based on rather sophisticated graph pebbling lower bounds. Much simpler and in several aspects more efficient schemes based on inverting random functions have been suggested, but they don’t give meaningful security guarantees due to existing time-memory trade-offs. In particular, Hellman showed that any permutation over a domain of size N can be inverted in time T by an algorithm that is given S bits of auxiliary information whenever (Formula presented). For functions Hellman gives a weaker attack with S2· T≈ N2 (e.g., S= T≈ N2/3). To prove lower bounds, one considers an adversary who has access to an oracle f: [ N] → [N] and can make T oracle queries. The best known lower bound is S· T∈ Ω(N) and holds for random functions and permutations. We construct functions that provably require more time and/or space to invert. Specifically, for any constant k we construct a function [N] → [N] that cannot be inverted unless Sk· T∈ Ω(Nk) (in particular, S= T≈ (Formula presented). Our construction does not contradict Hellman’s time-memory trade-off, because it cannot be efficiently evaluated in forward direction. However, its entire function table can be computed in time quasilinear in N, which is sufficient for the PoS application. Our simplest construction is built from a random function oracle g: [N] × [N] → [ N] and a random permutation oracle f: [N] → N] and is defined as h(x) = g(x, x′) where f(x) = π(f(x′)) with π being any involution without a fixed point, e.g. flipping all the bits. For this function we prove that any adversary who gets S bits of auxiliary information, makes at most T oracle queries, and inverts h on an ϵ fraction of outputs must satisfy S2· T∈ Ω(ϵ2N2).","lang":"eng"}],"page":"357 - 379","citation":{"ama":"Abusalah HM, Alwen JF, Cohen B, Khilko D, Pietrzak KZ, Reyzin L. Beyond Hellman’s time-memory trade-offs with applications to proofs of space. In: Vol 10625. Springer; 2017:357-379. doi:10.1007/978-3-319-70697-9_13","ista":"Abusalah HM, Alwen JF, Cohen B, Khilko D, Pietrzak KZ, Reyzin L. 2017. Beyond Hellman’s time-memory trade-offs with applications to proofs of space. ASIACRYPT: Theory and Applications of Cryptology and Information Security, LNCS, vol. 10625, 357–379.","apa":"Abusalah, H. M., Alwen, J. F., Cohen, B., Khilko, D., Pietrzak, K. Z., & Reyzin, L. (2017). Beyond Hellman’s time-memory trade-offs with applications to proofs of space (Vol. 10625, pp. 357–379). Presented at the ASIACRYPT: Theory and Applications of Cryptology and Information Security, Hong Kong, China: Springer. https://doi.org/10.1007/978-3-319-70697-9_13","ieee":"H. M. Abusalah, J. F. Alwen, B. Cohen, D. Khilko, K. Z. Pietrzak, and L. Reyzin, “Beyond Hellman’s time-memory trade-offs with applications to proofs of space,” presented at the ASIACRYPT: Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017, vol. 10625, pp. 357–379.","mla":"Abusalah, Hamza M., et al. Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space. Vol. 10625, Springer, 2017, pp. 357–79, doi:10.1007/978-3-319-70697-9_13.","short":"H.M. Abusalah, J.F. Alwen, B. Cohen, D. Khilko, K.Z. Pietrzak, L. Reyzin, in:, Springer, 2017, pp. 357–379.","chicago":"Abusalah, Hamza M, Joel F Alwen, Bram Cohen, Danylo Khilko, Krzysztof Z Pietrzak, and Leonid Reyzin. “Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space,” 10625:357–79. Springer, 2017. https://doi.org/10.1007/978-3-319-70697-9_13."},"date_published":"2017-11-18T00:00:00Z","scopus_import":1,"day":"18"},{"citation":{"mla":"Alt, Johannes. “Singularities of the Density of States of Random Gram Matrices.” Electronic Communications in Probability, vol. 22, 63, Institute of Mathematical Statistics, 2017, doi:10.1214/17-ECP97.","short":"J. Alt, Electronic Communications in Probability 22 (2017).","chicago":"Alt, Johannes. “Singularities of the Density of States of Random Gram Matrices.” Electronic Communications in Probability. Institute of Mathematical Statistics, 2017. https://doi.org/10.1214/17-ECP97.","ama":"Alt J. Singularities of the density of states of random Gram matrices. Electronic Communications in Probability. 2017;22. doi:10.1214/17-ECP97","ista":"Alt J. 2017. Singularities of the density of states of random Gram matrices. Electronic Communications in Probability. 22, 63.","apa":"Alt, J. (2017). Singularities of the density of states of random Gram matrices. Electronic Communications in Probability. Institute of Mathematical Statistics. https://doi.org/10.1214/17-ECP97","ieee":"J. Alt, “Singularities of the density of states of random Gram matrices,” Electronic Communications in Probability, vol. 22. Institute of Mathematical Statistics, 2017."},"publication":"Electronic Communications in Probability","date_published":"2017-11-21T00:00:00Z","scopus_import":1,"has_accepted_license":"1","day":"21","intvolume":" 22","title":"Singularities of the density of states of random Gram matrices","ddc":["539"],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"550","file":[{"file_id":"4663","relation":"main_file","checksum":"0ec05303a0de190de145654237984c79","date_updated":"2020-07-14T12:47:00Z","date_created":"2018-12-12T10:08:04Z","access_level":"open_access","file_name":"IST-2018-926-v1+1_euclid.ecp.1511233247.pdf","creator":"system","content_type":"application/pdf","file_size":470876}],"oa_version":"Published Version","pubrep_id":"926","type":"journal_article","abstract":[{"text":"For large random matrices X with independent, centered entries but not necessarily identical variances, the eigenvalue density of XX* is well-approximated by a deterministic measure on ℝ. We show that the density of this measure has only square and cubic-root singularities away from zero. We also extend the bulk local law in [5] to the vicinity of these singularities.","lang":"eng"}],"project":[{"grant_number":"338804","_id":"258DCDE6-B435-11E9-9278-68D0E5697425","name":"Random matrices, universality and disordered quantum systems","call_identifier":"FP7"}],"quality_controlled":"1","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"language":[{"iso":"eng"}],"doi":"10.1214/17-ECP97","publication_identifier":{"issn":["1083589X"]},"month":"11","publisher":"Institute of Mathematical Statistics","department":[{"_id":"LaEr"}],"publication_status":"published","year":"2017","volume":22,"date_created":"2018-12-11T11:47:07Z","date_updated":"2023-09-07T12:38:08Z","related_material":{"record":[{"id":"149","status":"public","relation":"dissertation_contains"}]},"author":[{"full_name":"Alt, Johannes","id":"36D3D8B6-F248-11E8-B48F-1D18A9856A87","last_name":"Alt","first_name":"Johannes"}],"article_number":"63","ec_funded":1,"publist_id":"7265","file_date_updated":"2020-07-14T12:47:00Z"},{"oa":1,"project":[{"name":"Moderne Concurrency Paradigms","call_identifier":"FWF","grant_number":"S11402-N23","_id":"25F5A88A-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"}],"quality_controlled":"1","doi":"10.1007/978-3-319-65765-3_7","conference":{"end_date":"2017-09-07","location":"Berlin, Germany","start_date":"2017-09-05","name":"FORMATS: Formal Modelling and Analysis of Timed Systems"},"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-331965764-6"]},"month":"09","year":"2017","department":[{"_id":"ToHe"}],"publisher":"Springer","publication_status":"published","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"6894"}]},"author":[{"full_name":"Bogomolov, Sergiy","first_name":"Sergiy","last_name":"Bogomolov","id":"369D9A44-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-0686-0365"},{"full_name":"Giacobbe, Mirco","orcid":"0000-0001-8180-0904","id":"3444EA5E-F248-11E8-B48F-1D18A9856A87","last_name":"Giacobbe","first_name":"Mirco"},{"orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A"},{"full_name":"Kong, Hui","id":"3BDE25AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3066-6941","first_name":"Hui","last_name":"Kong"}],"volume":"10419 ","date_created":"2018-12-11T11:47:41Z","date_updated":"2023-09-07T12:53:00Z","publist_id":"7129","file_date_updated":"2020-07-14T12:47:31Z","citation":{"chicago":"Bogomolov, Sergiy, Mirco Giacobbe, Thomas A Henzinger, and Hui Kong. “Conic Abstractions for Hybrid Systems,” 10419:116–32. Springer, 2017. https://doi.org/10.1007/978-3-319-65765-3_7.","mla":"Bogomolov, Sergiy, et al. Conic Abstractions for Hybrid Systems. Vol. 10419, Springer, 2017, pp. 116–32, doi:10.1007/978-3-319-65765-3_7.","short":"S. Bogomolov, M. Giacobbe, T.A. Henzinger, H. Kong, in:, Springer, 2017, pp. 116–132.","ista":"Bogomolov S, Giacobbe M, Henzinger TA, Kong H. 2017. Conic abstractions for hybrid systems. FORMATS: Formal Modelling and Analysis of Timed Systems, LNCS, vol. 10419, 116–132.","ieee":"S. Bogomolov, M. Giacobbe, T. A. Henzinger, and H. Kong, “Conic abstractions for hybrid systems,” presented at the FORMATS: Formal Modelling and Analysis of Timed Systems, Berlin, Germany, 2017, vol. 10419, pp. 116–132.","apa":"Bogomolov, S., Giacobbe, M., Henzinger, T. A., & Kong, H. (2017). Conic abstractions for hybrid systems (Vol. 10419, pp. 116–132). Presented at the FORMATS: Formal Modelling and Analysis of Timed Systems, Berlin, Germany: Springer. https://doi.org/10.1007/978-3-319-65765-3_7","ama":"Bogomolov S, Giacobbe M, Henzinger TA, Kong H. Conic abstractions for hybrid systems. In: Vol 10419. Springer; 2017:116-132. doi:10.1007/978-3-319-65765-3_7"},"page":"116 - 132","date_published":"2017-09-01T00:00:00Z","scopus_import":1,"has_accepted_license":"1","day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"647","ddc":["005"],"title":"Conic abstractions for hybrid systems","status":"public","pubrep_id":"831","oa_version":"Submitted Version","file":[{"file_id":"4956","relation":"main_file","checksum":"faf546914ba29bcf9974ee36b6b16750","date_updated":"2020-07-14T12:47:31Z","date_created":"2018-12-12T10:12:38Z","access_level":"open_access","file_name":"IST-2017-831-v1+1_main.pdf","creator":"system","content_type":"application/pdf","file_size":3806864}],"type":"conference","alternative_title":["LNCS"],"abstract":[{"lang":"eng","text":"Despite researchers’ efforts in the last couple of decades, reachability analysis is still a challenging problem even for linear hybrid systems. Among the existing approaches, the most practical ones are mainly based on bounded-time reachable set over-approximations. For the purpose of unbounded-time analysis, one important strategy is to abstract the original system and find an invariant for the abstraction. In this paper, we propose an approach to constructing a new kind of abstraction called conic abstraction for affine hybrid systems, and to computing reachable sets based on this abstraction. The essential feature of a conic abstraction is that it partitions the state space of a system into a set of convex polyhedral cones which is derived from a uniform conic partition of the derivative space. Such a set of polyhedral cones is able to cut all trajectories of the system into almost straight segments so that every segment of a reach pipe in a polyhedral cone tends to be straight as well, and hence can be over-approximated tightly by polyhedra using similar techniques as HyTech or PHAVer. In particular, for diagonalizable affine systems, our approach can guarantee to find an invariant for unbounded reachable sets, which is beyond the capability of bounded-time reachability analysis tools. We implemented the approach in a tool and experiments on benchmarks show that our approach is more powerful than SpaceEx and PHAVer in dealing with diagonalizable systems."}]},{"month":"03","publication_identifier":{"isbn":["978-366254576-8"]},"oa":1,"quality_controlled":"1","project":[{"grant_number":"S11402-N23","_id":"25F5A88A-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Moderne Concurrency Paradigms"},{"name":"The Wittgenstein Prize","call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"}],"conference":{"name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","end_date":"2017-04-29","start_date":"2017-04-22","location":"Uppsala, Sweden"},"doi":"10.1007/978-3-662-54577-5_34","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:47:27Z","publist_id":"7162","acknowledgement":"This research was supported in part by the Austrian Science Fund (FWF) under grants S11402-N23 (RiSE/SHiNE) and Z211-N23 (Wittgenstein Award), by the European Commission under grant 643921 (UnCoVerCPS), and by the ARC project DP140104219 (Robust AI Planning for Hybrid Systems).","year":"2017","publication_status":"published","department":[{"_id":"ToHe"}],"publisher":"Springer","author":[{"full_name":"Bogomolov, Sergiy","id":"369D9A44-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-0686-0365","first_name":"Sergiy","last_name":"Bogomolov"},{"first_name":"Goran","last_name":"Frehse","full_name":"Frehse, Goran"},{"full_name":"Giacobbe, Mirco","orcid":"0000-0001-8180-0904","id":"3444EA5E-F248-11E8-B48F-1D18A9856A87","last_name":"Giacobbe","first_name":"Mirco"},{"full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724"}],"related_material":{"record":[{"id":"6894","status":"public","relation":"dissertation_contains"}]},"date_updated":"2023-09-07T12:53:00Z","date_created":"2018-12-11T11:47:36Z","volume":10205,"scopus_import":1,"day":"31","has_accepted_license":"1","citation":{"chicago":"Bogomolov, Sergiy, Goran Frehse, Mirco Giacobbe, and Thomas A Henzinger. “Counterexample Guided Refinement of Template Polyhedra,” 10205:589–606. Springer, 2017. https://doi.org/10.1007/978-3-662-54577-5_34.","mla":"Bogomolov, Sergiy, et al. Counterexample Guided Refinement of Template Polyhedra. Vol. 10205, Springer, 2017, pp. 589–606, doi:10.1007/978-3-662-54577-5_34.","short":"S. Bogomolov, G. Frehse, M. Giacobbe, T.A. Henzinger, in:, Springer, 2017, pp. 589–606.","ista":"Bogomolov S, Frehse G, Giacobbe M, Henzinger TA. 2017. Counterexample guided refinement of template polyhedra. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 10205, 589–606.","apa":"Bogomolov, S., Frehse, G., Giacobbe, M., & Henzinger, T. A. (2017). Counterexample guided refinement of template polyhedra (Vol. 10205, pp. 589–606). Presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, Uppsala, Sweden: Springer. https://doi.org/10.1007/978-3-662-54577-5_34","ieee":"S. Bogomolov, G. Frehse, M. Giacobbe, and T. A. Henzinger, “Counterexample guided refinement of template polyhedra,” presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, Uppsala, Sweden, 2017, vol. 10205, pp. 589–606.","ama":"Bogomolov S, Frehse G, Giacobbe M, Henzinger TA. Counterexample guided refinement of template polyhedra. In: Vol 10205. Springer; 2017:589-606. doi:10.1007/978-3-662-54577-5_34"},"page":"589 - 606","date_published":"2017-03-31T00:00:00Z","type":"conference","alternative_title":["LNCS"],"abstract":[{"lang":"eng","text":"Template polyhedra generalize intervals and octagons to polyhedra whose facets are orthogonal to a given set of arbitrary directions. They have been employed in the abstract interpretation of programs and, with particular success, in the reachability analysis of hybrid automata. While previously, the choice of directions has been left to the user or a heuristic, we present a method for the automatic discovery of directions that generalize and eliminate spurious counterexamples. We show that for the class of convex hybrid automata, i.e., hybrid automata with (possibly nonlinear) convex constraints on derivatives, such directions always exist and can be found using convex optimization. We embed our method inside a CEGAR loop, thus enabling the time-unbounded reachability analysis of an important and richer class of hybrid automata than was previously possible. We evaluate our method on several benchmarks, demonstrating also its superior efficiency for the special case of linear hybrid automata."}],"_id":"631","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","title":"Counterexample guided refinement of template polyhedra","ddc":["000"],"intvolume":" 10205","pubrep_id":"966","file":[{"relation":"main_file","file_id":"4897","date_updated":"2020-07-14T12:47:27Z","date_created":"2018-12-12T10:11:41Z","checksum":"f395d0d20102b89aeaad8b4ef4f18f4f","file_name":"IST-2017-741-v1+1_main.pdf","access_level":"open_access","content_type":"application/pdf","file_size":569863,"creator":"system"},{"content_type":"application/pdf","file_size":563276,"creator":"system","access_level":"open_access","file_name":"IST-2018-741-v2+2_main.pdf","checksum":"f416ee1ae4497b23ecdf28b1f18bb8df","date_created":"2018-12-12T10:11:42Z","date_updated":"2020-07-14T12:47:27Z","relation":"main_file","file_id":"4898"}],"oa_version":"Submitted Version"},{"year":"2017","acknowledgement":"Partially supported by the IST Austria Excellence Scholarship.","publication_status":"published","publisher":"Institute of Mathematical Statistics","department":[{"_id":"LaEr"}],"author":[{"full_name":"Erdös, László","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5366-9603","first_name":"László","last_name":"Erdös"},{"full_name":"Schröder, Dominik J","last_name":"Schröder","first_name":"Dominik J","orcid":"0000-0002-2904-1856","id":"408ED176-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"6179"}]},"date_created":"2018-12-11T11:50:23Z","date_updated":"2023-09-07T12:54:12Z","volume":21,"article_number":"86","file_date_updated":"2018-12-12T10:18:10Z","ec_funded":1,"publist_id":"6214","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","project":[{"call_identifier":"FP7","name":"Random matrices, universality and disordered quantum systems","grant_number":"338804","_id":"258DCDE6-B435-11E9-9278-68D0E5697425"}],"doi":"10.1214/16-ECP38","language":[{"iso":"eng"}],"month":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"1144","status":"public","title":"Fluctuations of functions of Wigner matrices","ddc":["510"],"intvolume":" 21","pubrep_id":"747","file":[{"access_level":"open_access","file_name":"IST-2017-747-v1+1_euclid.ecp.1483347665.pdf","creator":"system","content_type":"application/pdf","file_size":440770,"file_id":"5329","relation":"main_file","date_updated":"2018-12-12T10:18:10Z","date_created":"2018-12-12T10:18:10Z"}],"oa_version":"Published Version","type":"journal_article","abstract":[{"text":"We show that matrix elements of functions of N × N Wigner matrices fluctuate on a scale of order N−1/2 and we identify the limiting fluctuation. Our result holds for any function f of the matrix that has bounded variation thus considerably relaxing the regularity requirement imposed in [7, 11].","lang":"eng"}],"publication":"Electronic Communications in Probability","citation":{"ista":"Erdös L, Schröder DJ. 2017. Fluctuations of functions of Wigner matrices. Electronic Communications in Probability. 21, 86.","apa":"Erdös, L., & Schröder, D. J. (2017). Fluctuations of functions of Wigner matrices. Electronic Communications in Probability. Institute of Mathematical Statistics. https://doi.org/10.1214/16-ECP38","ieee":"L. Erdös and D. J. Schröder, “Fluctuations of functions of Wigner matrices,” Electronic Communications in Probability, vol. 21. Institute of Mathematical Statistics, 2017.","ama":"Erdös L, Schröder DJ. Fluctuations of functions of Wigner matrices. Electronic Communications in Probability. 2017;21. doi:10.1214/16-ECP38","chicago":"Erdös, László, and Dominik J Schröder. “Fluctuations of Functions of Wigner Matrices.” Electronic Communications in Probability. Institute of Mathematical Statistics, 2017. https://doi.org/10.1214/16-ECP38.","mla":"Erdös, László, and Dominik J. Schröder. “Fluctuations of Functions of Wigner Matrices.” Electronic Communications in Probability, vol. 21, 86, Institute of Mathematical Statistics, 2017, doi:10.1214/16-ECP38.","short":"L. Erdös, D.J. Schröder, Electronic Communications in Probability 21 (2017)."},"date_published":"2017-01-02T00:00:00Z","scopus_import":1,"day":"02","has_accepted_license":"1"},{"month":"11","publication_identifier":{"issn":["07300301"]},"language":[{"iso":"eng"}],"doi":"10.1145/3130800.3130890","quality_controlled":"1","project":[{"grant_number":"642841","_id":"2508E324-B435-11E9-9278-68D0E5697425","name":"Distributed 3D Object Design","call_identifier":"H2020"},{"_id":"24F9549A-B435-11E9-9278-68D0E5697425","grant_number":"715767","name":"MATERIALIZABLE: Intelligent fabrication-oriented Computational Design and Modeling","call_identifier":"H2020"},{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"oa":1,"file_date_updated":"2020-07-14T12:46:35Z","ec_funded":1,"publist_id":"7334","article_number":"241","date_created":"2018-12-11T11:46:44Z","date_updated":"2023-09-07T13:11:15Z","volume":36,"author":[{"full_name":"Elek, Oskar","last_name":"Elek","first_name":"Oskar"},{"full_name":"Sumin, Denis","last_name":"Sumin","first_name":"Denis"},{"full_name":"Zhang, Ran","orcid":"0000-0002-3808-281X","id":"4DDBCEB0-F248-11E8-B48F-1D18A9856A87","last_name":"Zhang","first_name":"Ran"},{"full_name":"Weyrich, Tim","last_name":"Weyrich","first_name":"Tim"},{"full_name":"Myszkowski, Karol","last_name":"Myszkowski","first_name":"Karol"},{"full_name":"Bickel, Bernd","first_name":"Bernd","last_name":"Bickel","id":"49876194-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6511-9385"},{"last_name":"Wilkie","first_name":"Alexander","full_name":"Wilkie, Alexander"},{"first_name":"Jaroslav","last_name":"Krivanek","full_name":"Krivanek, Jaroslav"}],"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"8386"}]},"publication_status":"published","department":[{"_id":"BeBi"}],"publisher":"ACM","year":"2017","day":"20","has_accepted_license":"1","article_processing_charge":"No","scopus_import":1,"date_published":"2017-11-20T00:00:00Z","article_type":"original","publication":"ACM Transactions on Graphics","citation":{"ieee":"O. Elek et al., “Scattering-aware texture reproduction for 3D printing,” ACM Transactions on Graphics, vol. 36, no. 6. ACM, 2017.","apa":"Elek, O., Sumin, D., Zhang, R., Weyrich, T., Myszkowski, K., Bickel, B., … Krivanek, J. (2017). Scattering-aware texture reproduction for 3D printing. ACM Transactions on Graphics. ACM. https://doi.org/10.1145/3130800.3130890","ista":"Elek O, Sumin D, Zhang R, Weyrich T, Myszkowski K, Bickel B, Wilkie A, Krivanek J. 2017. Scattering-aware texture reproduction for 3D printing. ACM Transactions on Graphics. 36(6), 241.","ama":"Elek O, Sumin D, Zhang R, et al. Scattering-aware texture reproduction for 3D printing. ACM Transactions on Graphics. 2017;36(6). doi:10.1145/3130800.3130890","chicago":"Elek, Oskar, Denis Sumin, Ran Zhang, Tim Weyrich, Karol Myszkowski, Bernd Bickel, Alexander Wilkie, and Jaroslav Krivanek. “Scattering-Aware Texture Reproduction for 3D Printing.” ACM Transactions on Graphics. ACM, 2017. https://doi.org/10.1145/3130800.3130890.","short":"O. Elek, D. Sumin, R. Zhang, T. Weyrich, K. Myszkowski, B. Bickel, A. Wilkie, J. Krivanek, ACM Transactions on Graphics 36 (2017).","mla":"Elek, Oskar, et al. “Scattering-Aware Texture Reproduction for 3D Printing.” ACM Transactions on Graphics, vol. 36, no. 6, 241, ACM, 2017, doi:10.1145/3130800.3130890."},"abstract":[{"text":"Color texture reproduction in 3D printing commonly ignores volumetric light transport (cross-talk) between surface points on a 3D print. Such light diffusion leads to significant blur of details and color bleeding, and is particularly severe for highly translucent resin-based print materials. Given their widely varying scattering properties, this cross-talk between surface points strongly depends on the internal structure of the volume surrounding each surface point. Existing scattering-aware methods use simplified models for light diffusion, and often accept the visual blur as an immutable property of the print medium. In contrast, our work counteracts heterogeneous scattering to obtain the impression of a crisp albedo texture on top of the 3D print, by optimizing for a fully volumetric material distribution that preserves the target appearance. Our method employs an efficient numerical optimizer on top of a general Monte-Carlo simulation of heterogeneous scattering, supported by a practical calibration procedure to obtain scattering parameters from a given set of printer materials. Despite the inherent translucency of the medium, we reproduce detailed surface textures on 3D prints. We evaluate our system using a commercial, five-tone 3D print process and compare against the printer’s native color texturing mode, demonstrating that our method preserves high-frequency features well without having to compromise on color gamut.","lang":"eng"}],"issue":"6","type":"journal_article","oa_version":"Submitted Version","file":[{"access_level":"open_access","file_name":"IST-2018-1052-v1+1_ElekSumin2017SGA.pdf","file_size":107349827,"content_type":"application/pdf","creator":"system","relation":"main_file","file_id":"4836","checksum":"48386fa6956c3645fc89594dc898b147","date_created":"2018-12-12T10:10:46Z","date_updated":"2020-07-14T12:46:35Z"},{"access_level":"open_access","file_name":"ElekSumin2017SGA_reduced_file_size.pdf","content_type":"application/pdf","file_size":4683145,"creator":"bbickel","relation":"main_file","file_id":"7189","checksum":"21c89c28fb8d70f6602f752bf997aa0f","date_created":"2019-12-16T14:48:57Z","date_updated":"2020-07-14T12:46:35Z"}],"pubrep_id":"1052","ddc":["003","000","005"],"status":"public","title":"Scattering-aware texture reproduction for 3D printing","intvolume":" 36","_id":"486","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"main_file_link":[{"url":"https://eprint.iacr.org/2017/515","open_access":"1"}],"oa":1,"quality_controlled":"1","project":[{"grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"conference":{"end_date":"2017-07-24","location":"Santa Barbara, CA, United States","start_date":"2017-07-20","name":"CRYPTO: Cryptology"},"doi":"10.1007/978-3-319-63688-7_5","language":[{"iso":"eng"}],"month":"01","publication_identifier":{"isbn":["978-331963687-0"]},"year":"2017","publication_status":"published","publisher":"Springer","editor":[{"last_name":"Katz","first_name":"Jonathan","full_name":"Katz, Jonathan"},{"full_name":"Shacham, Hovav","first_name":"Hovav","last_name":"Shacham"}],"department":[{"_id":"KrPi"}],"author":[{"last_name":"Jafargholi","first_name":"Zahra","full_name":"Jafargholi, Zahra"},{"last_name":"Kamath Hosdurg","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan"},{"full_name":"Klein, Karen","last_name":"Klein","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Komargodski, Ilan","first_name":"Ilan","last_name":"Komargodski"},{"last_name":"Pietrzak","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z"},{"last_name":"Wichs","first_name":"Daniel","full_name":"Wichs, Daniel"}],"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"10035"}]},"date_created":"2018-12-11T11:47:38Z","date_updated":"2023-09-07T13:32:11Z","volume":10401,"publist_id":"7151","ec_funded":1,"citation":{"mla":"Jafargholi, Zahra, et al. Be Adaptive Avoid Overcommitting. Edited by Jonathan Katz and Hovav Shacham, vol. 10401, Springer, 2017, pp. 133–63, doi:10.1007/978-3-319-63688-7_5.","short":"Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K.Z. Pietrzak, D. Wichs, in:, J. Katz, H. Shacham (Eds.), Springer, 2017, pp. 133–163.","chicago":"Jafargholi, Zahra, Chethan Kamath Hosdurg, Karen Klein, Ilan Komargodski, Krzysztof Z Pietrzak, and Daniel Wichs. “Be Adaptive Avoid Overcommitting.” edited by Jonathan Katz and Hovav Shacham, 10401:133–63. Springer, 2017. https://doi.org/10.1007/978-3-319-63688-7_5.","ama":"Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs D. Be adaptive avoid overcommitting. In: Katz J, Shacham H, eds. Vol 10401. Springer; 2017:133-163. doi:10.1007/978-3-319-63688-7_5","ista":"Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs D. 2017. Be adaptive avoid overcommitting. CRYPTO: Cryptology, LNCS, vol. 10401, 133–163.","ieee":"Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K. Z. Pietrzak, and D. Wichs, “Be adaptive avoid overcommitting,” presented at the CRYPTO: Cryptology, Santa Barbara, CA, United States, 2017, vol. 10401, pp. 133–163.","apa":"Jafargholi, Z., Kamath Hosdurg, C., Klein, K., Komargodski, I., Pietrzak, K. Z., & Wichs, D. (2017). Be adaptive avoid overcommitting. In J. Katz & H. Shacham (Eds.) (Vol. 10401, pp. 133–163). Presented at the CRYPTO: Cryptology, Santa Barbara, CA, United States: Springer. https://doi.org/10.1007/978-3-319-63688-7_5"},"page":"133 - 163","date_published":"2017-01-01T00:00:00Z","scopus_import":1,"day":"01","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"637","title":"Be adaptive avoid overcommitting","status":"public","intvolume":" 10401","oa_version":"Submitted Version","type":"conference","alternative_title":["LNCS"],"abstract":[{"lang":"eng","text":"For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption (Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b). Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework that connects all of these works and allows us to present them in a unified and simplified fashion. Moreover, we use the framework to derive a new result for adaptively secure secret sharing over access structures defined via monotone circuits. We envision that further applications will follow in the future. Underlying our framework is the following simple idea. It is well known that selective security, where the adversary commits to n-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to 2n. However, in some cases the proof of selective security proceeds via a sequence of hybrids, where each pair of adjacent hybrids locally only requires some smaller partial information consisting of m ≪ n bits. The partial information needed might be completely different between different pairs of hybrids, and if we look across all the hybrids we might rely on the entire n-bit commitment. Nevertheless, the above is sufficient to prove adaptive security, at the cost of amplifying the adversary’s advantage by a factor of only 2m ≪ 2n. In all of our examples using the above framework, the different hybrids are captured by some sort of a graph pebbling game and the amount of information that the adversary needs to commit to in each pair of hybrids is bounded by the maximum number of pebbles in play at any point in time. Therefore, coming up with better strategies for proving adaptive security translates to various pebbling strategies for different types of graphs."}]},{"article_processing_charge":"No","month":"12","day":"29","citation":{"chicago":"Etheridge, Alison, and Nicholas H Barton. “Data for: Establishment in a New Habitat by Polygenic Adaptation.” Mendeley Data, 2017. https://doi.org/10.17632/nw68fxzjpm.1.","mla":"Etheridge, Alison, and Nicholas H. Barton. Data for: Establishment in a New Habitat by Polygenic Adaptation. Mendeley Data, 2017, doi:10.17632/nw68fxzjpm.1.","short":"A. Etheridge, N.H. Barton, (2017).","ista":"Etheridge A, Barton NH. 2017. Data for: Establishment in a new habitat by polygenic adaptation, Mendeley Data, 10.17632/nw68fxzjpm.1.","apa":"Etheridge, A., & Barton, N. H. (2017). Data for: Establishment in a new habitat by polygenic adaptation. Mendeley Data. https://doi.org/10.17632/nw68fxzjpm.1","ieee":"A. Etheridge and N. H. Barton, “Data for: Establishment in a new habitat by polygenic adaptation.” Mendeley Data, 2017.","ama":"Etheridge A, Barton NH. Data for: Establishment in a new habitat by polygenic adaptation. 2017. doi:10.17632/nw68fxzjpm.1"},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.17632/nw68fxzjpm.1"}],"oa":1,"doi":"10.17632/nw68fxzjpm.1","date_published":"2017-12-29T00:00:00Z","type":"research_data_reference","abstract":[{"text":"Mathematica notebooks used to generate figures.","lang":"eng"}],"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","_id":"9842","year":"2017","department":[{"_id":"NiBa"}],"publisher":"Mendeley Data","title":"Data for: Establishment in a new habitat by polygenic adaptation","status":"public","related_material":{"record":[{"relation":"used_in_publication","status":"public","id":"564"}]},"author":[{"full_name":"Etheridge, Alison","last_name":"Etheridge","first_name":"Alison"},{"full_name":"Barton, Nicholas H","last_name":"Barton","first_name":"Nicholas H","orcid":"0000-0002-8548-5240","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"}],"oa_version":"Published Version","date_created":"2021-08-09T13:18:55Z","date_updated":"2023-09-11T13:41:21Z"},{"title":"Biology of restriction-modification systems at the single-cell and population level","ddc":["576","579"],"status":"public","_id":"202","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","file":[{"file_id":"4710","relation":"main_file","checksum":"33cfb59674e91f82e3738396d3fb3776","date_created":"2018-12-12T10:08:48Z","date_updated":"2020-07-14T12:45:24Z","access_level":"open_access","file_name":"IST-2018-916-v1+3_2017_Pleska_Maros_Thesis.pdf","creator":"system","content_type":"application/pdf","file_size":18569590},{"date_created":"2019-04-05T08:33:14Z","date_updated":"2020-07-14T12:45:24Z","checksum":"dcc239968decb233e7f98cf1083d8c26","relation":"source_file","file_id":"6204","file_size":2801649,"content_type":"application/vnd.openxmlformats-officedocument.wordprocessingml.document","creator":"dernst","file_name":"2017_Pleska_Maros_Thesis.docx","access_level":"closed"}],"oa_version":"Published Version","pubrep_id":"916","alternative_title":["ISTA Thesis"],"type":"dissertation","abstract":[{"text":"Restriction-modification (RM) represents the simplest and possibly the most widespread mechanism of self/non-self discrimination in nature. In order to provide bacteria with immunity against bacteriophages and other parasitic genetic elements, RM systems rely on a balance between two enzymes: the restriction enzyme, which cleaves non-self DNA at specific restriction sites, and the modification enzyme, which tags the host’s DNA as self and thus protects it from cleavage. In this thesis, I use population and single-cell level experiments in combination with mathematical modeling to study different aspects of the interplay between RM systems, bacteria and bacteriophages. First, I analyze how mutations in phage restriction sites affect the probability of phage escape – an inherently stochastic process, during which phages accidently get modified instead of restricted. Next, I use single-cell experiments to show that RM systems can, with a low probability, attack the genome of their bacterial host and that this primitive form of autoimmunity leads to a tradeoff between the evolutionary cost and benefit of RM systems. Finally, I investigate the nature of interactions between bacteria, RM systems and temperate bacteriophages to find that, as a consequence of phage escape and its impact on population dynamics, RM systems can promote acquisition of symbiotic bacteriophages, rather than limit it. The results presented here uncover new fundamental biological properties of RM systems and highlight their importance in the ecology and evolution of bacteria, bacteriophages and their interactions.","lang":"eng"}],"page":"126","citation":{"chicago":"Pleska, Maros. “Biology of Restriction-Modification Systems at the Single-Cell and Population Level.” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_916.","mla":"Pleska, Maros. Biology of Restriction-Modification Systems at the Single-Cell and Population Level. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_916.","short":"M. Pleska, Biology of Restriction-Modification Systems at the Single-Cell and Population Level, Institute of Science and Technology Austria, 2017.","ista":"Pleska M. 2017. Biology of restriction-modification systems at the single-cell and population level. Institute of Science and Technology Austria.","ieee":"M. Pleska, “Biology of restriction-modification systems at the single-cell and population level,” Institute of Science and Technology Austria, 2017.","apa":"Pleska, M. (2017). Biology of restriction-modification systems at the single-cell and population level. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_916","ama":"Pleska M. Biology of restriction-modification systems at the single-cell and population level. 2017. doi:10.15479/AT:ISTA:th_916"},"date_published":"2017-10-01T00:00:00Z","article_processing_charge":"No","has_accepted_license":"1","day":"01","department":[{"_id":"CaGu"}],"publisher":"Institute of Science and Technology Austria","publication_status":"published","acknowledgement":"During my PhD studies, I received help from many people, all of which unfortunately cannot be listed here. I thank them deeply and hope that I never made them regret their kindness.\r\nI would like to express my deepest gratitude to Călin Guet, who went far beyond his responsibilities as an advisor and was to me also a great mentor and a friend. Călin never questioned my potential or lacked compassion and I cannot thank him enough for cultivating in me an independent scientist. I was amazed by his ability to recognize the most fascinating scientific problems in objects of study that others would find mundane. I hope I adopted at least a fraction of this ability.\r\nI will be forever grateful to Bruce Levin for all his support and especially for giving me the best possible example of how one can practice excellent science with humor and style. Working with Bruce was a true privilege.\r\nI thank Jonathan Bollback and Gašper Tkačik for serving in my PhD committee and the Austrian Academy of Science for funding my PhD research via the DOC fellowship.\r\nI thank all our lab members: Tobias Bergmiller for his guidance, especially in the first years of my research, and for being a good friend throughout; Remy Chait for staying in the lab at unreasonable hours and for the good laughs at bad jokes we shared; Anna Staron for supportively listening to my whines whenever I had to run a gel; Magdalena Steinrück for her pioneering work in the lab; Kathrin Tomasek for keeping the entropic forces in check and for her FACS virtuosity; Isabella Tomanek for always being nice to me, no matter how much bench space I took from her.\r\nI thank all my collaborators: Reiko Okura and Yuichi Wakamoto for performing and analyzing the microfluidic experiments; Long Qian and Edo Kussell for their bioinformatics analysis; Dominik Refardt for the λ kan phage; Moritz for his help with the mathematical modeling. I thank Fabienne Jesse for her tireless editorial work on all our manuscripts.\r\nFinally, I would like to thank my family and especially my wife Edita, who sacrificed a lot so that I can pursue my goals and dreams.\r\n","year":"2017","date_created":"2018-12-11T11:45:10Z","date_updated":"2023-09-15T12:04:56Z","related_material":{"record":[{"relation":"part_of_dissertation","status":"public","id":"1243"},{"status":"public","relation":"part_of_dissertation","id":"561"},{"status":"public","relation":"part_of_dissertation","id":"457"}]},"author":[{"orcid":"0000-0001-7460-7479","id":"4569785E-F248-11E8-B48F-1D18A9856A87","last_name":"Pleska","first_name":"Maros","full_name":"Pleska, Maros"}],"publist_id":"7711","file_date_updated":"2020-07-14T12:45:24Z","project":[{"name":"Effects of Stochasticity on the Function of Restriction-Modi cation Systems at the Single-Cell Level (DOC Fellowship)","_id":"251D65D8-B435-11E9-9278-68D0E5697425","grant_number":"24210"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"language":[{"iso":"eng"}],"supervisor":[{"full_name":"Guet, Calin C","orcid":"0000-0001-6220-2052","id":"47F8433E-F248-11E8-B48F-1D18A9856A87","last_name":"Guet","first_name":"Calin C"}],"degree_awarded":"PhD","doi":"10.15479/AT:ISTA:th_916","publication_identifier":{"issn":["2663-337X"]},"month":"10"},{"file_date_updated":"2020-07-14T12:47:26Z","related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"718"},{"id":"5678","relation":"part_of_dissertation","status":"public"},{"relation":"part_of_dissertation","status":"public","id":"87"}]},"author":[{"last_name":"Nikitenko","first_name":"Anton","orcid":"0000-0002-0659-3201","id":"3E4FF1BA-F248-11E8-B48F-1D18A9856A87","full_name":"Nikitenko, Anton"}],"date_created":"2019-04-09T15:04:32Z","date_updated":"2023-09-15T12:10:34Z","year":"2017","department":[{"_id":"HeEd"}],"publisher":"Institute of Science and Technology Austria","publication_status":"published","publication_identifier":{"issn":["2663-337X"]},"month":"10","doi":"10.15479/AT:ISTA:th_873","language":[{"iso":"eng"}],"degree_awarded":"PhD","supervisor":[{"full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"abstract":[{"lang":"eng","text":"The main objects considered in the present work are simplicial and CW-complexes with vertices forming a random point cloud. In particular, we consider a Poisson point process in R^n and study Delaunay and Voronoi complexes of the first and higher orders and weighted Delaunay complexes obtained as sections of Delaunay complexes, as well as the Čech complex. Further, we examine theDelaunay complex of a Poisson point process on the sphere S^n, as well as of a uniform point cloud, which is equivalent to the convex hull, providing a connection to the theory of random polytopes. Each of the complexes in question can be endowed with a radius function, which maps its cells to the radii of appropriately chosen circumspheres, called the radius of the cell. Applying and developing discrete Morse theory for these functions, joining it together with probabilistic and sometimes analytic machinery, and developing several integral geometric tools, we aim at getting the distributions of circumradii of typical cells. For all considered complexes, we are able to generalize and obtain up to constants the distribution of radii of typical intervals of all types. In low dimensions the constants can be computed explicitly, thus providing the explicit expressions for the expected numbers of cells. In particular, it allows to find the expected density of simplices of every dimension for a Poisson point process in R^4, whereas the result for R^3 was known already in 1970's."}],"type":"dissertation","alternative_title":["ISTA Thesis"],"pubrep_id":"873","file":[{"file_id":"6289","relation":"main_file","checksum":"ece7e598a2f060b263c2febf7f3fe7f9","date_created":"2019-04-09T14:54:51Z","date_updated":"2020-07-14T12:47:26Z","access_level":"open_access","file_name":"2017_Thesis_Nikitenko.pdf","creator":"dernst","content_type":"application/pdf","file_size":2324870},{"date_updated":"2020-07-14T12:47:26Z","date_created":"2019-04-09T14:54:51Z","checksum":"99b7ad76e317efd447af60f91e29b49b","file_id":"6290","relation":"source_file","creator":"dernst","content_type":"application/zip","file_size":2863219,"file_name":"2017_Thesis_Nikitenko_source.zip","access_level":"closed"}],"oa_version":"Published Version","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"6287","ddc":["514","516","519"],"status":"public","title":"Discrete Morse theory for random complexes ","article_processing_charge":"No","has_accepted_license":"1","day":"27","date_published":"2017-10-27T00:00:00Z","citation":{"chicago":"Nikitenko, Anton. “Discrete Morse Theory for Random Complexes .” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_873.","short":"A. Nikitenko, Discrete Morse Theory for Random Complexes , Institute of Science and Technology Austria, 2017.","mla":"Nikitenko, Anton. Discrete Morse Theory for Random Complexes . Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_873.","ieee":"A. Nikitenko, “Discrete Morse theory for random complexes ,” Institute of Science and Technology Austria, 2017.","apa":"Nikitenko, A. (2017). Discrete Morse theory for random complexes . Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_873","ista":"Nikitenko A. 2017. Discrete Morse theory for random complexes . Institute of Science and Technology Austria.","ama":"Nikitenko A. Discrete Morse theory for random complexes . 2017. doi:10.15479/AT:ISTA:th_873"},"page":"86"}]