TY - CONF AB - 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. AU - Henzinger, Thomas A AU - Sarac, Naci E ID - 8623 SN - 0302-9743 T2 - Runtime Verification TI - Monitorability under assumptions VL - 12399 ER - TY - CONF AB - 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. AU - Arroyo Guevara, Alan M AU - Klute, Fabian AU - Parada, Irene AU - Seidel, Raimund AU - Vogtenhuber, Birgit AU - Wiedera, Tilo ID - 8732 SN - 0302-9743 T2 - Graph-Theoretic Concepts in Computer Science TI - Inserting one edge into a simple drawing is hard VL - 12301 ER - TY - CHAP AB - 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. Our 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. As 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) . AU - Chakraborty, Suvradip AU - Prabhakaran, Manoj AU - Wichs, Daniel ED - Kiayias, A ID - 10865 SN - 0302-9743 T2 - Public-Key Cryptography TI - Witness maps and applications VL - 12110 ER - TY - JOUR AB - 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. AU - Rademacher, Simone Anna Elvira ID - 7611 JF - Letters in Mathematical Physics SN - 0377-9017 TI - Central limit theorem for Bose gases interacting through singular potentials VL - 110 ER - TY - JOUR AB - 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. AU - Baskett, Carina AU - Schroeder, Lucy AU - Weber, Marjorie G. AU - Schemske, Douglas W. ID - 7236 IS - 1 JF - Ecological Monographs SN - 0012-9615 TI - Multiple metrics of latitudinal patterns in insect pollination and herbivory for a tropical‐temperate congener pair VL - 90 ER -