TY - JOUR AB - Cryptographic security is usually defined as a guarantee that holds except when a bad event with negligible probability occurs, and nothing is guaranteed in that bad case. However, in settings where such failure can happen with substantial probability, one needs to provide guarantees even for the bad case. A typical example is where a (possibly weak) password is used instead of a secure cryptographic key to protect a session, the bad event being that the adversary correctly guesses the password. In a situation with multiple such sessions, a per-session guarantee is desired: any session for which the password has not been guessed remains secure, independently of whether other sessions have been compromised. A new formalism for stating such gracefully degrading security guarantees is introduced and applied to analyze the examples of password-based message authentication and password-based encryption. While a natural per-message guarantee is achieved for authentication, the situation of password-based encryption is more delicate: a per-session confidentiality guarantee only holds against attackers for which the distribution of password-guessing effort over the sessions is known in advance. In contrast, for more general attackers without such a restriction, a strong, composable notion of security cannot be achieved. AU - Demay, Gregory AU - Gazi, Peter AU - Maurer, Ueli AU - Tackmann, Bjorn ID - 5887 IS - 1 JF - Journal of Computer Security SN - 0926227X TI - Per-session security: Password-based cryptography revisited VL - 27 ER - TY - JOUR AB - We give non-degeneracy criteria for Riemannian simplices based on simplices in spaces of constant sectional curvature. It extends previous work on Riemannian simplices, where we developed Riemannian simplices with respect to Euclidean reference simplices. The criteria we give in this article are in terms of quality measures for spaces of constant curvature that we develop here. We see that simplices in spaces that have nearly constant curvature, are already non-degenerate under very weak quality demands. This is of importance because it allows for sampling of Riemannian manifolds based on anisotropy of the manifold and not (absolute) curvature. AU - Dyer, Ramsay AU - Vegter, Gert AU - Wintraecken, Mathijs ID - 6515 IS - 1 JF - Journal of Computational Geometry SN - 1920-180X TI - Simplices modelled on spaces of constant curvature VL - 10 ER - TY - CONF AB - We construct a verifiable delay function (VDF) by showing how the Rivest-Shamir-Wagner time-lock puzzle can be made publicly verifiable. Concretely, we give a statistically sound public-coin protocol to prove that a tuple (N,x,T,y) satisfies y=x2T (mod N) where the prover doesn’t know the factorization of N and its running time is dominated by solving the puzzle, that is, compute x2T, which is conjectured to require T sequential squarings. To get a VDF we make this protocol non-interactive using the Fiat-Shamir heuristic.The motivation for this work comes from the Chia blockchain design, which uses a VDF as akey ingredient. For typical parameters (T≤2 40, N= 2048), our proofs are of size around 10K B, verification cost around three RSA exponentiations and computing the proof is 8000 times faster than solving the puzzle even without any parallelism. AU - Pietrzak, Krzysztof Z ID - 6528 SN - 1868-8969 T2 - 10th Innovations in Theoretical Computer Science Conference TI - Simple verifiable delay functions VL - 124 ER - TY - CONF AB - In this paper, we address the problem of synthesizing periodic switching controllers for stabilizing a family of linear systems. Our broad approach consists of constructing a finite game graph based on the family of linear systems such that every winning strategy on the game graph corresponds to a stabilizing switching controller for the family of linear systems. The construction of a (finite) game graph, the synthesis of a winning strategy and the extraction of a stabilizing controller are all computationally feasible. We illustrate our method on an example. AU - Kundu, Atreyee AU - Garcia Soto, Miriam AU - Prabhakar, Pavithra ID - 6565 SN - 978-153866246-5 T2 - 5th Indian Control Conference Proceedings TI - Formal synthesis of stabilizing controllers for periodically controlled linear switched systems ER - TY - CONF AB - Fejes Tóth [5] and Schneider [9] studied approximations of smooth convex hypersurfaces in Euclidean space by piecewise flat triangular meshes with a given number of vertices on the hypersurface that are optimal with respect to Hausdorff distance. They proved that this Hausdorff distance decreases inversely proportional with m 2/(d−1), where m is the number of vertices and d is the dimension of Euclidean space. Moreover the pro-portionality constant can be expressed in terms of the Gaussian curvature, an intrinsic quantity. In this short note, we prove the extrinsic nature of this constant for manifolds of sufficiently high codimension. We do so by constructing an family of isometric embeddings of the flat torus in Euclidean space. AU - Vegter, Gert AU - Wintraecken, Mathijs ID - 6628 T2 - The 31st Canadian Conference in Computational Geometry TI - The extrinsic nature of the Hausdorff distance of optimal triangulations of manifolds ER - TY - CONF AB - 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 needed 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. AU - Edelsbrunner, Herbert AU - Virk, Ziga AU - Wagner, Hubert ID - 6648 SN - 9783959771047 T2 - 35th International Symposium on Computational Geometry TI - Topological data analysis in information space VL - 129 ER - TY - JOUR AB - 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. AU - Zenmyo, Naoki AU - Tokumaru, Hiroki AU - Uchinomiya, Shohei AU - Fuchida, Hirokazu AU - Tabata, Shigekazu AU - Hamachi, Itaru AU - Shigemoto, Ryuichi AU - Ojida, Akio ID - 6659 IS - 5 JF - Bulletin of the Chemical Society of Japan SN - 00092673 TI - Optimized reaction pair of the CysHis tag and Ni(II)-NTA probe for highly selective chemical labeling of membrane proteins VL - 92 ER - TY - CONF AB - 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. Recent 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. AU - Kolmogorov, Vladimir ID - 6725 SN - 1868-8969 T2 - 46th International Colloquium on Automata, Languages and Programming TI - Testing the complexity of a valued CSP language VL - 132 ER - TY - CHAP AB - Randomness is an essential part of any secure cryptosystem, but many constructions rely on distributions that are not uniform. This is particularly true for lattice based cryptosystems, which more often than not make use of discrete Gaussian distributions over the integers. For practical purposes it is crucial to evaluate the impact that approximation errors have on the security of a scheme to provide the best possible trade-off between security and performance. Recent years have seen surprising results allowing to use relatively low precision while maintaining high levels of security. A key insight in these results is that sampling a distribution with low relative error can provide very strong security guarantees. Since floating point numbers provide guarantees on the relative approximation error, they seem a suitable tool in this setting, but it is not obvious which sampling algorithms can actually profit from them. While previous works have shown that inversion sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES 2014; Prest, ASIACRYPT 2017), other works have called into question if this is possible for other sampling techniques (Zheng et al., Eprint report 2018/309). In this work, we consider all sampling algorithms that are popular in the cryptographic setting and analyze the relationship of floating point precision and the resulting relative error. We show that all of the algorithms either natively achieve a low relative error or can be adapted to do so. AU - Walter, Michael ED - Buchmann, J ED - Nitaj, A ED - Rachidi, T ID - 6726 SN - 0302-9743 T2 - Progress in Cryptology – AFRICACRYPT 2019 TI - Sampling the integers with low relative error VL - 11627 ER - TY - JOUR AB - Polar codes have gained extensive attention during the past few years and recently they have been selected for the next generation of wireless communications standards (5G). Successive-cancellation-based (SC-based) decoders, such as SC list (SCL) and SC flip (SCF), provide a reasonable error performance for polar codes at the cost of low decoding speed. Fast SC-based decoders, such as Fast-SSC, Fast-SSCL, and Fast-SSCF, identify the special constituent codes in a polar code graph off-line, produce a list of operations, store the list in memory, and feed the list to the decoder to decode the constituent codes in order efficiently, thus increasing the decoding speed. However, the list of operations is dependent on the code rate and as the rate changes, a new list is produced, making fast SC-based decoders not rate-flexible. In this paper, we propose a completely rate-flexible fast SC-based decoder by creating the list of operations directly in hardware, with low implementation complexity. We further propose a hardware architecture implementing the proposed method and show that the area occupation of the rate-flexible fast SC-based decoder in this paper is only 38% of the total area of the memory-based base-line decoder when 5G code rates are supported. AU - Hashemi, Seyyed Ali AU - Condo, Carlo AU - Mondelli, Marco AU - Gross, Warren J ID - 6750 IS - 22 JF - IEEE Transactions on Signal Processing SN - 1053587X TI - Rate-flexible fast polar decoders VL - 67 ER - TY - JOUR AB - We consider the graph class Grounded-L corresponding to graphs that admit an intersection representation by L-shaped curves, where additionally the topmost points of each curve are assumed to belong to a common horizontal line. We prove that Grounded-L graphs admit an equivalent characterisation in terms of vertex ordering with forbidden patterns. We also compare this class to related intersection classes, such as the grounded segment graphs, the monotone L-graphs (a.k.a. max point-tolerance graphs), or the outer-1-string graphs. We give constructions showing that these classes are all distinct and satisfy only trivial or previously known inclusions. AU - Jelínek, Vít AU - Töpfer, Martin ID - 6759 IS - 3 JF - Electronic Journal of Combinatorics TI - On grounded L-graphs and their relatives VL - 26 ER - TY - CONF AB - In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the qualitative winner or quantitative payoff of the game. In bidding games, in each turn, we hold an auction between the two players to determine which player moves the token. Bidding games have largely been studied with concrete bidding mechanisms that are variants of a first-price auction: in each turn both players simultaneously submit bids, the higher bidder moves the token, and pays his bid to the lower bidder in Richman bidding, to the bank in poorman bidding, and in taxman bidding, the bid is split between the other player and the bank according to a predefined constant factor. Bidding games are deterministic games. They have an intriguing connection with a fragment of stochastic games called randomturn games. We study, for the first time, a combination of bidding games with probabilistic behavior; namely, we study bidding games that are played on Markov decision processes, where the players bid for the right to choose the next action, which determines the probability distribution according to which the next vertex is chosen. We study parity and meanpayoff bidding games on MDPs and extend results from the deterministic bidding setting to the probabilistic one. AU - Avni, Guy AU - Henzinger, Thomas A AU - Ibsen-Jensen, Rasmus AU - Novotny, Petr ID - 6822 SN - 0302-9743 T2 - Proceedings of the 13th International Conference of Reachability Problems TI - Bidding games on Markov decision processes VL - 11674 ER - TY - CONF AB - The fundamental model-checking problem, given as input a model and a specification, asks for the algorithmic verification of whether the model satisfies the specification. Two classical models for reactive systems are graphs and Markov decision processes (MDPs). A basic specification formalism in the verification of reactive systems is the strong fairness (aka Streett) objective, where given different types of requests and corresponding grants, the requirement is that for each type, if the request event happens infinitely often, then the corresponding grant event must also happen infinitely often. All omega-regular objectives can be expressed as Streett objectives and hence they are canonical in verification. Consider graphs/MDPs with n vertices, m edges, and a Streett objectives with k pairs, and let b denote the size of the description of the Streett objective for the sets of requests and grants. The current best-known algorithm for the problem requires time O(min(n^2, m sqrt{m log n}) + b log n). In this work we present randomized near-linear time algorithms, with expected running time O~(m + b), where the O~ notation hides poly-log factors. Our randomized algorithms are near-linear in the size of the input, and hence optimal up to poly-log factors. AU - Chatterjee, Krishnendu AU - Dvorák, Wolfgang AU - Henzinger, Monika H AU - Svozil, Alexander ID - 6887 T2 - Leibniz International Proceedings in Informatics TI - Near-linear time algorithms for Streett objectives in graphs and MDPs VL - 140 ER - TY - CONF AB - In this paper, we design novel liquid time-constant recurrent neural networks for robotic control, inspired by the brain of the nematode, C. elegans. In the worm's nervous system, neurons communicate through nonlinear time-varying synaptic links established amongst them by their particular wiring structure. This property enables neurons to express liquid time-constants dynamics and therefore allows the network to originate complex behaviors with a small number of neurons. We identify neuron-pair communication motifs as design operators and use them to configure compact neuronal network structures to govern sequential robotic tasks. The networks are systematically designed to map the environmental observations to motor actions, by their hierarchical topology from sensory neurons, through recurrently-wired interneurons, to motor neurons. The networks are then parametrized in a supervised-learning scheme by a search-based algorithm. We demonstrate that obtained networks realize interpretable dynamics. We evaluate their performance in controlling mobile and arm robots, and compare their attributes to other artificial neural network-based control agents. Finally, we experimentally show their superior resilience to environmental noise, compared to the existing machine learning-based methods. AU - Lechner, Mathias AU - Hasani, Ramin AU - Zimmer, Manuel AU - Henzinger, Thomas A AU - Grosu, Radu ID - 6888 SN - 9781538660270 T2 - Proceedings - IEEE International Conference on Robotics and Automation TI - Designing worm-inspired neural networks for interpretable robotic control VL - 2019-May ER - TY - CONF AB - In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the winner of the game. Such games are central in formal methods since they model the interaction between a non-terminating system and its environment. In bidding games the players bid for the right to move the token: in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. Bidding games are known to have a clean and elegant mathematical structure that relies on the ability of the players to submit arbitrarily small bids. Many applications, however, require a fixed granularity for the bids, which can represent, for example, the monetary value expressed in cents. We study, for the first time, the combination of discrete-bidding and infinite-duration games. Our most important result proves that these games form a large determined subclass of concurrent games, where determinacy is the strong property that there always exists exactly one player who can guarantee winning the game. In particular, we show that, in contrast to non-discrete bidding games, the mechanism with which tied bids are resolved plays an important role in discrete-bidding games. We study several natural tie-breaking mechanisms and show that, while some do not admit determinacy, most natural mechanisms imply determinacy for every pair of initial budgets. AU - Aghajohari, Milad AU - Avni, Guy AU - Henzinger, Thomas A ID - 6886 TI - Determinacy in discrete-bidding infinite-duration games VL - 140 ER - TY - CONF AB - A vector addition system with states (VASS) consists of a finite set of states and counters. A configuration is a state and a value for each counter; a transition changes the state and each counter is incremented, decremented, or left unchanged. While qualitative properties such as state and configuration reachability have been studied for VASS, we consider the long-run average cost of infinite computations of VASS. The cost of a configuration is for each state, a linear combination of the counter values. In the special case of uniform cost functions, the linear combination is the same for all states. The (regular) long-run emptiness problem is, given a VASS, a cost function, and a threshold value, if there is a (lasso-shaped) computation such that the long-run average value of the cost function does not exceed the threshold. For uniform cost functions, we show that the regular long-run emptiness problem is (a) decidable in polynomial time for integer-valued VASS, and (b) decidable but nonelementarily hard for natural-valued VASS (i.e., nonnegative counters). For general cost functions, we show that the problem is (c) NP-complete for integer-valued VASS, and (d) undecidable for natural-valued VASS. Our most interesting result is for (c) integer-valued VASS with general cost functions, where we establish a connection between the regular long-run emptiness problem and quadratic Diophantine inequalities. The general (nonregular) long-run emptiness problem is equally hard as the regular problem in all cases except (c), where it remains open. AU - Chatterjee, Krishnendu AU - Henzinger, Thomas A AU - Otop, Jan ID - 6885 TI - Long-run average behavior of vector addition systems with states VL - 140 ER - TY - CONF AB - We study Markov decision processes and turn-based stochastic games with parity conditions. There are three qualitative winning criteria, namely, sure winning, which requires all paths to satisfy the condition, almost-sure winning, which requires the condition to be satisfied with probability 1, and limit-sure winning, which requires the condition to be satisfied with probability arbitrarily close to 1. We study the combination of two of these criteria for parity conditions, e.g., there are two parity conditions one of which must be won surely, and the other almost-surely. The problem has been studied recently by Berthon et al. for MDPs with combination of sure and almost-sure winning, under infinite-memory strategies, and the problem has been established to be in NP cap co-NP. Even in MDPs there is a difference between finite-memory and infinite-memory strategies. Our main results for combination of sure and almost-sure winning are as follows: (a) we show that for MDPs with finite-memory strategies the problem is in NP cap co-NP; (b) we show that for turn-based stochastic games the problem is co-NP-complete, both for finite-memory and infinite-memory strategies; and (c) we present algorithmic results for the finite-memory case, both for MDPs and turn-based stochastic games, by reduction to non-stochastic parity games. In addition we show that all the above complexity results also carry over to combination of sure and limit-sure winning, and results for all other combinations can be derived from existing results in the literature. Thus we present a complete picture for the study of combinations of two qualitative winning criteria for parity conditions in MDPs and turn-based stochastic games. AU - Chatterjee, Krishnendu AU - Piterman, Nir ID - 6889 TI - Combinations of Qualitative Winning for Stochastic Parity Games VL - 140 ER - TY - CONF AB - Consider a distributed system with n processors out of which f can be Byzantine faulty. In the approximate agreement task, each processor i receives an input value xi and has to decide on an output value yi such that 1. the output values are in the convex hull of the non-faulty processors’ input values, 2. the output values are within distance d of each other. Classically, the values are assumed to be from an m-dimensional Euclidean space, where m ≥ 1. In this work, we study the task in a discrete setting, where input values with some structure expressible as a graph. Namely, the input values are vertices of a finite graph G and the goal is to output vertices that are within distance d of each other in G, but still remain in the graph-induced convex hull of the input values. For d = 0, the task reduces to consensus and cannot be solved with a deterministic algorithm in an asynchronous system even with a single crash fault. For any d ≥ 1, we show that the task is solvable in asynchronous systems when G is chordal and n > (ω + 1)f, where ω is the clique number of G. In addition, we give the first Byzantine-tolerant algorithm for a variant of lattice agreement. For synchronous systems, we show tight resilience bounds for the exact variants of these and related tasks over a large class of combinatorial structures. AU - Nowak, Thomas AU - Rybicki, Joel ID - 6931 KW - consensus KW - approximate agreement KW - Byzantine faults KW - chordal graphs KW - lattice agreement T2 - 33rd International Symposium on Distributed Computing TI - Byzantine approximate agreement on graphs VL - 146 ER - TY - CONF AB - In this paper, we introduce a novel method to interpret recurrent neural networks (RNNs), particularly long short-term memory networks (LSTMs) at the cellular level. We propose a systematic pipeline for interpreting individual hidden state dynamics within the network using response characterization methods. The ranked contribution of individual cells to the network's output is computed by analyzing a set of interpretable metrics of their decoupled step and sinusoidal responses. As a result, our method is able to uniquely identify neurons with insightful dynamics, quantify relationships between dynamical properties and test accuracy through ablation analysis, and interpret the impact of network capacity on a network's dynamical distribution. Finally, we demonstrate the generalizability and scalability of our method by evaluating a series of different benchmark sequential datasets. AU - Hasani, Ramin AU - Amini, Alexander AU - Lechner, Mathias AU - Naser, Felix AU - Grosu, Radu AU - Rus, Daniela ID - 6985 SN - 9781728119854 T2 - Proceedings of the International Joint Conference on Neural Networks TI - Response characterization for auditing cell dynamics in long short-term memory networks ER - TY - JOUR AB - We consider the primitive relay channel, where the source sends a message to the relay and to the destination, and the relay helps the communication by transmitting an additional message to the destination via a separate channel. Two well-known coding techniques have been introduced for this setting: decode-and-forward and compress-and-forward. In decode-and-forward, the relay completely decodes the message and sends some information to the destination; in compress-and-forward, the relay does not decode, and it sends a compressed version of the received signal to the destination using Wyner–Ziv coding. In this paper, we present a novel coding paradigm that provides an improved achievable rate for the primitive relay channel. The idea is to combine compress-and-forward and decode-and-forward via a chaining construction. We transmit over pairs of blocks: in the first block, we use compress-and-forward; and, in the second block, we use decode-and-forward. More specifically, in the first block, the relay does not decode, it compresses the received signal via Wyner–Ziv, and it sends only part of the compression to the destination. In the second block, the relay completely decodes the message, it sends some information to the destination, and it also sends the remaining part of the compression coming from the first block. By doing so, we are able to strictly outperform both compress-and-forward and decode-and-forward. Note that the proposed coding scheme can be implemented with polar codes. As such, it has the typical attractive properties of polar coding schemes, namely, quasi-linear encoding and decoding complexity, and error probability that decays at super-polynomial speed. As a running example, we take into account the special case of the erasure relay channel, and we provide a comparison between the rates achievable by our proposed scheme and the existing upper and lower bounds. AU - Mondelli, Marco AU - Hassani, S. Hamed AU - Urbanke, Rüdiger ID - 7007 IS - 10 JF - Algorithms SN - 1999-4893 TI - A new coding paradigm for the primitive relay channel VL - 12 ER - TY - CONF AB - The aim of this short note is to expound one particular issue that was discussed during the talk [10] given at the symposium ”Researches on isometries as preserver problems and related topics” at Kyoto RIMS. That is, the role of Dirac masses by describing the isometry group of various metric spaces of probability measures. This article is of survey character, and it does not contain any essentially new results.From an isometric point of view, in some cases, metric spaces of measures are similar to C(K)-type function spaces. Similarity means here that their isometries are driven by some nice transformations of the underlying space. Of course, it depends on the particular choice of the metric how nice these transformations should be. Sometimes, as we will see, being a homeomorphism is enough to generate an isometry. But sometimes we need more: the transformation must preserve the underlying distance as well. Statements claiming that isometries in questions are necessarily induced by homeomorphisms are called Banach-Stone-type results, while results asserting that the underlying transformation is necessarily an isometry are termed as isometric rigidity results.As Dirac masses can be considered as building bricks of the set of all Borel measures, a natural question arises:Is it enough to understand how an isometry acts on the set of Dirac masses? Does this action extend uniquely to all measures?In what follows, we will thoroughly investigate this question. AU - Geher, Gyorgy Pal AU - Titkos, Tamas AU - Virosztek, Daniel ID - 7035 T2 - Kyoto RIMS Kôkyûroku TI - Dirac masses and isometric rigidity VL - 2125 ER - TY - BOOK AB - Wissen Sie, was sich hinter künstlicher Intelligenz und maschinellem Lernen verbirgt? Dieses Sachbuch erklärt Ihnen leicht verständlich und ohne komplizierte Formeln die grundlegenden Methoden und Vorgehensweisen des maschinellen Lernens. Mathematisches Vorwissen ist dafür nicht nötig. Kurzweilig und informativ illustriert Lisa, die Protagonistin des Buches, diese anhand von Alltagssituationen. Ein Buch für alle, die in Diskussionen über Chancen und Risiken der aktuellen Entwicklung der künstlichen Intelligenz und des maschinellen Lernens mit Faktenwissen punkten möchten. Auch für Schülerinnen und Schüler geeignet! ED - Kersting, Kristian ED - Lampert, Christoph ED - Rothkopf, Constantin ID - 7171 SN - 978-3-658-26762-9 TI - Wie Maschinen Lernen: Künstliche Intelligenz Verständlich Erklärt ER - TY - CONF AB - The genus g(G) of a graph G is the minimum g such that G has an embedding on the orientable surface M_g of genus g. A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z_2-genus of a graph G, denoted by g_0(G), is the minimum g such that G has an independently even drawing on M_g. By a result of Battle, Harary, Kodama and Youngs from 1962, the graph genus is additive over 2-connected blocks. In 2013, Schaefer and Stefankovic proved that the Z_2-genus of a graph is additive over 2-connected blocks as well, and asked whether this result can be extended to so-called 2-amalgamations, as an analogue of results by Decker, Glover, Huneke, and Stahl for the genus. We give the following partial answer. If G=G_1 cup G_2, G_1 and G_2 intersect in two vertices u and v, and G-u-v has k connected components (among which we count the edge uv if present), then |g_0(G)-(g_0(G_1)+g_0(G_2))|<=k+1. For complete bipartite graphs K_{m,n}, with n >= m >= 3, we prove that g_0(K_{m,n})/g(K_{m,n})=1-O(1/n). Similar results are proved also for the Euler Z_2-genus. We express the Z_2-genus of a graph using the minimum rank of partial symmetric matrices over Z_2; a problem that might be of independent interest. AU - Fulek, Radoslav AU - Kyncl, Jan ID - 7401 SN - 1868-8969 T2 - 35th International Symposium on Computational Geometry (SoCG 2019) TI - Z_2-Genus of graphs and minimum rank of partial symmetric matrices VL - 129 ER - TY - CHAP AB - We illustrate the ingredients of the state-of-the-art of model-based approach for the formal design and verification of cyber-physical systems. To capture the interaction between a discrete controller and its continuously evolving environment, we use the formal models of timed and hybrid automata. We explain the steps of modeling and verification in the tools Uppaal and SpaceEx using a case study based on a dual-chamber implantable pacemaker monitoring a human heart. We show how to design a model as a composition of components, how to construct models at varying levels of detail, how to establish that one model is an abstraction of another, how to specify correctness requirements using temporal logic, and how to verify that a model satisfies a logical requirement. AU - Alur, Rajeev AU - Giacobbe, Mirco AU - Henzinger, Thomas A AU - Larsen, Kim G. AU - Mikučionis, Marius ED - Steffen, Bernhard ED - Woeginger, Gerhard ID - 7453 SN - 1611-3349 T2 - Computing and Software Science TI - Continuous-time models for system design and analysis VL - 10000 ER - TY - JOUR AB - We consider an optimal control problem for an abstract nonlinear dissipative evolution equation. The differential constraint is penalized by augmenting the target functional by a nonnegative global-in-time functional which is null-minimized in the evolution equation is satisfied. Different variational settings are presented, leading to the convergence of the penalization method for gradient flows, noncyclic and semimonotone flows, doubly nonlinear evolutions, and GENERIC systems. AU - Portinale, Lorenzo AU - Stefanelli, Ulisse ID - 7550 IS - 2 JF - Advances in Mathematical Sciences and Applications SN - 1343-4373 TI - Penalization via global functionals of optimal-control problems for dissipative evolution VL - 28 ER - TY - GEN AB - There is increasing evidence that protein binding to specific sites along DNA can activate the reading out of genetic information without coming into direct physical contact with the gene. There also is evidence that these distant but interacting sites are embedded in a liquid droplet of proteins which condenses out of the surrounding solution. We argue that droplet-mediated interactions can account for crucial features of gene regulation only if the droplet is poised at a non-generic point in its phase diagram. We explore a minimal model that embodies this idea, show that this model has a natural mechanism for self-tuning, and suggest direct experimental tests. AU - Bialek, William AU - Gregor, Thomas AU - Tkačik, Gašper ID - 7552 T2 - arXiv:1912.08579 TI - Action at a distance in transcriptional regulation ER - TY - CONF AB - We present the results of a friendly competition for formal verification of continuous and hybrid systems with nonlinear continuous dynamics. The friendly competition took place as part of the workshop Applied Verification for Continuous and Hybrid Systems (ARCH) in 2019. In this year, 6 tools Ariadne, CORA, DynIbex, Flow*, Isabelle/HOL, and JuliaReach (in alphabetic order) participated. They are applied to solve reachability analysis problems on four benchmark problems, one of them with hybrid dynamics. We do not rank the tools based on the results, but show the current status and discover the potential advantages of different tools. AU - Immler, Fabian AU - Althoff, Matthias AU - Benet, Luis AU - Chapoutot, Alexandre AU - Chen, Xin AU - Forets, Marcelo AU - Geretti, Luca AU - Kochdumper, Niklas AU - Sanders, David P. AU - Schilling, Christian ID - 7576 T2 - EPiC Series in Computing TI - ARCH-COMP19 Category Report: Continuous and hybrid systems with nonlinear dynamics VL - 61 ER - TY - CONF AB - We study edge asymptotics of poissonized Plancherel-type measures on skew Young diagrams (integer partitions). These measures can be seen as generalizations of those studied by Baik--Deift--Johansson and Baik--Rains in resolving Ulam's problem on longest increasing subsequences of random permutations and the last passage percolation (corner growth) discrete versions thereof. Moreover they interpolate between said measures and the uniform measure on partitions. In the new KPZ-like 1/3 exponent edge scaling limit with logarithmic corrections, we find new probability distributions generalizing the classical Tracy--Widom GUE, GOE and GSE distributions from the theory of random matrices. AU - Betea, Dan AU - Bouttier, Jérémie AU - Nejjar, Peter AU - Vuletíc, Mirjana ID - 8175 T2 - Proceedings on the 31st International Conference on Formal Power Series and Algebraic Combinatorics TI - New edge asymptotics of skew Young diagrams via free boundaries ER - TY - CONF AB - This report presents the results of a friendly competition for formal verification of continuous and hybrid systems with linear continuous dynamics. The friendly competition took place as part of the workshop Applied Verification for Continuous and Hybrid Systems (ARCH) in 2019. In its third edition, seven tools have been applied to solve six different benchmark problems in the category for linear continuous dynamics (in alphabetical order): CORA, CORA/SX, HyDRA, Hylaa, JuliaReach, SpaceEx, and XSpeed. This report is a snapshot of the current landscape of tools and the types of benchmarks they are particularly suited for. Due to the diversity of problems, we are not ranking tools, yet the presented results provide one of the most complete assessments of tools for the safety verification of continuous and hybrid systems with linear continuous dynamics up to this date. AU - Althoff, Matthias AU - Bak, Stanley AU - Forets, Marcelo AU - Frehse, Goran AU - Kochdumper, Niklas AU - Ray, Rajarshi AU - Schilling, Christian AU - Schupp, Stefan ID - 8570 T2 - EPiC Series in Computing TI - ARCH-COMP19 Category Report: Continuous and hybrid systems with linear continuous dynamics VL - 61 ER - TY - JOUR AB - Glyphosate (N-phosphonomethyl glycine) and its commercial herbicide formulations have been shown to exert toxicity via various mechanisms. It has been asserted that glyphosate substitutes for glycine in polypeptide chains leading to protein misfolding and toxicity. However, as no direct evidence exists for glycine to glyphosate substitution in proteins, including in mammalian organisms, we tested this claim by conducting a proteomics analysis of MDA-MB-231 human breast cancer cells grown in the presence of 100 mg/L glyphosate for 6 days. Protein extracts from three treated and three untreated cell cultures were analysed as one TMT-6plex labelled sample, to highlight a specific pattern (+/+/+/−/−/−) of reporter intensities for peptides bearing true glyphosate treatment induced-post translational modifications as well as allowing an investigation of the total proteome. AU - Antoniou, Michael N. AU - Nicolas, Armel AU - Mesnage, Robin AU - Biserni, Martina AU - Rao, Francesco V. AU - Martin, Cristina Vazquez ID - 6819 JF - BMC Research Notes TI - Glyphosate does not substitute for glycine in proteins of actively dividing mammalian cells VL - 12 ER - TY - GEN AB - Additional file 1: Table S1. Kinetics of MDA-MB-231 cell growth in either the presence or absence of 100Â mg/L glyphosate. Cell counts are given at day-1 of seeding flasks and following 6-days of continuous culture. Note: no differences in cell numbers were observed between negative control and glyphosate treated cultures. AU - Antoniou, Michael N. AU - Nicolas, Armel AU - Mesnage, Robin AU - Biserni, Martina AU - Rao, Francesco V. AU - Martin, Cristina Vazquez ID - 9784 TI - MOESM1 of Glyphosate does not substitute for glycine in proteins of actively dividing mammalian cells ER - TY - GEN AB - More than 100 years after Grigg’s influential analysis of species’ borders, the causes of limits to species’ ranges still represent a puzzle that has never been understood with clarity. The topic has become especially important recently as many scientists have become interested in the potential for species’ ranges to shift in response to climate change—and yet nearly all of those studies fail to recognise or incorporate evolutionary genetics in a way that relates to theoretical developments. I show that range margins can be understood based on just two measurable parameters: (i) the fitness cost of dispersal—a measure of environmental heterogeneity—and (ii) the strength of genetic drift, which reduces genetic diversity. Together, these two parameters define an ‘expansion threshold’: adaptation fails when genetic drift reduces genetic diversity below that required for adaptation to a heterogeneous environment. When the key parameters drop below this expansion threshold locally, a sharp range margin forms. When they drop below this threshold throughout the species’ range, adaptation collapses everywhere, resulting in either extinction or formation of a fragmented metapopulation. Because the effects of dispersal differ fundamentally with dimension, the second parameter—the strength of genetic drift—is qualitatively different compared to a linear habitat. In two-dimensional habitats, genetic drift becomes effectively independent of selection. It decreases with ‘neighbourhood size’—the number of individuals accessible by dispersal within one generation. Moreover, in contrast to earlier predictions, which neglected evolution of genetic variance and/or stochasticity in two dimensions, dispersal into small marginal populations aids adaptation. This is because the reduction of both genetic and demographic stochasticity has a stronger effect than the cost of dispersal through increased maladaptation. The expansion threshold thus provides a novel, theoretically justified, and testable prediction for formation of the range margin and collapse of the species’ range. AU - Polechova, Jitka ID - 9839 TI - Data from: Is the sky the limit? On the expansion threshold of a species' range ER - TY - GEN AB - In this paper, we present the first fully asynchronous distributed key generation (ADKG) algorithm as well as the first distributed key generation algorithm that can create keys with a dual (f,2f+1)−threshold that are necessary for scalable consensus (which so far needs a trusted dealer assumption). In order to create a DKG with a dual (f,2f+1)− threshold we first answer in the affirmative the open question posed by Cachin et al. how to create an AVSS protocol with recovery thresholds f+1