TY - CHAP
AB - As autism spectrum disorder (ASD) is largely regarded as a neurodevelopmental condition, long-time consensus was that its hallmark features are irreversible. However, several studies from recent years using defined mouse models of ASD have provided clear evidence that in mice neurobiological and behavioural alterations can be ameliorated or even reversed by genetic restoration or pharmacological treatment either before or after symptom onset. Here, we review findings on genetic and pharmacological reversibility of phenotypes in mouse models of ASD. Our review should give a comprehensive overview on both aspects and encourage future studies to better understand the underlying molecular mechanisms that might be translatable from animals to humans.
AU - Schroeder, Jan
AU - Deliu, Elena
AU - Novarino, Gaia
AU - Schmeisser, Michael
ED - Schmeisser, Michael
ED - Boekers, Tobias
ID - 634
T2 - Translational Anatomy and Cell Biology of Autism Spectrum Disorder
TI - Genetic and pharmacological reversibility of phenotypes in mouse models of autism spectrum disorder
VL - 224
ER -
TY - CONF
AB - Memory-hard functions (MHFs) are hash algorithms whose evaluation cost is dominated by memory cost. As memory, unlike computation, costs about the same across different platforms, MHFs cannot be evaluated at significantly lower cost on dedicated hardware like ASICs. MHFs have found widespread applications including password hashing, key derivation, and proofs-of-work. This paper focuses on scrypt, a simple candidate MHF designed by Percival, and described in RFC 7914. It has been used within a number of cryptocurrencies (e.g., Litecoin and Dogecoin) and has been an inspiration for Argon2d, one of the winners of the recent password-hashing competition. Despite its popularity, no rigorous lower bounds on its memory complexity are known. We prove that scrypt is optimally memory-hard, i.e., its cumulative memory complexity (cmc) in the parallel random oracle model is Ω(n2w), where w and n are the output length and number of invocations of the underlying hash function, respectively. High cmc is a strong security target for MHFs introduced by Alwen and Serbinenko (STOC’15) which implies high memory cost even for adversaries who can amortize the cost over many evaluations and evaluate the underlying hash functions many times in parallel. Our proof is the first showing optimal memory-hardness for any MHF. Our result improves both quantitatively and qualitatively upon the recent work by Alwen et al. (EUROCRYPT’16) who proved a weaker lower bound of Ω(n2w/ log2 n) for a restricted class of adversaries.
AU - Alwen, Joel F
AU - Chen, Binchi
AU - Pietrzak, Krzysztof Z
AU - Reyzin, Leonid
AU - Tessaro, Stefano
ED - Coron, Jean-Sébastien
ED - Buus Nielsen, Jesper
ID - 635
SN - 978-331956616-0
TI - Scrypt is maximally memory hard
VL - 10212
ER -
TY - CONF
AB - Signal regular expressions can specify sequential properties of real-valued signals based on threshold conditions, regular operations, and duration constraints. In this paper we endow them with a quantitative semantics which indicates how robustly a signal matches or does not match a given expression. First, we show that this semantics is a safe approximation of a distance between the signal and the language defined by the expression. Then, we consider the robust matching problem, that is, computing the quantitative semantics of every segment of a given signal relative to an expression. We present an algorithm that solves this problem for piecewise-constant and piecewise-linear signals and show that for such signals the robustness map is a piecewise-linear function. The availability of an indicator describing how robustly a signal segment matches some regular pattern provides a general framework for quantitative monitoring of cyber-physical systems.
AU - Bakhirkin, Alexey
AU - Ferrere, Thomas
AU - Maler, Oded
AU - Ulus, Dogan
ED - Abate, Alessandro
ED - Geeraerts, Gilles
ID - 636
SN - 978-331965764-6
TI - On the quantitative semantics of regular expressions over real-valued signals
VL - 10419
ER -
TY - CONF
AB - For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption (Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b). Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework that connects all of these works and allows us to present them in a unified and simplified fashion. Moreover, we use the framework to derive a new result for adaptively secure secret sharing over access structures defined via monotone circuits. We envision that further applications will follow in the future. Underlying our framework is the following simple idea. It is well known that selective security, where the adversary commits to n-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to 2n. However, in some cases the proof of selective security proceeds via a sequence of hybrids, where each pair of adjacent hybrids locally only requires some smaller partial information consisting of m ≪ n bits. The partial information needed might be completely different between different pairs of hybrids, and if we look across all the hybrids we might rely on the entire n-bit commitment. Nevertheless, the above is sufficient to prove adaptive security, at the cost of amplifying the adversary’s advantage by a factor of only 2m ≪ 2n. In all of our examples using the above framework, the different hybrids are captured by some sort of a graph pebbling game and the amount of information that the adversary needs to commit to in each pair of hybrids is bounded by the maximum number of pebbles in play at any point in time. Therefore, coming up with better strategies for proving adaptive security translates to various pebbling strategies for different types of graphs.
AU - Jafargholi, Zahra
AU - Kamath Hosdurg, Chethan
AU - Klein, Karen
AU - Komargodski, Ilan
AU - Pietrzak, Krzysztof Z
AU - Wichs, Daniel
ED - Katz, Jonathan
ED - Shacham, Hovav
ID - 637
SN - 978-331963687-0
TI - Be adaptive avoid overcommitting
VL - 10401
ER -
TY - GEN
ED - Bogomolov, Sergiy
ED - Martel, Matthieu
ED - Prabhakar, Pavithra
ID - 638
TI - Numerical Software Verification
VL - 10152
ER -
TY - CONF
AB - Data-independent Memory Hard Functions (iMHFS) are finding a growing number of applications in security; especially in the domain of password hashing. An important property of a concrete iMHF is specified by fixing a directed acyclic graph (DAG) Gn on n nodes. The quality of that iMHF is then captured by the following two pebbling complexities of Gn: – The parallel cumulative pebbling complexity Π∥cc(Gn) must be as high as possible (to ensure that the amortized cost of computing the function on dedicated hardware is dominated by the cost of memory). – The sequential space-time pebbling complexity Πst(Gn) should be as close as possible to Π∥cc(Gn) (to ensure that using many cores in parallel and amortizing over many instances does not give much of an advantage). In this paper we construct a family of DAGs with best possible parameters in an asymptotic sense, i.e., where Π∥cc(Gn) = Ω(n2/ log(n)) (which matches a known upper bound) and Πst(Gn) is within a constant factor of Π∥cc(Gn). Our analysis relies on a new connection between the pebbling complexity of a DAG and its depth-robustness (DR) – a well studied combinatorial property. We show that high DR is sufficient for high Π∥cc. Alwen and Blocki (CRYPTO’16) showed that high DR is necessary and so, together, these results fully characterize DAGs with high Π∥cc in terms of DR. Complementing these results, we provide new upper and lower bounds on the Π∥cc of several important candidate iMHFs from the literature. We give the first lower bounds on the memory hardness of the Catena and Balloon Hashing functions in a parallel model of computation and we give the first lower bounds of any kind for (a version) of Argon2i. Finally we describe a new class of pebbling attacks improving on those of Alwen and Blocki (CRYPTO’16). By instantiating these attacks we upperbound the Π∥cc of the Password Hashing Competition winner Argon2i and one of the Balloon Hashing functions by O (n1.71). We also show an upper bound of O(n1.625) for the Catena functions and the two remaining Balloon Hashing functions.
AU - Alwen, Joel F
AU - Blocki, Jeremiah
AU - Pietrzak, Krzysztof Z
ED - Coron, Jean-Sébastien
ED - Buus Nielsen, Jesper
ID - 640
SN - 978-331956616-0
TI - Depth-robust graphs and their cumulative memory complexity
VL - 10212
ER -
TY - CONF
AB - We introduce two novel methods for learning parameters of graphical models for image labelling. The following two tasks underline both methods: (i) perturb model parameters based on given features and ground truth labelings, so as to exactly reproduce these labelings as optima of the local polytope relaxation of the labelling problem; (ii) train a predictor for the perturbed model parameters so that improved model parameters can be applied to the labelling of novel data. Our first method implements task (i) by inverse linear programming and task (ii) using a regressor e.g. a Gaussian process. Our second approach simultaneously solves tasks (i) and (ii) in a joint manner, while being restricted to linearly parameterised predictors. Experiments demonstrate the merits of both approaches.
AU - Trajkovska, Vera
AU - Swoboda, Paul
AU - Åström, Freddie
AU - Petra, Stefanie
ED - Lauze, François
ED - Dong, Yiqiu
ED - Bjorholm Dahl, Anders
ID - 641
SN - 978-331958770-7
TI - Graphical model parameter learning by inverse linear programming
VL - 10302
ER -
TY - JOUR
AB - Cauchy problems with SPDEs on the whole space are localized to Cauchy problems on a ball of radius R. This localization reduces various kinds of spatial approximation schemes to finite dimensional problems. The error is shown to be exponentially small. As an application, a numerical scheme is presented which combines the localization and the space and time discretization, and thus is fully implementable.
AU - Gerencser, Mate
AU - Gyöngy, István
ID - 642
IS - 307
JF - Mathematics of Computation
SN - 00255718
TI - Localization errors in solving stochastic partial differential equations in the whole space
VL - 86
ER -
TY - GEN
AB - Synchronous programs are easy to specify because the side effects of an operation are finished by the time the invocation of the operation returns to the caller. Asynchronous programs, on the other hand, are difficult to specify because there are side effects due to pending computation scheduled as a result of the invocation of an operation. They are also difficult to verify because of the large number of possible interleavings of concurrent asynchronous computation threads. We show that specifications and correctness proofs for asynchronous programs can be structured by introducing the fiction, for proof purposes, that intermediate, non-quiescent states of asynchronous operations can be ignored. Then, the task of specification becomes relatively simple and the task of verification can be naturally decomposed into smaller sub-tasks. The sub-tasks iteratively summarize, guided by the structure of an asynchronous program, the atomic effect of non-atomic operations and the synchronous effect of asynchronous operations. This structuring of specifications and proofs corresponds to the introduction of multiple layers of stepwise refinement for asynchronous programs. We present the first proof rule, called synchronization, to reduce asynchronous invocations on a lower layer to synchronous invocations on a higher layer. We implemented our proof method in CIVL and evaluated it on a collection of benchmark programs.
AU - Henzinger, Thomas A
AU - Kragl, Bernhard
AU - Qadeer, Shaz
ID - 6426
SN - 2664-1690
TI - Synchronizing the asynchronous
ER -
TY - JOUR
AB - It has been reported that nicotinamide-overload induces oxidative stress associated with insulin resistance, the key feature of type 2 diabetes mellitus (T2DM). This study aimed to investigate the effects of B vitamins in T2DM. Glucose tolerance tests (GTT) were carried out in adult Sprague-Dawley rats treated with or without cumulative doses of B vitamins. More specifically, insulin tolerance tests (ITT) were also carried out in adult Sprague-Dawley rats treated with or without cumulative doses of Vitamin B3. We found that cumulative Vitamin B1 and Vitamin B3 administration significantly increased the plasma H2O2 levels associated with high insulin levels. Only Vitamin B3 reduced muscular and hepatic glycogen contents. Cumulative administration of nicotinic acid, another form of Vitamin B3, also significantly increased plasma insulin level and H2O2 generation. Moreover, cumulative administration of nicotinic acid or nicotinamide impaired glucose metabolism. This study suggested that excess Vitamin B1 and Vitamin B3 caused oxidative stress and insulin resistance.
AU - Sun, Wuping
AU - Zhai, Ming-Zhu
AU - Zhou, Qian
AU - Qian, Chengrui
AU - Jiang, Changyu
ID - 643
IS - 4
JF - Chinese Journal of Physiology
SN - 03044920
TI - Effects of B vitamins overload on plasma insulin level and hydrogen peroxide generation in rats
VL - 60
ER -
TY - JOUR
AB - An instance of the valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values specifying costs of assignments of labels to its variables or the infinite value, which indicates an infeasible assignment. The goal is to find an assignment of labels to the variables that minimizes the sum. We study, assuming that P 6= NP, how the complexity of this very general problem depends on the set of functions allowed in the instances, the so-called constraint language. The case when all allowed functions take values in f0;1g corresponds to ordinary CSPs, where one deals only with the feasibility issue, and there is no optimization. This case is the subject of the algebraic CSP dichotomy conjecture predicting for which constraint languages CSPs are tractable (i.e., solvable in polynomial time) and for which they are NP-hard. The case when all allowed functions take only finite values corresponds to a finitevalued CSP, where the feasibility aspect is trivial and one deals only with the optimization issue. The complexity of finite-valued CSPs was fully classified by Thapper and Živný. An algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language was recently given by Kozik and Ochremiak. As our main result, we prove that if a constraint language satisfies this algebraic necessary condition, and the feasibility CSP (i.e., the problem of deciding whether a given instance has a feasible solution) corresponding to the VCSP with this language is tractable, then the VCSP is tractable. The algorithm is a simple combination of the assumed algorithm for the feasibility CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy for ordinary CSPs would imply a dichotomy for general-valued CSPs.
AU - Kolmogorov, Vladimir
AU - Krokhin, Andrei
AU - Rolinek, Michal
ID - 644
IS - 3
JF - SIAM Journal on Computing
TI - The complexity of general-valued CSPs
VL - 46
ER -
TY - CONF
AB - Markov decision processes (MDPs) are standard models for probabilistic systems with non-deterministic behaviours. Long-run average rewards provide a mathematically elegant formalism for expressing long term performance. Value iteration (VI) is one of the simplest and most efficient algorithmic approaches to MDPs with other properties, such as reachability objectives. Unfortunately, a naive extension of VI does not work for MDPs with long-run average rewards, as there is no known stopping criterion. In this work our contributions are threefold. (1) We refute a conjecture related to stopping criteria for MDPs with long-run average rewards. (2) We present two practical algorithms for MDPs with long-run average rewards based on VI. First, we show that a combination of applying VI locally for each maximal end-component (MEC) and VI for reachability objectives can provide approximation guarantees. Second, extending the above approach with a simulation-guided on-demand variant of VI, we present an anytime algorithm that is able to deal with very large models. (3) Finally, we present experimental results showing that our methods significantly outperform the standard approaches on several benchmarks.
AU - Ashok, Pranav
AU - Chatterjee, Krishnendu
AU - Daca, Przemyslaw
AU - Kretinsky, Jan
AU - Meggendorfer, Tobias
ED - Majumdar, Rupak
ED - Kunčak, Viktor
ID - 645
SN - 978-331963386-2
TI - Value iteration for long run average reward in markov decision processes
VL - 10426
ER -
TY - CONF
AB - We present a novel convex relaxation and a corresponding inference algorithm for the non-binary discrete tomography problem, that is, reconstructing discrete-valued images from few linear measurements. In contrast to state of the art approaches that split the problem into a continuous reconstruction problem for the linear measurement constraints and a discrete labeling problem to enforce discrete-valued reconstructions, we propose a joint formulation that addresses both problems simultaneously, resulting in a tighter convex relaxation. For this purpose a constrained graphical model is set up and evaluated using a novel relaxation optimized by dual decomposition. We evaluate our approach experimentally and show superior solutions both mathematically (tighter relaxation) and experimentally in comparison to previously proposed relaxations.
AU - Kuske, Jan
AU - Swoboda, Paul
AU - Petra, Stefanie
ED - Lauze, François
ED - Dong, Yiqiu
ED - Bjorholm Dahl, Anders
ID - 646
SN - 978-331958770-7
TI - A novel convex relaxation for non binary discrete tomography
VL - 10302
ER -
TY - CONF
AB - Despite researchers’ efforts in the last couple of decades, reachability analysis is still a challenging problem even for linear hybrid systems. Among the existing approaches, the most practical ones are mainly based on bounded-time reachable set over-approximations. For the purpose of unbounded-time analysis, one important strategy is to abstract the original system and find an invariant for the abstraction. In this paper, we propose an approach to constructing a new kind of abstraction called conic abstraction for affine hybrid systems, and to computing reachable sets based on this abstraction. The essential feature of a conic abstraction is that it partitions the state space of a system into a set of convex polyhedral cones which is derived from a uniform conic partition of the derivative space. Such a set of polyhedral cones is able to cut all trajectories of the system into almost straight segments so that every segment of a reach pipe in a polyhedral cone tends to be straight as well, and hence can be over-approximated tightly by polyhedra using similar techniques as HyTech or PHAVer. In particular, for diagonalizable affine systems, our approach can guarantee to find an invariant for unbounded reachable sets, which is beyond the capability of bounded-time reachability analysis tools. We implemented the approach in a tool and experiments on benchmarks show that our approach is more powerful than SpaceEx and PHAVer in dealing with diagonalizable systems.
AU - Bogomolov, Sergiy
AU - Giacobbe, Mirco
AU - Henzinger, Thomas A
AU - Kong, Hui
ID - 647
SN - 978-331965764-6
TI - Conic abstractions for hybrid systems
VL - 10419
ER -
TY - CONF
AB - Pseudoentropy has found a lot of important applications to cryptography and complexity theory. In this paper we focus on the foundational problem that has not been investigated so far, namely by how much pseudoentropy (the amount seen by computationally bounded attackers) diﬀers from its information-theoretic counterpart (seen by unbounded observers), given certain limits on attacker’s computational power? We provide the following answer for HILL pseudoentropy, which exhibits a threshold behavior around the size exponential in the entropy amount:– If the attacker size (s) and advantage () satisfy s (formula presented) where k is the claimed amount of pseudoentropy, then the pseudoentropy boils down to the information-theoretic smooth entropy. – If s (formula presented) then pseudoentropy could be arbitrarily bigger than the information-theoretic smooth entropy. Besides answering the posted question, we show an elegant application of our result to the complexity theory, namely that it implies the clas-sical result on the existence of functions hard to approximate (due to Pippenger). In our approach we utilize non-constructive techniques: the duality of linear programming and the probabilistic method.
AU - Skórski, Maciej
ED - Jäger, Gerhard
ED - Steila, Silvia
ID - 648
SN - 978-331955910-0
TI - On the complexity of breaking pseudoentropy
VL - 10185
ER -
TY - CHAP
AB - We give a short overview on a recently developed notion of Ricci curvature for discrete spaces. This notion relies on geodesic convexity properties of the relative entropy along geodesics in the space of probability densities, for a metric which is similar to (but different from) the 2-Wasserstein metric. The theory can be considered as a discrete counterpart to the theory of Ricci curvature for geodesic measure spaces developed by Lott–Sturm–Villani.
AU - Maas, Jan
ED - Najman, Laurent
ED - Romon, Pascal
ID - 649
T2 - Modern Approaches to Discrete Curvature
TI - Entropic Ricci curvature for discrete spaces
VL - 2184
ER -
TY - CONF
AB - In this work we present a short and unified proof for the Strong and Weak Regularity Lemma, based on the cryptographic tech-nique called low-complexity approximations. In short, both problems reduce to a task of finding constructively an approximation for a certain target function under a class of distinguishers (test functions), where dis-tinguishers are combinations of simple rectangle-indicators. In our case these approximations can be learned by a simple iterative procedure, which yields a unified and simple proof, achieving for any graph with density d and any approximation parameter the partition size. The novelty in our proof is: (a) a simple approach which yields both strong and weaker variant, and (b) improvements when d = o(1). At an abstract level, our proof can be seen a refinement and simplification of the “analytic” proof given by Lovasz and Szegedy.
AU - Skórski, Maciej
ED - Jäger, Gerhard
ED - Steila, Silvia
ID - 650
SN - 03029743
TI - A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds
VL - 10185
ER -
TY - JOUR
AB - Superhydrophobic surfaces reduce the frictional drag between water and solid materials, but this effect is often temporary. The realization of sustained drag reduction has applications for water vehicles and pipeline flows.
AU - Hof, Björn
ID - 651
IS - 7636
JF - Nature
SN - 00280836
TI - Fluid dynamics: Water flows out of touch
VL - 541
ER -
TY - CONF
AB - A (possibly degenerate) drawing of a graph G in the plane is approximable by an embedding if it can be turned into an embedding by an arbitrarily small perturbation. We show that testing, whether a drawing of a planar graph G in the plane is approximable by an embedding, can be carried out in polynomial time, if a desired embedding of G belongs to a fixed isotopy class, i.e., the rotation system (or equivalently the faces) of the embedding of G and the choice of outer face are fixed. In other words, we show that c-planarity with embedded pipes is tractable for graphs with fixed embeddings. To the best of our knowledge an analogous result was previously known essentially only when G is a cycle.
AU - Fulek, Radoslav
ID - 6517
TI - Embedding graphs into embedded graphs
VL - 92
ER -
TY - CONF
AB - Graph games with omega-regular winning conditions provide a mathematical framework to analyze a wide range of problems in the analysis of reactive systems and programs (such as the synthesis of reactive systems, program repair, and the verification of branching time properties). Parity conditions are canonical forms to specify omega-regular winning conditions. Graph games with parity conditions are equivalent to mu-calculus model checking, and thus a very important algorithmic problem. Symbolic algorithms are of great significance because they provide scalable algorithms for the analysis of large finite-state systems, as well as algorithms for the analysis of infinite-state systems with finite quotient. A set-based symbolic algorithm uses the basic set operations and the one-step predecessor operators. We consider graph games with n vertices and parity conditions with c priorities (equivalently, a mu-calculus formula with c alternations of least and greatest fixed points). While many explicit algorithms exist for graph games with parity conditions, for set-based symbolic algorithms there are only two algorithms (notice that we use space to refer to the number of sets stored by a symbolic algorithm): (a) the basic algorithm that requires O(n^c) symbolic operations and linear space; and (b) an improved algorithm that requires O(n^{c/2+1}) symbolic operations but also O(n^{c/2+1}) space (i.e., exponential space). In this work we present two set-based symbolic algorithms for parity games: (a) our first algorithm requires O(n^{c/2+1}) symbolic operations and only requires linear space; and (b) developing on our first algorithm, we present an algorithm that requires O(n^{c/3+1}) symbolic operations and only linear space. We also present the first linear space set-based symbolic algorithm for parity games that requires at most a sub-exponential number of symbolic operations.
AU - Chatterjee, Krishnendu
AU - Dvorák, Wolfgang
AU - Henzinger, Monika
AU - Loitzenbauer, Veronika
ID - 6519
TI - Improved set-based symbolic algorithms for parity games
VL - 82
ER -
TY - CONF
AB - We present an approach that enables robots to self-organize their sensorimotor behavior from scratch without providing specific information about neither the robot nor its environment. This is achieved by a simple neural control law that increases the consistency between external sensor dynamics and internal neural dynamics of the utterly simple controller. In this way, the embodiment and the agent-environment coupling are the only source of individual development. We show how an anthropomorphic tendon driven arm-shoulder system develops different behaviors depending on that coupling. For instance: Given a bottle half-filled with water, the arm starts to shake it, driven by the physical response of the water. When attaching a brush, the arm can be manipulated into wiping a table, and when connected to a revolvable wheel it finds out how to rotate it. Thus, the robot may be said to discover the affordances of the world. When allowing two (simulated) humanoid robots to interact physically, they engage into a joint behavior development leading to, for instance, spontaneous cooperation. More social effects are observed if the robots can visually perceive each other. Although, as an observer, it is tempting to attribute an apparent intentionality, there is nothing of the kind put in. As a conclusion, we argue that emergent behavior may be much less rooted in explicit intentions, internal motivations, or specific reward systems than is commonly believed.
AU - Der, Ralf
AU - Martius, Georg S
ID - 652
SN - 978-150905069-7
TI - Dynamical self consistency leads to behavioral development and emergent social interactions in robots
ER -
TY - CONF
AB - This paper studies the complexity of estimating Rényi divergences of discrete distributions: p observed from samples and the baseline distribution q known a priori. Extending the results of Acharya et al. (SODA'15) on estimating Rényi entropy, we present improved estimation techniques together with upper and lower bounds on the sample complexity. We show that, contrarily to estimating Rényi entropy where a sublinear (in the alphabet size) number of samples suffices, the sample complexity is heavily dependent on events occurring unlikely in q, and is unbounded in general (no matter what an estimation technique is used). For any divergence of integer order bigger than 1, we provide upper and lower bounds on the number of samples dependent on probabilities of p and q (the lower bounds hold for non-integer orders as well). We conclude that the worst-case sample complexity is polynomial in the alphabet size if and only if the probabilities of q are non-negligible. This gives theoretical insights into heuristics used in the applied literature to handle numerical instability, which occurs for small probabilities of q. Our result shows that they should be handled with care not only because of numerical issues, but also because of a blow up in the sample complexity.
AU - Skórski, Maciej
ID - 6526
SN - 9781509040964
T2 - 2017 IEEE International Symposium on Information Theory (ISIT)
TI - On the complexity of estimating Rènyi divergences
ER -
TY - CONF
AB - A memory-hard function (MHF) ƒn with parameter n can be computed in sequential time and space n. Simultaneously, a high amortized parallel area-time complexity (aAT) is incurred per evaluation. In practice, MHFs are used to limit the rate at which an adversary (using a custom computational device) can evaluate a security sensitive function that still occasionally needs to be evaluated by honest users (using an off-the-shelf general purpose device). The most prevalent examples of such sensitive functions are Key Derivation Functions (KDFs) and password hashing algorithms where rate limits help mitigate off-line dictionary attacks. As the honest users' inputs to these functions are often (low-entropy) passwords special attention is given to a class of side-channel resistant MHFs called iMHFs.
Essentially all iMHFs can be viewed as some mode of operation (making n calls to some round function) given by a directed acyclic graph (DAG) with very low indegree. Recently, a combinatorial property of a DAG has been identified (called "depth-robustness") which results in good provable security for an iMHF based on that DAG. Depth-robust DAGs have also proven useful in other cryptographic applications. Unfortunately, up till now, all known very depth-robust DAGs are impractically complicated and little is known about their exact (i.e. non-asymptotic) depth-robustness both in theory and in practice.
In this work we build and analyze (both formally and empirically) several exceedingly simple and efficient to navigate practical DAGs for use in iMHFs and other applications. For each DAG we:
*Prove that their depth-robustness is asymptotically maximal.
*Prove bounds of at least 3 orders of magnitude better on their exact depth-robustness compared to known bounds for other practical iMHF.
*Implement and empirically evaluate their depth-robustness and aAT against a variety of state-of-the art (and several new) depth-reduction and low aAT attacks.
We find that, against all attacks, the new DAGs perform significantly better in practice than Argon2i, the most widely deployed iMHF in practice.
Along the way we also improve the best known empirical attacks on the aAT of Argon2i by implementing and testing several heuristic versions of a (hitherto purely theoretical) depth-reduction attack. Finally, we demonstrate practicality of our constructions by modifying the Argon2i code base to use one of the new high aAT DAGs. Experimental benchmarks on a standard off-the-shelf CPU show that the new modifications do not adversely affect the impressive throughput of Argon2i (despite seemingly enjoying significantly higher aAT).
AU - Alwen, Joel F
AU - Blocki, Jeremiah
AU - Harsha, Ben
ID - 6527
SN - 9781450349468
T2 - Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security
TI - Practical graphs for optimal side-channel resistant memory-hard functions
ER -
TY - JOUR
AB - The extent of heterogeneity among driver gene mutations present in naturally occurring metastases - that is, treatment-naive metastatic disease - is largely unknown. To address this issue, we carried out 60× whole-genome sequencing of 26 metastases from four patients with pancreatic cancer. We found that identical mutations in known driver genes were present in every metastatic lesion for each patient studied. Passenger gene mutations, which do not have known or predicted functional consequences, accounted for all intratumoral heterogeneity. Even with respect to these passenger mutations, our analysis suggests that the genetic similarity among the founding cells of metastases was higher than that expected for any two cells randomly taken from a normal tissue. The uniformity of known driver gene mutations among metastases in the same patient has critical and encouraging implications for the success of future targeted therapies in advanced-stage disease.
AU - Makohon Moore, Alvin
AU - Zhang, Ming
AU - Reiter, Johannes
AU - Božić, Ivana
AU - Allen, Benjamin
AU - Kundu, Deepanjan
AU - Chatterjee, Krishnendu
AU - Wong, Fay
AU - Jiao, Yuchen
AU - Kohutek, Zachary
AU - Hong, Jungeui
AU - Attiyeh, Marc
AU - Javier, Breanna
AU - Wood, Laura
AU - Hruban, Ralph
AU - Nowak, Martin
AU - Papadopoulos, Nickolas
AU - Kinzler, Kenneth
AU - Vogelstein, Bert
AU - Iacobuzio Donahue, Christine
ID - 653
IS - 3
JF - Nature Genetics
SN - 10614036
TI - Limited heterogeneity of known driver gene mutations among the metastases of individual patients with pancreatic cancer
VL - 49
ER -
TY - JOUR
AB - In November 2016, developmental biologists, synthetic biologists and engineers gathered in Paris for a meeting called ‘Engineering the embryo’. The participants shared an interest in exploring how synthetic systems can reveal new principles of embryonic development, and how the in vitro manipulation and modeling of development using stem cells can be used to integrate ideas and expertise from physics, developmental biology and tissue engineering. As we review here, the conference pinpointed some of the challenges arising at the intersection of these fields, along with great enthusiasm for finding new approaches and collaborations.
AU - Kicheva, Anna
AU - Rivron, Nicolas
ID - 654
IS - 5
JF - Development
SN - 09501991
TI - Creating to understand – developmental biology meets engineering in Paris
VL - 144
ER -
TY - JOUR
AB - The bacterial flagellum is a self-assembling nanomachine. The external flagellar filament, several times longer than a bacterial cell body, is made of a few tens of thousands subunits of a single protein: flagellin. A fundamental problem concerns the molecular mechanism of how the flagellum grows outside the cell, where no discernible energy source is available. Here, we monitored the dynamic assembly of individual flagella using in situ labelling and real-time immunostaining of elongating flagellar filaments. We report that the rate of flagellum growth, initially ~1,700 amino acids per second, decreases with length and that the previously proposed chain mechanism does not contribute to the filament elongation dynamics. Inhibition of the proton motive force-dependent export apparatus revealed a major contribution of substrate injection in driving filament elongation. The combination of experimental and mathematical evidence demonstrates that a simple, injection-diffusion mechanism controls bacterial flagella growth outside the cell.
AU - Renault, Thibaud
AU - Abraham, Anthony
AU - Bergmiller, Tobias
AU - Paradis, Guillaume
AU - Rainville, Simon
AU - Charpentier, Emmanuelle
AU - Guet, Calin C
AU - Tu, Yuhai
AU - Namba, Keiichi
AU - Keener, James
AU - Minamino, Tohru
AU - Erhardt, Marc
ID - 655
JF - eLife
SN - 2050084X
TI - Bacterial flagella grow through an injection diffusion mechanism
VL - 6
ER -
TY - JOUR
AB - Human neurons transplanted into a mouse model for Alzheimer’s disease show human-specific vulnerability to β-amyloid plaques and may help to identify new therapeutic targets.
AU - Novarino, Gaia
ID - 656
IS - 381
JF - Science Translational Medicine
SN - 19466234
TI - Modeling Alzheimer's disease in mice with human neurons
VL - 9
ER -
TY - JOUR
AB - Plant organs are typically organized into three main tissue layers. The middle ground tissue layer comprises the majority of the plant body and serves a wide range of functions, including photosynthesis, selective nutrient uptake and storage, and gravity sensing. Ground tissue patterning and maintenance in Arabidopsis are controlled by a well-established gene network revolving around the key regulator SHORT-ROOT (SHR). In contrast, it is completely unknown how ground tissue identity is first specified from totipotent precursor cells in the embryo. The plant signaling molecule auxin, acting through AUXIN RESPONSE FACTOR (ARF) transcription factors, is critical for embryo patterning. The auxin effector ARF5/MONOPTEROS (MP) acts both cell-autonomously and noncell-autonomously to control embryonic vascular tissue formation and root initiation, respectively. Here we show that auxin response and ARF activity cell-autonomously control the asymmetric division of the first ground tissue cells. By identifying embryonic target genes, we show that MP transcriptionally initiates the ground tissue lineage and acts upstream of the regulatory network that controls ground tissue patterning and maintenance. Strikingly, whereas the SHR network depends on MP, this MP function is, at least in part, SHR independent. Our study therefore identifies auxin response as a regulator of ground tissue specification in the embryonic root, and reveals that ground tissue initiation and maintenance use different regulators and mechanisms. Moreover, our data provide a framework for the simultaneous formation of multiple cell types by the same transcriptional regulator.
AU - Möller, Barbara
AU - Ten Hove, Colette
AU - Xiang, Daoquan
AU - Williams, Nerys
AU - López, Lorena
AU - Yoshida, Saiko
AU - Smit, Margot
AU - Datla, Raju
AU - Weijers, Dolf
ID - 657
IS - 12
JF - PNAS
SN - 00278424
TI - Auxin response cell autonomously controls ground tissue initiation in the early arabidopsis embryo
VL - 114
ER -
TY - JOUR
AB - With the accelerated development of robot technologies, control becomes one of the central themes of research. In traditional approaches, the controller, by its internal functionality, finds appropriate actions on the basis of specific objectives for the task at hand. While very successful in many applications, self-organized control schemes seem to be favored in large complex systems with unknown dynamics or which are difficult to model. Reasons are the expected scalability, robustness, and resilience of self-organizing systems. The paper presents a self-learning neurocontroller based on extrinsic differential plasticity introduced recently, applying it to an anthropomorphic musculoskeletal robot arm with attached objects of unknown physical dynamics. The central finding of the paper is the following effect: by the mere feedback through the internal dynamics of the object, the robot is learning to relate each of the objects with a very specific sensorimotor pattern. Specifically, an attached pendulum pilots the arm into a circular motion, a half-filled bottle produces axis oriented shaking behavior, a wheel is getting rotated, and wiping patterns emerge automatically in a table-plus-brush setting. By these object-specific dynamical patterns, the robot may be said to recognize the object's identity, or in other words, it discovers dynamical affordances of objects. Furthermore, when including hand coordinates obtained from a camera, a dedicated hand-eye coordination self-organizes spontaneously. These phenomena are discussed from a specific dynamical system perspective. Central is the dedicated working regime at the border to instability with its potentially infinite reservoir of (limit cycle) attractors "waiting" to be excited. Besides converging toward one of these attractors, variate behavior is also arising from a self-induced attractor morphing driven by the learning rule. We claim that experimental investigations with this anthropomorphic, self-learning robot not only generate interesting and potentially useful behaviors, but may also help to better understand what subjective human muscle feelings are, how they can be rooted in sensorimotor patterns, and how these concepts may feed back on robotics.
AU - Der, Ralf
AU - Martius, Georg S
ID - 658
IS - MAR
JF - Frontiers in Neurorobotics
SN - 16625218
TI - Self organized behavior generation for musculoskeletal robots
VL - 11
ER -
TY - JOUR
AB - Migration frequently involves Rac-mediated protrusion of lamellipodia, formed by Arp2/3 complex-dependent branching thought to be crucial for force generation and stability of these networks. The formins FMNL2 and FMNL3 are Cdc42 effectors targeting to the lamellipodium tip and shown here to nucleate and elongate actin filaments with complementary activities in vitro. In migrating B16-F1 melanoma cells, both formins contribute to the velocity of lamellipodium protrusion. Loss of FMNL2/3 function in melanoma cells and fibroblasts reduces lamellipodial width, actin filament density and -bundling, without changing patterns of Arp2/3 complex incorporation. Strikingly, in melanoma cells, FMNL2/3 gene inactivation almost completely abolishes protrusion forces exerted by lamellipodia and modifies their ultrastructural organization. Consistently, CRISPR/Cas-mediated depletion of FMNL2/3 in fibroblasts reduces both migration and capability of cells to move against viscous media. Together, we conclude that force generation in lamellipodia strongly depends on FMNL formin activity, operating in addition to Arp2/3 complex-dependent filament branching.
AU - Kage, Frieda
AU - Winterhoff, Moritz
AU - Dimchev, Vanessa
AU - Müller, Jan
AU - Thalheim, Tobias
AU - Freise, Anika
AU - Brühmann, Stefan
AU - Kollasser, Jana
AU - Block, Jennifer
AU - Dimchev, Georgi A
AU - Geyer, Matthias
AU - Schnittler, Hams
AU - Brakebusch, Cord
AU - Stradal, Theresia
AU - Carlier, Marie
AU - Sixt, Michael K
AU - Käs, Josef
AU - Faix, Jan
AU - Rottner, Klemens
ID - 659
JF - Nature Communications
SN - 20411723
TI - FMNL formins boost lamellipodial force generation
VL - 8
ER -
TY - JOUR
AB - Growing microtubules are protected from depolymerization by the presence of a GTP or GDP/Pi cap. End-binding proteins of the EB1 family bind to the stabilizing cap, allowing monitoring of its size in real time. The cap size has been shown to correlate with instantaneous microtubule stability. Here we have quantitatively characterized the properties of cap size fluctuations during steadystate growth and have developed a theory predicting their timescale and amplitude from the kinetics of microtubule growth and cap maturation. In contrast to growth speed fluctuations, cap size fluctuations show a characteristic timescale, which is defined by the lifetime of the cap sites. Growth fluctuations affect the amplitude of cap size fluctuations; however, cap size does not affect growth speed, indicating that microtubules are far from instability during most of their time of growth. Our theory provides the basis for a quantitative understanding of microtubule stability fluctuations during steady-state growth.
AU - Rickman, Jamie
AU - Düllberg, Christian F
AU - Cade, Nicholas
AU - Griffin, Lewis
AU - Surrey, Thomas
ID - 660
IS - 13
JF - PNAS
SN - 00278424
TI - Steady state EB cap size fluctuations are determined by stochastic microtubule growth and maturation
VL - 114
ER -
TY - JOUR
AB - We report a direct-numerical-simulation study of the Taylor-Couette flow in the quasi-Keplerian regime at shear Reynolds numbers up to (105). Quasi-Keplerian rotating flow has been investigated for decades as a simplified model system to study the origin of turbulence in accretion disks that is not fully understood. The flow in this study is axially periodic and thus the experimental end-wall effects on the stability of the flow are avoided. Using optimal linear perturbations as initial conditions, our simulations find no sustained turbulence: the strong initial perturbations distort the velocity profile and trigger turbulence that eventually decays.
AU - Shi, Liang
AU - Hof, Björn
AU - Rampp, Markus
AU - Avila, Marc
ID - 662
IS - 4
JF - Physics of Fluids
SN - 10706631
TI - Hydrodynamic turbulence in quasi Keplerian rotating flows
VL - 29
ER -
TY - CONF
AB - In this paper, we propose an approach to automatically compute invariant clusters for nonlinear semialgebraic hybrid systems. An invariant cluster for an ordinary differential equation (ODE) is a multivariate polynomial invariant g(u→, x→) = 0, parametric in u→, which can yield an infinite number of concrete invariants by assigning different values to u→ so that every trajectory of the system can be overapproximated precisely by the intersection of a group of concrete invariants. For semialgebraic systems, which involve ODEs with multivariate polynomial right-hand sides, given a template multivariate polynomial g(u→, x→), an invariant cluster can be obtained by first computing the remainder of the Lie derivative of g(u→, x→) divided by g(u→, x→) and then solving the system of polynomial equations obtained from the coefficients of the remainder. Based on invariant clusters and sum-of-squares (SOS) programming, we present a new method for the safety verification of hybrid systems. Experiments on nonlinear benchmark systems from biology and control theory show that our approach is efficient.
AU - Kong, Hui
AU - Bogomolov, Sergiy
AU - Schilling, Christian
AU - Jiang, Yu
AU - Henzinger, Thomas A
ID - 663
SN - 978-145034590-3
T2 - Proceedings of the 20th International Conference on Hybrid Systems
TI - Safety verification of nonlinear hybrid systems based on invariant clusters
ER -
TY - JOUR
AB - The molecular mechanisms underlying phenotypic variation in isogenic bacterial populations remain poorly understood.We report that AcrAB-TolC, the main multidrug efflux pump of Escherichia coli, exhibits a strong partitioning bias for old cell poles by a segregation mechanism that is mediated by ternary AcrAB-TolC complex formation. Mother cells inheriting old poles are phenotypically distinct and display increased drug efflux activity relative to daughters. Consequently, we find systematic and long-lived growth differences between mother and daughter cells in the presence of subinhibitory drug concentrations. A simple model for biased partitioning predicts a population structure of long-lived and highly heterogeneous phenotypes. This straightforward mechanism of generating sustained growth rate differences at subinhibitory antibiotic concentrations has implications for understanding the emergence of multidrug resistance in bacteria.
AU - Bergmiller, Tobias
AU - Andersson, Anna M
AU - Tomasek, Kathrin
AU - Balleza, Enrique
AU - Kiviet, Daniel
AU - Hauschild, Robert
AU - Tkacik, Gasper
AU - Guet, Calin C
ID - 665
IS - 6335
JF - Science
SN - 00368075
TI - Biased partitioning of the multidrug efflux pump AcrAB TolC underlies long lived phenotypic heterogeneity
VL - 356
ER -
TY - JOUR
AB - Antibiotics elicit drastic changes in microbial gene expression, including the induction of stress response genes. While certain stress responses are known to “cross-protect” bacteria from other stressors, it is unclear whether cellular responses to antibiotics have a similar protective role. By measuring the genome-wide transcriptional response dynamics of Escherichia coli to four antibiotics, we found that trimethoprim induces a rapid acid stress response that protects bacteria from subsequent exposure to acid. Combining microfluidics with time-lapse imaging to monitor survival and acid stress response in single cells revealed that the noisy expression of the acid resistance operon gadBC correlates with single-cell survival. Cells with higher gadBC expression following trimethoprim maintain higher intracellular pH and survive the acid stress longer. The seemingly random single-cell survival under acid stress can therefore be predicted from gadBC expression and rationalized in terms of GadB/C molecular function. Overall, we provide a roadmap for identifying the molecular mechanisms of single-cell cross-protection between antibiotics and other stressors.
AU - Mitosch, Karin
AU - Rieckh, Georg
AU - Bollenbach, Tobias
ID - 666
IS - 4
JF - Cell Systems
SN - 24054712
TI - Noisy response to antibiotic stress predicts subsequent single cell survival in an acidic environment
VL - 4
ER -
TY - JOUR
AB - Perinatal exposure to penicillin may result in longlasting gut and behavioral changes.
AU - Novarino, Gaia
ID - 667
IS - 387
JF - Science Translational Medicine
SN - 19466234
TI - The antisocial side of antibiotics
VL - 9
ER -
TY - JOUR
AB - Macrophage filopodia, finger-like membrane protrusions, were first implicated in phagocytosis more than 100 years ago, but little is still known about the involvement of these actin-dependent structures in particle clearance. Using spinning disk confocal microscopy to image filopodial dynamics in mouse resident Lifeact-EGFP macrophages, we show that filopodia, or filopodia-like structures, support pathogen clearance by multiple means. Filopodia supported the phagocytic uptake of bacterial (Escherichia coli) particles by (i) capturing along the filopodial shaft and surfing toward the cell body, the most common mode of capture; (ii) capturing via the tip followed by retraction; (iii) combinations of surfing and retraction; or (iv) sweeping actions. In addition, filopodia supported the uptake of zymosan (Saccharomyces cerevisiae) particles by (i) providing fixation, (ii) capturing at the tip and filopodia-guided actin anterograde flow with phagocytic cup formation, and (iii) the rapid growth of new protrusions. To explore the role of filopodia-inducing Cdc42, we generated myeloid-restricted Cdc42 knock-out mice. Cdc42-deficient macrophages exhibited rapid phagocytic cup kinetics, but reduced particle clearance, which could be explained by the marked rounded-up morphology of these cells. Macrophages lacking Myo10, thought to act downstream of Cdc42, had normal morphology, motility, and phagocytic cup formation, but displayed markedly reduced filopodia formation. In conclusion, live-cell imaging revealed multiple mechanisms involving macrophage filopodia in particle capture and engulfment. Cdc42 is not critical for filopodia or phagocytic cup formation, but plays a key role in driving macrophage lamellipodial spreading.
AU - Horsthemke, Markus
AU - Bachg, Anne
AU - Groll, Katharina
AU - Moyzio, Sven
AU - Müther, Barbara
AU - Hemkemeyer, Sandra
AU - Wedlich Söldner, Roland
AU - Sixt, Michael K
AU - Tacke, Sebastian
AU - Bähler, Martin
AU - Hanley, Peter
ID - 668
IS - 17
JF - Journal of Biological Chemistry
SN - 00219258
TI - Multiple roles of filopodial dynamics in particle capture and phagocytosis and phenotypes of Cdc42 and Myo10 deletion
VL - 292
ER -
TY - JOUR
AB - The exocyst, a eukaryotic tethering complex, coregulates targeted exocytosis as an effector of small GTPases in polarized cell growth. In land plants, several exocyst subunits are encoded by double or triple paralogs, culminating in tens of EXO70 paralogs. Out of 23 Arabidopsis thaliana EXO70 isoforms, we analyzed seven isoforms expressed in pollen. Genetic and microscopic analyses of single mutants in EXO70A2, EXO70C1, EXO70C2, EXO70F1, EXO70H3, EXO70H5, and EXO70H6 genes revealed that only a loss-of-function EXO70C2 allele resulted in a significant male-specific transmission defect (segregation 40%:51%:9%) due to aberrant pollen tube growth. Mutant pollen tubes grown in vitro exhibited an enhanced growth rate and a decreased thickness of the tip cell wall, causing tip bursts. However, exo70C2 pollen tubes could frequently recover and restart their speedy elongation, resulting in a repetitive stop-and-go growth dynamics. A pollenspecific depletion of the closest paralog, EXO70C1, using artificial microRNA in the exo70C2 mutant background, resulted in a complete pollen-specific transmission defect, suggesting redundant functions of EXO70C1 and EXO70C2. Both EXO70C1 and EXO70C2, GFP tagged and expressed under the control of their native promoters, localized in the cytoplasm of pollen grains, pollen tubes, and also root trichoblast cells. The expression of EXO70C2-GFP complemented the aberrant growth of exo70C2 pollen tubes. The absent EXO70C2 interactions with core exocyst subunits in the yeast two-hybrid assay, cytoplasmic localization, and genetic effect suggest an unconventional EXO70 function possibly as a regulator of exocytosis outside the exocyst complex. In conclusion, EXO70C2 is a novel factor contributing to the regulation of optimal tip growth of Arabidopsis pollen tubes.
AU - Synek, Lukáš
AU - Vukašinović, Nemanja
AU - Kulich, Ivan
AU - Hála, Michal
AU - Aldorfová, Klára
AU - Fendrych, Matyas
AU - Žárský, Viktor
ID - 669
IS - 1
JF - Plant Physiology
SN - 00320889
TI - EXO70C2 is a key regulatory factor for optimal tip growth of pollen
VL - 174
ER -
TY - JOUR
AB - We propose an efficient method to model paper tearing in the context of interactive modeling. The method uses geometrical information to automatically detect potential starting points of tears. We further introduce a new hybrid geometrical and physical-based method to compute the trajectory of tears while procedurally synthesizing high resolution details of the tearing path using a texture based approach. The results obtained are compared with real paper and with previous studies on the expected geometric paths of paper that tears.
AU - Schreck, Camille
AU - Rohmer, Damien
AU - Hahmann, Stefanie
ID - 670
IS - 2
JF - Computer Graphics Forum
SN - 01677055
TI - Interactive paper tearing
VL - 36
ER -
TY - JOUR
AB - Humans routinely use conditionally cooperative strategies when interacting in repeated social dilemmas. They are more likely to cooperate if others cooperated before, and are ready to retaliate if others defected. To capture the emergence of reciprocity, most previous models consider subjects who can only choose from a restricted set of representative strategies, or who react to the outcome of the very last round only. As players memorize more rounds, the dimension of the strategy space increases exponentially. This increasing computational complexity renders simulations for individuals with higher cognitive abilities infeasible, especially if multiplayer interactions are taken into account. Here, we take an axiomatic approach instead. We propose several properties that a robust cooperative strategy for a repeated multiplayer dilemma should have. These properties naturally lead to a unique class of cooperative strategies, which contains the classical Win-Stay Lose-Shift rule as a special case. A comprehensive numerical analysis for the prisoner's dilemma and for the public goods game suggests that strategies of this class readily evolve across various memory-n spaces. Our results reveal that successful strategies depend not only on how cooperative others were in the past but also on the respective context of cooperation.
AU - Hilbe, Christian
AU - Martinez, Vaquero
AU - Chatterjee, Krishnendu
AU - Nowak, Martin
ID - 671
IS - 18
JF - PNAS
SN - 00278424
TI - Memory-n strategies of direct reciprocity
VL - 114
ER -
TY - JOUR
AB - Trafficking cells frequently transmigrate through epithelial and endothelial monolayers. How monolayers cooperate with the penetrating cells to support their transit is poorly understood. We studied dendritic cell (DC) entry into lymphatic capillaries as a model system for transendothelial migration. We find that the chemokine CCL21, which is the decisive guidance cue for intravasation, mainly localizes in the trans-Golgi network and intracellular vesicles of lymphatic endothelial cells. Upon DC transmigration, these Golgi deposits disperse and CCL21 becomes extracellularly enriched at the sites of endothelial cell-cell junctions. When we reconstitute the transmigration process in vitro, we find that secretion of CCL21-positive vesicles is triggered by a DC contact-induced calcium signal, and selective calcium chelation in lymphatic endothelium attenuates transmigration. Altogether, our data demonstrate a chemokine-mediated feedback between DCs and lymphatic endothelium, which facilitates transendothelial migration.
AU - Vaahtomeri, Kari
AU - Brown, Markus
AU - Hauschild, Robert
AU - De Vries, Ingrid
AU - Leithner, Alexander F
AU - Mehling, Matthias
AU - Kaufmann, Walter
AU - Sixt, Michael K
ID - 672
IS - 5
JF - Cell Reports
SN - 22111247
TI - Locally triggered release of the chemokine CCL21 promotes dendritic cell transmigration across lymphatic endothelia
VL - 19
ER -
TY - JOUR
AB - We present a numerical study of wavy supercritical cylindrical Couette flow between counter-rotating cylinders in which the wavy pattern propagates either prograde with the inner cylinder or retrograde opposite the rotation of the inner cylinder. The wave propagation reversals from prograde to retrograde and vice versa occur at distinct values of the inner cylinder Reynolds number when the associated frequency of the wavy instability vanishes. The reversal occurs for both twofold and threefold symmetric wavy vortices. Moreover, the wave propagation reversal only occurs for sufficiently strong counter-rotation. The flow pattern reversal appears to be intrinsic in the system as either periodic boundary conditions or fixed end wall boundary conditions for different system sizes always result in the wave propagation reversal. We present a detailed bifurcation sequence and parameter space diagram with respect to retrograde behavior of wavy flows. The retrograde propagation of the instability occurs when the inner Reynolds number is about two times the outer Reynolds number. The mechanism for the retrograde propagation is associated with the inviscidly unstable region near the inner cylinder and the direction of the global average azimuthal velocity. Flow dynamics, spatio-temporal behavior, global mean angular velocity, and torque of the flow with the wavy pattern are explored.
AU - Altmeyer, Sebastian
AU - Lueptow, Richard
ID - 673
IS - 5
JF - Physical Review E - Statistical, Nonlinear, and Soft Matter Physics
SN - 24700045
TI - Wave propagation reversal for wavy vortices in wide gap counter rotating cylindrical Couette flow
VL - 95
ER -
TY - JOUR
AB - Navigation of cells along gradients of guidance cues is a determining step in many developmental and immunological processes. Gradients can either be soluble or immobilized to tissues as demonstrated for the haptotactic migration of dendritic cells (DCs) toward higher concentrations of immobilized chemokine CCL21. To elucidate how gradient characteristics govern cellular response patterns, we here introduce an in vitro system allowing to track migratory responses of DCs to precisely controlled immobilized gradients of CCL21. We find that haptotactic sensing depends on the absolute CCL21 concentration and local steepness of the gradient, consistent with a scenario where DC directionality is governed by the signal-to-noise ratio of CCL21 binding to the receptor CCR7. We find that the conditions for optimal DC guidance are perfectly provided by the CCL21 gradients we measure in vivo. Furthermore, we find that CCR7 signal termination by the G-protein-coupled receptor kinase 6 (GRK6) is crucial for haptotactic but dispensable for chemotactic CCL21 gradient sensing in vitro and confirm those observations in vivo. These findings suggest that stable, tissue-bound CCL21 gradients as sustainable “roads” ensure optimal guidance in vivo.
AU - Schwarz, Jan
AU - Bierbaum, Veronika
AU - Vaahtomeri, Kari
AU - Hauschild, Robert
AU - Brown, Markus
AU - De Vries, Ingrid
AU - Leithner, Alexander F
AU - Reversat, Anne
AU - Merrin, Jack
AU - Tarrant, Teresa
AU - Bollenbach, Tobias
AU - Sixt, Michael K
ID - 674
IS - 9
JF - Current Biology
SN - 09609822
TI - Dendritic cells interpret haptotactic chemokine gradients in a manner governed by signal to noise ratio and dependent on GRK6
VL - 27
ER -
TY - JOUR
AB - We report the enhancement of infrared absorption of chemisorbed carbon monoxide on platinum in the gap of plasmonic nanoantennas. Our method is based on the self-assembled formation of platinum nanoislands on nanoscopic dipole antenna arrays manufactured via electron beam lithography. We employ systematic variations of the plasmonic antenna resonance to precisely couple to the molecular stretch vibration of carbon monoxide adsorbed on the platinum nanoislands. Ultimately, we reach more than 1500-fold infrared absorption enhancements, allowing for an ultrasensitive detection of a monolayer of chemisorbed carbon monoxide. The developed procedure can be adapted to other metal adsorbents and molecular species and could be utilized for coverage sensing in surface catalytic reactions.
AU - Haase, Johannes
AU - Bagiante, Salvatore
AU - Sigg, Hans
AU - Van Bokhoven, Jeroen
ID - 675
IS - 10
JF - Optics Letters
TI - Surface enhanced infrared absorption of chemisorbed carbon monoxide using plasmonic nanoantennas
VL - 42
ER -
TY - JOUR
AB - The INO80 complex (INO80-C) is an evolutionarily conserved nucleosome remodeler that acts in transcription, replication, and genome stability. It is required for resistance against genotoxic agents and is involved in the repair of DNA double-strand breaks (DSBs) by homologous recombination (HR). However, the causes of the HR defect in INO80-C mutant cells are controversial. Here, we unite previous findings using a system to study HR with high spatial resolution in budding yeast. We find that INO80-C has at least two distinct functions during HR—DNA end resection and presynaptic filament formation. Importantly, the second function is linked to the histone variant H2A.Z. In the absence of H2A.Z, presynaptic filament formation and HR are restored in INO80-C-deficient mutants, suggesting that presynaptic filament formation is the crucial INO80-C function during HR.
AU - Lademann, Claudio
AU - Renkawitz, Jörg
AU - Pfander, Boris
AU - Jentsch, Stefan
ID - 677
IS - 7
JF - Cell Reports
SN - 22111247
TI - The INO80 complex removes H2A.Z to promote presynaptic filament formation during homologous recombination
VL - 19
ER -
TY - JOUR
AB - The seminal observation that mechanical signals can elicit changes in biochemical signalling within cells, a process commonly termed mechanosensation and mechanotransduction, has revolutionized our understanding of the role of cell mechanics in various fundamental biological processes, such as cell motility, adhesion, proliferation and differentiation. In this Review, we will discuss how the interplay and feedback between mechanical and biochemical signals control tissue morphogenesis and cell fate specification in embryonic development.
AU - Petridou, Nicoletta
AU - Spiro, Zoltan P
AU - Heisenberg, Carl-Philipp J
ID - 678
IS - 6
JF - Nature Cell Biology
SN - 14657392
TI - Multiscale force sensing in development
VL - 19
ER -
TY - JOUR
AB - Protective responses against pathogens require a rapid mobilization of resting neutrophils and the timely removal of activated ones. Neutrophils are exceptionally short-lived leukocytes, yet it remains unclear whether the lifespan of pathogen-engaged neutrophils is regulated differently from that in the circulating steady-state pool. Here, we have found that under homeostatic conditions, the mRNA-destabilizing protein tristetraprolin (TTP) regulates apoptosis and the numbers of activated infiltrating murine neutrophils but not neutrophil cellularity. Activated TTP-deficient neutrophils exhibited decreased apoptosis and enhanced accumulation at the infection site. In the context of myeloid-specific deletion of Ttp, the potentiation of neutrophil deployment protected mice against lethal soft tissue infection with Streptococcus pyogenes and prevented bacterial dissemination. Neutrophil transcriptome analysis revealed that decreased apoptosis of TTP-deficient neutrophils was specifically associated with elevated expression of myeloid cell leukemia 1 (Mcl1) but not other antiapoptotic B cell leukemia/ lymphoma 2 (Bcl2) family members. Higher Mcl1 expression resulted from stabilization of Mcl1 mRNA in the absence of TTP. The low apoptosis rate of infiltrating TTP-deficient neutrophils was comparable to that of transgenic Mcl1-overexpressing neutrophils. Our study demonstrates that posttranscriptional gene regulation by TTP schedules the termination of the antimicrobial engagement of neutrophils. The balancing role of TTP comes at the cost of an increased risk of bacterial infections.
AU - Ebner, Florian
AU - Sedlyarov, Vitaly
AU - Tasciyan, Saren
AU - Ivin, Masa
AU - Kratochvill, Franz
AU - Gratz, Nina
AU - Kenner, Lukas
AU - Villunger, Andreas
AU - Sixt, Michael K
AU - Kovarik, Pavel
ID - 679
IS - 6
JF - The Journal of Clinical Investigation
SN - 00219738
TI - The RNA-binding protein tristetraprolin schedules apoptosis of pathogen-engaged neutrophils during bacterial infection
VL - 127
ER -
TY - JOUR
AB - In order to respond reliably to specific features of their environment, sensory neurons need to integrate multiple incoming noisy signals. Crucially, they also need to compete for the interpretation of those signals with other neurons representing similar features. The form that this competition should take depends critically on the noise corrupting these signals. In this study we show that for the type of noise commonly observed in sensory systems, whose variance scales with the mean signal, sensory neurons should selectively divide their input signals by their predictions, suppressing ambiguous cues while amplifying others. Any change in the stimulus context alters which inputs are suppressed, leading to a deep dynamic reshaping of neural receptive fields going far beyond simple surround suppression. Paradoxically, these highly variable receptive fields go alongside and are in fact required for an invariant representation of external sensory features. In addition to offering a normative account of context-dependent changes in sensory responses, perceptual inference in the presence of signal-dependent noise accounts for ubiquitous features of sensory neurons such as divisive normalization, gain control and contrast dependent temporal dynamics.
AU - Chalk, Matthew J
AU - Masset, Paul
AU - Gutkin, Boris
AU - Denève, Sophie
ID - 680
IS - 6
JF - PLoS Computational Biology
SN - 1553734X
TI - Sensory noise predicts divisive reshaping of receptive fields
VL - 13
ER -
TY - JOUR
AB - Two-player games on graphs provide the theoretical framework for many important problems such as reactive synthesis. While the traditional study of two-player zero-sum games has been extended to multi-player games with several notions of equilibria, they are decidable only for perfect-information games, whereas several applications require imperfect-information. In this paper we propose a new notion of equilibria, called doomsday equilibria, which is a strategy profile where all players satisfy their own objective, and if any coalition of players deviates and violates even one of the players' objective, then the objective of every player is violated. We present algorithms and complexity results for deciding the existence of doomsday equilibria for various classes of ω-regular objectives, both for imperfect-information games, and for perfect-information games. We provide optimal complexity bounds for imperfect-information games, and in most cases for perfect-information games.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Filiot, Emmanuel
AU - Raskin, Jean
ID - 681
JF - Information and Computation
SN - 08905401
TI - Doomsday equilibria for omega-regular games
VL - 254
ER -
TY - CONF
AB - Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of O(n7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture.
AU - Lubiw, Anna
AU - Masárová, Zuzana
AU - Wagner, Uli
ID - 683
TI - A proof of the orbit conjecture for flipping edge labelled triangulations
VL - 77
ER -
TY - CONF
AB - In classical machine learning, regression is treated as a black box process of identifying a suitable function from a hypothesis set without attempting to gain insight into the mechanism connecting inputs and outputs. In the natural sciences, however, finding an interpretable function for a phenomenon is the prime goal as it allows to understand and generalize results. This paper proposes a novel type of function learning network, called equation learner (EQL), that can learn analytical expressions and is able to extrapolate to unseen domains. It is implemented as an end-to-end differentiable feed-forward network and allows for efficient gradient based training. Due to sparsity regularization concise interpretable expressions can be obtained. Often the true underlying source expression is identified.
AU - Martius, Georg S
AU - Lampert, Christoph
ID - 6841
T2 - 5th International Conference on Learning Representations, ICLR 2017 - Workshop Track Proceedings
TI - Extrapolation and learning equations
ER -
TY - JOUR
AB - By applying methods and principles from the physical sciences to biological problems, D'Arcy Thompson's On Growth and Form demonstrated how mathematical reasoning reveals elegant, simple explanations for seemingly complex processes. This has had a profound influence on subsequent generations of developmental biologists. We discuss how this influence can be traced through twentieth century morphologists, embryologists and theoreticians to current research that explores the molecular and cellular mechanisms of tissue growth and patterning, including our own studies of the vertebrate neural tube.
AU - Briscoe, James
AU - Kicheva, Anna
ID - 685
JF - Mechanisms of Development
SN - 09254773
TI - The physics of development 100 years after D'Arcy Thompson's “on growth and form”
VL - 145
ER -
TY - JOUR
AB - Tissues are thought to behave like fluids with a given surface tension. Differences in tissue surface tension (TST) have been proposed to trigger cell sorting and tissue envelopment. D'Arcy Thompson in his seminal book ‘On Growth and Form’ has introduced this concept of differential TST as a key physical mechanism dictating tissue formation and organization within the developing organism. Over the past century, many studies have picked up the concept of differential TST and analyzed the role and cell biological basis of TST in development, underlining the importance and influence of this concept in developmental biology.
AU - Heisenberg, Carl-Philipp J
ID - 686
JF - Mechanisms of Development
SN - 09254773
TI - D'Arcy Thompson's ‘on growth and form’: From soap bubbles to tissue self organization
VL - 145
ER -
TY - JOUR
AB - Pursuing the similarity between the Kontsevich-Soibelman construction of the cohomological Hall algebra (CoHA) of BPS states and Lusztig's construction of canonical bases for quantum enveloping algebras, and the similarity between the integrality conjecture for motivic Donaldson-Thomas invariants and the PBW theorem for quantum enveloping algebras, we build a coproduct on the CoHA associated to a quiver with potential. We also prove a cohomological dimensional reduction theorem, further linking a special class of CoHAs with Yangians, and explaining how to connect the study of character varieties with the study of CoHAs.
AU - Davison, Ben
ID - 687
IS - 2
JF - Quarterly Journal of Mathematics
SN - 00335606
TI - The critical CoHA of a quiver with potential
VL - 68
ER -
TY - CONF
AB - We show that the framework of topological data analysis can be extended from metrics to general Bregman divergences, widening the scope of possible applications. Examples are the Kullback - Leibler divergence, which is commonly used for comparing text and images, and the Itakura - Saito divergence, popular for speech and sound. In particular, we prove that appropriately generalized čech and Delaunay (alpha) complexes capture the correct homotopy type, namely that of the corresponding union of Bregman balls. Consequently, their filtrations give the correct persistence diagram, namely the one generated by the uniformly growing Bregman balls. Moreover, we show that unlike the metric setting, the filtration of Vietoris-Rips complexes may fail to approximate the persistence diagram. We propose algorithms to compute the thus generalized čech, Vietoris-Rips and Delaunay complexes and experimentally test their efficiency. Lastly, we explain their surprisingly good performance by making a connection with discrete Morse theory.
AU - Edelsbrunner, Herbert
AU - Wagner, Hubert
ID - 688
SN - 18688969
TI - Topological data analysis with Bregman divergences
VL - 77
ER -
TY - JOUR
AB - Rett syndrome modeling in monkey mirrors the human disorder.
AU - Novarino, Gaia
ID - 689
IS - 393
JF - Science Translational Medicine
SN - 19466234
TI - Rett syndrome modeling goes simian
VL - 9
ER -
TY - JOUR
AB - Many central synapses contain a single presynaptic active zone and a single postsynaptic density. Vesicular release statistics at such “simple synapses” indicate that they contain a small complement of docking sites where vesicles repetitively dock and fuse. In this work, we investigate functional and morphological aspects of docking sites at simple synapses made between cerebellar parallel fibers and molecular layer interneurons. Using immunogold labeling of SDS-treated freeze-fracture replicas, we find that Cav2.1 channels form several clusters per active zone with about nine channels per cluster. The mean value and range of intersynaptic variation are similar for Cav2.1 cluster numbers and for functional estimates of docking-site numbers obtained from the maximum numbers of released vesicles per action potential. Both numbers grow in relation with synaptic size and decrease by a similar extent with age between 2 wk and 4 wk postnatal. Thus, the mean docking-site numbers were 3.15 at 2 wk (range: 1–10) and 2.03 at 4 wk (range: 1–4), whereas the mean numbers of Cav2.1 clusters were 2.84 at 2 wk (range: 1–8) and 2.37 at 4 wk (range: 1–5). These changes were accompanied by decreases of miniature current amplitude (from 93 pA to 56 pA), active-zone surface area (from 0.0427 μm2 to 0.0234 μm2), and initial success rate (from 0.609 to 0.353), indicating a tightening of synaptic transmission with development. Altogether, these results suggest a close correspondence between the number of functionally defined vesicular docking sites and that of clusters of voltage-gated calcium channels.
AU - Miki, Takafumi
AU - Kaufmann, Walter
AU - Malagon, Gerardo
AU - Gomez, Laura
AU - Tabuchi, Katsuhiko
AU - Watanabe, Masahiko
AU - Shigemoto, Ryuichi
AU - Marty, Alain
ID - 693
IS - 26
JF - PNAS
SN - 00278424
TI - Numbers of presynaptic Ca2+ channel clusters match those of functionally defined vesicular docking sites in single central synapses
VL - 114
ER -
TY - JOUR
AB - A change regarding the extent of adhesion - hereafter referred to as adhesion plasticity - between adhesive and less-adhesive states of mammalian cells is important for their behavior. To investigate adhesion plasticity, we have selected a stable isogenic subpopulation of human MDA-MB-468 breast carcinoma cells growing in suspension. These suspension cells are unable to re-adhere to various matrices or to contract three-dimensional collagen lattices. By using transcriptome analysis, we identified the focal adhesion protein tensin3 (Tns3) as a determinant of adhesion plasticity. Tns3 is strongly reduced at mRNA and protein levels in suspension cells. Furthermore, by transiently challenging breast cancer cells to grow under non-adherent conditions markedly reduces Tns3 protein expression, which is regained upon re-adhesion. Stable knockdown of Tns3 in parental MDA-MB-468 cells results in defective adhesion, spreading and migration. Tns3-knockdown cells display impaired structure and dynamics of focal adhesion complexes as determined by immunostaining. Restoration of Tns3 protein expression in suspension cells partially rescues adhesion and focal contact composition. Our work identifies Tns3 as a crucial focal adhesion component regulated by, and functionally contributing to, the switch between adhesive and non-adhesive states in MDA-MB-468 cancer cells.
AU - Veß, Astrid
AU - Blache, Ulrich
AU - Leitner, Laura
AU - Kurz, Angela
AU - Ehrenpfordt, Anja
AU - Sixt, Michael K
AU - Posern, Guido
ID - 694
IS - 13
JF - Journal of Cell Science
SN - 00219533
TI - A dual phenotype of MDA MB 468 cancer cells reveals mutual regulation of tensin3 and adhesion plasticity
VL - 130
ER -
TY - CONF
AB - De, Trevisan and Tulsiani [CRYPTO 2010] show that every distribution over n-bit strings which has constant statistical distance to uniform (e.g., the output of a pseudorandom generator mapping n-1 to n bit strings), can be distinguished from the uniform distribution with advantage epsilon by a circuit of size O( 2^n epsilon^2). We generalize this result, showing that a distribution which has less than k bits of min-entropy, can be distinguished from any distribution with k bits of delta-smooth min-entropy with advantage epsilon by a circuit of size O(2^k epsilon^2/delta^2). As a special case, this implies that any distribution with support at most 2^k (e.g., the output of a pseudoentropy generator mapping k to n bit strings) can be distinguished from any given distribution with min-entropy k+1 with advantage epsilon by a circuit of size O(2^k epsilon^2). Our result thus shows that pseudoentropy distributions face basically the same non-uniform attacks as pseudorandom distributions.
AU - Pietrzak, Krzysztof Z
AU - Skórski, Maciej
ID - 697
SN - 18688969
TI - Non uniform attacks against pseudoentropy
VL - 80
ER -
TY - JOUR
AB - Extracellular matrix signals from the microenvironment regulate gene expression patterns and cell behavior. Using a combination of experiments and geometric models, we demonstrate correlations between cell geometry, three-dimensional (3D) organization of chromosome territories, and gene expression. Fluorescence in situ hybridization experiments showed that micropatterned fibroblasts cultured on anisotropic versus isotropic substrates resulted in repositioning of specific chromosomes, which contained genes that were differentially regulated by cell geometries. Experiments combined with ellipsoid packing models revealed that the mechanosensitivity of chromosomes was correlated with their orientation in the nucleus. Transcription inhibition experiments suggested that the intermingling degree was more sensitive to global changes in transcription than to chromosome radial positioning and its orientations. These results suggested that cell geometry modulated 3D chromosome arrangement, and their neighborhoods correlated with gene expression patterns in a predictable manner. This is central to understanding geometric control of genetic programs involved in cellular homeostasis and the associated diseases.
AU - Wang, Yejun
AU - Nagarajan, Mallika
AU - Uhler, Caroline
AU - Shivashankar, Gv
ID - 698
IS - 14
JF - Molecular Biology of the Cell
SN - 10591524
TI - Orientation and repositioning of chromosomes correlate with cell geometry dependent gene expression
VL - 28
ER -
TY - JOUR
AB - In antagonistic symbioses, such as host–parasite interactions, one population’s success is the other’s loss. In mutualistic symbioses, such as division of labor, both parties can gain, but they might have different preferences over the possible mutualistic arrangements. The rates of evolution of the two populations in a symbiosis are important determinants of which population will be more successful: Faster evolution is thought to be favored in antagonistic symbioses (the “Red Queen effect”), but disfavored in certain mutualistic symbioses (the “Red King effect”). However, it remains unclear which biological parameters drive these effects. Here, we analyze the effects of the various determinants of evolutionary rate: generation time, mutation rate, population size, and the intensity of natural selection. Our main results hold for the case where mutation is infrequent. Slower evolution causes a long-term advantage in an important class of mutualistic interactions. Surprisingly, less intense selection is the strongest driver of this Red King effect, whereas relative mutation rates and generation times have little effect. In antagonistic interactions, faster evolution by any means is beneficial. Our results provide insight into the demographic evolution of symbionts.
AU - Veller, Carl
AU - Hayward, Laura
AU - Nowak, Martin
AU - Hilbe, Christian
ID - 699
IS - 27
JF - PNAS
SN - 00278424
TI - The red queen and king in finite populations
VL - 114
ER -
TY - JOUR
AB - Microtubules provide the mechanical force required for chromosome separation during mitosis. However, little is known about the dynamic (high-frequency) mechanical properties of microtubules. Here, we theoretically propose to control the vibrations of a doubly clamped microtubule by tip electrodes and to detect its motion via the optomechanical coupling between the vibrational modes of the microtubule and an optical cavity. In the presence of a red-detuned strong pump laser, this coupling leads to optomechanical-induced transparency of an optical probe field, which can be detected with state-of-the art technology. The center frequency and line width of the transparency peak give the resonance frequency and damping rate of the microtubule, respectively, while the height of the peak reveals information about the microtubule-cavity field coupling. Our method opens the new possibilities to gain information about the physical properties of microtubules, which will enhance our capability to design physical cancer treatment protocols as alternatives to chemotherapeutic drugs.
AU - Barzanjeh, Shabir
AU - Salari, Vahid
AU - Tuszynski, Jack
AU - Cifra, Michal
AU - Simon, Christoph
ID - 700
IS - 1
JF - Physical Review E Statistical Nonlinear and Soft Matter Physics
SN - 24700045
TI - Optomechanical proposal for monitoring microtubule mechanical vibrations
VL - 96
ER -
TY - JOUR
AB - A d-dimensional simplex S is called a k-reptile (or a k-reptile simplex) if it can be tiled by k simplices with disjoint interiors that are all mutually congruent and similar to S. For d = 2, triangular k-reptiles exist for all k of the form a^2, 3a^2 or a^2+b^2 and they have been completely characterized by Snover, Waiveris, and Williams. On the other hand, the only k-reptile simplices that are known for d ≥ 3, have k = m^d, where m is a positive integer. We substantially simplify the proof by Matoušek and the second author that for d = 3, k-reptile tetrahedra can exist only for k = m^3. We then prove a weaker analogue of this result for d = 4 by showing that four-dimensional k-reptile simplices can exist only for k = m^2.
AU - Kynčl, Jan
AU - Patakova, Zuzana
ID - 701
IS - 3
JF - The Electronic Journal of Combinatorics
SN - 10778926
TI - On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4
VL - 24
ER -
TY - JOUR
AB - Leading autism-associated mutation in mouse partially mimics human disorder.
AU - Novarino, Gaia
ID - 702
IS - 399
JF - Science Translational Medicine
SN - 19466234
TI - The riddle of CHD8 haploinsufficiency in autism spectrum disorder
VL - 9
ER -
TY - JOUR
AB - A hippocampal mossy fiber synapse has a complex structure and is implicated in learning and memory. In this synapse, the mossy fiber boutons attach to the dendritic shaft by puncta adherentia junctions and wrap around a multiply-branched spine, forming synaptic junctions. We have recently shown using transmission electron microscopy, immunoelectron microscopy and serial block face-scanning electron microscopy that atypical puncta adherentia junctions are formed in the afadin-deficient mossy fiber synapse and that the complexity of postsynaptic spines and mossy fiber boutons, the number of spine heads, the area of postsynaptic densities and the density of synaptic vesicles docked to active zones are decreased in the afadin-deficient synapse. We investigated here the roles of afadin in the functional differentiations of the mossy fiber synapse using the afadin-deficient mice. The electrophysiological studies showed that both the release probability of glutamate and the postsynaptic responsiveness to glutamate were markedly reduced, but not completely lost, in the afadin-deficient mossy fiber synapse, whereas neither long-term potentiation nor long-term depression was affected. These results indicate that afadin plays roles in the functional differentiations of the presynapse and the postsynapse of the hippocampal mossy fiber synapse.
AU - Geng, Xiaoqi
AU - Maruo, Tomohiko
AU - Mandai, Kenji
AU - Supriyanto, Irwan
AU - Miyata, Muneaki
AU - Sakakibara, Shotaro
AU - Mizoguchi, Akira
AU - Takai, Yoshimi
AU - Mori, Masahiro
ID - 706
IS - 8
JF - Genes to Cells
SN - 13569597
TI - Roles of afadin in functional differentiations of hippocampal mossy fiber synapse
VL - 22
ER -
TY - JOUR
AB - We answer a question of M. Gromov on the waist of the unit ball.
AU - Akopyan, Arseniy
AU - Karasev, Roman
ID - 707
IS - 4
JF - Bulletin of the London Mathematical Society
SN - 00246093
TI - A tight estimate for the waist of the ball
VL - 49
ER -
TY - JOUR
AB - In the developing and adult brain, oligodendrocyte precursor cells (OPCs) are influenced by neuronal activity: they are involved in synaptic signaling with neurons, and their proliferation and differentiation into myelinating glia can be altered by transient changes in neuronal firing. An important question that has been unanswered is whether OPCs can discriminate different patterns of neuronal activity and respond to them in a distinct way. Here, we demonstrate in brain slices that the pattern of neuronal activity determines the functional changes triggered at synapses between axons and OPCs. Furthermore, we show that stimulation of the corpus callosum at different frequencies in vivo affects proliferation and differentiation of OPCs in a dissimilar way. Our findings suggest that neurons do not influence OPCs in “all-or-none” fashion but use their firing pattern to tune the response and behavior of these nonneuronal cells.
AU - Nagy, Balint
AU - Hovhannisyan, Anahit
AU - Barzan, Ruxandra
AU - Chen, Ting
AU - Kukley, Maria
ID - 708
IS - 8
JF - PLoS Biology
SN - 15449173
TI - Different patterns of neuronal activity trigger distinct responses of oligodendrocyte precursor cells in the corpus callosum
VL - 15
ER -
TY - JOUR
AB - Adipose tissues play key roles in energy homeostasis. Brown adipocytes and beige adipocytes in white adipose tissue (WAT) share the similar characters of thermogenesis, both of them could be potential targets for obesity management. Several thermo-sensitive transient receptor potential channels (thermoTRPs) are shown to be involved in adipocyte biology. However, the expression pattern of thermoTRPs in adipose tissues from obese mice is still unknown. The mRNA expression of thermoTRPs in subcutaneous WAT (sWAT) and interscapular brown adipose tissue (iBAT) from lean and obese mice were measured using reverse transcriptase-quantitative PCRs (RT-qPCR). The results demonstrated that all 10 thermoTRPs are expressed in both iBAT and sWAT, and without significant difference in the mRNA expression level of thermoTRPs between these two tissues. Moreover, Trpv1 and Trpv3 mRNA expression levels in both iBAT and sWAT were significantly decreased in high fat diet (HFD)-induced obese mice and db/db (leptin receptor deficient) mice. Trpm2 mRNA expression level was significantly decreased only in sWAT from HFD-induced obese mice and db/db mice. On the other hand, Trpv2 and Trpv4 mRNA expression levels in iBAT and sWAT were significantly increased in HFD-induced obese mice and db/db mice. Taken together, we conclude that all 10 thermoTRPs are expressed in iBAT and sWAT. And several thermoTRPs differentially expressed in adipose tissues from HFD-induced obese mice and db/db mice, suggesting a potential involvement in anti-obesity regulations.
AU - Sun, Wuping
AU - Li, Chen
AU - Zhang, Yonghong
AU - Jiang, Changyu
AU - Zhai, Ming-Zhu
AU - Zhou, Qian
AU - Xiao, Lizu
AU - Deng, Qiwen
ID - 709
IS - 8
JF - Cell Biology International
SN - 10656995
TI - Gene expression changes of thermo sensitive transient receptor potential channels in obese mice
VL - 41
ER -
TY - CONF
AB - We revisit the problem of estimating entropy of discrete distributions from independent samples, studied recently by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015), improving their upper and lower bounds on the necessary sample size n. For estimating Renyi entropy of order alpha, up to constant accuracy and error probability, we show the following * Upper bounds n = O(1) 2^{(1-1/alpha)H_alpha} for integer alpha>1, as the worst case over distributions with Renyi entropy equal to H_alpha. * Lower bounds n = Omega(1) K^{1-1/alpha} for any real alpha>1, with the constant being an inverse polynomial of the accuracy, as the worst case over all distributions on K elements. Our upper bounds essentially replace the alphabet size by a factor exponential in the entropy, which offers improvements especially in low or medium entropy regimes (interesting for example in anomaly detection). As for the lower bounds, our proof explicitly shows how the complexity depends on both alphabet and accuracy, partially solving the open problem posted in previous works. The argument for upper bounds derives a clean identity for the variance of falling-power sum of a multinomial distribution. Our approach for lower bounds utilizes convex optimization to find a distribution with possibly worse estimation performance, and may be of independent interest as a tool to work with Le Cam’s two point method.
AU - Obremski, Maciej
AU - Skórski, Maciej
ID - 710
SN - 18688969
TI - Renyi entropy estimation revisited
VL - 81
ER -
TY - CONF
AB - Nested weighted automata (NWA) present a robust and convenient automata-theoretic formalism for quantitative specifications. Previous works have considered NWA that processed input words only in the forward direction. It is natural to allow the automata to process input words backwards as well, for example, to measure the maximal or average time between a response and the preceding request. We therefore introduce and study bidirectional NWA that can process input words in both directions. First, we show that bidirectional NWA can express interesting quantitative properties that are not expressible by forward-only NWA. Second, for the fundamental decision problems of emptiness and universality, we establish decidability and complexity results for the new framework which match the best-known results for the special case of forward-only NWA. Thus, for NWA, the increased expressiveness of bidirectionality is achieved at no additional computational complexity. This is in stark contrast to the unweighted case, where bidirectional finite automata are no more expressive but exponentially more succinct than their forward-only counterparts.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 711
SN - 18688969
TI - Bidirectional nested weighted automata
VL - 85
ER -
TY - JOUR
AB - We establish a weak–strong uniqueness principle for solutions to entropy-dissipating reaction–diffusion equations: As long as a strong solution to the reaction–diffusion equation exists, any weak solution and even any renormalized solution must coincide with this strong solution. Our assumptions on the reaction rates are just the entropy condition and local Lipschitz continuity; in particular, we do not impose any growth restrictions on the reaction rates. Therefore, our result applies to any single reversible reaction with mass-action kinetics as well as to systems of reversible reactions with mass-action kinetics satisfying the detailed balance condition. Renormalized solutions are known to exist globally in time for reaction–diffusion equations with entropy-dissipating reaction rates; in contrast, the global-in-time existence of weak solutions is in general still an open problem–even for smooth data–, thereby motivating the study of renormalized solutions. The key ingredient of our result is a careful adjustment of the usual relative entropy functional, whose evolution cannot be controlled properly for weak solutions or renormalized solutions.
AU - Fischer, Julian L
ID - 712
JF - Nonlinear Analysis: Theory, Methods and Applications
SN - 0362546X
TI - Weak–strong uniqueness of solutions to entropy dissipating reaction–diffusion equations
VL - 159
ER -
TY - JOUR
AB - To determine the dynamics of allelic-specific expression during mouse development, we analyzed RNA-seq data from 23 F1 tissues from different developmental stages, including 19 female tissues allowing X chromosome inactivation (XCI) escapers to also be detected. We demonstrate that allelic expression arising from genetic or epigenetic differences is highly tissue-specific. We find that tissue-specific strain-biased gene expression may be regulated by tissue-specific enhancers or by post-transcriptional differences in stability between the alleles. We also find that escape from X-inactivation is tissue-specific, with leg muscle showing an unexpectedly high rate of XCI escapers. By surveying a range of tissues during development, and performing extensive validation, we are able to provide a high confidence list of mouse imprinted genes including 18 novel genes. This shows that cluster size varies dynamically during development and can be substantially larger than previously thought, with the Igf2r cluster extending over 10 Mb in placenta.
AU - Andergassen, Daniel
AU - Dotter, Christoph
AU - Wenzel, Dyniel
AU - Sigl, Verena
AU - Bammer, Philipp
AU - Muckenhuber, Markus
AU - Mayer, Daniela
AU - Kulinski, Tomasz
AU - Theussl, Hans
AU - Penninger, Josef
AU - Bock, Christoph
AU - Barlow, Denise
AU - Pauler, Florian
AU - Hudson, Quanah
ID - 713
JF - eLife
SN - 2050084X
TI - Mapping the mouse Allelome reveals tissue specific regulation of allelic expression
VL - 6
ER -
TY - JOUR
AB - Background HIV-1 infection and drug abuse are frequently co-morbid and their association greatly increases the severity of HIV-1-induced neuropathology. While nucleus accumbens (NAcc) function is severely perturbed by drugs of abuse, little is known about how HIV-1 infection affects NAcc. Methods We used calcium and voltage imaging to investigate the effect of HIV-1 trans-activator of transcription (Tat) on rat NAcc. Based on previous neuronal studies, we hypothesized that Tat modulates intracellular Ca2+ homeostasis of NAcc neurons. Results We provide evidence that Tat triggers a Ca2+ signaling cascade in NAcc medium spiny neurons (MSN) expressing D1-like dopamine receptors leading to neuronal depolarization. Firstly, Tat induced inositol 1,4,5-trisphsophate (IP3) receptor-mediated Ca2+ release from endoplasmic reticulum, followed by Ca2+ and Na+ influx via transient receptor potential canonical channels. The influx of cations depolarizes the membrane promoting additional Ca2+ entry through voltage-gated P/Q-type Ca2+ channels and opening of tetrodotoxin-sensitive Na+ channels. By activating this mechanism, Tat elicits a feed-forward depolarization increasing the excitability of D1-phosphatidylinositol-linked NAcc MSN. We previously found that cocaine targets NAcc neurons directly (independent of the inhibition of dopamine transporter) only when IP3-generating mechanisms are concomitantly initiated. When tested here, cocaine produced a dose-dependent potentiation of the effect of Tat on cytosolic Ca2+. Conclusion We describe for the first time a HIV-1 Tat-triggered Ca2+ signaling in MSN of NAcc involving TRPC and depolarization and a potentiation of the effect of Tat by cocaine, which may be relevant for the reward axis in cocaine-abusing HIV-1-positive patients.
AU - Brailoiu, Gabriela
AU - Deliu, Elena
AU - Barr, Jeffrey
AU - Console Bram, Linda
AU - Ciuciu, Alexandra
AU - Abood, Mary
AU - Unterwald, Ellen
AU - Brǎiloiu, Eugen
ID - 714
JF - Drug and Alcohol Dependence
SN - 03768716
TI - HIV Tat excites D1 receptor-like expressing neurons from rat nucleus accumbens
VL - 178
ER -
TY - JOUR
AB - We study controller synthesis problems for finite-state Markov decision processes, where the objective is to optimize the expected mean-payoff performance and stability (also known as variability in the literature). We argue that the basic notion of expressing the stability using the statistical variance of the mean payoff is sometimes insufficient, and propose an alternative definition. We show that a strategy ensuring both the expected mean payoff and the variance below given bounds requires randomization and memory, under both the above definitions. We then show that the problem of finding such a strategy can be expressed as a set of constraints.
AU - Brázdil, Tomáš
AU - Chatterjee, Krishnendu
AU - Forejt, Vojtěch
AU - Kučera, Antonín
ID - 1294
JF - Journal of Computer and System Sciences
TI - Trading performance for stability in Markov decision processes
VL - 84
ER -
TY - JOUR
AB - Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrences of new mutations is much longer than the time it takes for a mutated genotype to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a stochastic process evolving one genotype by means of mutation and selection between the resident and the mutated genotype. The probability of accepting the mutated genotype then depends on the change in fitness. We study this process, SSWM, from an algorithmic perspective, quantifying its expected optimisation time for various parameters and investigating differences to a similar evolutionary algorithm, the well-known (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient.
AU - Paixao, Tiago
AU - Pérez Heredia, Jorge
AU - Sudholt, Dirk
AU - Trubenova, Barbora
ID - 1336
IS - 2
JF - Algorithmica
SN - 01784617
TI - Towards a runtime comparison of natural and artificial evolution
VL - 78
ER -
TY - JOUR
AB - We consider the local eigenvalue distribution of large self-adjoint N×N random matrices H=H∗ with centered independent entries. In contrast to previous works the matrix of variances sij=\mathbbmE|hij|2 is not assumed to be stochastic. Hence the density of states is not the Wigner semicircle law. Its possible shapes are described in the companion paper (Ajanki et al. in Quadratic Vector Equations on the Complex Upper Half Plane. arXiv:1506.05095). We show that as N grows, the resolvent, G(z)=(H−z)−1, converges to a diagonal matrix, diag(m(z)), where m(z)=(m1(z),…,mN(z)) solves the vector equation −1/mi(z)=z+∑jsijmj(z) that has been analyzed in Ajanki et al. (Quadratic Vector Equations on the Complex Upper Half Plane. arXiv:1506.05095). We prove a local law down to the smallest spectral resolution scale, and bulk universality for both real symmetric and complex hermitian symmetry classes.
AU - Ajanki, Oskari H
AU - Erdös, László
AU - Krüger, Torben H
ID - 1337
IS - 3-4
JF - Probability Theory and Related Fields
SN - 01788051
TI - Universality for general Wigner-type matrices
VL - 169
ER -
TY - JOUR
AB - We present a computer-aided programming approach to concurrency. The approach allows programmers to program assuming a friendly, non-preemptive scheduler, and our synthesis procedure inserts synchronization to ensure that the final program works even with a preemptive scheduler. The correctness specification is implicit, inferred from the non-preemptive behavior. Let us consider sequences of calls that the program makes to an external interface. The specification requires that any such sequence produced under a preemptive scheduler should be included in the set of sequences produced under a non-preemptive scheduler. We guarantee that our synthesis does not introduce deadlocks and that the synchronization inserted is optimal w.r.t. a given objective function. The solution is based on a finitary abstraction, an algorithm for bounded language inclusion modulo an independence relation, and generation of a set of global constraints over synchronization placements. Each model of the global constraints set corresponds to a correctness-ensuring synchronization placement. The placement that is optimal w.r.t. the given objective function is chosen as the synchronization solution. We apply the approach to device-driver programming, where the driver threads call the software interface of the device and the API provided by the operating system. Our experiments demonstrate that our synthesis method is precise and efficient. The implicit specification helped us find one concurrency bug previously missed when model-checking using an explicit, user-provided specification. We implemented objective functions for coarse-grained and fine-grained locking and observed that different synchronization placements are produced for our experiments, favoring a minimal number of synchronization operations or maximum concurrency, respectively.
AU - Cerny, Pavol
AU - Clarke, Edmund
AU - Henzinger, Thomas A
AU - Radhakrishna, Arjun
AU - Ryzhyk, Leonid
AU - Samanta, Roopsha
AU - Tarrach, Thorsten
ID - 1338
IS - 2-3
JF - Formal Methods in System Design
TI - From non-preemptive to preemptive scheduling using synchronization synthesis
VL - 50
ER -
TY - JOUR
AB - The behaviour of gene regulatory networks (GRNs) is typically analysed using simulation-based statistical testing-like methods. In this paper, we demonstrate that we can replace this approach by a formal verification-like method that gives higher assurance and scalability. We focus on Wagner’s weighted GRN model with varying weights, which is used in evolutionary biology. In the model, weight parameters represent the gene interaction strength that may change due to genetic mutations. For a property of interest, we synthesise the constraints over the parameter space that represent the set of GRNs satisfying the property. We experimentally show that our parameter synthesis procedure computes the mutational robustness of GRNs—an important problem of interest in evolutionary biology—more efficiently than the classical simulation method. We specify the property in linear temporal logic. We employ symbolic bounded model checking and SMT solving to compute the space of GRNs that satisfy the property, which amounts to synthesizing a set of linear constraints on the weights.
AU - Giacobbe, Mirco
AU - Guet, Calin C
AU - Gupta, Ashutosh
AU - Henzinger, Thomas A
AU - Paixao, Tiago
AU - Petrov, Tatjana
ID - 1351
IS - 8
JF - Acta Informatica
SN - 00015903
TI - Model checking the evolution of gene regulatory networks
VL - 54
ER -
TY - JOUR
AB - One of the major challenges in physically based modelling is making simulations efficient. Adaptive models provide an essential solution to these efficiency goals. These models are able to self-adapt in space and time, attempting to provide the best possible compromise between accuracy and speed. This survey reviews the adaptive solutions proposed so far in computer graphics. Models are classified according to the strategy they use for adaptation, from time-stepping and freezing techniques to geometric adaptivity in the form of structured grids, meshes and particles. Applications range from fluids, through deformable bodies, to articulated solids.
AU - Manteaux, Pierre
AU - Wojtan, Christopher J
AU - Narain, Rahul
AU - Redon, Stéphane
AU - Faure, François
AU - Cani, Marie
ID - 1367
IS - 6
JF - Computer Graphics Forum
SN - 01677055
TI - Adaptive physically based models in computer graphics
VL - 36
ER -
TY - JOUR
AB - We consider the problem of computing the set of initial states of a dynamical system such that there exists a control strategy to ensure that the trajectories satisfy a temporal logic specification with probability 1 (almost-surely). We focus on discrete-time, stochastic linear dynamics and specifications given as formulas of the Generalized Reactivity(1) fragment of Linear Temporal Logic over linear predicates in the states of the system. We propose a solution based on iterative abstraction-refinement, and turn-based 2-player probabilistic games. While the theoretical guarantee of our algorithm after any finite number of iterations is only a partial solution, we show that if our algorithm terminates, then the result is the set of all satisfying initial states. Moreover, for any (partial) solution our algorithm synthesizes witness control strategies to ensure almost-sure satisfaction of the temporal logic specification. While the proposed algorithm guarantees progress and soundness in every iteration, it is computationally demanding. We offer an alternative, more efficient solution for the reachability properties that decomposes the problem into a series of smaller problems of the same type. All algorithms are demonstrated on an illustrative case study.
AU - Svoreňová, Mária
AU - Kretinsky, Jan
AU - Chmelik, Martin
AU - Chatterjee, Krishnendu
AU - Cěrná, Ivana
AU - Belta, Cǎlin
ID - 1407
IS - 2
JF - Nonlinear Analysis: Hybrid Systems
TI - Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games
VL - 23
ER -
TY - JOUR
AB - Phat is an open-source C. ++ library for the computation of persistent homology by matrix reduction, targeted towards developers of software for topological data analysis. We aim for a simple generic design that decouples algorithms from data structures without sacrificing efficiency or user-friendliness. We provide numerous different reduction strategies as well as data types to store and manipulate the boundary matrix. We compare the different combinations through extensive experimental evaluation and identify optimization techniques that work well in practical situations. We also compare our software with various other publicly available libraries for persistent homology.
AU - Bauer, Ulrich
AU - Kerber, Michael
AU - Reininghaus, Jan
AU - Wagner, Hubert
ID - 1433
JF - Journal of Symbolic Computation
SN - 07477171
TI - Phat - Persistent homology algorithms toolbox
VL - 78
ER -
TY - JOUR
AB - We consider N×N Hermitian random matrices H consisting of blocks of size M≥N6/7. The matrix elements are i.i.d. within the blocks, close to a Gaussian in the four moment matching sense, but their distribution varies from block to block to form a block-band structure, with an essential band width M. We show that the entries of the Green’s function G(z)=(H−z)−1 satisfy the local semicircle law with spectral parameter z=E+iη down to the real axis for any η≫N−1, using a combination of the supersymmetry method inspired by Shcherbina (J Stat Phys 155(3): 466–499, 2014) and the Green’s function comparison strategy. Previous estimates were valid only for η≫M−1. The new estimate also implies that the eigenvectors in the middle of the spectrum are fully delocalized.
AU - Bao, Zhigang
AU - Erdös, László
ID - 1528
IS - 3-4
JF - Probability Theory and Related Fields
SN - 01788051
TI - Delocalization for a class of random block band matrices
VL - 167
ER -
TY - CONF
AB - We study probabilistic models of natural images and extend the autoregressive family of PixelCNN models by incorporating latent variables. Subsequently, we describe two new generative image models that exploit different image transformations as latent variables: a quantized grayscale view of the image or a multi-resolution image pyramid. The proposed models tackle two known shortcomings of existing PixelCNN models: 1) their tendency to focus on low-level image details, while largely ignoring high-level image information, such as object shapes, and 2) their computationally costly procedure for image sampling. We experimentally demonstrate benefits of our LatentPixelCNN models, in particular showing that they produce much more realistically looking image samples than previous state-of-the-art probabilistic models.
AU - Kolesnikov, Alexander
AU - Lampert, Christoph
ID - 1000
SN - 978-151085514-4
TI - PixelCNN models with auxiliary variables for natural image modeling
VL - 70
ER -
TY - CONF
AB - We present a computational approach for designing CurveUps, curvy shells that form from an initially flat state. They consist of small rigid tiles that are tightly held together by two pre-stretched elastic sheets attached to them. Our method allows the realization of smooth, doubly curved surfaces that can be fabricated as a flat piece. Once released, the restoring forces of the pre-stretched sheets support the object to take shape in 3D. CurveUps are structurally stable in their target configuration. The design process starts with a target surface. Our method generates a tile layout in 2D and optimizes the distribution, shape, and attachment areas of the tiles to obtain a configuration that is fabricable and in which the curved up state closely matches the target. Our approach is based on an efficient approximate model and a local optimization strategy for an otherwise intractable nonlinear optimization problem. We demonstrate the effectiveness of our approach for a wide range of shapes, all realized as physical prototypes.
AU - Guseinov, Ruslan
AU - Miguel, Eder
AU - Bickel, Bernd
ID - 1001
IS - 4
TI - CurveUps: Shaping objects from flat plates with tension-actuated curvature
VL - 36
ER -
TY - CONF
AB - We present an interactive design system to create functional mechanical objects. Our computational approach allows novice users to retarget an existing mechanical template to a user-specified input shape. Our proposed representation for a mechanical template encodes a parameterized mechanism, mechanical constraints that ensure a physically valid configuration, spatial relationships of mechanical parts to the user-provided shape, and functional constraints that specify an intended functionality. We provide an intuitive interface and optimization-in-the-loop approach for finding a valid configuration of the mechanism and the shape to ensure that higher-level functional goals are met. Our algorithm interactively optimizes the mechanism while the user manipulates the placement of mechanical components and the shape. Our system allows users to efficiently explore various design choices and to synthesize customized mechanical objects that can be fabricated with rapid prototyping technologies. We demonstrate the efficacy of our approach by retargeting various mechanical templates to different shapes and fabricating the resulting functional mechanical objects.
AU - Zhang, Ran
AU - Auzinger, Thomas
AU - Ceylan, Duygu
AU - Li, Wilmot
AU - Bickel, Bernd
ID - 1002
IS - 4
SN - 07300301
TI - Functionality-aware retargeting of mechanisms to 3D shapes
VL - 36
ER -
TY - CONF
AB - Network games (NGs) are played on directed graphs and are extensively used in network design and analysis. Search problems for NGs include finding special strategy profiles such as a Nash equilibrium and a globally optimal solution. The networks modeled by NGs may be huge. In formal verification, abstraction has proven to be an extremely effective technique for reasoning about systems with big and even infinite state spaces. We describe an abstraction-refinement methodology for reasoning about NGs. Our methodology is based on an abstraction function that maps the state space of an NG to a much smaller state space. We search for a global optimum and a Nash equilibrium by reasoning on an under- and an overapproximation defined on top of this smaller state space. When the approximations are too coarse to find such profiles, we refine the abstraction function. Our experimental results demonstrate the efficiency of the methodology.
AU - Avni, Guy
AU - Guha, Shibashis
AU - Kupferman, Orna
ID - 1003
SN - 10450823
TI - An abstraction-refinement methodology for reasoning about network games
ER -
TY - JOUR
AB - The fundamental tasks of the root system are, besides anchoring, mediating interactions between plant and soil and providing the plant with water and nutrients. The architecture of the root system is controlled by endogenous mechanisms that constantly integrate environmental signals, such as availability of nutrients and water. Extremely important for efficient soil exploitation and survival under less favorable conditions is the developmental flexibility of the root system that is largely determined by its postembryonic branching capacity. Modulation of initiation and outgrowth of lateral roots provides roots with an exceptional plasticity, allows optimal adjustment to underground heterogeneity, and enables effective soil exploitation and use of resources. Here we discuss recent advances in understanding the molecular mechanisms that shape the plant root system and integrate external cues to adapt to the changing environment.
AU - Ötvös, Krisztina
AU - Benková, Eva
ID - 1004
JF - Current Opinion in Genetics & Development
SN - 0959437X
TI - Spatiotemporal mechanisms of root branching
VL - 45
ER -
TY - JOUR
AB - Background: The phenomenon of immune priming, i.e. enhanced protection following a secondary exposure to a pathogen, has now been demonstrated in a wide range of invertebrate species. Despite accumulating phenotypic evidence, knowledge of its mechanistic underpinnings is currently very limited. Here we used the system of the red flour beetle, Tribolium castaneum and the insect pathogen Bacillus thuringiensis (Bt) to further our molecular understanding of the oral immune priming phenomenon. We addressed how ingestion of bacterial cues (derived from spore supernatants) of an orally pathogenic and non-pathogenic Bt strain affects gene expression upon later challenge exposure, using a whole-transcriptome sequencing approach. Results: Whereas gene expression of individuals primed with the orally non-pathogenic strain showed minor changes to controls, we found that priming with the pathogenic strain induced regulation of a large set of distinct genes, many of which are known immune candidates. Intriguingly, the immune repertoire activated upon priming and subsequent challenge qualitatively differed from the one mounted upon infection with Bt without previous priming. Moreover, a large subset of priming-specific genes showed an inverse regulation compared to their regulation upon challenge only. Conclusions: Our data demonstrate that gene expression upon infection is strongly affected by previous immune priming. We hypothesise that this shift in gene expression indicates activation of a more targeted and efficient response towards a previously encountered pathogen, in anticipation of potential secondary encounter.
AU - Greenwood, Jenny
AU - Milutinovic, Barbara
AU - Peuß, Robert
AU - Behrens, Sarah
AU - Essar, Daniela
AU - Rosenstiel, Philip
AU - Schulenburg, Hinrich
AU - Kurtz, Joachim
ID - 1006
IS - 1
JF - BMC Genomics
SN - 14712164
TI - Oral immune priming with Bacillus thuringiensis induces a shift in the gene expression of Tribolium castaneum larvae
VL - 18
ER -
TY - JOUR
AB - A nonlinear system possesses an invariance with respect to a set of transformations if its output dynamics remain invariant when transforming the input, and adjusting the initial condition accordingly. Most research has focused on invariances with respect to time-independent pointwise transformations like translational-invariance (u(t) -> u(t) + p, p in R) or scale-invariance (u(t) -> pu(t), p in R>0). In this article, we introduce the concept of s0-invariances with respect to continuous input transformations exponentially growing/decaying over time. We show that s0-invariant systems not only encompass linear time-invariant (LTI) systems with transfer functions having an irreducible zero at s0 in R, but also that the input/output relationship of nonlinear s0-invariant systems possesses properties well known from their linear counterparts. Furthermore, we extend the concept of s0-invariances to second- and higher-order s0-invariances, corresponding to invariances with respect to transformations of the time-derivatives of the input, and encompassing LTI systems with zeros of multiplicity two or higher. Finally, we show that nth-order 0-invariant systems realize – under mild conditions – nth-order nonlinear differential operators: when excited by an input of a characteristic functional form, the system’s output converges to a constant value only depending on the nth (nonlinear) derivative of the input.
AU - Lang, Moritz
AU - Sontag, Eduardo
ID - 1007
JF - Automatica
SN - 00051098
TI - Zeros of nonlinear systems with input invariances
VL - 81C
ER -
TY - CONF
AB - A standard objective in partially-observable Markov decision processes (POMDPs) is to find a policy that maximizes the expected discounted-sum payoff. However, such policies may still permit unlikely but highly undesirable outcomes, which is problematic especially in safety-critical applications. Recently, there has been a surge of interest in POMDPs where the goal is to maximize the probability to ensure that the payoff is at least a given threshold, but these approaches do not consider any optimization beyond satisfying this threshold constraint. In this work we go beyond both the “expectation” and “threshold” approaches and consider a “guaranteed payoff optimization (GPO)” problem for POMDPs, where we are given a threshold t and the objective is to find a policy σ such that a) each possible outcome of σ yields a discounted-sum payoff of at least t, and b) the expected discounted-sum payoff of σ is optimal (or near-optimal) among all policies satisfying a). We present a practical approach to tackle the GPO problem and evaluate it on standard POMDP benchmarks.
AU - Chatterjee, Krishnendu
AU - Novotny, Petr
AU - Pérez, Guillermo
AU - Raskin, Jean
AU - Zikelic, Djordje
ID - 1009
T2 - Proceedings of the 31st AAAI Conference on Artificial Intelligence
TI - Optimizing expectation with guarantees in POMDPs
VL - 5
ER -
TY - JOUR
AB - We prove a local law in the bulk of the spectrum for random Gram matrices XX∗, a generalization of sample covariance matrices, where X is a large matrix with independent, centered entries with arbitrary variances. The limiting eigenvalue density that generalizes the Marchenko-Pastur law is determined by solving a system of nonlinear equations. Our entrywise and averaged local laws are on the optimal scale with the optimal error bounds. They hold both in the square case (hard edge) and in the properly rectangular case (soft edge). In the latter case we also establish a macroscopic gap away from zero in the spectrum of XX∗.
AU - Alt, Johannes
AU - Erdös, László
AU - Krüger, Torben H
ID - 1010
JF - Electronic Journal of Probability
SN - 10836489
TI - Local law for random Gram matrices
VL - 22
ER -
TY - CONF
AB - Pushdown systems (PDSs) and recursive state machines (RSMs), which are linearly equivalent, are standard models for interprocedural analysis. Yet RSMs are more convenient as they (a) explicitly model function calls and returns, and (b) specify many natural parameters for algorithmic analysis, e.g., the number of entries and exits. We consider a general framework where RSM transitions are labeled from a semiring and path properties are algebraic with semiring operations, which can model, e.g., interprocedural reachability and dataflow analysis problems. Our main contributions are new algorithms for several fundamental problems. As compared to a direct translation of RSMs to PDSs and the best-known existing bounds of PDSs, our analysis algorithm improves the complexity for finite-height semirings (that subsumes reachability and standard dataflow properties). We further consider the problem of extracting distance values from the representation structures computed by our algorithm, and give efficient algorithms that distinguish the complexity of a one-time preprocessing from the complexity of each individual query. Another advantage of our algorithm is that our improvements carry over to the concurrent setting, where we improve the bestknown complexity for the context-bounded analysis of concurrent RSMs. Finally, we provide a prototype implementation that gives a significant speed-up on several benchmarks from the SLAM/SDV project.
AU - Chatterjee, Krishnendu
AU - Kragl, Bernhard
AU - Mishra, Samarth
AU - Pavlogiannis, Andreas
ED - Yang, Hongseok
ID - 1011
SN - 03029743
TI - Faster algorithms for weighted recursive state machines
VL - 10201
ER -
TY - JOUR
AB - From microwave ovens to satellite television to the GPS and data services on our mobile phones, microwave technology is everywhere today. But one technology that has so far failed to prove its worth in this wavelength regime is quantum communication that uses the states of single photons as information carriers. This is because single microwave photons, as opposed to classical microwave signals, are extremely vulnerable to noise from thermal excitations in the channels through which they travel. Two new independent studies, one by Ze-Liang Xiang at Technische Universität Wien (Vienna), Austria, and colleagues [1] and another by Benoît Vermersch at the University of Innsbruck, also in Austria, and colleagues [2] now describe a theoretical protocol for microwave quantum communication that is resilient to thermal and other types of noise. Their approach could become a powerful technique to establish fast links between superconducting data processors in a future all-microwave quantum network.
AU - Fink, Johannes M
ID - 1013
IS - 32
JF - Physics
TI - Viewpoint: Microwave quantum states beat the heat
VL - 10
ER -
TY - JOUR
AB - Vortices are commonly observed in the context of classical hydrodynamics: from whirlpools after stirring the coffee in a cup to a violent atmospheric phenomenon such as a tornado, all classical vortices are characterized by an arbitrary circulation value of the local velocity field. On the other hand the appearance of vortices with quantized circulation represents one of the fundamental signatures of macroscopic quantum phenomena. In two-dimensional superfluids quantized vortices play a key role in determining finite-temperature properties, as the superfluid phase and the normal state are separated by a vortex unbinding transition, the Berezinskii-Kosterlitz-Thouless transition. Very recent experiments with two-dimensional superfluid fermions motivate the present work: we present theoretical results based on the renormalization group showing that the universal jump of the superfluid density and the critical temperature crucially depend on the interaction strength, providing a strong benchmark for forthcoming investigations.
AU - Bighin, Giacomo
AU - Salasnich, Luca
ID - 1015
JF - Scientific Reports
SN - 20452322
TI - Vortices and antivortices in two-dimensional ultracold Fermi gases
VL - 7
ER -
TY - JOUR
AB - The integrity and dynamic properties of the microtubule cytoskeleton are indispensable for the development of the mammalian brain. Consequently, mutations in the genes that encode the structural component (the α/β-tubulin heterodimer) can give rise to severe, sporadic neurodevelopmental disorders. These are commonly referred to as the tubulinopathies. Here we report the addition of recessive quadrupedalism, also known as Uner Tan syndrome (UTS), to the growing list of diseases caused by tubulin variants. Analysis of a consanguineous UTS family identified a biallelic TUBB2B mutation, resulting in a p.R390Q amino acid substitution. In addition to the identifying quadrupedal locomotion, all three patients showed severe cerebellar hypoplasia. None, however, displayed the basal ganglia malformations typically associated with TUBB2B mutations. Functional analysis of the R390Q substitution revealed that it did not affect the ability of β-tubulin to fold or become assembled into the α/β-heterodimer, nor did it influence the incorporation of mutant-containing heterodimers into microtubule polymers. The 390Q mutation in S. cerevisiae TUB2 did not affect growth under basal conditions, but did result in increased sensitivity to microtubule-depolymerizing drugs, indicative of a mild impact of this mutation on microtubule function. The TUBB2B mutation described here represents an unusual recessive mode of inheritance for missense-mediated tubulinopathies and reinforces the sensitivity of the developing cerebellum to microtubule defects.
AU - Breuss, Martin
AU - Nguyen, Thai
AU - Srivatsan, Anjana
AU - Leca, Ines
AU - Tian, Guoling
AU - Fritz, Tanja
AU - Hansen, Andi H
AU - Musaev, Damir
AU - Mcevoy Venneri, Jennifer
AU - Kiely, James
AU - Rosti, Rasim
AU - Scott, Eric
AU - Tan, Uner
AU - Kolodner, Richard
AU - Cowan, Nicholas
AU - Keays, David
AU - Gleeson, Joseph
ID - 1016
IS - 2
JF - Human Molecular Genetics
SN - 09646906
TI - Uner Tan syndrome caused by a homozygous TUBB2B mutation affecting microtubule stability
VL - 26
ER -
TY - JOUR
AB - The development of the vertebrate central nervous system is reliant on a complex cascade of biological processes that include mitotic division, relocation of migrating neurons, and the extension of dendritic and axonal processes. Each of these cellular events requires the diverse functional repertoire of the microtubule cytoskeleton for the generation of forces, assembly of macromolecular complexes and transport of molecules and organelles. The tubulins are a multi-gene family that encode for the constituents of microtubules, and have been implicated in a spectrum of neurological disorders. Evidence is building that different tubulins tune the functional properties of the microtubule cytoskeleton dependent on the cell type, developmental profile and subcellular localisation. Here we review of the origins of the functional specification of the tubulin gene family in the developing brain at a transcriptional, translational, and post-transcriptional level. We remind the reader that tubulins are not just loading controls for your average Western blot.
AU - Breuss, Martin
AU - Leca, Ines
AU - Gstrein, Thomas
AU - Hansen, Andi H
AU - Keays, David
ID - 1017
JF - Molecular and Cellular Neuroscience
SN - 10447431
TI - Tubulins and brain development: The origins of functional specification
VL - 84
ER -
TY - JOUR
AB - In plants, the multistep phosphorelay (MSP) pathway mediates a range of regulatory processes, including those activated by cytokinins. The crosstalk between cytokinin response and light is known for a long time. However, the molecular mechanism underlying the interactionbetween light and cytokinin signaling remains elusive. In the screen for upstream regulators we identified a LONG PALE HYPOCOTYL (LPH) gene whose activity is indispensable for spatiotemporally correct expression of CYTOKININ INDEPENDENT-1 (CKI1), encoding the constitutively active sensor histidine kinase that activates MSP signaling. lph is a new allele of HEME OXYGENASE 1 (HY1) which encodes the key protein in the biosynthesis of phytochromobilin, a cofactor of photoconvertiblephytochromes. Our analysis confirmed the light-dependent regulation oftheCKI1 expression pattern. We show that CKI1 expression is under the control of phytochrome A (phyA), functioning as a dual (both positive and negative) regulator of CKI1 expression, presumably via the phyA-regulated transcription factors PHYTOCHROME INTERACTING FACTOR 3 (PIF3) and CIRCADIAN CLOCK ASSOCIATED 1 (CCA1). Changes in CKI1 expression observed in lph/hy1-7 and phy mutants correlatewithmisregulation of MSP signaling, changedcytokinin sensitivity and developmental aberrations,previously shown to be associated with cytokinin and/or CKI1 action. Besides that, we demonstrate novel role of phyA-dependent CKI1 expression in the hypocotyl elongation and hook development during skotomorphogenesis. Based on these results, we propose that the light-dependent regulation of CKI1 provides a plausible mechanistic link underlying the well-known interaction between light- and cytokinin-controlled plant development.
AU - Dobisova, Tereza
AU - Hrdinova, Vendula
AU - Cuesta, Candela
AU - Michlickova, Sarka
AU - Urbankova, Ivana
AU - Hejatkova, Romana
AU - Zadnikova, Petra
AU - Pernisová, Markéta
AU - Benková, Eva
AU - Hejátko, Jan
ID - 1018
IS - 1
JF - Plant Physiology
TI - Light regulated expression of sensor histidine kinase CKI1 controls cytokinin related development
VL - 174
ER -
TY - JOUR
AB - As a consequence of its difference in copy number between males and females, the X chromosome is subject to unique evolutionary forces and gene regulatory mechanisms. Previous studies of Drosophila melanogaster have shown that the expression of X-linked, testis-specific reporter genes is suppressed in the male germline. However, it is not known whether this phenomenon is restricted to testis-expressed genes or if it is a more general property of genes with tissue-specific expression, which are also underrepresented on the X chromosome. To test this, we compared the expression of three tissue-specific reporter genes (ovary, accessory gland and Malpighian tubule) inserted at various autosomal and X-chromosomal locations. In contrast to testis-specific reporter genes, we found no reduction of X-linked expression in any of the other tissues. In accessory gland and Malpighian tubule, we detected higher expression of the X-linked reporter genes, which suggests that they are at least partially dosage compensated. We found no difference in the tissue-specificity of X-linked and autosomal reporter genes. These findings indicate that, in general, the X chromosome is not a detrimental environment for tissue-specific gene expression and that the suppression of X-linked expression is limited to the male germline.
AU - Argyridou, Eliza
AU - Huylmans, Ann K
AU - Königer, Annabella
AU - Parsch, John
ID - 1019
IS - 1
JF - Heredity
SN - 0018067X
TI - X-linkage is not a general inhibitor of tissue-specific gene expression in Drosophila melanogaster
VL - 119
ER -
TY - JOUR
AB - Cellulose is the most abundant biopolymer on Earth. Cellulose fibers, such as the one extracted form cotton or woodpulp, have been used by humankind for hundreds of years to make textiles and paper. Here we show how, by engineering light-matter interaction, we can optimize light scattering using exclusively cellulose nanocrystals. The produced material is sustainable, biocompatible, and when compared to ordinary microfiber-based paper, it shows enhanced scattering strength (×4), yielding a transport mean free path as low as 3.5 μm in the visible light range. The experimental results are in a good agreement with the theoretical predictions obtained with a diffusive model for light propagation.
AU - Caixeiro, Soraya
AU - Peruzzo, Matilda
AU - Onelli, Olimpia
AU - Vignolini, Silvia
AU - Sapienza, Riccardo
ID - 1020
IS - 9
JF - ACS Applied Materials and Interfaces
SN - 19448244
TI - Disordered cellulose based nanostructures for enhanced light scattering
VL - 9
ER -
TY - JOUR
AB - Most flows in nature and engineering are turbulent because of their large velocities and spatial scales. Laboratory experiments on rotating quasi-Keplerian flows, for which the angular velocity decreases radially but the angular momentum increases, are however laminar at Reynolds numbers exceeding one million. This is in apparent contradiction to direct numerical simulations showing that in these experiments turbulence transition is triggered by the axial boundaries. We here show numerically that as the Reynolds number increases, turbulence becomes progressively confined to the boundary layers and the flow in the bulk fully relaminarizes. Our findings support that turbulence is unlikely to occur in isothermal constant-density quasi-Keplerian flows.
AU - Lopez Alonso, Jose M
AU - Avila, Marc
ID - 1021
JF - Journal of Fluid Mechanics
SN - 00221120
TI - Boundary layer turbulence in experiments on quasi Keplerian flows
VL - 817
ER -