--- _id: '7896' 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. " alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Chethan full_name: Kamath Hosdurg, Chethan id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87 last_name: Kamath Hosdurg citation: 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 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. ieee: C. Kamath Hosdurg, “On the average-case hardness of total search problems,” Institute of Science and Technology Austria, 2020. ista: Kamath Hosdurg C. 2020. On the average-case hardness of total search problems. Institute of Science and Technology Austria. 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. short: C. Kamath Hosdurg, On the Average-Case Hardness of Total Search Problems, Institute of Science and Technology Austria, 2020. date_created: 2020-05-26T14:08:55Z date_published: 2020-05-25T00:00:00Z date_updated: 2023-09-07T13:15:55Z day: '25' ddc: - '000' degree_awarded: PhD department: - _id: KrPi doi: 10.15479/AT:ISTA:7896 ec_funded: 1 file: - access_level: open_access checksum: b39e2e1c376f5819b823fb7077491c64 content_type: application/pdf creator: dernst date_created: 2020-05-26T14:08:13Z date_updated: 2020-07-14T12:48:04Z file_id: '7897' file_name: 2020_Thesis_Kamath.pdf file_size: 1622742 relation: main_file - access_level: closed checksum: 8b26ba729c1a85ac6bea775f5d73cdc7 content_type: application/x-zip-compressed creator: dernst date_created: 2020-05-26T14:08:23Z date_updated: 2020-07-14T12:48:04Z file_id: '7898' file_name: Thesis_Kamath.zip file_size: 15301529 relation: source_file file_date_updated: 2020-07-14T12:48:04Z has_accepted_license: '1' language: - iso: eng license: https://creativecommons.org/licenses/by/4.0/ month: '05' oa: 1 oa_version: Published Version page: '126' project: - _id: 258C570E-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '259668' name: Provable Security for Physical Cryptography - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication_identifier: issn: - 2663-337X publication_status: published publisher: Institute of Science and Technology Austria related_material: record: - id: '6677' relation: part_of_dissertation status: public status: public supervisor: - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 title: On the average-case hardness of total search problems tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: dissertation user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2020' ... --- _id: '7936' 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.' article_number: 1716-1725 article_processing_charge: No author: - first_name: Amélie full_name: Royer, Amélie id: 3811D890-F248-11E8-B48F-1D18A9856A87 last_name: Royer orcid: 0000-0002-8407-0705 - first_name: Christoph full_name: Lampert, Christoph id: 40C20FD2-F248-11E8-B48F-1D18A9856A87 last_name: Lampert orcid: 0000-0001-8622-7887 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' 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. 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. 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.' 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. short: A. Royer, C. Lampert, in:, IEEE Winter Conference on Applications of Computer Vision, IEEE, 2020. conference: end_date: 2020-03-05 location: ' Snowmass Village, CO, United States' name: 'WACV: Winter Conference on Applications of Computer Vision' start_date: 2020-03-01 date_created: 2020-06-07T22:00:53Z date_published: 2020-03-01T00:00:00Z date_updated: 2023-09-07T13:16:17Z day: '01' department: - _id: ChLa doi: 10.1109/WACV45572.2020.9093288 external_id: arxiv: - '2004.12623' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2004.12623 month: '03' oa: 1 oa_version: Preprint publication: IEEE Winter Conference on Applications of Computer Vision publication_identifier: isbn: - '9781728165530' publication_status: published publisher: IEEE quality_controlled: '1' related_material: record: - id: '8331' relation: dissertation_contains status: deleted - id: '8390' relation: dissertation_contains status: public scopus_import: 1 status: public title: Localizing grouped instances for efficient detection in low-resource scenarios type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2020' ... --- _id: '7937' abstract: - lang: eng 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.' article_number: 2180-2189 article_processing_charge: No author: - first_name: Amélie full_name: Royer, Amélie id: 3811D890-F248-11E8-B48F-1D18A9856A87 last_name: Royer orcid: 0000-0002-8407-0705 - first_name: Christoph full_name: Lampert, Christoph id: 40C20FD2-F248-11E8-B48F-1D18A9856A87 last_name: Lampert orcid: 0000-0001-8622-7887 citation: 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' 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. 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. 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. short: A. Royer, C. Lampert, in:, 2020 IEEE Winter Conference on Applications of Computer Vision, IEEE, 2020. conference: end_date: 2020-03-05 location: Snowmass Village, CO, United States name: 'WACV: Winter Conference on Applications of Computer Vision' start_date: 2020-03-01 date_created: 2020-06-07T22:00:53Z date_published: 2020-03-01T00:00:00Z date_updated: 2023-09-07T13:16:17Z day: '01' department: - _id: ChLa doi: 10.1109/WACV45572.2020.9093635 external_id: arxiv: - '2008.11995' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/2008.11995 month: '03' oa: 1 oa_version: Preprint publication: 2020 IEEE Winter Conference on Applications of Computer Vision publication_identifier: isbn: - '9781728165530' publication_status: published publisher: IEEE quality_controlled: '1' related_material: record: - id: '8331' relation: dissertation_contains status: deleted - id: '8390' relation: dissertation_contains status: public scopus_import: '1' status: public title: A flexible selection scheme for minimum-effort transfer learning type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2020' ... --- _id: '8092' 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. article_processing_charge: No author: - first_name: Amélie full_name: Royer, Amélie id: 3811D890-F248-11E8-B48F-1D18A9856A87 last_name: Royer orcid: 0000-0002-8407-0705 - first_name: Konstantinos full_name: Bousmalis, Konstantinos last_name: Bousmalis - first_name: Stephan full_name: Gouws, Stephan last_name: Gouws - first_name: Fred full_name: Bertsch, Fred last_name: Bertsch - first_name: Inbar full_name: Mosseri, Inbar last_name: Mosseri - first_name: Forrester full_name: Cole, Forrester last_name: Cole - first_name: Kevin full_name: Murphy, Kevin last_name: Murphy citation: 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' 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.' 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.' 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. date_created: 2020-07-05T22:00:46Z date_published: 2020-01-08T00:00:00Z date_updated: 2023-09-07T13:16:18Z day: '08' department: - _id: ChLa doi: 10.1007/978-3-030-30671-7_3 editor: - first_name: Richa full_name: Singh, Richa last_name: Singh - first_name: Mayank full_name: Vatsa, Mayank last_name: Vatsa - first_name: Vishal M. full_name: Patel, Vishal M. last_name: Patel - first_name: Nalini full_name: Ratha, Nalini last_name: Ratha external_id: arxiv: - '1711.05139' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1711.05139 month: '01' oa: 1 oa_version: Preprint page: 33-49 publication: Domain Adaptation for Visual Understanding publication_identifier: isbn: - '9783030306717' publication_status: published publisher: Springer Nature quality_controlled: '1' related_material: record: - id: '8331' relation: dissertation_contains status: deleted - id: '8390' relation: dissertation_contains status: public scopus_import: '1' status: public title: 'XGAN: Unsupervised image-to-image translation for many-to-many mappings' type: book_chapter user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2020' ... --- _id: '7944' abstract: - lang: eng 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." alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Zuzana full_name: Masárová, Zuzana id: 45CFE238-F248-11E8-B48F-1D18A9856A87 last_name: Masárová orcid: 0000-0002-6660-1322 citation: 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 chicago: Masárová, Zuzana. “Reconfiguration Problems.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7944. ieee: Z. Masárová, “Reconfiguration problems,” Institute of Science and Technology Austria, 2020. ista: Masárová Z. 2020. Reconfiguration problems. Institute of Science and Technology Austria. mla: Masárová, Zuzana. Reconfiguration Problems. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7944. short: Z. Masárová, Reconfiguration Problems, Institute of Science and Technology Austria, 2020. date_created: 2020-06-08T00:49:46Z date_published: 2020-06-09T00:00:00Z date_updated: 2023-09-07T13:17:37Z day: '09' ddc: - '516' - '514' degree_awarded: PhD department: - _id: HeEd - _id: UlWa doi: 10.15479/AT:ISTA:7944 file: - access_level: open_access checksum: df688bc5a82b50baee0b99d25fc7b7f0 content_type: application/pdf creator: zmasarov date_created: 2020-06-08T00:34:00Z date_updated: 2020-07-14T12:48:05Z file_id: '7945' file_name: THESIS_Zuzka_Masarova.pdf file_size: 13661779 relation: main_file - access_level: closed checksum: 45341a35b8f5529c74010b7af43ac188 content_type: application/zip creator: zmasarov date_created: 2020-06-08T00:35:30Z date_updated: 2020-07-14T12:48:05Z file_id: '7946' file_name: THESIS_Zuzka_Masarova_SOURCE_FILES.zip file_size: 32184006 relation: source_file file_date_updated: 2020-07-14T12:48:05Z has_accepted_license: '1' keyword: - reconfiguration - reconfiguration graph - triangulations - flip - constrained triangulations - shellability - piecewise-linear balls - token swapping - trees - coloured weighted token swapping language: - iso: eng license: https://creativecommons.org/licenses/by-sa/4.0/ month: '06' oa: 1 oa_version: Published Version page: '160' publication_identifier: isbn: - 978-3-99078-005-3 issn: - 2663-337X publication_status: published publisher: Institute of Science and Technology Austria related_material: record: - id: '7950' relation: part_of_dissertation status: public - id: '5986' relation: part_of_dissertation status: public status: public supervisor: - first_name: Uli full_name: Wagner, Uli id: 36690CA2-F248-11E8-B48F-1D18A9856A87 last_name: Wagner orcid: 0000-0002-1494-0568 - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 title: Reconfiguration problems tmp: 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) short: CC BY-SA (4.0) type: dissertation user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2020' ...