@article{6419, abstract = {Characterizing the fitness landscape, a representation of fitness for a large set of genotypes, is key to understanding how genetic information is interpreted to create functional organisms. Here we determined the evolutionarily-relevant segment of the fitness landscape of His3, a gene coding for an enzyme in the histidine synthesis pathway, focusing on combinations of amino acid states found at orthologous sites of extant species. Just 15% of amino acids found in yeast His3 orthologues were always neutral while the impact on fitness of the remaining 85% depended on the genetic background. Furthermore, at 67% of sites, amino acid replacements were under sign epistasis, having both strongly positive and negative effect in different genetic backgrounds. 46% of sites were under reciprocal sign epistasis. The fitness impact of amino acid replacements was influenced by only a few genetic backgrounds but involved interaction of multiple sites, shaping a rugged fitness landscape in which many of the shortest paths between highly fit genotypes are inaccessible.}, author = {Pokusaeva, Victoria and Usmanova, Dinara R. and Putintseva, Ekaterina V. and Espinar, Lorena and Sarkisyan, Karen and Mishin, Alexander S. and Bogatyreva, Natalya S. and Ivankov, Dmitry and Akopyan, Arseniy and Avvakumov, Sergey and Povolotskaya, Inna S. and Filion, Guillaume J. and Carey, Lucas B. and Kondrashov, Fyodor}, issn = {15537404}, journal = {PLoS Genetics}, number = {4}, publisher = {Public Library of Science}, title = {{An experimental assay of the interactions of amino acids from orthologous sequences shaping a complex fitness landscape}}, doi = {10.1371/journal.pgen.1008079}, volume = {15}, year = {2019}, } @inproceedings{6428, abstract = {Safety and security are major concerns in the development of Cyber-Physical Systems (CPS). Signal temporal logic (STL) was proposedas a language to specify and monitor the correctness of CPS relativeto formalized requirements. Incorporating STL into a developmentprocess enables designers to automatically monitor and diagnosetraces, compute robustness estimates based on requirements, andperform requirement falsification, leading to productivity gains inverification and validation activities; however, in its current formSTL is agnostic to the input/output classification of signals, andthis negatively impacts the relevance of the analysis results.In this paper we propose to make the interface explicit in theSTL language by introducing input/output signal declarations. Wethen define new measures of input vacuity and output robustnessthat better reflect the nature of the system and the specification in-tent. The resulting framework, which we call interface-aware signaltemporal logic (IA-STL), aids verification and validation activities.We demonstrate the benefits of IA-STL on several CPS analysisactivities: (1) robustness-driven sensitivity analysis, (2) falsificationand (3) fault localization. We describe an implementation of our en-hancement to STL and associated notions of robustness and vacuityin a prototype extension of Breach, a MATLAB®/Simulink®toolboxfor CPS verification and validation. We explore these methodologi-cal improvements and evaluate our results on two examples fromthe automotive domain: a benchmark powertrain control systemand a hydrogen fuel cell system.}, author = {Ferrere, Thomas and Nickovic, Dejan and Donzé, Alexandre and Ito, Hisahiro and Kapinski, James}, booktitle = {Proceedings of the 2019 22nd ACM International Conference on Hybrid Systems: Computation and Control}, isbn = {9781450362825}, location = {Montreal, Canada}, pages = {57--66}, publisher = {ACM}, title = {{Interface-aware signal temporal logic}}, doi = {10.1145/3302504.3311800}, year = {2019}, } @inproceedings{6430, abstract = {A proxy re-encryption (PRE) scheme is a public-key encryption scheme that allows the holder of a key pk to derive a re-encryption key for any other key 𝑝𝑘′. This re-encryption key lets anyone transform ciphertexts under pk into ciphertexts under 𝑝𝑘′ without having to know the underlying message, while transformations from 𝑝𝑘′ to pk should not be possible (unidirectional). Security is defined in a multi-user setting against an adversary that gets the users’ public keys and can ask for re-encryption keys and can corrupt users by requesting their secret keys. Any ciphertext that the adversary cannot trivially decrypt given the obtained secret and re-encryption keys should be secure. All existing security proofs for PRE only show selective security, where the adversary must first declare the users it wants to corrupt. This can be lifted to more meaningful adaptive security by guessing the set of corrupted users among the n users, which loses a factor exponential in Open image in new window , rendering the result meaningless already for moderate Open image in new window . Jafargholi et al. (CRYPTO’17) proposed a framework that in some cases allows to give adaptive security proofs for schemes which were previously only known to be selectively secure, while avoiding the exponential loss that results from guessing the adaptive choices made by an adversary. We apply their framework to PREs that satisfy some natural additional properties. Concretely, we give a more fine-grained reduction for several unidirectional PREs, proving adaptive security at a much smaller loss. The loss depends on the graph of users whose edges represent the re-encryption keys queried by the adversary. For trees and chains the loss is quasi-polynomial in the size and for general graphs it is exponential in their depth and indegree (instead of their size as for previous reductions). Fortunately, trees and low-depth graphs cover many, if not most, interesting applications. Our results apply e.g. to the bilinear-map based PRE schemes by Ateniese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme (STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14).}, author = {Fuchsbauer, Georg and Kamath Hosdurg, Chethan and Klein, Karen and Pietrzak, Krzysztof Z}, isbn = {9783030172589}, issn = {16113349}, location = {Beijing, China}, pages = {317--346}, publisher = {Springer Nature}, title = {{Adaptively secure proxy re-encryption}}, doi = {10.1007/978-3-030-17259-6_11}, volume = {11443}, year = {2019}, } @phdthesis{6435, abstract = {Social insect colonies tend to have numerous members which function together like a single organism in such harmony that the term ``super-organism'' is often used. In this analogy the reproductive caste is analogous to the primordial germ cells of a metazoan, while the sterile worker caste corresponds to somatic cells. The worker castes, like tissues, are in charge of all functions of a living being, besides reproduction. The establishment of new super-organismal units (i.e. new colonies) is accomplished by the co-dependent castes. The term oftentimes goes beyond a metaphor. We invoke it when we speak about the metabolic rate, thermoregulation, nutrient regulation and gas exchange of a social insect colony. Furthermore, we assert that the super-organism has an immune system, and benefits from ``social immunity''. Social immunity was first summoned by evolutionary biologists to resolve the apparent discrepancy between the expected high frequency of disease outbreak amongst numerous, closely related tightly-interacting hosts, living in stable and microbially-rich environments, against the exceptionally scarce epidemic accounts in natural populations. Social immunity comprises a multi-layer assembly of behaviours which have evolved to effectively keep the pathogenic enemies of a colony at bay. The field of social immunity has drawn interest, as it becomes increasingly urgent to stop the collapse of pollinator species and curb the growth of invasive pests. In the past decade, several mechanisms of social immune responses have been dissected, but many more questions remain open. I present my work in two experimental chapters. In the first, I use invasive garden ants (*Lasius neglectus*) to study how pathogen load and its distribution among nestmates affect the grooming response of the group. Any given group of ants will carry out the same total grooming work, but will direct their grooming effort towards individuals carrying a relatively higher spore load. Contrary to expectation, the highest risk of transmission does not stem from grooming highly contaminated ants, but instead, we suggest that the grooming response likely minimizes spore loss to the environment, reducing contamination from inadvertent pickup from the substrate. The second is a comparative developmental approach. I follow black garden ant queens (*Lasius niger*) and their colonies from mating flight, through hibernation for a year. Colonies which grow fast from the start, have a lower chance of survival through hibernation, and those which survive grow at a lower pace later. This is true for colonies of naive and challenged queens. Early pathogen exposure of the queens changes colony dynamics in an unexpected way: colonies from exposed queens are more likely to grow slowly and recover in numbers only after they survive hibernation. In addition to the two experimental chapters, this thesis includes a co-authored published review on organisational immunity, where we enlist the experimental evidence and theoretical framework on which this hypothesis is built, identify the caveats and underline how the field is ripe to overcome them. In a final chapter, I describe my part in two collaborative efforts, one to develop an image-based tracker, and the second to develop a classifier for ant behaviour.}, author = {Casillas Perez, Barbara E}, issn = {2663-337X}, keywords = {Social Immunity, Sanitary care, Social Insects, Organisational Immunity, Colony development, Multi-target tracking}, pages = {183}, publisher = {Institute of Science and Technology Austria}, title = {{Collective defenses of garden ants against a fungal pathogen}}, doi = {10.15479/AT:ISTA:6435}, year = {2019}, } @article{6442, abstract = {This paper investigates the use of fundamental solutions for animating detailed linear water surface waves. We first propose an analytical solution for efficiently animating circular ripples in closed form. We then show how to adapt the method of fundamental solutions (MFS) to create ambient waves interacting with complex obstacles. Subsequently, we present a novel wavelet-based discretization which outperforms the state of the art MFS approach for simulating time-varying water surface waves with moving obstacles. Our results feature high-resolution spatial details, interactions with complex boundaries, and large open ocean domains. Our method compares favorably with previous work as well as known analytical solutions. We also present comparisons between our method and real world examples.}, author = {Schreck, Camille and Hafner, Christian and Wojtan, Christopher J}, journal = {ACM Transactions on Graphics}, number = {4}, publisher = {ACM}, title = {{Fundamental solutions for water wave animation}}, doi = {10.1145/3306346.3323002}, volume = {38}, year = {2019}, } @article{6451, abstract = {Epidermal growth factor receptor (EGFR) signaling controls skin development and homeostasis inmice and humans, and its deficiency causes severe skin inflammation, which might affect epidermalstem cell behavior. Here, we describe the inflammation-independent effects of EGFR deficiency dur-ing skin morphogenesis and in adult hair follicle stem cells. Expression and alternative splicing analysisof RNA sequencing data from interfollicular epidermis and outer root sheath indicate that EGFR con-trols genes involved in epidermal differentiation and also in centrosome function, DNA damage, cellcycle, and apoptosis. Genetic experiments employingp53deletion in EGFR-deficient epidermis revealthat EGFR signaling exhibitsp53-dependent functions in proliferative epidermal compartments, aswell asp53-independent functions in differentiated hair shaft keratinocytes. Loss of EGFR leads toabsence of LEF1 protein specifically in the innermost epithelial hair layers, resulting in disorganizationof medulla cells. Thus, our results uncover important spatial and temporal features of cell-autonomousEGFR functions in the epidermis.}, author = {Amberg, Nicole and Sotiropoulou, Panagiota A. and Heller, Gerwin and Lichtenberger, Beate M. and Holcmann, Martin and Camurdanoglu, Bahar and Baykuscheva-Gentscheva, Temenuschka and Blanpain, Cedric and Sibilia, Maria}, issn = {2589-0042}, journal = {iScience}, pages = {243--256}, publisher = {Elsevier}, title = {{EGFR controls hair shaft differentiation in a p53-independent manner}}, doi = {10.1016/j.isci.2019.04.018}, volume = {15}, year = {2019}, } @article{6454, abstract = {Adult neural stem cells and multiciliated ependymalcells are glial cells essential for neurological func-tions. Together, they make up the adult neurogenicniche. Using both high-throughput clonal analysisand single-cell resolution of progenitor division pat-terns and fate, we show that these two componentsof the neurogenic niche are lineally related: adult neu-ral stem cells are sister cells to ependymal cells,whereas most ependymal cells arise from the termi-nal symmetric divisions of the lineage. Unexpectedly,we found that the antagonist regulators of DNA repli-cation, GemC1 and Geminin, can tune the proportionof neural stem cells and ependymal cells. Our find-ings reveal the controlled dynamic of the neurogenicniche ontogeny and identify the Geminin familymembers as key regulators of the initial pool of adultneural stem cells.}, author = {Ortiz-Álvarez, G and Daclin, M and Shihavuddin, A and Lansade, P and Fortoul, A and Faucourt, M and Clavreul, S and Lalioti, ME and Taraviras, S and Hippenmeyer, Simon and Livet, J and Meunier, A and Genovesio, A and Spassky, N}, issn = {1097-4199}, journal = {Neuron}, number = {1}, pages = {159--172.e7}, publisher = {Elsevier}, title = {{Adult neural stem cells and multiciliated ependymal cells share a common lineage regulated by the Geminin family members}}, doi = {10.1016/j.neuron.2019.01.051}, volume = {102}, year = {2019}, } @article{6455, abstract = {During corticogenesis, distinct subtypes of neurons are sequentially born from ventricular zone progenitors. How these cells are molecularly temporally patterned is poorly understood. We used single-cell RNA sequencing at high temporal resolution to trace the lineage of the molecular identities of successive generations of apical progenitors (APs) and their daughter neurons in mouse embryos. We identified a core set of evolutionarily conserved, temporally patterned genes that drive APs from internally driven to more exteroceptive states. We found that the Polycomb repressor complex 2 (PRC2) epigenetically regulates AP temporal progression. Embryonic age–dependent AP molecular states are transmitted to their progeny as successive ground states, onto which essentially conserved early postmitotic differentiation programs are applied, and are complemented by later-occurring environment-dependent signals. Thus, epigenetically regulated temporal molecular birthmarks present in progenitors act in their postmitotic progeny to seed adult neuronal diversity.}, author = {Telley, L and Agirman, G and Prados, J and Amberg, Nicole and Fièvre, S and Oberst, P and Bartolini, G and Vitali, I and Cadilhac, C and Hippenmeyer, Simon and Nguyen, L and Dayer, A and Jabaudon, D}, issn = {1095-9203}, journal = {Science}, number = {6440}, publisher = {AAAS}, title = {{Temporal patterning of apical progenitors and their daughter neurons in the developing neocortex}}, doi = {10.1126/science.aav2522}, volume = {364}, year = {2019}, } @inproceedings{6462, abstract = {A controller is a device that interacts with a plant. At each time point,it reads the plant’s state and issues commands with the goal that the plant oper-ates optimally. Constructing optimal controllers is a fundamental and challengingproblem. Machine learning techniques have recently been successfully applied totrain controllers, yet they have limitations. Learned controllers are monolithic andhard to reason about. In particular, it is difficult to add features without retraining,to guarantee any level of performance, and to achieve acceptable performancewhen encountering untrained scenarios. These limitations can be addressed bydeploying quantitative run-timeshieldsthat serve as a proxy for the controller.At each time point, the shield reads the command issued by the controller andmay choose to alter it before passing it on to the plant. We show how optimalshields that interfere as little as possible while guaranteeing a desired level ofcontroller performance, can be generated systematically and automatically usingreactive synthesis. First, we abstract the plant by building a stochastic model.Second, we consider the learned controller to be a black box. Third, we mea-surecontroller performanceandshield interferenceby two quantitative run-timemeasures that are formally defined using weighted automata. Then, the problemof constructing a shield that guarantees maximal performance with minimal inter-ference is the problem of finding an optimal strategy in a stochastic2-player game“controller versus shield” played on the abstract state space of the plant with aquantitative objective obtained from combining the performance and interferencemeasures. We illustrate the effectiveness of our approach by automatically con-structing lightweight shields for learned traffic-light controllers in various roadnetworks. The shields we generate avoid liveness bugs, improve controller per-formance in untrained and changing traffic situations, and add features to learnedcontrollers, such as giving priority to emergency vehicles.}, author = {Avni, Guy and Bloem, Roderick and Chatterjee, Krishnendu and Henzinger, Thomas A and Konighofer, Bettina and Pranger, Stefan}, booktitle = {31st International Conference on Computer-Aided Verification}, isbn = {9783030255398}, issn = {0302-9743}, location = {New York, NY, United States}, pages = {630--649}, publisher = {Springer}, title = {{Run-time optimization for learned controllers through quantitative games}}, doi = {10.1007/978-3-030-25540-4_36}, volume = {11561}, year = {2019}, } @article{6465, abstract = {Tight control over protein degradation is a fundamental requirement for cells to respond rapidly to various stimuli and adapt to a fluctuating environment. Here we develop a versatile, easy-to-handle library of destabilizing tags (degrons) for the precise regulation of protein expression profiles in mammalian cells by modulating target protein half-lives in a predictable manner. Using the well-established tetracycline gene-regulation system as a model, we show that the dynamics of protein expression can be tuned by fusing appropriate degron tags to gene regulators. Next, we apply this degron library to tune a synthetic pulse-generating circuit in mammalian cells. With this toolbox we establish a set of pulse generators with tailored pulse lengths and magnitudes of protein expression. This methodology will prove useful in the functional roles of essential proteins, fine-tuning of gene-expression systems, and enabling a higher complexity in the design of synthetic biological systems in mammalian cells.}, author = {Chassin, Hélène and Müller, Marius and Tigges, Marcel and Scheller, Leo and Lang, Moritz and Fussenegger, Martin}, issn = {20411723}, journal = {Nature Communications}, number = {1}, publisher = {Springer Nature}, title = {{A modular degron library for synthetic circuits in mammalian cells}}, doi = {10.1038/s41467-019-09974-5}, volume = {10}, year = {2019}, } @article{6466, abstract = {One of the most striking and consistent results in speciation genomics is the heterogeneous divergence observed across the genomes of closely related species. This pattern was initially attributed to different levels of gene exchange—with divergence preserved at loci generating a barrier to gene flow but homogenized at unlinked neutral loci. Although there is evidence to support this model, it is now recognized that interpreting patterns of divergence across genomes is not so straightforward. One problem is that heterogenous divergence between populations can also be generated by other processes (e.g. recurrent selective sweeps or background selection) without any involvement of differential gene flow. Thus, integrated studies that identify which loci are likely subject to divergent selection are required to shed light on the interplay between selection and gene flow during the early phases of speciation. In this issue of Molecular Ecology, Rifkin et al. (2019) confront this challenge using a pair of sister morning glory species. They wisely design their sampling to take the geographic context of individuals into account, including geographically isolated (allopatric) and co‐occurring (sympatric) populations. This enabled them to show that individuals are phenotypically less differentiated in sympatry. They also found that the loci that resist introgression are enriched for those most differentiated in allopatry and loci that exhibit signals of divergent selection. One great strength of the study is the combination of methods from population genetics and molecular evolution, including the development of a model to simultaneously infer admixture proportions and selfing rates.}, author = {Field, David and Fraisse, Christelle}, issn = {1365294X}, journal = {Molecular ecology}, number = {7}, pages = {1579--1581}, publisher = {Wiley}, title = {{Breaking down barriers in morning glories}}, doi = {10.1111/mec.15048}, volume = {28}, year = {2019}, } @article{6467, abstract = {Fitness interactions between mutations can influence a population’s evolution in many different ways. While epistatic effects are difficult to measure precisely, important information is captured by the mean and variance of log fitnesses for individuals carrying different numbers of mutations. We derive predictions for these quantities from a class of simple fitness landscapes, based on models of optimizing selection on quantitative traits. We also explore extensions to the models, including modular pleiotropy, variable effect sizes, mutational bias and maladaptation of the wild type. We illustrate our approach by reanalysing a large dataset of mutant effects in a yeast snoRNA (small nucleolar RNA). Though characterized by some large epistatic effects, these data give a good overall fit to the non-epistatic null model, suggesting that epistasis might have limited influence on the evolutionary dynamics in this system. We also show how the amount of epistasis depends on both the underlying fitness landscape and the distribution of mutations, and so is expected to vary in consistent ways between new mutations, standing variation and fixed mutations.}, author = {Fraisse, Christelle and Welch, John J.}, issn = {1744957X}, journal = {Biology Letters}, number = {4}, publisher = {Royal Society of London}, title = {{The distribution of epistasis on simple fitness landscapes}}, doi = {10.1098/rsbl.2018.0881}, volume = {15}, year = {2019}, } @article{6470, abstract = {Investigating neuronal activity using genetically encoded Ca2+ indicators in behaving animals is hampered by inaccuracies in spike inference from fluorescent tracers. Here we combine two‐photon [Ca2+] imaging with cell‐attached recordings, followed by post hoc determination of the expression level of GCaMP6f, to explore how it affects the amplitude, kinetics and temporal summation of somatic [Ca2+] transients in mouse hippocampal pyramidal cells (PCs). The amplitude of unitary [Ca2+] transients (evoked by a single action potential) negatively correlates with GCaMP6f expression, but displays large variability even among PCs with similarly low expression levels. The summation of fluorescence signals is frequency‐dependent, supralinear and also shows remarkable cell‐to‐cell variability. We performed experimental data‐based simulations and found that spike inference error rates using MLspike depend strongly on unitary peak amplitudes and GCaMP6f expression levels. We provide simple methods for estimating the unitary [Ca2+] transients in individual weakly GCaMP6f‐expressing PCs, with which we achieve spike inference error rates of ∼5%. }, author = {Éltes, Tímea and Szoboszlay, Miklos and Szigeti, Margit Katalin and Nusser, Zoltan}, issn = {14697793}, journal = {Journal of Physiology}, number = {11}, pages = {2925–2947}, publisher = {Wiley}, title = {{Improved spike inference accuracy by estimating the peak amplitude of unitary [Ca2+] transients in weakly GCaMP6f-expressing hippocampal pyramidal cells}}, doi = {10.1113/JP277681}, volume = {597}, year = {2019}, } @phdthesis{6473, abstract = {Single cells are constantly interacting with their environment and each other, more importantly, the accurate perception of environmental cues is crucial for growth, survival, and reproduction. This communication between cells and their environment can be formalized in mathematical terms and be quantified as the information flow between them, as prescribed by information theory. The recent availability of real–time dynamical patterns of signaling molecules in single cells has allowed us to identify encoding about the identity of the environment in the time–series. However, efficient estimation of the information transmitted by these signals has been a data–analysis challenge due to the high dimensionality of the trajectories and the limited number of samples. In the first part of this thesis, we develop and evaluate decoding–based estimation methods to lower bound the mutual information and derive model–based precise information estimates for biological reaction networks governed by the chemical master equation. This is followed by applying the decoding-based methods to study the intracellular representation of extracellular changes in budding yeast, by observing the transient dynamics of nuclear translocation of 10 transcription factors in response to 3 stress conditions. Additionally, we apply these estimators to previously published data on ERK and Ca2+ signaling and yeast stress response. We argue that this single cell decoding-based measure of information provides an unbiased, quantitative and interpretable measure for the fidelity of biological signaling processes. Finally, in the last section, we deal with gene regulation which is primarily controlled by transcription factors (TFs) that bind to the DNA to activate gene expression. The possibility that non-cognate TFs activate transcription diminishes the accuracy of regulation with potentially disastrous effects for the cell. This ’crosstalk’ acts as a previously unexplored source of noise in biochemical networks and puts a strong constraint on their performance. To mitigate erroneous initiation we propose an out of equilibrium scheme that implements kinetic proofreading. We show that such architectures are favored over their equilibrium counterparts for complex organisms despite introducing noise in gene expression. }, author = {Cepeda Humerez, Sarah A}, issn = {2663-337X}, keywords = {Information estimation, Time-series, data analysis}, pages = {135}, publisher = {Institute of Science and Technology Austria}, title = {{Estimating information flow in single cells}}, doi = {10.15479/AT:ISTA:6473}, year = {2019}, } @article{6477, abstract = {Thermalizing quantum systems are conventionallydescribed by statistical mechanics at equilib-rium. However, not all systems fall into this category, with many-body localization providinga generic mechanism for thermalization to fail in strongly disordered systems. Many-bodylocalized (MBL) systems remain perfect insulators at nonzero temperature, which do notthermalize and therefore cannot be describedusing statistical mechanics. This Colloquiumreviews recent theoretical and experimental advances in studies of MBL systems, focusing onthe new perspective provided by entanglement and nonequilibrium experimental probes suchas quantum quenches. Theoretically, MBL systems exhibit a new kind of robust integrability: anextensive set of quasilocal integrals of motion emerges, which provides an intuitive explanationof the breakdown of thermalization. A description based on quasilocal integrals of motion isused to predict dynamical properties of MBL systems, such as the spreading of quantumentanglement, the behavior of local observables, and the response to external dissipativeprocesses. Furthermore, MBL systems can exhibit eigenstate transitions and quantum ordersforbidden in thermodynamic equilibrium. An outline isgiven of the current theoretical under-standing of the quantum-to-classical transitionbetween many-body localized and ergodic phasesand anomalous transport in the vicinity of that transition. Experimentally, synthetic quantumsystems, which are well isolated from an external thermal reservoir, provide natural platforms forrealizing the MBL phase. Recent experiments with ultracold atoms, trapped ions, superconductingqubits, and quantum materials, in which different signatures of many-body localization have beenobserved, are reviewed. This Colloquium concludes by listing outstanding challenges andpromising future research directions.}, author = {Abanin, Dmitry A. and Altman, Ehud and Bloch, Immanuel and Serbyn, Maksym}, issn = {0034-6861}, journal = {Reviews of Modern Physics}, number = {2}, publisher = {American Physical Society}, title = {{Colloquium: Many-body localization, thermalization, and entanglement}}, doi = {10.1103/revmodphys.91.021001}, volume = {91}, year = {2019}, } @inproceedings{6482, abstract = {Computer vision systems for automatic image categorization have become accurate and reliable enough that they can run continuously for days or even years as components of real-world commercial applications. A major open problem in this context, however, is quality control. Good classification performance can only be expected if systems run under the specific conditions, in particular data distributions, that they were trained for. Surprisingly, none of the currently used deep network architectures have a built-in functionality that could detect if a network operates on data from a distribution it was not trained for, such that potentially a warning to the human users could be triggered. In this work, we describe KS(conf), a procedure for detecting such outside of specifications (out-of-specs) operation, based on statistical testing of the network outputs. We show by extensive experiments using the ImageNet, AwA2 and DAVIS datasets on a variety of ConvNets architectures that KS(conf) reliably detects out-of-specs situations. It furthermore has a number of properties that make it a promising candidate for practical deployment: it is easy to implement, adds almost no overhead to the system, works with all networks, including pretrained ones, and requires no a priori knowledge of how the data distribution could change. }, author = {Sun, Rémy and Lampert, Christoph}, isbn = {9783030129385}, issn = {1611-3349}, location = {Stuttgart, Germany}, pages = {244--259}, publisher = {Springer Nature}, title = {{KS(conf): A light-weight test if a ConvNet operates outside of Its specifications}}, doi = {10.1007/978-3-030-12939-2_18}, volume = {11269}, year = {2019}, } @misc{6485, abstract = {Traditional concurrent programming involves manipulating shared mutable state. Alternatives to this programming style are communicating sequential processes (CSP) [1] and actor [2] models, which share data via explicit communication. Rendezvous channelis the common abstraction for communication between several processes, where senders and receivers perform a rendezvous handshake as a part of their protocol (senders wait for receivers and vice versa). Additionally to this, channels support the select expression. In this work, we present the first efficient lock-free channel algorithm, and compare it against Go [3] and Kotlin [4] baseline implementations.}, author = {Koval, Nikita and Alistarh, Dan-Adrian and Elizarov, Roman}, booktitle = {Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming}, isbn = {9781450362252}, location = {Washington, NY, United States}, pages = {417--418}, publisher = {ACM Press}, title = {{Lock-free channels for programming via communicating sequential processes}}, doi = {10.1145/3293883.3297000}, year = {2019}, } @article{6486, abstract = {Based on a novel control scheme, where a steady modification of the streamwise velocity profile leads to complete relaminarization of initially fully turbulent pipe flow, we investigate the applicability and usefulness of custom-shaped honeycombs for such control. The custom-shaped honeycombs are used as stationary flow management devices which generate specific modifications of the streamwise velocity profile. Stereoscopic particle image velocimetry and pressure drop measurements are used to investigate and capture the development of the relaminarizing flow downstream these devices. We compare the performance of straight (constant length across the radius of the pipe) honeycombs with custom-shaped ones (variable length across the radius) and try to determine the optimal shape for maximal relaminarization at minimal pressure loss. The optimally modified streamwise velocity profile is found to be M-shaped, and the maximum attainable Reynolds number for total relaminarization is found to be of the order of 10,000. Consequently, the respective reduction in skin friction downstream of the device is almost by a factor of 5. The break-even point, where the additional pressure drop caused by the device is balanced by the savings due to relaminarization and a net gain is obtained, corresponds to a downstream stretch of distances as low as approximately 100 pipe diameters of laminar flow.}, author = {Kühnen, Jakob and Scarselli, Davide and Hof, Björn}, issn = {1528901X}, journal = {Journal of Fluids Engineering}, number = {11}, publisher = {ASME}, title = {{Relaminarization of pipe flow by means of 3D-printed shaped honeycombs}}, doi = {10.1115/1.4043494}, volume = {141}, year = {2019}, } @inproceedings{6490, abstract = {Smart contracts are programs that are stored and executed on the Blockchain and can receive, manage and transfer money (cryptocurrency units). Two important problems regarding smart contracts are formal analysis and compiler optimization. Formal analysis is extremely important, because smart contracts hold funds worth billions of dollars and their code is immutable after deployment. Hence, an undetected bug can cause significant financial losses. Compiler optimization is also crucial, because every action of a smart contract has to be executed by every node in the Blockchain network. Therefore, optimizations in compiling smart contracts can lead to significant savings in computation, time and energy. Two classical approaches in program analysis and compiler optimization are intraprocedural and interprocedural analysis. In intraprocedural analysis, each function is analyzed separately, while interprocedural analysis considers the entire program. In both cases, the analyses are usually reduced to graph problems over the control flow graph (CFG) of the program. These graph problems are often computationally expensive. Hence, there has been ample research on exploiting structural properties of CFGs for efficient algorithms. One such well-studied property is the treewidth, which is a measure of tree-likeness of graphs. It is known that intraprocedural CFGs of structured programs have treewidth at most 6, whereas the interprocedural treewidth cannot be bounded. This result has been used as a basis for many efficient intraprocedural analyses. In this paper, we explore the idea of exploiting the treewidth of smart contracts for formal analysis and compiler optimization. First, similar to classical programs, we show that the intraprocedural treewidth of structured Solidity and Vyper smart contracts is at most 9. Second, for global analysis, we prove that the interprocedural treewidth of structured smart contracts is bounded by 10 and, in sharp contrast with classical programs, treewidth-based algorithms can be easily applied for interprocedural analysis. Finally, we supplement our theoretical results with experiments using a tool we implemented for computing treewidth of smart contracts and show that the treewidth is much lower in practice. We use 36,764 real-world Ethereum smart contracts as benchmarks and find that they have an average treewidth of at most 3.35 for the intraprocedural case and 3.65 for the interprocedural case. }, author = {Chatterjee, Krishnendu and Goharshady, Amir Kafshdar and Goharshady, Ehsan Kafshdar}, booktitle = {Proceedings of the 34th ACM Symposium on Applied Computing}, isbn = {9781450359337}, location = {Limassol, Cyprus}, pages = {400--408}, publisher = {ACM}, title = {{The treewidth of smart contracts}}, doi = {10.1145/3297280.3297322}, volume = {Part F147772}, year = {2019}, } @inproceedings{6493, abstract = {We present two algorithmic approaches for synthesizing linear hybrid automata from experimental data. Unlike previous approaches, our algorithms work without a template and generate an automaton with nondeterministic guards and invariants, and with an arbitrary number and topology of modes. They thus construct a succinct model from the data and provide formal guarantees. In particular, (1) the generated automaton can reproduce the data up to a specified tolerance and (2) the automaton is tight, given the first guarantee. Our first approach encodes the synthesis problem as a logical formula in the theory of linear arithmetic, which can then be solved by an SMT solver. This approach minimizes the number of modes in the resulting model but is only feasible for limited data sets. To address scalability, we propose a second approach that does not enforce to find a minimal model. The algorithm constructs an initial automaton and then iteratively extends the automaton based on processing new data. Therefore the algorithm is well-suited for online and synthesis-in-the-loop applications. The core of the algorithm is a membership query that checks whether, within the specified tolerance, a given data set can result from the execution of a given automaton. We solve this membership problem for linear hybrid automata by repeated reachability computations. We demonstrate the effectiveness of the algorithm on synthetic data sets and on cardiac-cell measurements.}, author = {Garcia Soto, Miriam and Henzinger, Thomas A and Schilling, Christian and Zeleznik, Luka}, booktitle = {31st International Conference on Computer-Aided Verification}, isbn = {9783030255398}, issn = {0302-9743}, keywords = {Synthesis, Linear hybrid automaton, Membership}, location = {New York City, NY, USA}, pages = {297--314}, publisher = {Springer}, title = {{Membership-based synthesis of linear hybrid automata}}, doi = {10.1007/978-3-030-25540-4_16}, volume = {11561}, year = {2019}, }