@article{792, abstract = {The chaotic dynamics of low-dimensional systems, such as Lorenz or Rössler flows, is guided by the infinity of periodic orbits embedded in their strange attractors. Whether this is also the case for the infinite-dimensional dynamics of Navier–Stokes equations has long been speculated, and is a topic of ongoing study. Periodic and relative periodic solutions have been shown to be involved in transitions to turbulence. Their relevance to turbulent dynamics – specifically, whether periodic orbits play the same role in high-dimensional nonlinear systems like the Navier–Stokes equations as they do in lower-dimensional systems – is the focus of the present investigation. We perform here a detailed study of pipe flow relative periodic orbits with energies and mean dissipations close to turbulent values. We outline several approaches to reduction of the translational symmetry of the system. We study pipe flow in a minimal computational cell at Re=2500, and report a library of invariant solutions found with the aid of the method of slices. Detailed study of the unstable manifolds of a sample of these solutions is consistent with the picture that relative periodic orbits are embedded in the chaotic saddle and that they guide the turbulent dynamics.}, author = {Budanur, Nazmi B and Short, Kimberly and Farazmand, Mohammad and Willis, Ashley and Cvitanović, Predrag}, issn = {00221120}, journal = {Journal of Fluid Mechanics}, pages = {274 -- 301}, publisher = {Cambridge University Press}, title = {{Relative periodic orbits form the backbone of turbulent pipe flow}}, doi = {10.1017/jfm.2017.699}, volume = {833}, year = {2017}, } @article{793, abstract = {Let P be a finite point set in the plane. A cordinary triangle in P is a subset of P consisting of three non-collinear points such that each of the three lines determined by the three points contains at most c points of P . Motivated by a question of Erdös, and answering a question of de Zeeuw, we prove that there exists a constant c > 0such that P contains a c-ordinary triangle, provided that P is not contained in the union of two lines. Furthermore, the number of c-ordinary triangles in P is Ω(| P |). }, author = {Fulek, Radoslav and Mojarrad, Hossein and Naszódi, Márton and Solymosi, József and Stich, Sebastian and Szedlák, May}, issn = {09257721}, journal = {Computational Geometry: Theory and Applications}, pages = {28 -- 31}, publisher = {Elsevier}, title = {{On the existence of ordinary triangles}}, doi = {10.1016/j.comgeo.2017.07.002}, volume = {66}, year = {2017}, } @article{794, abstract = {We show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle.}, author = {Fulek, Radoslav}, journal = {Computational Geometry: Theory and Applications}, pages = {1 -- 13}, publisher = {Elsevier}, title = {{C-planarity of embedded cyclic c-graphs}}, doi = {10.1016/j.comgeo.2017.06.016}, volume = {66}, year = {2017}, } @article{795, abstract = {We introduce a common generalization of the strong Hanani–Tutte theorem and the weak Hanani–Tutte theorem: if a graph G has a drawing D in the plane where every pair of independent edges crosses an even number of times, then G has a planar drawing preserving the rotation of each vertex whose incident edges cross each other evenly in D. The theorem is implicit in the proof of the strong Hanani–Tutte theorem by Pelsmajer, Schaefer and Štefankovič. We give a new, somewhat simpler proof.}, author = {Fulek, Radoslav and Kynčl, Jan and Pálvölgyi, Dömötör}, issn = {10778926}, journal = {Electronic Journal of Combinatorics}, number = {3}, publisher = {International Press}, title = {{Unified Hanani Tutte theorem}}, doi = {10.37236/6663}, volume = {24}, year = {2017}, } @article{796, abstract = {We present the fabrication and characterization of an aluminum transmon qubit on a silicon-on-insulator substrate. Key to the qubit fabrication is the use of an anhydrous hydrofluoric vapor process which selectively removes the lossy silicon oxide buried underneath the silicon device layer. For a 5.6 GHz qubit measured dispersively by a 7.1 GHz resonator, we find T1 = 3.5 μs and T∗2 = 2.2 μs. This process in principle permits the co-fabrication of silicon photonic and mechanical elements, providing a route towards chip-scale integration of electro-opto-mechanical transducers for quantum networking of superconducting microwave quantum circuits. The additional processing steps are compatible with established fabrication techniques for aluminum transmon qubits on silicon.}, author = {Keller, Andrew J and Dieterle, Paul and Fang, Michael and Berger, Brett and Fink, Johannes M and Painter, Oskar}, issn = {00036951}, journal = {Applied Physics Letters}, number = {4}, publisher = {American Institute of Physics}, title = {{Al transmon qubits on silicon on insulator for quantum device integration}}, doi = {10.1063/1.4994661}, volume = {111}, year = {2017}, } @article{797, abstract = {Phasenübergänge helfen beim Verständnis von Vielteilchensystemen in der Festkörperphysik und Fluiddynamik bis hin zur Teilchenphysik. Unserer internationalen Kollaboration ist es gelungen, einen neuartigen Phasenübergang in einem Quantensystem zu beobachten [1]. In einem Mikrowellenresonator konnte erstmals die spontane Zustandsänderung von undurchsichtig zu transparent nachgewiesen werden.}, author = {Fink, Johannes M}, journal = {Physik in unserer Zeit}, number = {3}, pages = {111 -- 113}, publisher = {Wiley}, title = {{Photonenblockade aufgelöst}}, doi = {10.1002/piuz.201770305}, volume = {48}, year = {2017}, } @article{798, abstract = {Nonreciprocal circuit elements form an integral part of modern measurement and communication systems. Mathematically they require breaking of time-reversal symmetry, typically achieved using magnetic materials and more recently using the quantum Hall effect, parametric permittivity modulation or Josephson nonlinearities. Here we demonstrate an on-chip magnetic-free circulator based on reservoir-engineered electromechanic interactions. Directional circulation is achieved with controlled phase-sensitive interference of six distinct electro-mechanical signal conversion paths. The presented circulator is compact, its silicon-on-insulator platform is compatible with both superconducting qubits and silicon photonics, and its noise performance is close to the quantum limit. With a high dynamic range, a tunable bandwidth of up to 30 MHz and an in situ reconfigurability as beam splitter or wavelength converter, it could pave the way for superconducting qubit processors with multiplexed on-chip signal processing and readout.}, author = {Barzanjeh, Shabir and Wulf, Matthias and Peruzzo, Matilda and Kalaee, Mahmoud and Dieterle, Paul and Painter, Oskar and Fink, Johannes M}, issn = {20411723}, journal = {Nature Communications}, number = {1}, publisher = {Nature Publishing Group}, title = {{Mechanical on chip microwave circulator}}, doi = {10.1038/s41467-017-01304-x}, volume = {8}, year = {2017}, } @article{799, abstract = {Membrane traffic at the trans-Golgi network (TGN) is crucial for correctly distributing various membrane proteins to their destination. Polarly localized auxin efflux proteins, including PIN-FORMED1 (PIN1), are dynamically transported between the endosomes and the plasma membrane (PM) in the plant cells. The intracellular trafficking of PIN1 protein is sensitive to a fungal toxin brefeldin A (BFA), which is known to inhibit guanine-nucleotide exchange factors for ADP ribosylation factors (ARF GEFs) such as GNOM. However, the molecular details of the BFA-sensitive trafficking pathway have not been revealed fully. In a previous study, we have identified an Arabidopsis mutant BFA-visualized endocytic trafficking defective 3 (ben3) which exhibited reduced sensitivity to BFA in terms of BFA-induced intracellular PIN1 agglomeration. Here, we show that BEN3 encodes a member of BIG family ARF GEFs, BIG2. Fluorescent proteins tagged BEN3/BIG2 co-localized with markers for TGN / early endosome (EE). Inspection of conditionally induced de novo synthesized PIN1 confirmed that its secretion to the PM is BFA-sensitive and established BEN3/BIG2 as a crucial component of this BFA action at the level of TGN/EE. Furthermore, ben3 mutation alleviated BFA-induced agglomeration of another TGN-localized ARF GEF BEN1/MIN7. Taken together our results suggest that BEN3/BIG2 is an ARF GEF component, which confers BFA sensitivity to the TGN/EE in Arabidopsis.}, author = {Kitakura, Saeko and Adamowski, Maciek and Matsuura, Yuki and Santuari, Luca and Kouno, Hirotaka and Arima, Kohei and Hardtke, Christian and Friml, Jirí and Kakimoto, Tatsuo and Tanaka, Hirokazu}, issn = {00320781}, journal = {Plant and Cell Physiology}, number = {10}, publisher = {Oxford University Press}, title = {{BEN3/BIG2 ARF GEF is involved in brefeldin a-sensitive trafficking at the trans-Golgi network/early endosome in Arabidopsis thaliana}}, doi = {10.1093/pcp/pcx118}, volume = {58}, year = {2017}, } @article{800, abstract = {Gamma oscillations (30–150 Hz) in neuronal networks are associated with the processing and recall of information. We measured local field potentials in the dentate gyrus of freely moving mice and found that gamma activity occurs in bursts, which are highly heterogeneous in their spatial extensions, ranging from focal to global coherent events. Synaptic communication among perisomatic-inhibitory interneurons (PIIs) is thought to play an important role in the generation of hippocampal gamma patterns. However, how neuronal circuits can generate synchronous oscillations at different spatial scales is unknown. We analyzed paired recordings in dentate gyrus slices and show that synaptic signaling at interneuron-interneuron synapses is distance dependent. Synaptic strength declines whereas the duration of inhibitory signals increases with axonal distance among interconnected PIIs. Using neuronal network modeling, we show that distance-dependent inhibition generates multiple highly synchronous focal gamma bursts allowing the network to process complex inputs in parallel in flexibly organized neuronal centers.}, author = {Strüber, Michael and Sauer, Jonas and Jonas, Peter M and Bartos, Marlene}, issn = {20411723}, journal = {Nature Communications}, number = {1}, publisher = {Nature Publishing Group}, title = {{Distance-dependent inhibition facilitates focality of gamma oscillations in the dentate gyrus}}, doi = {10.1038/s41467-017-00936-3}, volume = {8}, year = {2017}, } @article{803, abstract = {Eukaryotic cells store their chromosomes in a single nucleus. This is important to maintain genomic integrity, as chromosomes packaged into separate nuclei (micronuclei) are prone to massive DNA damage. During mitosis, higher eukaryotes disassemble their nucleus and release individualized chromosomes for segregation. How numerous chromosomes subsequently reform a single nucleus has remained unclear. Using image-based screening of human cells, we identified barrier-to-autointegration factor (BAF) as a key factor guiding membranes to form a single nucleus. Unexpectedly, nuclear assembly does not require BAF?s association with inner nuclear membrane proteins but instead relies on BAF?s ability to bridge distant DNA sites. Live-cell imaging and in vitro reconstitution showed that BAF enriches around the mitotic chromosome ensemble to induce a densely cross-bridged chromatin layer that is mechanically stiff and limits membranes to the surface. Our study reveals that BAF-mediated changes in chromosome mechanics underlie nuclear assembly with broad implications for proper genome function.}, author = {Samwer, Matthias and Schneider, Maximilian and Hoefler, Rudolf and Schmalhorst, Philipp S and Jude, Julian and Zuber, Johannes and Gerlic, Daniel}, issn = {00928674}, journal = {Cell}, number = {5}, pages = {956 -- 972}, publisher = {Cell Press}, title = {{DNA cross-bridging shapes a single nucleus from a set of mitotic chromosomes}}, doi = {10.1016/j.cell.2017.07.038}, volume = {170}, year = {2017}, } @article{804, abstract = {Polysaccharides (carbohydrates) are key regulators of a large number of cell biological processes. However, precise biochemical or genetic manipulation of these often complex structures is laborious and hampers experimental structure–function studies. Molecular Dynamics (MD) simulations provide a valuable alternative tool to generate and test hypotheses on saccharide function. Yet, currently used MD force fields often overestimate the aggregation propensity of polysaccharides, affecting the usability of those simulations. Here we tested MARTINI, a popular coarse-grained (CG) force field for biological macromolecules, for its ability to accurately represent molecular forces between saccharides. To this end, we calculated a thermodynamic solution property, the second virial coefficient of the osmotic pressure (B22). Comparison with light scattering experiments revealed a nonphysical aggregation of a prototypical polysaccharide in MARTINI, pointing at an imbalance of the nonbonded solute–solute, solute–water, and water–water interactions. This finding also applies to smaller oligosaccharides which were all found to aggregate in simulations even at moderate concentrations, well below their solubility limit. Finally, we explored the influence of the Lennard-Jones (LJ) interaction between saccharide molecules and propose a simple scaling of the LJ interaction strength that makes MARTINI more reliable for the simulation of saccharides.}, author = {Schmalhorst, Philipp S and Deluweit, Felix and Scherrers, Roger and Heisenberg, Carl-Philipp J and Sikora, Mateusz K}, issn = {15499618}, journal = {Journal of Chemical Theory and Computation}, number = {10}, pages = {5039 -- 5053}, publisher = {American Chemical Society}, title = {{Overcoming the limitations of the MARTINI force field in simulations of polysaccharides}}, doi = {10.1021/acs.jctc.7b00374}, volume = {13}, year = {2017}, } @article{805, abstract = {During corticogenesis, distinct classes of neurons are born from progenitor cells located in the ventricular and subventricular zones, from where they migrate towards the pial surface to assemble into highly organized layer-specific circuits. However, the precise and coordinated transcriptional network activity defining neuronal identity is still not understood. Here, we show that genetic depletion of the basic helix-loop-helix (bHLH) transcription factor E2A splice variant E47 increased the number of Tbr1-positive deep layer and Satb2-positive upper layer neurons at E14.5, while depletion of the alternatively spliced E12 variant did not affect layer-specific neurogenesis. While ChIP-Seq identified a big overlap for E12- and E47-specific binding sites in embryonic NSCs, including sites at the cyclin-dependent kinase inhibitor (CDKI) Cdkn1c gene locus, RNA-Seq revealed a unique transcriptional regulation by each splice variant. E47 activated the expression of the CDKI Cdkn1c through binding to a distal enhancer. Finally, overexpression of E47 in embryonic NSCs in vitro impaired neurite outgrowth and E47 overexpression in vivo by in utero electroporation disturbed proper layer-specific neurogenesis and upregulated p57(KIP2) expression. Overall, this study identified E2A target genes in embryonic NSCs and demonstrates that E47 regulates neuronal differentiation via p57(KIP2).}, author = {Pfurr, Sabrina and Chu, Yu and Bohrer, Christian and Greulich, Franziska and Beattie, Robert J and Mammadzada, Könül and Hils, Miriam and Arnold, Sebastian and Taylor, Verdon and Schachtrup, Kristina and Uhlenhaut, N Henriette and Schachtrup, Christian}, journal = {Development}, pages = {3917 -- 3931}, publisher = {Company of Biologists}, title = {{The E2A splice variant E47 regulates the differentiation of projection neurons via p57(KIP2) during cortical development}}, doi = {10.1242/dev.145698}, volume = {144}, year = {2017}, } @article{807, abstract = {On January the 1st, 2016 a new agreement between 32 Austrian scientific libraries and the publisher Springer took its effect: this deal covers accessing the licensed content on the one hand, and publishing open access on the other hand. More than 1000 papers by Austrian authors were published open access at Springer in the first year alone. The working group "Springer Compact Evaluierung" made the data for these articles available via the platform OpenAPC and would like to use this opportunity to give a short account of what this publishing agreement actually entails and the working group intends to do.}, author = {Andrae, Magdalena and Villányi, Márton}, issn = {10222588}, journal = {Mitteilungen der Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare}, number = {2}, pages = {274 -- 280}, publisher = {VÖB}, title = {{Der Springer Compact-Deal – Ein erster Einblick in die Evaluierung einer Offsetting-Vereinbarung}}, doi = {10.31263/voebm.v70i2.1898}, volume = {70}, year = {2017}, } @phdthesis{818, abstract = {Antibiotics have diverse effects on bacteria, including massive changes in bacterial gene expression. Whereas the gene expression changes under many antibiotics have been measured, the temporal organization of these responses and their dependence on the bacterial growth rate are unclear. As described in Chapter 1, we quantified the temporal gene expression changes in the bacterium Escherichia coli in response to the sudden exposure to antibiotics using a fluorescent reporter library and a robotic system. Our data show temporally structured gene expression responses, with response times for individual genes ranging from tens of minutes to several hours. We observed that many stress response genes were activated in response to antibiotics. As certain stress responses cross-protect bacteria from other stressors, we then asked whether cellular responses to antibiotics have a similar protective role in Chapter 2. Indeed, we found that the trimethoprim-induced acid stress response protects bacteria from subsequent acid stress. We combined microfluidics with time-lapse imaging to monitor survival, intracellular pH, and acid stress response in single cells. This approach revealed that the variable expression of the acid resistance operon gadBC strongly correlates with single-cell survival time. Cells with higher gadBC expression following trimethoprim maintain higher intracellular pH and survive the acid stress longer. Overall, we provide a way to identify single-cell cross-protection between antibiotics and environmental stressors from temporal gene expression data, and show how antibiotics can increase bacterial fitness in changing environments. While gene expression changes to antibiotics show a clear temporal structure at the population-level, it is unclear whether this clear temporal order is followed by every single cell. Using dual-reporter strains described in Chapter 3, we measured gene expression dynamics of promoter pairs in the same cells using microfluidics and microscopy. Chapter 4 shows that the oxidative stress response and the DNA stress response showed little timing variability and a clear temporal order under the antibiotic nitrofurantoin. In contrast, the acid stress response under trimethoprim ran independently from all other activated response programs including the DNA stress response, which showed particularly high timing variability in this stress condition. In summary, this approach provides insight into the temporal organization of gene expression programs at the single-cell level and suggests dependencies between response programs and the underlying variability-introducing mechanisms. Altogether, this work advances our understanding of the diverse effects that antibiotics have on bacteria. These results were obtained by taking into account gene expression dynamics, which allowed us to identify general principles, molecular mechanisms, and dependencies between genes. Our findings may have implications for infectious disease treatments, and microbial communities in the human body and in nature. }, author = {Mitosch, Karin}, issn = {2663-337X}, pages = {113}, publisher = {Institute of Science and Technology Austria}, title = {{Timing, variability and cross-protection in bacteria – insights from dynamic gene expression responses to antibiotics}}, doi = {10.15479/AT:ISTA:th_862}, year = {2017}, } @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 = {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{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}, }