@article{1294, abstract = {We study controller synthesis problems for finite-state Markov decision processes, where the objective is to optimize the expected mean-payoff performance and stability (also known as variability in the literature). We argue that the basic notion of expressing the stability using the statistical variance of the mean payoff is sometimes insufficient, and propose an alternative definition. We show that a strategy ensuring both the expected mean payoff and the variance below given bounds requires randomization and memory, under both the above definitions. We then show that the problem of finding such a strategy can be expressed as a set of constraints.}, author = {Brázdil, Tomáš and Chatterjee, Krishnendu and Forejt, Vojtěch and Kučera, Antonín}, journal = {Journal of Computer and System Sciences}, pages = {144 -- 170}, publisher = {Elsevier}, title = {{Trading performance for stability in Markov decision processes}}, doi = {10.1016/j.jcss.2016.09.009}, volume = {84}, year = {2017}, } @inproceedings{13160, abstract = {Transforming deterministic ω -automata into deterministic parity automata is traditionally done using variants of appearance records. We present a more efficient variant of this approach, tailored to Rabin automata, and several optimizations applicable to all appearance records. We compare the methods experimentally and find out that our method produces smaller automata than previous approaches. Moreover, the experiments demonstrate the potential of our method for LTL synthesis, using LTL-to-Rabin translators. It leads to significantly smaller parity automata when compared to state-of-the-art approaches on complex formulae.}, author = {Kretinsky, Jan and Meggendorfer, Tobias and Waldmann, Clara and Weininger, Maximilian}, booktitle = {Tools and Algorithms for the Construction and Analysis of Systems}, isbn = {9783662545768}, issn = {1611-3349}, location = {Uppsala, Sweden}, pages = {443--460}, publisher = {Springer}, title = {{Index appearance record for transforming Rabin automata into parity automata}}, doi = {10.1007/978-3-662-54577-5_26}, volume = {10205}, 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 = {00278424}, 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{823, abstract = {The resolution of a linear system with positive integer variables is a basic yet difficult computational problem with many applications. We consider sparse uncorrelated random systems parametrised by the density c and the ratio α=N/M between number of variables N and number of constraints M. By means of ensemble calculations we show that the space of feasible solutions endows a Van-Der-Waals phase diagram in the plane (c, α). We give numerical evidence that the associated computational problems become more difficult across the critical point and in particular in the coexistence region.}, author = {Colabrese, Simona and De Martino, Daniele and Leuzzi, Luca and Marinari, Enzo}, issn = {17425468}, journal = { Journal of Statistical Mechanics: Theory and Experiment}, number = {9}, publisher = {IOPscience}, title = {{Phase transitions in integer linear problems}}, doi = {10.1088/1742-5468/aa85c3}, volume = {2017}, 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 = {00221120}, 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}, } @article{825, abstract = {What data is needed about data? Describing the process to answer this question for the institutional data repository IST DataRep.}, author = {Petritsch, Barbara}, issn = {10222588}, journal = {Mitteilungen der Vereinigung Österreichischer Bibliothekarinnen & Bibliothekare}, number = {2}, pages = {200 -- 207}, publisher = {VÖB}, title = {{Metadata for research data in practice}}, doi = {10.31263/voebm.v70i2.1678}, volume = {70}, 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 = {03029743}, 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{834, abstract = {Thermal and many-body localized phases are separated by a dynamical phase transition of a new kind. We analyze the distribution of off-diagonal matrix elements of local operators across this transition in two different models of disordered spin chains. We show that the behavior of matrix elements can be used to characterize the breakdown of thermalization and to extract the many-body Thouless energy. We find that upon increasing the disorder strength the system enters a critical region around the many-body localization transition. The properties of the system in this region are: (i) the Thouless energy becomes smaller than the level spacing, (ii) the matrix elements show critical dependence on the energy difference, and (iii) the matrix elements, viewed as amplitudes of a fictitious wave function, exhibit strong multifractality. This critical region decreases with the system size, which we interpret as evidence for a diverging correlation length at the many-body localization transition. Our findings show that the correlation length becomes larger than the accessible system sizes in a broad range of disorder strength values and shed light on the critical behavior near the many-body localization transition.}, author = {Serbyn, Maksym and Zlatko, Papic and Abanin, Dmitry}, issn = {24699950}, journal = {Physical Review B - Condensed Matter and Materials Physics}, number = {10}, publisher = {American Physical Society}, title = {{Thouless energy and multifractality across the many-body localization transition}}, doi = {10.1103/PhysRevB.96.104201}, volume = {96}, 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}, }