--- _id: '8623' abstract: - lang: eng text: We introduce the monitoring of trace properties under assumptions. An assumption limits the space of possible traces that the monitor may encounter. An assumption may result from knowledge about the system that is being monitored, about the environment, or about another, connected monitor. We define monitorability under assumptions and study its theoretical properties. In particular, we show that for every assumption A, the boolean combinations of properties that are safe or co-safe relative to A are monitorable under A. We give several examples and constructions on how an assumption can make a non-monitorable property monitorable, and how an assumption can make a monitorable property monitorable with fewer resources, such as integer registers. acknowledgement: This research was supported in part by the Austrian Science Fund (FWF) under grant Z211-N23 (Wittgenstein Award). alternative_title: - LNCS article_processing_charge: No author: - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000-0002-2985-7724 - first_name: Naci E full_name: Sarac, Naci E id: 8C6B42F8-C8E6-11E9-A03A-F2DCE5697425 last_name: Sarac citation: ama: 'Henzinger TA, Sarac NE. Monitorability under assumptions. In: Runtime Verification. Vol 12399. Springer Nature; 2020:3-18. doi:10.1007/978-3-030-60508-7_1' apa: 'Henzinger, T. A., & Sarac, N. E. (2020). Monitorability under assumptions. In Runtime Verification (Vol. 12399, pp. 3–18). Los Angeles, CA, United States: Springer Nature. https://doi.org/10.1007/978-3-030-60508-7_1' chicago: Henzinger, Thomas A, and Naci E Sarac. “Monitorability under Assumptions.” In Runtime Verification, 12399:3–18. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-60508-7_1. ieee: T. A. Henzinger and N. E. Sarac, “Monitorability under assumptions,” in Runtime Verification, Los Angeles, CA, United States, 2020, vol. 12399, pp. 3–18. ista: 'Henzinger TA, Sarac NE. 2020. Monitorability under assumptions. Runtime Verification. RV: Runtime Verification, LNCS, vol. 12399, 3–18.' mla: Henzinger, Thomas A., and Naci E. Sarac. “Monitorability under Assumptions.” Runtime Verification, vol. 12399, Springer Nature, 2020, pp. 3–18, doi:10.1007/978-3-030-60508-7_1. short: T.A. Henzinger, N.E. Sarac, in:, Runtime Verification, Springer Nature, 2020, pp. 3–18. conference: end_date: 2020-10-09 location: Los Angeles, CA, United States name: 'RV: Runtime Verification' start_date: 2020-10-06 date_created: 2020-10-07T15:05:37Z date_published: 2020-10-02T00:00:00Z date_updated: 2023-09-05T15:08:26Z day: '02' ddc: - '000' department: - _id: ToHe doi: 10.1007/978-3-030-60508-7_1 external_id: isi: - '000728160600001' file: - access_level: open_access checksum: 00661f9b7034f52e18bf24fa552b8194 content_type: application/pdf creator: esarac date_created: 2020-10-15T14:28:06Z date_updated: 2020-10-15T14:28:06Z file_id: '8665' file_name: monitorability.pdf file_size: 478148 relation: main_file success: 1 file_date_updated: 2020-10-15T14:28:06Z has_accepted_license: '1' intvolume: ' 12399' isi: 1 language: - iso: eng month: '10' oa: 1 oa_version: Submitted Version page: 3-18 project: - _id: 25F42A32-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z211 name: The Wittgenstein Prize publication: Runtime Verification publication_identifier: eissn: - 1611-3349 isbn: - '9783030605070' - '9783030605087' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Monitorability under assumptions type: conference user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 12399 year: '2020' ... --- _id: '8732' abstract: - lang: eng text: 'A simple drawing D(G) of a graph G is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge e in the complement of G can be inserted into D(G) if there exists a simple drawing of G+e extending D(G). As a result of Levi’s Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of G can be inserted. In contrast, we show that it is NP -complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles A and a pseudosegment σ , it can be decided in polynomial time whether there exists a pseudocircle Φσ extending σ for which A∪{Φσ} is again an arrangement of pseudocircles.' alternative_title: - LNCS article_processing_charge: No author: - first_name: Alan M full_name: Arroyo Guevara, Alan M id: 3207FDC6-F248-11E8-B48F-1D18A9856A87 last_name: Arroyo Guevara orcid: 0000-0003-2401-8670 - first_name: Fabian full_name: Klute, Fabian last_name: Klute - first_name: Irene full_name: Parada, Irene last_name: Parada - first_name: Raimund full_name: Seidel, Raimund last_name: Seidel - first_name: Birgit full_name: Vogtenhuber, Birgit last_name: Vogtenhuber - first_name: Tilo full_name: Wiedera, Tilo last_name: Wiedera citation: ama: 'Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T. Inserting one edge into a simple drawing is hard. In: Graph-Theoretic Concepts in Computer Science. Vol 12301. Springer Nature; 2020:325-338. doi:10.1007/978-3-030-60440-0_26' apa: 'Arroyo Guevara, A. M., Klute, F., Parada, I., Seidel, R., Vogtenhuber, B., & Wiedera, T. (2020). Inserting one edge into a simple drawing is hard. In Graph-Theoretic Concepts in Computer Science (Vol. 12301, pp. 325–338). Leeds, United Kingdom: Springer Nature. https://doi.org/10.1007/978-3-030-60440-0_26' chicago: Arroyo Guevara, Alan M, Fabian Klute, Irene Parada, Raimund Seidel, Birgit Vogtenhuber, and Tilo Wiedera. “Inserting One Edge into a Simple Drawing Is Hard.” In Graph-Theoretic Concepts in Computer Science, 12301:325–38. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-60440-0_26. ieee: A. M. Arroyo Guevara, F. Klute, I. Parada, R. Seidel, B. Vogtenhuber, and T. Wiedera, “Inserting one edge into a simple drawing is hard,” in Graph-Theoretic Concepts in Computer Science, Leeds, United Kingdom, 2020, vol. 12301, pp. 325–338. ista: 'Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T. 2020. Inserting one edge into a simple drawing is hard. Graph-Theoretic Concepts in Computer Science. WG: Workshop on Graph-Theoretic Concepts in Computer Science, LNCS, vol. 12301, 325–338.' mla: Arroyo Guevara, Alan M., et al. “Inserting One Edge into a Simple Drawing Is Hard.” Graph-Theoretic Concepts in Computer Science, vol. 12301, Springer Nature, 2020, pp. 325–38, doi:10.1007/978-3-030-60440-0_26. short: A.M. Arroyo Guevara, F. Klute, I. Parada, R. Seidel, B. Vogtenhuber, T. Wiedera, in:, Graph-Theoretic Concepts in Computer Science, Springer Nature, 2020, pp. 325–338. conference: end_date: 2020-06-26 location: Leeds, United Kingdom name: 'WG: Workshop on Graph-Theoretic Concepts in Computer Science' start_date: 2020-06-24 date_created: 2020-11-06T08:45:03Z date_published: 2020-10-09T00:00:00Z date_updated: 2023-09-05T15:09:16Z day: '09' department: - _id: UlWa doi: 10.1007/978-3-030-60440-0_26 ec_funded: 1 intvolume: ' 12301' language: - iso: eng month: '10' oa_version: None page: 325-338 project: - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships publication: Graph-Theoretic Concepts in Computer Science publication_identifier: eissn: - 1611-3349 isbn: - '9783030604394' - '9783030604400' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Inserting one edge into a simple drawing is hard type: conference user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 12301 year: '2020' ... --- _id: '10865' abstract: - lang: eng text: "We introduce the notion of Witness Maps as a cryptographic notion of a proof system. A Unique Witness Map (UWM) deterministically maps all witnesses for an \ NP statement to a single representative witness, resulting in a computationally sound, deterministic-prover, non-interactive witness independent proof system. A relaxation of UWM, called Compact Witness Map (CWM), maps all the witnesses to a small number of witnesses, resulting in a “lossy” deterministic-prover, non-interactive proof-system. We also define a Dual Mode Witness Map (DMWM) which adds an “extractable” mode to a CWM.\r\nOur main construction is a DMWM for all NP relations, assuming sub-exponentially secure indistinguishability obfuscation ( iO ), along with standard cryptographic assumptions. The DMWM construction relies on a CWM and a new primitive called Cumulative All-Lossy-But-One Trapdoor Functions (C-ALBO-TDF), both of which are in turn instantiated based on iO and other primitives. Our instantiation of a CWM is in fact a UWM; in turn, we show that a UWM implies Witness Encryption. Along the way to constructing UWM and C-ALBO-TDF, we also construct, from standard assumptions, Puncturable Digital Signatures and a new primitive called Cumulative Lossy Trapdoor Functions (C-LTDF). The former improves up on a construction of Bellare et al. (Eurocrypt 2016), who relied on sub-exponentially secure iO and sub-exponentially secure OWF.\r\nAs an application of our constructions, we show how to use a DMWM to construct the first leakage and tamper-resilient signatures with a deterministic signer, thereby solving a decade old open problem posed by Katz and Vaikunthanathan (Asiacrypt 2009), by Boyle, Segev and Wichs (Eurocrypt 2011), as well as by Faonio and Venturi (Asiacrypt 2016). Our construction achieves the optimal leakage rate of 1−o(1) ." acknowledgement: We would like to thank the anonymous reviewers of PKC 2019 for their useful comments and suggestions. We thank Omer Paneth for pointing out to us the connection between Unique Witness Maps (UWM) and Witness encryption (WE). The first author would like to acknowledge Pandu Rangan for his involvement during the initial discussion phase of the project. article_processing_charge: No author: - first_name: Suvradip full_name: Chakraborty, Suvradip id: B9CD0494-D033-11E9-B219-A439E6697425 last_name: Chakraborty - first_name: Manoj full_name: Prabhakaran, Manoj last_name: Prabhakaran - first_name: Daniel full_name: Wichs, Daniel last_name: Wichs citation: ama: 'Chakraborty S, Prabhakaran M, Wichs D. Witness maps and applications. In: Kiayias A, ed. Public-Key Cryptography. Vol 12110. LNCS. Cham: Springer Nature; 2020:220-246. doi:10.1007/978-3-030-45374-9_8' apa: 'Chakraborty, S., Prabhakaran, M., & Wichs, D. (2020). Witness maps and applications. In A. Kiayias (Ed.), Public-Key Cryptography (Vol. 12110, pp. 220–246). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-45374-9_8' chicago: 'Chakraborty, Suvradip, Manoj Prabhakaran, and Daniel Wichs. “Witness Maps and Applications.” In Public-Key Cryptography, edited by A Kiayias, 12110:220–46. LNCS. Cham: Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45374-9_8.' ieee: 'S. Chakraborty, M. Prabhakaran, and D. Wichs, “Witness maps and applications,” in Public-Key Cryptography, vol. 12110, A. Kiayias, Ed. Cham: Springer Nature, 2020, pp. 220–246.' ista: 'Chakraborty S, Prabhakaran M, Wichs D. 2020.Witness maps and applications. In: Public-Key Cryptography. vol. 12110, 220–246.' mla: Chakraborty, Suvradip, et al. “Witness Maps and Applications.” Public-Key Cryptography, edited by A Kiayias, vol. 12110, Springer Nature, 2020, pp. 220–46, doi:10.1007/978-3-030-45374-9_8. short: S. Chakraborty, M. Prabhakaran, D. Wichs, in:, A. Kiayias (Ed.), Public-Key Cryptography, Springer Nature, Cham, 2020, pp. 220–246. date_created: 2022-03-18T11:35:51Z date_published: 2020-04-29T00:00:00Z date_updated: 2023-09-05T15:10:02Z day: '29' doi: 10.1007/978-3-030-45374-9_8 editor: - first_name: A full_name: Kiayias, A last_name: Kiayias intvolume: ' 12110' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2020/090 month: '04' oa: 1 oa_version: Preprint page: 220-246 place: Cham publication: Public-Key Cryptography publication_identifier: eissn: - 1611-3349 isbn: - '9783030453732' - '9783030453749' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' series_title: LNCS status: public title: Witness maps and applications type: book_chapter user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 12110 year: '2020' ... --- _id: '7611' abstract: - lang: eng text: We consider a system of N bosons in the limit N→∞, interacting through singular potentials. For initial data exhibiting Bose–Einstein condensation, the many-body time evolution is well approximated through a quadratic fluctuation dynamics around a cubic nonlinear Schrödinger equation of the condensate wave function. We show that these fluctuations satisfy a (multi-variate) central limit theorem. acknowledgement: "Simone Rademacher acknowledges partial support from the NCCR SwissMAP. This project has received\r\nfunding from the European Union’s Horizon 2020 research and innovation program under the Marie\r\nSkłodowska-Curie Grant Agreement No. 754411.\r\nOpen access funding provided by Institute of Science and Technology (IST Austria).\r\nS.R. would like to thank Benjamin Schlein for many fruitful discussions." article_processing_charge: Yes (via OA deal) article_type: original author: - first_name: Simone Anna Elvira full_name: Rademacher, Simone Anna Elvira id: 856966FE-A408-11E9-977E-802DE6697425 last_name: Rademacher orcid: 0000-0001-5059-4466 citation: ama: Rademacher SAE. Central limit theorem for Bose gases interacting through singular potentials. Letters in Mathematical Physics. 2020;110:2143-2174. doi:10.1007/s11005-020-01286-w apa: Rademacher, S. A. E. (2020). Central limit theorem for Bose gases interacting through singular potentials. Letters in Mathematical Physics. Springer Nature. https://doi.org/10.1007/s11005-020-01286-w chicago: Rademacher, Simone Anna Elvira. “Central Limit Theorem for Bose Gases Interacting through Singular Potentials.” Letters in Mathematical Physics. Springer Nature, 2020. https://doi.org/10.1007/s11005-020-01286-w. ieee: S. A. E. Rademacher, “Central limit theorem for Bose gases interacting through singular potentials,” Letters in Mathematical Physics, vol. 110. Springer Nature, pp. 2143–2174, 2020. ista: Rademacher SAE. 2020. Central limit theorem for Bose gases interacting through singular potentials. Letters in Mathematical Physics. 110, 2143–2174. mla: Rademacher, Simone Anna Elvira. “Central Limit Theorem for Bose Gases Interacting through Singular Potentials.” Letters in Mathematical Physics, vol. 110, Springer Nature, 2020, pp. 2143–74, doi:10.1007/s11005-020-01286-w. short: S.A.E. Rademacher, Letters in Mathematical Physics 110 (2020) 2143–2174. date_created: 2020-03-23T11:11:47Z date_published: 2020-03-12T00:00:00Z date_updated: 2023-09-05T15:14:50Z day: '12' ddc: - '510' department: - _id: RoSe doi: 10.1007/s11005-020-01286-w ec_funded: 1 external_id: isi: - '000551556000006' file: - access_level: open_access checksum: 3bdd41f10ad947b67a45b98f507a7d4a content_type: application/pdf creator: dernst date_created: 2020-11-20T12:04:26Z date_updated: 2020-11-20T12:04:26Z file_id: '8784' file_name: 2020_LettersMathPhysics_Rademacher.pdf file_size: 478683 relation: main_file success: 1 file_date_updated: 2020-11-20T12:04:26Z has_accepted_license: '1' intvolume: ' 110' isi: 1 language: - iso: eng month: '03' oa: 1 oa_version: Published Version page: 2143-2174 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: Letters in Mathematical Physics publication_identifier: eissn: - 1573-0530 issn: - 0377-9017 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Central limit theorem for Bose gases interacting through singular potentials 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: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 110 year: '2020' ... --- _id: '7236' abstract: - lang: eng text: The biotic interactions hypothesis posits that biotic interactions are more important drivers of adaptation closer to the equator, evidenced by “stronger” contemporary interactions (e.g. greater interaction rates) and/or patterns of trait evolution consistent with a history of stronger interactions. Support for the hypothesis is mixed, but few studies span tropical and temperate regions while experimentally controlling for evolutionary history. Here, we integrate field observations and common garden experiments to quantify the relative importance of pollination and herbivory in a pair of tropical‐temperate congeneric perennial herbs. Phytolacca rivinoides and P. americana are pioneer species native to the Neotropics and the eastern USA, respectively. We compared plant‐pollinator and plant‐herbivore interactions between three tropical populations of P. rivinoides from Costa Rica and three temperate populations of P. americana from its northern range edge in Michigan and Ohio. For some metrics of interaction importance, we also included three subtropical populations of P. americana from its southern range edge in Florida. This approach confounds species and region but allows us, uniquely, to measure complementary proxies of interaction importance across a tropical‐temperate range in one system. To test the prediction that lower‐latitude plants are more reliant on insect pollinators, we quantified floral display and reward, insect visitation rates, and self‐pollination ability (autogamy). To test the prediction that lower‐latitude plants experience more herbivore pressure, we quantified herbivory rates, herbivore abundance, and leaf palatability. We found evidence supporting the biotic interactions hypothesis for most comparisons between P. rivinoides and north‐temperate P. americana (floral display, insect visitation, autogamy, herbivory, herbivore abundance, and young‐leaf palatability). Results for subtropical P. americana populations, however, were typically not intermediate between P. rivinoides and north‐temperate P. americana, as would be predicted by a linear latitudinal gradient in interaction importance. Subtropical young‐leaf palatability was intermediate, but subtropical mature leaves were the least palatable, and pollination‐related traits did not differ between temperate and subtropical regions. These nonlinear patterns of interaction importance suggest future work to relate interaction importance to climatic or biotic thresholds. In sum, we found that the biotic interactions hypothesis was more consistently supported at the larger spatial scale of our study. article_number: e01397 article_processing_charge: Yes (via OA deal) article_type: original author: - first_name: Carina full_name: Baskett, Carina id: 3B4A7CE2-F248-11E8-B48F-1D18A9856A87 last_name: Baskett orcid: 0000-0002-7354-8574 - first_name: Lucy full_name: Schroeder, Lucy last_name: Schroeder - first_name: Marjorie G. full_name: Weber, Marjorie G. last_name: Weber - first_name: Douglas W. full_name: Schemske, Douglas W. last_name: Schemske citation: ama: Baskett C, Schroeder L, Weber MG, Schemske DW. Multiple metrics of latitudinal patterns in insect pollination and herbivory for a tropical‐temperate congener pair. Ecological Monographs. 2020;90(1). doi:10.1002/ecm.1397 apa: Baskett, C., Schroeder, L., Weber, M. G., & Schemske, D. W. (2020). Multiple metrics of latitudinal patterns in insect pollination and herbivory for a tropical‐temperate congener pair. Ecological Monographs. Wiley. https://doi.org/10.1002/ecm.1397 chicago: Baskett, Carina, Lucy Schroeder, Marjorie G. Weber, and Douglas W. Schemske. “Multiple Metrics of Latitudinal Patterns in Insect Pollination and Herbivory for a Tropical‐temperate Congener Pair.” Ecological Monographs. Wiley, 2020. https://doi.org/10.1002/ecm.1397. ieee: C. Baskett, L. Schroeder, M. G. Weber, and D. W. Schemske, “Multiple metrics of latitudinal patterns in insect pollination and herbivory for a tropical‐temperate congener pair,” Ecological Monographs, vol. 90, no. 1. Wiley, 2020. ista: Baskett C, Schroeder L, Weber MG, Schemske DW. 2020. Multiple metrics of latitudinal patterns in insect pollination and herbivory for a tropical‐temperate congener pair. Ecological Monographs. 90(1), e01397. mla: Baskett, Carina, et al. “Multiple Metrics of Latitudinal Patterns in Insect Pollination and Herbivory for a Tropical‐temperate Congener Pair.” Ecological Monographs, vol. 90, no. 1, e01397, Wiley, 2020, doi:10.1002/ecm.1397. short: C. Baskett, L. Schroeder, M.G. Weber, D.W. Schemske, Ecological Monographs 90 (2020). date_created: 2020-01-07T12:47:07Z date_published: 2020-02-01T00:00:00Z date_updated: 2023-09-05T15:43:19Z day: '01' ddc: - '570' department: - _id: NiBa doi: 10.1002/ecm.1397 ec_funded: 1 external_id: isi: - '000508511600001' file: - access_level: open_access checksum: ab8130c6e68101f5a091d05324c36f08 content_type: application/pdf creator: dernst date_created: 2020-02-10T08:18:14Z date_updated: 2020-07-14T12:47:54Z file_id: '7469' file_name: 2020_EcologMono_Baskett.pdf file_size: 537941 relation: main_file file_date_updated: 2020-07-14T12:47:54Z has_accepted_license: '1' intvolume: ' 90' isi: 1 issue: '1' language: - iso: eng month: '02' oa: 1 oa_version: Published Version project: - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships publication: Ecological Monographs publication_identifier: eissn: - 1557-7015 issn: - 0012-9615 publication_status: published publisher: Wiley quality_controlled: '1' scopus_import: '1' status: public title: Multiple metrics of latitudinal patterns in insect pollination and herbivory for a tropical‐temperate congener pair 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: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 90 year: '2020' ...