[{"abstract":[{"lang":"eng","text":"A search problem lies in the complexity class FNP if a solution to the given instance of the problem can be verified efficiently. The complexity class TFNP consists of all search problems in FNP that are total in the sense that a solution is guaranteed to exist. TFNP contains a host of interesting problems from fields such as algorithmic game theory, computational topology, number theory and combinatorics. Since TFNP is a semantic class, it is unlikely to have a complete problem. Instead, one studies its syntactic subclasses which are defined based on the combinatorial principle used to argue totality. Of particular interest is the subclass PPAD, which contains important problems\r\nlike computing Nash equilibrium for bimatrix games and computational counterparts of several fixed-point theorems as complete. In the thesis, we undertake the study of averagecase hardness of TFNP, and in particular its subclass PPAD.\r\nAlmost nothing was known about average-case hardness of PPAD before a series of recent results showed how to achieve it using a cryptographic primitive called program obfuscation.\r\nHowever, it is currently not known how to construct program obfuscation from standard cryptographic assumptions. Therefore, it is desirable to relax the assumption under which average-case hardness of PPAD can be shown. In the thesis we take a step in this direction. First, we show that assuming the (average-case) hardness of a numbertheoretic\r\nproblem related to factoring of integers, which we call Iterated-Squaring, PPAD is hard-on-average in the random-oracle model. Then we strengthen this result to show that the average-case hardness of PPAD reduces to the (adaptive) soundness of the Fiat-Shamir Transform, a well-known technique used to compile a public-coin interactive protocol into a non-interactive one. As a corollary, we obtain average-case hardness for PPAD in the random-oracle model assuming the worst-case hardness of #SAT. Moreover, the above results can all be strengthened to obtain average-case hardness for the class CLS ⊆ PPAD.\r\nOur main technical contribution is constructing incrementally-verifiable procedures for computing Iterated-Squaring and #SAT. By incrementally-verifiable, we mean that every intermediate state of the computation includes a proof of its correctness, and the proof can be updated and verified in polynomial time. Previous constructions of such procedures relied on strong, non-standard assumptions. Instead, we introduce a technique called recursive proof-merging to obtain the same from weaker assumptions. "}],"oa_version":"Published Version","alternative_title":["ISTA Thesis"],"month":"05","publication_identifier":{"issn":["2663-337X"]},"degree_awarded":"PhD","publication_status":"published","file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"7897","checksum":"b39e2e1c376f5819b823fb7077491c64","creator":"dernst","date_updated":"2020-07-14T12:48:04Z","file_size":1622742,"date_created":"2020-05-26T14:08:13Z","file_name":"2020_Thesis_Kamath.pdf"},{"access_level":"closed","relation":"source_file","content_type":"application/x-zip-compressed","checksum":"8b26ba729c1a85ac6bea775f5d73cdc7","file_id":"7898","creator":"dernst","date_updated":"2020-07-14T12:48:04Z","file_size":15301529,"date_created":"2020-05-26T14:08:23Z","file_name":"Thesis_Kamath.zip"}],"language":[{"iso":"eng"}],"related_material":{"record":[{"id":"6677","status":"public","relation":"part_of_dissertation"}]},"ec_funded":1,"_id":"7896","type":"dissertation","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","supervisor":[{"full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"}],"date_updated":"2023-09-07T13:15:55Z","ddc":["000"],"department":[{"_id":"KrPi"}],"file_date_updated":"2020-07-14T12:48:04Z","publisher":"Institute of Science and Technology Austria","oa":1,"has_accepted_license":"1","year":"2020","day":"25","page":"126","date_published":"2020-05-25T00:00:00Z","doi":"10.15479/AT:ISTA:7896","date_created":"2020-05-26T14:08:55Z","project":[{"grant_number":"259668","name":"Provable Security for Physical Cryptography","call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425"},{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"citation":{"ista":"Kamath Hosdurg C. 2020. On the average-case hardness of total search problems. Institute of Science and Technology Austria.","chicago":"Kamath Hosdurg, Chethan. “On the Average-Case Hardness of Total Search Problems.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7896.","short":"C. Kamath Hosdurg, On the Average-Case Hardness of Total Search Problems, Institute of Science and Technology Austria, 2020.","ieee":"C. Kamath Hosdurg, “On the average-case hardness of total search problems,” Institute of Science and Technology Austria, 2020.","ama":"Kamath Hosdurg C. On the average-case hardness of total search problems. 2020. doi:10.15479/AT:ISTA:7896","apa":"Kamath Hosdurg, C. (2020). On the average-case hardness of total search problems. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:7896","mla":"Kamath Hosdurg, Chethan. On the Average-Case Hardness of Total Search Problems. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7896."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg"}],"article_processing_charge":"No","title":"On the average-case hardness of total search problems"},{"date_updated":"2023-09-07T13:16:17Z","department":[{"_id":"ChLa"}],"_id":"7936","type":"conference","conference":{"name":"WACV: Winter Conference on Applications of Computer Vision","location":" Snowmass Village, CO, United States","end_date":"2020-03-05","start_date":"2020-03-01"},"status":"public","publication_identifier":{"isbn":["9781728165530"]},"publication_status":"published","language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"dissertation_contains","status":"deleted","id":"8331"},{"relation":"dissertation_contains","status":"public","id":"8390"}]},"abstract":[{"lang":"eng","text":"State-of-the-art detection systems are generally evaluated on their ability to exhaustively retrieve objects densely distributed in the image, across a wide variety of appearances and semantic categories. Orthogonal to this, many real-life object detection applications, for example in remote sensing, instead require dealing with large images that contain only a few small objects of a single class, scattered heterogeneously across the space. In addition, they are often subject to strict computational constraints, such as limited battery capacity and computing power.To tackle these more practical scenarios, we propose a novel flexible detection scheme that efficiently adapts to variable object sizes and densities: We rely on a sequence of detection stages, each of which has the ability to predict groups of objects as well as individuals. Similar to a detection cascade, this multi-stage architecture spares computational effort by discarding large irrelevant regions of the image early during the detection process. The ability to group objects provides further computational and memory savings, as it allows working with lower image resolutions in early stages, where groups are more easily detected than individuals, as they are more salient. We report experimental results on two aerial image datasets, and show that the proposed method is as accurate yet computationally more efficient than standard single-shot detectors, consistently across three different backbone architectures."}],"oa_version":"Preprint","scopus_import":1,"main_file_link":[{"url":"https://arxiv.org/abs/2004.12623","open_access":"1"}],"month":"03","citation":{"ama":"Royer A, Lampert C. Localizing grouped instances for efficient detection in low-resource scenarios. In: IEEE Winter Conference on Applications of Computer Vision. IEEE; 2020. doi:10.1109/WACV45572.2020.9093288","apa":"Royer, A., & Lampert, C. (2020). Localizing grouped instances for efficient detection in low-resource scenarios. In IEEE Winter Conference on Applications of Computer Vision. Snowmass Village, CO, United States: IEEE. https://doi.org/10.1109/WACV45572.2020.9093288","short":"A. Royer, C. Lampert, in:, IEEE Winter Conference on Applications of Computer Vision, IEEE, 2020.","ieee":"A. Royer and C. Lampert, “Localizing grouped instances for efficient detection in low-resource scenarios,” in IEEE Winter Conference on Applications of Computer Vision, Snowmass Village, CO, United States, 2020.","mla":"Royer, Amélie, and Christoph Lampert. “Localizing Grouped Instances for Efficient Detection in Low-Resource Scenarios.” IEEE Winter Conference on Applications of Computer Vision, 1716–1725, IEEE, 2020, doi:10.1109/WACV45572.2020.9093288.","ista":"Royer A, Lampert C. 2020. Localizing grouped instances for efficient detection in low-resource scenarios. IEEE Winter Conference on Applications of Computer Vision. WACV: Winter Conference on Applications of Computer Vision, 1716–1725.","chicago":"Royer, Amélie, and Christoph Lampert. “Localizing Grouped Instances for Efficient Detection in Low-Resource Scenarios.” In IEEE Winter Conference on Applications of Computer Vision. IEEE, 2020. https://doi.org/10.1109/WACV45572.2020.9093288."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Amélie","id":"3811D890-F248-11E8-B48F-1D18A9856A87","full_name":"Royer, Amélie","orcid":"0000-0002-8407-0705","last_name":"Royer"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","first_name":"Christoph","last_name":"Lampert","full_name":"Lampert, Christoph","orcid":"0000-0001-8622-7887"}],"article_processing_charge":"No","external_id":{"arxiv":["2004.12623"]},"title":"Localizing grouped instances for efficient detection in low-resource scenarios","article_number":"1716-1725","year":"2020","day":"01","publication":"IEEE Winter Conference on Applications of Computer Vision","date_published":"2020-03-01T00:00:00Z","doi":"10.1109/WACV45572.2020.9093288","date_created":"2020-06-07T22:00:53Z","quality_controlled":"1","publisher":"IEEE","oa":1},{"month":"03","scopus_import":"1","main_file_link":[{"url":"http://arxiv.org/abs/2008.11995","open_access":"1"}],"oa_version":"Preprint","abstract":[{"text":"Fine-tuning is a popular way of exploiting knowledge contained in a pre-trained convolutional network for a new visual recognition task. However, the orthogonal setting of transferring knowledge from a pretrained network to a visually different yet semantically close source is rarely considered: This commonly happens with real-life data, which is not necessarily as clean as the training source (noise, geometric transformations, different modalities, etc.).To tackle such scenarios, we introduce a new, generalized form of fine-tuning, called flex-tuning, in which any individual unit (e.g. layer) of a network can be tuned, and the most promising one is chosen automatically. In order to make the method appealing for practical use, we propose two lightweight and faster selection procedures that prove to be good approximations in practice. We study these selection criteria empirically across a variety of domain shifts and data scarcity scenarios, and show that fine-tuning individual units, despite its simplicity, yields very good results as an adaptation technique. As it turns out, in contrast to common practice, rather than the last fully-connected unit it is best to tune an intermediate or early one in many domain- shift scenarios, which is accurately detected by flex-tuning.","lang":"eng"}],"related_material":{"record":[{"relation":"dissertation_contains","id":"8331","status":"deleted"},{"status":"public","id":"8390","relation":"dissertation_contains"}]},"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9781728165530"]},"publication_status":"published","status":"public","type":"conference","conference":{"name":"WACV: Winter Conference on Applications of Computer Vision","start_date":"2020-03-01","end_date":"2020-03-05","location":"Snowmass Village, CO, United States"},"_id":"7937","department":[{"_id":"ChLa"}],"date_updated":"2023-09-07T13:16:17Z","publisher":"IEEE","quality_controlled":"1","oa":1,"doi":"10.1109/WACV45572.2020.9093635","date_published":"2020-03-01T00:00:00Z","date_created":"2020-06-07T22:00:53Z","day":"01","publication":"2020 IEEE Winter Conference on Applications of Computer Vision","year":"2020","article_number":"2180-2189","title":"A flexible selection scheme for minimum-effort transfer learning","author":[{"full_name":"Royer, Amélie","orcid":"0000-0002-8407-0705","last_name":"Royer","id":"3811D890-F248-11E8-B48F-1D18A9856A87","first_name":"Amélie"},{"first_name":"Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","last_name":"Lampert","orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph"}],"external_id":{"arxiv":["2008.11995"]},"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Royer, Amélie, and Christoph Lampert. “A Flexible Selection Scheme for Minimum-Effort Transfer Learning.” In 2020 IEEE Winter Conference on Applications of Computer Vision. IEEE, 2020. https://doi.org/10.1109/WACV45572.2020.9093635.","ista":"Royer A, Lampert C. 2020. A flexible selection scheme for minimum-effort transfer learning. 2020 IEEE Winter Conference on Applications of Computer Vision. WACV: Winter Conference on Applications of Computer Vision, 2180–2189.","mla":"Royer, Amélie, and Christoph Lampert. “A Flexible Selection Scheme for Minimum-Effort Transfer Learning.” 2020 IEEE Winter Conference on Applications of Computer Vision, 2180–2189, IEEE, 2020, doi:10.1109/WACV45572.2020.9093635.","ama":"Royer A, Lampert C. A flexible selection scheme for minimum-effort transfer learning. In: 2020 IEEE Winter Conference on Applications of Computer Vision. IEEE; 2020. doi:10.1109/WACV45572.2020.9093635","apa":"Royer, A., & Lampert, C. (2020). A flexible selection scheme for minimum-effort transfer learning. In 2020 IEEE Winter Conference on Applications of Computer Vision. Snowmass Village, CO, United States: IEEE. https://doi.org/10.1109/WACV45572.2020.9093635","ieee":"A. Royer and C. Lampert, “A flexible selection scheme for minimum-effort transfer learning,” in 2020 IEEE Winter Conference on Applications of Computer Vision, Snowmass Village, CO, United States, 2020.","short":"A. Royer, C. Lampert, in:, 2020 IEEE Winter Conference on Applications of Computer Vision, IEEE, 2020."}},{"acknowledgement":"Krishnendu Chatterjee is supported by the Austrian ScienceFund (FWF) NFN Grant No. S11407-N23 (RiSE/SHiNE),and COST Action GAMENET. Petr Novotn ́y is supported bythe Czech Science Foundation grant No. GJ19-15134Y.","publisher":"Association for the Advancement of Artificial Intelligence","quality_controlled":"1","year":"2020","publication":"Proceedings of the 30th International Conference on Automated Planning and Scheduling","day":"01","page":"48-56","date_created":"2020-08-02T22:00:58Z","date_published":"2020-06-01T00:00:00Z","project":[{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407"}],"citation":{"ista":"Chatterjee K, Chmelik M, Karkhanis D, Novotný P, Royer A. 2020. Multiple-environment Markov decision processes: Efficient analysis and applications. Proceedings of the 30th International Conference on Automated Planning and Scheduling. ICAPS: International Conference on Automated Planning and Scheduling vol. 30, 48–56.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, Deep Karkhanis, Petr Novotný, and Amélie Royer. “Multiple-Environment Markov Decision Processes: Efficient Analysis and Applications.” In Proceedings of the 30th International Conference on Automated Planning and Scheduling, 30:48–56. Association for the Advancement of Artificial Intelligence, 2020.","ieee":"K. Chatterjee, M. Chmelik, D. Karkhanis, P. Novotný, and A. Royer, “Multiple-environment Markov decision processes: Efficient analysis and applications,” in Proceedings of the 30th International Conference on Automated Planning and Scheduling, Nancy, France, 2020, vol. 30, pp. 48–56.","short":"K. Chatterjee, M. Chmelik, D. Karkhanis, P. Novotný, A. Royer, in:, Proceedings of the 30th International Conference on Automated Planning and Scheduling, Association for the Advancement of Artificial Intelligence, 2020, pp. 48–56.","ama":"Chatterjee K, Chmelik M, Karkhanis D, Novotný P, Royer A. Multiple-environment Markov decision processes: Efficient analysis and applications. In: Proceedings of the 30th International Conference on Automated Planning and Scheduling. Vol 30. Association for the Advancement of Artificial Intelligence; 2020:48-56.","apa":"Chatterjee, K., Chmelik, M., Karkhanis, D., Novotný, P., & Royer, A. (2020). Multiple-environment Markov decision processes: Efficient analysis and applications. In Proceedings of the 30th International Conference on Automated Planning and Scheduling (Vol. 30, pp. 48–56). Nancy, France: Association for the Advancement of Artificial Intelligence.","mla":"Chatterjee, Krishnendu, et al. “Multiple-Environment Markov Decision Processes: Efficient Analysis and Applications.” Proceedings of the 30th International Conference on Automated Planning and Scheduling, vol. 30, Association for the Advancement of Artificial Intelligence, 2020, pp. 48–56."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"last_name":"Chmelik","full_name":"Chmelik, Martin","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Karkhanis, Deep","last_name":"Karkhanis","first_name":"Deep"},{"full_name":"Novotný, Petr","last_name":"Novotný","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","first_name":"Petr"},{"first_name":"Amélie","id":"3811D890-F248-11E8-B48F-1D18A9856A87","last_name":"Royer","orcid":"0000-0002-8407-0705","full_name":"Royer, Amélie"}],"title":"Multiple-environment Markov decision processes: Efficient analysis and applications","abstract":[{"text":"Multiple-environment Markov decision processes (MEMDPs) are MDPs equipped with not one, but multiple probabilistic transition functions, which represent the various possible unknown environments. While the previous research on MEMDPs focused on theoretical properties for long-run average payoff, we study them with discounted-sum payoff and focus on their practical advantages and applications. MEMDPs can be viewed as a special case of Partially observable and Mixed observability MDPs: the state of the system is perfectly observable, but not the environment. We show that the specific structure of MEMDPs allows for more efficient algorithmic analysis, in particular for faster belief updates. We demonstrate the applicability of MEMDPs in several domains. In particular, we formalize the sequential decision-making approach to contextual recommendation systems as MEMDPs and substantially improve over the previous MDP approach.","lang":"eng"}],"oa_version":"None","scopus_import":"1","intvolume":" 30","month":"06","publication_status":"published","publication_identifier":{"issn":["23340835"],"eissn":["23340843"]},"language":[{"iso":"eng"}],"volume":30,"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"8390"}]},"_id":"8193","conference":{"name":"ICAPS: International Conference on Automated Planning and Scheduling","start_date":"2020-10-26","location":"Nancy, France","end_date":"2020-10-30"},"type":"conference","status":"public","date_updated":"2023-09-07T13:16:18Z","department":[{"_id":"KrCh"}]},{"department":[{"_id":"ChLa"}],"date_updated":"2023-09-07T13:16:18Z","type":"book_chapter","status":"public","_id":"8092","related_material":{"record":[{"relation":"dissertation_contains","status":"deleted","id":"8331"},{"relation":"dissertation_contains","status":"public","id":"8390"}]},"publication_status":"published","publication_identifier":{"isbn":["9783030306717"]},"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1711.05139"}],"scopus_import":"1","month":"01","abstract":[{"lang":"eng","text":"Image translation refers to the task of mapping images from a visual domain to another. Given two unpaired collections of images, we aim to learn a mapping between the corpus-level style of each collection, while preserving semantic content shared across the two domains. We introduce xgan, a dual adversarial auto-encoder, which captures a shared representation of the common domain semantic content in an unsupervised way, while jointly learning the domain-to-domain image translations in both directions. We exploit ideas from the domain adaptation literature and define a semantic consistency loss which encourages the learned embedding to preserve semantics shared across domains. We report promising qualitative results for the task of face-to-cartoon translation. The cartoon dataset we collected for this purpose, “CartoonSet”, is also publicly available as a new benchmark for semantic style transfer at https://google.github.io/cartoonset/index.html."}],"oa_version":"Preprint","external_id":{"arxiv":["1711.05139"]},"article_processing_charge":"No","author":[{"orcid":"0000-0002-8407-0705","full_name":"Royer, Amélie","last_name":"Royer","id":"3811D890-F248-11E8-B48F-1D18A9856A87","first_name":"Amélie"},{"first_name":"Konstantinos","last_name":"Bousmalis","full_name":"Bousmalis, Konstantinos"},{"first_name":"Stephan","full_name":"Gouws, Stephan","last_name":"Gouws"},{"first_name":"Fred","full_name":"Bertsch, Fred","last_name":"Bertsch"},{"full_name":"Mosseri, Inbar","last_name":"Mosseri","first_name":"Inbar"},{"full_name":"Cole, Forrester","last_name":"Cole","first_name":"Forrester"},{"full_name":"Murphy, Kevin","last_name":"Murphy","first_name":"Kevin"}],"title":"XGAN: Unsupervised image-to-image translation for many-to-many mappings","editor":[{"first_name":"Richa","full_name":"Singh, Richa","last_name":"Singh"},{"last_name":"Vatsa","full_name":"Vatsa, Mayank","first_name":"Mayank"},{"first_name":"Vishal M.","last_name":"Patel","full_name":"Patel, Vishal M."},{"full_name":"Ratha, Nalini","last_name":"Ratha","first_name":"Nalini"}],"citation":{"chicago":"Royer, Amélie, Konstantinos Bousmalis, Stephan Gouws, Fred Bertsch, Inbar Mosseri, Forrester Cole, and Kevin Murphy. “XGAN: Unsupervised Image-to-Image Translation for Many-to-Many Mappings.” In Domain Adaptation for Visual Understanding, edited by Richa Singh, Mayank Vatsa, Vishal M. Patel, and Nalini Ratha, 33–49. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-30671-7_3.","ista":"Royer A, Bousmalis K, Gouws S, Bertsch F, Mosseri I, Cole F, Murphy K. 2020.XGAN: Unsupervised image-to-image translation for many-to-many mappings. In: Domain Adaptation for Visual Understanding. , 33–49.","mla":"Royer, Amélie, et al. “XGAN: Unsupervised Image-to-Image Translation for Many-to-Many Mappings.” Domain Adaptation for Visual Understanding, edited by Richa Singh et al., Springer Nature, 2020, pp. 33–49, doi:10.1007/978-3-030-30671-7_3.","short":"A. Royer, K. Bousmalis, S. Gouws, F. Bertsch, I. Mosseri, F. Cole, K. Murphy, in:, R. Singh, M. Vatsa, V.M. Patel, N. Ratha (Eds.), Domain Adaptation for Visual Understanding, Springer Nature, 2020, pp. 33–49.","ieee":"A. Royer et al., “XGAN: Unsupervised image-to-image translation for many-to-many mappings,” in Domain Adaptation for Visual Understanding, R. Singh, M. Vatsa, V. M. Patel, and N. Ratha, Eds. Springer Nature, 2020, pp. 33–49.","ama":"Royer A, Bousmalis K, Gouws S, et al. XGAN: Unsupervised image-to-image translation for many-to-many mappings. In: Singh R, Vatsa M, Patel VM, Ratha N, eds. Domain Adaptation for Visual Understanding. Springer Nature; 2020:33-49. doi:10.1007/978-3-030-30671-7_3","apa":"Royer, A., Bousmalis, K., Gouws, S., Bertsch, F., Mosseri, I., Cole, F., & Murphy, K. (2020). XGAN: Unsupervised image-to-image translation for many-to-many mappings. In R. Singh, M. Vatsa, V. M. Patel, & N. Ratha (Eds.), Domain Adaptation for Visual Understanding (pp. 33–49). Springer Nature. https://doi.org/10.1007/978-3-030-30671-7_3"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"33-49","date_created":"2020-07-05T22:00:46Z","date_published":"2020-01-08T00:00:00Z","doi":"10.1007/978-3-030-30671-7_3","year":"2020","publication":"Domain Adaptation for Visual Understanding","day":"08","oa":1,"publisher":"Springer Nature","quality_controlled":"1"},{"file_date_updated":"2020-07-14T12:48:05Z","department":[{"_id":"HeEd"},{"_id":"UlWa"}],"ddc":["516","514"],"date_updated":"2023-09-07T13:17:37Z","supervisor":[{"last_name":"Wagner","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert"}],"keyword":["reconfiguration","reconfiguration graph","triangulations","flip","constrained triangulations","shellability","piecewise-linear balls","token swapping","trees","coloured weighted token swapping"],"status":"public","tmp":{"short":"CC BY-SA (4.0)","image":"/images/cc_by_sa.png","legal_code_url":"https://creativecommons.org/licenses/by-sa/4.0/legalcode","name":"Creative Commons Attribution-ShareAlike 4.0 International Public License (CC BY-SA 4.0)"},"type":"dissertation","_id":"7944","license":"https://creativecommons.org/licenses/by-sa/4.0/","related_material":{"record":[{"relation":"part_of_dissertation","id":"7950","status":"public"},{"id":"5986","status":"public","relation":"part_of_dissertation"}]},"language":[{"iso":"eng"}],"file":[{"creator":"zmasarov","date_updated":"2020-07-14T12:48:05Z","file_size":13661779,"date_created":"2020-06-08T00:34:00Z","file_name":"THESIS_Zuzka_Masarova.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"7945","checksum":"df688bc5a82b50baee0b99d25fc7b7f0"},{"file_name":"THESIS_Zuzka_Masarova_SOURCE_FILES.zip","date_created":"2020-06-08T00:35:30Z","file_size":32184006,"date_updated":"2020-07-14T12:48:05Z","creator":"zmasarov","checksum":"45341a35b8f5529c74010b7af43ac188","file_id":"7946","content_type":"application/zip","relation":"source_file","access_level":"closed"}],"publication_status":"published","degree_awarded":"PhD","publication_identifier":{"isbn":["978-3-99078-005-3"],"issn":["2663-337X"]},"month":"06","alternative_title":["ISTA Thesis"],"oa_version":"Published Version","abstract":[{"text":"This thesis considers two examples of reconfiguration problems: flipping edges in edge-labelled triangulations of planar point sets and swapping labelled tokens placed on vertices of a graph. In both cases the studied structures – all the triangulations of a given point set or all token placements on a given graph – can be thought of as vertices of the so-called reconfiguration graph, in which two vertices are adjacent if the corresponding structures differ by a single elementary operation – by a flip of a diagonal in a triangulation or by a swap of tokens on adjacent vertices, respectively. We study the reconfiguration of one instance of a structure into another via (shortest) paths in the reconfiguration graph.\r\n\r\nFor triangulations of point sets in which each edge has a unique label and a flip transfers the label from the removed edge to the new edge, we prove a polynomial-time testable condition, called the Orbit Theorem, that characterizes when two triangulations of the same point set lie in the same connected component of the reconfiguration graph. The condition was first conjectured by Bose, Lubiw, Pathak and Verdonschot. We additionally provide a polynomial time algorithm that computes a reconfiguring flip sequence, if it exists. Our proof of the Orbit Theorem uses topological properties of a certain high-dimensional cell complex that has the usual reconfiguration graph as its 1-skeleton.\r\n\r\nIn the context of token swapping on a tree graph, we make partial progress on the problem of finding shortest reconfiguration sequences. We disprove the so-called Happy Leaf Conjecture and demonstrate the importance of swapping tokens that are already placed at the correct vertices. We also prove that a generalization of the problem to weighted coloured token swapping is NP-hard on trees but solvable in polynomial time on paths and stars.","lang":"eng"}],"title":"Reconfiguration problems","article_processing_charge":"No","author":[{"orcid":"0000-0002-6660-1322","full_name":"Masárová, Zuzana","last_name":"Masárová","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"mla":"Masárová, Zuzana. Reconfiguration Problems. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7944.","ama":"Masárová Z. Reconfiguration problems. 2020. doi:10.15479/AT:ISTA:7944","apa":"Masárová, Z. (2020). Reconfiguration problems. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:7944","short":"Z. Masárová, Reconfiguration Problems, Institute of Science and Technology Austria, 2020.","ieee":"Z. Masárová, “Reconfiguration problems,” Institute of Science and Technology Austria, 2020.","chicago":"Masárová, Zuzana. “Reconfiguration Problems.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7944.","ista":"Masárová Z. 2020. Reconfiguration problems. Institute of Science and Technology Austria."},"date_created":"2020-06-08T00:49:46Z","date_published":"2020-06-09T00:00:00Z","doi":"10.15479/AT:ISTA:7944","page":"160","day":"09","year":"2020","has_accepted_license":"1","oa":1,"publisher":"Institute of Science and Technology Austria"},{"project":[{"call_identifier":"FWF","_id":"26031614-B435-11E9-9278-68D0E5697425","name":"Quantum rotations in the presence of a many-body environment","grant_number":"P29902"},{"grant_number":"801770","name":"Angulon: physics and applications of a new quasiparticle","call_identifier":"H2020","_id":"2688CF98-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"26986C82-B435-11E9-9278-68D0E5697425","grant_number":"M02641","name":"A path-integral approach to composite impurities"},{"grant_number":"694227","name":"Analysis of quantum many-body systems","_id":"25C6DC12-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"article_number":"164302","title":"Intermolecular forces and correlations mediated by a phonon bath","external_id":{"arxiv":["1912.02658"],"isi":["000530448300001"]},"article_processing_charge":"No","author":[{"last_name":"Li","full_name":"Li, Xiang","first_name":"Xiang","id":"4B7E523C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Enderalp","id":"38CB71F6-F248-11E8-B48F-1D18A9856A87","full_name":"Yakaboylu, Enderalp","orcid":"0000-0001-5973-0874","last_name":"Yakaboylu"},{"first_name":"Giacomo","id":"4CA96FD4-F248-11E8-B48F-1D18A9856A87","full_name":"Bighin, Giacomo","orcid":"0000-0001-8823-9777","last_name":"Bighin"},{"full_name":"Schmidt, Richard","last_name":"Schmidt","first_name":"Richard"},{"id":"37CB05FA-F248-11E8-B48F-1D18A9856A87","first_name":"Mikhail","full_name":"Lemeshko, Mikhail","orcid":"0000-0002-6990-7802","last_name":"Lemeshko"},{"orcid":"0000-0003-3146-6746","full_name":"Deuchert, Andreas","last_name":"Deuchert","id":"4DA65CD0-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"chicago":"Li, Xiang, Enderalp Yakaboylu, Giacomo Bighin, Richard Schmidt, Mikhail Lemeshko, and Andreas Deuchert. “Intermolecular Forces and Correlations Mediated by a Phonon Bath.” The Journal of Chemical Physics. AIP Publishing, 2020. https://doi.org/10.1063/1.5144759.","ista":"Li X, Yakaboylu E, Bighin G, Schmidt R, Lemeshko M, Deuchert A. 2020. Intermolecular forces and correlations mediated by a phonon bath. The Journal of Chemical Physics. 152(16), 164302.","mla":"Li, Xiang, et al. “Intermolecular Forces and Correlations Mediated by a Phonon Bath.” The Journal of Chemical Physics, vol. 152, no. 16, 164302, AIP Publishing, 2020, doi:10.1063/1.5144759.","ama":"Li X, Yakaboylu E, Bighin G, Schmidt R, Lemeshko M, Deuchert A. Intermolecular forces and correlations mediated by a phonon bath. The Journal of Chemical Physics. 2020;152(16). doi:10.1063/1.5144759","apa":"Li, X., Yakaboylu, E., Bighin, G., Schmidt, R., Lemeshko, M., & Deuchert, A. (2020). Intermolecular forces and correlations mediated by a phonon bath. The Journal of Chemical Physics. AIP Publishing. https://doi.org/10.1063/1.5144759","ieee":"X. Li, E. Yakaboylu, G. Bighin, R. Schmidt, M. Lemeshko, and A. Deuchert, “Intermolecular forces and correlations mediated by a phonon bath,” The Journal of Chemical Physics, vol. 152, no. 16. AIP Publishing, 2020.","short":"X. Li, E. Yakaboylu, G. Bighin, R. Schmidt, M. Lemeshko, A. Deuchert, The Journal of Chemical Physics 152 (2020)."},"oa":1,"quality_controlled":"1","publisher":"AIP Publishing","acknowledgement":"We are grateful to Areg Ghazaryan for valuable discussions. M.L. acknowledges support from the Austrian Science Fund (FWF) under Project No. P29902-N27 and from the European Research Council (ERC) Starting Grant No. 801770 (ANGULON). G.B. acknowledges support from the Austrian Science Fund (FWF) under Project No. M2461-N27. A.D. acknowledges funding from the European Union’s Horizon 2020 research and innovation programme under the European Research Council (ERC) Grant Agreement No. 694227 and under the Marie Sklodowska-Curie Grant Agreement No. 836146. R.S. was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – EXC-2111 – 390814868.","date_created":"2020-09-30T10:33:17Z","date_published":"2020-04-27T00:00:00Z","doi":"10.1063/1.5144759","publication":"The Journal of Chemical Physics","day":"27","year":"2020","isi":1,"keyword":["Physical and Theoretical Chemistry","General Physics and Astronomy"],"status":"public","article_type":"original","type":"journal_article","_id":"8587","department":[{"_id":"MiLe"},{"_id":"RoSe"}],"date_updated":"2023-09-07T13:16:42Z","intvolume":" 152","month":"04","main_file_link":[{"url":"https://arxiv.org/abs/1912.02658","open_access":"1"}],"oa_version":"Preprint","abstract":[{"text":"Inspired by the possibility to experimentally manipulate and enhance chemical reactivity in helium nanodroplets, we investigate the effective interaction and the resulting correlations between two diatomic molecules immersed in a bath of bosons. By analogy with the bipolaron, we introduce the biangulon quasiparticle describing two rotating molecules that align with respect to each other due to the effective attractive interaction mediated by the excitations of the bath. We study this system in different parameter regimes and apply several theoretical approaches to describe its properties. Using a Born–Oppenheimer approximation, we investigate the dependence of the effective intermolecular interaction on the rotational state of the two molecules. In the strong-coupling regime, a product-state ansatz shows that the molecules tend to have a strong alignment in the ground state. To investigate the system in the weak-coupling regime, we apply a one-phonon excitation variational ansatz, which allows us to access the energy spectrum. In comparison to the angulon quasiparticle, the biangulon shows shifted angulon instabilities and an additional spectral instability, where resonant angular momentum transfer between the molecules and the bath takes place. These features are proposed as an experimentally observable signature for the formation of the biangulon quasiparticle. Finally, by using products of single angulon and bare impurity wave functions as basis states, we introduce a diagonalization scheme that allows us to describe the transition from two separated angulons to a biangulon as a function of the distance between the two molecules.","lang":"eng"}],"ec_funded":1,"volume":152,"related_material":{"record":[{"id":"8958","status":"public","relation":"dissertation_contains"}]},"issue":"16","language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"eissn":["1089-7690"],"issn":["0021-9606"]}},{"tmp":{"name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)","image":"/images/cc_by_nc_sa.png","legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","short":"CC BY-NC-SA (4.0)"},"type":"dissertation","status":"public","_id":"8341","file_date_updated":"2021-09-16T12:49:12Z","department":[{"_id":"MaLo"}],"date_updated":"2023-09-07T13:17:06Z","supervisor":[{"full_name":"Loose, Martin","orcid":"0000-0001-7309-9724","last_name":"Loose","first_name":"Martin","id":"462D4284-F248-11E8-B48F-1D18A9856A87"}],"ddc":["570"],"alternative_title":["ISTA Thesis"],"month":"09","acknowledged_ssus":[{"_id":"Bio"},{"_id":"LifeSc"},{"_id":"NanoFab"}],"abstract":[{"lang":"eng","text":"One of the most striking hallmarks of the eukaryotic cell is the presence of intracellular vesicles and organelles. Each of these membrane-enclosed compartments has a distinct composition of lipids and proteins, which is essential for accurate membrane traffic and homeostasis. Interestingly, their biochemical identities are achieved with the help\r\nof small GTPases of the Rab family, which cycle between GDP- and GTP-bound forms on the selected membrane surface. While this activity switch is well understood for an individual protein, how Rab GTPases collectively transition between states to generate decisive signal propagation in space and time is unclear. In my PhD thesis, I present\r\nin vitro reconstitution experiments with theoretical modeling to systematically study a minimal Rab5 activation network from bottom-up. We find that positive feedback based on known molecular interactions gives rise to bistable GTPase activity switching on system’s scale. Furthermore, we determine that collective transition near the critical\r\npoint is intrinsically stochastic and provide evidence that the inactive Rab5 abundance on the membrane can shape the network response. Finally, we demonstrate that collective switching can spread on the lipid bilayer as a traveling activation wave, representing a possible emergent activity pattern in endosomal maturation. Together, our\r\nfindings reveal new insights into the self-organization properties of signaling networks away from chemical equilibrium. Our work highlights the importance of systematic characterization of biochemical systems in well-defined physiological conditions. This way, we were able to answer long-standing open questions in the field and close the gap between regulatory processes on a molecular scale and emergent responses on system’s level."}],"oa_version":"Published Version","license":"https://creativecommons.org/licenses/by-nc-sa/4.0/","related_material":{"record":[{"status":"public","id":"7580","relation":"part_of_dissertation"}]},"degree_awarded":"PhD","publication_status":"published","publication_identifier":{"issn":["2663-337X"]},"language":[{"iso":"eng"}],"file":[{"creator":"dernst","date_updated":"2021-09-16T12:49:12Z","file_size":65246782,"date_created":"2020-09-08T09:00:29Z","file_name":"2020_Urban_Bezeljak_Thesis_TeX.zip","access_level":"closed","relation":"source_file","content_type":"application/x-zip-compressed","checksum":"70871b335a595252a66c6bbf0824fb02","file_id":"8342"},{"file_id":"8343","checksum":"59a62275088b00b7241e6ff4136434c7","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_name":"2020_Urban_Bezeljak_Thesis.pdf","date_created":"2020-09-08T09:00:27Z","file_size":31259058,"date_updated":"2021-09-16T12:49:12Z","creator":"dernst"}],"article_processing_charge":"No","author":[{"first_name":"Urban","id":"2A58201A-F248-11E8-B48F-1D18A9856A87","last_name":"Bezeljak","full_name":"Bezeljak, Urban","orcid":"0000-0003-1365-5631"}],"title":"In vitro reconstitution of a Rab activation switch","citation":{"short":"U. Bezeljak, In Vitro Reconstitution of a Rab Activation Switch, Institute of Science and Technology Austria, 2020.","ieee":"U. Bezeljak, “In vitro reconstitution of a Rab activation switch,” Institute of Science and Technology Austria, 2020.","ama":"Bezeljak U. In vitro reconstitution of a Rab activation switch. 2020. doi:10.15479/AT:ISTA:8341","apa":"Bezeljak, U. (2020). In vitro reconstitution of a Rab activation switch. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:8341","mla":"Bezeljak, Urban. In Vitro Reconstitution of a Rab Activation Switch. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:8341.","ista":"Bezeljak U. 2020. In vitro reconstitution of a Rab activation switch. Institute of Science and Technology Austria.","chicago":"Bezeljak, Urban. “In Vitro Reconstitution of a Rab Activation Switch.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:8341."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa":1,"publisher":"Institute of Science and Technology Austria","acknowledgement":"My thanks goes to the Loose lab members, BioImaging, Life Science and Nanofabrication Facilities and the wonderful international community at IST for sharing this experience with me.","page":"215","date_created":"2020-09-08T08:53:53Z","doi":"10.15479/AT:ISTA:8341","date_published":"2020-09-08T00:00:00Z","year":"2020","has_accepted_license":"1","day":"08"},{"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"eissn":["1091-6490"],"issn":["0027-8424"]},"issue":"12","volume":117,"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"8341"}],"link":[{"description":"News on IST Homepage","relation":"press_release","url":"https://ist.ac.at/en/news/proteins-as-molecular-switches/"}]},"oa_version":"Preprint","abstract":[{"text":"The eukaryotic endomembrane system is controlled by small GTPases of the Rab family, which are activated at defined times and locations in a switch-like manner. While this switch is well understood for an individual protein, how regulatory networks produce intracellular activity patterns is currently not known. Here, we combine in vitro reconstitution experiments with computational modeling to study a minimal Rab5 activation network. We find that the molecular interactions in this system give rise to a positive feedback and bistable collective switching of Rab5. Furthermore, we find that switching near the critical point is intrinsically stochastic and provide evidence that controlling the inactive population of Rab5 on the membrane can shape the network response. Notably, we demonstrate that collective switching can spread on the membrane surface as a traveling wave of Rab5 activation. Together, our findings reveal how biochemical signaling networks control vesicle trafficking pathways and how their nonequilibrium properties define the spatiotemporal organization of the cell.","lang":"eng"}],"acknowledged_ssus":[{"_id":"Bio"},{"_id":"LifeSc"}],"intvolume":" 117","month":"03","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1101/776567"}],"scopus_import":"1","date_updated":"2023-09-07T13:17:06Z","department":[{"_id":"MaLo"},{"_id":"CaBe"}],"_id":"7580","status":"public","type":"journal_article","article_type":"original","publication":"Proceedings of the National Academy of Sciences","day":"24","year":"2020","isi":1,"date_created":"2020-03-12T05:32:26Z","doi":"10.1073/pnas.1921027117","date_published":"2020-03-24T00:00:00Z","page":"6504-6549","oa":1,"quality_controlled":"1","publisher":"Proceedings of the National Academy of Sciences","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"mla":"Bezeljak, Urban, et al. “Stochastic Activation and Bistability in a Rab GTPase Regulatory Network.” Proceedings of the National Academy of Sciences, vol. 117, no. 12, Proceedings of the National Academy of Sciences, 2020, pp. 6504–49, doi:10.1073/pnas.1921027117.","short":"U. Bezeljak, H. Loya, B.M. Kaczmarek, T.E. Saunders, M. Loose, Proceedings of the National Academy of Sciences 117 (2020) 6504–6549.","ieee":"U. Bezeljak, H. Loya, B. M. Kaczmarek, T. E. Saunders, and M. Loose, “Stochastic activation and bistability in a Rab GTPase regulatory network,” Proceedings of the National Academy of Sciences, vol. 117, no. 12. Proceedings of the National Academy of Sciences, pp. 6504–6549, 2020.","ama":"Bezeljak U, Loya H, Kaczmarek BM, Saunders TE, Loose M. Stochastic activation and bistability in a Rab GTPase regulatory network. Proceedings of the National Academy of Sciences. 2020;117(12):6504-6549. doi:10.1073/pnas.1921027117","apa":"Bezeljak, U., Loya, H., Kaczmarek, B. M., Saunders, T. E., & Loose, M. (2020). Stochastic activation and bistability in a Rab GTPase regulatory network. Proceedings of the National Academy of Sciences. Proceedings of the National Academy of Sciences. https://doi.org/10.1073/pnas.1921027117","chicago":"Bezeljak, Urban, Hrushikesh Loya, Beata M Kaczmarek, Timothy E. Saunders, and Martin Loose. “Stochastic Activation and Bistability in a Rab GTPase Regulatory Network.” Proceedings of the National Academy of Sciences. Proceedings of the National Academy of Sciences, 2020. https://doi.org/10.1073/pnas.1921027117.","ista":"Bezeljak U, Loya H, Kaczmarek BM, Saunders TE, Loose M. 2020. Stochastic activation and bistability in a Rab GTPase regulatory network. Proceedings of the National Academy of Sciences. 117(12), 6504–6549."},"title":"Stochastic activation and bistability in a Rab GTPase regulatory network","article_processing_charge":"No","external_id":{"isi":["000521821800040"]},"author":[{"first_name":"Urban","id":"2A58201A-F248-11E8-B48F-1D18A9856A87","full_name":"Bezeljak, Urban","orcid":"0000-0003-1365-5631","last_name":"Bezeljak"},{"first_name":"Hrushikesh","full_name":"Loya, Hrushikesh","last_name":"Loya"},{"first_name":"Beata M","id":"36FA4AFA-F248-11E8-B48F-1D18A9856A87","full_name":"Kaczmarek, Beata M","last_name":"Kaczmarek"},{"first_name":"Timothy E.","last_name":"Saunders","full_name":"Saunders, Timothy E."},{"first_name":"Martin","id":"462D4284-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-7309-9724","full_name":"Loose, Martin","last_name":"Loose"}],"project":[{"_id":"2599F062-B435-11E9-9278-68D0E5697425","grant_number":"RGY0083/2016","name":"Reconstitution of cell polarity and axis determination in a cell-free system"}]},{"has_accepted_license":"1","year":"2020","day":"26","page":"xviii+120","date_published":"2020-06-26T00:00:00Z","doi":"10.15479/AT:ISTA:8032","date_created":"2020-06-26T10:00:36Z","publisher":"Institute of Science and Technology Austria","oa":1,"citation":{"chicago":"Huszár, Kristóf. “Combinatorial Width Parameters for 3-Dimensional Manifolds.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:8032.","ista":"Huszár K. 2020. Combinatorial width parameters for 3-dimensional manifolds. Institute of Science and Technology Austria.","mla":"Huszár, Kristóf. Combinatorial Width Parameters for 3-Dimensional Manifolds. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:8032.","apa":"Huszár, K. (2020). Combinatorial width parameters for 3-dimensional manifolds. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:8032","ama":"Huszár K. Combinatorial width parameters for 3-dimensional manifolds. 2020. doi:10.15479/AT:ISTA:8032","ieee":"K. Huszár, “Combinatorial width parameters for 3-dimensional manifolds,” Institute of Science and Technology Austria, 2020.","short":"K. Huszár, Combinatorial Width Parameters for 3-Dimensional Manifolds, Institute of Science and Technology Austria, 2020."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"first_name":"Kristóf","id":"33C26278-F248-11E8-B48F-1D18A9856A87","full_name":"Huszár, Kristóf","orcid":"0000-0002-5445-5057","last_name":"Huszár"}],"article_processing_charge":"No","title":"Combinatorial width parameters for 3-dimensional manifolds","publication_identifier":{"issn":["2663-337X"],"isbn":["978-3-99078-006-0"]},"publication_status":"published","degree_awarded":"PhD","file":[{"file_size":2637562,"date_updated":"2020-07-14T12:48:08Z","creator":"khuszar","file_name":"Kristof_Huszar-Thesis.pdf","date_created":"2020-06-26T10:03:58Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","checksum":"bd8be6e4f1addc863dfcc0fad29ee9c3","file_id":"8034"},{"file_id":"8035","checksum":"d5f8456202b32f4a77552ef47a2837d1","content_type":"application/x-zip-compressed","relation":"source_file","access_level":"closed","file_name":"Kristof_Huszar-Thesis-source.zip","date_created":"2020-06-26T10:10:06Z","file_size":7163491,"date_updated":"2020-07-14T12:48:08Z","creator":"khuszar"}],"language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"6556"},{"status":"public","id":"7093","relation":"dissertation_contains"}]},"abstract":[{"lang":"eng","text":"Algorithms in computational 3-manifold topology typically take a triangulation as an input and return topological information about the underlying 3-manifold. However, extracting the desired information from a triangulation (e.g., evaluating an invariant) is often computationally very expensive. In recent years this complexity barrier has been successfully tackled in some cases by importing ideas from the theory of parameterized algorithms into the realm of 3-manifolds. Various computationally hard problems were shown to be efficiently solvable for input triangulations that are sufficiently “tree-like.”\r\nIn this thesis we focus on the key combinatorial parameter in the above context: we consider the treewidth of a compact, orientable 3-manifold, i.e., the smallest treewidth of the dual graph of any triangulation thereof. By building on the work of Scharlemann–Thompson and Scharlemann–Schultens–Saito on generalized Heegaard splittings, and on the work of Jaco–Rubinstein on layered triangulations, we establish quantitative relations between the treewidth and classical topological invariants of a 3-manifold. In particular, among other results, we show that the treewidth of a closed, orientable, irreducible, non-Haken 3-manifold is always within a constant factor of its Heegaard genus."}],"acknowledged_ssus":[{"_id":"E-Lib"},{"_id":"CampIT"}],"oa_version":"Published Version","alternative_title":["ISTA Thesis"],"month":"06","supervisor":[{"first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568"},{"last_name":"Spreer","full_name":"Spreer, Jonathan","first_name":"Jonathan"}],"date_updated":"2023-09-07T13:18:27Z","ddc":["514"],"file_date_updated":"2020-07-14T12:48:08Z","department":[{"_id":"UlWa"}],"_id":"8032","type":"dissertation","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public"}]