@phdthesis{819, abstract = {Contagious diseases must transmit from infectious to susceptible hosts in order to reproduce. Whilst vectored pathogens can rely on intermediaries to find new hosts for them, many infectious pathogens require close contact or direct interaction between hosts for transmission. Hence, this means that conspecifics are often the main source of infection for most animals and so, in theory, animals should avoid conspecifics to reduce their risk of infection. Of course, in reality animals must interact with one another, as a bare minimum, to mate. However, being social provides many additional benefits and group living has become a taxonomically diverse and widespread trait. How then do social animals overcome the issue of increased disease? Over the last few decades, the social insects (ants, termites and some bees and wasps) have become a model system for studying disease in social animals. On paper, a social insect colony should be particularly susceptible to disease, given that they often contain thousands of potential hosts that are closely related and frequently interact, as well as exhibiting stable environmental conditions that encourage microbial growth. Yet, disease outbreaks appear to be rare and attempts to eradicate pest species using pathogens have failed time and again. Evolutionary biologists investigating this observation have discovered that the reduced disease susceptibility in social insects is, in part, due to collectively performed disease defences of the workers. These defences act like a “social immune system” for the colony, resulting in a per capita decrease in disease, termed social immunity. Our understanding of social immunity, and its importance in relation to the immunological defences of each insect, continues to grow, but there remain many open questions. In this thesis I have studied disease defence in garden ants. In the first data chapter, I use the invasive garden ant, Lasius neglectus, to investigate how colonies mitigate lethal infections and prevent them from spreading systemically. I find that ants have evolved ‘destructive disinfection’ – a behaviour that uses endogenously produced acidic poison to kill diseased brood and to prevent the pathogen from replicating. In the second experimental chapter, I continue to study the use of poison in invasive garden ant colonies, finding that it is sprayed prophylactically within the nest. However, this spraying has negative effects on developing pupae when they have had their cocoons artificially removed. Hence, I suggest that acidic nest sanitation may be maintaining larval cocoon spinning in this species. In the next experimental chapter, I investigated how colony founding black garden ant queens (Lasius niger) prevent disease when a co-foundress dies. I show that ant queens prophylactically perform undertaking behaviours, similar to those performed by the workers in mature nests. When a co-foundress was infected, these undertaking behaviours improved the survival of the healthy queen. In the final data chapter, I explored how immunocompetence (measured as antifungal activity) changes as incipient black garden ant colonies grow and mature, from the solitary queen phase to colonies with several hundred workers. Queen and worker antifungal activity varied throughout this time period, but despite social immunity, did not decrease as colonies matured. In addition to the above data chapters, this thesis includes two co-authored reviews. In the first, we examine the state of the art in the field of social immunity and how it might develop in the future. In the second, we identify several challenges and open questions in the study of disease defence in animals. We highlight how social insects offer a unique model to tackle some of these problems, as disease defence can be studied from the cell to the society. }, author = {Pull, Christopher}, issn = {2663-337X}, pages = {122}, publisher = {Institute of Science and Technology Austria}, title = {{Disease defence in garden ants}}, doi = {10.15479/AT:ISTA:th_861}, year = {2017}, } @phdthesis{820, abstract = {The lac operon is a classic model system for bacterial gene regulation, and has been studied extensively in E. coli, a classic model organism. However, not much is known about E. coli’s ecology and life outside the laboratory, in particular in soil and water environments. The natural diversity of the lac operon outside the laboratory, its role in the ecology of E. coli and the selection pressures it is exposed to, are similarly unknown. In Chapter Two of this thesis, I explore the genetic diversity, phylogenetic history and signatures of selection of the lac operon across 20 natural isolates of E. coli and divergent clades of Escherichia. I found that complete lac operons were present in all isolates examined, which in all but one case were functional. The lac operon phylogeny conformed to the whole-genome phylogeny of the divergent Escherichia clades, which excludes horizontal gene transfer as an explanation for the presence of functional lac operons in these clades. All lac operon genes showed a signature of purifying selection; this signature was strongest for the lacY gene. Lac operon genes of human and environmental isolates showed similar signatures of selection, except the lacZ gene, which showed a stronger signature of selection in environmental isolates. In Chapter Three, I try to identify the natural genetic variation relevant for phenotype and fitness in the lac operon, comparing growth rate on lactose and LacZ activity of the lac operons of these wild isolates in a common genetic background. Sequence variation in the lac promoter region, upstream of the -10 and -35 RNA polymerase binding motif, predicted variation in LacZ activity at full induction, using a thermodynamic model of polymerase binding (Tugrul, 2016). However, neither variation in LacZ activity, nor RNA polymerase binding predicted by the model correlated with variation in growth rate. Lac operons of human and environmental isolates did not differ systematically in either growth rate on lactose or LacZ protein activity, suggesting that these lac operons have been exposed to similar selection pressures. We thus have no evidence that the phenotypic variation we measured is relevant for fitness. To start assessing the effect of genomic background on the growth phenotype conferred by the lac operon, I compared growth on minimal medium with lactose between lac operon constructs and the corresponding original isolates, I found that maximal growth rate was determined by genomic background, with almost all backgrounds conferring higher growth rates than lab strain K12 MG1655. However, I found no evidence that the lactose concentration at which growth was half maximal depended on genomic background.}, author = {Jesse, Fabienne}, issn = {2663-337X}, pages = {87}, publisher = {Institute of Science and Technology Austria}, title = {{The lac operon in the wild}}, doi = {10.15479/AT:ISTA:th_857}, year = {2017}, } @phdthesis{821, abstract = {This dissertation focuses on algorithmic aspects of program verification, and presents modeling and complexity advances on several problems related to the static analysis of programs, the stateless model checking of concurrent programs, and the competitive analysis of real-time scheduling algorithms. Our contributions can be broadly grouped into five categories. Our first contribution is a set of new algorithms and data structures for the quantitative and data-flow analysis of programs, based on the graph-theoretic notion of treewidth. It has been observed that the control-flow graphs of typical programs have special structure, and are characterized as graphs of small treewidth. We utilize this structural property to provide faster algorithms for the quantitative and data-flow analysis of recursive and concurrent programs. In most cases we make an algebraic treatment of the considered problem, where several interesting analyses, such as the reachability, shortest path, and certain kind of data-flow analysis problems follow as special cases. We exploit the constant-treewidth property to obtain algorithmic improvements for on-demand versions of the problems, and provide data structures with various tradeoffs between the resources spent in the preprocessing and querying phase. We also improve on the algorithmic complexity of quantitative problems outside the algebraic path framework, namely of the minimum mean-payoff, minimum ratio, and minimum initial credit for energy problems. Our second contribution is a set of algorithms for Dyck reachability with applications to data-dependence analysis and alias analysis. In particular, we develop an optimal algorithm for Dyck reachability on bidirected graphs, which are ubiquitous in context-insensitive, field-sensitive points-to analysis. Additionally, we develop an efficient algorithm for context-sensitive data-dependence analysis via Dyck reachability, where the task is to obtain analysis summaries of library code in the presence of callbacks. Our algorithm preprocesses libraries in almost linear time, after which the contribution of the library in the complexity of the client analysis is (i)~linear in the number of call sites and (ii)~only logarithmic in the size of the whole library, as opposed to linear in the size of the whole library. Finally, we prove that Dyck reachability is Boolean Matrix Multiplication-hard in general, and the hardness also holds for graphs of constant treewidth. This hardness result strongly indicates that there exist no combinatorial algorithms for Dyck reachability with truly subcubic complexity. Our third contribution is the formalization and algorithmic treatment of the Quantitative Interprocedural Analysis framework. In this framework, the transitions of a recursive program are annotated as good, bad or neutral, and receive a weight which measures the magnitude of their respective effect. The Quantitative Interprocedural Analysis problem asks to determine whether there exists an infinite run of the program where the long-run ratio of the bad weights over the good weights is above a given threshold. We illustrate how several quantitative problems related to static analysis of recursive programs can be instantiated in this framework, and present some case studies to this direction. Our fourth contribution is a new dynamic partial-order reduction for the stateless model checking of concurrent programs. Traditional approaches rely on the standard Mazurkiewicz equivalence between traces, by means of partitioning the trace space into equivalence classes, and attempting to explore a few representatives from each class. We present a new dynamic partial-order reduction method called the Data-centric Partial Order Reduction (DC-DPOR). Our algorithm is based on a new equivalence between traces, called the observation equivalence. DC-DPOR explores a coarser partitioning of the trace space than any exploration method based on the standard Mazurkiewicz equivalence. Depending on the program, the new partitioning can be even exponentially coarser. Additionally, DC-DPOR spends only polynomial time in each explored class. Our fifth contribution is the use of automata and game-theoretic verification techniques in the competitive analysis and synthesis of real-time scheduling algorithms for firm-deadline tasks. On the analysis side, we leverage automata on infinite words to compute the competitive ratio of real-time schedulers subject to various environmental constraints. On the synthesis side, we introduce a new instance of two-player mean-payoff partial-information games, and show how the synthesis of an optimal real-time scheduler can be reduced to computing winning strategies in this new type of games.}, author = {Pavlogiannis, Andreas}, issn = {2663-337X}, pages = {418}, publisher = {Institute of Science and Technology Austria}, title = {{Algorithmic advances in program analysis and their applications}}, doi = {10.15479/AT:ISTA:th_854}, year = {2017}, } @article{822, abstract = {Polymicrobial infections constitute small ecosystems that accommodate several bacterial species. Commonly, these bacteria are investigated in isolation. However, it is unknown to what extent the isolates interact and whether their interactions alter bacterial growth and ecosystem resilience in the presence and absence of antibiotics. We quantified the complete ecological interaction network for 72 bacterial isolates collected from 23 individuals diagnosed with polymicrobial urinary tract infections and found that most interactions cluster based on evolutionary relatedness. Statistical network analysis revealed that competitive and cooperative reciprocal interactions are enriched in the global network, while cooperative interactions are depleted in the individual host community networks. A population dynamics model parameterized by our measurements suggests that interactions restrict community stability, explaining the observed species diversity of these communities. We further show that the clinical isolates frequently protect each other from clinically relevant antibiotics. Together, these results highlight that ecological interactions are crucial for the growth and survival of bacteria in polymicrobial infection communities and affect their assembly and resilience. }, author = {De Vos, Marjon and Zagórski, Marcin P and Mcnally, Alan and Bollenbach, Mark Tobias}, issn = {0027-8424}, journal = {PNAS}, number = {40}, pages = {10666 -- 10671}, publisher = {National Academy of Sciences}, title = {{Interaction networks, ecological stability, and collective antibiotic tolerance in polymicrobial infections}}, doi = {10.1073/pnas.1713372114}, volume = {114}, year = {2017}, } @article{8235, abstract = {Due to large homology of human and canine EGFR, dogs suffering from spontaneous EGFR+ cancer can be considered as ideal translational models. Thereby, novel immunotherapeutic compounds can be developed for both human and veterinary patients. This study describes the radiolabeling of a canine anti-EGFR IgG antibody (can225IgG) with potential diagnostic and therapeutic value in comparative clinical settings. Can225IgG was functionalized with DTPA for subsequent chelation with the radionuclide 99mTc. Successful coupling of 10 DTPA molecules per antibody on average was proven by significant mass increase in MALDI-TOF spectroscopy, gel electrophoresis and immunoblots. Following functionalization and radiolabeling, 99mTc-DTPA-can225IgG fully retained its binding capacity towards human and canine EGFR in flow cytometry, immuno- and radioblots, and autoradiography. The affinity of radiolabeled can225IgG was determined to KD 0.8 ±0.0031 nM in a real-time kinetics assay on canine carcinoma cells by a competition binding technique. Stability tests of the radiolabeled compound identified TRIS buffered saline as the ideal formulation for short-term storage with 87.11 ±6.04% intact compound being still detected 60 minutes post radiolabeling. High stability, specificity and EGFR binding affinity pinpoint towards 99mTc-radiolabeled can225IgG antibody as an ideal lead compound for the first proof-of-concept diagnostic and therapeutic applications in canine cancer patients.}, author = {Fazekas-Singer, Judit and Berroterán-Infante, Neydher and Rami-Mark, Christina and Dumanic, Monika and Matz, Miroslawa and Willmann, Michael and Andreae, Fritz and Singer, Josef and Wadsak, Wolfgang and Mitterhauser, Markus and Jensen-Jarolim, Erika}, issn = {1949-2553}, journal = {Oncotarget}, pages = {83128--83141}, publisher = {Impact Journals}, title = {{Development of a radiolabeled caninized anti-EGFR antibody for comparative oncology trials}}, doi = {10.18632/oncotarget.20914}, volume = {8}, year = {2017}, } @article{8236, abstract = {Th2 immunity and allergic immune surveillance play critical roles in host responses to pathogens, parasites and allergens. Numerous studies have reported significant links between Th2 responses and cancer, including insights into the functions of IgE antibodies and associated effector cells in both antitumour immune surveillance and therapy. The interdisciplinary field of AllergoOncology was given Task Force status by the European Academy of Allergy and Clinical Immunology in 2014. Affiliated expert groups focus on the interface between allergic responses and cancer, applied to immune surveillance, immunomodulation and the functions of IgE‐mediated immune responses against cancer, to derive novel insights into more effective treatments. Coincident with rapid expansion in clinical application of cancer immunotherapies, here we review the current state‐of‐the‐art and future translational opportunities, as well as challenges in this relatively new field. Recent developments include improved understanding of Th2 antibodies, intratumoral innate allergy effector cells and mediators, IgE‐mediated tumour antigen cross‐presentation by dendritic cells, as well as immunotherapeutic strategies such as vaccines and recombinant antibodies, and finally, the management of allergy in daily clinical oncology. Shedding light on the crosstalk between allergic response and cancer is paving the way for new avenues of treatment.}, author = {Jensen-Jarolim, E. and Bax, H. J. and Bianchini, R. and Capron, M. and Corrigan, C. and Castells, M. and Dombrowicz, D. and Daniels-Wells, T. R. and Fazekas, Judit and Fiebiger, E. and Gatault, S. and Gould, H. J. and Janda, J. and Josephs, D. H. and Karagiannis, P. and Levi-Schaffer, F. and Meshcheryakova, A. and Mechtcheriakova, D. and Mekori, Y. and Mungenast, F. and Nigro, E. A. and Penichet, M. L. and Redegeld, F. and Saul, L. and Singer, J. and Spicer, J. F. and Siccardi, A. G. and Spillner, E. and Turner, M. C. and Untersmayr, E. and Vangelista, L. and Karagiannis, S. N.}, issn = {0105-4538}, journal = {Allergy}, number = {6}, pages = {866--887}, publisher = {Wiley}, title = {{AllergoOncology - the impact of allergy in oncology: EAACI position paper}}, doi = {10.1111/all.13119}, volume = {72}, year = {2017}, } @article{8237, abstract = {Monoclonal antibodies find broad application as therapy for various types of cancer by employing multiple mechanisms of action against tumors. Manipulating the Fc-mediated functions of antibodies that engage immune effector cells, such as NK cells, represents a strategy to influence effector cell activation and to enhance antibody potency and potentially efficacy. We developed a novel approach to generate and ascertain the functional attributes of Fc mutant monoclonal antibodies. This entailed coupling single expression vector (pVitro1) antibody cloning, using polymerase incomplete primer extension (PIPE) polymerase chain reaction, together with simultaneous Fc region point mutagenesis and high yield transient expression in human mammalian cells. Employing this, we engineered wild type, low (N297Q, NQ), and high (S239D/I332E, DE) FcR-binding Fc mutant monoclonal antibody panels recognizing two cancer antigens, HER2/neu and chondroitin sulfate proteoglycan 4. Antibodies were generated with universal mutagenic primers applicable to any IgG1 pVitro1 constructs, with high mutagenesis and transfection efficiency, in small culture volumes, at high yields and within 12 days from design to purified material. Antibody variants conserved their Fab-mediated recognition of target antigens and their direct anti-proliferative effects against cancer cells. Fc mutations had a significant impact on antibody interactions with Fc receptors (FcRs) on human NK cells, and consequently on the potency of NK cell activation, quantified by immune complex-mediated calcium mobilization and by antibody-dependent cellular cytotoxicity (ADCC) of tumor cells. This strategy for manipulation and testing of Fc region engagement with cognate FcRs can facilitate the design of antibodies with defined effector functions and potentially enhanced efficacy against tumor cells.}, author = {Ilieva, Kristina M. and Fazekas-Singer, Judit and Achkova, Daniela Y. and Dodev, Tihomir S. and Mele, Silvia and Crescioli, Silvia and Bax, Heather J. and Cheung, Anthony and Karagiannis, Panagiotis and Correa, Isabel and Figini, Mariangela and Marlow, Rebecca and Josephs, Debra H. and Beavil, Andrew J. and Maher, John and Spicer, James F. and Jensen-Jarolim, Erika and Tutt, Andrew N. and Karagiannis, Sophia N.}, issn = {1664-3224}, journal = {Frontiers in Immunology}, publisher = {Frontiers}, title = {{Functionally active Fc mutant antibodies recognizing cancer antigens generated rapidly at high yields}}, doi = {10.3389/fimmu.2017.01112}, volume = {8}, year = {2017}, } @article{8239, abstract = {Acrolein, a highly reactive unsaturated aldehyde, is generated in large amounts during smoking and is best known for its genotoxic capacity. Here, we aimed to assess whether acrolein at concentrations relevant for smokers may also exert immunomodulatory effects that could be relevant in allergy or cancer. In a BALB/c allergy model repeated nasal exposure to acrolein abrogated allergen-specific antibody and cytokine formation, and led to a relative accumulation of regulatory T cells in the lungs. Only the acrolein-treated mice were protected from bronchial hyperreactivity as well as from anaphylactic reactions upon challenge with the specific allergen. Moreover, grafted D2F2 tumor cells grew faster and intratumoral Foxp3+ cell accumulation was observed in these mice compared to sham-treated controls. Results from reporter cell lines suggested that acrolein acts via the aryl-hydrocarbon receptor which could be inhibited by resveratrol and 3′-methoxy-4′-nitroflavone Acrolein- stimulation of human PBMCs increased Foxp3+ expression by T cells which could be antagonized by resveratrol. Our mouse and human data thus revealed that acrolein exerts systemic immunosuppression by promoting Foxp3+ regulatory cells. This provides a novel explanation why smokers have a lower allergy, but higher cancer risk.}, author = {Roth-Walter, Franziska and Bergmayr, Cornelia and Meitz, Sarah and Buchleitner, Stefan and Stremnitzer, Caroline and Fazekas, Judit and Moskovskich, Anna and Müller, Mario A. and Roth, Georg A. and Manzano-Szalai, Krisztina and Dvorak, Zdenek and Neunkirchner, Alina and Jensen-Jarolim, Erika}, issn = {2045-2322}, journal = {Scientific Reports}, publisher = {Springer Nature}, title = {{Janus-faced Acrolein prevents allergy but accelerates tumor growth by promoting immunoregulatory Foxp3+ cells: Mouse model for passive respiratory exposure}}, doi = {10.1038/srep45067}, volume = {7}, year = {2017}, } @article{824, abstract = {In shear flows at transitional Reynolds numbers, localized patches of turbulence, known as puffs, coexist with the laminar flow. Recently, Avila et al. (Phys. Rev. Lett., vol. 110, 2013, 224502) discovered two spatially localized relative periodic solutions for pipe flow, which appeared in a saddle-node bifurcation at low Reynolds number. Combining slicing methods for continuous symmetry reduction with Poincaré sections for the first time in a shear flow setting, we compute and visualize the unstable manifold of the lower-branch solution and show that it extends towards the neighbourhood of the upper-branch solution. Surprisingly, this connection even persists far above the bifurcation point and appears to mediate the first stage of the puff generation: amplification of streamwise localized fluctuations. When the state-space trajectories on the unstable manifold reach the vicinity of the upper branch, corresponding fluctuations expand in space and eventually take the usual shape of a puff.}, author = {Budanur, Nazmi B and Hof, Björn}, issn = {0022-1120}, journal = {Journal of Fluid Mechanics}, publisher = {Cambridge University Press}, title = {{Heteroclinic path to spatially localized chaos in pipe flow}}, doi = {10.1017/jfm.2017.516}, volume = {827}, year = {2017}, } @article{8240, abstract = {Background/Aim: Cancer cell lines are indispensible surrogate models in cancer research, as they can be used off-the-shelf, expanded to the desired extent, easily modified and exchanged between research groups for affirmation, reproduction or follow-up experiments. As malignant cells are prone to genomic instability, phenotypical changes may occur after certain passages in culture. Thus, cell lines have to be regularly authenticated to ensure data quality. In between experiments these cell lines are often stored in liquid nitrogen for extended time periods. Although freezing of cells is a necessary evil, little research is performed on how long-term storage affects cancer cell lines. Therefore, this study investigated the effects of a 28-year long liquid nitrogen storage period on BT474 cells with regard to phenotypical changes, differences in cell-surface receptor expression as well as cytokine and gene expressional variations. Methods: Two batches of BT474 cells, one frozen in 1986, the other directly purchased from ATCC were investigated by light microscopy, cell growth analysis, flow cytometry and cytokine as well as whole-transcriptome expression profiling. Results: The cell lines were morphologically indifferent and showed similar growth rates and similar cell-surface receptor expression. Transcriptome analysis revealed significant differences in only 26 of 40,716 investigated RefSeq transcripts with 4 of them being up-regulated and 22 down-regulated. Conclusion: This study demonstrates that even after very long periods of storage in liquid nitrogen, cancer cell lines display only minimal changes in their gene expression profiles. However, also such minor changes should be carefully assessed before continuation of experiments, especially if phenotypic alterations can be additionally observed.}, author = {Fazekas, Judit and Grunt, Thomas W. and Jensen-Jarolim, Erika and Singer, Josef}, issn = {1949-2553}, journal = {Oncotarget}, pages = {35076--35087}, publisher = {Impact Journals}, title = {{Long term storage in liquid nitrogen leads to only minor phenotypic and gene expression changes in the mammary carcinoma model cell line BT474}}, doi = {10.18632/oncotarget.16623}, volume = {8}, year = {2017}, } @inproceedings{8299, abstract = {Permissionless blockchain-based cryptocurrencies commonly use proof-of-work (PoW) or proof-of-stake (PoS) to ensure their security, e.g. to prevent double spending attacks. However, both approaches have disadvantages: PoW leads to massive amounts of wasted electricity and re-centralization, whereas major stakeholders in PoS might be able to create a monopoly. In this work, we propose proof-of-personhood (PoP), a mechanism that binds physical entities to virtual identities in a way that enables accountability while preserving anonymity. Afterwards we introduce PoPCoin, a new cryptocurrency, whose consensus mechanism leverages PoP to eliminate the dis-advantages of PoW and PoS while ensuring security. PoPCoin leads to a continuously fair and democratic wealth creation process which paves the way for an experimental basic income infrastructure.}, author = {Borge, Maria and Kokoris Kogias, Eleftherios and Jovanovic, Philipp and Gasser, Linus and Gailly, Nicolas and Ford, Bryan}, booktitle = {2017 IEEE European Symposium on Security and Privacy Workshops}, location = {Paris, France}, publisher = {IEEE}, title = {{Proof-of-personhood: Redemocratizing permissionless cryptocurrencies}}, doi = {10.1109/eurospw.2017.46}, year = {2017}, } @inproceedings{8301, abstract = {Software-update mechanisms are critical to the security of modern systems, but their typically centralized design presents a lucrative and frequently attacked target. In this work, we propose CHAINIAC, a decentralized software-update framework that eliminates single points of failure, enforces transparency, and provides efficient verifiability of integrity and authenticity for software-release processes. Independent witness servers collectively verify conformance of software updates to release policies, build verifiers validate the source-to-binary correspondence, and a tamper-proof release log stores collectively signed updates, thus ensuring that no release is accepted by clients before being widely disclosed and validated. The release log embodies a skipchain, a novel data structure, enabling arbitrarily out-of-date clients to efficiently validate updates and signing keys. Evaluation of our CHAINIAC prototype on reproducible Debian packages shows that the automated update process takes the average of 5 minutes per release for individual packages, and only 20 seconds for the aggregate timeline. We further evaluate the framework using real-world data from the PyPI package repository and show that it offers clients security comparable to verifying every single update themselves while consuming only one-fifth of the bandwidth and having a minimal computational overhead.}, author = {Nikitin, Kirill and Kokoris Kogias, Eleftherios and Jovanovic, Philipp and Gasser, Linus and Gailly, Nicolas and Khoffi, Ismail and Cappos, Justin and Ford, Bryan}, booktitle = {Proceedings of the 26th USENIX Conference on Security Symposium}, isbn = {9781931971409}, location = {Vancouver, Canada}, pages = {1271–1287}, publisher = {USENIX Association}, title = {{CHAINIAC: Proactive software-update transparency via collectively signed skipchains and verified builds}}, year = {2017}, } @inproceedings{8306, abstract = {Bias-resistant public randomness is a critical component in many (distributed) protocols. Generating public randomness is hard, however, because active adversaries may behave dishonestly to bias public random choices toward their advantage. Existing solutions do not scale to hundreds or thousands of participants, as is needed in many decentralized systems. We propose two large-scale distributed protocols, RandHound and RandHerd, which provide publicly-verifiable, unpredictable, and unbiasable randomness against Byzantine adversaries. RandHound relies on an untrusted client to divide a set of randomness servers into groups for scalability, and it depends on the pigeonhole principle to ensure output integrity, even for non-random, adversarial group choices. RandHerd implements an efficient, decentralized randomness beacon. RandHerd is structurally similar to a BFT protocol, but uses RandHound in a one-time setup to arrange participants into verifiably unbiased random secret-sharing groups, which then repeatedly produce random output at predefined intervals. Our prototype demonstrates that RandHound and RandHerd achieve good performance across hundreds of participants while retaining a low failure probability by properly selecting protocol parameters, such as a group size and secret-sharing threshold. For example, when sharding 512 nodes into groups of 32, our experiments show that RandHound can produce fresh random output after 240 seconds. RandHerd, after a setup phase of 260 seconds, is able to generate fresh random output in intervals of approximately 6 seconds. For this configuration, both protocols operate at a failure probability of at most 0.08% against a Byzantine adversary.}, author = {Syta, E. and Jovanovic, P. and Kokoris Kogias, Eleftherios and Gailly, N. and Gasser, L. and Khoffi, I. and Fischer, M. J. and Ford, B.}, booktitle = {2017 IEEE Symposium on Security and Privacy}, isbn = {9781509055340}, issn = {2375-1207}, location = {San Jose, CA, United States}, pages = {444--460}, publisher = {IEEE}, title = {{Scalable bias-resistant distributed randomness}}, doi = {10.1109/SP.2017.45}, year = {2017}, } @inproceedings{833, abstract = {We present an efficient algorithm to compute Euler characteristic curves of gray scale images of arbitrary dimension. In various applications the Euler characteristic curve is used as a descriptor of an image. Our algorithm is the first streaming algorithm for Euler characteristic curves. The usage of streaming removes the necessity to store the entire image in RAM. Experiments show that our implementation handles terabyte scale images on commodity hardware. Due to lock-free parallelism, it scales well with the number of processor cores. Additionally, we put the concept of the Euler characteristic curve in the wider context of computational topology. In particular, we explain the connection with persistence diagrams.}, author = {Heiss, Teresa and Wagner, Hubert}, editor = {Felsberg, Michael and Heyden, Anders and Krüger, Norbert}, issn = {0302-9743}, location = {Ystad, Sweden}, pages = {397 -- 409}, publisher = {Springer}, title = {{Streaming algorithm for Euler characteristic curves of multidimensional images}}, doi = {10.1007/978-3-319-64689-3_32}, volume = {10424}, year = {2017}, } @article{835, abstract = {An outstanding question in animal development, tissue homeostasis and disease is how cell populations adapt to sensory inputs. During Drosophila larval development, hematopoietic sites are in direct contact with sensory neuron clusters of the peripheral nervous system (PNS), and blood cells (hemocytes) require the PNS for their survival and recruitment to these microenvironments, known as Hematopoietic Pockets. Here we report that Activin-β, a TGF-β family ligand, is expressed by sensory neurons of the PNS and regulates the proliferation and adhesion of hemocytes. These hemocyte responses depend on PNS activity, as shown by agonist treatment and transient silencing of sensory neurons. Activin-β has a key role in this regulation, which is apparent from reporter expression and mutant analyses. This mechanism of local sensory neurons controlling blood cell adaptation invites evolutionary parallels with vertebrate hematopoietic progenitors and the independent myeloid system of tissue macrophages, whose regulation by local microenvironments remain undefined.}, author = {Makhijani, Kalpana and Alexander, Brandy and Rao, Deepti and Petraki, Sophia and Herboso, Leire and Kukar, Katelyn and Batool, Itrat and Wachner, Stephanie and Gold, Katrina and Wong, Corinna and O'Connor, Michael and Brückner, Katja}, issn = {20411723}, journal = {Nature Communications}, publisher = {Nature Publishing Group}, title = {{Regulation of Drosophila hematopoietic sites by Activin-β from active sensory neurons}}, doi = {10.1038/ncomms15990}, volume = {8}, year = {2017}, } @inproceedings{836, abstract = {Recent research has examined how to study the topological features of a continuous self-map by means of the persistence of the eigenspaces, for given eigenvalues, of the endomorphism induced in homology over a field. This raised the question of how to select dynamically significant eigenvalues. The present paper aims to answer this question, giving an algorithm that computes the persistence of eigenspaces for every eigenvalue simultaneously, also expressing said eigenspaces as direct sums of “finite” and “singular” subspaces.}, author = {Ethier, Marc and Jablonski, Grzegorz and Mrozek, Marian}, booktitle = {Special Sessions in Applications of Computer Algebra}, isbn = {978-331956930-7}, location = {Kalamata, Greece}, pages = {119 -- 136}, publisher = {Springer}, title = {{Finding eigenvalues of self-maps with the Kronecker canonical form}}, doi = {10.1007/978-3-319-56932-1_8}, volume = {198}, year = {2017}, } @phdthesis{837, abstract = {The hippocampus is a key brain region for memory and notably for spatial memory, and is needed for both spatial working and reference memories. Hippocampal place cells selectively discharge in specific locations of the environment to form mnemonic represen tations of space. Several behavioral protocols have been designed to test spatial memory which requires the experimental subject to utilize working memory and reference memory. However, less is known about how these memory traces are presented in the hippo campus, especially considering tasks that require both spatial working and long -term reference memory demand. The aim of my thesis was to elucidate how spatial working memory, reference memory, and the combination of both are represented in the hippocampus. In this thesis, using a radial eight -arm maze, I examined how the combined demand on these memories influenced place cell assemblies while reference memories were partially updated by changing some of the reward- arms. This was contrasted with task varian ts requiring working or reference memories only. Reference memory update led to gradual place field shifts towards the rewards on the switched arms. Cells developed enhanced firing in passes between newly -rewarded arms as compared to those containing an unchanged reward. The working memory task did not show such gradual changes. Place assemblies on occasions replayed trajectories of the maze; at decision points the next arm choice was preferentially replayed in tasks needing reference memory while in the pure working memory task the previously visited arm was replayed. Hence trajectory replay only reflected the decision of the animal in tasks needing reference memory update. At the reward locations, in all three tasks outbound trajectories of the current arm were preferentially replayed, showing the animals’ next path to the center. At reward locations trajectories were replayed preferentially in reverse temporal order. Moreover, in the center reverse replay was seen in the working memory task but in the other tasks forward replay was seen. Hence, the direction of reactivation was determined by the goal locations so that part of the trajectory which was closer to the goal was reactivated later in an HSE while places further away from the goal were reactivated earlier. Altogether my work demonstrated that reference memory update triggers several levels of reorganization of the hippocampal cognitive map which are not seen in simpler working memory demand s. Moreover, hippocampus is likely to be involved in spatial decisions through reactivating planned trajectories when reference memory recall is required for such a decision. }, author = {Xu, Haibing}, issn = {2663-337X}, pages = {93}, publisher = {Institute of Science and Technology Austria}, title = {{Reactivation of the hippocampal cognitive map in goal-directed spatial tasks}}, doi = {10.15479/AT:ISTA:th_858}, year = {2017}, } @phdthesis{838, abstract = {In this thesis we discuss the exact security of message authentications codes HMAC , NMAC , and PMAC . 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). PMAC is a block-cipher based mode of operation, which also happens to be the most famous fully parallel MAC. 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, under two assumptions. Unfortunately, for many instantiations of HMAC one of them has been found to be wrong. To restore the provable guarantees for NMAC , Bellare [Crypto’06] showed its security without this assumption. PMAC was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a pseudorandom permutation over n -bit strings, PMAC constitutes a provably secure variable input-length PRF. For adversaries making q queries, each of length at most ` (in n -bit blocks), and of total length σ ≤ q` , the original paper proves an upper bound on the distinguishing advantage of O ( σ 2 / 2 n ), while the currently best bound is O ( qσ/ 2 n ). In this work we show that this bound is tight by giving an attack with advantage Ω( q 2 `/ 2 n ). In the PMAC construction one initially XORs a mask to every message block, where the mask for the i th block is computed as τ i := γ i · L , where L is a (secret) random value, and γ i is the i -th codeword of the Gray code. Our attack applies more generally to any sequence of γ i ’s which contains a large coset of a subgroup of GF (2 n ). As for NMAC , our first contribution is a simpler and uniform proof: 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 also show that this ε + `qδ bound is basically tight by constructing an f for which an attack with advantage `qδ exists. Moreover, we analyze the PRF-security of a modification of NMAC called NI by An and Bellare that avoids the constant rekeying on multi-block messages in NMAC and allows for an information-theoretic analysis. We carry out such an analysis, obtaining a tight `q 2 / 2 c bound for this step, improving over the trivial bound of ` 2 q 2 / 2 c . Finally, we investigate, if the security of PMAC can be further improved by using τ i ’s that are k -wise independent, for k > 1 (the original has k = 1). We observe that the security of PMAC will not increase in general if k = 2, and then prove that the security increases to O ( q 2 / 2 n ), if the k = 4. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether k = 3 is already sufficient to get this level of security is left as an open problem. Keywords: Message authentication codes, Pseudorandom functions, HMAC, PMAC. }, author = {Rybar, Michal}, issn = {2663-337X}, pages = {86}, publisher = {Institute of Science and Technology Austria}, title = {{(The exact security of) Message authentication codes}}, doi = {10.15479/AT:ISTA:th_828}, year = {2017}, } @inbook{84, abstract = {The advent of high-throughput technologies and the concurrent advances in information sciences have led to a data revolution in biology. This revolution is most significant in molecular biology, with an increase in the number and scale of the “omics” projects over the last decade. Genomics projects, for example, have produced impressive advances in our knowledge of the information concealed into genomes, from the many genes that encode for the proteins that are responsible for most if not all cellular functions, to the noncoding regions that are now known to provide regulatory functions. Proteomics initiatives help to decipher the role of post-translation modifications on the protein structures and provide maps of protein-protein interactions, while functional genomics is the field that attempts to make use of the data produced by these projects to understand protein functions. The biggest challenge today is to assimilate the wealth of information provided by these initiatives into a conceptual framework that will help us decipher life. For example, the current views of the relationship between protein structure and function remain fragmented. We know of their sequences, more and more about their structures, we have information on their biological activities, but we have difficulties connecting this dotted line into an informed whole. We lack the experimental and computational tools for directly studying protein structure, function, and dynamics at the molecular and supra-molecular levels. In this chapter, we review some of the current developments in building the computational tools that are needed, focusing on the role that geometry and topology play in these efforts. One of our goals is to raise the general awareness about the importance of geometric methods in elucidating the mysterious foundations of our very existence. Another goal is the broadening of what we consider a geometric algorithm. There is plenty of valuable no-man’s-land between combinatorial and numerical algorithms, and it seems opportune to explore this land with a computational-geometric frame of mind.}, author = {Edelsbrunner, Herbert and Koehl, Patrice}, booktitle = {Handbook of Discrete and Computational Geometry, Third Edition}, editor = {Toth, Csaba and O'Rourke, Joseph and Goodman, Jacob}, pages = {1709 -- 1735}, publisher = {Taylor & Francis}, title = {{Computational topology for structural molecular biology}}, doi = {10.1201/9781315119601}, year = {2017}, } @article{840, abstract = {Heavy holes confined in quantum dots are predicted to be promising candidates for the realization of spin qubits with long coherence times. Here we focus on such heavy-hole states confined in germanium hut wires. By tuning the growth density of the latter we can realize a T-like structure between two neighboring wires. Such a structure allows the realization of a charge sensor, which is electrostatically and tunnel coupled to a quantum dot, with charge-transfer signals as high as 0.3 e. By integrating the T-like structure into a radiofrequency reflectometry setup, single-shot measurements allowing the extraction of hole tunneling times are performed. The extracted tunneling times of less than 10 μs are attributed to the small effective mass of Ge heavy-hole states and pave the way toward projective spin readout measurements.}, author = {Vukusic, Lada and Kukucka, Josip and Watzinger, Hannes and Katsaros, Georgios}, issn = {1530-6984}, journal = {Nano Letters}, number = {9}, pages = {5706 -- 5710}, publisher = {American Chemical Society}, title = {{Fast hole tunneling times in germanium hut wires probed by single-shot reflectometry}}, doi = {10.1021/acs.nanolett.7b02627}, volume = {17}, year = {2017}, }