TY - JOUR
AB - Synaptic cell adhesion molecules are increasingly gaining attention for conferring specific properties to individual synapses. Netrin-G1 and netrin-G2 are trans-synaptic adhesion molecules that distribute on distinct axons, and their presence restricts the expression of their cognate receptors, NGL1 and NGL2, respectively, to specific subdendritic segments of target neurons. However, the neural circuits and functional roles of netrin-G isoform complexes remain unclear. Here, we use netrin-G-KO and NGL-KO mice to reveal that netrin-G1/NGL1 and netrin-G2/NGL2 interactions specify excitatory synapses in independent hippocampal pathways. In the hippocampal CA1 area, netrin-G1/NGL1 and netrin-G2/NGL2 were expressed in the temporoammonic and Schaffer collateral pathways, respectively. The lack of presynaptic netrin-Gs led to the dispersion of NGLs from postsynaptic membranes. In accord, netrin-G mutant synapses displayed opposing phenotypes in long-term and short-term plasticity through discrete biochemical pathways. The plasticity phenotypes in netrin-G-KOs were phenocopied in NGL-KOs, with a corresponding loss of netrin-Gs from presynaptic membranes. Our findings show that netrin-G/NGL interactions differentially control synaptic plasticity in distinct circuits via retrograde signaling mechanisms and explain how synaptic inputs are diversified to control neuronal activity.
AU - Matsukawa, Hiroshi
AU - Akiyoshi Nishimura, Sachiko
AU - Zhang, Qi
AU - Luján, Rafael
AU - Yamaguchi, Kazuhiko
AU - Goto, Hiromichi
AU - Yaguchi, Kunio
AU - Hashikawa, Tsutomu
AU - Sano, Chie
AU - Shigemoto, Ryuichi
AU - Nakashiba, Toshiaki
AU - Itohara, Shigeyoshi
ID - 2018
IS - 47
JF - Journal of Neuroscience
TI - Netrin-G/NGL complexes encode functional synaptic diversification
VL - 34
ER -
TY - JOUR
AB - We prove that the empirical density of states of quantum spin glasses on arbitrary graphs converges to a normal distribution as long as the maximal degree is negligible compared with the total number of edges. This extends the recent results of Keating et al. (2014) that were proved for graphs with bounded chromatic number and with symmetric coupling distribution. Furthermore, we generalise the result to arbitrary hypergraphs. We test the optimality of our condition on the maximal degree for p-uniform hypergraphs that correspond to p-spin glass Hamiltonians acting on n distinguishable spin- 1/2 particles. At the critical threshold p = n1/2 we find a sharp classical-quantum phase transition between the normal distribution and the Wigner semicircle law. The former is characteristic to classical systems with commuting variables, while the latter is a signature of noncommutative random matrix theory.
AU - Erdös, László
AU - Schröder, Dominik J
ID - 2019
IS - 3-4
JF - Mathematical Physics, Analysis and Geometry
TI - Phase transition in the density of states of quantum spin glasses
VL - 17
ER -
TY - JOUR
AB - The mammalian heart has long been considered a postmitotic organ, implying that the total number of cardiomyocytes is set at birth. Analysis of cell division in the mammalian heart is complicated by cardiomyocyte binucleation shortly after birth, which makes it challenging to interpret traditional assays of cell turnover [Laflamme MA, Murray CE (2011) Nature 473(7347):326–335; Bergmann O, et al. (2009) Science 324(5923):98–102]. An elegant multi-isotope imaging-mass spectrometry technique recently calculated the low, discrete rate of cardiomyocyte generation in mice [Senyo SE, et al. (2013) Nature 493(7432):433–436], yet our cellular-level understanding of postnatal cardiomyogenesis remains limited. Herein, we provide a new line of evidence for the differentiated α-myosin heavy chain-expressing cardiomyocyte as the cell of origin of postnatal cardiomyogenesis using the “mosaic analysis with double markers” mouse model. We show limited, life-long, symmetric division of cardiomyocytes as a rare event that is evident in utero but significantly diminishes after the first month of life in mice; daughter cardiomyocytes divide very seldom, which this study is the first to demonstrate, to our knowledge. Furthermore, ligation of the left anterior descending coronary artery, which causes a myocardial infarction in the mosaic analysis with double-marker mice, did not increase the rate of cardiomyocyte division above the basal level for up to 4 wk after the injury. The clonal analysis described here provides direct evidence of postnatal mammalian cardiomyogenesis.
AU - Ali, Shah
AU - Hippenmeyer, Simon
AU - Saadat, Lily
AU - Luo, Liqun
AU - Weissman, Irving
AU - Ardehali, Reza
ID - 2020
IS - 24
JF - PNAS
TI - Existing cardiomyocytes generate cardiomyocytes at a low rate after birth in mice
VL - 111
ER -
TY - JOUR
AB - Neurotrophins regulate diverse aspects of neuronal development and plasticity, but their precise in vivo functions during neural circuit assembly in the central brain remain unclear. We show that the neurotrophin receptor tropomyosin-related kinase C (TrkC) is required for dendritic growth and branching of mouse cerebellar Purkinje cells. Sparse TrkC knockout reduced dendrite complexity, but global Purkinje cell knockout had no effect. Removal of the TrkC ligand neurotrophin-3 (NT-3) from cerebellar granule cells, which provide major afferent input to developing Purkinje cell dendrites, rescued the dendrite defects caused by sparse TrkC disruption in Purkinje cells. Our data demonstrate that NT-3 from presynaptic neurons (granule cells) is required for TrkC-dependent competitive dendrite morphogenesis in postsynaptic neurons (Purkinje cells)—a previously unknown mechanism of neural circuit development.
AU - William, Joo
AU - Hippenmeyer, Simon
AU - Luo, Liqun
ID - 2021
IS - 6209
JF - Science
TI - Dendrite morphogenesis depends on relative levels of NT-3/TrkC signaling
VL - 346
ER -
TY - JOUR
AB - Radial glial progenitors (RGPs) are responsible for producing nearly all neocortical neurons. To gain insight into the patterns of RGP division and neuron production, we quantitatively analyzed excitatory neuron genesis in the mouse neocortex using Mosaic Analysis with Double Markers, which provides single-cell resolution of progenitor division patterns and potential in vivo. We found that RGPs progress through a coherent program in which their proliferative potential diminishes in a predictable manner. Upon entry into the neurogenic phase, individual RGPs produce ∼8–9 neurons distributed in both deep and superficial layers, indicating a unitary output in neuronal production. Removal of OTX1, a transcription factor transiently expressed in RGPs, results in both deep- and superficial-layer neuron loss and a reduction in neuronal unit size. Moreover, ∼1/6 of neurogenic RGPs proceed to produce glia. These results suggest that progenitor behavior and histogenesis in the mammalian neocortex conform to a remarkably orderly and deterministic program.
AU - Gao, Peng
AU - Postiglione, Maria P
AU - Krieger, Teresa
AU - Hernandez, Luisirene
AU - Wang, Chao
AU - Han, Zhi
AU - Streicher, Carmen
AU - Papusheva, Ekaterina
AU - Insolera, Ryan
AU - Chugh, Kritika
AU - Kodish, Oren
AU - Huang, Kun
AU - Simons, Benjamin
AU - Luo, Liqun
AU - Hippenmeyer, Simon
AU - Shi, Song
ID - 2022
IS - 4
JF - Cell
TI - Deterministic progenitor behavior and unitary production of neurons in the neocortex
VL - 159
ER -
TY - JOUR
AB - The yeast Rab5 homologue, Vps21p, is known to be involved both in the vacuolar protein sorting (VPS) pathway from the trans-Golgi network to the vacuole, and in the endocytic pathway from the plasma membrane to the vacuole. However, the intracellular location at which these two pathways converge remains unclear. In addition, the endocytic pathway is not completely blocked in yeast cells lacking all Rab5 genes, suggesting the existence of an unidentified route that bypasses the Rab5-dependent endocytic pathway. Here we show that convergence of the endocytic and VPS pathways occurs upstream of the requirement for Vps21p in these pathways. We also identify a previously unidentified endocytic pathway mediated by the AP-3 complex. Importantly, the AP-3-mediated pathway appears mostly intact in Rab5-disrupted cells, and thus works as an alternative route to the vacuole/lysosome. We propose that the endocytic traffic branches into two routes to reach the vacuole: a Rab5-dependent VPS pathway and a Rab5-independent AP-3-mediated pathway.
AU - Toshima, Junko
AU - Nishinoaki, Show
AU - Sato, Yoshifumi
AU - Yamamoto, Wataru
AU - Furukawa, Daiki
AU - Siekhaus, Daria E
AU - Sawaguchi, Akira
AU - Toshima, Jiro
ID - 2024
JF - Nature Communications
TI - Bifurcation of the endocytic pathway into Rab5-dependent and -independent transport to the vacuole
VL - 5
ER -
TY - CONF
AB - We present a tool for translating LTL formulae into deterministic ω-automata. It is the first tool that covers the whole LTL that does not use Safra’s determinization or any of its variants. This leads to smaller automata. There are several outputs of the tool: firstly, deterministic Rabin automata, which are the standard input for probabilistic model checking, e.g. for the probabilistic model-checker PRISM; secondly, deterministic generalized Rabin automata, which can also be used for probabilistic model checking and are sometimes by orders of magnitude smaller. We also link our tool to PRISM and show that this leads to a significant speed-up of probabilistic LTL model checking, especially with the generalized Rabin automata.
AU - Komárková, Zuzana
AU - Kretinsky, Jan
ED - Cassez, Franck
ED - Raskin, Jean-François
ID - 2026
T2 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
TI - Rabinizer 3: Safraless translation of ltl to small deterministic automata
VL - 8837
ER -
TY - CONF
AB - We present a general framework for applying machine-learning algorithms to the verification of Markov decision processes (MDPs). The primary goal of these techniques is to improve performance by avoiding an exhaustive exploration of the state space. Our framework focuses on probabilistic reachability, which is a core property for verification, and is illustrated through two distinct instantiations. The first assumes that full knowledge of the MDP is available, and performs a heuristic-driven partial exploration of the model, yielding precise lower and upper bounds on the required probability. The second tackles the case where we may only sample the MDP, and yields probabilistic guarantees, again in terms of both the lower and upper bounds, which provides efficient stopping criteria for the approximation. The latter is the first extension of statistical model checking for unbounded properties inMDPs. In contrast with other related techniques, our approach is not restricted to time-bounded (finite-horizon) or discounted properties, nor does it assume any particular properties of the MDP. We also show how our methods extend to LTL objectives. We present experimental results showing the performance of our framework on several examples.
AU - Brázdil, Tomáš
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Forejt, Vojtěch
AU - Kretinsky, Jan
AU - Kwiatkowska, Marta
AU - Parker, David
AU - Ujma, Mateusz
ED - Cassez, Franck
ED - Raskin, Jean-François
ID - 2027
T2 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
TI - Verification of markov decision processes using learning algorithms
VL - 8837
ER -
TY - JOUR
AB - Understanding the dynamics of noisy neurons remains an important challenge in neuroscience. Here, we describe a simple probabilistic model that accurately describes the firing behavior in a large class (type II) of neurons. To demonstrate the usefulness of this model, we show how it accurately predicts the interspike interval (ISI) distributions, bursting patterns and mean firing rates found by: (1) simulations of the classic Hodgkin-Huxley model with channel noise, (2) experimental data from squid giant axon with a noisy input current and (3) experimental data on noisy firing from a neuron within the suprachiasmatic nucleus (SCN). This simple model has 6 parameters, however, in some cases, two of these parameters are coupled and only 5 parameters account for much of the known behavior. From these parameters, many properties of spiking can be found through simple calculation. Thus, we show how the complex effects of noise can be understood through a simple and general probabilistic model.
AU - Bodova, Katarina
AU - Paydarfar, David
AU - Forger, Daniel
ID - 2028
JF - Journal of Theoretical Biology
TI - Characterizing spiking in noisy type II neurons
VL - 365
ER -
TY - JOUR
AB - Spin-wave theory is a key ingredient in our comprehension of quantum spin systems, and is used successfully for understanding a wide range of magnetic phenomena, including magnon condensation and stability of patterns in dipolar systems. Nevertheless, several decades of research failed to establish the validity of spin-wave theory rigorously, even for the simplest models of quantum spins. A rigorous justification of the method for the three-dimensional quantum Heisenberg ferromagnet at low temperatures is presented here. We derive sharp bounds on its free energy by combining a bosonic formulation of the model introduced by Holstein and Primakoff with probabilistic estimates and operator inequalities.
AU - Correggi, Michele
AU - Giuliani, Alessandro
AU - Seiringer, Robert
ID - 2029
IS - 2
JF - EPL
TI - Validity of spin-wave theory for the quantum Heisenberg model
VL - 108
ER -
TY - JOUR
AB - A puzzling property of synaptic transmission, originally established at the neuromuscular junction, is that the time course of transmitter release is independent of the extracellular Ca2+ concentration ([Ca2+]o), whereas the rate of release is highly [Ca2+]o-dependent. Here, we examine the time course of release at inhibitory basket cell-Purkinje cell synapses and show that it is independent of [Ca2+]o. Modeling of Ca2+-dependent transmitter release suggests that the invariant time course of release critically depends on tight coupling between Ca2+ channels and release sensors. Experiments with exogenous Ca2+ chelators reveal that channel-sensor coupling at basket cell-Purkinje cell synapses is very tight, with a mean distance of 10–20 nm. Thus, tight channel-sensor coupling provides a mechanistic explanation for the apparent [Ca2+]o independence of the time course of release.
AU - Arai, Itaru
AU - Jonas, Peter M
ID - 2031
JF - eLife
TI - Nanodomain coupling explains Ca^2+ independence of transmitter release time course at a fast central synapse
VL - 3
ER -
TY - JOUR
AB - As light-based control of fundamental signaling pathways is becoming a reality, the field of optogenetics is rapidly moving beyond neuroscience. We have recently developed receptor tyrosine kinases that are activated by light and control cell proliferation, epithelial–mesenchymal transition, and angiogenic sprouting—cell behaviors central to cancer progression.
AU - Inglés Prieto, Álvaro
AU - Gschaider-Reichhart, Eva
AU - Schelch, Karin
AU - Janovjak, Harald L
AU - Grusch, Michael
ID - 2032
IS - 4
JF - Molecular and Cellular Oncology
TI - The optogenetic promise for oncology: Episode I
VL - 1
ER -
TY - CONF
AB - The learning with privileged information setting has recently attracted a lot of attention within the machine learning community, as it allows the integration of additional knowledge into the training process of a classifier, even when this comes in the form of a data modality that is not available at test time. Here, we show that privileged information can naturally be treated as noise in the latent function of a Gaussian process classifier (GPC). That is, in contrast to the standard GPC setting, the latent function is not just a nuisance but a feature: it becomes a natural measure of confidence about the training data by modulating the slope of the GPC probit likelihood function. Extensive experiments on public datasets show that the proposed GPC method using privileged noise, called GPC+, improves over a standard GPC without privileged knowledge, and also over the current state-of-the-art SVM-based method, SVM+. Moreover, we show that advanced neural networks and deep learning methods can be compressed as privileged information.
AU - Hernandez Lobato, Daniel
AU - Sharmanska, Viktoriia
AU - Kersting, Kristian
AU - Lampert, Christoph
AU - Quadrianto, Novi
ID - 2033
IS - January
T2 - Advances in Neural Information Processing Systems
TI - Mind the nuisance: Gaussian process classification using privileged noise
VL - 1
ER -
TY - JOUR
AB - In rapidly changing environments, selection history may impact the dynamics of adaptation. Mutations selected in one environment may result in pleiotropic fitness trade-offs in subsequent novel environments, slowing the rates of adaptation. Epistatic interactions between mutations selected in sequential stressful environments may slow or accelerate subsequent rates of adaptation, depending on the nature of that interaction. We explored the dynamics of adaptation during sequential exposure to herbicides with different modes of action in Chlamydomonas reinhardtii. Evolution of resistance to two of the herbicides was largely independent of selection history. For carbetamide, previous adaptation to other herbicide modes of action positively impacted the likelihood of adaptation to this herbicide. Furthermore, while adaptation to all individual herbicides was associated with pleiotropic fitness costs in stress-free environments, we observed that accumulation of resistance mechanisms was accompanied by a reduction in overall fitness costs. We suggest that antagonistic epistasis may be a driving mechanism that enables populations to more readily adapt in novel environments. These findings highlight the potential for sequences of xenobiotics to facilitate the rapid evolution of multiple-drug and -pesticide resistance, as well as the potential for epistatic interactions between adaptive mutations to facilitate evolutionary rescue in rapidly changing environments.
AU - Lagator, Mato
AU - Colegrave, Nick
AU - Neve, Paul
ID - 2036
IS - 1794
JF - Proceedings of the Royal Society of London Series B Biological Sciences
TI - Selection history and epistatic interactions impact dynamics of adaptation to novel environmental stresses
VL - 281
ER -
TY - JOUR
AB - Recently, there has been an effort to add quantitative objectives to formal verification and synthesis. We introduce and investigate the extension of temporal logics with quantitative atomic assertions. At the heart of quantitative objectives lies the accumulation of values along a computation. It is often the accumulated sum, as with energy objectives, or the accumulated average, as with mean-payoff objectives. We investigate the extension of temporal logics with the prefix-accumulation assertions Sum(v) ≥ c and Avg(v) ≥ c, where v is a numeric (or Boolean) variable of the system, c is a constant rational number, and Sum(v) and Avg(v) denote the accumulated sum and average of the values of v from the beginning of the computation up to the current point in time. We also allow the path-accumulation assertions LimInfAvg(v) ≥ c and LimSupAvg(v) ≥ c, referring to the average value along an entire infinite computation. We study the border of decidability for such quantitative extensions of various temporal logics. In particular, we show that extending the fragment of CTL that has only the EX, EF, AX, and AG temporal modalities with both prefix-accumulation assertions, or extending LTL with both path-accumulation assertions, results in temporal logics whose model-checking problem is decidable. Moreover, the prefix-accumulation assertions may be generalized with "controlled accumulation," allowing, for example, to specify constraints on the average waiting time between a request and a grant. On the negative side, we show that this branching-time logic is, in a sense, the maximal logic with one or both of the prefix-accumulation assertions that permits a decidable model-checking procedure. Extending a temporal logic that has the EG or EU modalities, such as CTL or LTL, makes the problem undecidable.
AU - Boker, Udi
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Kupferman, Orna
ID - 2038
IS - 4
JF - ACM Transactions on Computational Logic (TOCL)
TI - Temporal specifications with accumulative values
VL - 15
ER -
TY - JOUR
AB - A fundamental question in biology is the following: what is the time scale that is needed for evolutionary innovations? There are many results that characterize single steps in terms of the fixation time of new mutants arising in populations of certain size and structure. But here we ask a different question, which is concerned with the much longer time scale of evolutionary trajectories: how long does it take for a population exploring a fitness landscape to find target sequences that encode new biological functions? Our key variable is the length, (Formula presented.) of the genetic sequence that undergoes adaptation. In computer science there is a crucial distinction between problems that require algorithms which take polynomial or exponential time. The latter are considered to be intractable. Here we develop a theoretical approach that allows us to estimate the time of evolution as function of (Formula presented.) We show that adaptation on many fitness landscapes takes time that is exponential in (Formula presented.) even if there are broad selection gradients and many targets uniformly distributed in sequence space. These negative results lead us to search for specific mechanisms that allow evolution to work on polynomial time scales. We study a regeneration process and show that it enables evolution to work in polynomial time.
AU - Chatterjee, Krishnendu
AU - Pavlogiannis, Andreas
AU - Adlam, Ben
AU - Nowak, Martin
ID - 2039
IS - 9
JF - PLoS Computational Biology
TI - The time scale of evolutionary innovation
VL - 10
ER -
TY - JOUR
AB - Development requires tissue growth as well as cell diversification. To address how these processes are coordinated, we analyzed the development of molecularly distinct domains of neural progenitors in the mouse and chick neural tube. We show that during development, these domains undergo changes in size that do not scale with changes in overall tissue size. Our data show that domain proportions are first established by opposing morphogen gradients and subsequently controlled by domain-specific regulation of differentiation rate but not differences in proliferation rate. Regulation of differentiation rate is key to maintaining domain proportions while accommodating both intra- and interspecies variations in size. Thus, the sequential control of progenitor specification and differentiation elaborates pattern without requiring that signaling gradients grow as tissues expand.
AU - Kicheva, Anna
AU - Bollenbach, Mark Tobias
AU - Ribeiro, Ana
AU - Pérez Valle, Helena
AU - Lovell Badge, Robin
AU - Episkopou, Vasso
AU - Briscoe, James
ID - 2040
IS - 6204
JF - Science
TI - Coordination of progenitor specification and growth in mouse and chick spinal cord
VL - 345
ER -
TY - JOUR
AB - The hippocampus mediates several higher brain functions, such as learning, memory, and spatial coding. The input region of the hippocampus, the dentate gyrus, plays a critical role in these processes. Several lines of evidence suggest that the dentate gyrus acts as a preprocessor of incoming information, preparing it for subsequent processing in CA3. For example, the dentate gyrus converts input from the entorhinal cortex, where cells have multiple spatial fields, into the spatially more specific place cell activity characteristic of the CA3 region. Furthermore, the dentate gyrus is involved in pattern separation, transforming relatively similar input patterns into substantially different output patterns. Finally, the dentate gyrus produces a very sparse coding scheme in which only a very small fraction of neurons are active at any one time.
AU - Jonas, Peter M
AU - Lisman, John
ID - 2041
JF - Frontiers in Neural Circuits
TI - Structure, function and plasticity of hippocampal dentate gyrus microcircuits
VL - 8
ER -
TY - JOUR
AB - Background: CRISPR is a microbial immune system likely to be involved in host-parasite coevolution. It functions using target sequences encoded by the bacterial genome, which interfere with invading nucleic acids using a homology-dependent system. The system also requires protospacer associated motifs (PAMs), short motifs close to the target sequence that are required for interference in CRISPR types I and II. Here, we investigate whether PAMs are depleted in phage genomes due to selection pressure to escape recognition.Results: To this end, we analyzed two data sets. Phages infecting all bacterial hosts were analyzed first, followed by a detailed analysis of phages infecting the genus Streptococcus, where PAMs are best understood. We use two different measures of motif underrepresentation that control for codon bias and the frequency of submotifs. We compare phages infecting species with a particular CRISPR type to those infecting species without that type. Since only known PAMs were investigated, the analysis is restricted to CRISPR types I-C and I-E and in Streptococcus to types I-C and II. We found evidence for PAM depletion in Streptococcus phages infecting hosts with CRISPR type I-C, in Vibrio phages infecting hosts with CRISPR type I-E and in Streptococcus thermopilus phages infecting hosts with type II-A, known as CRISPR3.Conclusions: The observed motif depletion in phages with hosts having CRISPR can be attributed to selection rather than to mutational bias, as mutational bias should affect the phages of all hosts. This observation implies that the CRISPR system has been efficient in the groups discussed here.
AU - Kupczok, Anne
AU - Bollback, Jonathan P
ID - 2042
IS - 1
JF - BMC Genomics
TI - Motif depletion in bacteriophages infecting hosts with CRISPR systems
VL - 15
ER -
TY - CONF
AB - Persistent homology is a popular and powerful tool for capturing topological features of data. Advances in algorithms for computing persistent homology have reduced the computation time drastically – as long as the algorithm does not exhaust the available memory. Following up on a recently presented parallel method for persistence computation on shared memory systems [1], we demonstrate that a simple adaption of the standard reduction algorithm leads to a variant for distributed systems. Our algorithmic design ensures that the data is distributed over the nodes without redundancy; this permits the computation of much larger instances than on a single machine. Moreover, we observe that the parallelism at least compensates for the overhead caused by communication between nodes, and often even speeds up the computation compared to sequential and even parallel shared memory algorithms. In our experiments, we were able to compute the persistent homology of filtrations with more than a billion (109) elements within seconds on a cluster with 32 nodes using less than 6GB of memory per node.
AU - Bauer, Ulrich
AU - Kerber, Michael
AU - Reininghaus, Jan
ED - McGeoch, Catherine
ED - Meyer, Ulrich
ID - 2043
T2 - Proceedings of the Workshop on Algorithm Engineering and Experiments
TI - Distributed computation of persistent homology
ER -
TY - CHAP
AB - We present a parallel algorithm for computing the persistent homology of a filtered chain complex. Our approach differs from the commonly used reduction algorithm by first computing persistence pairs within local chunks, then simplifying the unpaired columns, and finally applying standard reduction on the simplified matrix. The approach generalizes a technique by Günther et al., which uses discrete Morse Theory to compute persistence; we derive the same worst-case complexity bound in a more general context. The algorithm employs several practical optimization techniques, which are of independent interest. Our sequential implementation of the algorithm is competitive with state-of-the-art methods, and we further improve the performance through parallel computation.
AU - Bauer, Ulrich
AU - Kerber, Michael
AU - Reininghaus, Jan
ED - Bremer, Peer-Timo
ED - Hotz, Ingrid
ED - Pascucci, Valerio
ED - Peikert, Ronald
ID - 2044
T2 - Topological Methods in Data Analysis and Visualization III
TI - Clear and Compress: Computing Persistent Homology in Chunks
ER -
TY - CONF
AB - We introduce and study a new notion of enhanced chosen-ciphertext security (ECCA) for public-key encryption. Loosely speaking, in the ECCA security experiment, the decryption oracle provided to the adversary is augmented to return not only the output of the decryption algorithm on a queried ciphertext but also of a randomness-recovery algorithm associated to the scheme. Our results mainly concern the case where the randomness-recovery algorithm is efficient. We provide constructions of ECCA-secure encryption from adaptive trapdoor functions as defined by Kiltz et al. (EUROCRYPT 2010), resulting in ECCA encryption from standard number-theoretic assumptions. We then give two applications of ECCA-secure encryption: (1) We use it as a unifying concept in showing equivalence of adaptive trapdoor functions and tag-based adaptive trapdoor functions, resolving an open question of Kiltz et al. (2) We show that ECCA-secure encryption can be used to securely realize an approach to public-key encryption with non-interactive opening (PKENO) originally suggested by Damgård and Thorbek (EUROCRYPT 2007), resulting in new and practical PKENO schemes quite different from those in prior work. Our results demonstrate that ECCA security is of both practical and theoretical interest.
AU - Dachman Soled, Dana
AU - Fuchsbauer, Georg
AU - Mohassel, Payman
AU - O’Neill, Adam
ED - Krawczyk, Hugo
ID - 2045
T2 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
TI - Enhanced chosen-ciphertext security and applications
VL - 8383
ER -
TY - CONF
AB - We introduce policy-based signatures (PBS), where a signer can only sign messages conforming to some authority-specified policy. The main requirements are unforgeability and privacy, the latter meaning that signatures not reveal the policy. PBS offers value along two fronts: (1) On the practical side, they allow a corporation to control what messages its employees can sign under the corporate key. (2) On the theoretical side, they unify existing work, capturing other forms of signatures as special cases or allowing them to be easily built. Our work focuses on definitions of PBS, proofs that this challenging primitive is realizable for arbitrary policies, efficient constructions for specific policies, and a few representative applications.
AU - Bellare, Mihir
AU - Fuchsbauer, Georg
ED - Krawczyk, Hugo
ID - 2046
T2 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
TI - Policy-based signatures
VL - 8383
ER -
TY - CONF
AB - Following the publication of an attack on genome-wide association studies (GWAS) data proposed by Homer et al., considerable attention has been given to developing methods for releasing GWAS data in a privacy-preserving way. Here, we develop an end-to-end differentially private method for solving regression problems with convex penalty functions and selecting the penalty parameters by cross-validation. In particular, we focus on penalized logistic regression with elastic-net regularization, a method widely used to in GWAS analyses to identify disease-causing genes. We show how a differentially private procedure for penalized logistic regression with elastic-net regularization can be applied to the analysis of GWAS data and evaluate our method’s performance.
AU - Yu, Fei
AU - Rybar, Michal
AU - Uhler, Caroline
AU - Fienberg, Stephen
ED - Domingo Ferrer, Josep
ID - 2047
T2 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
TI - Differentially-private logistic regression for detecting multiple-SNP association in GWAS databases
VL - 8744
ER -
TY - JOUR
AB - The flow instability and further transition to turbulence in a toroidal pipe (torus) with curvature ratio (tube-to-coiling diameter) 0.049 is investigated experimentally. The flow inside the toroidal pipe is driven by a steel sphere fitted to the inner pipe diameter. The sphere is moved with constant azimuthal velocity from outside the torus by a moving magnet. The experiment is designed to investigate curved pipe flow by optical measurement techniques. Using stereoscopic particle image velocimetry, laser Doppler velocimetry and pressure drop measurements, the flow is measured for Reynolds numbers ranging from 1000 to 15 000. Time- and space-resolved velocity fields are obtained and analysed. The steady axisymmetric basic flow is strongly influenced by centrifugal effects. On an increase of the Reynolds number we find a sequence of bifurcations. For Re=4075±2% a supercritical bifurcation to an oscillatory flow is found in which waves travel in the streamwise direction with a phase velocity slightly faster than the mean flow. The oscillatory flow is superseded by a presumably quasi-periodic flow at a further increase of the Reynolds number before turbulence sets in. The results are found to be compatible, in general, with earlier experimental and numerical investigations on transition to turbulence in helical and curved pipes. However, important aspects of the bifurcation scenario differ considerably.
AU - Kühnen, Jakob
AU - Holzner, Markus
AU - Hof, Björn
AU - Kuhlmann, Hendrik
ID - 2050
JF - Journal of Fluid Mechanics
TI - Experimental investigation of transitional flow in a toroidal pipe
VL - 738
ER -
TY - CONF
AB - We show that the usual score function for conditional Markov networks can be written as the expectation over the scores of their spanning trees. We also show that a small random sample of these output trees can attain a significant fraction of the margin obtained by the complete graph and we provide conditions under which we can perform tractable inference. The experimental results confirm that practical learning is scalable to realistic datasets using this approach.
AU - Marchand, Mario
AU - Hongyu, Su
AU - Emilie Morvant
AU - Rousu, Juho
AU - Shawe-Taylor, John
ID - 2051
TI - Multilabel structured output learning with random spanning trees of max-margin Markov networks
ER -
TY - CONF
AB - A standard technique for solving the parameterized model checking problem is to reduce it to the classic model checking problem of finitely many finite-state systems. This work considers some of the theoretical power and limitations of this technique. We focus on concurrent systems in which processes communicate via pairwise rendezvous, as well as the special cases of disjunctive guards and token passing; specifications are expressed in indexed temporal logic without the next operator; and the underlying network topologies are generated by suitable Monadic Second Order Logic formulas and graph operations. First, we settle the exact computational complexity of the parameterized model checking problem for some of our concurrent systems, and establish new decidability results for others. Second, we consider the cases that model checking the parameterized system can be reduced to model checking some fixed number of processes, the number is known as a cutoff. We provide many cases for when such cutoffs can be computed, establish lower bounds on the size of such cutoffs, and identify cases where no cutoff exists. Third, we consider cases for which the parameterized system is equivalent to a single finite-state system (more precisely a Büchi word automaton), and establish tight bounds on the sizes of such automata.
AU - Aminof, Benjamin
AU - Kotek, Tomer
AU - Rubin, Sacha
AU - Spegni, Francesco
AU - Veith, Helmut
ED - Baldan, Paolo
ED - Gorla, Daniele
ID - 2052
T2 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
TI - Parameterized model checking of rendezvous systems
VL - 8704
ER -
TY - CONF
AB - In contrast to the usual understanding of probabilistic systems as stochastic processes, recently these systems have also been regarded as transformers of probabilities. In this paper, we give a natural definition of strong bisimulation for probabilistic systems corresponding to this view that treats probability distributions as first-class citizens. Our definition applies in the same way to discrete systems as well as to systems with uncountable state and action spaces. Several examples demonstrate that our definition refines the understanding of behavioural equivalences of probabilistic systems. In particular, it solves a longstanding open problem concerning the representation of memoryless continuous time by memoryfull continuous time. Finally, we give algorithms for computing this bisimulation not only for finite but also for classes of uncountably infinite systems.
AU - Hermanns, Holger
AU - Krčál, Jan
AU - Kretinsky, Jan
ED - Baldan, Paolo
ED - Gorla, Daniele
ID - 2053
T2 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
TI - Probabilistic bisimulation: Naturally on distributions
VL - 8704
ER -
TY - CONF
AB - We study two-player concurrent games on finite-state graphs played for an infinite number of rounds, where in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine the successor state. The objectives are ω-regular winning conditions specified as parity objectives. We consider the qualitative analysis problems: the computation of the almost-sure and limit-sure winning set of states, where player 1 can ensure to win with probability 1 and with probability arbitrarily close to 1, respectively. In general the almost-sure and limit-sure winning strategies require both infinite-memory as well as infinite-precision (to describe probabilities). While the qualitative analysis problem for concurrent parity games with infinite-memory, infinite-precision randomized strategies was studied before, we study the bounded-rationality problem for qualitative analysis of concurrent parity games, where the strategy set for player 1 is restricted to bounded-resource strategies. In terms of precision, strategies can be deterministic, uniform, finite-precision, or infinite-precision; and in terms of memory, strategies can be memoryless, finite-memory, or infinite-memory. We present a precise and complete characterization of the qualitative winning sets for all combinations of classes of strategies. In particular, we show that uniform memoryless strategies are as powerful as finite-precision infinite-memory strategies, and infinite-precision memoryless strategies are as powerful as infinite-precision finite-memory strategies. We show that the winning sets can be computed in (n2d+3) time, where n is the size of the game structure and 2d is the number of priorities (or colors), and our algorithms are symbolic. The membership problem of whether a state belongs to a winning set can be decided in NP ∩ coNP. Our symbolic algorithms are based on a characterization of the winning sets as μ-calculus formulas, however, our μ-calculus formulas are crucially different from the ones for concurrent parity games (without bounded rationality); and our memoryless witness strategy constructions are significantly different from the infinite-memory witness strategy constructions for concurrent parity games.
AU - Chatterjee, Krishnendu
ED - Baldan, Paolo
ED - Gorla, Daniele
ID - 2054
T2 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
TI - Qualitative concurrent parity games: Bounded rationality
VL - 8704
ER -
TY - JOUR
AB - We consider a continuous-time Markov chain (CTMC) whose state space is partitioned into aggregates, and each aggregate is assigned a probability measure. A sufficient condition for defining a CTMC over the aggregates is presented as a variant of weak lumpability, which also characterizes that the measure over the original process can be recovered from that of the aggregated one. We show how the applicability of de-aggregation depends on the initial distribution. The application section is devoted to illustrate how the developed theory aids in reducing CTMC models of biochemical systems particularly in connection to protein-protein interactions. We assume that the model is written by a biologist in form of site-graph-rewrite rules. Site-graph-rewrite rules compactly express that, often, only a local context of a protein (instead of a full molecular species) needs to be in a certain configuration in order to trigger a reaction event. This observation leads to suitable aggregate Markov chains with smaller state spaces, thereby providing sufficient reduction in computational complexity. This is further exemplified in two case studies: simple unbounded polymerization and early EGFR/insulin crosstalk.
AU - Ganguly, Arnab
AU - Petrov, Tatjana
AU - Koeppl, Heinz
ID - 2056
IS - 3
JF - Journal of Mathematical Biology
TI - Markov chain aggregation and its applications to combinatorial reaction networks
VL - 69
ER -
TY - CONF
AB - In the past few years, a lot of attention has been devoted to multimedia indexing by fusing multimodal informations. Two kinds of fusion schemes are generally considered: The early fusion and the late fusion. We focus on late classifier fusion, where one combines the scores of each modality at the decision level. To tackle this problem, we investigate a recent and elegant well-founded quadratic program named MinCq coming from the machine learning PAC-Bayesian theory. MinCq looks for the weighted combination, over a set of real-valued functions seen as voters, leading to the lowest misclassification rate, while maximizing the voters’ diversity. We propose an extension of MinCq tailored to multimedia indexing. Our method is based on an order-preserving pairwise loss adapted to ranking that allows us to improve Mean Averaged Precision measure while taking into account the diversity of the voters that we want to fuse. We provide evidence that this method is naturally adapted to late fusion procedures and confirm the good behavior of our approach on the challenging PASCAL VOC’07 benchmark.
AU - Morvant, Emilie
AU - Habrard, Amaury
AU - Ayache, Stéphane
ID - 2057
T2 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
TI - Majority vote of diverse classifiers for late fusion
VL - 8621
ER -
TY - CONF
AB - We present a method for smoothly blending between existing liquid animations. We introduce a semi-automatic method for matching two existing liquid animations, which we use to create new fluid motion that plausibly interpolates the input. Our contributions include a new space-time non-rigid iterative closest point algorithm that incorporates user guidance, a subsampling technique for efficient registration of meshes with millions of vertices, and a fast surface extraction algorithm that produces 3D triangle meshes from a 4D space-time surface. Our technique can be used to instantly create hundreds of new simulations, or to interactively explore complex parameter spaces. Our method is guaranteed to produce output that does not deviate from the input animations, and it generalizes to multiple dimensions. Because our method runs at interactive rates after the initial precomputation step, it has potential applications in games and training simulations.
AU - Raveendran, Karthik
AU - Wojtan, Christopher J
AU - Thuerey, Nils
AU - Türk, Greg
ID - 2058
IS - 4
T2 - ACM Transactions on Graphics
TI - Blending liquids
VL - 33
ER -
TY - JOUR
AB - Plant embryogenesis is regulated by differential distribution of the plant hormone auxin. However, the cells establishing these gradients during microspore embryogenesis remain to be identified. For the first time, we describe, using the DR5 or DR5rev reporter gene systems, the GFP- and GUS-based auxin biosensors to monitor auxin during Brassica napus androgenesis at cellular resolution in the initial stages. Our study provides evidence that the distribution of auxin changes during embryo development and depends on the temperature-inducible in vitro culture conditions. For this, microspores (mcs) were induced to embryogenesis by heat treatment and then subjected to genetic modification via Agrobacterium tumefaciens. The duration of high temperature treatment had a significant influence on auxin distribution in isolated and in vitro-cultured microspores and on microspore-derived embryo development. In the “mild” heat-treated (1 day at 32 °C) mcs, auxin localized in a polar way already at the uni-nucleate microspore, which was critical for the initiation of embryos with suspensor-like structure. Assuming a mean mcs radius of 20 μm, endogenous auxin content in a single cell corresponded to concentration of 1.01 μM. In mcs subjected to a prolonged heat (5 days at 32 °C), although auxin concentration increased dozen times, auxin polarization was set up at a few-celled pro-embryos without suspensor. Those embryos were enclosed in the outer wall called the exine. The exine rupture was accompanied by the auxin gradient polarization. Relative quantitative estimation of auxin, using time-lapse imaging, revealed that primordia possess up to 1.3-fold higher amounts than those found in the root apices of transgenic MDEs in the presence of exogenous auxin. Our results show, for the first time, which concentration of endogenous auxin coincides with the first cell division and how the high temperature interplays with auxin, by what affects delay early establishing microspore polarity. Moreover, we present how the local auxin accumulation demonstrates the apical–basal axis formation of the androgenic embryo and directs the axiality of the adult haploid plant.
AU - Dubas, Ewa
AU - Moravčíková, Jana
AU - Libantová, Jana
AU - Matušíková, Ildikó
AU - Benková, Eva
AU - Zur, Iwona
AU - Krzewska, Monika
ID - 2059
IS - 5
JF - Protoplasma
TI - The influence of heat stress on auxin distribution in transgenic B napus microspores and microspore derived embryos
VL - 251
ER -
TY - JOUR
AB - Development of cambium and its activity is important for our knowledge of the mechanism of secondary growth. Arabidopsis thaliana emerges as a good model plant for such a kind of study. Thus, this paper reports on cellular events taking place in the interfascicular regions of inflorescence stems of A. thaliana, leading to the development of interfascicular cambium from differentiated interfascicular parenchyma cells (IPC). These events are as follows: appearance of auxin accumulation, PIN1 gene expression, polar PIN1 protein localization in the basal plasma membrane and periclinal divisions. Distribution of auxin was observed to be higher in differentiating into cambium parenchyma cells compared to cells within the pith and cortex. Expression of PIN1 in IPC was always preceded by auxin accumulation. Basal localization of PIN1 was already established in the cells prior to their periclinal division. These cellular events initiated within parenchyma cells adjacent to the vascular bundles and successively extended from that point towards the middle region of the interfascicular area, located between neighboring vascular bundles. The final consequence of which was the closure of the cambial ring within the stem. Changes in the chemical composition of IPC walls were also detected and included changes of pectic epitopes, xyloglucans (XG) and extensins rich in hydroxyproline (HRGPs). In summary, results presented in this paper describe interfascicular cambium ontogenesis in terms of successive cellular events in the interfascicular regions of inflorescence stems of Arabidopsis.
AU - Mazur, Ewa
AU - Kurczyñska, Ewa
AU - Friml, Jiří
ID - 2061
IS - 5
JF - Protoplasma
TI - Cellular events during interfascicular cambium ontogenesis in inflorescence stems of Arabidopsis
VL - 251
ER -
TY - JOUR
AB - The success story of fast-spiking, parvalbumin-positive (PV+) GABAergic interneurons (GABA, γ-aminobutyric acid) in the mammalian central nervous system is noteworthy. In 1995, the properties of these interneurons were completely unknown. Twenty years later, thanks to the massive use of subcellular patch-clamp techniques, simultaneous multiple-cell recording, optogenetics, in vivo measurements, and computational approaches, our knowledge about PV+ interneurons became more extensive than for several types of pyramidal neurons. These findings have implications beyond the “small world” of basic research on GABAergic cells. For example, the results provide a first proof of principle that neuroscientists might be able to close the gaps between the molecular, cellular, network, and behavioral levels, representing one of the main challenges at the present time. Furthermore, the results may form the basis for PV+ interneurons as therapeutic targets for brain disease in the future. However, much needs to be learned about the basic function of these interneurons before clinical neuroscientists will be able to use PV+ interneurons for therapeutic purposes.
AU - Hu, Hua
AU - Gan, Jian
AU - Jonas, Peter M
ID - 2062
IS - 6196
JF - Science
TI - Fast-spiking parvalbumin^+ GABAergic interneurons: From cellular design to microcircuit function
VL - 345
ER -
TY - CONF
AB - We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems.We focus on qualitative properties forMDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability. We introduce a new simulation relation to capture the refinement relation ofMDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.We present an automated technique for assume-guarantee style reasoning for compositional analysis ofMDPs with qualitative properties by giving a counterexample guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Daca, Przemyslaw
ID - 2063
TI - CEGAR for qualitative analysis of probabilistic systems
VL - 8559
ER -
TY - JOUR
AB - We examined the synaptic structure, quantity, and distribution of α-amino-3-hydroxy-5-methylisoxazole-4-propionic acid (AMPA)- and N-methyl-D-aspartate (NMDA)-type glutamate receptors (AMPARs and NMDARs, respectively) in rat cochlear nuclei by a highly sensitive freeze-fracture replica labeling technique. Four excitatory synapses formed by two distinct inputs, auditory nerve (AN) and parallel fibers (PF), on different cell types were analyzed. These excitatory synapse types included AN synapses on bushy cells (AN-BC synapses) and fusiform cells (AN-FC synapses) and PF synapses on FC (PF-FC synapses) and cartwheel cell spines (PF-CwC synapses). Immunogold labeling revealed differences in synaptic structure as well as AMPAR and NMDAR number and/or density in both AN and PF synapses, indicating a target-dependent organization. The immunogold receptor labeling also identified differences in the synaptic organization of FCs based on AN or PF connections, indicating an input-dependent organization in FCs. Among the four excitatory synapse types, the AN-BC synapses were the smallest and had the most densely packed intramembrane particles (IMPs), whereas the PF-CwC synapses were the largest and had sparsely packed IMPs. All four synapse types showed positive correlations between the IMP-cluster area and the AMPAR number, indicating a common intrasynapse-type relationship for glutamatergic synapses. Immunogold particles for AMPARs were distributed over the entire area of individual AN synapses; PF synapses often showed synaptic areas devoid of labeling. The gold-labeling for NMDARs occurred in a mosaic fashion, with less positive correlations between the IMP-cluster area and the NMDAR number. Our observations reveal target- and input-dependent features in the structure, number, and organization of AMPARs and NMDARs in AN and PF synapses.
AU - Rubio, Maía
AU - Fukazawa, Yugo
AU - Kamasawa, Naomi
AU - Clarkson, Cheryl
AU - Molnár, Elek
AU - Shigemoto, Ryuichi
ID - 2064
IS - 18
JF - Journal of Comparative Neurology
TI - Target- and input-dependent organization of AMPA and NMDA receptors in synaptic connections of the cochlear nucleus
VL - 522
ER -
TY - CONF
AB - Spinning tops and yo-yos have long fascinated cultures around the world with their unexpected, graceful motions that seemingly elude gravity. We present an algorithm to generate designs for spinning objects by optimizing rotational dynamics properties. As input, the user provides a solid 3D model and a desired axis of rotation. Our approach then modifies the mass distribution such that the principal directions of the moment of inertia align with the target rotation frame. We augment the model by creating voids inside its volume, with interior fill represented by an adaptive multi-resolution vox-elization. The discrete voxel fill values are optimized using a continuous, nonlinear formulation. Further, we optimize for rotational stability by maximizing the dominant principal moment. We extend our technique to incorporate deformation and multiple materials for cases where internal voids alone are insufficient. Our method is well-suited for a variety of 3D printed models, ranging from characters to abstract shapes. We demonstrate tops and yo-yos that spin surprisingly stably despite their asymmetric appearance.
AU - Bac̈her, Moritz
AU - Whiting, Emily
AU - Bernd Bickel
AU - Sorkine-Hornung, Olga
ID - 2080
IS - 4
TI - Spin-It: Optimizing moment of inertia for spinnable objects
VL - 33
ER -
TY - CONF
AB - We propose an interactive, optimization-in-the-loop tool for designing inflatable structures. Given a target shape, the user draws a network of seams defining desired segment boundaries in 3D. Our method computes optimally-shaped flat panels for the segments, such that the inflated structure is as close as possible to the target while satisfying the desired seam positions. Our approach is underpinned by physics-based pattern optimization, accurate coarse-scale simulation using tension field theory, and a specialized constraint-optimization method. Our system is fast enough to warrant interactive exploration of different seam layouts, including internal connections, and their effects on the inflated shape. We demonstrate the resulting design process on a varied set of simulation examples, some of which we have fabricated, demonstrating excellent agreement with the design intent.
AU - Skouras, Mélina
AU - Thomaszewski, Bernhard
AU - Kaufmann, Peter
AU - Garg, Akash
AU - Bickel, Bernd
AU - Grinspun, Eitan
AU - Gross, Markus
ID - 2081
IS - 4
TI - Designing inflatable structures
VL - 33
ER -
TY - CONF
AB - NMAC is a mode of operation which turns a fixed input-length keyed hash function f into a variable input-length function. A practical single-key variant of NMAC called HMAC is a very popular and widely deployed message authentication code (MAC). Security proofs and attacks for NMAC can typically be lifted to HMAC. NMAC was introduced by Bellare, Canetti and Krawczyk [Crypto'96], who proved it to be a secure pseudorandom function (PRF), and thus also a MAC, assuming that (1) f is a PRF and (2) the function we get when cascading f is weakly collision-resistant. Unfortunately, HMAC is typically instantiated with cryptographic hash functions like MD5 or SHA-1 for which (2) has been found to be wrong. To restore the provable guarantees for NMAC, Bellare [Crypto'06] showed its security based solely on the assumption that f is a PRF, albeit via a non-uniform reduction. - Our first contribution is a simpler and uniform proof for this fact: If f is an ε-secure PRF (against q queries) and a δ-non-adaptively secure PRF (against q queries), then NMAC f is an (ε+ℓqδ)-secure PRF against q queries of length at most ℓ blocks each. - We then show that this ε+ℓqδ bound is basically tight. For the most interesting case where ℓqδ ≥ ε we prove this by constructing an f for which an attack with advantage ℓqδ exists. This also violates the bound O(ℓε) on the PRF-security of NMAC recently claimed by Koblitz and Menezes. - Finally, we analyze the PRF-security of a modification of NMAC called NI [An and Bellare, Crypto'99] that differs mainly by using a compression function with an additional keying input. This avoids the constant rekeying on multi-block messages in NMAC and allows for a security proof starting by the standard switch from a PRF to a random function, followed by an information-theoretic analysis. We carry out such an analysis, obtaining a tight ℓq2/2 c bound for this step, improving over the trivial bound of ℓ2q2/2c. The proof borrows combinatorial techniques originally developed for proving the security of CBC-MAC [Bellare et al., Crypto'05].
AU - Gazi, Peter
AU - Pietrzak, Krzysztof Z
AU - Rybar, Michal
ED - Garay, Juan
ED - Gennaro, Rosario
ID - 2082
IS - 1
TI - The exact PRF-security of NMAC and HMAC
VL - 8616
ER -
TY - JOUR
AB - Understanding the effects of sex and migration on adaptation to novel environments remains a key problem in evolutionary biology. Using a single-cell alga Chlamydomonas reinhardtii, we investigated how sex and migration affected rates of evolutionary rescue in a sink environment, and subsequent changes in fitness following evolutionary rescue. We show that sex and migration affect both the rate of evolutionary rescue and subsequent adaptation. However, their combined effects change as the populations adapt to a sink habitat. Both sex and migration independently increased rates of evolutionary rescue, but the effect of sex on subsequent fitness improvements, following initial rescue, changed with migration, as sex was beneficial in the absence of migration but constraining adaptation when combined with migration. These results suggest that sex and migration are beneficial during the initial stages of adaptation, but can become detrimental as the population adapts to its environment.
AU - Lagator, Mato
AU - Morgan, Andrew
AU - Neve, Paul
AU - Colegrave, Nick
ID - 2083
IS - 8
JF - Evolution
TI - Role of sex and migration in adaptation to sink environments
VL - 68
ER -
TY - JOUR
AB - Receptor tyrosine kinases (RTKs) are a large family of cell surface receptors that sense growth factors and hormones and regulate a variety of cell behaviours in health and disease. Contactless activation of RTKs with spatial and temporal precision is currently not feasible. Here, we generated RTKs that are insensitive to endogenous ligands but can be selectively activated by low-intensity blue light. We screened light-oxygen-voltage (LOV)-sensing domains for their ability to activate RTKs by light-activated dimerization. Incorporation of LOV domains found in aureochrome photoreceptors of stramenopiles resulted in robust activation of the fibroblast growth factor receptor 1 (FGFR1), epidermal growth factor receptor (EGFR) and rearranged during transfection (RET). In human cancer and endothelial cells, light induced cellular signalling with spatial and temporal precision. Furthermore, light faithfully mimicked complex mitogenic and morphogenic cell behaviour induced by growth factors. RTKs under optical control (Opto-RTKs) provide a powerful optogenetic approach to actuate cellular signals and manipulate cell behaviour.
AU - Grusch, Michael
AU - Schelch, Karin
AU - Riedler, Robert
AU - Gschaider-Reichhart, Eva
AU - Differ, Christopher
AU - Berger, Walter
AU - Inglés Prieto, Álvaro
AU - Janovjak, Harald L
ID - 2084
IS - 15
JF - EMBO Journal
TI - Spatio-temporally precise activation of engineered receptor tyrosine kinases by light
VL - 33
ER -
TY - JOUR
AB - Pathogens may gain a fitness advantage through manipulation of the behaviour of their hosts. Likewise, host behavioural changes can be a defence mechanism, counteracting the impact of pathogens on host fitness. We apply harmonic radar technology to characterize the impact of an emerging pathogen - Nosema ceranae (Microsporidia) - on honeybee (Apis mellifera) flight and orientation performance in the field. Honeybees are the most important commercial pollinators. Emerging diseases have been proposed to play a prominent role in colony decline, partly through sub-lethal behavioural manipulation of their hosts. We found that homing success was significantly reduced in diseased (65.8%) versus healthy foragers (92.5%). Although lost bees had significantly reduced continuous flight times and prolonged resting times, other flight characteristics and navigational abilities showed no significant difference between infected and non-infected bees. Our results suggest that infected bees express normal flight characteristics but are constrained in their homing ability, potentially compromising the colony by reducing its resource inputs, but also counteracting the intra-colony spread of infection. We provide the first high-resolution analysis of sub-lethal effects of an emerging disease on insect flight behaviour. The potential causes and the implications for both host and parasite are discussed.
AU - Wolf, Stephan
AU - Mcmahon, Dino
AU - Lim, Ka
AU - Pull, Christopher
AU - Clark, Suzanne
AU - Paxton, Robert
AU - Osborne, Juliet
ID - 2086
IS - 8
JF - PLoS One
TI - So near and yet so far: Harmonic radar reveals reduced homing ability of Nosema infected honeybees
VL - 9
ER -
TY - JOUR
AB - The facial performance of an individual is inherently rich in subtle deformation and timing details. Although these subtleties make the performance realistic and compelling, they often elude both motion capture and hand animation. We present a technique for adding fine-scale details and expressiveness to low-resolution art-directed facial performances, such as those created manually using a rig, via marker-based capture, by fitting a morphable model to a video, or through Kinect reconstruction using recent faceshift technology. We employ a high-resolution facial performance capture system to acquire a representative performance of an individual in which he or she explores the full range of facial expressiveness. From the captured data, our system extracts an expressiveness model that encodes subtle spatial and temporal deformation details specific to that particular individual. Once this model has been built, these details can be transferred to low-resolution art-directed performances. We demonstrate results on various forms of input; after our enhancement, the resulting animations exhibit the same nuances and fine spatial details as the captured performance, with optional temporal enhancement to match the dynamics of the actor. Finally, we show that our technique outperforms the current state-of-the-art in example-based facial animation.
AU - Bermano, Amit H
AU - Bradley, Derek J
AU - Beeler, Thabo
AU - Zund, Fabio
AU - Nowrouzezahrai, Derek
AU - Baran, Ilya
AU - Sorkine-Hornung, Olga
AU - Pfister, Hanspeter
AU - Sumner, Robert W
AU - Bernd Bickel
AU - Groß, Markus S
ID - 2115
IS - 2
JF - ACM Transactions on Graphics
TI - Facial performance enhancement using dynamic shape space analysis
VL - 33
ER -
TY - JOUR
AB - We study approximations to a class of vector-valued equations of Burgers type driven by a multiplicative space-time white noise. A solution theory for this class of equations has been developed recently in Probability Theory Related Fields by Hairer and Weber. The key idea was to use the theory of controlled rough paths to give definitions of weak/mild solutions and to set up a Picard iteration argument. In this article the limiting behavior of a rather large class of (spatial) approximations to these equations is studied. These approximations are shown to converge and convergence rates are given, but the limit may depend on the particular choice of approximation. This effect is a spatial analogue to the Itô-Stratonovich correction in the theory of stochastic ordinary differential equations, where it is well known that different approximation schemes may converge to different solutions.
AU - Hairer, Martin M
AU - Jan Maas
AU - Weber, Hendrik
ID - 2131
IS - 5
JF - Communications on Pure and Applied Mathematics
TI - Approximating Rough Stochastic PDEs
VL - 67
ER -
TY - JOUR
AB - We consider discrete porous medium equations of the form ∂tρt=Δϕ(ρt), where Δ is the generator of a reversible continuous time Markov chain on a finite set χ, and ϕ is an increasing function. We show that these equations arise as gradient flows of certain entropy functionals with respect to suitable non-local transportation metrics. This may be seen as a discrete analogue of the Wasserstein gradient flow structure for porous medium equations in ℝn discovered by Otto. We present a one-dimensional counterexample to geodesic convexity and discuss Gromov-Hausdorff convergence to the Wasserstein metric.
AU - Erbar, Matthias
AU - Jan Maas
ID - 2132
IS - 4
JF - Discrete and Continuous Dynamical Systems- Series A
TI - Gradient flow structures for discrete porous medium equations
VL - 34
ER -
TY - JOUR
AB - Let ℭ denote the Clifford algebra over ℝ𝑛, which is the von Neumann algebra generated by n self-adjoint operators Q j , j = 1,…,n satisfying the canonical anticommutation relations, Q i Q j + Q j Q i = 2δ ij I, and let τ denote the normalized trace on ℭ. This algebra arises in quantum mechanics as the algebra of observables generated by n fermionic degrees of freedom. Let 𝔓 denote the set of all positive operators 𝜌∈ℭ such that τ(ρ) = 1; these are the non-commutative analogs of probability densities in the non-commutative probability space (ℭ,𝜏). The fermionic Fokker–Planck equation is a quantum-mechanical analog of the classical Fokker–Planck equation with which it has much in common, such as the same optimal hypercontractivity properties. In this paper we construct a Riemannian metric on 𝔓 that we show to be a natural analog of the classical 2-Wasserstein metric, and we show that, in analogy with the classical case, the fermionic Fokker–Planck equation is gradient flow in this metric for the relative entropy with respect to the ground state. We derive a number of consequences of this, such as a sharp Talagrand inequality for this metric, and we prove a number of results pertaining to this metric. Several open problems are raised.
AU - Carlen, Eric
AU - Maas, Jan
ID - 2133
IS - 3
JF - Communications in Mathematical Physics
TI - An analog of the 2-Wasserstein metric in non-commutative probability under which the fermionic Fokker-Planck equation is gradient flow for the entropy
VL - 331
ER -
TY - JOUR
AB - We propose a technique for engineering momentum-dependent dissipation in Bose-Einstein condensates with non-local interactions. The scheme relies on the use of momentum-dependent dark-states in close analogy to velocity-selective coherent population trapping. During the short-time dissipative dynamics, the system is driven into a particular finite-momentum phonon mode, which in real space corresponds to an ordered structure with non-local density-density correlations. Dissipation-induced ordering can be observed and studied in present-day experiments using cold atoms with dipole-dipole or off-resonant Rydberg interactions. Due to its dissipative nature, the ordering does not require artificial breaking of translational symmetry by an opticallattice or harmonic trap. This opens up a perspective of direct cooling of quantum gases into strongly-interacting phases.
AU - Otterbach, Johannes
AU - Lemeshko, Mikhail
ID - 2140
IS - 7
JF - Physical Review Letters
TI - Dissipative preparation of spatial order in Rydberg-dressed Bose-Einstein condensates
VL - 113
ER -
TY - JOUR
AB - The computation of the winning set for Büchi objectives in alternating games on graphs is a central problem in computer-aided verification with a large number of applications. The long-standing best known upper bound for solving the problem is Õ(n ⋅ m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the Õ(n ⋅ m) boundary by presenting a new technique that reduces the running time to O(n2). This bound also leads to O(n2)-time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of Õ(n ⋅ m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n3)), and (3) in Markov decision processes (improving for m>n4/3 an earlier bound of O(m ⋅ √m)). We then show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. Our algorithms are the first dynamic algorithms for this problem. We then consider another core graph theoretic problem in verification of probabilistic systems, namely computing the maximal end-component decomposition of a graph. We present two improved static algorithms for the maximal end-component decomposition problem. Our first algorithm is an O(m ⋅ √m)-time algorithm, and our second algorithm is an O(n2)-time algorithm which is obtained using the same technique as for alternating Büchi games. Thus, we obtain an O(min &lcu;m ⋅ √m,n2})-time algorithm improving the long-standing O(n ⋅ m) time bound. Finally, we show how to maintain the maximal end-component decomposition of a graph under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per edge deletion, and O(m) worst-case time per edge insertion. Again, our algorithms are the first dynamic algorithms for this problem.
AU - Chatterjee, Krishnendu
AU - Henzinger, Monika
ID - 2141
IS - 3
JF - Journal of the ACM
TI - Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition
VL - 61
ER -
TY - CONF
AB - We define a simple, explicit map sending a morphism f : M → N of pointwise finite dimensional persistence modules to a matching between the barcodes of M and N. Our main result is that, in a precise sense, the quality of this matching is tightly controlled by the lengths of the longest intervals in the barcodes of ker f and coker f . As an immediate corollary, we obtain a new proof of the algebraic stability theorem for persistence barcodes [5, 9], a fundamental result in the theory of persistent homology. In contrast to previous proofs, ours shows explicitly how a δ-interleaving morphism between two persistence modules induces a δ-matching between the barcodes of the two modules. Our main result also specializes to a structure theorem for submodules and quotients of persistence modules. Copyright is held by the owner/author(s).
AU - Bauer, Ulrich
AU - Lesnick, Michael
ID - 2153
T2 - Proceedings of the Annual Symposium on Computational Geometry
TI - Induced matchings of barcodes and the algebraic stability of persistence
ER -