[{"publisher":"Springer","language":[{"iso":"eng"}],"article_processing_charge":"No","has_accepted_license":"1","date_published":"2016-02-02T00:00:00Z","author":[{"full_name":"Abusalah, Hamza M","first_name":"Hamza M","id":"40297222-F248-11E8-B48F-1D18A9856A87","last_name":"Abusalah"},{"full_name":"Fuchsbauer, Georg","first_name":"Georg","id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","last_name":"Fuchsbauer"},{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"}],"page":"413 - 428","conference":{"name":"CT-RSA: Topics in Cryptology","start_date":"2016-02-29","end_date":"2016-03-04","location":"San Francisco, CA, USA"},"project":[{"call_identifier":"FP7","name":"Provable Security for Physical Cryptography","_id":"258C570E-B435-11E9-9278-68D0E5697425","grant_number":"259668"}],"alternative_title":["LNCS"],"scopus_import":"1","_id":"1236","file_date_updated":"2020-07-14T12:44:41Z","ddc":["005","600"],"date_created":"2018-12-11T11:50:52Z","acknowledgement":"Supported by the European Research Council, ERC Starting Grant (259668-PSPC).","isi":1,"volume":9610,"oa":1,"publist_id":"6097","date_updated":"2026-04-08T14:10:21Z","pubrep_id":"764","intvolume":"      9610","file":[{"date_updated":"2020-07-14T12:44:41Z","file_name":"IST-2017-764-v1+1_279.pdf","access_level":"open_access","content_type":"application/pdf","date_created":"2018-12-12T10:08:05Z","creator":"system","file_size":495176,"relation":"main_file","file_id":"4664","checksum":"3851cee49933ae13b1272e516f213e13"}],"external_id":{"isi":["000374102500024"]},"title":"Constrained PRFs for unbounded inputs","status":"public","department":[{"_id":"KrPi"}],"ec_funded":1,"citation":{"ista":"Abusalah HM, Fuchsbauer G, Pietrzak KZ. 2016. Constrained PRFs for unbounded inputs. CT-RSA: Topics in Cryptology, LNCS, vol. 9610, 413–428.","ama":"Abusalah HM, Fuchsbauer G, Pietrzak KZ. Constrained PRFs for unbounded inputs. In: Vol 9610. Springer; 2016:413-428. doi:<a href=\"https://doi.org/10.1007/978-3-319-29485-8_24\">10.1007/978-3-319-29485-8_24</a>","ieee":"H. M. Abusalah, G. Fuchsbauer, and K. Z. Pietrzak, “Constrained PRFs for unbounded inputs,” presented at the CT-RSA: Topics in Cryptology, San Francisco, CA, USA, 2016, vol. 9610, pp. 413–428.","short":"H.M. Abusalah, G. Fuchsbauer, K.Z. Pietrzak, in:, Springer, 2016, pp. 413–428.","mla":"Abusalah, Hamza M., et al. <i>Constrained PRFs for Unbounded Inputs</i>. Vol. 9610, Springer, 2016, pp. 413–28, doi:<a href=\"https://doi.org/10.1007/978-3-319-29485-8_24\">10.1007/978-3-319-29485-8_24</a>.","chicago":"Abusalah, Hamza M, Georg Fuchsbauer, and Krzysztof Z Pietrzak. “Constrained PRFs for Unbounded Inputs,” 9610:413–28. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-29485-8_24\">https://doi.org/10.1007/978-3-319-29485-8_24</a>.","apa":"Abusalah, H. M., Fuchsbauer, G., &#38; Pietrzak, K. Z. (2016). Constrained PRFs for unbounded inputs (Vol. 9610, pp. 413–428). Presented at the CT-RSA: Topics in Cryptology, San Francisco, CA, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-319-29485-8_24\">https://doi.org/10.1007/978-3-319-29485-8_24</a>"},"doi":"10.1007/978-3-319-29485-8_24","oa_version":"Submitted Version","publication_status":"published","month":"02","year":"2016","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","abstract":[{"text":"A constrained pseudorandom function F: K × X → Y for a family T ⊆ 2X of subsets of X is a function where for any key k ∈ K and set S ∈ T one can efficiently compute a constrained key kS which allows to evaluate F (k, ·) on all inputs x ∈ S, while even given this key, the outputs on all inputs x ∉ S look random. At Asiacrypt’13 Boneh and Waters gave a construction which supports the most general set family so far. Its keys kc are defined for sets decided by boolean circuits C and enable evaluation of the PRF on any x ∈ X where C(x) = 1. In their construction the PRF input length and the size of the circuits C for which constrained keys can be computed must be fixed beforehand during key generation. We construct a constrained PRF that has an unbounded input length and whose constrained keys can be defined for any set recognized by a Turing machine. The only a priori bound we make is on the description size of the machines. We prove our construction secure assuming publiccoin differing-input obfuscation. As applications of our constrained PRF we build a broadcast encryption scheme where the number of potential receivers need not be fixed at setup (in particular, the length of the keys is independent of the number of parties) and the first identity-based non-interactive key exchange protocol with no bound on the number of parties that can agree on a shared key.","lang":"eng"}],"related_material":{"record":[{"relation":"dissertation_contains","id":"83","status":"public"}]},"type":"conference","day":"02","quality_controlled":"1"},{"oa_version":"Submitted Version","related_material":{"record":[{"status":"public","id":"83","relation":"dissertation_contains"}]},"abstract":[{"lang":"eng","text":"A constrained pseudorandom function (CPRF) F: K×X → Y for a family T of subsets of χ is a function where for any key k ∈ K and set S ∈ T one can efficiently compute a short constrained key kS, which allows to evaluate F(k, ·) on all inputs x ∈ S, while the outputs on all inputs x /∈ S look random even given kS. Abusalah et al. recently constructed the first constrained PRF for inputs of arbitrary length whose sets S are decided by Turing machines. They use their CPRF to build broadcast encryption and the first ID-based non-interactive key exchange for an unbounded number of users. Their constrained keys are obfuscated circuits and are therefore large. In this work we drastically reduce the key size and define a constrained key for a Turing machine M as a short signature on M. For this, we introduce a new signature primitive with constrained signing keys that let one only sign certain messages, while forging a signature on others is hard even when knowing the coins for key generation."}],"type":"conference","day":"01","quality_controlled":"1","publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","month":"01","year":"2016","intvolume":"      9696","oa":1,"volume":9696,"publist_id":"6098","date_updated":"2026-04-08T14:10:21Z","ec_funded":1,"doi":"10.1007/978-3-319-39555-5_24","citation":{"mla":"Abusalah, Hamza M., and Georg Fuchsbauer. <i>Constrained PRFs for Unbounded Inputs with Short Keys</i>. Vol. 9696, Springer, 2016, pp. 445–63, doi:<a href=\"https://doi.org/10.1007/978-3-319-39555-5_24\">10.1007/978-3-319-39555-5_24</a>.","chicago":"Abusalah, Hamza M, and Georg Fuchsbauer. “Constrained PRFs for Unbounded Inputs with Short Keys,” 9696:445–63. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-39555-5_24\">https://doi.org/10.1007/978-3-319-39555-5_24</a>.","apa":"Abusalah, H. M., &#38; Fuchsbauer, G. (2016). Constrained PRFs for unbounded inputs with short keys (Vol. 9696, pp. 445–463). Presented at the ACNS: Applied Cryptography and Network Security, Guildford, UK: Springer. <a href=\"https://doi.org/10.1007/978-3-319-39555-5_24\">https://doi.org/10.1007/978-3-319-39555-5_24</a>","ieee":"H. M. Abusalah and G. Fuchsbauer, “Constrained PRFs for unbounded inputs with short keys,” presented at the ACNS: Applied Cryptography and Network Security, Guildford, UK, 2016, vol. 9696, pp. 445–463.","short":"H.M. Abusalah, G. Fuchsbauer, in:, Springer, 2016, pp. 445–463.","ista":"Abusalah HM, Fuchsbauer G. 2016. Constrained PRFs for unbounded inputs with short keys. ACNS: Applied Cryptography and Network Security, LNCS, vol. 9696, 445–463.","ama":"Abusalah HM, Fuchsbauer G. Constrained PRFs for unbounded inputs with short keys. In: Vol 9696. Springer; 2016:445-463. doi:<a href=\"https://doi.org/10.1007/978-3-319-39555-5_24\">10.1007/978-3-319-39555-5_24</a>"},"external_id":{"isi":["000386324500024"]},"title":"Constrained PRFs for unbounded inputs with short keys","status":"public","department":[{"_id":"KrPi"}],"date_created":"2018-12-11T11:50:52Z","acknowledgement":"H. Abusalah—Research supported by the European Research Council, ERC starting grant (259668-PSPC) and ERC consolidator grant (682815 - TOCNeT).","isi":1,"main_file_link":[{"url":"https://eprint.iacr.org/2016/279.pdf","open_access":"1"}],"date_published":"2016-01-01T00:00:00Z","author":[{"full_name":"Abusalah, Hamza M","first_name":"Hamza M","id":"40297222-F248-11E8-B48F-1D18A9856A87","last_name":"Abusalah"},{"last_name":"Fuchsbauer","id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","first_name":"Georg","full_name":"Fuchsbauer, Georg"}],"conference":{"name":"ACNS: Applied Cryptography and Network Security","start_date":"2016-06-19","end_date":"2016-06-22","location":"Guildford, UK"},"page":"445 - 463","publisher":"Springer","article_processing_charge":"No","language":[{"iso":"eng"}],"_id":"1235","project":[{"name":"Provable Security for Physical Cryptography","call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425","grant_number":"259668"},{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","grant_number":"682815"}],"alternative_title":["LNCS"],"scopus_import":"1"},{"article_processing_charge":"No","language":[{"iso":"eng"}],"publisher":"Wiley","has_accepted_license":"1","page":"6339 - 6342","author":[{"last_name":"Gschaider-Reichhart","orcid":"0000-0002-7218-7738","id":"3FEE232A-F248-11E8-B48F-1D18A9856A87","first_name":"Eva","full_name":"Gschaider-Reichhart, Eva"},{"orcid":"0000-0002-5409-8571","last_name":"Inglés Prieto","id":"2A9DB292-F248-11E8-B48F-1D18A9856A87","first_name":"Álvaro","full_name":"Inglés Prieto, Álvaro"},{"full_name":"Tichy, Alexandra-Madelaine","first_name":"Alexandra-Madelaine","id":"29D8BB2C-F248-11E8-B48F-1D18A9856A87","last_name":"Tichy"},{"id":"3EEDE19A-F248-11E8-B48F-1D18A9856A87","last_name":"Mckenzie","full_name":"Mckenzie, Catherine","first_name":"Catherine"},{"first_name":"Harald L","full_name":"Janovjak, Harald L","last_name":"Janovjak","orcid":"0000-0002-8023-9315","id":"33BA6C30-F248-11E8-B48F-1D18A9856A87"}],"date_published":"2016-05-17T00:00:00Z","project":[{"grant_number":"303564","call_identifier":"FP7","name":"Microbial Ion Channels for Synthetic Neurobiology","_id":"25548C20-B435-11E9-9278-68D0E5697425"},{"_id":"255A6082-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Molecular Drug Targets","grant_number":"W1232-B24"}],"scopus_import":"1","_id":"1441","issue":"21","file_date_updated":"2020-07-14T12:44:55Z","date_created":"2018-12-11T11:52:02Z","ddc":["571","576"],"acknowledgement":"A.I.-P. was supported by a Ramon Areces fellowship, and E.R. by the graduate program MolecularDrugTargets (Austrian Science Fund (FWF): W1232) and a FemTech fellowship (Austrian Research Promotion Agency: 3580812).","isi":1,"pubrep_id":"840","date_updated":"2026-04-08T14:11:53Z","oa":1,"volume":55,"publist_id":"5755","file":[{"date_updated":"2020-07-14T12:44:55Z","file_name":"IST-2017-840-v1+1_reichhart.pdf","date_created":"2018-12-12T10:17:03Z","content_type":"application/pdf","access_level":"open_access","creator":"system","file_size":1268662,"relation":"main_file","file_id":"5255","checksum":"26da07960e57ac4750b54179197ce57f"}],"intvolume":"        55","status":"public","title":"A phytochrome sensory domain permits receptor activation by red light","external_id":{"isi":["000377918400039"]},"department":[{"_id":"HaJa"}],"doi":"10.1002/anie.201601736","citation":{"short":"E. Gschaider-Reichhart, Á. Inglés Prieto, A.-M. Tichy, C. Mckenzie, H.L. Janovjak, Angewandte Chemie - International Edition 55 (2016) 6339–6342.","ieee":"E. Gschaider-Reichhart, Á. Inglés Prieto, A.-M. Tichy, C. Mckenzie, and H. L. Janovjak, “A phytochrome sensory domain permits receptor activation by red light,” <i>Angewandte Chemie - International Edition</i>, vol. 55, no. 21. Wiley, pp. 6339–6342, 2016.","ama":"Gschaider-Reichhart E, Inglés Prieto Á, Tichy A-M, Mckenzie C, Janovjak HL. A phytochrome sensory domain permits receptor activation by red light. <i>Angewandte Chemie - International Edition</i>. 2016;55(21):6339-6342. doi:<a href=\"https://doi.org/10.1002/anie.201601736\">10.1002/anie.201601736</a>","ista":"Gschaider-Reichhart E, Inglés Prieto Á, Tichy A-M, Mckenzie C, Janovjak HL. 2016. A phytochrome sensory domain permits receptor activation by red light. Angewandte Chemie - International Edition. 55(21), 6339–6342.","apa":"Gschaider-Reichhart, E., Inglés Prieto, Á., Tichy, A.-M., Mckenzie, C., &#38; Janovjak, H. L. (2016). A phytochrome sensory domain permits receptor activation by red light. <i>Angewandte Chemie - International Edition</i>. Wiley. <a href=\"https://doi.org/10.1002/anie.201601736\">https://doi.org/10.1002/anie.201601736</a>","mla":"Gschaider-Reichhart, Eva, et al. “A Phytochrome Sensory Domain Permits Receptor Activation by Red Light.” <i>Angewandte Chemie - International Edition</i>, vol. 55, no. 21, Wiley, 2016, pp. 6339–42, doi:<a href=\"https://doi.org/10.1002/anie.201601736\">10.1002/anie.201601736</a>.","chicago":"Gschaider-Reichhart, Eva, Álvaro Inglés Prieto, Alexandra-Madelaine Tichy, Catherine Mckenzie, and Harald L Janovjak. “A Phytochrome Sensory Domain Permits Receptor Activation by Red Light.” <i>Angewandte Chemie - International Edition</i>. Wiley, 2016. <a href=\"https://doi.org/10.1002/anie.201601736\">https://doi.org/10.1002/anie.201601736</a>."},"ec_funded":1,"publication":"Angewandte Chemie - International Edition","oa_version":"Submitted Version","year":"2016","month":"05","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication_status":"published","type":"journal_article","related_material":{"record":[{"relation":"dissertation_contains","id":"418","status":"public"}]},"abstract":[{"text":"Optogenetics and photopharmacology enable the spatio-temporal control of cell and animal behavior by light. Although red light offers deep-tissue penetration and minimal phototoxicity, very few red-light-sensitive optogenetic methods are currently available. We have now developed a red-light-induced homodimerization domain. We first showed that an optimized sensory domain of the cyanobacterial phytochrome 1 can be expressed robustly and without cytotoxicity in human cells. We then applied this domain to induce the dimerization of two receptor tyrosine kinases—the fibroblast growth factor receptor 1 and the neurotrophin receptor trkB. This new optogenetic method was then used to activate the MAPK/ERK pathway non-invasively in mammalian tissue and in multicolor cell-signaling experiments. The light-controlled dimerizer and red-light-activated receptor tyrosine kinases will prove useful to regulate a variety of cellular processes with light. Go deep with red: The sensory domain (S) of the cyanobacterial phytochrome 1 (CPH1) was repurposed to induce the homodimerization of proteins in living cells by red light. By using this domain, light-activated protein kinases were engineered that can be activated orthogonally from many fluorescent proteins and through mammalian tissue. Pr/Pfr=red-/far-red-absorbing state of CPH1.","lang":"eng"}],"quality_controlled":"1","corr_author":"1","day":"17"},{"file_date_updated":"2020-07-14T12:44:46Z","date_created":"2018-12-11T11:51:35Z","ddc":["000"],"issue":"4","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"isi":1,"author":[{"full_name":"Hahn, David","first_name":"David","id":"357A6A66-F248-11E8-B48F-1D18A9856A87","last_name":"Hahn"},{"id":"3C61F1D2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6646-5546","last_name":"Wojtan","full_name":"Wojtan, Christopher J","first_name":"Christopher J"}],"conference":{"end_date":"2016-07-28","start_date":"2016-07-24","location":"Anaheim, CA, USA","name":"ACM SIGGRAPH"},"date_published":"2016-07-01T00:00:00Z","language":[{"iso":"eng"}],"article_processing_charge":"No","publisher":"ACM","has_accepted_license":"1","_id":"1362","article_number":"104","project":[{"grant_number":"638176","_id":"2533E772-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Big Splash: Efficient Simulation of Natural Phenomena at Extremely Large Scales"}],"alternative_title":["ACM Transactions on Graphics"],"scopus_import":"1","oa_version":"Published Version","type":"conference","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"839"}]},"abstract":[{"lang":"eng","text":"We present a boundary element based method for fast simulation of brittle fracture. By introducing simplifying assumptions that allow us to quickly estimate stress intensities and opening displacements during crack propagation, we build a fracture algorithm where the cost of each time step scales linearly with the length of the crackfront. The transition from a full boundary element method to our faster variant is possible at the beginning of any time step. This allows us to build a hybrid method, which uses the expensive but more accurate BEM while the number of degrees of freedom is low, and uses the fast method once that number exceeds a given threshold as the crack geometry becomes more complicated. Furthermore, we integrate this fracture simulation with a standard rigid-body solver. Our rigid-body coupling solves a Neumann boundary value problem by carefully separating translational, rotational and deformational components of the collision forces and then applying a Tikhonov regularizer to the resulting linear system. We show that our method produces physically reasonable results in standard test cases and is capable of dealing with complex scenes faster than previous finite- or boundary element approaches."}],"quality_controlled":"1","corr_author":"1","day":"01","year":"2016","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","month":"07","publication_status":"published","intvolume":"        35","file":[{"creator":"system","file_size":12453704,"access_level":"open_access","content_type":"application/pdf","date_created":"2018-12-12T10:15:04Z","date_updated":"2020-07-14T12:44:46Z","file_name":"IST-2016-632-v1+2_a104-hahn.pdf","file_id":"5121","checksum":"943712d9c9dc8bb5048d4adc561d7d38","relation":"main_file"}],"license":"https://creativecommons.org/licenses/by/4.0/","pubrep_id":"632","date_updated":"2026-04-08T14:20:15Z","volume":35,"oa":1,"publist_id":"5880","doi":"10.1145/2897824.2925902","citation":{"mla":"Hahn, David, and Chris Wojtan. <i>Fast Approximations for Boundary Element Based Brittle Fracture Simulation</i>. Vol. 35, no. 4, 104, ACM, 2016, doi:<a href=\"https://doi.org/10.1145/2897824.2925902\">10.1145/2897824.2925902</a>.","chicago":"Hahn, David, and Chris Wojtan. “Fast Approximations for Boundary Element Based Brittle Fracture Simulation,” Vol. 35. ACM, 2016. <a href=\"https://doi.org/10.1145/2897824.2925902\">https://doi.org/10.1145/2897824.2925902</a>.","apa":"Hahn, D., &#38; Wojtan, C. (2016). Fast approximations for boundary element based brittle fracture simulation (Vol. 35). Presented at the ACM SIGGRAPH, Anaheim, CA, USA: ACM. <a href=\"https://doi.org/10.1145/2897824.2925902\">https://doi.org/10.1145/2897824.2925902</a>","ieee":"D. Hahn and C. Wojtan, “Fast approximations for boundary element based brittle fracture simulation,” presented at the ACM SIGGRAPH, Anaheim, CA, USA, 2016, vol. 35, no. 4.","short":"D. Hahn, C. Wojtan, in:, ACM, 2016.","ista":"Hahn D, Wojtan C. 2016. Fast approximations for boundary element based brittle fracture simulation. ACM SIGGRAPH, ACM Transactions on Graphics, vol. 35, 104.","ama":"Hahn D, Wojtan C. Fast approximations for boundary element based brittle fracture simulation. In: Vol 35. ACM; 2016. doi:<a href=\"https://doi.org/10.1145/2897824.2925902\">10.1145/2897824.2925902</a>"},"ec_funded":1,"status":"public","external_id":{"isi":["000380112400074"]},"title":"Fast approximations for boundary element based brittle fracture simulation","department":[{"_id":"ChWo"}]},{"intvolume":"        26","date_updated":"2026-04-08T14:19:43Z","volume":26,"publist_id":"6087","doi":"10.1016/j.cub.2015.12.041","citation":{"short":"M. Pleska, L. Qian, R. Okura, T. Bergmiller, Y. Wakamoto, E. Kussell, C.C. Guet, Current Biology 26 (2016) 404–409.","ieee":"M. Pleska <i>et al.</i>, “Bacterial autoimmunity due to a restriction-modification system,” <i>Current Biology</i>, vol. 26, no. 3. Cell Press, pp. 404–409, 2016.","ama":"Pleska M, Qian L, Okura R, et al. Bacterial autoimmunity due to a restriction-modification system. <i>Current Biology</i>. 2016;26(3):404-409. doi:<a href=\"https://doi.org/10.1016/j.cub.2015.12.041\">10.1016/j.cub.2015.12.041</a>","ista":"Pleska M, Qian L, Okura R, Bergmiller T, Wakamoto Y, Kussell E, Guet CC. 2016. Bacterial autoimmunity due to a restriction-modification system. Current Biology. 26(3), 404–409.","apa":"Pleska, M., Qian, L., Okura, R., Bergmiller, T., Wakamoto, Y., Kussell, E., &#38; Guet, C. C. (2016). Bacterial autoimmunity due to a restriction-modification system. <i>Current Biology</i>. Cell Press. <a href=\"https://doi.org/10.1016/j.cub.2015.12.041\">https://doi.org/10.1016/j.cub.2015.12.041</a>","chicago":"Pleska, Maros, Long Qian, Reiko Okura, Tobias Bergmiller, Yuichi Wakamoto, Edo Kussell, and Calin C Guet. “Bacterial Autoimmunity Due to a Restriction-Modification System.” <i>Current Biology</i>. Cell Press, 2016. <a href=\"https://doi.org/10.1016/j.cub.2015.12.041\">https://doi.org/10.1016/j.cub.2015.12.041</a>.","mla":"Pleska, Maros, et al. “Bacterial Autoimmunity Due to a Restriction-Modification System.” <i>Current Biology</i>, vol. 26, no. 3, Cell Press, 2016, pp. 404–09, doi:<a href=\"https://doi.org/10.1016/j.cub.2015.12.041\">10.1016/j.cub.2015.12.041</a>."},"publication":"Current Biology","department":[{"_id":"CaGu"}],"status":"public","title":"Bacterial autoimmunity due to a restriction-modification system","external_id":{"isi":["000369502900034"]},"oa_version":"None","quality_controlled":"1","day":"08","type":"journal_article","abstract":[{"lang":"eng","text":"Restriction-modification (RM) systems represent a minimal and ubiquitous biological system of self/non-self discrimination in prokaryotes [1], which protects hosts from exogenous DNA [2]. The mechanism is based on the balance between methyltransferase (M) and cognate restriction endonuclease (R). M tags endogenous DNA as self by methylating short specific DNA sequences called restriction sites, whereas R recognizes unmethylated restriction sites as non-self and introduces a double-stranded DNA break [3]. Restriction sites are significantly underrepresented in prokaryotic genomes [4-7], suggesting that the discrimination mechanism is imperfect and occasionally leads to autoimmunity due to self-DNA cleavage (self-restriction) [8]. Furthermore, RM systems can promote DNA recombination [9] and contribute to genetic variation in microbial populations, thus facilitating adaptive evolution [10]. However, cleavage of self-DNA by RM systems as elements shaping prokaryotic genomes has not been directly detected, and its cause, frequency, and outcome are unknown. We quantify self-restriction caused by two RM systems of Escherichia coli and find that, in agreement with levels of restriction site avoidance, EcoRI, but not EcoRV, cleaves self-DNA at a measurable rate. Self-restriction is a stochastic process, which temporarily induces the SOS response, and is followed by DNA repair, maintaining cell viability. We find that RM systems with higher restriction efficiency against bacteriophage infections exhibit a higher rate of self-restriction, and that this rate can be further increased by stochastic imbalance between R and M. Our results identify molecular noise in RM systems as a factor shaping prokaryotic genomes."}],"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"202"}]},"year":"2016","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","month":"02","publication_status":"published","author":[{"first_name":"Maros","full_name":"Pleska, Maros","orcid":"0000-0001-7460-7479","last_name":"Pleska","id":"4569785E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Qian, Long","first_name":"Long","last_name":"Qian"},{"last_name":"Okura","first_name":"Reiko","full_name":"Okura, Reiko"},{"full_name":"Bergmiller, Tobias","first_name":"Tobias","id":"2C471CFA-F248-11E8-B48F-1D18A9856A87","last_name":"Bergmiller","orcid":"0000-0001-5396-4346"},{"full_name":"Wakamoto, Yuichi","first_name":"Yuichi","last_name":"Wakamoto"},{"last_name":"Kussell","full_name":"Kussell, Edo","first_name":"Edo"},{"orcid":"0000-0001-6220-2052","last_name":"Guet","id":"47F8433E-F248-11E8-B48F-1D18A9856A87","first_name":"Calin C","full_name":"Guet, Calin C"}],"page":"404 - 409","date_published":"2016-02-08T00:00:00Z","article_processing_charge":"No","language":[{"iso":"eng"}],"publisher":"Cell Press","_id":"1243","scopus_import":"1","project":[{"grant_number":"24210","_id":"251D65D8-B435-11E9-9278-68D0E5697425","name":"Effects of Stochasticity on the Function of Restriction-Modi cation Systems at the Single-Cell Level"}],"date_created":"2018-12-11T11:50:54Z","issue":"3","isi":1,"acknowledgement":"This work was funded by an HFSP Young Investigators’ grant. M.P. is a recipient of a DOC Fellowship of the Austrian Academy of Science at the Institute of Science and Technology Austria. R.O. and Y.W. were supported by the Platform for Dynamic Approaches to Living System from MEXT, Japan. We wish to thank I. Kobayashi for providing us with the EcoRI and EcoRV plasmids, and A. Campbell for providing us with the λ vir phage. We thank D. Siekhaus and C. Uhler and members of the C.C.G. and J.P. Bollback laboratories for in-depth discussions. We thank B. Stern for comments on an earlier version of the manuscript. We especially thank B.R. Levin for advice and comments, and the anonymous reviewers for significantly improving the manuscript."},{"status":"public","title":"Linear distances between Markov chains","department":[{"_id":"ToHe"},{"_id":"KrCh"},{"_id":"CaGu"}],"citation":{"apa":"Daca, P., Henzinger, T. A., Kretinsky, J., &#38; Petrov, T. (2016). Linear distances between Markov chains (Vol. 59). Presented at the CONCUR: Concurrency Theory, Quebec City; Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2016.20\">https://doi.org/10.4230/LIPIcs.CONCUR.2016.20</a>","chicago":"Daca, Przemyslaw, Thomas A Henzinger, Jan Kretinsky, and Tatjana Petrov. “Linear Distances between Markov Chains,” Vol. 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2016.20\">https://doi.org/10.4230/LIPIcs.CONCUR.2016.20</a>.","mla":"Daca, Przemyslaw, et al. <i>Linear Distances between Markov Chains</i>. Vol. 59, 20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2016.20\">10.4230/LIPIcs.CONCUR.2016.20</a>.","ama":"Daca P, Henzinger TA, Kretinsky J, Petrov T. Linear distances between Markov chains. In: Vol 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2016.20\">10.4230/LIPIcs.CONCUR.2016.20</a>","ista":"Daca P, Henzinger TA, Kretinsky J, Petrov T. 2016. Linear distances between Markov chains. CONCUR: Concurrency Theory, LIPIcs, vol. 59, 20.","short":"P. Daca, T.A. Henzinger, J. Kretinsky, T. Petrov, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.","ieee":"P. Daca, T. A. Henzinger, J. Kretinsky, and T. Petrov, “Linear distances between Markov chains,” presented at the CONCUR: Concurrency Theory, Quebec City; Canada, 2016, vol. 59."},"doi":"10.4230/LIPIcs.CONCUR.2016.20","ec_funded":1,"pubrep_id":"794","date_updated":"2026-04-08T14:21:07Z","publist_id":"6283","volume":59,"oa":1,"intvolume":"        59","file":[{"relation":"main_file","file_id":"4895","file_name":"IST-2017-794-v1+1_LIPIcs-CONCUR-2016-20.pdf","date_updated":"2018-12-12T10:11:39Z","date_created":"2018-12-12T10:11:39Z","content_type":"application/pdf","access_level":"open_access","creator":"system","file_size":501827}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","year":"2016","month":"08","publication_status":"published","type":"conference","related_material":{"record":[{"relation":"dissertation_contains","id":"1155","status":"public"}]},"abstract":[{"lang":"eng","text":"We introduce a general class of distances (metrics) between Markov chains, which are based on linear behaviour. This class encompasses distances given topologically (such as the total variation distance or trace distance) as well as by temporal logics or automata. We investigate which of the distances can be approximated by observing the systems, i.e. by black-box testing or simulation, and we provide both negative and positive results. "}],"quality_controlled":"1","day":"01","oa_version":"Published Version","alternative_title":["LIPIcs"],"project":[{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","call_identifier":"FP7","grant_number":"267989"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23"},{"call_identifier":"FWF","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"}],"scopus_import":1,"_id":"1093","article_number":"20","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","has_accepted_license":"1","conference":{"name":"CONCUR: Concurrency Theory","start_date":"2016-08-23","end_date":"2016-08-26","location":"Quebec City; Canada"},"author":[{"id":"49351290-F248-11E8-B48F-1D18A9856A87","last_name":"Daca","full_name":"Daca, Przemyslaw","first_name":"Przemyslaw"},{"full_name":"Henzinger, Thomas A","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000−0002−2985−7724"},{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","last_name":"Kretinsky","orcid":"0000-0002-8122-2881","full_name":"Kretinsky, Jan","first_name":"Jan"},{"first_name":"Tatjana","full_name":"Petrov, Tatjana","last_name":"Petrov","orcid":"0000-0002-9041-0905","id":"3D5811FC-F248-11E8-B48F-1D18A9856A87"}],"date_published":"2016-08-01T00:00:00Z","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"acknowledgement":"This research was funded in part by the European Research Council (ERC) under grant agreement 267989\r\n(QUAREM), the Austrian Science Fund (FWF) under grants project S11402-N23 (RiSE and SHiNE)\r\nand Z211-N23 (Wittgenstein Award), by the Czech Science Foundation Grant No. P202/12/G061, and\r\nby the SNSF Advanced Postdoc. Mobility Fellowship – grant number P300P2_161067.","file_date_updated":"2018-12-12T10:11:39Z","date_created":"2018-12-11T11:50:06Z","ddc":["004"]},{"alternative_title":["LNCS"],"project":[{"grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Reactive Modeling"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"Formal methods for the design and analysis of complex systems","call_identifier":"FWF","grant_number":"Z211"},{"grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"scopus_import":"1","_id":"1234","publisher":"Springer","article_processing_charge":"No","language":[{"iso":"eng"}],"date_published":"2016-01-01T00:00:00Z","author":[{"full_name":"Daca, Przemyslaw","first_name":"Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87","last_name":"Daca"},{"first_name":"Thomas A","full_name":"Henzinger, Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","last_name":"Kretinsky","orcid":"0000-0002-8122-2881","full_name":"Kretinsky, Jan","first_name":"Jan"},{"id":"3D5811FC-F248-11E8-B48F-1D18A9856A87","last_name":"Petrov","orcid":"0000-0002-9041-0905","full_name":"Petrov, Tatjana","first_name":"Tatjana"}],"page":"112 - 129","conference":{"name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","location":"Eindhoven, The Netherlands","end_date":"2016-04-08","start_date":"2016-04-02"},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1504.05739"}],"acknowledgement":"This research was funded in part by the European Research Council (ERC) under\r\ngrant  agreement  267989  (QUAREM),  the  Austrian  Science  Fund  (FWF)  under\r\ngrants project S11402-N23 (RiSE) and Z211-N23 (Wittgenstein Award), the Peo-\r\nple Programme (Marie Curie Actions) of the European Union’s Seventh Framework\r\nProgramme (FP7/2007-2013) REA Grant No 291734, the SNSF Advanced Postdoc.\r\nMobility Fellowship – grant number P300P2\r\n161067, and the Czech Science Foun-\r\ndation under grant agreement P202/12/G061.","isi":1,"date_created":"2018-12-11T11:50:51Z","external_id":{"arxiv":["1504.05739"],"isi":["000406428000007"]},"title":"Faster statistical model checking for unbounded temporal properties","status":"public","department":[{"_id":"ToHe"},{"_id":"CaGu"}],"ec_funded":1,"citation":{"chicago":"Daca, Przemyslaw, Thomas A Henzinger, Jan Kretinsky, and Tatjana Petrov. “Faster Statistical Model Checking for Unbounded Temporal Properties,” 9636:112–29. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-662-49674-9_7\">https://doi.org/10.1007/978-3-662-49674-9_7</a>.","mla":"Daca, Przemyslaw, et al. <i>Faster Statistical Model Checking for Unbounded Temporal Properties</i>. Vol. 9636, Springer, 2016, pp. 112–29, doi:<a href=\"https://doi.org/10.1007/978-3-662-49674-9_7\">10.1007/978-3-662-49674-9_7</a>.","apa":"Daca, P., Henzinger, T. A., Kretinsky, J., &#38; Petrov, T. (2016). Faster statistical model checking for unbounded temporal properties (Vol. 9636, pp. 112–129). Presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, Eindhoven, The Netherlands: Springer. <a href=\"https://doi.org/10.1007/978-3-662-49674-9_7\">https://doi.org/10.1007/978-3-662-49674-9_7</a>","ista":"Daca P, Henzinger TA, Kretinsky J, Petrov T. 2016. Faster statistical model checking for unbounded temporal properties. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 9636, 112–129.","ama":"Daca P, Henzinger TA, Kretinsky J, Petrov T. Faster statistical model checking for unbounded temporal properties. In: Vol 9636. Springer; 2016:112-129. doi:<a href=\"https://doi.org/10.1007/978-3-662-49674-9_7\">10.1007/978-3-662-49674-9_7</a>","ieee":"P. Daca, T. A. Henzinger, J. Kretinsky, and T. Petrov, “Faster statistical model checking for unbounded temporal properties,” presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, Eindhoven, The Netherlands, 2016, vol. 9636, pp. 112–129.","short":"P. Daca, T.A. Henzinger, J. Kretinsky, T. Petrov, in:, Springer, 2016, pp. 112–129."},"doi":"10.1007/978-3-662-49674-9_7","oa":1,"volume":9636,"publist_id":"6099","date_updated":"2026-04-08T14:21:07Z","intvolume":"      9636","publication_status":"published","month":"01","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","year":"2016","related_material":{"record":[{"relation":"later_version","id":"471","status":"public"},{"relation":"dissertation_contains","id":"1155","status":"public"}]},"abstract":[{"lang":"eng","text":"We present a new algorithm for the statistical model checking of Markov chains with respect to unbounded temporal properties, including full linear temporal logic. The main idea is that we monitor each simulation run on the fly, in order to detect quickly if a bottom strongly connected component is entered with high probability, in which case the simulation run can be terminated early. As a result, our simulation runs are often much shorter than required by termination bounds that are computed a priori for a desired level of confidence on a large state space. In comparison to previous algorithms for statistical model checking our method is not only faster in many cases but also requires less information about the system, namely, only the minimum transition probability that occurs in the Markov chain. In addition, our method can be generalised to unbounded quantitative properties such as mean-payoff bounds."}],"type":"conference","day":"01","quality_controlled":"1","oa_version":"Preprint","arxiv":1},{"publication_status":"published","month":"07","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","year":"2016","abstract":[{"text":"We present an extension to the quantifier-free theory of integer arrays which allows us to express counting. The properties expressible in Array Folds Logic (AFL) include statements such as &quot;the first array cell contains the array length,&quot; and &quot;the array contains equally many minimal and maximal elements.&quot; These properties cannot be expressed in quantified fragments of the theory of arrays, nor in the theory of concatenation. Using reduction to counter machines, we show that the satisfiability problem of AFL is PSPACE-complete, and with a natural restriction the complexity decreases to NP. We also show that adding either universal quantifiers or concatenation leads to undecidability.\r\nAFL contains terms that fold a function over an array. We demonstrate that folding, a well-known concept from functional languages, allows us to concisely summarize loops that count over arrays, which occurs frequently in real-life programs. We provide a tool that can discharge proof obligations in AFL, and we demonstrate on practical examples that our decision procedure can solve a broad range of problems in symbolic testing and program verification.","lang":"eng"}],"related_material":{"record":[{"status":"public","id":"1155","relation":"dissertation_contains"}]},"type":"conference","day":"13","corr_author":"1","quality_controlled":"1","oa_version":"Preprint","arxiv":1,"external_id":{"arxiv":["1603.06850"],"isi":["000387731400013"]},"title":"Array folds logic","status":"public","department":[{"_id":"ToHe"}],"ec_funded":1,"citation":{"short":"P. Daca, T.A. Henzinger, A. Kupriyanov, in:, Springer, 2016, pp. 230–248.","ieee":"P. Daca, T. A. Henzinger, and A. Kupriyanov, “Array folds logic,” presented at the CAV: Computer Aided Verification, Toronto, Canada, 2016, vol. 9780, pp. 230–248.","ama":"Daca P, Henzinger TA, Kupriyanov A. Array folds logic. In: Vol 9780. Springer; 2016:230-248. doi:<a href=\"https://doi.org/10.1007/978-3-319-41540-6_13\">10.1007/978-3-319-41540-6_13</a>","ista":"Daca P, Henzinger TA, Kupriyanov A. 2016. Array folds logic. CAV: Computer Aided Verification, LNCS, vol. 9780, 230–248.","apa":"Daca, P., Henzinger, T. A., &#38; Kupriyanov, A. (2016). Array folds logic (Vol. 9780, pp. 230–248). Presented at the CAV: Computer Aided Verification, Toronto, Canada: Springer. <a href=\"https://doi.org/10.1007/978-3-319-41540-6_13\">https://doi.org/10.1007/978-3-319-41540-6_13</a>","mla":"Daca, Przemyslaw, et al. <i>Array Folds Logic</i>. Vol. 9780, Springer, 2016, pp. 230–48, doi:<a href=\"https://doi.org/10.1007/978-3-319-41540-6_13\">10.1007/978-3-319-41540-6_13</a>.","chicago":"Daca, Przemyslaw, Thomas A Henzinger, and Andrey Kupriyanov. “Array Folds Logic,” 9780:230–48. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-41540-6_13\">https://doi.org/10.1007/978-3-319-41540-6_13</a>."},"doi":"10.1007/978-3-319-41540-6_13","publist_id":"5818","volume":9780,"oa":1,"date_updated":"2026-04-08T14:21:07Z","intvolume":"      9780","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1603.06850"}],"isi":1,"date_created":"2018-12-11T11:51:45Z","alternative_title":["LNCS"],"project":[{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Reactive Modeling","grant_number":"267989"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"name":"Formal methods for the design and analysis of complex systems","call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"}],"scopus_import":"1","_id":"1391","publisher":"Springer","article_processing_charge":"No","language":[{"iso":"eng"}],"date_published":"2016-07-13T00:00:00Z","conference":{"end_date":"2016-07-23","start_date":"2016-07-17","location":"Toronto, Canada","name":"CAV: Computer Aided Verification"},"page":"230 - 248","author":[{"id":"49351290-F248-11E8-B48F-1D18A9856A87","last_name":"Daca","full_name":"Daca, Przemyslaw","first_name":"Przemyslaw"},{"first_name":"Thomas A","full_name":"Henzinger, Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kupriyanov","id":"2C311BF8-F248-11E8-B48F-1D18A9856A87","first_name":"Andrey","full_name":"Kupriyanov, Andrey"}]},{"department":[{"_id":"ToHe"}],"status":"public","external_id":{"isi":["000375148800016"],"arxiv":["1511.02615"]},"title":"Abstraction-driven concolic testing","citation":{"chicago":"Daca, Przemyslaw, Ashutosh Gupta, and Thomas A Henzinger. “Abstraction-Driven Concolic Testing,” 9583:328–47. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-662-49122-5_16\">https://doi.org/10.1007/978-3-662-49122-5_16</a>.","mla":"Daca, Przemyslaw, et al. <i>Abstraction-Driven Concolic Testing</i>. Vol. 9583, Springer, 2016, pp. 328–47, doi:<a href=\"https://doi.org/10.1007/978-3-662-49122-5_16\">10.1007/978-3-662-49122-5_16</a>.","apa":"Daca, P., Gupta, A., &#38; Henzinger, T. A. (2016). Abstraction-driven concolic testing (Vol. 9583, pp. 328–347). Presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, St. Petersburg, FL, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-662-49122-5_16\">https://doi.org/10.1007/978-3-662-49122-5_16</a>","ieee":"P. Daca, A. Gupta, and T. A. Henzinger, “Abstraction-driven concolic testing,” presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, St. Petersburg, FL, USA, 2016, vol. 9583, pp. 328–347.","short":"P. Daca, A. Gupta, T.A. Henzinger, in:, Springer, 2016, pp. 328–347.","ista":"Daca P, Gupta A, Henzinger TA. 2016. Abstraction-driven concolic testing. VMCAI: Verification, Model Checking and Abstract Interpretation, LNCS, vol. 9583, 328–347.","ama":"Daca P, Gupta A, Henzinger TA. Abstraction-driven concolic testing. In: Vol 9583. Springer; 2016:328-347. doi:<a href=\"https://doi.org/10.1007/978-3-662-49122-5_16\">10.1007/978-3-662-49122-5_16</a>"},"doi":"10.1007/978-3-662-49122-5_16","ec_funded":1,"date_updated":"2026-04-08T14:21:07Z","volume":9583,"oa":1,"publist_id":"6104","intvolume":"      9583","month":"01","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","year":"2016","publication_status":"published","quality_controlled":"1","day":"01","type":"conference","related_material":{"record":[{"id":"1155","relation":"dissertation_contains","status":"public"}]},"abstract":[{"text":"Concolic testing is a promising method for generating test suites for large programs. However, it suffers from the path-explosion problem and often fails to find tests that cover difficult-to-reach parts of programs. In contrast, model checkers based on counterexample-guided abstraction refinement explore programs exhaustively, while failing to scale on large programs with precision. In this paper, we present a novel method that iteratively combines concolic testing and model checking to find a test suite for a given coverage criterion. If concolic testing fails to cover some test goals, then the model checker refines its program abstraction to prove more paths infeasible, which reduces the search space for concolic testing. We have implemented our method on top of the concolictesting tool Crest and the model checker CpaChecker. We evaluated our tool on a collection of programs and a category of SvComp benchmarks. In our experiments, we observed an improvement in branch coverage compared to Crest from 48% to 63% in the best case, and from 66% to 71% on average.","lang":"eng"}],"oa_version":"Preprint","arxiv":1,"scopus_import":"1","project":[{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","call_identifier":"FP7","grant_number":"267989"},{"name":"Formal methods for the design and analysis of complex systems","call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"}],"alternative_title":["LNCS"],"_id":"1230","language":[{"iso":"eng"}],"article_processing_charge":"No","publisher":"Springer","page":"328 - 347","author":[{"last_name":"Daca","id":"49351290-F248-11E8-B48F-1D18A9856A87","first_name":"Przemyslaw","full_name":"Daca, Przemyslaw"},{"full_name":"Gupta, Ashutosh","first_name":"Ashutosh","id":"335E5684-F248-11E8-B48F-1D18A9856A87","last_name":"Gupta"},{"orcid":"0000−0002−2985−7724","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","full_name":"Henzinger, Thomas A"}],"conference":{"name":"VMCAI: Verification, Model Checking and Abstract Interpretation","location":"St. Petersburg, FL, USA","start_date":"2016-01-17","end_date":"2016-01-19"},"date_published":"2016-01-01T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1511.02615","open_access":"1"}],"isi":1,"acknowledgement":"We thank Andrey Kupriyanov for feedback on the manuscript,\r\nand Michael Tautschnig for help with preparing the experiments. This research was supported in part by the European Research Council (ERC) under grant 267989 (QUAREM) and by the Austrian Science Fund (FWF) under grants S11402-N23 (RiSE) and Z211-N23 (Wittgenstein Award).","date_created":"2018-12-11T11:50:50Z"},{"status":"public","title":"Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs","department":[{"_id":"KrCh"}],"doi":"10.4230/LIPIcs.ESA.2016.28","citation":{"ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2016. Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs. ESA: European Symposium on Algorithms, LIPIcs, vol. 57, 28.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs. In: Vol 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2016.28\">10.4230/LIPIcs.ESA.2016.28</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, “Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs,” presented at the ESA: European Symposium on Algorithms, Aarhus, Denmark, 2016, vol. 57.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. “Optimal Reachability and a Space Time Tradeoff for Distance Queries in Constant Treewidth Graphs,” Vol. 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2016.28\">https://doi.org/10.4230/LIPIcs.ESA.2016.28</a>.","mla":"Chatterjee, Krishnendu, et al. <i>Optimal Reachability and a Space Time Tradeoff for Distance Queries in Constant Treewidth Graphs</i>. Vol. 57, 28, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2016.28\">10.4230/LIPIcs.ESA.2016.28</a>.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2016). Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs (Vol. 57). Presented at the ESA: European Symposium on Algorithms, Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2016.28\">https://doi.org/10.4230/LIPIcs.ESA.2016.28</a>"},"ec_funded":1,"pubrep_id":"777","date_updated":"2026-04-08T14:22:16Z","oa":1,"volume":57,"publist_id":"6312","intvolume":"        57","file":[{"file_size":579225,"creator":"system","date_created":"2018-12-12T10:14:31Z","content_type":"application/pdf","access_level":"open_access","file_name":"IST-2017-777-v1+1_LIPIcs-ESA-2016-28.pdf","date_updated":"2018-12-12T10:14:31Z","file_id":"5084","relation":"main_file"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"08","year":"2016","publication_status":"published","type":"conference","abstract":[{"text":"We consider data-structures for answering reachability and distance queries on constant-treewidth graphs with n nodes, on the standard RAM computational model with wordsize W=Theta(log n). Our first contribution is a data-structure that after O(n) preprocessing time, allows (1) pair reachability queries in O(1) time; and (2) single-source reachability queries in O(n/log n) time. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries. The data-structure uses at all times O(n) space. Our second contribution is a space-time tradeoff data-structure for distance queries. For any epsilon in [1/2,1], we provide a data-structure with polynomial preprocessing time that allows pair queries in O(n^{1-\\epsilon} alpha(n)) time, where alpha is the inverse of the Ackermann function, and at all times uses O(n^epsilon) space. The input graph G is not considered in the space complexity. ","lang":"eng"}],"related_material":{"record":[{"relation":"dissertation_contains","id":"821","status":"public"}]},"quality_controlled":"1","day":"01","oa_version":"Published Version","alternative_title":["LIPIcs"],"project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"}],"scopus_import":"1","_id":"1071","article_number":"28","article_processing_charge":"No","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","has_accepted_license":"1","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus"},{"last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","full_name":"Pavlogiannis, Andreas"}],"conference":{"name":"ESA: European Symposium on Algorithms","location":"Aarhus, Denmark","start_date":"2016-08-22","end_date":"2016-08-24"},"date_published":"2016-08-01T00:00:00Z","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"acknowledgement":"The research was partly supported by Austrian Science Fund (FWF) Grant No P23499-N23, FWF NFN Grant No S11407-N23 (RiSE/SHiNE) and ERC Start grant (279307: Graph Games).","file_date_updated":"2018-12-12T10:14:31Z","date_created":"2018-12-11T11:49:59Z","ddc":["004","006"]},{"_id":"1397","OA_place":"publisher","citation":{"mla":"Chmelik, Martin. <i>Algorithms for Partially Observable Markov Decision Processes</i>. Institute of Science and Technology Austria, 2016.","chicago":"Chmelik, Martin. “Algorithms for Partially Observable Markov Decision Processes.” Institute of Science and Technology Austria, 2016.","apa":"Chmelik, M. (2016). <i>Algorithms for partially observable markov decision processes</i>. Institute of Science and Technology Austria.","ista":"Chmelik M. 2016. Algorithms for partially observable markov decision processes. Institute of Science and Technology Austria.","ama":"Chmelik M. Algorithms for partially observable markov decision processes. 2016.","ieee":"M. Chmelik, “Algorithms for partially observable markov decision processes,” Institute of Science and Technology Austria, 2016.","short":"M. Chmelik, Algorithms for Partially Observable Markov Decision Processes, Institute of Science and Technology Austria, 2016."},"department":[{"_id":"KrCh"}],"title":"Algorithms for partially observable markov decision processes","status":"public","alternative_title":["ISTA Thesis"],"date_published":"2016-02-01T00:00:00Z","author":[{"full_name":"Chmelik, Martin","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","last_name":"Chmelik"}],"page":"232","publist_id":"5810","date_updated":"2026-04-08T14:23:19Z","publisher":"Institute of Science and Technology Austria","language":[{"iso":"eng"}],"article_processing_charge":"No","publication_identifier":{"issn":["2663-337X"]},"day":"01","supervisor":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"}],"corr_author":"1","abstract":[{"lang":"eng","text":"We study partially observable Markov decision processes (POMDPs) with objectives used in verification and artificial intelligence. The qualitative analysis problem given a POMDP and an objective asks whether there is a strategy (policy) to ensure that the objective is satisfied almost surely (with probability 1), resp. with positive probability (with probability greater than 0). For POMDPs with limit-average payoff, where a reward value in the interval [0,1] is associated to every transition, and the payoff of an infinite path is the long-run average of the rewards, we consider two types of path constraints: (i) a quantitative limit-average constraint defines the set of paths where the payoff is at least a given threshold L1 = 1. Our main results for qualitative limit-average constraint under almost-sure winning are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative limit-average constraints we show that the problem of deciding the existence of a finite-memory controller is undecidable. We present a prototype implementation of our EXPTIME algorithm. For POMDPs with w-regular conditions specified as parity objectives, while the qualitative analysis problems are known to be undecidable even for very special case of parity objectives, we establish decidability (with optimal complexity) of the qualitative analysis problems for POMDPs with parity objectives under finite-memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. Based on our theoretical algorithms we also present a practical approach, where we design heuristics to deal with the exponential complexity, and have applied our implementation on a number of well-known POMDP examples for robotics applications. For POMDPs with a set of target states and an integer cost associated with every transition, we study the optimization objective that asks to minimize the expected total cost of reaching a state in the target set, while ensuring that the target set is reached almost surely. We show that for general integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost, both double and exponential in the POMDP state space size; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms that extend existing algorithms for POMDPs with finite-horizon objectives. We show experimentally that it performs well in many examples of interest. We study more deeply the problem of almost-sure reachability, where  given a set of target states, the question is to decide whether there is a strategy to ensure that the target set is reached almost surely. While in general the problem EXPTIME-complete, in many practical cases strategies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. We first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach. Decentralized POMDPs (DEC-POMDPs) extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. In this work we consider Goal DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new and novel method to solve the problem that extends methods for finite-horizon DEC-POMDPs and the real-time dynamic programming approach for POMDPs. We present experimental results on several examples, and show that our approach presents promising results. In the end we present a short summary of a few other results related to verification of MDPs and POMDPs."}],"type":"dissertation","degree_awarded":"PhD","publication_status":"published","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","month":"02","year":"2016","date_created":"2018-12-11T11:51:47Z","oa_version":"None"},{"_id":"1129","OA_place":"publisher","alternative_title":["ISTA Thesis"],"author":[{"last_name":"Schwarz","id":"346C1EC6-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","full_name":"Schwarz, Jan"}],"page":"178","date_published":"2016-07-01T00:00:00Z","language":[{"iso":"eng"}],"article_processing_charge":"No","publisher":"Institute of Science and Technology Austria","has_accepted_license":"1","acknowledgement":"First, I would like to thank Michael Sixt for being a great supervisor, mentor and\r\nscientist. I highly appreciate his guidance and continued support. Furthermore, I\r\nam very grateful that he gave me the exceptional opportunity to pursue many\r\nideas of which some managed to be included in this thesis.\r\nI owe sincere thanks to the members of my PhD thesis committee, Daria\r\nSiekhaus, Daniel Legler and Harald Janovjak. Especially I would like to thank\r\nDaria for her advice and encouragement during our regular progress meetings.\r\nI also want to thank the team and fellows of the Boehringer Ingelheim Fond\r\n(BIF) PhD Fellowship for amazing and inspiring meetings and the BIF for\r\nfinancial support.\r\nImportant factors for the success of this thesis were the warm, creative\r\nand helpful atmosphere as well as the team spirit of the whole Sixt Lab.\r\nTherefore I would like to thank my current and former colleagues Frank Assen,\r\nMarkus Brown, Ingrid de Vries, Michelle Duggan, Alexander Eichner, Miroslav\r\nHons, Eva Kiermaier, Aglaja Kopf, Alexander Leithner, Christine Moussion, Jan\r\nMüller, Maria Nemethova, Jörg Renkawitz, Anne Reversat, Kari Vaahtomeri,\r\nMichele Weber and Stefan Wieser. We had an amazing time with many\r\nlegendary evenings and events. Along these lines I want to thank the in vitro\r\ncrew of the lab, Jörg, Anne and Alex, for lots of ideas and productive\r\ndiscussions. I am sure, some day we will reveal the secret of the ‘splodge’.\r\nI want to thank the members of the Heisenberg Lab for a great time and\r\nthrilling kicker matches. In this regard I especially want to thank Maurizio\r\n‘Gnocci’ Monti, Gabriel Krens, Alex Eichner, Martin Behrndt, Vanessa Barone,Philipp Schmalhorst, Michael Smutny, Daniel Capek, Anne Reversat, Eva\r\nKiermaier, Frank Assen and Jan Müller for wonderful after-lunch matches.\r\nI would not have been able to analyze the thousands of cell trajectories\r\nand probably hundreds of thousands of mouse clicks without the productive\r\ncollaboration with Veronika Bierbaum and Tobias Bollenbach. Thanks Vroni for\r\ncountless meetings, discussions and graphs and of course for proofreading and\r\nadvice for this thesis. For proofreading I also want to thank Evi, Jörg, Jack and\r\nAnne.\r\nI would like to acknowledge Matthias Mehling for a very productive\r\ncollaboration and for introducing me into the wild world of microfluidics. Jack\r\nMerrin, for countless wafers, PDMS coated coverslips and help with anything\r\nmicro-fabrication related. And Maria Nemethova for establishing the ‘click’\r\npatterning approach with me. Without her it still would be just one of the ideas…\r\nMany thanks to Ekaterina Papusheva, Robert Hauschild, Doreen Milius\r\nand Nasser Darwish from the Bioimaging Facility as well as the Preclinical and\r\nthe Life Science facilities of IST Austria for excellent technical support. At this\r\npoint I especially want to thank Robert for countless image analyses and\r\ntechnical ideas. Always interested and creative he played an essential role in all\r\nof my projects.\r\nAdditionally I want to thank Ingrid and Gabby for welcoming me warmly\r\nwhen I first started at IST, for scientific and especially mental support in all\r\nthose years, countless coffee sessions and Heurigen evenings. #BioimagingFacility #LifeScienceFacility #PreClinicalFacility","publication_identifier":{"issn":["2663-337X"]},"degree_awarded":"PhD","file_date_updated":"2021-02-22T11:43:14Z","date_created":"2018-12-11T11:50:18Z","ddc":["570"],"citation":{"mla":"Schwarz, Jan. <i>Quantitative Analysis of Haptotactic Cell Migration</i>. Institute of Science and Technology Austria, 2016.","chicago":"Schwarz, Jan. “Quantitative Analysis of Haptotactic Cell Migration.” Institute of Science and Technology Austria, 2016.","apa":"Schwarz, J. (2016). <i>Quantitative analysis of haptotactic cell migration</i>. Institute of Science and Technology Austria.","ista":"Schwarz J. 2016. Quantitative analysis of haptotactic cell migration. Institute of Science and Technology Austria.","ama":"Schwarz J. Quantitative analysis of haptotactic cell migration. 2016.","ieee":"J. Schwarz, “Quantitative analysis of haptotactic cell migration,” Institute of Science and Technology Austria, 2016.","short":"J. Schwarz, Quantitative Analysis of Haptotactic Cell Migration, Institute of Science and Technology Austria, 2016."},"status":"public","title":"Quantitative analysis of haptotactic cell migration","department":[{"_id":"MiSi"}],"file":[{"date_updated":"2019-08-13T10:55:35Z","file_name":"Thesis_JSchwarz_final.pdf","date_created":"2019-08-13T10:55:35Z","content_type":"application/pdf","access_level":"closed","file_size":32044069,"creator":"dernst","relation":"main_file","checksum":"e3cd6b28f9c5cccb8891855565a2dade","file_id":"6813"},{"file_size":8396717,"creator":"dernst","content_type":"application/pdf","date_created":"2021-02-22T11:43:14Z","access_level":"open_access","date_updated":"2021-02-22T11:43:14Z","file_name":"2016_Thesis_JSchwarz.pdf","file_id":"9181","checksum":"c3dbe219acf87eed2f46d21d5cca00de","success":1,"relation":"main_file"}],"date_updated":"2026-04-08T14:28:53Z","publist_id":"6231","oa":1,"type":"dissertation","abstract":[{"text":"Directed cell migration is a hallmark feature, present in almost all multi-cellular\r\norganisms. Despite its importance, basic questions regarding force transduction\r\nor directional sensing are still heavily investigated. Directed migration of cells\r\nguided by immobilized guidance cues - haptotaxis - occurs in key-processes,\r\nsuch as embryonic development and immunity (Middleton et al., 1997; Nguyen\r\net al., 2000; Thiery, 1984; Weber et al., 2013). Immobilized guidance cues\r\ncomprise adhesive ligands, such as collagen and fibronectin (Barczyk et al.,\r\n2009), or chemokines - the main guidance cues for migratory leukocytes\r\n(Middleton et al., 1997; Weber et al., 2013). While adhesive ligands serve as\r\nattachment sites guiding cell migration (Carter, 1965), chemokines instruct\r\nhaptotactic migration by inducing adhesion to adhesive ligands and directional\r\nguidance (Rot and Andrian, 2004; Schumann et al., 2010). Quantitative analysis\r\nof the cellular response to immobilized guidance cues requires in vitro assays\r\nthat foster cell migration, offer accurate control of the immobilized cues on a\r\nsubcellular scale and in the ideal case closely reproduce in vivo conditions. The\r\nexploration of haptotactic cell migration through design and employment of such\r\nassays represents the main focus of this work.\r\nDendritic cells (DCs) are leukocytes, which after encountering danger\r\nsignals such as pathogens in peripheral organs instruct naïve T-cells and\r\nconsequently the adaptive immune response in the lymph node (Mellman and\r\nSteinman, 2001). To reach the lymph node from the periphery, DCs follow\r\nhaptotactic gradients of the chemokine CCL21 towards lymphatic vessels\r\n(Weber et al., 2013). Questions about how DCs interpret haptotactic CCL21\r\ngradients have not yet been addressed. The main reason for this is the lack of\r\nan assay that offers diverse haptotactic environments, hence allowing the study\r\nof DC migration as a response to different signals of immobilized guidance cue.\r\nIn this work, we developed an in vitro assay that enables us to\r\nquantitatively assess DC haptotaxis, by combining precisely controllable\r\nchemokine photo-patterning with physically confining migration conditions. With this tool at hand, we studied the influence of CCL21 gradient properties and\r\nconcentration on DC haptotaxis. We found that haptotactic gradient sensing\r\ndepends on the absolute CCL21 concentration in combination with the local\r\nsteepness of the gradient. Our analysis suggests that the directionality of\r\nmigrating DCs is governed by the signal-to-noise ratio of CCL21 binding to its\r\nreceptor CCR7. Moreover, the haptotactic CCL21 gradient formed in vivo\r\nprovides an optimal shape for DCs to recognize haptotactic guidance cue.\r\nBy reconstitution of the CCL21 gradient in vitro we were also able to\r\nstudy the influence of CCR7 signal termination on DC haptotaxis. To this end,\r\nwe used DCs lacking the G-protein coupled receptor kinase GRK6, which is\r\nresponsible for CCL21 induced CCR7 receptor phosphorylation and\r\ndesensitization (Zidar et al., 2009). We found that CCR7 desensitization by\r\nGRK6 is crucial for maintenance of haptotactic CCL21 gradient sensing in vitro\r\nand confirm those observations in vivo.\r\nIn the context of the organism, immobilized haptotactic guidance cues\r\noften coincide and compete with soluble chemotactic guidance cues. During\r\nwound healing, fibroblasts are exposed and influenced by adhesive cues and\r\nsoluble factors at the same time (Wu et al., 2012; Wynn, 2008). Similarly,\r\nmigrating DCs are exposed to both, soluble chemokines (CCL19 and truncated\r\nCCL21) inducing chemotactic behavior as well as the immobilized CCL21. To\r\nquantitatively assess these complex coinciding immobilized and soluble\r\nguidance cues, we implemented our chemokine photo-patterning technique in a\r\nmicrofluidic system allowing for chemotactic gradient generation. To validate\r\nthe assay, we observed DC migration in competing CCL19/CCL21\r\nenvironments.\r\nAdhesiveness guided haptotaxis has been studied intensively over the\r\nlast century. However, quantitative studies leading to conceptual models are\r\nlargely missing, again due to the lack of a precisely controllable in vitro assay. A\r\nrequirement for such an in vitro assay is that it must prevent any uncontrolled\r\ncell adhesion. This can be accomplished by stable passivation of the surface. In\r\naddition, controlled adhesion must be sustainable, quantifiable and dose\r\ndependent in order to create homogenous gradients. Therefore, we developed a novel covalent photo-patterning technique satisfying all these needs. In\r\ncombination with a sustainable poly-vinyl alcohol (PVA) surface coating we\r\nwere able to generate gradients of adhesive cue to direct cell migration. This\r\napproach allowed us to characterize the haptotactic migratory behavior of\r\nzebrafish keratocytes in vitro. Furthermore, defined patterns of adhesive cue\r\nallowed us to control for cell shape and growth on a subcellular scale.","lang":"eng"}],"acknowledged_ssus":[{"_id":"Bio"},{"_id":"PreCl"},{"_id":"LifeSc"}],"supervisor":[{"orcid":"0000-0002-6620-9179","last_name":"Sixt","id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","first_name":"Michael K","full_name":"Sixt, Michael K"}],"corr_author":"1","day":"01","month":"07","year":"2016","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publication_status":"published","oa_version":"Published Version"},{"date_created":"2018-12-11T11:51:21Z","ddc":["570"],"file_date_updated":"2020-07-14T12:44:43Z","isi":1,"tmp":{"image":"/images/cc_by_nc_sa.png","short":"CC BY-NC-SA (4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)"},"acknowledgement":"This work was supported by the German Research Foundation (DFG) Priority Program SP 1464 to T.E.B.S. and M.S., and European Research Council (ERC GA 281556) and Human Frontiers Program grants to M.S.\r\nService Units of IST Austria for excellent technical support.","has_accepted_license":"1","article_processing_charge":"No","language":[{"iso":"eng"}],"publisher":"Nature Publishing Group","author":[{"last_name":"Leithner","orcid":"0000-0002-1073-744X","id":"3B1B77E4-F248-11E8-B48F-1D18A9856A87","first_name":"Alexander F","full_name":"Leithner, Alexander F"},{"full_name":"Eichner, Alexander","first_name":"Alexander","id":"4DFA52AE-F248-11E8-B48F-1D18A9856A87","last_name":"Eichner"},{"first_name":"Jan","full_name":"Müller, Jan","last_name":"Müller","id":"AD07FDB4-0F61-11EA-8158-C4CC64CEAA8D"},{"full_name":"Reversat, Anne","first_name":"Anne","id":"35B76592-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-0666-8928","last_name":"Reversat"},{"last_name":"Brown","id":"3DAB9AFC-F248-11E8-B48F-1D18A9856A87","first_name":"Markus","full_name":"Brown, Markus"},{"id":"346C1EC6-F248-11E8-B48F-1D18A9856A87","last_name":"Schwarz","full_name":"Schwarz, Jan","first_name":"Jan"},{"full_name":"Merrin, Jack","first_name":"Jack","id":"4515C308-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5145-4609","last_name":"Merrin"},{"full_name":"De Gorter, David","first_name":"David","last_name":"De Gorter"},{"first_name":"Florian","full_name":"Schur, Florian","last_name":"Schur","orcid":"0000-0003-4790-8078","id":"48AD8942-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Bayerl","full_name":"Bayerl, Jonathan","first_name":"Jonathan"},{"first_name":"Ingrid","full_name":"De Vries, Ingrid","last_name":"De Vries","id":"4C7D837E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Wieser, Stefan","first_name":"Stefan","id":"355AA5A0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2670-2217","last_name":"Wieser"},{"full_name":"Hauschild, Robert","first_name":"Robert","id":"4E01D6B4-F248-11E8-B48F-1D18A9856A87","last_name":"Hauschild","orcid":"0000-0001-9843-3522"},{"last_name":"Lai","full_name":"Lai, Frank","first_name":"Frank"},{"full_name":"Moser, Markus","first_name":"Markus","last_name":"Moser"},{"first_name":"Dontscho","full_name":"Kerjaschki, Dontscho","last_name":"Kerjaschki"},{"full_name":"Rottner, Klemens","first_name":"Klemens","last_name":"Rottner"},{"last_name":"Small","first_name":"Victor","full_name":"Small, Victor"},{"last_name":"Stradal","full_name":"Stradal, Theresia","first_name":"Theresia"},{"id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6620-9179","last_name":"Sixt","full_name":"Sixt, Michael K","first_name":"Michael K"}],"page":"1253 - 1259","date_published":"2016-10-24T00:00:00Z","scopus_import":"1","project":[{"_id":"25A603A2-B435-11E9-9278-68D0E5697425","name":"Cytoskeletal force generation and force transduction of migrating leukocytes","call_identifier":"FP7","grant_number":"281556"}],"_id":"1321","oa_version":"Submitted Version","month":"10","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","year":"2016","publication_status":"published","corr_author":"1","quality_controlled":"1","day":"24","type":"journal_article","abstract":[{"text":"Most migrating cells extrude their front by the force of actin polymerization. Polymerization requires an initial nucleation step, which is mediated by factors establishing either parallel filaments in the case of filopodia or branched filaments that form the branched lamellipodial network. Branches are considered essential for regular cell motility and are initiated by the Arp2/3 complex, which in turn is activated by nucleation-promoting factors of the WASP and WAVE families. Here we employed rapid amoeboid crawling leukocytes and found that deletion of the WAVE complex eliminated actin branching and thus lamellipodia formation. The cells were left with parallel filaments at the leading edge, which translated, depending on the differentiation status of the cell, into a unipolar pointed cell shape or cells with multiple filopodia. Remarkably, unipolar cells migrated with increased speed and enormous directional persistence, while they were unable to turn towards chemotactic gradients. Cells with multiple filopodia retained chemotactic activity but their migration was progressively impaired with increasing geometrical complexity of the extracellular environment. These findings establish that diversified leading edge protrusions serve as explorative structures while they slow down actual locomotion.","lang":"eng"}],"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"323"}]},"acknowledged_ssus":[{"_id":"SSU"}],"date_updated":"2026-04-08T22:30:03Z","volume":18,"oa":1,"publist_id":"5949","license":"https://creativecommons.org/licenses/by-nc-sa/4.0/","article_type":"original","intvolume":"        18","file":[{"relation":"main_file","file_id":"7844","checksum":"e1411cb7c99a2d9089c178a6abef25e7","file_name":"2018_NatureCell_Leithner.pdf","date_updated":"2020-07-14T12:44:43Z","access_level":"open_access","date_created":"2020-05-14T16:33:46Z","content_type":"application/pdf","creator":"dernst","file_size":4433280}],"department":[{"_id":"MiSi"},{"_id":"NanoFab"},{"_id":"Bio"}],"status":"public","title":"Diversified actin protrusions promote environmental exploration but are dispensable for locomotion of leukocytes","external_id":{"isi":["000387165600018"]},"citation":{"ama":"Leithner AF, Eichner A, Müller J, et al. Diversified actin protrusions promote environmental exploration but are dispensable for locomotion of leukocytes. <i>Nature Cell Biology</i>. 2016;18:1253-1259. doi:<a href=\"https://doi.org/10.1038/ncb3426\">10.1038/ncb3426</a>","ista":"Leithner AF, Eichner A, Müller J, Reversat A, Brown M, Schwarz J, Merrin J, De Gorter D, Schur FK, Bayerl J, de Vries I, Wieser S, Hauschild R, Lai F, Moser M, Kerjaschki D, Rottner K, Small V, Stradal T, Sixt MK. 2016. Diversified actin protrusions promote environmental exploration but are dispensable for locomotion of leukocytes. Nature Cell Biology. 18, 1253–1259.","short":"A.F. Leithner, A. Eichner, J. Müller, A. Reversat, M. Brown, J. Schwarz, J. Merrin, D. De Gorter, F.K. Schur, J. Bayerl, I. de Vries, S. Wieser, R. Hauschild, F. Lai, M. Moser, D. Kerjaschki, K. Rottner, V. Small, T. Stradal, M.K. Sixt, Nature Cell Biology 18 (2016) 1253–1259.","ieee":"A. F. Leithner <i>et al.</i>, “Diversified actin protrusions promote environmental exploration but are dispensable for locomotion of leukocytes,” <i>Nature Cell Biology</i>, vol. 18. Nature Publishing Group, pp. 1253–1259, 2016.","apa":"Leithner, A. F., Eichner, A., Müller, J., Reversat, A., Brown, M., Schwarz, J., … Sixt, M. K. (2016). Diversified actin protrusions promote environmental exploration but are dispensable for locomotion of leukocytes. <i>Nature Cell Biology</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/ncb3426\">https://doi.org/10.1038/ncb3426</a>","chicago":"Leithner, Alexander F, Alexander Eichner, Jan Müller, Anne Reversat, Markus Brown, Jan Schwarz, Jack Merrin, et al. “Diversified Actin Protrusions Promote Environmental Exploration but Are Dispensable for Locomotion of Leukocytes.” <i>Nature Cell Biology</i>. Nature Publishing Group, 2016. <a href=\"https://doi.org/10.1038/ncb3426\">https://doi.org/10.1038/ncb3426</a>.","mla":"Leithner, Alexander F., et al. “Diversified Actin Protrusions Promote Environmental Exploration but Are Dispensable for Locomotion of Leukocytes.” <i>Nature Cell Biology</i>, vol. 18, Nature Publishing Group, 2016, pp. 1253–59, doi:<a href=\"https://doi.org/10.1038/ncb3426\">10.1038/ncb3426</a>."},"doi":"10.1038/ncb3426","publication":"Nature Cell Biology","ec_funded":1},{"file_date_updated":"2018-12-12T10:13:02Z","date_created":"2018-12-11T11:50:16Z","ddc":["004","005","006","532","621"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"acknowledgement":"First and foremost I would like to thank Chris. I have been incredibly lucky to have\r\nyou as my advisor. Your integrity and aspiration to do the right thing in all walks of\r\nlife is something I admire and aspire to. I also really appreciate the fact that when\r\nworking with you it felt like we were equals. I think we had a very synergetic work\r\nrelationship: I learned immensely from you, but I dare say that you learned a few\r\nthings from me as well. ;)\r\nNext, I would like to thank my amazing committee. Hao, it was a fantastic\r\nexperience working with you. You showed me how to persevere and keep morale\r\nhigh when things were looking the most bleak before the deadline. You are an\r\nincredible motivator and super fun to be around! Vladimir, thanks for the shared\r\nlunches and the poker games. Sorry for not bringing them back when I got busy.\r\nAlso, sorry for embarrassing you by asking about your guitar playing that one\r\ntime. You really are quite awesome! Nils, one of the friendliest and most humble\r\npeople you will meet and a top notch researcher to boot! Thank you for joining\r\nmy committee late!\r\nI would also like to acknowledge the Visual Computing group at IST Austria\r\nfrom whom I have learned so much. The excellent discussions we had in reading\r\ngroups and research meetings really helped me become a better researcher!\r\nNext, I would like to thank all the amazing people that I met during my PhD\r\nstudies, both at IST Austria, in Vienna and elsewhere. ","publication_identifier":{"issn":["2663-337X"]},"degree_awarded":"PhD","page":"114","author":[{"first_name":"Morten","full_name":"Bojsen-Hansen, Morten","last_name":"Bojsen-Hansen","orcid":"0000-0002-4417-3224","id":"439F0C8C-F248-11E8-B48F-1D18A9856A87"}],"date_published":"2016-07-15T00:00:00Z","article_processing_charge":"No","language":[{"iso":"eng"}],"publisher":"Institute of Science and Technology Austria","has_accepted_license":"1","OA_place":"publisher","_id":"1122","alternative_title":["ISTA Thesis"],"oa_version":"Published Version","type":"dissertation","related_material":{"record":[{"id":"5558","relation":"other","status":"public"}]},"abstract":[{"lang":"eng","text":"Computer graphics is an extremely exciting field for two reasons. On the one hand,\r\nthere is a healthy injection of pragmatism coming from the visual effects industry\r\nthat want robust algorithms that work so they can produce results at an increasingly\r\nfrantic pace. On the other hand, they must always try to push the envelope and\r\nachieve the impossible to wow their audiences in the next blockbuster, which means\r\nthat the industry has not succumb to conservatism, and there is plenty of room to\r\ntry out new and crazy ideas if there is a chance that it will pan into something\r\nuseful.\r\nWater simulation has been in visual effects for decades, however it still remains\r\nextremely challenging because of its high computational cost and difficult artdirectability.\r\nThe work in this thesis tries to address some of these difficulties.\r\nSpecifically, we make the following three novel contributions to the state-of-the-art\r\nin water simulation for visual effects.\r\nFirst, we develop the first algorithm that can convert any sequence of closed\r\nsurfaces in time into a moving triangle mesh. State-of-the-art methods at the time\r\ncould only handle surfaces with fixed connectivity, but we are the first to be able to\r\nhandle surfaces that merge and split apart. This is important for water simulation\r\npractitioners, because it allows them to convert splashy water surfaces extracted\r\nfrom particles or simulated using grid-based level sets into triangle meshes that can\r\nbe either textured and enhanced with extra surface dynamics as a post-process.\r\nWe also apply our algorithm to other phenomena that merge and split apart, such\r\nas morphs and noisy reconstructions of human performances.\r\nSecond, we formulate a surface-based energy that measures the deviation of a\r\nwater surface froma physically valid state. Such discrepancies arise when there is a\r\nmismatch in the degrees of freedom between the water surface and the underlying\r\nphysics solver. This commonly happens when practitioners use a moving triangle\r\nmesh with a grid-based physics solver, or when high-resolution grid-based surfaces\r\nare combined with low-resolution physics. Following the direction of steepest\r\ndescent on our surface-based energy, we can either smooth these artifacts or turn\r\nthem into high-resolution waves by interpreting the energy as a physical potential.\r\nThird, we extend state-of-the-art techniques in non-reflecting boundaries to handle spatially and time-varying background flows. This allows a novel new\r\nworkflow where practitioners can re-simulate part of an existing simulation, such\r\nas removing a solid obstacle, adding a new splash or locally changing the resolution.\r\nSuch changes can easily lead to new waves in the re-simulated region that would\r\nreflect off of the new simulation boundary, effectively ruining the illusion of a\r\nseamless simulation boundary between the existing and new simulations. Our\r\nnon-reflecting boundaries makes sure that such waves are absorbed."}],"corr_author":"1","supervisor":[{"full_name":"Wojtan, Christopher J","first_name":"Christopher J","id":"3C61F1D2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6646-5546","last_name":"Wojtan"}],"day":"15","year":"2016","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","month":"07","publication_status":"published","file":[{"file_id":"4982","relation":"main_file","content_type":"application/pdf","date_created":"2018-12-12T10:13:02Z","access_level":"open_access","creator":"system","file_size":13869345,"file_name":"IST-2016-640-v1+1_2016_Bojsen-Hansen_TCaAWSW.pdf","date_updated":"2018-12-12T10:13:02Z"}],"date_updated":"2026-04-08T14:24:06Z","oa":1,"publist_id":"6238","doi":"10.15479/AT:ISTA:th_640","citation":{"ama":"Bojsen-Hansen M. Tracking, correcting and absorbing water surface waves. 2016. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_640\">10.15479/AT:ISTA:th_640</a>","ista":"Bojsen-Hansen M. 2016. Tracking, correcting and absorbing water surface waves. Institute of Science and Technology Austria.","short":"M. Bojsen-Hansen, Tracking, Correcting and Absorbing Water Surface Waves, Institute of Science and Technology Austria, 2016.","ieee":"M. Bojsen-Hansen, “Tracking, correcting and absorbing water surface waves,” Institute of Science and Technology Austria, 2016.","apa":"Bojsen-Hansen, M. (2016). <i>Tracking, correcting and absorbing water surface waves</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:th_640\">https://doi.org/10.15479/AT:ISTA:th_640</a>","chicago":"Bojsen-Hansen, Morten. “Tracking, Correcting and Absorbing Water Surface Waves.” Institute of Science and Technology Austria, 2016. <a href=\"https://doi.org/10.15479/AT:ISTA:th_640\">https://doi.org/10.15479/AT:ISTA:th_640</a>.","mla":"Bojsen-Hansen, Morten. <i>Tracking, Correcting and Absorbing Water Surface Waves</i>. Institute of Science and Technology Austria, 2016, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_640\">10.15479/AT:ISTA:th_640</a>."},"status":"public","title":"Tracking, correcting and absorbing water surface waves","department":[{"_id":"ChWo"}]},{"publication_identifier":{"issn":["2663-337X"]},"acknowledgement":"Foremost, I would like to thank Uli Wagner for introducing me to the exciting interface between\r\ntopology and combinatorics, and for our subsequent years of fruitful collaboration.\r\nIn our creative endeavors to eliminate intersection points, we had the chance to be joined later\r\nby Sergey Avvakumov and Arkadiy Skopenkov, which led us to new surprises in dimension 12.\r\nMy stay at EPFL and IST Austria was made very agreeable thanks to all these wonderful\r\npeople: Cyril Becker, Marek Filakovsky, Peter Franek, Radoslav Fulek, Peter Gazi, Kristof Huszar,\r\nMarek Krcal, Zuzana Masarova, Arnaud de Mesmay, Filip Moric, Michal Rybar, Martin Tancer,\r\nand Stephan Zhechev.\r\nFinally, I would like to thank my thesis committee Herbert Edelsbrunner and Roman Karasev\r\nfor their careful reading of the present manuscript and for the many improvements they suggested.","degree_awarded":"PhD","date_created":"2018-12-11T11:50:16Z","ddc":["500"],"file_date_updated":"2021-02-22T11:36:34Z","_id":"1123","OA_place":"publisher","alternative_title":["ISTA Thesis"],"author":[{"last_name":"Mabillard","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","first_name":"Isaac","full_name":"Mabillard, Isaac"}],"page":"55","date_published":"2016-08-01T00:00:00Z","has_accepted_license":"1","language":[{"iso":"eng"}],"article_processing_charge":"No","publisher":"Institute of Science and Technology Austria","corr_author":"1","supervisor":[{"last_name":"Wagner","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","full_name":"Wagner, Uli"}],"day":"01","type":"dissertation","related_material":{"record":[{"status":"public","id":"2159","relation":"part_of_dissertation"}]},"abstract":[{"text":"Motivated by topological Tverberg-type problems  in topological combinatorics and by classical\r\nresults about embeddings (maps without double points), we study the question whether a finite\r\nsimplicial complex K  can be mapped into Rd  without triple, quadruple, or, more generally, r-fold points  (image points with at least r  distinct preimages), for a given multiplicity r ≤ 2. In particular, we are interested in maps f : K → Rd  that have no global r -fold intersection points, i.e., no r -fold points with preimages in r pairwise disjoint  simplices of K , and we seek necessary and sufficient conditions for the existence of such maps.\r\n\r\nWe present higher-multiplicity analogues of several classical results for embeddings, in particular of the completeness of the Van Kampen obstruction  for embeddability of k -dimensional\r\ncomplexes into R2k , k ≥ 3. Speciffically, we show that under suitable restrictions on the dimensions(viz., if dimK  = (r ≥ 1)k  and d  = rk \\ for some k ≥ 3), a well-known deleted product criterion (DPC ) is not only necessary but also sufficient for the existence of maps without global r -fold points. Our main technical tool is a higher-multiplicity version of the classical Whitney trick , by which pairs of isolated r -fold points of opposite sign  can be eliminated by local modiffications of the map, assuming codimension d – dimK ≥ 3.\r\n\r\nAn important guiding idea for our work was that suffciency of the DPC, together with an old\r\nresult of Özaydin's on the existence of equivariant maps, might yield an approach to disproving the remaining open cases of the the long-standing topological Tverberg conjecture , i.e., to construct maps from the N -simplex σN  to Rd  without r-Tverberg points when r not a prime power  and\r\nN  = (d  + 1)(r – 1). Unfortunately, our proof of the sufficiency of the DPC requires codimension d – dimK ≥ 3, which is not satisfied for K  = σN .\r\n\r\nIn 2015, Frick [16] found a very elegant way to overcome this \\codimension 3 obstacle&quot; and\r\nto construct the first counterexamples to the topological Tverberg conjecture for all parameters(d; r ) with d ≥ 3r  + 1 and r  not a prime power, by a reduction1  to a suitable lower-dimensional skeleton, for which the codimension 3 restriction is satisfied and maps without r -Tverberg points exist by Özaydin's result and sufficiency of the DPC.\r\n\r\nIn this thesis, we present a different construction (which does not use the constraint method) that yields counterexamples for d ≥ 3r , r  not a prime power.     ","lang":"eng"}],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","year":"2016","month":"08","publication_status":"published","oa_version":"Published Version","citation":{"ama":"Mabillard I. Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture. 2016.","ista":"Mabillard I. 2016. Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture. Institute of Science and Technology Austria.","short":"I. Mabillard, Eliminating Higher-Multiplicity Intersections: An r-Fold Whitney Trick for the Topological Tverberg Conjecture, Institute of Science and Technology Austria, 2016.","ieee":"I. Mabillard, “Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture,” Institute of Science and Technology Austria, 2016.","apa":"Mabillard, I. (2016). <i>Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture</i>. Institute of Science and Technology Austria.","chicago":"Mabillard, Isaac. “Eliminating Higher-Multiplicity Intersections: An r-Fold Whitney Trick for the Topological Tverberg Conjecture.” Institute of Science and Technology Austria, 2016.","mla":"Mabillard, Isaac. <i>Eliminating Higher-Multiplicity Intersections: An r-Fold Whitney Trick for the Topological Tverberg Conjecture</i>. Institute of Science and Technology Austria, 2016."},"department":[{"_id":"UlWa"}],"status":"public","title":"Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture","file":[{"file_name":"Thesis_final version_Mabillard_w_signature_page.pdf","date_updated":"2019-08-13T08:45:27Z","file_size":2227916,"creator":"dernst","date_created":"2019-08-13T08:45:27Z","content_type":"application/pdf","access_level":"closed","relation":"main_file","checksum":"2d140cc924cd1b764544906fc22684ef","file_id":"6809"},{"creator":"dernst","file_size":2227916,"date_created":"2021-02-22T11:36:34Z","content_type":"application/pdf","access_level":"open_access","file_name":"2016_Mabillard_Thesis.pdf","date_updated":"2021-02-22T11:36:34Z","file_id":"9178","checksum":"2d140cc924cd1b764544906fc22684ef","success":1,"relation":"main_file"}],"date_updated":"2026-04-08T14:24:23Z","oa":1,"publist_id":"6237"},{"date_published":"2016-08-01T00:00:00Z","author":[{"last_name":"Rieckh","id":"34DA8BD6-F248-11E8-B48F-1D18A9856A87","first_name":"Georg","full_name":"Rieckh, Georg"}],"page":"114","publisher":"Institute of Science and Technology Austria","language":[{"iso":"eng"}],"article_processing_charge":"No","has_accepted_license":"1","_id":"1128","OA_place":"publisher","alternative_title":["ISTA Thesis"],"file_date_updated":"2020-09-21T11:30:40Z","ddc":["570"],"date_created":"2018-12-11T11:50:18Z","publication_identifier":{"issn":["2663-337X"]},"degree_awarded":"PhD","file":[{"access_level":"closed","date_created":"2019-08-13T11:46:25Z","content_type":"application/pdf","creator":"dernst","file_size":2614660,"file_name":"Thesis_Georg_Rieckh_w_signature_page.pdf","date_updated":"2019-08-13T11:46:25Z","file_id":"6815","checksum":"ec453918c3bf8e6f460fd1156ef7b493","relation":"main_file"},{"file_name":"Thesis_Georg_Rieckh.pdf","date_updated":"2020-09-21T11:30:40Z","access_level":"open_access","date_created":"2020-09-21T11:30:40Z","content_type":"application/pdf","file_size":6096178,"creator":"dernst","success":1,"relation":"main_file","checksum":"51ae398166370d18fd22478b6365c4da","file_id":"8542"}],"publist_id":"6232","oa":1,"date_updated":"2026-04-08T14:24:58Z","citation":{"ista":"Rieckh G. 2016. Studying the complexities of transcriptional regulation. Institute of Science and Technology Austria.","ama":"Rieckh G. Studying the complexities of transcriptional regulation. 2016.","ieee":"G. Rieckh, “Studying the complexities of transcriptional regulation,” Institute of Science and Technology Austria, 2016.","short":"G. Rieckh, Studying the Complexities of Transcriptional Regulation, Institute of Science and Technology Austria, 2016.","mla":"Rieckh, Georg. <i>Studying the Complexities of Transcriptional Regulation</i>. Institute of Science and Technology Austria, 2016.","chicago":"Rieckh, Georg. “Studying the Complexities of Transcriptional Regulation.” Institute of Science and Technology Austria, 2016.","apa":"Rieckh, G. (2016). <i>Studying the complexities of transcriptional regulation</i>. Institute of Science and Technology Austria."},"title":"Studying the complexities of transcriptional regulation","status":"public","department":[{"_id":"GaTk"}],"oa_version":"Published Version","abstract":[{"text":"The process of gene expression is central to the modern understanding of how cellular systems\r\nfunction. In this process, a special kind of regulatory proteins, called transcription factors,\r\nare important to determine how much protein is produced from a given gene. As biological\r\ninformation is transmitted from transcription factor concentration to mRNA levels to amounts of\r\nprotein, various sources of noise arise and pose limits to the fidelity of intracellular signaling.\r\nThis thesis concerns itself with several aspects of stochastic gene expression: (i) the mathematical\r\ndescription of complex promoters responsible for the stochastic production of biomolecules,\r\n(ii) fundamental limits to information processing the cell faces due to the interference from multiple\r\nfluctuating signals, (iii) how the presence of gene expression noise influences the evolution\r\nof regulatory sequences, (iv) and tools for the experimental study of origins and consequences\r\nof cell-cell heterogeneity, including an application to bacterial stress response systems.","lang":"eng"}],"type":"dissertation","day":"01","corr_author":"1","supervisor":[{"full_name":"Tkacik, Gasper","first_name":"Gasper","id":"3D494DCA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6699-1455","last_name":"Tkacik"}],"publication_status":"published","month":"08","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","year":"2016"},{"degree_awarded":"PhD","publication_identifier":{"issn":["2663-337X"]},"date_created":"2018-12-11T11:50:17Z","ddc":["570"],"file_date_updated":"2021-02-22T11:42:06Z","alternative_title":["ISTA Thesis"],"_id":"1124","OA_place":"publisher","has_accepted_license":"1","language":[{"iso":"eng"}],"article_processing_charge":"No","publisher":"Institute of Science and Technology Austria","page":"129","author":[{"last_name":"Morri","id":"4863116E-F248-11E8-B48F-1D18A9856A87","first_name":"Maurizio","full_name":"Morri, Maurizio"}],"date_published":"2016-03-01T00:00:00Z","month":"03","year":"2016","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publication_status":"published","supervisor":[{"first_name":"Harald L","full_name":"Janovjak, Harald L","orcid":"0000-0002-8023-9315","last_name":"Janovjak","id":"33BA6C30-F248-11E8-B48F-1D18A9856A87"}],"corr_author":"1","day":"01","type":"dissertation","oa_version":"Published Version","department":[{"_id":"HaJa"}],"status":"public","title":"Optical functionalization of human class A orphan G-protein coupled receptors","citation":{"ista":"Morri M. 2016. Optical functionalization of human class A orphan G-protein coupled receptors. Institute of Science and Technology Austria.","ama":"Morri M. Optical functionalization of human class A orphan G-protein coupled receptors. 2016.","ieee":"M. Morri, “Optical functionalization of human class A orphan G-protein coupled receptors,” Institute of Science and Technology Austria, 2016.","short":"M. Morri, Optical Functionalization of Human Class A Orphan G-Protein Coupled Receptors, Institute of Science and Technology Austria, 2016.","chicago":"Morri, Maurizio. “Optical Functionalization of Human Class A Orphan G-Protein Coupled Receptors.” Institute of Science and Technology Austria, 2016.","mla":"Morri, Maurizio. <i>Optical Functionalization of Human Class A Orphan G-Protein Coupled Receptors</i>. Institute of Science and Technology Austria, 2016.","apa":"Morri, M. (2016). <i>Optical functionalization of human class A orphan G-protein coupled receptors</i>. Institute of Science and Technology Austria."},"date_updated":"2026-04-08T14:26:54Z","oa":1,"publist_id":"6236","file":[{"file_id":"6812","checksum":"b439803ac0827cdddd56562a54e3b53b","relation":"main_file","file_size":4785167,"creator":"dernst","date_created":"2019-08-13T10:50:00Z","content_type":"application/pdf","access_level":"closed","file_name":"MORRI_PhD_thesis_FINALPLUSSIGNATURES (2).pdf","date_updated":"2019-08-13T10:50:00Z"},{"date_updated":"2021-02-22T11:42:06Z","file_name":"2016_MORRI_Thesis.pdf","creator":"dernst","file_size":4495669,"date_created":"2021-02-22T11:42:06Z","content_type":"application/pdf","access_level":"open_access","success":1,"relation":"main_file","checksum":"dd4136247fe472e7d47880ec68ac8de0","file_id":"9180"}]},{"oa":1,"publist_id":"6238","has_accepted_license":"1","date_updated":"2026-04-08T14:24:05Z","pubrep_id":"640","publisher":"Institute of Science and Technology Austria","article_processing_charge":"No","date_published":"2016-09-23T00:00:00Z","author":[{"last_name":"Bojsen-Hansen","orcid":"0000-0002-4417-3224","id":"439F0C8C-F248-11E8-B48F-1D18A9856A87","first_name":"Morten","full_name":"Bojsen-Hansen, Morten"}],"file":[{"access_level":"open_access","content_type":"application/x-bzip2","date_created":"2018-12-12T13:02:18Z","creator":"system","file_size":55237885,"file_name":"IST-2016-48-v1+1_2016_Bojsen-Hansen_TCaAWSW.tar.bz2","date_updated":"2020-07-14T12:47:02Z","checksum":"5b1b256ad796fbddb4b7729f5e45e444","file_id":"5589","relation":"main_file"}],"department":[{"_id":"ChWo"}],"title":"Tracking, Correcting and Absorbing Water Surface Waves","status":"public","_id":"5558","citation":{"mla":"Bojsen-Hansen, Morten. <i>Tracking, Correcting and Absorbing Water Surface Waves</i>. Institute of Science and Technology Austria, 2016, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:48\">10.15479/AT:ISTA:48</a>.","chicago":"Bojsen-Hansen, Morten. “Tracking, Correcting and Absorbing Water Surface Waves.” Institute of Science and Technology Austria, 2016. <a href=\"https://doi.org/10.15479/AT:ISTA:48\">https://doi.org/10.15479/AT:ISTA:48</a>.","apa":"Bojsen-Hansen, M. (2016). Tracking, Correcting and Absorbing Water Surface Waves. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:48\">https://doi.org/10.15479/AT:ISTA:48</a>","ista":"Bojsen-Hansen M. 2016. Tracking, Correcting and Absorbing Water Surface Waves, Institute of Science and Technology Austria, <a href=\"https://doi.org/10.15479/AT:ISTA:48\">10.15479/AT:ISTA:48</a>.","ama":"Bojsen-Hansen M. Tracking, Correcting and Absorbing Water Surface Waves. 2016. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:48\">10.15479/AT:ISTA:48</a>","ieee":"M. Bojsen-Hansen, “Tracking, Correcting and Absorbing Water Surface Waves.” Institute of Science and Technology Austria, 2016.","short":"M. Bojsen-Hansen, (2016)."},"doi":"10.15479/AT:ISTA:48","oa_version":"Published Version","ddc":["004"],"date_created":"2018-12-12T12:31:31Z","datarep_id":"48","file_date_updated":"2020-07-14T12:47:02Z","year":"2016","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"09","day":"23","related_material":{"record":[{"status":"public","id":"1122","relation":"other"}]},"abstract":[{"lang":"eng","text":"PhD thesis LaTeX source code"}],"type":"research_data","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"}},{"arxiv":1,"oa_version":"Preprint","abstract":[{"lang":"eng","text":"We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural problems that arise in program analysis. We consider that each component of the concurrent system is a graph with constant treewidth, a property satisfied by the controlflow graphs of most programs. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis. The study of multiple queries allows us to consider the tradeoff between the resource usage of the one-time preprocessing and for each individual query. The traditional approach constructs the product graph of all components and applies the best-known graph algorithm on the product. In this approach, even the answer to a single query requires the transitive closure (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time. Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time, each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results showing that the worst-case running time of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (i.e., improving the worst-case bound for the shortest path problem in general graphs). Preliminary experimental results show that our algorithms perform favorably on several benchmarks."}],"related_material":{"record":[{"id":"5441","relation":"earlier_version","status":"public"},{"status":"public","relation":"earlier_version","id":"5442"},{"relation":"later_version","id":"6009","status":"public"},{"relation":"dissertation_contains","id":"821","status":"public"},{"status":"public","id":"8934","relation":"dissertation_contains"}]},"type":"conference","day":"11","corr_author":"1","quality_controlled":"1","publication_status":"published","year":"2016","month":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"publist_id":"5761","volume":"20-22","date_updated":"2026-04-08T22:30:58Z","ec_funded":1,"citation":{"ieee":"K. Chatterjee, A. K. Goharshady, R. Ibsen-Jensen, and A. Pavlogiannis, “Algorithms for algebraic path properties in concurrent systems of constant treewidth components,” presented at the POPL: Principles of Programming Languages, St. Petersburg, FL, USA, 2016, vol. 20–22, pp. 733–747.","short":"K. Chatterjee, A.K. Goharshady, R. Ibsen-Jensen, A. Pavlogiannis, in:, ACM, 2016, pp. 733–747.","ista":"Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A. 2016. Algorithms for algebraic path properties in concurrent systems of constant treewidth components. POPL: Principles of Programming Languages, POPL, vol. 20–22, 733–747.","ama":"Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A. Algorithms for algebraic path properties in concurrent systems of constant treewidth components. In: Vol 20-22. ACM; 2016:733-747. doi:<a href=\"https://doi.org/10.1145/2837614.2837624\">10.1145/2837614.2837624</a>","mla":"Chatterjee, Krishnendu, et al. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. Vol. 20–22, ACM, 2016, pp. 733–47, doi:<a href=\"https://doi.org/10.1145/2837614.2837624\">10.1145/2837614.2837624</a>.","chicago":"Chatterjee, Krishnendu, Amir Kafshdar Goharshady, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. “Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components,” 20–22:733–47. ACM, 2016. <a href=\"https://doi.org/10.1145/2837614.2837624\">https://doi.org/10.1145/2837614.2837624</a>.","apa":"Chatterjee, K., Goharshady, A. K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2016). Algorithms for algebraic path properties in concurrent systems of constant treewidth components (Vol. 20–22, pp. 733–747). Presented at the POPL: Principles of Programming Languages, St. Petersburg, FL, USA: ACM. <a href=\"https://doi.org/10.1145/2837614.2837624\">https://doi.org/10.1145/2837614.2837624</a>"},"doi":"10.1145/2837614.2837624","external_id":{"arxiv":["1510.07565"]},"title":"Algorithms for algebraic path properties in concurrent systems of constant treewidth components","status":"public","department":[{"_id":"KrCh"}],"date_created":"2018-12-11T11:52:01Z","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1510.07565"}],"date_published":"2016-01-11T00:00:00Z","page":"733 - 747","conference":{"name":"POPL: Principles of Programming Languages","location":"St. Petersburg, FL, USA","start_date":"2016-01-20","end_date":"2016-01-22"},"author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"391365CE-F248-11E8-B48F-1D18A9856A87","last_name":"Goharshady","orcid":"0000-0003-1702-6584","full_name":"Goharshady, Amir","first_name":"Amir"},{"full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","first_name":"Andreas"}],"publisher":"ACM","language":[{"iso":"eng"}],"_id":"1437","project":[{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"alternative_title":["POPL"],"scopus_import":1},{"alternative_title":["LNCS"],"project":[{"grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Reactive Modeling"}],"scopus_import":"1","_id":"1386","publisher":"Springer","article_processing_charge":"No","language":[{"iso":"eng"}],"date_published":"2016-07-01T00:00:00Z","page":"3 - 22","author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"3AAD03D6-F248-11E8-B48F-1D18A9856A87","last_name":"Fu","full_name":"Fu, Hongfei","first_name":"Hongfei"},{"last_name":"Goharshady","orcid":"0000-0003-1702-6584","id":"391365CE-F248-11E8-B48F-1D18A9856A87","first_name":"Amir","full_name":"Goharshady, Amir"}],"conference":{"name":"CAV: Computer Aided Verification","location":"Toronto, Canada","end_date":"2016-07-23","start_date":"2016-07-17"},"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1604.07169"}],"isi":1,"date_created":"2018-12-11T11:51:43Z","title":"Termination analysis of probabilistic programs through Positivstellensatz's","external_id":{"arxiv":["1604.07169"],"isi":["000387731200001"]},"status":"public","department":[{"_id":"KrCh"}],"ec_funded":1,"citation":{"apa":"Chatterjee, K., Fu, H., &#38; Goharshady, A. K. (2016). Termination analysis of probabilistic programs through Positivstellensatz’s (Vol. 9779, pp. 3–22). Presented at the CAV: Computer Aided Verification, Toronto, Canada: Springer. <a href=\"https://doi.org/10.1007/978-3-319-41528-4_1\">https://doi.org/10.1007/978-3-319-41528-4_1</a>","mla":"Chatterjee, Krishnendu, et al. <i>Termination Analysis of Probabilistic Programs through Positivstellensatz’s</i>. Vol. 9779, Springer, 2016, pp. 3–22, doi:<a href=\"https://doi.org/10.1007/978-3-319-41528-4_1\">10.1007/978-3-319-41528-4_1</a>.","chicago":"Chatterjee, Krishnendu, Hongfei Fu, and Amir Kafshdar Goharshady. “Termination Analysis of Probabilistic Programs through Positivstellensatz’s,” 9779:3–22. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-41528-4_1\">https://doi.org/10.1007/978-3-319-41528-4_1</a>.","short":"K. Chatterjee, H. Fu, A.K. Goharshady, in:, Springer, 2016, pp. 3–22.","ieee":"K. Chatterjee, H. Fu, and A. K. Goharshady, “Termination analysis of probabilistic programs through Positivstellensatz’s,” presented at the CAV: Computer Aided Verification, Toronto, Canada, 2016, vol. 9779, pp. 3–22.","ama":"Chatterjee K, Fu H, Goharshady AK. Termination analysis of probabilistic programs through Positivstellensatz’s. In: Vol 9779. Springer; 2016:3-22. doi:<a href=\"https://doi.org/10.1007/978-3-319-41528-4_1\">10.1007/978-3-319-41528-4_1</a>","ista":"Chatterjee K, Fu H, Goharshady AK. 2016. Termination analysis of probabilistic programs through Positivstellensatz’s. CAV: Computer Aided Verification, LNCS, vol. 9779, 3–22."},"doi":"10.1007/978-3-319-41528-4_1","volume":9779,"publist_id":"5824","oa":1,"date_updated":"2026-04-08T22:30:58Z","intvolume":"      9779","publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","year":"2016","month":"07","abstract":[{"lang":"eng","text":"We consider nondeterministic probabilistic programs with the most basic liveness property of termination. We present efficient methods for termination analysis of nondeterministic probabilistic programs with polynomial guards and assignments. Our approach is through synthesis of polynomial ranking supermartingales, that on one hand significantly generalizes linear ranking supermartingales and on the other hand is a counterpart of polynomial ranking-functions for proving termination of nonprobabilistic programs. The approach synthesizes polynomial ranking-supermartingales through Positivstellensatz's, yielding an efficient method which is not only sound, but also semi-complete over a large subclass of programs. We show experimental results to demonstrate that our approach can handle several classical programs with complex polynomial guards and assignments, and can synthesize efficient quadratic ranking-supermartingales when a linear one does not exist even for simple affine programs."}],"related_material":{"record":[{"id":"8934","relation":"dissertation_contains","status":"public"}]},"type":"conference","day":"01","corr_author":"1","quality_controlled":"1","oa_version":"Preprint","arxiv":1}]