--- _id: '6647' abstract: - lang: eng text: The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2. alternative_title: - LIPIcs arxiv: 1 author: - first_name: Radoslav full_name: Fulek, Radoslav id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87 last_name: Fulek orcid: 0000-0001-8485-1774 - first_name: Bernd full_name: Gärtner, Bernd last_name: Gärtner - first_name: Andrey full_name: Kupavskii, Andrey last_name: Kupavskii - first_name: Pavel full_name: Valtr, Pavel last_name: Valtr - first_name: Uli full_name: Wagner, Uli id: 36690CA2-F248-11E8-B48F-1D18A9856A87 last_name: Wagner orcid: 0000-0002-1494-0568 citation: ama: 'Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. In: 35th International Symposium on Computational Geometry. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:38:1-38:13. doi:10.4230/LIPICS.SOCG.2019.38' apa: 'Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2019). The crossing Tverberg theorem. In 35th International Symposium on Computational Geometry (Vol. 129, p. 38:1-38:13). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.38' chicago: Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” In 35th International Symposium on Computational Geometry, 129:38:1-38:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.SOCG.2019.38. ieee: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” in 35th International Symposium on Computational Geometry, Portland, OR, United States, 2019, vol. 129, p. 38:1-38:13. ista: 'Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2019. The crossing Tverberg theorem. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium on Computational Geometry, LIPIcs, vol. 129, 38:1-38:13.' mla: Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” 35th International Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13, doi:10.4230/LIPICS.SOCG.2019.38. short: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13. conference: end_date: 2019-06-21 location: Portland, OR, United States name: 'SoCG 2019: Symposium on Computational Geometry' start_date: 2019-06-18 date_created: 2019-07-17T10:35:04Z date_published: 2019-06-01T00:00:00Z date_updated: 2023-12-13T12:03:35Z day: '01' ddc: - '000' - '510' department: - _id: UlWa doi: 10.4230/LIPICS.SOCG.2019.38 external_id: arxiv: - '1812.04911' file: - access_level: open_access checksum: d6d017f8b41291b94d102294fa96ae9c content_type: application/pdf creator: dernst date_created: 2019-07-24T06:54:52Z date_updated: 2020-07-14T12:47:35Z file_id: '6667' file_name: 2019_LIPICS_Fulek.pdf file_size: 559837 relation: main_file file_date_updated: 2020-07-14T12:47:35Z has_accepted_license: '1' intvolume: ' 129' language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: 38:1-38:13 project: - _id: 261FA626-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: M02281 name: Eliminating intersections in drawings of graphs publication: 35th International Symposium on Computational Geometry publication_identifier: isbn: - '9783959771047' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: record: - id: '13974' relation: later_version status: public scopus_import: 1 status: public title: The crossing Tverberg theorem 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: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 129 year: '2019' ... --- _id: '6648' abstract: - lang: eng text: "Various kinds of data are routinely represented as discrete probability distributions. Examples include text documents summarized by histograms of word occurrences and images represented as histograms of oriented gradients. Viewing a discrete probability distribution as a point in the standard simplex of the appropriate dimension, we can understand collections of such objects in geometric and topological terms. Importantly, instead of using the standard Euclidean distance, we look into dissimilarity measures with information-theoretic justification, and we develop the theory\r\nneeded for applying topological data analysis in this setting. In doing so, we emphasize constructions that enable the usage of existing computational topology software in this context." alternative_title: - LIPIcs arxiv: 1 author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Ziga full_name: Virk, Ziga last_name: Virk - first_name: Hubert full_name: Wagner, Hubert id: 379CA8B8-F248-11E8-B48F-1D18A9856A87 last_name: Wagner citation: ama: 'Edelsbrunner H, Virk Z, Wagner H. Topological data analysis in information space. In: 35th International Symposium on Computational Geometry. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:31:1-31:14. doi:10.4230/LIPICS.SOCG.2019.31' apa: 'Edelsbrunner, H., Virk, Z., & Wagner, H. (2019). Topological data analysis in information space. In 35th International Symposium on Computational Geometry (Vol. 129, p. 31:1-31:14). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.31' chicago: Edelsbrunner, Herbert, Ziga Virk, and Hubert Wagner. “Topological Data Analysis in Information Space.” In 35th International Symposium on Computational Geometry, 129:31:1-31:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.SOCG.2019.31. ieee: H. Edelsbrunner, Z. Virk, and H. Wagner, “Topological data analysis in information space,” in 35th International Symposium on Computational Geometry, Portland, OR, United States, 2019, vol. 129, p. 31:1-31:14. ista: 'Edelsbrunner H, Virk Z, Wagner H. 2019. Topological data analysis in information space. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium on Computational Geometry, LIPIcs, vol. 129, 31:1-31:14.' mla: Edelsbrunner, Herbert, et al. “Topological Data Analysis in Information Space.” 35th International Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 31:1-31:14, doi:10.4230/LIPICS.SOCG.2019.31. short: H. Edelsbrunner, Z. Virk, H. Wagner, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 31:1-31:14. conference: end_date: 2019-06-21 location: Portland, OR, United States name: 'SoCG 2019: Symposium on Computational Geometry' start_date: 2019-06-18 date_created: 2019-07-17T10:36:09Z date_published: 2019-06-01T00:00:00Z date_updated: 2021-01-12T08:08:23Z day: '01' ddc: - '510' department: - _id: HeEd doi: 10.4230/LIPICS.SOCG.2019.31 external_id: arxiv: - '1903.08510' file: - access_level: open_access checksum: 8ec8720730d4c789bf7b06540f1c29f4 content_type: application/pdf creator: dernst date_created: 2019-07-24T06:40:01Z date_updated: 2020-07-14T12:47:35Z file_id: '6666' file_name: 2019_LIPICS_Edelsbrunner.pdf file_size: 1355179 relation: main_file file_date_updated: 2020-07-14T12:47:35Z has_accepted_license: '1' intvolume: ' 129' language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: 31:1-31:14 project: - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication: 35th International Symposium on Computational Geometry publication_identifier: isbn: - '9783959771047' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: 1 status: public title: Topological data analysis in information space 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: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 129 year: '2019' ... --- _id: '6650' abstract: - lang: eng text: We propose a novel technique for the automatic design of molds to cast highly complex shapes. The technique generates composite, two-piece molds. Each mold piece is made up of a hard plastic shell and a flexible silicone part. Thanks to the thin, soft, and smartly shaped silicone part, which is kept in place by a hard plastic shell, we can cast objects of unprecedented complexity. An innovative algorithm based on a volumetric analysis defines the layout of the internal cuts in the silicone mold part. Our approach can robustly handle thin protruding features and intertwined topologies that have caused previous methods to fail. We compare our results with state of the art techniques, and we demonstrate the casting of shapes with extremely complex geometry. article_number: '110' article_processing_charge: No author: - first_name: Thomas full_name: Alderighi, Thomas last_name: Alderighi - first_name: Luigi full_name: Malomo, Luigi last_name: Malomo - first_name: Daniela full_name: Giorgi, Daniela last_name: Giorgi - first_name: Bernd full_name: Bickel, Bernd id: 49876194-F248-11E8-B48F-1D18A9856A87 last_name: Bickel orcid: 0000-0001-6511-9385 - first_name: Paolo full_name: Cignoni, Paolo last_name: Cignoni - first_name: Nico full_name: Pietroni, Nico last_name: Pietroni citation: ama: Alderighi T, Malomo L, Giorgi D, Bickel B, Cignoni P, Pietroni N. Volume-aware design of composite molds. ACM Transactions on Graphics. 2019;38(4). doi:10.1145/3306346.3322981 apa: Alderighi, T., Malomo, L., Giorgi, D., Bickel, B., Cignoni, P., & Pietroni, N. (2019). Volume-aware design of composite molds. ACM Transactions on Graphics. ACM. https://doi.org/10.1145/3306346.3322981 chicago: Alderighi, Thomas, Luigi Malomo, Daniela Giorgi, Bernd Bickel, Paolo Cignoni, and Nico Pietroni. “Volume-Aware Design of Composite Molds.” ACM Transactions on Graphics. ACM, 2019. https://doi.org/10.1145/3306346.3322981. ieee: T. Alderighi, L. Malomo, D. Giorgi, B. Bickel, P. Cignoni, and N. Pietroni, “Volume-aware design of composite molds,” ACM Transactions on Graphics, vol. 38, no. 4. ACM, 2019. ista: Alderighi T, Malomo L, Giorgi D, Bickel B, Cignoni P, Pietroni N. 2019. Volume-aware design of composite molds. ACM Transactions on Graphics. 38(4), 110. mla: Alderighi, Thomas, et al. “Volume-Aware Design of Composite Molds.” ACM Transactions on Graphics, vol. 38, no. 4, 110, ACM, 2019, doi:10.1145/3306346.3322981. short: T. Alderighi, L. Malomo, D. Giorgi, B. Bickel, P. Cignoni, N. Pietroni, ACM Transactions on Graphics 38 (2019). date_created: 2019-07-19T06:18:15Z date_published: 2019-07-01T00:00:00Z date_updated: 2023-08-29T06:35:52Z day: '01' ddc: - '000' department: - _id: BeBi doi: 10.1145/3306346.3322981 ec_funded: 1 external_id: isi: - '000475740600084' file: - access_level: open_access checksum: b4562af94672b44d2a501046427412af content_type: application/pdf creator: dernst date_created: 2019-07-19T06:18:53Z date_updated: 2020-07-14T12:47:35Z file_id: '6651' file_name: 2019_ACM_Alderighi_AuthorVersion.pdf file_size: 74316182 relation: main_file file_date_updated: 2020-07-14T12:47:35Z has_accepted_license: '1' intvolume: ' 38' isi: 1 issue: '4' language: - iso: eng month: '07' oa: 1 oa_version: Submitted Version project: - _id: 24F9549A-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '715767' name: 'MATERIALIZABLE: Intelligent fabrication-oriented Computational Design and Modeling' publication: ACM Transactions on Graphics publication_identifier: issn: - 0730-0301 publication_status: published publisher: ACM quality_controlled: '1' related_material: link: - description: YouTube Video relation: supplementary_material url: https://youtu.be/SO349S8-x_w scopus_import: '1' status: public title: Volume-aware design of composite molds type: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 38 year: '2019' ... --- _id: '6657' abstract: - lang: eng text: 'In this article a model is described how Open Access definitions can be formed on the basis of objective criteria. The common Open Access definitions such as "gold" and "green" are not exactly defined. This becomes a problem as soon as one begins to measure Open Access, for example if the development of the Open Access share should be monitored. This was discussed in the working group on Open Access Monitoring of the AT2OA project and the present model was developed, which is based on 5 critics with 4 characteristics: location, licence, version, embargo and conditions of the Open Access publication are taken into account. In the meantime, the model has also been tested in practice using R scripts, and the initial results are quite promising.' article_processing_charge: No article_type: original author: - first_name: Patrick full_name: Danowski, Patrick id: 2EBD1598-F248-11E8-B48F-1D18A9856A87 last_name: Danowski orcid: 0000-0002-6026-4409 citation: ama: Danowski P. An Austrian proposal for the classification of Open Access Tuples (COAT) - distinguish different open access types beyond colors. Mitteilungen der Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare. 2019;72(1):59-65. doi:10.31263/voebm.v72i1.2276 apa: Danowski, P. (2019). An Austrian proposal for the classification of Open Access Tuples (COAT) - distinguish different open access types beyond colors. Mitteilungen Der Vereinigung Österreichischer Bibliothekarinnen Und Bibliothekare. Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare. https://doi.org/10.31263/voebm.v72i1.2276 chicago: Danowski, Patrick. “An Austrian Proposal for the Classification of Open Access Tuples (COAT) - Distinguish Different Open Access Types beyond Colors.” Mitteilungen Der Vereinigung Österreichischer Bibliothekarinnen Und Bibliothekare. Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare, 2019. https://doi.org/10.31263/voebm.v72i1.2276. ieee: P. Danowski, “An Austrian proposal for the classification of Open Access Tuples (COAT) - distinguish different open access types beyond colors,” Mitteilungen der Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare, vol. 72, no. 1. Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare, pp. 59–65, 2019. ista: Danowski P. 2019. An Austrian proposal for the classification of Open Access Tuples (COAT) - distinguish different open access types beyond colors. Mitteilungen der Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare. 72(1), 59–65. mla: Danowski, Patrick. “An Austrian Proposal for the Classification of Open Access Tuples (COAT) - Distinguish Different Open Access Types beyond Colors.” Mitteilungen Der Vereinigung Österreichischer Bibliothekarinnen Und Bibliothekare, vol. 72, no. 1, Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare, 2019, pp. 59–65, doi:10.31263/voebm.v72i1.2276. short: P. Danowski, Mitteilungen Der Vereinigung Österreichischer Bibliothekarinnen Und Bibliothekare 72 (2019) 59–65. date_created: 2019-07-21T21:59:15Z date_published: 2019-05-17T00:00:00Z date_updated: 2023-10-17T11:33:58Z day: '17' ddc: - '020' department: - _id: E-Lib doi: 10.31263/voebm.v72i1.2276 file: - access_level: open_access checksum: c0d2695d6d0d34e62ba06fb3f0ebaaed content_type: application/pdf creator: apreinsp date_created: 2019-07-22T08:45:03Z date_updated: 2020-07-14T12:47:35Z file_id: '6661' file_name: 2019_MitteilungenDerVOEB_Danowski.pdf file_size: 468558 relation: main_file file_date_updated: 2020-07-14T12:47:35Z has_accepted_license: '1' intvolume: ' 72' issue: '1' language: - iso: eng month: '05' oa: 1 oa_version: Published Version page: 59-65 publication: Mitteilungen der Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare publication_identifier: eissn: - 1022-2588 publication_status: published publisher: Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare quality_controlled: '1' related_material: record: - id: '5686' relation: earlier_version status: public scopus_import: '1' status: public title: An Austrian proposal for the classification of Open Access Tuples (COAT) - distinguish different open access types beyond colors 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: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 72 year: '2019' ... --- _id: '6658' abstract: - lang: eng text: 'New genes are a major source of novelties, and a disproportionate amount of them are known to show testis expression in later phases of male gametogenesis in different groups such as mammals and plants. Here, we propose that this enhanced expression is a consequence of haploid selection during the latter stages of male gametogenesis. Because emerging adaptive mutations will be fixed faster if their phenotypes are expressed by haploid rather than diploid genotypes, new genes with advantageous functions arising during this unique stage of development have a better chance to become fixed. To test this hypothesis, expression levels of genes of differing evolutionary age were examined at various stages of Drosophila spermatogenesis. We found, consistent with a model based on haploid selection, that new Drosophila genes are both expressed in later haploid phases of spermatogenesis and harbor a significant enrichment of adaptive mutations. Additionally, the observed overexpression of new genes in the latter phases of spermatogenesis was limited to the autosomes. Because all male cells exhibit hemizygous expression for X-linked genes (and therefore effectively haploid), there is no expectation that selection acting on late spermatogenesis will have a different effect on X-linked genes in comparison to initial diploid phases. Together, our proposed hypothesis and the analyzed data suggest that natural selection in haploid cells elucidates several aspects of the origin of new genes by explaining the general prevalence of their testis expression, and a parsimonious solution for new alleles to avoid being lost by genetic drift or pseudogenization. ' article_processing_charge: No author: - first_name: Julia full_name: Raices, Julia id: 3EE67F22-F248-11E8-B48F-1D18A9856A87 last_name: Raices - first_name: Paulo full_name: Otto, Paulo last_name: Otto - first_name: Maria full_name: Vibranovski, Maria last_name: Vibranovski citation: ama: Raices J, Otto P, Vibranovski M. Haploid selection drives new gene male germline expression. Genome Research. 2019;29(7):1115-1122. doi:10.1101/gr.238824.118 apa: Raices, J., Otto, P., & Vibranovski, M. (2019). Haploid selection drives new gene male germline expression. Genome Research. CSH Press. https://doi.org/10.1101/gr.238824.118 chicago: Raices, Julia, Paulo Otto, and Maria Vibranovski. “Haploid Selection Drives New Gene Male Germline Expression.” Genome Research. CSH Press, 2019. https://doi.org/10.1101/gr.238824.118. ieee: J. Raices, P. Otto, and M. Vibranovski, “Haploid selection drives new gene male germline expression,” Genome Research, vol. 29, no. 7. CSH Press, pp. 1115–1122, 2019. ista: Raices J, Otto P, Vibranovski M. 2019. Haploid selection drives new gene male germline expression. Genome Research. 29(7), 1115–1122. mla: Raices, Julia, et al. “Haploid Selection Drives New Gene Male Germline Expression.” Genome Research, vol. 29, no. 7, CSH Press, 2019, pp. 1115–22, doi:10.1101/gr.238824.118. short: J. Raices, P. Otto, M. Vibranovski, Genome Research 29 (2019) 1115–1122. date_created: 2019-07-21T21:59:15Z date_published: 2019-07-01T00:00:00Z date_updated: 2023-08-29T06:35:05Z day: '01' ddc: - '576' department: - _id: BeVi doi: 10.1101/gr.238824.118 external_id: isi: - '000473730600007' file: - access_level: open_access checksum: 4636f03a6750f90b88bf2bc3eb9d71ae content_type: application/pdf creator: apreinsp date_created: 2019-07-24T08:05:56Z date_updated: 2020-07-14T12:47:35Z file_id: '6670' file_name: 2019_GenomeResearch_Raices.pdf file_size: 2319022 relation: main_file file_date_updated: 2020-07-14T12:47:35Z has_accepted_license: '1' intvolume: ' 29' isi: 1 issue: '7' language: - iso: eng license: https://creativecommons.org/licenses/by-nc/4.0/ month: '07' oa: 1 oa_version: Published Version page: 1115-1122 publication: Genome Research publication_status: published publisher: CSH Press quality_controlled: '1' scopus_import: '1' status: public title: Haploid selection drives new gene male germline expression tmp: image: /images/cc_by_nc.png legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) short: CC BY-NC (4.0) type: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 29 year: '2019' ... --- _id: '6659' abstract: - lang: eng text: Chemical labeling of proteins with synthetic molecular probes offers the possibility to probe the functions of proteins of interest in living cells. However, the methods for covalently labeling targeted proteins using complementary peptide tag-probe pairs are still limited, irrespective of the versatility of such pairs in biological research. Herein, we report the new CysHis tag-Ni(II) probe pair for the specific covalent labeling of proteins. A broad-range evaluation of the reactivity profiles of the probe and the CysHis peptide tag afforded a tag-probe pair with an optimized and high labeling selectivity and reactivity. In particular, the labeling specificity of this pair was notably improved compared to the previously reported one. This pair was successfully utilized for the fluorescence imaging of membrane proteins on the surfaces of living cells, demonstrating its potential utility in biological research. acknowledgement: his work was supported by the Grant-in-Aid for Scientific Research B (JSPS KAKENHI grant no. JP17H03090 to A. O.); the Scientific Research on Innovative Areas “Chemistry for Multimolecular Crowding Biosystems” (JSPS KAKENHI grant no. JP17H06349 to A. O.); and the European Union (European Research Council Advanced grant no. 694539 and Human Brain Project Ref. 720270 to R. S.). A. O. acknowledges the financial support of the Takeda Science Foundation. article_processing_charge: No article_type: original author: - first_name: Naoki full_name: Zenmyo, Naoki last_name: Zenmyo - first_name: Hiroki full_name: Tokumaru, Hiroki last_name: Tokumaru - first_name: Shohei full_name: Uchinomiya, Shohei last_name: Uchinomiya - first_name: Hirokazu full_name: Fuchida, Hirokazu last_name: Fuchida - first_name: Shigekazu full_name: Tabata, Shigekazu id: 4427179E-F248-11E8-B48F-1D18A9856A87 last_name: Tabata - first_name: Itaru full_name: Hamachi, Itaru last_name: Hamachi - first_name: Ryuichi full_name: Shigemoto, Ryuichi id: 499F3ABC-F248-11E8-B48F-1D18A9856A87 last_name: Shigemoto orcid: 0000-0001-8761-9444 - first_name: Akio full_name: Ojida, Akio last_name: Ojida citation: ama: Zenmyo N, Tokumaru H, Uchinomiya S, et al. Optimized reaction pair of the CysHis tag and Ni(II)-NTA probe for highly selective chemical labeling of membrane proteins. Bulletin of the Chemical Society of Japan. 2019;92(5):995-1000. doi:10.1246/bcsj.20190034 apa: Zenmyo, N., Tokumaru, H., Uchinomiya, S., Fuchida, H., Tabata, S., Hamachi, I., … Ojida, A. (2019). Optimized reaction pair of the CysHis tag and Ni(II)-NTA probe for highly selective chemical labeling of membrane proteins. Bulletin of the Chemical Society of Japan. Bulletin of the Chemical Society of Japan. https://doi.org/10.1246/bcsj.20190034 chicago: Zenmyo, Naoki, Hiroki Tokumaru, Shohei Uchinomiya, Hirokazu Fuchida, Shigekazu Tabata, Itaru Hamachi, Ryuichi Shigemoto, and Akio Ojida. “Optimized Reaction Pair of the CysHis Tag and Ni(II)-NTA Probe for Highly Selective Chemical Labeling of Membrane Proteins.” Bulletin of the Chemical Society of Japan. Bulletin of the Chemical Society of Japan, 2019. https://doi.org/10.1246/bcsj.20190034. ieee: N. Zenmyo et al., “Optimized reaction pair of the CysHis tag and Ni(II)-NTA probe for highly selective chemical labeling of membrane proteins,” Bulletin of the Chemical Society of Japan, vol. 92, no. 5. Bulletin of the Chemical Society of Japan, pp. 995–1000, 2019. ista: Zenmyo N, Tokumaru H, Uchinomiya S, Fuchida H, Tabata S, Hamachi I, Shigemoto R, Ojida A. 2019. Optimized reaction pair of the CysHis tag and Ni(II)-NTA probe for highly selective chemical labeling of membrane proteins. Bulletin of the Chemical Society of Japan. 92(5), 995–1000. mla: Zenmyo, Naoki, et al. “Optimized Reaction Pair of the CysHis Tag and Ni(II)-NTA Probe for Highly Selective Chemical Labeling of Membrane Proteins.” Bulletin of the Chemical Society of Japan, vol. 92, no. 5, Bulletin of the Chemical Society of Japan, 2019, pp. 995–1000, doi:10.1246/bcsj.20190034. short: N. Zenmyo, H. Tokumaru, S. Uchinomiya, H. Fuchida, S. Tabata, I. Hamachi, R. Shigemoto, A. Ojida, Bulletin of the Chemical Society of Japan 92 (2019) 995–1000. date_created: 2019-07-21T21:59:16Z date_published: 2019-05-15T00:00:00Z date_updated: 2021-01-12T08:08:26Z day: '15' ddc: - '570' department: - _id: RySh doi: 10.1246/bcsj.20190034 ec_funded: 1 file: - access_level: open_access checksum: 186de511d6e0ca93f5d981e2443eb8cd content_type: application/pdf creator: dernst date_created: 2020-10-02T08:49:58Z date_updated: 2020-10-02T08:49:58Z file_id: '8594' file_name: 2019_BCSJ_Zenmyo.pdf file_size: 2464903 relation: main_file success: 1 file_date_updated: 2020-10-02T08:49:58Z has_accepted_license: '1' intvolume: ' 92' issue: '5' language: - iso: eng month: '05' oa: 1 oa_version: Published Version page: 995-1000 project: - _id: 25CA28EA-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '694539' name: 'In situ analysis of single channel subunit composition in neurons: physiological implication in synaptic plasticity and behaviour' publication: Bulletin of the Chemical Society of Japan publication_identifier: issn: - '00092673' publication_status: published publisher: Bulletin of the Chemical Society of Japan quality_controlled: '1' scopus_import: '1' status: public title: Optimized reaction pair of the CysHis tag and Ni(II)-NTA probe for highly selective chemical labeling of membrane proteins type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 92 year: '2019' ... --- _id: '6660' abstract: - lang: eng text: "Commercially available full-color 3D printing allows for detailed control of material deposition in a volume, but an exact reproduction of a target surface appearance is hampered by the strong subsurface scattering that causes nontrivial volumetric cross-talk at the print surface. Previous work showed how an iterative optimization scheme based on accumulating absorptive materials at the surface can be used to find a volumetric distribution of print materials that closely approximates a given target appearance.\r\n\r\nIn this work, we first revisit the assumption that pushing the absorptive materials to the surface results in minimal volumetric cross-talk. We design a full-fledged optimization on a small domain for this task and confirm this previously reported heuristic. Then, we extend the above approach that is critically limited to color reproduction on planar surfaces, to arbitrary 3D shapes. Our method enables high-fidelity color texture reproduction on 3D prints by effectively compensating for internal light scattering within arbitrarily shaped objects. In addition, we propose a content-aware gamut mapping that significantly improves color reproduction for the pathological case of thin geometric features. Using a wide range of sample objects with complex textures and geometries, we demonstrate color reproduction whose fidelity is superior to state-of-the-art drivers for color 3D printers." article_number: '111' article_processing_charge: No author: - first_name: Denis full_name: Sumin, Denis last_name: Sumin - first_name: Tim full_name: Weyrich, Tim last_name: Weyrich - first_name: Tobias full_name: Rittig, Tobias last_name: Rittig - first_name: Vahid full_name: Babaei, Vahid last_name: Babaei - first_name: Thomas full_name: Nindel, Thomas last_name: Nindel - first_name: Alexander full_name: Wilkie, Alexander last_name: Wilkie - first_name: Piotr full_name: Didyk, Piotr last_name: Didyk - first_name: Bernd full_name: Bickel, Bernd id: 49876194-F248-11E8-B48F-1D18A9856A87 last_name: Bickel orcid: 0000-0001-6511-9385 - first_name: Jaroslav full_name: Křivánek, Jaroslav last_name: Křivánek - first_name: Karol full_name: Myszkowski, Karol last_name: Myszkowski citation: ama: Sumin D, Weyrich T, Rittig T, et al. Geometry-aware scattering compensation for 3D printing. ACM Transactions on Graphics. 2019;38(4). doi:10.1145/3306346.3322992 apa: Sumin, D., Weyrich, T., Rittig, T., Babaei, V., Nindel, T., Wilkie, A., … Myszkowski, K. (2019). Geometry-aware scattering compensation for 3D printing. ACM Transactions on Graphics. ACM. https://doi.org/10.1145/3306346.3322992 chicago: Sumin, Denis, Tim Weyrich, Tobias Rittig, Vahid Babaei, Thomas Nindel, Alexander Wilkie, Piotr Didyk, Bernd Bickel, Jaroslav Křivánek, and Karol Myszkowski. “Geometry-Aware Scattering Compensation for 3D Printing.” ACM Transactions on Graphics. ACM, 2019. https://doi.org/10.1145/3306346.3322992. ieee: D. Sumin et al., “Geometry-aware scattering compensation for 3D printing,” ACM Transactions on Graphics, vol. 38, no. 4. ACM, 2019. ista: Sumin D, Weyrich T, Rittig T, Babaei V, Nindel T, Wilkie A, Didyk P, Bickel B, Křivánek J, Myszkowski K. 2019. Geometry-aware scattering compensation for 3D printing. ACM Transactions on Graphics. 38(4), 111. mla: Sumin, Denis, et al. “Geometry-Aware Scattering Compensation for 3D Printing.” ACM Transactions on Graphics, vol. 38, no. 4, 111, ACM, 2019, doi:10.1145/3306346.3322992. short: D. Sumin, T. Weyrich, T. Rittig, V. Babaei, T. Nindel, A. Wilkie, P. Didyk, B. Bickel, J. Křivánek, K. Myszkowski, ACM Transactions on Graphics 38 (2019). date_created: 2019-07-22T07:22:28Z date_published: 2019-07-04T00:00:00Z date_updated: 2023-08-29T06:40:49Z day: '04' ddc: - '000' department: - _id: BeBi doi: 10.1145/3306346.3322992 ec_funded: 1 external_id: isi: - '000475740600085' file: - access_level: open_access checksum: 43c2019d6b48ed9c56e31686c4c2d1f5 content_type: application/pdf creator: dernst date_created: 2019-07-24T07:36:08Z date_updated: 2020-07-14T12:47:36Z file_id: '6669' file_name: 2019_ACM_Sumin_AuthorVersion.pdf file_size: 10109800 relation: main_file - access_level: open_access checksum: f80f365a04e35855fa467ea7ab26b16c content_type: application/zip creator: dernst date_created: 2019-10-11T06:51:07Z date_updated: 2020-07-14T12:47:36Z file_id: '6938' file_name: sumin19geometry-aware-suppl.zip file_size: 11051245 relation: supplementary_material file_date_updated: 2020-07-14T12:47:36Z has_accepted_license: '1' intvolume: ' 38' isi: 1 issue: '4' language: - iso: eng month: '07' oa: 1 oa_version: Submitted Version project: - _id: 2508E324-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '642841' name: Distributed 3D Object Design - _id: 24F9549A-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '715767' name: 'MATERIALIZABLE: Intelligent fabrication-oriented Computational Design and Modeling' publication: ACM Transactions on Graphics publication_identifier: issn: - 0730-0301 publication_status: published publisher: ACM quality_controlled: '1' scopus_import: '1' status: public title: Geometry-aware scattering compensation for 3D printing type: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 38 year: '2019' ... --- _id: '6662' abstract: - lang: eng text: "In phase retrieval, we want to recover an unknown signal \U0001D465∈ℂ\U0001D451 from n quadratic measurements of the form \U0001D466\U0001D456=|⟨\U0001D44E\U0001D456,\U0001D465⟩|2+\U0001D464\U0001D456, where \U0001D44E\U0001D456∈ℂ\U0001D451 are known sensing vectors and \U0001D464\U0001D456 is measurement noise. We ask the following weak recovery question: What is the minimum number of measurements n needed to produce an estimator \U0001D465^(\U0001D466) that is positively correlated with the signal \U0001D465? We consider the case of Gaussian vectors \U0001D44E\U0001D44E\U0001D456. We prove that—in the high-dimensional limit—a sharp phase transition takes place, and we locate the threshold in the regime of vanishingly small noise. For \U0001D45B≤\U0001D451−\U0001D45C(\U0001D451), no estimator can do significantly better than random and achieve a strictly positive correlation. For \U0001D45B≥\U0001D451+\U0001D45C(\U0001D451), a simple spectral estimator achieves a positive correlation. Surprisingly, numerical simulations with the same spectral estimator demonstrate promising performance with realistic sensing matrices. Spectral methods are used to initialize non-convex optimization algorithms in phase retrieval, and our approach can boost the performance in this setting as well. Our impossibility result is based on classical information-theoretic arguments. The spectral algorithm computes the leading eigenvector of a weighted empirical covariance matrix. We obtain a sharp characterization of the spectral properties of this random matrix using tools from free probability and generalizing a recent result by Lu and Li. Both the upper bound and lower bound generalize beyond phase retrieval to measurements \U0001D466\U0001D456 produced according to a generalized linear model. As a by-product of our analysis, we compare the threshold of the proposed spectral method with that of a message passing algorithm." article_type: original arxiv: 1 author: - first_name: Marco full_name: Mondelli, Marco id: 27EB676C-8706-11E9-9510-7717E6697425 last_name: Mondelli orcid: 0000-0002-3242-7020 - first_name: Andrea full_name: Montanari, Andrea last_name: Montanari citation: ama: Mondelli M, Montanari A. Fundamental limits of weak recovery with applications to phase retrieval. Foundations of Computational Mathematics. 2019;19(3):703-773. doi:10.1007/s10208-018-9395-y apa: Mondelli, M., & Montanari, A. (2019). Fundamental limits of weak recovery with applications to phase retrieval. Foundations of Computational Mathematics. Springer. https://doi.org/10.1007/s10208-018-9395-y chicago: Mondelli, Marco, and Andrea Montanari. “Fundamental Limits of Weak Recovery with Applications to Phase Retrieval.” Foundations of Computational Mathematics. Springer, 2019. https://doi.org/10.1007/s10208-018-9395-y. ieee: M. Mondelli and A. Montanari, “Fundamental limits of weak recovery with applications to phase retrieval,” Foundations of Computational Mathematics, vol. 19, no. 3. Springer, pp. 703–773, 2019. ista: Mondelli M, Montanari A. 2019. Fundamental limits of weak recovery with applications to phase retrieval. Foundations of Computational Mathematics. 19(3), 703–773. mla: Mondelli, Marco, and Andrea Montanari. “Fundamental Limits of Weak Recovery with Applications to Phase Retrieval.” Foundations of Computational Mathematics, vol. 19, no. 3, Springer, 2019, pp. 703–73, doi:10.1007/s10208-018-9395-y. short: M. Mondelli, A. Montanari, Foundations of Computational Mathematics 19 (2019) 703–773. date_created: 2019-07-22T13:23:48Z date_published: 2019-06-01T00:00:00Z date_updated: 2021-01-12T08:08:28Z day: '01' doi: 10.1007/s10208-018-9395-y extern: '1' external_id: arxiv: - '1708.05932' intvolume: ' 19' issue: '3' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1708.05932 month: '06' oa: 1 oa_version: Preprint page: 703-773 publication: Foundations of Computational Mathematics publication_identifier: eissn: - 1615-3383 publication_status: published publisher: Springer quality_controlled: '1' status: public title: Fundamental limits of weak recovery with applications to phase retrieval type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 19 year: '2019' ... --- _id: '6663' abstract: - lang: eng text: Consider the problem of constructing a polar code of block length N for a given transmission channel W. Previous approaches require one to compute the reliability of the N synthetic channels and then use only those that are sufficiently reliable. However, we know from two independent works by Schürch and by Bardet et al. that the synthetic channels are partially ordered with respect to degradation. Hence, it is natural to ask whether the partial order can be exploited to reduce the computational burden of the construction problem. We show that, if we take advantage of the partial order, we can construct a polar code by computing the reliability of roughly a fraction 1/ log 3/2 N of the synthetic channels. In particular, we prove that N/ log 3/2 N is a lower bound on the number of synthetic channels to be considered and such a bound is tight up to a multiplicative factor log log N. This set of roughly N/ log 3/2 N synthetic channels is universal, in the sense that it allows one to construct polar codes for any W, and it can be identified by solving a maximum matching problem on a bipartite graph. Our proof technique consists of reducing the construction problem to the problem of computing the maximum cardinality of an antichain for a suitable partially ordered set. As such, this method is general, and it can be used to further improve the complexity of the construction problem, in case a refined partial order on the synthetic channels of polar codes is discovered. arxiv: 1 author: - first_name: Marco full_name: Mondelli, Marco id: 27EB676C-8706-11E9-9510-7717E6697425 last_name: Mondelli orcid: 0000-0002-3242-7020 - first_name: Hamed full_name: Hassani, Hamed last_name: Hassani - first_name: Rudiger full_name: Urbanke, Rudiger last_name: Urbanke citation: ama: Mondelli M, Hassani H, Urbanke R. Construction of polar codes with sublinear complexity. IEEE. 2019;65(5):2782-2791. doi:10.1109/tit.2018.2889667 apa: Mondelli, M., Hassani, H., & Urbanke, R. (2019). Construction of polar codes with sublinear complexity. IEEE. IEEE. https://doi.org/10.1109/tit.2018.2889667 chicago: Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “Construction of Polar Codes with Sublinear Complexity.” IEEE. IEEE, 2019. https://doi.org/10.1109/tit.2018.2889667. ieee: M. Mondelli, H. Hassani, and R. Urbanke, “Construction of polar codes with sublinear complexity,” IEEE, vol. 65, no. 5. IEEE, pp. 2782–2791, 2019. ista: Mondelli M, Hassani H, Urbanke R. 2019. Construction of polar codes with sublinear complexity. IEEE. 65(5), 2782–2791. mla: Mondelli, Marco, et al. “Construction of Polar Codes with Sublinear Complexity.” IEEE, vol. 65, no. 5, IEEE, 2019, pp. 2782–91, doi:10.1109/tit.2018.2889667. short: M. Mondelli, H. Hassani, R. Urbanke, IEEE 65 (2019) 2782–2791. date_created: 2019-07-23T07:32:57Z date_published: 2019-05-01T00:00:00Z date_updated: 2023-02-23T12:50:20Z day: '01' doi: 10.1109/tit.2018.2889667 extern: '1' external_id: arxiv: - '1612.05295' intvolume: ' 65' issue: '5' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1612.05295 month: '05' oa: 1 oa_version: Preprint page: 2782-2791 publication: IEEE publication_status: published publisher: IEEE quality_controlled: '1' related_material: record: - id: '6729' relation: earlier_version status: public status: public title: Construction of polar codes with sublinear complexity type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 65 year: '2019' ... --- _id: '6671' abstract: - lang: eng text: 'In this paper we discuss three results. The first two concern general sets of positive reach: we first characterize the reach of a closed set by means of a bound on the metric distortion between the distance measured in the ambient Euclidean space and the shortest path distance measured in the set. Secondly, we prove that the intersection of a ball with radius less than the reach with the set is geodesically convex, meaning that the shortest path between any two points in the intersection lies itself in the intersection. For our third result we focus on manifolds with positive reach and give a bound on the angle between tangent spaces at two different points in terms of the reach and the distance between the two points.' article_processing_charge: Yes (via OA deal) article_type: original author: - first_name: Jean-Daniel full_name: Boissonnat, Jean-Daniel last_name: Boissonnat - first_name: André full_name: Lieutier, André last_name: Lieutier - first_name: Mathijs full_name: Wintraecken, Mathijs id: 307CFBC8-F248-11E8-B48F-1D18A9856A87 last_name: Wintraecken orcid: 0000-0002-7472-2220 citation: ama: Boissonnat J-D, Lieutier A, Wintraecken M. The reach, metric distortion, geodesic convexity and the variation of tangent spaces. Journal of Applied and Computational Topology. 2019;3(1-2):29–58. doi:10.1007/s41468-019-00029-8 apa: Boissonnat, J.-D., Lieutier, A., & Wintraecken, M. (2019). The reach, metric distortion, geodesic convexity and the variation of tangent spaces. Journal of Applied and Computational Topology. Springer Nature. https://doi.org/10.1007/s41468-019-00029-8 chicago: Boissonnat, Jean-Daniel, André Lieutier, and Mathijs Wintraecken. “The Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces.” Journal of Applied and Computational Topology. Springer Nature, 2019. https://doi.org/10.1007/s41468-019-00029-8. ieee: J.-D. Boissonnat, A. Lieutier, and M. Wintraecken, “The reach, metric distortion, geodesic convexity and the variation of tangent spaces,” Journal of Applied and Computational Topology, vol. 3, no. 1–2. Springer Nature, pp. 29–58, 2019. ista: Boissonnat J-D, Lieutier A, Wintraecken M. 2019. The reach, metric distortion, geodesic convexity and the variation of tangent spaces. Journal of Applied and Computational Topology. 3(1–2), 29–58. mla: Boissonnat, Jean-Daniel, et al. “The Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces.” Journal of Applied and Computational Topology, vol. 3, no. 1–2, Springer Nature, 2019, pp. 29–58, doi:10.1007/s41468-019-00029-8. short: J.-D. Boissonnat, A. Lieutier, M. Wintraecken, Journal of Applied and Computational Topology 3 (2019) 29–58. date_created: 2019-07-24T08:37:29Z date_published: 2019-06-01T00:00:00Z date_updated: 2023-08-22T12:37:47Z day: '01' ddc: - '000' department: - _id: HeEd doi: 10.1007/s41468-019-00029-8 ec_funded: 1 file: - access_level: open_access checksum: a5b244db9f751221409cf09c97ee0935 content_type: application/pdf creator: dernst date_created: 2019-07-31T08:09:56Z date_updated: 2020-07-14T12:47:36Z file_id: '6741' file_name: 2019_JournAppliedComputTopol_Boissonnat.pdf file_size: 2215157 relation: main_file file_date_updated: 2020-07-14T12:47:36Z has_accepted_license: '1' intvolume: ' 3' issue: 1-2 language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: 29–58 project: - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships - _id: B67AFEDC-15C9-11EA-A837-991A96BB2854 name: IST Austria Open Access Fund publication: Journal of Applied and Computational Topology publication_identifier: eissn: - 2367-1734 issn: - 2367-1726 publication_status: published publisher: Springer Nature quality_controlled: '1' status: public title: The reach, metric distortion, geodesic convexity and the variation of tangent spaces 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: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 3 year: '2019' ... --- _id: '6672' abstract: - lang: eng text: The construction of anisotropic triangulations is desirable for various applications, such as the numerical solving of partial differential equations and the representation of surfaces in graphics. To solve this notoriously difficult problem in a practical way, we introduce the discrete Riemannian Voronoi diagram, a discrete structure that approximates the Riemannian Voronoi diagram. This structure has been implemented and was shown to lead to good triangulations in $\mathbb{R}^2$ and on surfaces embedded in $\mathbb{R}^3$ as detailed in our experimental companion paper. In this paper, we study theoretical aspects of our structure. Given a finite set of points $\mathcal{P}$ in a domain $\Omega$ equipped with a Riemannian metric, we compare the discrete Riemannian Voronoi diagram of $\mathcal{P}$ to its Riemannian Voronoi diagram. Both diagrams have dual structures called the discrete Riemannian Delaunay and the Riemannian Delaunay complex. We provide conditions that guarantee that these dual structures are identical. It then follows from previous results that the discrete Riemannian Delaunay complex can be embedded in $\Omega$ under sufficient conditions, leading to an anisotropic triangulation with curved simplices. Furthermore, we show that, under similar conditions, the simplices of this triangulation can be straightened. arxiv: 1 author: - first_name: Jean-Daniel full_name: Boissonnat, Jean-Daniel last_name: Boissonnat - first_name: Mael full_name: Rouxel-Labbé, Mael last_name: Rouxel-Labbé - first_name: Mathijs full_name: Wintraecken, Mathijs id: 307CFBC8-F248-11E8-B48F-1D18A9856A87 last_name: Wintraecken orcid: 0000-0002-7472-2220 citation: ama: Boissonnat J-D, Rouxel-Labbé M, Wintraecken M. Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. 2019;48(3):1046-1097. doi:10.1137/17m1152292 apa: Boissonnat, J.-D., Rouxel-Labbé, M., & Wintraecken, M. (2019). Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM). https://doi.org/10.1137/17m1152292 chicago: Boissonnat, Jean-Daniel, Mael Rouxel-Labbé, and Mathijs Wintraecken. “Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM), 2019. https://doi.org/10.1137/17m1152292. ieee: J.-D. Boissonnat, M. Rouxel-Labbé, and M. Wintraecken, “Anisotropic triangulations via discrete Riemannian Voronoi diagrams,” SIAM Journal on Computing, vol. 48, no. 3. Society for Industrial & Applied Mathematics (SIAM), pp. 1046–1097, 2019. ista: Boissonnat J-D, Rouxel-Labbé M, Wintraecken M. 2019. Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. 48(3), 1046–1097. mla: Boissonnat, Jean-Daniel, et al. “Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams.” SIAM Journal on Computing, vol. 48, no. 3, Society for Industrial & Applied Mathematics (SIAM), 2019, pp. 1046–97, doi:10.1137/17m1152292. short: J.-D. Boissonnat, M. Rouxel-Labbé, M. Wintraecken, SIAM Journal on Computing 48 (2019) 1046–1097. date_created: 2019-07-24T08:42:12Z date_published: 2019-05-21T00:00:00Z date_updated: 2021-01-12T08:08:30Z day: '21' doi: 10.1137/17m1152292 extern: '1' external_id: arxiv: - '1703.06487' intvolume: ' 48' issue: '3' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1703.06487 month: '05' oa: 1 oa_version: Preprint page: 1046-1097 publication: SIAM Journal on Computing publication_identifier: eissn: - 1095-7111 issn: - 0097-5397 publication_status: published publisher: Society for Industrial & Applied Mathematics (SIAM) quality_controlled: '1' status: public title: Anisotropic triangulations via discrete Riemannian Voronoi diagrams type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 48 year: '2019' ... --- _id: '6673' abstract: - lang: eng text: Several classic problems in graph processing and computational geometry are solved via incremental algorithms, which split computation into a series of small tasks acting on shared state, which gets updated progressively. While the sequential variant of such algorithms usually specifies a fixed (but sometimes random) order in which the tasks should be performed, a standard approach to parallelizing such algorithms is to relax this constraint to allow for out-of-order parallel execution. This is the case for parallel implementations of Dijkstra's single-source shortest-paths (SSSP) algorithm, and for parallel Delaunay mesh triangulation. While many software frameworks parallelize incremental computation in this way, it is still not well understood whether this relaxed ordering approach can still provide any complexity guarantees. In this paper, we address this problem, and analyze the efficiency guarantees provided by a range of incremental algorithms when parallelized via relaxed schedulers. We show that, for algorithms such as Delaunay mesh triangulation and sorting by insertion, schedulers with a maximum relaxation factor of k in terms of the maximum priority inversion allowed will introduce a maximum amount of wasted work of O(łog n poly(k)), where n is the number of tasks to be executed. For SSSP, we show that the additional work is O(poly(k), dmax / wmin), where dmax is the maximum distance between two nodes, and wmin is the minimum such distance. In practical settings where n >> k, this suggests that the overheads of relaxation will be outweighed by the improved scalability of the relaxed scheduler. On the negative side, we provide lower bounds showing that certain algorithms will inherently incur a non-trivial amount of wasted work due to scheduler relaxation, even for relatively benign relaxed schedulers. article_processing_charge: No arxiv: 1 author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Giorgi full_name: Nadiradze, Giorgi id: 3279A00C-F248-11E8-B48F-1D18A9856A87 last_name: Nadiradze orcid: 0000-0001-5634-0731 - first_name: Nikita full_name: Koval, Nikita id: 2F4DB10C-F248-11E8-B48F-1D18A9856A87 last_name: Koval citation: ama: 'Alistarh D-A, Nadiradze G, Koval N. Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. In: 31st ACM Symposium on Parallelism in Algorithms and Architectures. ACM Press; 2019:145-154. doi:10.1145/3323165.3323201' apa: 'Alistarh, D.-A., Nadiradze, G., & Koval, N. (2019). Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. In 31st ACM Symposium on Parallelism in Algorithms and Architectures (pp. 145–154). Phoenix, AZ, United States: ACM Press. https://doi.org/10.1145/3323165.3323201' chicago: Alistarh, Dan-Adrian, Giorgi Nadiradze, and Nikita Koval. “Efficiency Guarantees for Parallel Incremental Algorithms under Relaxed Schedulers.” In 31st ACM Symposium on Parallelism in Algorithms and Architectures, 145–54. ACM Press, 2019. https://doi.org/10.1145/3323165.3323201. ieee: D.-A. Alistarh, G. Nadiradze, and N. Koval, “Efficiency guarantees for parallel incremental algorithms under relaxed schedulers,” in 31st ACM Symposium on Parallelism in Algorithms and Architectures, Phoenix, AZ, United States, 2019, pp. 145–154. ista: 'Alistarh D-A, Nadiradze G, Koval N. 2019. Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. 31st ACM Symposium on Parallelism in Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms and Architectures, 145–154.' mla: Alistarh, Dan-Adrian, et al. “Efficiency Guarantees for Parallel Incremental Algorithms under Relaxed Schedulers.” 31st ACM Symposium on Parallelism in Algorithms and Architectures, ACM Press, 2019, pp. 145–54, doi:10.1145/3323165.3323201. short: D.-A. Alistarh, G. Nadiradze, N. Koval, in:, 31st ACM Symposium on Parallelism in Algorithms and Architectures, ACM Press, 2019, pp. 145–154. conference: end_date: 2019-06-24 location: Phoenix, AZ, United States name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures' start_date: 2019-06-22 date_created: 2019-07-24T08:59:36Z date_published: 2019-06-01T00:00:00Z date_updated: 2023-09-07T13:31:39Z day: '01' department: - _id: DaAl doi: 10.1145/3323165.3323201 ec_funded: 1 external_id: arxiv: - '2003.09363' isi: - '000507618500018' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2003.09363 month: '06' oa: 1 oa_version: Preprint page: 145-154 project: - _id: 268A44D6-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '805223' name: Elastic Coordination for Scalable Machine Learning publication: 31st ACM Symposium on Parallelism in Algorithms and Architectures publication_identifier: isbn: - '9781450361842' publication_status: published publisher: ACM Press quality_controlled: '1' related_material: record: - id: '10429' relation: dissertation_contains status: public scopus_import: '1' status: public title: Efficiency guarantees for parallel incremental algorithms under relaxed schedulers type: conference user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 year: '2019' ... --- _id: '6676' abstract: - lang: eng text: "It is impossible to deterministically solve wait-free consensus in an asynchronous system. The classic proof uses a valency argument, which constructs an infinite execution by repeatedly extending a finite execution. We introduce extension-based proofs, a class of impossibility proofs that are modelled as an interaction between a prover and a protocol and that include valency arguments.\r\n\r\nUsing proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k ≥ 2 processes in a wait-free manner. However, it was unknown whether proofs based on simpler techniques were possible. We show that this impossibility result cannot be obtained by an extension-based proof and, hence, extension-based proofs are limited in power." article_processing_charge: No arxiv: 1 author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: James full_name: Aspnes, James last_name: Aspnes - first_name: Faith full_name: Ellen, Faith last_name: Ellen - first_name: Rati full_name: Gelashvili, Rati last_name: Gelashvili - first_name: Leqi full_name: Zhu, Leqi last_name: Zhu citation: ama: 'Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Why extension-based proofs fail. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. ACM Press; 2019:986-996. doi:10.1145/3313276.3316407' apa: 'Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., & Zhu, L. (2019). Why extension-based proofs fail. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (pp. 986–996). Phoenix, AZ, United States: ACM Press. https://doi.org/10.1145/3313276.3316407' chicago: Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. “Why Extension-Based Proofs Fail.” In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 986–96. ACM Press, 2019. https://doi.org/10.1145/3313276.3316407. ieee: D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Why extension-based proofs fail,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Phoenix, AZ, United States, 2019, pp. 986–996. ista: 'Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2019. Why extension-based proofs fail. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 986–996.' mla: Alistarh, Dan-Adrian, et al. “Why Extension-Based Proofs Fail.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM Press, 2019, pp. 986–96, doi:10.1145/3313276.3316407. short: D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM Press, 2019, pp. 986–996. conference: end_date: 2019-06-26 location: Phoenix, AZ, United States name: 'STOC: Symposium on Theory of Computing' start_date: 2019-06-23 date_created: 2019-07-24T09:13:05Z date_published: 2019-06-01T00:00:00Z date_updated: 2023-12-13T12:28:28Z day: '01' department: - _id: DaAl doi: 10.1145/3313276.3316407 external_id: arxiv: - '1811.01421' isi: - '000523199100089' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1811.01421 month: '06' oa: 1 oa_version: Preprint page: 986-996 publication: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing publication_identifier: isbn: - '9781450367059' publication_status: published publisher: ACM Press quality_controlled: '1' related_material: record: - id: '14364' relation: later_version status: public scopus_import: '1' status: public title: Why extension-based proofs fail type: conference user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 year: '2019' ... --- _id: '6677' abstract: - lang: eng text: "The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.\r\n\r\nWe show that solving the END−OF−METERED−LINE problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD. Our result opens up the possibility of sampling moderately-sized games for which it is hard to find a Nash equilibrium, by reducing the inversion of appropriately chosen one-way functions to #SAT.\r\n\r\nOur main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n)." article_processing_charge: No author: - first_name: Arka Rai full_name: Choudhuri, Arka Rai last_name: Choudhuri - first_name: Pavel full_name: Hubáček, Pavel last_name: Hubáček - first_name: Chethan full_name: Kamath Hosdurg, Chethan id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87 last_name: Kamath Hosdurg - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 - first_name: Alon full_name: Rosen, Alon last_name: Rosen - first_name: Guy N. full_name: Rothblum, Guy N. last_name: Rothblum citation: ama: 'Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum GN. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019. ACM Press; 2019:1103-1114. doi:10.1145/3313276.3316400' apa: 'Choudhuri, A. R., Hubáček, P., Kamath Hosdurg, C., Pietrzak, K. Z., Rosen, A., & Rothblum, G. N. (2019). Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019 (pp. 1103–1114). Phoenix, AZ, United States: ACM Press. https://doi.org/10.1145/3313276.3316400' chicago: Choudhuri, Arka Rai, Pavel Hubáček, Chethan Kamath Hosdurg, Krzysztof Z Pietrzak, Alon Rosen, and Guy N. Rothblum. “Finding a Nash Equilibrium Is No Easier than Breaking Fiat-Shamir.” In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019, 1103–14. ACM Press, 2019. https://doi.org/10.1145/3313276.3316400. ieee: A. R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K. Z. Pietrzak, A. Rosen, and G. N. Rothblum, “Finding a Nash equilibrium is no easier than breaking Fiat-Shamir,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019, Phoenix, AZ, United States, 2019, pp. 1103–1114. ista: 'Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum GN. 2019. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019. STOC: Symposium on Theory of Computing, 1103–1114.' mla: Choudhuri, Arka Rai, et al. “Finding a Nash Equilibrium Is No Easier than Breaking Fiat-Shamir.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019, ACM Press, 2019, pp. 1103–14, doi:10.1145/3313276.3316400. short: A.R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K.Z. Pietrzak, A. Rosen, G.N. Rothblum, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019, ACM Press, 2019, pp. 1103–1114. conference: end_date: 2019-06-26 location: Phoenix, AZ, United States name: 'STOC: Symposium on Theory of Computing' start_date: 2019-06-23 date_created: 2019-07-24T09:20:53Z date_published: 2019-06-01T00:00:00Z date_updated: 2023-09-07T13:15:55Z day: '01' department: - _id: KrPi doi: 10.1145/3313276.3316400 ec_funded: 1 external_id: isi: - '000523199100100' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2019/549 month: '06' oa: 1 oa_version: Preprint page: 1103-1114 project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019 publication_identifier: isbn: - '9781450367059' publication_status: published publisher: ACM Press quality_controlled: '1' related_material: record: - id: '7896' relation: dissertation_contains status: public scopus_import: '1' status: public title: Finding a Nash equilibrium is no easier than breaking Fiat-Shamir type: conference user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 year: '2019' ... --- _id: '6680' abstract: - lang: eng text: This paper analyzes how partial selfing in a large source population influences its ability to colonize a new habitat via the introduction of a few founder individuals. Founders experience inbreeding depression due to partially recessive deleterious alleles as well as maladaptation to the new environment due to selection on a large number of additive loci. I first introduce a simplified version of the Inbreeding History Model (Kelly, 2007) in order to characterize mutation‐selection balance in a large, partially selfing source population under selection involving multiple non‐identical loci. I then use individual‐based simulations to study the eco‐evolutionary dynamics of founders establishing in the new habitat under a model of hard selection. The study explores how selfing rate shapes establishment probabilities of founders via effects on both inbreeding depression and adaptability to the new environment, and also distinguishes the effects of selfing on the initial fitness of founders from its effects on the long‐term adaptive response of the populations they found. A high rate of (but not complete) selfing is found to aid establishment over a wide range of parameters, even in the absence of mate limitation. The sensitivity of the results to assumptions about the nature of polygenic selection are discussed. article_processing_charge: Yes (via OA deal) author: - first_name: Himani full_name: Sachdeva, Himani id: 42377A0A-F248-11E8-B48F-1D18A9856A87 last_name: Sachdeva citation: ama: Sachdeva H. Effect of partial selfing and polygenic selection on establishment in a new habitat. Evolution. 2019;73(9):1729-1745. doi:10.1111/evo.13812 apa: Sachdeva, H. (2019). Effect of partial selfing and polygenic selection on establishment in a new habitat. Evolution. Wiley. https://doi.org/10.1111/evo.13812 chicago: Sachdeva, Himani. “Effect of Partial Selfing and Polygenic Selection on Establishment in a New Habitat.” Evolution. Wiley, 2019. https://doi.org/10.1111/evo.13812. ieee: H. Sachdeva, “Effect of partial selfing and polygenic selection on establishment in a new habitat,” Evolution, vol. 73, no. 9. Wiley, pp. 1729–1745, 2019. ista: Sachdeva H. 2019. Effect of partial selfing and polygenic selection on establishment in a new habitat. Evolution. 73(9), 1729–1745. mla: Sachdeva, Himani. “Effect of Partial Selfing and Polygenic Selection on Establishment in a New Habitat.” Evolution, vol. 73, no. 9, Wiley, 2019, pp. 1729–45, doi:10.1111/evo.13812. short: H. Sachdeva, Evolution 73 (2019) 1729–1745. date_created: 2019-07-25T09:08:28Z date_published: 2019-09-01T00:00:00Z date_updated: 2023-08-29T06:43:58Z day: '01' ddc: - '576' department: - _id: NiBa doi: 10.1111/evo.13812 external_id: isi: - '000481300600001' file: - access_level: open_access checksum: 772ce7035965153959b946a1033de1ca content_type: application/pdf creator: kschuh date_created: 2019-09-17T10:56:27Z date_updated: 2020-07-14T12:47:37Z file_id: '6881' file_name: 2019_Evolution_Sachdeva.pdf file_size: 937573 relation: main_file file_date_updated: 2020-07-14T12:47:37Z has_accepted_license: '1' intvolume: ' 73' isi: 1 issue: '9' language: - iso: eng month: '09' oa: 1 oa_version: Published Version page: 1729-1745 publication: Evolution publication_identifier: eissn: - 1558-5646 issn: - 0014-3820 publication_status: published publisher: Wiley quality_controlled: '1' related_material: record: - id: '9802' relation: research_data status: public scopus_import: '1' status: public title: Effect of partial selfing and polygenic selection on establishment in a new habitat 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: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 73 year: '2019' ... --- _id: '6681' abstract: - lang: eng text: "The first part of the thesis considers the computational aspects of the homotopy groups πd(X) of a topological space X. It is well known that there is no algorithm to decide whether the fundamental group π1(X) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute the higher homotopy group πd(X) for any given d ≥ 2.\r\nHowever, these algorithms come with a caveat: They compute the isomorphism type of πd(X), d ≥ 2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πd(X). We present an algorithm that, given a simply connected space X, computes πd(X) and represents its elements as simplicial maps from suitable triangulations of the d-sphere Sd to X. For fixed d, the algorithm runs in time exponential in size(X), the number of simplices of X. Moreover, we prove that this is optimal: For every fixed d ≥ 2,\r\nwe construct a family of simply connected spaces X such that for any simplicial map representing a generator of πd(X), the size of the triangulation of S d on which the map is defined, is exponential in size(X).\r\nIn the second part of the thesis, we prove that the following question is algorithmically undecidable for d < ⌊3(k+1)/2⌋, k ≥ 5 and (k, d) ̸= (5, 7), which covers essentially everything outside the meta-stable range: Given a finite simplicial complex K of dimension k, decide whether there exists a piecewise-linear (i.e., linear on an arbitrarily fine subdivision of K) embedding f : K ↪→ Rd of K into a d-dimensional Euclidean space." alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Stephan Y full_name: Zhechev, Stephan Y id: 3AA52972-F248-11E8-B48F-1D18A9856A87 last_name: Zhechev citation: ama: Zhechev SY. Algorithmic aspects of homotopy theory and embeddability. 2019. doi:10.15479/AT:ISTA:6681 apa: Zhechev, S. Y. (2019). Algorithmic aspects of homotopy theory and embeddability. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:6681 chicago: Zhechev, Stephan Y. “Algorithmic Aspects of Homotopy Theory and Embeddability.” Institute of Science and Technology Austria, 2019. https://doi.org/10.15479/AT:ISTA:6681. ieee: S. Y. Zhechev, “Algorithmic aspects of homotopy theory and embeddability,” Institute of Science and Technology Austria, 2019. ista: Zhechev SY. 2019. Algorithmic aspects of homotopy theory and embeddability. Institute of Science and Technology Austria. mla: Zhechev, Stephan Y. Algorithmic Aspects of Homotopy Theory and Embeddability. Institute of Science and Technology Austria, 2019, doi:10.15479/AT:ISTA:6681. short: S.Y. Zhechev, Algorithmic Aspects of Homotopy Theory and Embeddability, Institute of Science and Technology Austria, 2019. date_created: 2019-07-26T11:14:34Z date_published: 2019-08-08T00:00:00Z date_updated: 2023-09-07T13:10:36Z day: '08' ddc: - '514' degree_awarded: PhD department: - _id: UlWa doi: 10.15479/AT:ISTA:6681 file: - access_level: open_access checksum: 3231e7cbfca3b5687366f84f0a57a0c0 content_type: application/pdf creator: szhechev date_created: 2019-08-07T13:02:50Z date_updated: 2020-07-14T12:47:37Z file_id: '6771' file_name: Stephan_Zhechev_thesis.pdf file_size: 1464227 relation: main_file - access_level: closed checksum: 85d65eb27b4377a9e332ee37a70f08b6 content_type: application/octet-stream creator: szhechev date_created: 2019-08-07T13:03:22Z date_updated: 2020-07-14T12:47:37Z file_id: '6772' file_name: Stephan_Zhechev_thesis.tex file_size: 303988 relation: source_file - access_level: closed checksum: 86b374d264ca2dd53e712728e253ee75 content_type: application/zip creator: szhechev date_created: 2019-08-07T13:03:34Z date_updated: 2020-07-14T12:47:37Z file_id: '6773' file_name: supplementary_material.zip file_size: 1087004 relation: supplementary_material file_date_updated: 2020-07-14T12:47:37Z has_accepted_license: '1' language: - iso: eng month: '08' oa: 1 oa_version: Published Version page: '104' publication_identifier: issn: - 2663-337X publication_status: published publisher: Institute of Science and Technology Austria related_material: record: - id: '6774' 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 title: Algorithmic aspects of homotopy theory and embeddability 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: '2019' ... --- _id: '6710' abstract: - lang: eng text: Sexual dimorphism in morphology, physiology or life history traits is common in dioecious plants at reproductive maturity, but it is typically inconspicuous or absent in juveniles. Although plants of different sexes probably begin to diverge in gene expression both before their reproduction commences and before dimorphism becomes readily apparent, to our knowledge transcriptome-wide differential gene expression has yet to be demonstrated for any angiosperm species. article_processing_charge: No article_type: original author: - first_name: Guillaume full_name: Cossard, Guillaume last_name: Cossard - first_name: Melissa A full_name: Toups, Melissa A id: 4E099E4E-F248-11E8-B48F-1D18A9856A87 last_name: Toups orcid: 0000-0002-9752-7380 - first_name: 'John ' full_name: 'Pannell, John ' last_name: Pannell citation: ama: Cossard G, Toups MA, Pannell J. Sexual dimorphism and rapid turnover in gene expression in pre-reproductive seedlings of a dioecious herb. Annals of botany. 2019;123(7):1119-1131. doi:10.1093/aob/mcy183 apa: Cossard, G., Toups, M. A., & Pannell, J. (2019). Sexual dimorphism and rapid turnover in gene expression in pre-reproductive seedlings of a dioecious herb. Annals of Botany. Oxford University Press. https://doi.org/10.1093/aob/mcy183 chicago: Cossard, Guillaume, Melissa A Toups, and John Pannell. “Sexual Dimorphism and Rapid Turnover in Gene Expression in Pre-Reproductive Seedlings of a Dioecious Herb.” Annals of Botany. Oxford University Press, 2019. https://doi.org/10.1093/aob/mcy183. ieee: G. Cossard, M. A. Toups, and J. Pannell, “Sexual dimorphism and rapid turnover in gene expression in pre-reproductive seedlings of a dioecious herb,” Annals of botany, vol. 123, no. 7. Oxford University Press, pp. 1119–1131, 2019. ista: Cossard G, Toups MA, Pannell J. 2019. Sexual dimorphism and rapid turnover in gene expression in pre-reproductive seedlings of a dioecious herb. Annals of botany. 123(7), 1119–1131. mla: Cossard, Guillaume, et al. “Sexual Dimorphism and Rapid Turnover in Gene Expression in Pre-Reproductive Seedlings of a Dioecious Herb.” Annals of Botany, vol. 123, no. 7, Oxford University Press, 2019, pp. 1119–31, doi:10.1093/aob/mcy183. short: G. Cossard, M.A. Toups, J. Pannell, Annals of Botany 123 (2019) 1119–1131. date_created: 2019-07-28T21:59:15Z date_published: 2019-06-04T00:00:00Z date_updated: 2023-08-29T06:42:22Z day: '04' department: - _id: BeVi doi: 10.1093/aob/mcy183 external_id: isi: - '000493043500004' pmid: - '30289430' intvolume: ' 123' isi: 1 issue: '7' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.1093/aob/mcy183 month: '06' oa: 1 oa_version: Published Version page: 1119-1131 pmid: 1 publication: Annals of botany publication_identifier: eissn: - 1095-8290 issn: - 0305-7364 publication_status: published publisher: Oxford University Press quality_controlled: '1' scopus_import: '1' status: public title: Sexual dimorphism and rapid turnover in gene expression in pre-reproductive seedlings of a dioecious herb type: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 123 year: '2019' ... --- _id: '6713' abstract: - lang: eng text: Evolutionary studies are often limited by missing data that are critical to understanding the history of selection. Selection experiments, which reproduce rapid evolution under controlled conditions, are excellent tools to study how genomes evolve under selection. Here we present a genomic dissection of the Longshanks selection experiment, in which mice were selectively bred over 20 generations for longer tibiae relative to body mass, resulting in 13% longer tibiae in two replicates. We synthesized evolutionary theory, genome sequences and molecular genetics to understand the selection response and found that it involved both polygenic adaptation and discrete loci of major effect, with the strongest loci tending to be selected in parallel between replicates. We show that selection may favor de-repression of bone growth through inactivating two limb enhancers of an inhibitor, Nkx3-2. Our integrative genomic analyses thus show that it is possible to connect individual base-pair changes to the overall selection response. article_number: e42014 article_processing_charge: No author: - first_name: João Pl full_name: Castro, João Pl last_name: Castro - first_name: Michelle N. full_name: Yancoskie, Michelle N. last_name: Yancoskie - first_name: Marta full_name: Marchini, Marta last_name: Marchini - first_name: Stefanie full_name: Belohlavy, Stefanie id: 43FE426A-F248-11E8-B48F-1D18A9856A87 last_name: Belohlavy orcid: 0000-0002-9849-498X - first_name: Layla full_name: Hiramatsu, Layla last_name: Hiramatsu - first_name: Marek full_name: Kučka, Marek last_name: Kučka - first_name: William H. full_name: Beluch, William H. last_name: Beluch - first_name: Ronald full_name: Naumann, Ronald last_name: Naumann - first_name: Isabella full_name: Skuplik, Isabella last_name: Skuplik - first_name: John full_name: Cobb, John last_name: Cobb - first_name: Nicholas H full_name: Barton, Nicholas H id: 4880FE40-F248-11E8-B48F-1D18A9856A87 last_name: Barton orcid: 0000-0002-8548-5240 - first_name: Campbell full_name: Rolian, Campbell last_name: Rolian - first_name: Yingguang Frank full_name: Chan, Yingguang Frank last_name: Chan citation: ama: Castro JP, Yancoskie MN, Marchini M, et al. An integrative genomic analysis of the Longshanks selection experiment for longer limbs in mice. eLife. 2019;8. doi:10.7554/eLife.42014 apa: Castro, J. P., Yancoskie, M. N., Marchini, M., Belohlavy, S., Hiramatsu, L., Kučka, M., … Chan, Y. F. (2019). An integrative genomic analysis of the Longshanks selection experiment for longer limbs in mice. ELife. eLife Sciences Publications. https://doi.org/10.7554/eLife.42014 chicago: Castro, João Pl, Michelle N. Yancoskie, Marta Marchini, Stefanie Belohlavy, Layla Hiramatsu, Marek Kučka, William H. Beluch, et al. “An Integrative Genomic Analysis of the Longshanks Selection Experiment for Longer Limbs in Mice.” ELife. eLife Sciences Publications, 2019. https://doi.org/10.7554/eLife.42014. ieee: J. P. Castro et al., “An integrative genomic analysis of the Longshanks selection experiment for longer limbs in mice,” eLife, vol. 8. eLife Sciences Publications, 2019. ista: Castro JP, Yancoskie MN, Marchini M, Belohlavy S, Hiramatsu L, Kučka M, Beluch WH, Naumann R, Skuplik I, Cobb J, Barton NH, Rolian C, Chan YF. 2019. An integrative genomic analysis of the Longshanks selection experiment for longer limbs in mice. eLife. 8, e42014. mla: Castro, João Pl, et al. “An Integrative Genomic Analysis of the Longshanks Selection Experiment for Longer Limbs in Mice.” ELife, vol. 8, e42014, eLife Sciences Publications, 2019, doi:10.7554/eLife.42014. short: J.P. Castro, M.N. Yancoskie, M. Marchini, S. Belohlavy, L. Hiramatsu, M. Kučka, W.H. Beluch, R. Naumann, I. Skuplik, J. Cobb, N.H. Barton, C. Rolian, Y.F. Chan, ELife 8 (2019). date_created: 2019-07-28T21:59:17Z date_published: 2019-06-06T00:00:00Z date_updated: 2024-03-25T23:30:11Z day: '06' ddc: - '576' department: - _id: NiBa doi: 10.7554/eLife.42014 external_id: isi: - '000473588700001' pmid: - '31169497' file: - access_level: open_access checksum: fa0936fe58f0d9e3f8e75038570e5a17 content_type: application/pdf creator: apreinsp date_created: 2019-07-29T07:41:18Z date_updated: 2020-07-14T12:47:38Z file_id: '6721' file_name: 2019_eLife_Castro.pdf file_size: 6748249 relation: main_file file_date_updated: 2020-07-14T12:47:38Z has_accepted_license: '1' intvolume: ' 8' isi: 1 language: - iso: eng month: '06' oa: 1 oa_version: Published Version pmid: 1 publication: eLife publication_status: published publisher: eLife Sciences Publications quality_controlled: '1' related_material: record: - id: '9804' relation: research_data status: public - id: '11388' relation: dissertation_contains status: public scopus_import: '1' status: public title: An integrative genomic analysis of the Longshanks selection experiment for longer limbs in mice 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: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 8 year: '2019' ... --- _id: '6717' abstract: - lang: eng text: With the recent publication by Silpe and Bassler (2019), considering phage detection of a bacterial quorum-sensing (QS) autoinducer, we now have as many as five examples of phage-associated intercellular communication (Table 1). Each potentially involves ecological inferences by phages as to concentrations of surrounding phage-infected or uninfected bacteria. While the utility of phage detection of bacterial QS molecules may at first glance appear to be straightforward, we suggest in this commentary that the underlying ecological explanation is unlikely to be simple. article_number: '1171' article_processing_charge: Yes (via OA deal) author: - first_name: Claudia full_name: Igler, Claudia id: 46613666-F248-11E8-B48F-1D18A9856A87 last_name: Igler - first_name: Stephen T. full_name: Abedon, Stephen T. last_name: Abedon citation: ama: 'Igler C, Abedon ST. Commentary: A host-produced quorum-sensing autoinducer controls a phage lysis-lysogeny decision. Frontiers in Microbiology. 2019;10. doi:10.3389/fmicb.2019.01171' apa: 'Igler, C., & Abedon, S. T. (2019). Commentary: A host-produced quorum-sensing autoinducer controls a phage lysis-lysogeny decision. Frontiers in Microbiology. Frontiers. https://doi.org/10.3389/fmicb.2019.01171' chicago: 'Igler, Claudia, and Stephen T. Abedon. “Commentary: A Host-Produced Quorum-Sensing Autoinducer Controls a Phage Lysis-Lysogeny Decision.” Frontiers in Microbiology. Frontiers, 2019. https://doi.org/10.3389/fmicb.2019.01171.' ieee: 'C. Igler and S. T. Abedon, “Commentary: A host-produced quorum-sensing autoinducer controls a phage lysis-lysogeny decision,” Frontiers in Microbiology, vol. 10. Frontiers, 2019.' ista: 'Igler C, Abedon ST. 2019. Commentary: A host-produced quorum-sensing autoinducer controls a phage lysis-lysogeny decision. Frontiers in Microbiology. 10, 1171.' mla: 'Igler, Claudia, and Stephen T. Abedon. “Commentary: A Host-Produced Quorum-Sensing Autoinducer Controls a Phage Lysis-Lysogeny Decision.” Frontiers in Microbiology, vol. 10, 1171, Frontiers, 2019, doi:10.3389/fmicb.2019.01171.' short: C. Igler, S.T. Abedon, Frontiers in Microbiology 10 (2019). date_created: 2019-07-28T21:59:18Z date_published: 2019-06-03T00:00:00Z date_updated: 2023-08-29T06:41:20Z day: '03' ddc: - '570' department: - _id: CaGu doi: 10.3389/fmicb.2019.01171 external_id: isi: - '000470131200001' file: - access_level: open_access checksum: 317a06067e9a8e717bb55f23e0d77ba7 content_type: application/pdf creator: apreinsp date_created: 2019-07-29T07:51:54Z date_updated: 2020-07-14T12:47:38Z file_id: '6722' file_name: 2019_Frontiers_Igler.pdf file_size: 246151 relation: main_file file_date_updated: 2020-07-14T12:47:38Z has_accepted_license: '1' intvolume: ' 10' isi: 1 language: - iso: eng month: '06' oa: 1 oa_version: Published Version project: - _id: 251EE76E-B435-11E9-9278-68D0E5697425 grant_number: '24573' name: Design principles underlying genetic switch architecture (DOC Fellowship) publication: Frontiers in Microbiology publication_status: published publisher: Frontiers quality_controlled: '1' scopus_import: '1' status: public title: 'Commentary: A host-produced quorum-sensing autoinducer controls a phage lysis-lysogeny decision' 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: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 10 year: '2019' ... --- _id: '6725' abstract: - lang: eng text: "A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that can express a wide range of discrete optimization problems. A VCSP instance is given by a finite set of variables, a finite domain of labels, and an objective function to be minimized. This function is represented as a sum of terms where each term depends on a subset of the variables. To obtain different classes of optimization problems, one can restrict all terms to come from a fixed set Γ of cost functions, called a language. \r\nRecent breakthrough results have established a complete complexity classification of such classes with respect to language Γ: if all cost functions in Γ satisfy a certain algebraic condition then all Γ-instances can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately, testing this condition for a given language Γ is known to be NP-hard. We thus study exponential algorithms for this meta-problem. We show that the tractability condition of a finite-valued language Γ can be tested in O(3‾√3|D|⋅poly(size(Γ))) time, where D is the domain of Γ and poly(⋅) is some fixed polynomial. We also obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH). More precisely, we prove that for any constant δ<1 there is no O(3‾√3δ|D|) algorithm, assuming that SETH holds." alternative_title: - LIPIcs arxiv: 1 author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: 'Kolmogorov V. Testing the complexity of a valued CSP language. In: 46th International Colloquium on Automata, Languages and Programming. Vol 132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:77:1-77:12. doi:10.4230/LIPICS.ICALP.2019.77' apa: 'Kolmogorov, V. (2019). Testing the complexity of a valued CSP language. In 46th International Colloquium on Automata, Languages and Programming (Vol. 132, p. 77:1-77:12). Patras, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2019.77' chicago: Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” In 46th International Colloquium on Automata, Languages and Programming, 132:77:1-77:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ICALP.2019.77. ieee: V. Kolmogorov, “Testing the complexity of a valued CSP language,” in 46th International Colloquium on Automata, Languages and Programming, Patras, Greece, 2019, vol. 132, p. 77:1-77:12. ista: 'Kolmogorov V. 2019. Testing the complexity of a valued CSP language. 46th International Colloquium on Automata, Languages and Programming. ICALP 2019: International Colloquim on Automata, Languages and Programming, LIPIcs, vol. 132, 77:1-77:12.' mla: Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” 46th International Colloquium on Automata, Languages and Programming, vol. 132, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12, doi:10.4230/LIPICS.ICALP.2019.77. short: V. Kolmogorov, in:, 46th International Colloquium on Automata, Languages and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12. conference: end_date: 2019-07-12 location: Patras, Greece name: 'ICALP 2019: International Colloquim on Automata, Languages and Programming' start_date: 2019-07-08 date_created: 2019-07-29T12:23:29Z date_published: 2019-07-01T00:00:00Z date_updated: 2021-01-12T08:08:40Z day: '01' ddc: - '000' department: - _id: VlKo doi: 10.4230/LIPICS.ICALP.2019.77 ec_funded: 1 external_id: arxiv: - '1803.02289' file: - access_level: open_access checksum: f5ebee8eec6ae09e30365578ee63a492 content_type: application/pdf creator: dernst date_created: 2019-07-31T07:01:45Z date_updated: 2020-07-14T12:47:38Z file_id: '6738' file_name: 2019_LIPICS_Kolmogorov.pdf file_size: 575475 relation: main_file file_date_updated: 2020-07-14T12:47:38Z has_accepted_license: '1' intvolume: ' 132' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: 77:1-77:12 project: - _id: 25FBA906-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '616160' name: 'Discrete Optimization in Computer Vision: Theory and Practice' publication: 46th International Colloquium on Automata, Languages and Programming publication_identifier: isbn: - 978-3-95977-109-2 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: 1 status: public title: Testing the complexity of a valued CSP language 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: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 132 year: '2019' ...