Air temperature distribution and energy-balance modelling of a debris-covered glacier - SHAW, THOMAS E.; BROCK, BEN W.; FYFFE, CATRIONA L.; Pellicciotti, Francesca; RUTTER, NICK; DIOTRI, FABRIZIO (Journal of Glaciology)
Near-surface air temperature is an important determinant of the surface energy balance of glaciers and is often represented by a constant linear temperature gradients (TGs) in models. Spatio-temporal variability in 2 m air temperature was measured across the debris-covered Miage Glacier, Italy, over an 89 d period during the 2014 ablation season using a network of 19 stations. Air temperature was found to be strongly dependent upon elevation for most stations, even under varying meteorological conditions and at different times of day, and its spatial variability was well explained by a locally derived mean linear TG (MG–TG) of −0.0088°C m−1. However, local temperature depressions occurred over areas of very thin or patchy debris cover. The MG–TG, together with other air TGs, extrapolated from both on- and off-glacier sites, were applied in a distributed energy-balance model. Compared with piecewise air temperature extrapolation from all on-glacier stations, modelled ablation, using the MG–TG, increased by <1%, increasing to >4% using the environmental ‘lapse rate’. Ice melt under thick debris was relatively insensitive to air temperature, while the effects of different temperature extrapolation methods were strongest at high elevation sites of thin and patchy debris cover.
Keywords: Earth-Surface Processes

A physically based 3‐D model of ice cliff evolution over debris‐covered glaciers - Buri, Pascal; Miles, Evan S.; Steiner, Jakob F.; Immerzeel, Walter W.; Wagnon, Patrick; Pellicciotti, Francesca (Journal of Geophysical Research: Earth Surface)
We use high-resolution digital elevation models (DEMs) from unmanned aerial vehicle (UAV) surveys to document the evolution of four ice cliffs on the debris-covered tongue of Lirung Glacier, Nepal, over one ablation season. Observations show that out of four cliffs, three different patterns of evolution emerge: (i) reclining cliffs that flatten during the ablation season; (ii) stable cliffs that maintain a self-similar geometry; and (iii) growing cliffs, expanding laterally. We use the insights from this unique data set to develop a 3-D model of cliff backwasting and evolution that is validated against observations and an independent data set of volume losses. The model includes ablation at the cliff surface driven by energy exchange with the atmosphere, reburial of cliff cells by surrounding debris, and the effect of adjacent ponds. The cliff geometry is updated monthly to account for the modifications induced by each of those processes. Model results indicate that a major factor affecting the survival of steep cliffs is the coupling with ponded water at its base, which prevents progressive flattening and possible disappearance of a cliff. The radial growth observed at one cliff is explained by higher receipts of longwave and shortwave radiation, calculated taking into account atmospheric fluxes, shading, and the emission of longwave radiation from debris surfaces. The model is a clear step forward compared to existing static approaches that calculate atmospheric melt over an invariant cliff geometry and can be used for long-term simulations of cliff evolution and to test existing hypotheses about cliffs' survival.
Keywords: Earth-Surface Processes; Geophysics

Heterogeneous glacier thinning patterns over the last 40 years in Langtang Himal, Nepal - Ragettli, Silvan; Bolch, Tobias; Pellicciotti, Francesca (The Cryosphere)
This study presents volume and mass changes of seven (five partially debris-covered, two debris-free) glaciers in the upper Langtang catchment in Nepal. We use a digital elevation model (DEM) from 1974 stereo Hexagon satellite data and seven DEMs derived from 2006–2015 stereo or tri-stereo satellite imagery (e.g., SPOT6/7). The availability of multiple independent DEM differences allows the identification of a robust signal and narrowing down of the uncertainty about recent volume changes. The volume changes calculated over several multiyear periods between 2006 and 2015 consistently indicate that glacier thinning has accelerated with respect to the period 1974–2006. We calculate an ensemble-mean elevation change rate of –0.45 ± 0.18 m a−1 for 2006–2015, while for the period 1974–2006 we compute a rate of −0.24 ± 0.08 m a−1. However, the behavior of glaciers in the study area is heterogeneous, and the presence or absence of debris does not seem to be a good predictor for mass balance trends. Debris-covered tongues have nonlinear thinning profiles, and we show that recent accelerations in thinning correlate with the presence of supraglacial cliffs and lakes. At stagnating glacier areas near the glacier front, however, thinning rates decreased with time or remained constant. The April 2015 Nepal earthquake triggered large avalanches in the study catchment. Analysis of two post-earthquake DEMs revealed that the avalanche deposit volumes remaining 6 months after the earthquake are negligible in comparison to 2006–2015 elevation changes. However, the deposits compensate about 40 % the mass loss of debris-covered tongues of 1 average year.
Keywords: Earth-Surface Processes; Water Science and Technology

DNA demethylation is initiated in the central cells of Arabidopsis and rice - Park, Kyunghyuk; Kim, M. Yvonne; Vickers, Martin; Park, Jin-Sup; Hyun, Youbong; Okamoto, Takashi; Zilberman, Daniel; Fischer, Robert L.; Feng, Xiaoqi; Choi, Yeonhee; Scholten, Stefan (Proceedings of the National Academy of Sciences)
Cytosine methylation is a DNA modification with important regulatory functions in eukaryotes. In flowering plants, sexual reproduction is accompanied by extensive DNA demethylation, which is required for proper gene expression in the endosperm, a nutritive extraembryonic seed tissue. Endosperm arises from a fusion of a sperm cell carried in the pollen and a female central cell. Endosperm DNA demethylation is observed specifically on the chromosomes inherited from the central cell in Arabidopsis thaliana, rice, and maize, and requires the DEMETER DNA demethylase in Arabidopsis. DEMETER is expressed in the central cell before fertilization, suggesting that endosperm demethylation patterns are inherited from the central cell. Down-regulation of the MET1 DNA methyltransferase has also been proposed to contribute to central cell demethylation. However, with the exception of three maize genes, central cell DNA methylation has not been directly measured, leaving the origin and mechanism of endosperm demethylation uncertain. Here, we report genome-wide analysis of DNA methylation in the central cells of Arabidopsis and rice—species that diverged 150 million years ago—as well as in rice egg cells. We find that DNA demethylation in both species is initiated in central cells, which requires DEMETER in Arabidopsis. However, we do not observe a global reduction of CG methylation that would be indicative of lowered MET1 activity; on the contrary, CG methylation efficiency is elevated in female gametes compared with nonsexual tissues. Our results demonstrate that locus-specific, active DNA demethylation in the central cell is the origin of maternal chromosome hypomethylation in the endosperm.
Keywords: Multidisciplinary

Arabidopsis male sexual lineage exhibits more robust maintenance of CG methylation than somatic tissues - Hsieh, Ping-Hung; He, Shengbo; Buttress, Toby; Gao, Hongbo; Couchman, Matthew; Fischer, Robert L.; Zilberman, Daniel; Feng, Xiaoqi (Proceedings of the National Academy of Sciences)
Cytosine DNA methylation regulates the expression of eukaryotic genes and transposons. Methylation is copied by methyltransferases after DNA replication, which results in faithful transmission of methylation patterns during cell division and, at least in flowering plants, across generations. Transgenerational inheritance is mediated by a small group of cells that includes gametes and their progenitors. However, methylation is usually analyzed in somatic tissues that do not contribute to the next generation, and the mechanisms of transgenerational inheritance are inferred from such studies. To gain a better understanding of how DNA methylation is inherited, we analyzed purified Arabidopsis thaliana sperm and vegetative cells-the cell types that comprise pollen-with mutations in the DRM, CMT2, and CMT3 methyltransferases. We find that DNA methylation dependency on these enzymes is similar in sperm, vegetative cells, and somatic tissues, although DRM activity extends into heterochromatin in vegetative cells, likely reflecting transcription of heterochromatic transposons in this cell type. We also show that lack of histone H1, which elevates heterochromatic DNA methylation in somatic tissues, does not have this effect in pollen. Instead, levels of CG methylation in wild-type sperm and vegetative cells, as well as in wild-type microspores from which both pollen cell types originate, are substantially higher than in wild-type somatic tissues and similar to those of H1-depleted roots. Our results demonstrate that the mechanisms of methylation maintenance are similar between pollen and somatic cells, but the efficiency of CG methylation is higher in pollen, allowing methylation patterns to be accurately inherited across generations.

High performance computing at IST Austria: Modelling the human hippocampus - Schlögl, Alois; Stadlbauer, Stephan (AHPC16 - Austrian HPC Meeting 2016)

Controlling the lifetimes of dynamic nanoparticle aggregates by spiropyran functionalization - Kundu, Pintu K.; Das, Sanjib; Ahrens, Johannes; Klajn, Rafal (Nanoscale)
Novel light-responsive nanoparticles were synthesized by decorating the surfaces of gold and silver nanoparticles with a nitrospiropyran molecular photoswitch. Upon exposure to UV light in nonpolar solvents, these nanoparticles self-assembled to afford spherical aggregates, which disassembled rapidly when the UV stimulus was turned off. The sizes of these aggregates depended on the nanoparticle concentration, and their lifetimes could be controlled by adjusting the surface concentration of nitrospiropyran on the nanoparticles. The conformational flexibility of nitrospiropyran, which was altered by modifying the structure of the background ligand, had a profound impact on the self-assembly process. By coating the nanoparticles with a spiropyran lacking the nitro group, a conceptually different self-assembly system, relying on a reversible proton transfer, was realized. The resulting particles spontaneously (in the dark) assembled into aggregates that could be readily disassembled upon exposure to blue light.
Keywords: General Materials Science

Inside cover: Reversible photoisomerization of spiropyran on the surfaces of Au25 nanoclusters (ChemPhysChem 12/2016) - Udayabhaskararao, T.; Kundu, Pintu K.; Ahrens, Johannes; Klajn, Rafal (ChemPhysChem)
The Inside Cover picture illustrates the fluorescent properties of a gold nanocluster functionalized with several copies of a red-emitting merocyanine (image by Ella Marushchenko). The red fluorescence can be turned on and off reversibly by using an external stimulus.
Keywords: Physical and Theoretical Chemistry; Atomic and Molecular Physics; and Optics

Long-term stability of the HR 8799 planetary system without resonant lock - Götberg, Ylva Louise Linsdotter; Davies, Melvyn B.; Mustill, Alexander J.; Johansen, Anders; Church, Ross P. (Astronomy & Astrophysics)
HR 8799 is a star accompanied by four massive planets on wide orbits. The observed planetary configuration has been shown to be unstable on a timescale much shorter than the estimated age of the system (~30 Myr) unless the planets are locked into mean motion resonances. This condition is characterised by small-amplitude libration of one or more resonant angles that stabilise the system by preventing close encounters. We simulate planetary systems similar to the HR 8799 planetary system, exploring the parameter space in separation between the orbits, planetary masses and distance from the Sun to the star. We find systems that look like HR 8799 and remain stable for longer than the estimated age of HR 8799. None of our systems are forced into resonances. We find, with nominal masses (Mb = 5 MJup and Mc,d,e = 7 MJup) and in a narrow range of orbit separations, that 5 of 100 systems match the observations and lifetime. Considering a broad range of orbit separations, we find 12 of 900 similar systems. The systems survive significantly longer because of their slightly increased initial orbit separations compared to assuming circular orbits from the observed positions. A small increase in separation leads to a significant increase in survival time. The low eccentricity the orbits develop from gravitational interaction is enough for the planets to match the observations. With lower masses, but still comfortably within the estimated planet mass uncertainty, we find 18 of 100 matching and long-lived systems in a narrow orbital separation range. In the broad separation range, we find 82 of 900 matching systems. Our results imply that the planets in the HR 8799 system do not have to be in strong mean motion resonances. We also investigate the future of wide-orbit planetary systems using our HR 8799 analogues. We find that 80% of the systems have two planets left after strong planet-planet scattering and these are on eccentric orbits with semi-major axes of a1 ~ 10 AU and a2 ~ 30−1000 AU. We speculate that other wide-orbit planetary systems, such as AB Pic and HD 106906, are the remnants of HR 8799 analogues that underwent close encounters and dynamical instability.
Keywords: Space and Planetary Science; Astronomy and Astrophysics

Dynamic resource allocation games - Avni, Guy; Henzinger, Thomas A; Kupferman, Orna
In resource allocation games, selfish players share resources that are needed in order to fulfill their objectives. The cost of using a resource depends on the load on it. In the traditional setting, the players make their choices concurrently and in one-shot. That is, a strategy for a player is a subset of the resources. We introduce and study dynamic resource allocation games. In this setting, the game proceeds in phases. In each phase each player chooses one resource. A scheduler dictates the order in which the players proceed in a phase, possibly scheduling several players to proceed concurrently. The game ends when each player has collected a set of resources that fulfills his objective. The cost for each player then depends on this set as well as on the load on the resources in it – we consider both congestion and cost-sharing games. We argue that the dynamic setting is the suitable setting for many applications in practice. We study the stability of dynamic resource allocation games, where the appropriate notion of stability is that of subgame perfect equilibrium, study the inefficiency incurred due to selfish behavior, and also study problems that are particular to the dynamic setting, like constraints on the order in which resources can be chosen or the problem of finding a scheduler that achieves stability.

Attosecond delays in molecular photoionization - Huppert, Martin; Jordan, Inga; Baykusheva, Denitsa Rangelova; von Conta, Aaron; Wörner, Hans Jakob (Physical Review Letters)
We report measurements of energy-dependent attosecond photoionization delays between the two outer-most valence shells of N2O and H2O. The combination of single-shot signal referencing with the use of different metal foils to filter the attosecond pulse train enables us to extract delays from congested spectra. Remarkably large delays up to 160 as are observed in N2O, whereas the delays in H2O are all smaller than 50 as in the photon-energy range of 20-40 eV. These results are interpreted by developing a theory of molecular photoionization delays. The long delays measured in N2O are shown to reflect the population of molecular shape resonances that trap the photoelectron for a duration of up to ∼110 as. The unstructured continua of H2O result in much smaller delays at the same photon energies. Our experimental and theoretical methods make the study of molecular attosecond photoionization dynamics accessible.
Keywords: General Physics and Astronomy

In situ frequency gating and beam splitting of vacuum- and extreme-ultraviolet pulses - Rajeev, Rajendran; Hellwagner, Johannes; Schumacher, Anne; Jordan, Inga; Huppert, Martin; Tehlar, Andres; Niraghatam, Bhargava Ram; Baykusheva, Denitsa Rangelova; Lin, Nan; von Conta, Aaron; Wörner, Hans Jakob (Light: Science & Applications)
Monochromatization of high-harmonic sources has opened fascinating perspectives regarding time-resolved photoemission from all phases of matter. Such studies have invariably involved the use of spectral filters or spectrally dispersive optical components that are inherently lossy and technically complex. Here we present a new technique for the spectral selection of near-threshold harmonics and their spatial separation from the driving beams without any optical elements. We discover the existence of a narrow phase-matching gate resulting from the combination of the non-collinear generation geometry in an extended medium, atomic resonances and absorption. Our technique offers a filter contrast of up to 104 for the selected harmonics against the adjacent ones and offers multiple temporally synchronized beamlets in a single unified scheme. We demonstrate the selective generation of 133, 80 or 56 nm femtosecond pulses from a 400-nm driver, which is specific to the target gas. These results open new pathways towards phase-sensitive multi-pulse spectroscopy in the vacuum- and extreme-ultraviolet, and frequency-selective output coupling from enhancement cavities.
Keywords: Atomic and Molecular Physics; and Optics; Electronic; Optical and Magnetic Materials

Adaptation to parasites and costs of parasite resistance in mutator and nonmutator bacteria - Wielgoss, Sébastien; Bergmiller, Tobias; Bischofberger, Anna M.; Hall, Alex R. (Molecular Biology and Evolution)
Parasitism creates selection for resistance mechanisms in host populations and is hypothesized to promote increased host evolvability. However, the influence of these traits on host evolution when parasites are no longer present is unclear. We used experimental evolution and whole-genome sequencing of Escherichia coli to determine the effects of past and present exposure to parasitic viruses (phages) on the spread of mutator alleles, resistance, and bacterial competitive fitness. We found that mutator alleles spread rapidly during adaptation to any of four different phage species, and this pattern was even more pronounced with multiple phages present simultaneously. However, hypermutability did not detectably accelerate adaptation in the absence of phages and recovery of fitness costs associated with resistance. Several lineages evolved phage resistance through elevated mucoidy, and during subsequent evolution in phage-free conditions they rapidly reverted to nonmucoid, phage-susceptible phenotypes. Genome sequencing revealed that this phenotypic reversion was achieved by additional genetic changes rather than by genotypic reversion of the initial resistance mutations. Insertion sequence (IS) elements played a key role in both the acquisition of resistance and adaptation in the absence of parasites; unlike single nucleotide polymorphisms, IS insertions were not more frequent in mutator lineages. Our results provide a genetic explanation for rapid reversion of mucoidy, a phenotype observed in other bacterial species including human pathogens. Moreover, this demonstrates that the types of genetic change underlying adaptation to fitness costs, and consequently the impact of evolvability mechanisms such as increased point-mutation rates, depend critically on the mechanism of resistance.

Selective barriers to horizontal gene transfer - Acar, Hande
Horizontal gene transfer (HGT), the lateral acquisition of genes across existing species boundaries, is a major evolutionary force shaping microbial genomes that facilitates adaptation to new environments as well as resistance to antimicrobial drugs. As such, understanding the mechanisms and constraints that determine the outcomes of HGT events is crucial to understand the dynamics of HGT and to design better strategies to overcome the challenges that originate from it. Following the insertion and expression of a newly transferred gene, the success of an HGT event will depend on the fitness effect it has on the recipient (host) cell. Therefore, predicting the impact of HGT on the genetic composition of a population critically depends on the distribution of fitness effects (DFE) of horizontally transferred genes. However, to date, we have little knowledge of the DFE of newly transferred genes, and hence little is known about the shape and scale of this distribution. It is particularly important to better understand the selective barriers that determine the fitness effects of newly transferred genes. In spite of substantial bioinformatics efforts to identify horizontally transferred genes and selective barriers, a systematic experimental approach to elucidate the roles of different selective barriers in defining the fate of a transfer event has largely been absent. Similarly, although the fact that environment might alter the fitness effect of a horizontally transferred gene may seem obvious, little attention has been given to it in a systematic experimental manner. In this study, we developed a systematic experimental approach that consists of transferring 44 arbitrarily selected Salmonella typhimurium orthologous genes into an Escherichia coli host, and estimating the fitness effects of these transferred genes at a constant expression level by performing competition assays against the wild type. In chapter 2, we performed one-to-one competition assays between a mutant strain carrying a transferred gene and the wild type strain. By using flow cytometry we estimated selection coefficients for the transferred genes with a precision level of 10-3,and obtained the DFE of horizontally transferred genes. We then investigated if these fitness effects could be predicted by any of the intrinsic properties of the genes, namely, functional category, degree of complexity (protein-protein interactions), GC content, codon usage and length. Our analyses revealed that the functional category and length of the genes act as potential selective barriers. Finally, using the same procedure with the endogenous E. coli orthologs of these 44 genes, we demonstrated that gene dosage is the most prominent selective barrier to HGT. In chapter 3, using the same set of genes we investigated the role of environment on the success of HGT events. Under six different environments with different levels of stress we performed more complex competition assays, where we mixed all 44 mutant strains carrying transferred genes with the wild type strain. To estimate the fitness effects of genes relative to wild type we used next generation sequencing. We found that the DFEs of horizontally transferred genes are highly dependent on the environment, with abundant gene–by-environment interactions. Furthermore, we demonstrated a relationship between average fitness effect of a gene across all environments and its environmental variance, and thus its predictability. Finally, in spite of the fitness effects of genes being highly environment-dependent, we still observed a common shape of DFEs across all tested environments.

Approximation and convergence of the intrinsic volume - Edelsbrunner, Herbert; Pausinger, Florian (Advances in Mathematics)
We introduce a modification of the classic notion of intrinsic volume using persistence moments of height functions. Evaluating the modified first intrinsic volume on digital approximations of a compact body with smoothly embedded boundary in Rn, we prove convergence to the first intrinsic volume of the body as the resolution of the approximation improves. We have weaker results for the other modified intrinsic volumes, proving they converge to the corresponding intrinsic volumes of the n-dimensional unit ball.

Studying the complexities of transcriptional regulation - Rieckh, Georg
The process of gene expression is central to the modern understanding of how cellular systems function. In this process, a special kind of regulatory proteins, called transcription factors, are important to determine how much protein is produced from a given gene. As biological information is transmitted from transcription factor concentration to mRNA levels to amounts of protein, various sources of noise arise and pose limits to the fidelity of intracellular signaling. This thesis concerns itself with several aspects of stochastic gene expression: (i) the mathematical description of complex promoters responsible for the stochastic production of biomolecules, (ii) fundamental limits to information processing the cell faces due to the interference from multiple fluctuating signals, (iii) how the presence of gene expression noise influences the evolution of regulatory sequences, (iv) and tools for the experimental study of origins and consequences of cell-cell heterogeneity, including an application to bacterial stress response systems.

Optical functionalization of human class A orphan G-protein coupled receptors - Morri, Maurizio

Quantitative analysis of haptotactic cell migration - Schwarz, Jan
Directed cell migration is a hallmark feature, present in almost all multi-cellular organisms. Despite its importance, basic questions regarding force transduction or directional sensing are still heavily investigated. Directed migration of cells guided by immobilized guidance cues - haptotaxis - occurs in key-processes, such as embryonic development and immunity (Middleton et al., 1997; Nguyen et al., 2000; Thiery, 1984; Weber et al., 2013). Immobilized guidance cues comprise adhesive ligands, such as collagen and fibronectin (Barczyk et al., 2009), or chemokines - the main guidance cues for migratory leukocytes (Middleton et al., 1997; Weber et al., 2013). While adhesive ligands serve as attachment sites guiding cell migration (Carter, 1965), chemokines instruct haptotactic migration by inducing adhesion to adhesive ligands and directional guidance (Rot and Andrian, 2004; Schumann et al., 2010). Quantitative analysis of the cellular response to immobilized guidance cues requires in vitro assays that foster cell migration, offer accurate control of the immobilized cues on a subcellular scale and in the ideal case closely reproduce in vivo conditions. The exploration of haptotactic cell migration through design and employment of such assays represents the main focus of this work. Dendritic cells (DCs) are leukocytes, which after encountering danger signals such as pathogens in peripheral organs instruct naïve T-cells and consequently the adaptive immune response in the lymph node (Mellman and Steinman, 2001). To reach the lymph node from the periphery, DCs follow haptotactic gradients of the chemokine CCL21 towards lymphatic vessels (Weber et al., 2013). Questions about how DCs interpret haptotactic CCL21 gradients have not yet been addressed. The main reason for this is the lack of an assay that offers diverse haptotactic environments, hence allowing the study of DC migration as a response to different signals of immobilized guidance cue. In this work, we developed an in vitro assay that enables us to quantitatively assess DC haptotaxis, by combining precisely controllable chemokine photo-patterning with physically confining migration conditions. With this tool at hand, we studied the influence of CCL21 gradient properties and concentration on DC haptotaxis. We found that haptotactic gradient sensing depends on the absolute CCL21 concentration in combination with the local steepness of the gradient. Our analysis suggests that the directionality of migrating DCs is governed by the signal-to-noise ratio of CCL21 binding to its receptor CCR7. Moreover, the haptotactic CCL21 gradient formed in vivo provides an optimal shape for DCs to recognize haptotactic guidance cue. By reconstitution of the CCL21 gradient in vitro we were also able to study the influence of CCR7 signal termination on DC haptotaxis. To this end, we used DCs lacking the G-protein coupled receptor kinase GRK6, which is responsible for CCL21 induced CCR7 receptor phosphorylation and desensitization (Zidar et al., 2009). We found that CCR7 desensitization by GRK6 is crucial for maintenance of haptotactic CCL21 gradient sensing in vitro and confirm those observations in vivo. In the context of the organism, immobilized haptotactic guidance cues often coincide and compete with soluble chemotactic guidance cues. During wound healing, fibroblasts are exposed and influenced by adhesive cues and soluble factors at the same time (Wu et al., 2012; Wynn, 2008). Similarly, migrating DCs are exposed to both, soluble chemokines (CCL19 and truncated CCL21) inducing chemotactic behavior as well as the immobilized CCL21. To quantitatively assess these complex coinciding immobilized and soluble guidance cues, we implemented our chemokine photo-patterning technique in a microfluidic system allowing for chemotactic gradient generation. To validate the assay, we observed DC migration in competing CCL19/CCL21 environments. Adhesiveness guided haptotaxis has been studied intensively over the last century. However, quantitative studies leading to conceptual models are largely missing, again due to the lack of a precisely controllable in vitro assay. A requirement for such an in vitro assay is that it must prevent any uncontrolled cell adhesion. This can be accomplished by stable passivation of the surface. In addition, controlled adhesion must be sustainable, quantifiable and dose dependent in order to create homogenous gradients. Therefore, we developed a novel covalent photo-patterning technique satisfying all these needs. In combination with a sustainable poly-vinyl alcohol (PVA) surface coating we were able to generate gradients of adhesive cue to direct cell migration. This approach allowed us to characterize the haptotactic migratory behavior of zebrafish keratocytes in vitro. Furthermore, defined patterns of adhesive cue allowed us to control for cell shape and growth on a subcellular scale.

Theoretical foundations of multi-task lifelong learning - Pentina, Anastasia
Traditionally machine learning has been focusing on the problem of solving a single task in isolation. While being quite well understood, this approach disregards an important aspect of human learning: when facing a new problem, humans are able to exploit knowledge acquired from previously learned tasks. Intuitively, access to several problems simultaneously or sequentially could also be advantageous for a machine learning system, especially if these tasks are closely related. Indeed, results of many empirical studies have provided justification for this intuition. However, theoretical justifications of this idea are rather limited. The focus of this thesis is to expand the understanding of potential benefits of information transfer between several related learning problems. We provide theoretical analysis for three scenarios of multi-task learning - multiple kernel learning, sequential learning and active task selection. We also provide a PAC-Bayesian perspective on lifelong learning and investigate how the task generation process influences the generalization guarantees in this scenario. In addition, we show how some of the obtained theoretical results can be used to derive principled multi-task and lifelong learning algorithms and illustrate their performance on various synthetic and real-world datasets.

Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture - Mabillard, Isaac
Motivated by topological Tverberg-type problems in topological combinatorics and by classical results about embeddings (maps without double points), we study the question whether a finite simplicial complex K can be mapped into Rd without triple, quadruple, or, more generally, r-fold points (image points with at least r distinct preimages), for a given multiplicity r ≤ 2. In particular, we are interested in maps f : K → Rd that have no global r -fold intersection points, i.e., no r -fold points with preimages in r pairwise disjoint simplices of K , and we seek necessary and sufficient conditions for the existence of such maps. We present higher-multiplicity analogues of several classical results for embeddings, in particular of the completeness of the Van Kampen obstruction for embeddability of k -dimensional complexes into R2k , k ≥ 3. Speciffically, we show that under suitable restrictions on the dimensions(viz., if dimK = (r ≥ 1)k and d = rk \ for some k ≥ 3), a well-known deleted product criterion (DPC ) is not only necessary but also sufficient for the existence of maps without global r -fold points. Our main technical tool is a higher-multiplicity version of the classical Whitney trick , by which pairs of isolated r -fold points of opposite sign can be eliminated by local modiffications of the map, assuming codimension d – dimK ≥ 3. An important guiding idea for our work was that suffciency of the DPC, together with an old result of Özaydin's on the existence of equivariant maps, might yield an approach to disproving the remaining open cases of the the long-standing topological Tverberg conjecture , i.e., to construct maps from the N -simplex σN to Rd without r-Tverberg points when r not a prime power and N = (d + 1)(r – 1). Unfortunately, our proof of the sufficiency of the DPC requires codimension d – dimK ≥ 3, which is not satisfied for K = σN . In 2015, Frick [16] found a very elegant way to overcome this \codimension 3 obstacle" and to construct the first counterexamples to the topological Tverberg conjecture for all parameters(d; r ) with d ≥ 3r + 1 and r not a prime power, by a reduction1 to a suitable lower-dimensional skeleton, for which the codimension 3 restriction is satisfied and maps without r -Tverberg points exist by Özaydin's result and sufficiency of the DPC. In this thesis, we present a different construction (which does not use the constraint method) that yields counterexamples for d ≥ 3r , r not a prime power.

Symmetric spike timing-dependent plasticity at CA3–CA3 synapses optimizes storage and recall in autoassociative networks - Mishra, Rajiv Kumar; Kim, Sooyun; Guzmán, José; Jonas, Peter M (Nature Communications)
CA3–CA3 recurrent excitatory synapses are thought to play a key role in memory storage and pattern completion. Whether the plasticity properties of these synapses are consistent with their proposed network functions remains unclear. Here, we examine the properties of spike timing-dependent plasticity (STDP) at CA3–CA3 synapses. Low-frequency pairing of excitatory postsynaptic potentials (EPSPs) and action potentials (APs) induces long-term potentiation (LTP), independent of temporal order. The STDP curve is symmetric and broad (half-width ~150 ms). Consistent with these STDP induction properties, AP–EPSP sequences lead to supralinear summation of spine [Ca2+] transients. Furthermore, afterdepolarizations (ADPs) following APs efficiently propagate into dendrites of CA3 pyramidal neurons, and EPSPs summate with dendritic ADPs. In autoassociative network models, storage and recall are more robust with symmetric than with asymmetric STDP rules. Thus, a specialized STDP induction rule allows reliable storage and recall of information in the hippocampal CA3 network.

Synaptic plasticity rules at CA3-CA3 recurrent synapses in hippocampus - Mishra, Rajiv Kumar
CA3 pyramidal neurons are thought to pay a key role in memory storage and pattern completion by activity-dependent synaptic plasticity between CA3-CA3 recurrent excitatory synapses. To examine the induction rules of synaptic plasticity at CA3-CA3 synapses, we performed whole-cell patch-clamp recordings in acute hippocampal slices from rats (postnatal 21-24 days) at room temperature. Compound excitatory postsynaptic potentials (ESPSs) were recorded by tract stimulation in stratum oriens in the presence of 10 µM gabazine. High-frequency stimulation (HFS) induced N-methyl-D-aspartate (NMDA) receptor-dependent long-term potentiation (LTP). Although LTP by HFS did not requier postsynaptic spikes, it was blocked by Na+-channel blockers suggesting that local active processes (e.g.) dendritic spikes) may contribute to LTP induction without requirement of a somatic action potential (AP). We next examined the properties of spike timing-dependent plasticity (STDP) at CA3-CA3 synapses. Unexpectedly, low-frequency pairing of EPSPs and backpropagated action potentialy (bAPs) induced LTP, independent of temporal order. The STDP curve was symmetric and broad, with a half-width of ~150 ms. Consistent with these specific STDP induction properties, post-presynaptic sequences led to a supralinear summation of spine [Ca2+] transients. Furthermore, in autoassociative network models, storage and recall was substantially more robust with symmetric than with asymmetric STDP rules. In conclusion, we found associative forms of LTP at CA3-CA3 recurrent collateral synapses with distinct induction rules. LTP induced by HFS may be associated with dendritic spikes. In contrast, low frequency pairing of pre- and postsynaptic activity induced LTP only if EPSP-AP were temporally very close. Together, these induction mechanisms of synaptiic plasticity may contribute to memory storage in the CA3-CA3 microcircuit at different ranges of activity.

Evolutionary proccesses in variable emvironments - Novak, Sebastian
Natural environments are never constant but subject to spatial and temporal change on all scales, increasingly so due to human activity. Hence, it is crucial to understand the impact of environmental variation on evolutionary processes. In this thesis, I present three topics that share the common theme of environmental variation, yet illustrate its effect from different perspectives. First, I show how a temporally fluctuating environment gives rise to second-order selection on a modifier for stress-induced mutagenesis. Without fluctuations, when populations are adapted to their environment, mutation rates are minimized. I argue that a stress-induced mutator mechanism may only be maintained if the population is repeatedly subjected to diverse environmental challenges, and I outline implications of the presented results to antibiotic treatment strategies. Second, I discuss my work on the evolution of dispersal. Besides reproducing known results about the effect of heterogeneous habitats on dispersal, it identifies spatial changes in dispersal type frequencies as a source for selection for increased propensities to disperse. This concept contains effects of relatedness that are known to promote dispersal, and I explain how it identifies other forces selecting for dispersal and puts them on a common scale. Third, I analyse genetic variances of phenotypic traits under multivariate stabilizing selection. For the case of constant environments, I generalize known formulae of equilibrium variances to multiple traits and discuss how the genetic variance of a focal trait is influenced by selection on background traits. I conclude by presenting ideas and preliminary work aiming at including environmental fluctuations in the form of moving trait optima into the model.

Automatic synthesis of synchronisation primitives for concurrent programs - Tarrach, Thorsten
In this thesis we present a computer-aided programming approach to concurrency. Our approach helps the programmer by automatically fixing concurrency-related bugs, i.e. bugs that occur when the program is executed using an aggressive preemptive scheduler, but not when using a non-preemptive (cooperative) scheduler. Bugs are program behaviours that are incorrect w.r.t. a specification. We consider both user-provided explicit specifications in the form of assertion statements in the code as well as an implicit specification. The implicit specification is inferred from the non-preemptive behaviour. Let us consider sequences of calls that the program makes to an external interface. The implicit specification requires that any such sequence produced under a preemptive scheduler should be included in the set of sequences produced under a non-preemptive scheduler. We consider several semantics-preserving fixes that go beyond atomic sections typically explored in the synchronisation synthesis literature. Our synthesis is able to place locks, barriers and wait-signal statements and last, but not least reorder independent statements. The latter may be useful if a thread is released to early, e.g., before some initialisation is completed. We guarantee that our synthesis does not introduce deadlocks and that the synchronisation inserted is optimal w.r.t. a given objective function. We dub our solution trace-based synchronisation synthesis and it is loosely based on counterexample-guided inductive synthesis (CEGIS). The synthesis works by discovering a trace that is incorrect w.r.t. the specification and identifying ordering constraints crucial to trigger the specification violation. Synchronisation may be placed immediately (greedy approach) or delayed until all incorrect traces are found (non-greedy approach). For the non-greedy approach we construct a set of global constraints over synchronisation placements. Each model of the global constraints set corresponds to a correctness-ensuring synchronisation placement. The placement that is optimal w.r.t. the given objective function is chosen as the synchronisation solution. We evaluate our approach on a number of realistic (albeit simplified) Linux device-driver benchmarks. The benchmarks are versions of the drivers with known concurrency-related bugs. For the experiments with an explicit specification we added assertions that would detect the bugs in the experiments. Device drivers lend themselves to implicit specification, where the device and the operating system are the external interfaces. Our experiments demonstrate that our synthesis method is precise and efficient. We implemented objective functions for coarse-grained and fine-grained locking and observed that different synchronisation placements are produced for our experiments, favouring e.g. a minimal number of synchronisation operations or maximum concurrency.

Linear distances between Markov chains - Daca, Przemyslaw; Henzinger, Thomas A; Kretinsky, Jan; Petrov, Tatjana
We introduce a general class of distances (metrics) between Markov chains, which are based on linear behaviour. This class encompasses distances given topologically (such as the total variation distance or trace distance) as well as by temporal logics or automata. We investigate which of the distances can be approximated by observing the systems, i.e. by black-box testing or simulation, and we provide both negative and positive results.

Faster statistical model checking for unbounded temporal properties - Daca, Przemyslaw; Henzinger, Thomas A; Kretinsky, Jan; Petrov, Tatjana
We present a new algorithm for the statistical model checking of Markov chains with respect to unbounded temporal properties, including full linear temporal logic. The main idea is that we monitor each simulation run on the fly, in order to detect quickly if a bottom strongly connected component is entered with high probability, in which case the simulation run can be terminated early. As a result, our simulation runs are often much shorter than required by termination bounds that are computed a priori for a desired level of confidence on a large state space. In comparison to previous algorithms for statistical model checking our method is not only faster in many cases but also requires less information about the system, namely, only the minimum transition probability that occurs in the Markov chain. In addition, our method can be generalised to unbounded quantitative properties such as mean-payoff bounds.

Abstraction-driven concolic testing - Daca, Przemyslaw; Gupta, Ashutosh; Henzinger, Thomas A
Concolic testing is a promising method for generating test suites for large programs. However, it suffers from the path-explosion problem and often fails to find tests that cover difficult-to-reach parts of programs. In contrast, model checkers based on counterexample-guided abstraction refinement explore programs exhaustively, while failing to scale on large programs with precision. In this paper, we present a novel method that iteratively combines concolic testing and model checking to find a test suite for a given coverage criterion. If concolic testing fails to cover some test goals, then the model checker refines its program abstraction to prove more paths infeasible, which reduces the search space for concolic testing. We have implemented our method on top of the concolictesting tool Crest and the model checker CpaChecker. We evaluated our tool on a collection of programs and a category of SvComp benchmarks. In our experiments, we observed an improvement in branch coverage compared to Crest from 48% to 63% in the best case, and from 66% to 71% on average.

Array folds logic - Daca, Przemyslaw; Henzinger, Thomas A; Kupriyanov, Andrey
We present an extension to the quantifier-free theory of integer arrays which allows us to express counting. The properties expressible in Array Folds Logic (AFL) include statements such as "the first array cell contains the array length," and "the array contains equally many minimal and maximal elements." These properties cannot be expressed in quantified fragments of the theory of arrays, nor in the theory of concatenation. Using reduction to counter machines, we show that the satisfiability problem of AFL is PSPACE-complete, and with a natural restriction the complexity decreases to NP. We also show that adding either universal quantifiers or concatenation leads to undecidability. AFL contains terms that fold a function over an array. We demonstrate that folding, a well-known concept from functional languages, allows us to concisely summarize loops that count over arrays, which occurs frequently in real-life programs. We provide a tool that can discharge proof obligations in AFL, and we demonstrate on practical examples that our decision procedure can solve a broad range of problems in symbolic testing and program verification.

Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs - Chatterjee, Krishnendu; Ibsen-Jensen, Rasmus; Pavlogiannis, Andreas
We consider data-structures for answering reachability and distance queries on constant-treewidth graphs with n nodes, on the standard RAM computational model with wordsize W=Theta(log n). Our first contribution is a data-structure that after O(n) preprocessing time, allows (1) pair reachability queries in O(1) time; and (2) single-source reachability queries in O(n/log n) time. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries. The data-structure uses at all times O(n) space. Our second contribution is a space-time tradeoff data-structure for distance queries. For any epsilon in [1/2,1], we provide a data-structure with polynomial preprocessing time that allows pair queries in O(n^{1-ε} alpha(n)) time, where alpha is the inverse of the Ackermann function, and at all times uses O(n^epsilon) space. The input graph G is not considered in the space complexity.

Fast approximations for boundary element based brittle fracture simulation - Hahn, David; Wojtan, Christopher J
We present a boundary element based method for fast simulation of brittle fracture. By introducing simplifying assumptions that allow us to quickly estimate stress intensities and opening displacements during crack propagation, we build a fracture algorithm where the cost of each time step scales linearly with the length of the crackfront. The transition from a full boundary element method to our faster variant is possible at the beginning of any time step. This allows us to build a hybrid method, which uses the expensive but more accurate BEM while the number of degrees of freedom is low, and uses the fast method once that number exceeds a given threshold as the crack geometry becomes more complicated. Furthermore, we integrate this fracture simulation with a standard rigid-body solver. Our rigid-body coupling solves a Neumann boundary value problem by carefully separating translational, rotational and deformational components of the collision forces and then applying a Tikhonov regularizer to the resulting linear system. We show that our method produces physically reasonable results in standard test cases and is capable of dealing with complex scenes faster than previous finite- or boundary element approaches.

Offline witness encryption - Abusalah, Hamza M; Fuchsbauer, Georg; Pietrzak, Krzysztof Z
Witness encryption (WE) was introduced by Garg et al. [GGSW13]. A WE scheme is defined for some NP language L and lets a sender encrypt messages relative to instances x. A ciphertext for x can be decrypted using w witnessing x ∈ L, but hides the message if x ∈ L. Garg et al. construct WE from multilinear maps and give another construction [GGH+13b] using indistinguishability obfuscation (iO) for circuits. Due to the reliance on such heavy tools, WE can cur- rently hardly be implemented on powerful hardware and will unlikely be realizable on constrained devices like smart cards any time soon. We construct a WE scheme where encryption is done by simply computing a Naor-Yung ciphertext (two CPA encryptions and a NIZK proof). To achieve this, our scheme has a setup phase, which outputs public parameters containing an obfuscated circuit (only required for decryption), two encryption keys and a common reference string (used for encryption). This setup need only be run once, and the parame- ters can be used for arbitrary many encryptions. Our scheme can also be turned into a functional WE scheme, where a message is encrypted w.r.t. a statement and a function f, and decryption with a witness w yields f (m, w). Our construction is inspired by the functional encryption scheme by Garg et al. and we prove (selective) security assuming iO and statistically simulation-sound NIZK. We give a construction of the latter in bilinear groups and combining it with ElGamal encryption, our ciphertexts are of size 1.3 kB at a 128-bit security level and can be computed on a smart card.

Constrained PRFs for unbounded inputs - Abusalah, Hamza M; Fuchsbauer, Georg; Pietrzak, Krzysztof Z
A constrained pseudorandom function F: K × X → Y for a family T ⊆ 2X of subsets of X is a function where for any key k ∈ K and set S ∈ T one can efficiently compute a constrained key kS which allows to evaluate F (k, ·) on all inputs x ∈ S, while even given this key, the outputs on all inputs x ∉ S look random. At Asiacrypt’13 Boneh and Waters gave a construction which supports the most general set family so far. Its keys kc are defined for sets decided by boolean circuits C and enable evaluation of the PRF on any x ∈ X where C(x) = 1. In their construction the PRF input length and the size of the circuits C for which constrained keys can be computed must be fixed beforehand during key generation. We construct a constrained PRF that has an unbounded input length and whose constrained keys can be defined for any set recognized by a Turing machine. The only a priori bound we make is on the description size of the machines. We prove our construction secure assuming publiccoin differing-input obfuscation. As applications of our constrained PRF we build a broadcast encryption scheme where the number of potential receivers need not be fixed at setup (in particular, the length of the keys is independent of the number of parties) and the first identity-based non-interactive key exchange protocol with no bound on the number of parties that can agree on a shared key.

Constrained PRFs for unbounded inputs with short keys - Abusalah, Hamza M; Fuchsbauer, Georg
A constrained pseudorandom function (CPRF) F: K×X → Y for a family T of subsets of χ is a function where for any key k ∈ K and set S ∈ T one can efficiently compute a short constrained key kS, which allows to evaluate F(k, ·) on all inputs x ∈ S, while the outputs on all inputs x /∈ S look random even given kS. Abusalah et al. recently constructed the first constrained PRF for inputs of arbitrary length whose sets S are decided by Turing machines. They use their CPRF to build broadcast encryption and the first ID-based non-interactive key exchange for an unbounded number of users. Their constrained keys are obfuscated circuits and are therefore large. In this work we drastically reduce the key size and define a constrained key for a Turing machine M as a short signature on M. For this, we introduce a new signature primitive with constrained signing keys that let one only sign certain messages, while forging a signature on others is hard even when knowing the coins for key generation.

A phytochrome sensory domain permits receptor activation by red light - Gschaider-Reichhart, Eva; Inglés Prieto, Álvaro; Tichy, Alexandra-Madelaine; Mckenzie, Catherine; Janovjak, Harald L (Angewandte Chemie - International Edition)
Optogenetics and photopharmacology enable the spatio-temporal control of cell and animal behavior by light. Although red light offers deep-tissue penetration and minimal phototoxicity, very few red-light-sensitive optogenetic methods are currently available. We have now developed a red-light-induced homodimerization domain. We first showed that an optimized sensory domain of the cyanobacterial phytochrome 1 can be expressed robustly and without cytotoxicity in human cells. We then applied this domain to induce the dimerization of two receptor tyrosine kinases—the fibroblast growth factor receptor 1 and the neurotrophin receptor trkB. This new optogenetic method was then used to activate the MAPK/ERK pathway non-invasively in mammalian tissue and in multicolor cell-signaling experiments. The light-controlled dimerizer and red-light-activated receptor tyrosine kinases will prove useful to regulate a variety of cellular processes with light. Go deep with red: The sensory domain (S) of the cyanobacterial phytochrome 1 (CPH1) was repurposed to induce the homodimerization of proteins in living cells by red light. By using this domain, light-activated protein kinases were engineered that can be activated orthogonally from many fluorescent proteins and through mammalian tissue. Pr/Pfr=red-/far-red-absorbing state of CPH1.

Intrinsic limits to gene regulation by global crosstalk - Friedlander, Tamar; Prizak, Roshan; Guet, Calin C; Barton, Nicholas H; Tkacik, Gasper (Nature Communications)
Gene regulation relies on the specificity of transcription factor (TF)–DNA interactions. Limited specificity may lead to crosstalk: a regulatory state in which a gene is either incorrectly activated due to noncognate TF–DNA interactions or remains erroneously inactive. As each TF can have numerous interactions with noncognate cis-regulatory elements, crosstalk is inherently a global problem, yet has previously not been studied as such. We construct a theoretical framework to analyse the effects of global crosstalk on gene regulation. We find that crosstalk presents a significant challenge for organisms with low-specificity TFs, such as metazoans. Crosstalk is not easily mitigated by known regulatory schemes acting at equilibrium, including variants of cooperativity and combinatorial regulation. Our results suggest that crosstalk imposes a previously unexplored global constraint on the functioning and evolution of regulatory networks, which is qualitatively distinct from the known constraints that act at the level of individual gene regulatory elements.

Mitochondrial uncouplers inhibit clathrin-mediated endocytosis largely through cytoplasmic acidification - Dejonghe, Wim; Kuenen, Sabine; Mylle, Evelien; Vasileva, Mina K; Keech, Olivier; Viotti, Corrado; Swerts, Jef; Fendrych, Matyas; Ortiz Morea, Fausto; Mishev, Kiril; Delang, Simon; Scholl, Stefan; et al. (Nature Communications)
ATP production requires the establishment of an electrochemical proton gradient across the inner mitochondrial membrane. Mitochondrial uncouplers dissipate this proton gradient and disrupt numerous cellular processes, including vesicular trafficking, mainly through energy depletion. Here we show that Endosidin9 (ES9), a novel mitochondrial uncoupler, is a potent inhibitor of clathrin-mediated endocytosis (CME) in different systems and that ES9 induces inhibition of CME not because of its effect on cellular ATP, but rather due to its protonophore activity that leads to cytoplasm acidification. We show that the known tyrosine kinase inhibitor tyrphostinA23, which is routinely used to block CME, displays similar properties, thus questioning its use as a specific inhibitor of cargo recognition by the AP-2 adaptor complex via tyrosine motif-based endocytosis signals. Furthermore, we show that cytoplasm acidification dramatically affects the dynamics and recruitment of clathrin and associated adaptors, and leads to reduction of phosphatidylinositol 4,5-biphosphate from the plasma membrane.

Heavy-hole states in germanium hut wires - Watzinger, Hannes; Kloeffel, Christoph; Vukusic, Lada; Rossell, Marta; Sessi, Violetta; Kukucka, Josip; Kirchschlager, Raimund; Lausecker, Elisabeth; Truhlar, Alisha; Glaser, Martin; Rastelli, Armando; Fuhrer, Andreas; et al. (Nano Letters)
Hole spins have gained considerable interest in the past few years due to their potential for fast electrically controlled qubits. Here, we study holes confined in Ge hut wires, a so-far unexplored type of nanostructure. Low-temperature magnetotransport measurements reveal a large anisotropy between the in-plane and out-of-plane g-factors of up to 18. Numerical simulations verify that this large anisotropy originates from a confined wave function of heavy-hole character. A light-hole admixture of less than 1% is estimated for the states of lowest energy, leading to a surprisingly large reduction of the out-of-plane g-factors compared with those for pure heavy holes. Given this tiny light-hole contribution, the spin lifetimes are expected to be very long, even in isotopically nonpurified samples.

Safety assured formal model driven design of the multifunction vehicle bus controller - Jiang, Yu; Liu, Han; Song, Houbing; Kong, Hui; Gu, Ming; Sun, Jiaguang; Sha, Lui
In this paper, we present a formal model-driven engineering approach to establishing a safety-assured implementation of Multifunction vehicle bus controller (MVBC) based on the generic reference models and requirements described in the International Electrotechnical Commission (IEC) standard IEC-61375. First, the generic models described in IEC-61375 are translated into a network of timed automata, and some safety requirements tested in IEC-61375 are formalized as timed computation tree logic (TCTL) formulas. With the help of Uppaal, we check and debug whether the timed automata satisfy the formulas or not. Within this step, several logic inconsistencies in the original standard are detected and corrected. Then, we apply the tool Times to generate C code from the verified model, which was later synthesized into a real MVBC chip. Finally, the runtime verification tool RMOR is applied to verify some safety requirements at the implementation level. We set up a real platform with worldwide mostly used MVBC D113, and verify the correctness and the scalability of the synthesized MVBC chip more comprehensively. The errors in the standard has been confirmed and the resulted MVBC has been deployed in real train communication network.

Commutativity in the algorithmic Lovasz local lemma - Kolmogorov, Vladimir (Proceedings - Annual IEEE Symposium on Foundations of Computer Science)
We consider the recent formulation of the Algorithmic Lovász Local Lemma [1], [2] for finding objects that avoid "bad features", or "flaws". It extends the Moser-Tardos resampling algorithm [3] to more general discrete spaces. At each step the method picks a flaw present in the current state and "resamples" it using a "resampling oracle" provided by the user. However, it is less flexible than the Moser-Tardos method since [1], [2] require a specific flaw selection rule, whereas [3] allows an arbitrary rule (and thus can potentially be implemented more efficiently). We formulate a new "commutativity" condition, and prove that it is sufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additional assumption. We then show that existing resampling oracles for perfect matchings and permutations do satisfy this condition. Finally, we generalize the precondition in [2] (in the case of symmetric potential causality graphs). This unifies special cases that previously were treated separately.

Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs - Chatterjee, Krishnendu; Fu, Hongfei; Novotny, Petr; Hasheminezhad, Rouzbeh
In this paper, we consider termination of probabilistic programs with real-valued variables. The questions concerned are: (a) qualitative ones that ask (i) whether the program terminates with probability 1 (almost-sure termination) and (ii) whether the expected termination time is finite (finite termination); (b) quantitative ones that ask (i) to approximate the expected termination time (expectation problem) and (ii) to compute a bound B such that the probability to terminate after B steps decreases exponentially (concentration problem). To solve these questions, we utilize the notion of ranking supermartingales which is a powerful approach for proving termination of probabilistic programs. In detail, we focus on algorithmic synthesis of linear ranking-supermartingales over affine probabilistic programs (APP's) with both angelic and demonic non-determinism. An important subclass of APP's is LRAPP which is defined as the class of all APP's over which a linear ranking-supermartingale exists. Our main contributions are as follows. Firstly, we show that the membership problem of LRAPP (i) can be decided in polynomial time for APP's with at most demonic non-determinism, and (ii) is NP-hard and in PSPACE for APP's with angelic non-determinism; moreover, the NP-hardness result holds already for APP's without probability and demonic non-determinism. Secondly, we show that the concentration problem over LRAPP can be solved in the same complexity as for the membership problem of LRAPP. Finally, we show that the expectation problem over LRAPP can be solved in 2EXPTIME and is PSPACE-hard even for APP's without probability and non-determinism (i.e., deterministic programs). Our experimental results demonstrate the effectiveness of our approach to answer the qualitative and quantitative questions over APP's with at most demonic non-determinism.

Data from: How does epistasis influence the response to selection? - Barton, Nicholas H
Much of quantitative genetics is based on the ‘infinitesimal model’, under which selection has a negligible effect on the genetic variance. This is typically justified by assuming a very large number of loci with additive effects. However, it applies even when genes interact, provided that the number of loci is large enough that selection on each of them is weak relative to random drift. In the long term, directional selection will change allele frequencies, but even then, the effects of epistasis on the ultimate change in trait mean due to selection may be modest. Stabilising selection can maintain many traits close to their optima, even when the underlying alleles are weakly selected. However, the number of traits that can be optimised is apparently limited to ~4Ne by the ‘drift load’, and this is hard to reconcile with the apparent complexity of many organisms. Just as for the mutation load, this limit can be evaded by a particular form of negative epistasis. A more robust limit is set by the variance in reproductive success. This suggests that selection accumulates information most efficiently in the infinitesimal regime, when selection on individual alleles is weak, and comparable with random drift. A review of evidence on selection strength suggests that although most variance in fitness may be because of alleles with large Nes, substantial amounts of adaptation may be because of alleles in the infinitesimal regime, in which epistasis has modest effects.

Data from evolutionary interplay between structure, energy and epistasis in the coat protein of the ϕX174 phage family - Fernandes Redondo, Rodrigo A; de Vladar, Harold; Włodarski, Tomasz; Bollback, Jonathan P
Viral capsids are structurally constrained by interactions among the amino acids (AAs) of their constituent proteins. Therefore, epistasis is expected to evolve among physically interacting sites and to influence the rates of substitution. To study the evolution of epistasis, we focused on the major structural protein of the ϕX174 phage family by, first, reconstructing the ancestral protein sequences of 18 species using a Bayesian statistical framework. The inferred ancestral reconstruction differed at eight AAs, for a total of 256 possible ancestral haplotypes. For each ancestral haplotype and the extant species, we estimated, in silico, the distribution of free energies and epistasis of the capsid structure. We found that free energy has not significantly increased but epistasis has. We decomposed epistasis up to fifth order and found that higher-order epistasis sometimes compensates pairwise interactions making the free energy seem additive. The dN/dS ratio is low, suggesting strong purifying selection, and that structure is under stabilizing selection. We synthesized phages carrying ancestral haplotypes of the coat protein gene and measured their fitness experimentally. Our findings indicate that stabilizing mutations can have higher fitness, and that fitness optima do not necessarily coincide with energy minima.

C-planarity of embedded cyclic c-graphs - Fulek, Radoslav
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.

On expansion and topological overlap - Dotterrer, Dominic; Kaufman, Tali; Wagner, Uli
We give a detailed and easily accessible proof of Gromov's Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map X → ℝd there exists a point p ∈ ℝd whose preimage intersects a positive fraction μ > 0 of the d-cells of X. More generally, the conclusion holds if ℝd is replaced by any d-dimensional piecewise-linear (PL) manifold M, with a constant μ that depends only on d and on the expansion properties of X, but not on M.

Intrinsic membrane properties determine hippocampal differential firing pattern in vivo in anesthetized rats - Kowalski, Janina; Gan, Jian; Jonas, Peter M; Pernia-Andrade, Alejandro (Hippocampus)
The hippocampus plays a key role in learning and memory. Previous studies suggested that the main types of principal neurons, dentate gyrus granule cells (GCs), CA3 pyramidal neurons, and CA1 pyramidal neurons, differ in their activity pattern, with sparse firing in GCs and more frequent firing in CA3 and CA1 pyramidal neurons. It has been assumed but never shown that such different activity may be caused by differential synaptic excitation. To test this hypothesis, we performed high-resolution whole-cell patch-clamp recordings in anesthetized rats in vivo. In contrast to previous in vitro data, both CA3 and CA1 pyramidal neurons fired action potentials spontaneously, with a frequency of ∼3–6 Hz, whereas GCs were silent. Furthermore, both CA3 and CA1 cells primarily fired in bursts. To determine the underlying mechanisms, we quantitatively assessed the frequency of spontaneous excitatory synaptic input, the passive membrane properties, and the active membrane characteristics. Surprisingly, GCs showed comparable synaptic excitation to CA3 and CA1 cells and the highest ratio of excitation versus hyperpolarizing inhibition. Thus, differential synaptic excitation is not responsible for differences in firing. Moreover, the three types of hippocampal neurons markedly differed in their passive properties. While GCs showed the most negative membrane potential, CA3 pyramidal neurons had the highest input resistance and the slowest membrane time constant. The three types of neurons also differed in the active membrane characteristics. GCs showed the highest action potential threshold, but displayed the largest gain of the input-output curves. In conclusion, our results reveal that differential firing of the three main types of hippocampal principal neurons in vivo is not primarily caused by differences in the characteristics of the synaptic input, but by the distinct properties of synaptic integration and input-output transformation.

Inference algorithms for pattern-based CRFs on sequence data - Kolmogorov, Vladimir; Takhanov, Rustem (Algorithmica)
We consider Conditional random fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) (Formula presented.) is the sum of terms over intervals [i, j] where each term is non-zero only if the substring (Formula presented.) equals a prespecified pattern w. Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.) where L is the combined length of input patterns, (Formula presented.) is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of Ye et al. (NIPS, 2009) whose complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.), where (Formula presented.) is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights.

The CLE gene family in Populus trichocarpa - Liu, Zhijun; Yang, Nan; Lv, Yanting; Pan, Lixia; Lv, Shuo; Han, Huibin; Wang, Guodong (Plant Signaling & Behavior)
The CLE (CLAVATA3/Embryo Surrounding Region-related) peptides are small secreted signaling peptides that are primarily involved in the regulation of stem cell homeostasis in different plant meristems. Particularly, the characterization of the CLE41-PXY/TDR signaling pathway has greatly advanced our understanding on the potential roles of CLE peptides in vascular development and wood formation. Nevertheless, our knowledge on this gene family in a tree species is limited. In a recent study, we reported on a systematically investigation of the CLE gene family in Populus trichocarpa . The potential roles of PtCLE genes were studied by comparative analysis and transcriptional pro fi ling. Among fi fty PtCLE members, many PtCLE proteins share identical CLE motifs or contain the same CLE motif as that of AtCLEs, while PtCLE genes exhibited either comparable or distinct expression patterns comparing to their Arabidopsis counterparts. These fi ndings indicate the existence of both functional conservation and functional divergence between PtCLEs and their AtCLE orthologues. Our results provide valuable resources for future functional investigations of these critical signaling molecules in woody plants.

Efficient microwave to optical photon conversion: An electro-optical realization - Rueda, Alfredo; Sedlmeir, Florian; Collodo, Michele; Vogl, Ulrich; Stiller, Birgit; Schunk, Gerhard; Strekalov, Dmitry; Marquardt, Christoph; Fink, Johannes M; Painter, Oskar; Leuchs, Gerd; Schwefel, Harald (Optica)
Linking classical microwave electrical circuits to the optical telecommunication band is at the core of modern communication. Future quantum information networks will require coherent microwave-to-optical conversion to link electronic quantum processors and memories via low-loss optical telecommunication networks. Efficient conversion can be achieved with electro-optical modulators operating at the single microwave photon level. In the standard electro-optic modulation scheme, this is impossible because both up- and down-converted sidebands are necessarily present. Here, we demonstrate true single-sideband up- or down-conversion in a triply resonant whispering gallery mode resonator by explicitly addressing modes with asymmetric free spectral range. Compared to previous experiments, we show a 3 orders of magnitude improvement of the electro-optical conversion efficiency, reaching 0.1% photon number conversion for a 10 GHz microwave tone at 0.42 mW of optical pump power. The presented scheme is fully compatible with existing superconducting 3D circuit quantum electrodynamics technology and can be used for nonclassical state conversion and communication. Our conversion bandwidth is larger than 1 MHz and is not fundamentally limited.

Modes and exceptional points in waveguides with impedance boundary conditions - Midya, Bikashkali; Konotop, Vladimir (Optics Letters)
A planar waveguide with an impedance boundary, composed of nonperfect metallic plates, and with passive or active dielectric filling, is considered. We show the possibility of selective mode guiding and amplification when a homogeneous pump is added to the dielectric and analyze differences in TE and TM mode propagation. Such a non-conservative system is also shown to feature exceptional points for specific and experimentally tunable parameters, which are described for a particular case of transparent dielectric.

Vascular cambium regeneration and vessel formation in wounded inflorescence stems of Arabidopsis - Mazur, Ewa; Benková, Eva; Friml, Jirí (Scientific Reports)
Synchronized tissue polarization during regeneration or de novo vascular tissue formation is a plant-specific example of intercellular communication and coordinated development. According to the canalization hypothesis, the plant hormone auxin serves as polarizing signal that mediates directional channel formation underlying the spatio-temporal vasculature patterning. A necessary part of canalization is a positive feedback between auxin signaling and polarity of the intercellular auxin flow. The cellular and molecular mechanisms of this process are still poorly understood, not the least, because of a lack of a suitable model system. We show that the main genetic model plant, Arabidopsis (Arabidopsis thaliana) can be used to study the canalization during vascular cambium regeneration and new vasculature formation. We monitored localized auxin responses, directional auxin-transport channels formation, and establishment of new vascular cambium polarity during regenerative processes after stem wounding. The increased auxin response above and around the wound preceded the formation of PIN1 auxin transporter-marked channels from the primarily homogenous tissue and the transient, gradual changes in PIN1 localization preceded the polarity of newly formed vascular tissue. Thus, Arabidopsis is a useful model for studies of coordinated tissue polarization and vasculature formation after wounding allowing for genetic and mechanistic dissection of the canalization hypothesis.

How MicroRNAs Are involved in splitting the mind - Tsai, Lihuei; Siegert, Sandra (JAMA Psychiatry)
This article provides an introduction to the role of microRNAs in the nervous system and outlines their potential involvement in the pathophysiology of schizophrenia, which is hypothesized to arise owing to environmental factors and genetic predisposition.

Arbitrarily strong amplifiers of natural selection - Pavlogiannis, Andreas; Tkadlec, Josef; Chatterjee, Krishnendu; Nowak, Martin

Flower colour data and phylogeny (NEXUS) files - Ellis, Thomas; Field, David
We collected flower colour information on species in the tribe Antirrhineae from taxonomic literature. We also retreived molecular data from GenBank for as many of these species as possible to estimate phylogenetic relationships among these taxa. We then used the R package 'diversitree' to examine patterns of evolutionary transitions between anthocyanin and yellow pigmentation across the phylogeny. For full details of the methods see: Ellis TJ and Field DL "Repeated gains in yellow and anthocyanin pigmentation in flower colour transitions in the Antirrhineae”, Annals of Botany (in press)

Fiji script to determine average speed and direction of migration of cells - Hauschild, Robert
This FIJI script calculates the population average of the migration speed as a function of time of all cells from wide field microscopy movies.
Keywords: cell migration; wide field microscopy; FIJI

Synthetic discrete tomography problems - Swoboda, Paul
Small synthetic discrete tomography problems. Sizes are 32x32, 64z64 and 256x256. Projection angles are 2, 4, and 6. Number of labels are 3 and 5.
Keywords: discrete tomography

Tracking, correcting and absorbing water surface waves - Bojsen-Hansen, Morten
Computer graphics is an extremely exciting field for two reasons. On the one hand, there is a healthy injection of pragmatism coming from the visual effects industry that want robust algorithms that work so they can produce results at an increasingly frantic pace. On the other hand, they must always try to push the envelope and achieve the impossible to wow their audiences in the next blockbuster, which means that the industry has not succumb to conservatism, and there is plenty of room to try out new and crazy ideas if there is a chance that it will pan into something useful. Water simulation has been in visual effects for decades, however it still remains extremely challenging because of its high computational cost and difficult artdirectability. The work in this thesis tries to address some of these difficulties. Specifically, we make the following three novel contributions to the state-of-the-art in water simulation for visual effects. First, we develop the first algorithm that can convert any sequence of closed surfaces in time into a moving triangle mesh. State-of-the-art methods at the time could only handle surfaces with fixed connectivity, but we are the first to be able to handle surfaces that merge and split apart. This is important for water simulation practitioners, because it allows them to convert splashy water surfaces extracted from particles or simulated using grid-based level sets into triangle meshes that can be either textured and enhanced with extra surface dynamics as a post-process. We also apply our algorithm to other phenomena that merge and split apart, such as morphs and noisy reconstructions of human performances. Second, we formulate a surface-based energy that measures the deviation of a water surface froma physically valid state. Such discrepancies arise when there is a mismatch in the degrees of freedom between the water surface and the underlying physics solver. This commonly happens when practitioners use a moving triangle mesh with a grid-based physics solver, or when high-resolution grid-based surfaces are combined with low-resolution physics. Following the direction of steepest descent on our surface-based energy, we can either smooth these artifacts or turn them into high-resolution waves by interpreting the energy as a physical potential. Third, we extend state-of-the-art techniques in non-reflecting boundaries to handle spatially and time-varying background flows. This allows a novel new workflow where practitioners can re-simulate part of an existing simulation, such as removing a solid obstacle, adding a new splash or locally changing the resolution. Such changes can easily lead to new waves in the re-simulated region that would reflect off of the new simulation boundary, effectively ruining the illusion of a seamless simulation boundary between the existing and new simulations. Our non-reflecting boundaries makes sure that such waves are absorbed.

The role of pollinator-mediated selection in the maintenance of a flower color polymorphism in an Antirrhinum majus hybrid zone - Ellis, Thomas
Hybrid zones represent evolutionary laboratories, where recombination brings together alleles in combinations which have not previously been tested by selection. This provides an excellent opportunity to test the effect of molecular variation on fitness, and how this variation is able to spread through populations in a natural context. The snapdragon Antirrhinum majus is polymorphic in the wild for two loci controlling the distribution of yellow and magenta floral pigments. Where the yellow A. m. striatum and the magenta A. m. pseudomajus meet along a valley in the Spanish Pyrenees they form a stable hybrid zone Alleles at these loci recombine to give striking transgressive variation for flower colour. The sharp transition in phenotype over ~1km implies strong selection maintaining the hybrid zone. An indirect assay of pollinator visitation in the field found that pollinators forage in a positive-frequency dependent manner on Antirrhinum, matching previous data on fruit set. Experimental arrays and paternity analysis of wild-pollinated seeds demonstrated assortative mating for pigmentation alleles, and that pollinator behaviour alone is sufficient to explain this pattern. Selection by pollinators should be sufficiently strong to maintain the hybrid zone, although other mechanisms may be at work. At a broader scale I examined evolutionary transitions between yellow and anthocyanin pigmentation in the tribe Antirrhinae, and found that selection has acted strate that pollinators are a major determinant of reproductive success and mating patterns in wild Antirrhinum.

Evolution of transcriptional regulatory sequences - Tugrul, Murat
Evolution of gene regulation is important for phenotypic evolution and diversity. Sequence-specific binding of regulatory proteins is one of the key regulatory mechanisms determining gene expression. Although there has been intense interest in evolution of regulatory binding sites in the last decades, a theoretical understanding is far from being complete. In this thesis, I aim at a better understanding of the evolution of transcriptional regulatory binding sequences by using biophysical and population genetic models. In the first part of the thesis, I discuss how to formulate the evolutionary dynamics of binding se- quences in a single isolated binding site and in promoter/enhancer regions. I develop a theoretical framework bridging between a thermodynamical model for transcription and a mutation-selection-drift model for monomorphic populations. I mainly address the typical evolutionary rates, and how they de- pend on biophysical parameters (e.g. binding length and specificity) and population genetic parameters (e.g. population size and selection strength). In the second part of the thesis, I analyse empirical data for a better evolutionary and biophysical understanding of sequence-specific binding of bacterial RNA polymerase. First, I infer selection on regulatory and non-regulatory binding sites of RNA polymerase in the E. coli K12 genome. Second, I infer the chemical potential of RNA polymerase, an important but unknown physical parameter defining the threshold energy for strong binding. Furthermore, I try to understand the relation between the lac promoter sequence diversity and the LacZ activity variation among 20 bacterial isolates by constructing a simple but biophysically motivated gene expression model. Lastly, I lay out a statistical framework to predict adaptive point mutations in de novo promoter evolution in a selection experiment.

Inference of mating patterns among wild snapdragons in a natural hybrid zone in 2012 - Field, David; Ellis, Thomas
Genotypic, phenotypic and demographic data for 2128 wild snapdragons and 1127 open-pollinated progeny from a natural hybrid zone, collected as part of Tom Ellis' PhD thesis (submitted) February 2016). Tissue samples were sent to LGC Genomics in Berlin for DNA extraction, and genotyping at 70 SNP markers by KASPR genotyping. 29 of these SNPs failed to amplify reliably, and have been removed from this dataset. Other data were retreived from an online database of this population at www.antspec.org.
Keywords: paternity assignment; pedigree; matting patterns; assortative mating; Antirrhinum majus; frequency-dependent selection; plant-pollinator interaction

Data on pollinator observations and offpsring phenotypes - Ellis, Thomas
Data from array experiments investigating pollinator behaviour on snapdragons in controlled conditions, and their effect on plant mating. Data were collected as part of Tom Ellis' PhD thesis , submitted February 2016. We placed a total of 36 plants in a grid inside a closed organza tent, with a single hive of commercially bred bumblebees (Bombus hortorum). We used only the yellow-flowered Antirrhinum majus striatum and the magenta-flowered Antirrhinum majus pseudomajus, at ratios of 6:36, 12:24, 18:18, 24:12 and 30:6. After 24 hours to learn how to deal with snapdragons, I observed pollinators foraging on plants, and recorded the transitions between plants. Thereafter seeds on plants were allowed to develops. A sample of these were grown to maturity when their flower colour could be determined, and they were scored as yellow, magenta, or hybrid.

Pollinator visitation data for wild Antirrhinum majus plants, with phenotypic and frequency data. - Ellis, Thomas
Data on pollinator visitation to wild snapdragons in a natural hybrid zone, collected as part of Tom Ellis' PhD thesis (submitted February 2016). Snapdragon flowers have a mouth-like structure which pollinators must open to access nectar. We placed 5mm cellophane tags in these mouths, which are held in place by the pressure of the flower until a pollinator visits. When she opens the flower, the tag drops out, and one can infer a visit. We surveyed plants over multiple days in 2010, 2011 and 2012. Also included are data on phenotypic and demographic variables which may be explanatory variables for pollinator visitation.

Experimental Data for Binding Site Evolution of Bacterial RNA Polymerase - Tugrul, Murat
The data stored here is used in Murat Tugrul's PhD thesis (Chapter 3), which is related to the evolution of bacterial RNA polymerase binding. Magdalena Steinrueck (PhD Student in Calin Guet's group at IST Austria) performed the experiments and created the data on de novo promoter evolution. Fabienne Jesse (PhD Student in Jon Bollback's group at IST Austria) performed the experiments and created the data on lac promoter evolution.
Keywords: RNAP binding; de novo promoter evolution; lac promoter

Tracking, Correcting and Absorbing Water Surface Waves - Bojsen-Hansen, Morten
PhD thesis LaTeX source code

MATLAB analysis code for 'Sequence-Specific Thermodynamic Properties of Nucleic Acids Influence Both Transcriptional Pausing and Backtracking in Yeast' - Lukacisin, Martin; Landon, Matthieu; Jajoo, Rishi
MATLAB code and processed datasets available for reproducing the results in: Lukačišin, M.*, Landon, M.*, Jajoo, R*. (2016) Sequence-Specific Thermodynamic Properties of Nucleic Acids Influence Both Transcriptional Pausing and Backtracking in Yeast. *equal contributions
Keywords: transcription; pausing; backtracking; polymerase; RNA; NET-seq; nucleosome; basepairing

eXTP: Enhanced X-ray timing and polarization mission - Zhang, S. N.; Feroci, M.; Santangelo, A.; Dong, Y. W.; Feng, H.; Lu, F. J.; Nandra, K.; Wang, Z. S.; Zhang, S.; Bozzo, E.; Brandt, S.; De Rosa, A.; et al. (Proceedings of the SPIE)
eXTP is a science mission designed to study the state of matter under extreme conditions of density, gravity and magnetism. Primary goals are the determination of the equation of state of matter at supra-nuclear density, the measurement of QED effects in highly magnetized star, and the study of accretion in the strong-field regime of gravity. Primary targets include isolated and binary neutron stars, strong magnetic field systems like magnetars, and stellar-mass and supermassive black holes. The mission carries a unique and unprecedented suite of state-of-the-art scientific instruments enabling for the first time ever the simultaneous spectral-timing-polarimetry studies of cosmic sources in the energy range from 0.5-30 keV (and beyond). Key elements of the payload are: the Spectroscopic Focusing Array (SFA) - a set of 11 X-ray optics for a total effective area of ∼0.9 m2 and 0.6 m2 at 2 keV and 6 keV respectively, equipped with Silicon Drift Detectors offering <180 eV spectral resolution; the Large Area Detector (LAD) - a deployable set of 640 Silicon Drift Detectors, for a total effective area of ∼3.4 m2, between 6 and 10 keV, and spectral resolution better than 250 eV; the Polarimetry Focusing Array (PFA) - a set of 2 X-ray telescope, for a total effective area of 250 cm2 at 2 keV, equipped with imaging gas pixel photoelectric polarimeters; the Wide Field Monitor (WFM) - a set of 3 coded mask wide field units, equipped with position-sensitive Silicon Drift Detectors, each covering a 90 degrees x 90 degrees field of view. The eXTP international consortium includes major institutions of the Chinese Academy of Sciences and Universities in China, as well as major institutions in several European countries and the United States. The predecessor of eXTP, the XTP mission concept, has been selected and funded as one of the so-called background missions in the Strategic Priority Space Science Program of the Chinese Academy of Sciences since 2011. The strong European participation has significantly enhanced the scientific capabilities of eXTP. The planned launch date of the mission is earlier than 2025.

XIPE: The x-ray imaging polarimetry explorer - Soffitta, Paolo; Bellazzini, Ronaldo; Bozzo, Enrico; Burwitz, Vadim; Castro Tirado, Alberto; Costa, Enrico; Courvoisier, Thierry; Feng, Hua; Gburek, Szymon; Goosmann, Rene'; Karas, Vladimir; Matt, Giorgio; et al. (Space Telescopes and Instrumentation 2016: Ultraviolet to Gamma Ray)
XIPE, the X-ray Imaging Polarimetry Explorer, is a mission dedicated to X-ray Astronomy. At the time of writing XIPE is in a competitive phase A as fourth medium size mission of ESA (M4). It promises to reopen the polarimetry window in high energy Astrophysics after more than 4 decades thanks to a detector that efficiently exploits the photoelectric effect and to X-ray optics with large effective area. XIPE uniqueness is time-spectrally-spatially- resolved X-ray polarimetry as a breakthrough in high energy astrophysics and fundamental physics. Indeed the payload consists of three Gas Pixel Detectors at the focus of three X-ray optics with a total effective area larger than one XMM mirror but with a low weight. The payload is compatible with the fairing of the Vega launcher. XIPE is designed as an observatory for X-ray astronomers with 75 % of the time dedicated to a Guest Observer competitive program and it is organized as a consortium across Europe with main contributions from Italy, Germany, Spain, United Kingdom, Poland, Sweden.

Using galaxy formation simulations to optimize LIGO follow-up observations - Antolini, Elisa; Caiazzo, Ilaria; Davé, Romeel; Heyl, Jeremy S. (Monthly Notices of the Royal Astronomical Society)
The recent discovery of gravitational radiation from merging black holes poses a challenge of how to organize the electromagnetic follow-up of gravitational-wave events as well as observed bursts of neutrinos. We propose a technique to select the galaxies that are most likely to host the event given some assumptions of whether the particular event is associated with recent star formation, low-metallicity stars or simply proportional to the total stellar mass in the galaxy. We combine data from the 2-MASS Photometric Redshift Galaxy Catalogue with results from galaxy formation simulations to develop observing strategies that potentially reduce the area of sky to search by up to a factor of 2 relative to an unweighted search of galaxies, and a factor of 20 to a search over the entire LIGO localization region.
Keywords: Space and Planetary Science; Astronomy and Astrophysics

Impaired amino acid transport at the blood brain barrier is a cause of autism spectrum disorder - Tarlungeanu, Dora-Clara; Deliu, Elena; Dotter, Christoph; Kara, Majdi; Janiesch, Philipp; Scalise, Mariafrancesca; Galluccio, Michele; Tesulov, Mateja; Morelli, Emanuela; Sönmez, Fatma; Bilgüvar, Kaya; Ohgaki, Ryuichi; et al. (Cell)
Autism spectrum disorders (ASD) are a group of genetic disorders often overlapping with other neurological conditions. We previously described abnormalities in the branched-chain amino acid (BCAA) catabolic pathway as a cause of ASD. Here, we show that the solute carrier transporter 7a5 (SLC7A5), a large neutral amino acid transporter localized at the blood brain barrier (BBB), has an essential role in maintaining normal levels of brain BCAAs. In mice, deletion of Slc7a5 from the endothelial cells of the BBB leads to atypical brain amino acid profile, abnormal mRNA translation, and severe neurological abnormalities. Furthermore, we identified several patients with autistic traits and motor delay carrying deleterious homozygous mutations in the SLC7A5 gene. Finally, we demonstrate that BCAA intracerebroventricular administration ameliorates abnormal behaviors in adult mutant mice. Our data elucidate a neurological syndrome defined by SLC7A5 mutations and support an essential role for the BCAA in human brain function.

Diversified actin protrusions promote environmental exploration but are dispensable for locomotion of leukocytes - Leithner, Alexander F; Eichner, Alexander; Müller, Jan; Reversat, Anne; Brown, Markus; Schwarz, Jan; Merrin, Jack; De Gorter, David; Schur, Florian; Bayerl, Jonathan; De Vries, Ingrid; Wieser, Stefan; et al. (Nature Cell Biology)
Most migrating cells extrude their front by the force of actin polymerization. Polymerization requires an initial nucleation step, which is mediated by factors establishing either parallel filaments in the case of filopodia or branched filaments that form the branched lamellipodial network. Branches are considered essential for regular cell motility and are initiated by the Arp2/3 complex, which in turn is activated by nucleation-promoting factors of the WASP and WAVE families. Here we employed rapid amoeboid crawling leukocytes and found that deletion of the WAVE complex eliminated actin branching and thus lamellipodia formation. The cells were left with parallel filaments at the leading edge, which translated, depending on the differentiation status of the cell, into a unipolar pointed cell shape or cells with multiple filopodia. Remarkably, unipolar cells migrated with increased speed and enormous directional persistence, while they were unable to turn towards chemotactic gradients. Cells with multiple filopodia retained chemotactic activity but their migration was progressively impaired with increasing geometrical complexity of the extracellular environment. These findings establish that diversified leading edge protrusions serve as explorative structures while they slow down actual locomotion.

Optogenetic control of nodal signaling reveals a temporal pattern of nodal signaling regulating cell fate specification during gastrulation - Sako, Keisuke; Pradhan, Saurabh; Barone, Vanessa; Inglés Prieto, Álvaro; Mueller, Patrick; Ruprecht, Verena; Capek, Daniel; Galande, Sanjeev; Janovjak, Harald L; Heisenberg, Carl-Philipp J (Cell Reports)
During metazoan development, the temporal pattern of morphogen signaling is critical for organizing cell fates in space and time. Yet, tools for temporally controlling morphogen signaling within the embryo are still scarce. Here, we developed a photoactivatable Nodal receptor to determine how the temporal pattern of Nodal signaling affects cell fate specification during zebrafish gastrulation. By using this receptor to manipulate the duration of Nodal signaling in vivo by light, we show that extended Nodal signaling within the organizer promotes prechordal plate specification and suppresses endoderm differentiation. Endoderm differentiation is suppressed by extended Nodal signaling inducing expression of the transcriptional repressor goosecoid (gsc) in prechordal plate progenitors, which in turn restrains Nodal signaling from upregulating the endoderm differentiation gene sox17 within these cells. Thus, optogenetic manipulation of Nodal signaling identifies a critical role of Nodal signaling duration for organizer cell fate specification during gastrulation.

Algorithms for algebraic path properties in concurrent systems of constant treewidth components - Chatterjee, Krishnendu; Goharshady, Amir; Ibsen-Jensen, Rasmus; Pavlogiannis, Andreas
We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural problems that arise in program analysis. We consider that each component of the concurrent system is a graph with constant treewidth, a property satisfied by the controlflow graphs of most programs. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis. The study of multiple queries allows us to consider the tradeoff between the resource usage of the one-time preprocessing and for each individual query. The traditional approach constructs the product graph of all components and applies the best-known graph algorithm on the product. In this approach, even the answer to a single query requires the transitive closure (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time. Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time, each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results showing that the worst-case running time of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (i.e., improving the worst-case bound for the shortest path problem in general graphs). Preliminary experimental results show that our algorithms perform favorably on several benchmarks.

Termination analysis of probabilistic programs through Positivstellensatz's - Chatterjee, Krishnendu; Fu, Hongfei; Goharshady, Amir
We consider nondeterministic probabilistic programs with the most basic liveness property of termination. We present efficient methods for termination analysis of nondeterministic probabilistic programs with polynomial guards and assignments. Our approach is through synthesis of polynomial ranking supermartingales, that on one hand significantly generalizes linear ranking supermartingales and on the other hand is a counterpart of polynomial ranking-functions for proving termination of nonprobabilistic programs. The approach synthesizes polynomial ranking-supermartingales through Positivstellensatz's, yielding an efficient method which is not only sound, but also semi-complete over a large subclass of programs. We show experimental results to demonstrate that our approach can handle several classical programs with complex polynomial guards and assignments, and can synthesize efficient quadratic ranking-supermartingales when a linear one does not exist even for simple affine programs.

Study of Fe (Se, Te) micron-sized rings by magnetic force microscopy - Polshyn, Hryhoriy; Zhang, Can; Naibert, Tyler; Eckstein, James; Budakian, Raffi (APS March Meeting 2015)
The study of fluxoid states and fluxoid dynamics in mesoscopic iron-based superconducting rings is valuable for characterizing the basic properties of the superconductor, and may also provide important insight into the superconducting paring symmetry. We report the fabrications of micron-sized rings and disks from thin films of Fe(Se, Te) grown by molecular beam epitaxy. In order to study fluxoid states in rings we developed a custom-tailored version of magnetic force microscopy (MFM). This technique has a number of qualitative advantages for working with mesoscopic superconducting samples in comparison to the conventional MFM and other imaging techniques. We observed metastable fluxoid states in rings of different sizes. Thermally activated fluxoid dynamics of these states was studied and modeled. In addition, we found different regimes of interaction between Fe(Se, Te) ring and MFM tip which are explained. Possibilities of the existence of exotic vortex states and proposals for experiments to test the symmetry of the superconducting order parameter in iron based superconductors are analyzed.

Bayesian inference for stochastic individual-based models of ecological systems: a pest control simulation study - Parise, Francesca; Lygeros, John; Ruess, Jakob (Frontiers in Environmental Science)
Mathematical models are of fundamental importance in the understanding of complex population dynamics. For instance, they can be used to predict the population evolution starting from different initial conditions or to test how a system responds to external perturbations. For this analysis to be meaningful in real applications, however, it is of paramount importance to choose an appropriate model structure and to infer the model parameters from measured data. While many parameter inference methods are available for models based on deterministic ordinary differential equations, the same does not hold for more detailed individual-based models. Here we consider, in particular, stochastic models in which the time evolution of the species abundances is described by a continuous-time Markov chain. These models are governed by a master equation that is typically difficult to solve. Consequently, traditional inference methods that rely on iterative evaluation of parameter likelihoods are computationally intractable. The aim of this paper is to present recent advances in parameter inference for continuous-time Markov chain models, based on a moment closure approximation of the parameter likelihood, and to investigate how these results can help in understanding, and ultimately controlling, complex systems in ecology. Specifically, we illustrate through an agricultural pest case study how parameters of a stochastic individual-based model can be identified from measured data and how the resulting model can be used to solve an optimal control problem in a stochastic setting. In particular, we show how the matter of determining the optimal combination of two different pest control methods can be formulated as a chance constrained optimization problem where the control action is modeled as a state reset, leading to a hybrid system formulation.
Keywords: General Environmental Science

Directly reprogrammed human neurons retain aging-associated transcriptomic signatures and reveal age-related nucleocytoplasmic defects - Mertens, Jerome; Paquola, Apuã C.M.; Ku, Manching; Hatch, Emily; Böhnke, Lena; Ladjevardi, Shauheen; McGrath, Sean; Campbell, Benjamin; Lee, Hyungjun; Herdy, Joseph R.; Gonçalves, J. Tiago; Toda, Tomohisa; et al. (Cell Stem Cell)
Aging is a major risk factor for many human diseases, and in vitro generation of human neurons is an attractive approach for modeling aging-related brain disorders. However, modeling aging in differentiated human neurons has proved challenging. We generated neurons from human donors across a broad range of ages, either by iPSC-based reprogramming and differentiation or by direct conversion into induced neurons (iNs). While iPSCs and derived neurons did not retain aging-associated gene signatures, iNs displayed age-specific transcriptional profiles and revealed age-associated decreases in the nuclear transport receptor RanBP17. We detected an age-dependent loss of nucleocytoplasmic compartmentalization (NCC) in donor fibroblasts and corresponding iNs and found that reduced RanBP17 impaired NCC in young cells, while iPSC rejuvenation restored NCC in aged cells. These results show that iNs retain important aging-related signatures, thus allowing modeling of the aging process in vitro, and they identify impaired NCC as an important factor in human aging.
Keywords: Cell Biology; Genetics; Molecular Medicine

The nucleoporin Nup153 regulates embryonic stem cell pluripotency through gene silencing - Jacinto, Filipe V.; Benner, Chris; HETZER, Martin W (Genes & Development)
Nucleoporins (Nups) are a family of proteins best known as the constituent building blocks of nuclear pore complexes (NPCs), membrane-embedded channels that mediate nuclear transport across the nuclear envelope. Recent evidence suggests that several Nups have additional roles in controlling the activation and silencing of developmental genes; however, the mechanistic details of these functions remain poorly understood. Here, we show that depletion of Nup153 in mouse embryonic stem cells (mESCs) causes the derepression of developmental genes and induction of early differentiation. This loss of stem cell identity is not associated with defects in the nuclear import of key pluripotency factors. Rather, Nup153 binds around the transcriptional start site (TSS) of developmental genes and mediates the recruitment of the polycomb-repressive complex 1 (PRC1) to a subset of its target loci. Our results demonstrate a chromatin-associated role of Nup153 in maintaining stem cell pluripotency by functioning in mammalian epigenetic gene silencing.
Keywords: Developmental Biology; Genetics

Integrated transcriptome and proteome analyses reveal organ-specific proteome deterioration in old rats - Ori, Alessandro; Toyama, Brandon H.; Harris, Michael S.; Bock, Thomas; Iskar, Murat; Bork, Peer; Ingolia, Nicholas T.; HETZER, Martin W; Beck, Martin (Cell Systems)
Aging is associated with the decline of protein, cell, and organ function. Here, we use an integrated approach to characterize gene expression, bulk translation, and cell biology in the brains and livers of young and old rats. We identify 468 differences in protein abundance between young and old animals. The majority are a consequence of altered translation output, that is, the combined effect of changes in transcript abundance and translation efficiency. In addition, we identify 130 proteins whose overall abundance remains unchanged but whose sub-cellular localization, phosphorylation state, or splice-form varies. While some protein-level differences appear to be a generic property of the rats’ chronological age, the majority are specific to one organ. These may be a consequence of the organ’s physiology or the chronological age of the cells within the tissue. Taken together, our study provides an initial view of the proteome at the molecular, sub-cellular, and organ level in young and old rats.
Keywords: Cell Biology; Histology; Pathology and Forensic Medicine

Nuclear pore proteins and the control of genome functions - Ibarra, Arkaitz; HETZER, Martin W (Genes & Development)
Nuclear pore complexes (NPCs) are composed of several copies of ∼30 different proteins called nucleoporins (Nups). NPCs penetrate the nuclear envelope (NE) and regulate the nucleocytoplasmic trafficking of macromolecules. Beyond this vital role, NPC components influence genome functions in a transport-independent manner. Nups play an evolutionarily conserved role in gene expression regulation that, in metazoans, extends into the nuclear interior. Additionally, in proliferative cells, Nups play a crucial role in genome integrity maintenance and mitotic progression. Here we discuss genome-related functions of Nups and their impact on essential DNA metabolism processes such as transcription, chromosome duplication, and segregation.
Keywords: Developmental Biology; Genetics

Linking micronuclei to chromosome fragmentation - Hatch, Emily M.; HETZER, Martin W (Cell)
Human cancer cells bear complex chromosome rearrangements that can be potential drivers of cancer development. However, the molecular mechanisms underlying these rearrangements have been unclear. Zhang et al. use a new technique combining live-cell imaging and single-cell sequencing to demonstrate that chromosomes mis-segregated to micronuclei frequently undergo chromothripsis-like rearrangements in the subsequent cell cycle.
Keywords: General Biochemistry; Genetics and Molecular Biology

Chromothripsis - Hatch, Emily M.; HETZER, Martin W (Current Biology)
Keywords: General Agricultural and Biological Sciences; General Biochemistry; Genetics and Molecular Biology

Evidence for PopIII-like stellar populations in the most luminous Lyα emitters at the epoch of reionisation: Spectroscopic confirmation - Sobral, David; Matthee, Jorryt J; Darvish, Behnam; Schaerer, Daniel; Mobasher, Bahram; Röttgering, Huub; Santos, Sérgio; Hemmati, Shoubaneh (The Astrophysical Journal)
Faint Lyα emitters become increasingly rarer toward the reionization epoch (z ∼ 6–7). However, observations from a very large (∼5 deg2) Lyα narrow-band survey at z = 6.6 show that this is not the case for the most luminous emitters, capable of ionizing their own local bubbles. Here we present follow-up observations of the two most luminous Lyα candidates in the COSMOS field: “MASOSA” and “CR7.” We used X-SHOOTER, SINFONI, and FORS2 on the Very Large Telescope, and DEIMOS on Keck, to confirm both candidates beyond any doubt. We find redshifts of z = 6.541 and z = 6.604 for “MASOSA” and “CR7,” respectively. MASOSA has a strong detection in Lyα with a line width of 386 ± 30 km s−1 (FWHM) and with very high EW0 (>200 Å), but undetected in the continuum, implying very low stellar mass and a likely young, metal-poor stellar population. “CR7,” with an observed Lyα luminosity of 1043.92±0.05 erg s−1 is the most luminous Lyα emitter ever found at z > 6 and is spatially extended (∼16 kpc). “CR7” reveals a narrow Lyα line with 266 ± 15 km s−1 FWHM, being detected in the near-infrared (NIR) (rest-frame UV; β = −2.3 ± 0.1) and in IRAC/Spitzer. We detect a narrow He II 1640 Å emission line (6σ, FWHM = 130 ± 30 km s−1 ) in CR7 which can explain the clear excess seen in the J-band photometry (EW0 ∼ 80 Å). We find no other emission lines from the UV to the NIR in our X-SHOOTER spectra (He II/O III] 1663 Å > 3 and He II/C III] 1908 Å > 2.5). We conclude that CR7 is best explained by a combination of a PopIII-like population, which dominates the rest-frame UV and the nebular emission, and a more normal stellar population, which presumably dominates the mass. Hubble Space Telescope/WFC3 observations show that the light is indeed spatially separated between a very blue component, coincident with Lyα and He II emission, and two red components (∼5 kpc away), which dominate the mass. Our findings are consistent with theoretical predictions of a PopIII wave, with PopIII star formation migrating away from the original sites of star formation.
Keywords: Space and Planetary Science; Astronomy and Astrophysics; dark ages; reionization; first stars – early universe – galaxies: evolution

CF-HiZELS, an ∼10 deg2 emission-line survey with spectroscopic follow-up: Hα, [O III] + Hβ and [O II] luminosity functions at z = 0.8, 1.4 and 2.2 - Sobral, D.; Matthee, Jorryt J; Best, P. N.; Smail, I.; Khostovan, A. A.; Milvang-Jensen, B.; Kim, J.-W.; Stott, J.; Calhau, J.; Nayyeri, H.; Mobasher, B. (Monthly Notices of the Royal Astronomical Society)
We present results from the largest contiguous narrow-band survey in the near-infrared. We have used the wide-field infrared camera/Canada–France–Hawaii Telescope and the lowOH2 filter (1.187 ± 0.005 μm) to survey ≈10 deg2 of contiguous extragalactic sky in the SA22 field. A total of ∼6000 candidate emission-line galaxies are found. We use deep ugrizJK data to obtain robust photometric redshifts. We combine our data with the High-redshift(Z) Emission Line Survey (HiZELS), explore spectroscopic surveys (VVDS, VIPERS) and obtain our own spectroscopic follow-up with KMOS, FMOS and MOSFIRE to derive large samples of high-redshift emission-line selected galaxies: 3471 Hα emitters at z = 0.8, 1343 [O III] + Hβ emitters at z = 1.4 and 572 [O II] emitters at z = 2.2. We probe comoving volumes of >106 Mpc3 and find significant overdensities, including an 8.5σ (spectroscopically confirmed) overdensity of Hα emitters at z = 0.81. We derive Hα, [O III] + Hβ and [O II] luminosity functions at z = 0.8, 1.4, 2.2, respectively, and present implications for future surveys such as Euclid. Our uniquely large volumes/areas allow us to subdivide the samples in thousands of randomized combinations of areas and provide a robust empirical measurement of sample/cosmic variance. We show that surveys for star-forming/emission-line galaxies at a depth similar to ours can only overcome cosmic-variance (errors <10 per cent) if they are based on volumes >5 × 105 Mpc3; errors on L* and ϕ* due to sample (cosmic) variance on surveys probing ∼104 and ∼105 Mpc3 are typically very high: ∼300 and ∼40–60 per cent, respectively.
Keywords: Space and Planetary Science; Astronomy and Astrophysics; galaxies: evolution; galaxies: formation; galaxies: luminosity function; mass function; cosmology: observations; early Universe; large-scale structure of Universe

Identification of the brightest Lyα emitters at z = 6.6: implications for the evolution of the luminosity function in the reionization era - Matthee, Jorryt J; Sobral, David; Santos, Sérgio; Röttgering, Huub; Darvish, Behnam; Mobasher, Bahram (Monthly Notices of the Royal Astronomical Society)
Using wide-field narrow-band surveys, we provide a new measurement of the z = 6.6 Lymanα emitter (LAE) luminosity function (LF), which constraints the bright end for the first time. We use a combination of archival narrow-band NB921 data in UDS and new NB921 measurements in SA22 and COSMOS/UltraVISTA, all observed with the Subaru telescope, with a total area of ∼5 deg2. We exclude lower redshift interlopers by using broad-band optical and near-infrared photometry and also exclude three supernovae with data split over multiple epochs. Combining the UDS and COSMOS samples, we find no evolution of the bright end of the Lyα LF between z = 5.7 and 6.6, which is supported by spectroscopic follow-up, and conclude that sources with Himiko-like luminosity are not as rare as previously thought, with number densities of ∼1.5 × 10−5 Mpc−3. Combined with our wide-field SA22 measurements, our results indicate a non-Schechter-like bright end of the LF at z = 6.6 and a different evolution of observed faint and bright LAEs, overcoming cosmic variance. This differential evolution is also seen in the spectroscopic follow-up of UV-selected galaxies and is now also confirmed for LAEs, and we argue that it may be an effect of reionization. Using a toy model, we show that such differential evolution of the LF is expected, since brighter sources are able to ionize their surroundings earlier, such that Lyα photons are able to escape. Our targets are excellent candidates for detailed follow-up studies and provide the possibility to give a unique view on the earliest stages in the formation of galaxies and reionization process.
Keywords: Space and Planetary Science; Astronomy and Astrophysics

The brightest Lyα emitter: Pop III or black hole? - Pallottini, A.; Ferrara, A.; Pacucci, F.; Gallerani, S.; Salvadori, S.; Schneider, R.; Schaerer, D.; Sobral, D.; Matthee, Jorryt J (Monthly Notices of the Royal Astronomical Society)
CR7 is the brightest z = 6.6 Ly α emitter (LAE) known to date, and spectroscopic follow-up by Sobral et al. suggests that CR7 might host Population (Pop) III stars. We examine this interpretation using cosmological hydrodynamical simulations. Several simulated galaxies show the same ‘Pop III wave’ pattern observed in CR7. However, to reproduce the extreme CR7 Ly α/He II1640 line luminosities (⁠Lα/HeII⁠) a top-heavy initial mass function and a massive ( ≳ 107 M⊙) Pop III burst with age ≲ 2 Myr are required. Assuming that the observed properties of Ly α and He II emission are typical for Pop III, we predict that in the COSMOS/UDS/SA22 fields, 14 out of the 30 LAEs at z = 6.6 with Lα > 1043.3 erg s−1 should also host Pop III stars producing an observable LHeII≳1042.7ergs−1⁠. As an alternate explanation, we explore the possibility that CR7 is instead powered by accretion on to a direct collapse black hole. Our model predicts Lα, LHeII⁠, and X-ray luminosities that are in agreement with the observations. In any case, the observed properties of CR7 indicate that this galaxy is most likely powered by sources formed from pristine gas. We propose that further X-ray observations can distinguish between the two above scenarios.
Keywords: Space and Planetary Science; Astronomy and Astrophysics; black hole physics; stars: Population III; galaxies: high-redshift

On multiple keyword sponsored search auctions with budgets - Colini-Baldeschi, Riccardo; Leonardi, Stefano; Henzinger, Monika H; Starnberger, Martin (ACM Transactions on Economics and Computation)
We study multiple keyword sponsored search auctions with budgets. Each keyword has multiple ad slots with a click-through rate. The bidders have additive valuations, which are linear in the click-through rates, and budgets, which are restricting their overall payments. Additionally, the number of slots per keyword assigned to a bidder is bounded. We show the following results: (1) We give the first mechanism for multiple keywords, where click-through rates differ among slots. Our mechanism is incentive compatible in expectation, individually rational in expectation, and Pareto optimal. (2) We study the combinatorial setting, where each bidder is only interested in a subset of the keywords. We give an incentive compatible, individually rational, Pareto-optimal, and deterministic mechanism for identical click-through rates. (3) We give an impossibility result for incentive compatible, individually rational, Pareto-optimal, and deterministic mechanisms for bidders with diminishing marginal valuations.
Keywords: Algorithms; Economics; Clinching ascending auction; auctions with budgets; Sponsored search auctions

Auctions for heterogeneous items and budget limits - Dütting, Paul; Henzinger, Monika H; Starnberger, Martin (ACM Transactions on Economics and Computation)
We study individual rational, Pareto-optimal, and incentive compatible mechanisms for auctions with heterogeneous items and budget limits. We consider settings with multiunit demand and additive valuations. For single-dimensional valuations we prove a positive result for randomized mechanisms, and a negative result for deterministic mechanisms. While the positive result allows for private budgets, the negative result is for public budgets. For multidimensional valuations and public budgets we prove an impossibility result that applies to deterministic and randomized mechanisms. Taken together this shows the power of randomization in certain settings with heterogeneous items, but it also shows its limitations.
Keywords: Algorithmic game theory; auction theory; Clinching auction; Pareto optimality; Budget limits

Combinatorial auctions with conflict-based externalities - Cheung, Yun Kuen; Henzinger, Monika H; Hoefer, Martin; Starnberger, Martin (11th International Conference on Web and Internet Economics)
Combinatorial auctions (CA) are a well-studied area in algorithmic mechanism design. However, contrary to the standard model, empirical studies suggest that a bidder’s valuation often does not depend solely on the goods assigned to him. For instance, in adwords auctions an advertiser might not want his ads to be displayed next to his competitors’ ads. In this paper, we propose and analyze several natural graph-theoretic models that incorporate such negative externalities, in which bidders form a directed conflict graph with maximum out-degree Δ. We design algorithms and truthful mechanisms for social welfare maximization that attain approximation ratios depending on Δ. For CA, our results are twofold: (1) A lottery that eliminates conflicts by discarding bidders/items independent of the bids. It allows to apply any truthful 𝛼-approximation mechanism for conflict-free valuations and yields an 𝒪(𝛼Δ)-approximation mechanism. (2) For fractionally sub-additive valuations, we design a rounding algorithm via a novel combination of a semi-definite program and a linear program, resulting in a cone program; the approximation ratio is 𝒪((ΔloglogΔ)/logΔ). The ratios are almost optimal given existing hardness results. For adwords auctions, we present several algorithms for the most relevant scenario when the number of items is small. In particular, we design a truthful mechanism with approximation ratio 𝑜(Δ) when the number of items is only logarithmic in the number of bidders.

Ad exchange: Envy-free auctions with mediators - Ben-Zwi, Oren; Henzinger, Monika H; Loitzenbauer, Veronika (11th International Conference on Web and Internet Economics)
Ad exchanges are an emerging platform for trading advertisement slots on the web with billions of dollars revenue per year. Every time a user visits a web page, the publisher of that web page can ask an ad exchange to auction off the ad slots on this page to determine which advertisements are shown at which price. Due to the high volume of traffic, ad networks typically act as mediators for individual advertisers at ad exchanges. If multiple advertisers in an ad network are interested in the ad slots of the same auction, the ad network might use a “local” auction to resell the obtained ad slots among its advertisers. In this work we want to deepen the theoretical understanding of these new markets by analyzing them from the viewpoint of combinatorial auctions. Prior work studied mostly single-item auctions, while we allow the advertisers to express richer preferences over multiple items. We develop a game-theoretic model for the entanglement of the central auction at the ad exchange with the local auctions at the ad networks. We consider the incentives of all three involved parties and suggest a three-party competitive equilibrium, an extension of the Walrasian equilibrium that ensures envy-freeness for all participants. We show the existence of a three-party competitive equilibrium and a polynomial-time algorithm to find one for gross-substitute bidder valuations.

Improved algorithms for decremental single-source reachability on directed graphs - Henzinger, Monika H; Krinninger, Sebastian; Nanongkai, Danupon (42nd International Colloquium on Automata, Languages and Programming)
Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with 𝑜(𝑚𝑛) total update time, where 𝑚 is the number of edges and 𝑛 is the number of nodes in the graph [Henzinger et al. STOC 2014]. The algorithm is a combination of several different algorithms, each for a different 𝑚 vs. 𝑛 trade-off. For the case of 𝑚=Θ(𝑛1.5) the running time is 𝑂(𝑛2.47), just barely below 𝑚𝑛=Θ(𝑛2.5). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of 𝑂̃ (min(𝑚7/6𝑛2/3,𝑚3/4𝑛5/4+𝑜(1),𝑚2/3𝑛4/3+𝑜(1)+𝑚3/7𝑛12/7+𝑜(1))). This gives, e.g., 𝑂(𝑛2.36) for the notorious case 𝑚=Θ(𝑛1.5). We obtain the same upper bounds for the problem of maintaining the strongly connected components of a directed graph undergoing edge deletions. Our algorithms are correct with high probabililty against an oblivious adversary.

Finding 2-edge and 2-vertex strongly connected components in quadratic time - Henzinger, Monika H; Krinninger, Sebastian; Loitzenbauer, Veronika (2nd International Colloquium on Automata, Languages and Programming)
We present faster algorithms for computing the 2-edge and 2-vertex strongly connected components of a directed graph. While in undirected graphs the 2-edge and 2-vertex connected components can be found in linear time, in directed graphs with m edges and n vertices only rather simple O(m n)-time algorithms were known. We use a hierarchical sparsification technique to obtain algorithms that run in time 𝑂(𝑛2). For 2-edge strongly connected components our algorithm gives the first running time improvement in 20 years. Additionally we present an 𝑂(𝑚2/log𝑛)-time algorithm for 2-edge strongly connected components, and thus improve over the O(m n) running time also when 𝑚=𝑂(𝑛). Our approach extends to k-edge and k-vertex strongly connected components for any constant k with a running time of 𝑂(𝑛2log𝑛) for k-edge-connectivity and 𝑂(𝑛3) for k-vertex-connectivity.

Online ad assignment with an ad exchange - Dvořák, Wolfgang; Henzinger, Monika H (12th International Workshop of Approximation and Online Algorithms)
Ad exchanges are becoming an increasingly popular way to sell advertisement slots on the internet. An ad exchange is basically a spot market for ad impressions. A publisher who has already signed contracts reserving advertisement impressions on his pages can choose between assigning a new ad impression for a new page view to a contracted advertiser or to sell it at an ad exchange. This leads to an online revenue maximization problem for the publisher. Given a new impression to sell decide whether (a) to assign it to a contracted advertiser and if so to which one or (b) to sell it at the ad exchange and if so at which reserve price. We make no assumptions about the distribution of the advertiser valuations that participate in the ad exchange and show that there exists a simple primal-dual based online algorithm, whose lower bound for the revenue converges to 𝑅𝐴𝐷𝑋+𝑅𝐴(1−1/𝑒), where 𝑅𝐴𝐷𝑋 is the revenue that the optimum algorithm achieves from the ad exchange and 𝑅𝐴 is the revenue that the optimum algorithm achieves from the contracted advertisers.

Design of dynamic algorithms via primal-dual method - Bhattacharya, Sayan; Henzinger, Monika H; Italiano, Giuseppe F. (42nd International Colloquium on Automata, Languages and Programming)
In this paper, we develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an 𝑂(𝑓2)-approximately optimal solution in 𝑂(𝑓⋅log(𝑚+𝑛)) amortized update time, where 𝑓 is the maximum “frequency” of an element, 𝑛 is the number of sets, and 𝑚 is the maximum number of elements in the universe at any point in time. (2) For the dynamic 𝑏-matching problem, we maintain an 𝑂(1)-approximately optimal solution in 𝑂(log3𝑛) amortized update time, where 𝑛 is the number of nodes in the graph.

Split diversity in constrained conservation prioritization using integer linear programming - Chernomor, Olga; Minh, Bui Quang; Forest, Félix; Klaere, Steffen; Ingram, Travis; Henzinger, Monika H; von Haeseler, Arndt (Methods in Ecology and Evolution)
Phylogenetic diversity (PD) is a measure of biodiversity based on the evolutionary history of species. Here, we discuss several optimization problems related to the use of PD, and the more general measure split diversity (SD), in conservation prioritization. Depending on the conservation goal and the information available about species, one can construct optimization routines that incorporate various conservation constraints. We demonstrate how this information can be used to select sets of species for conservation action. Specifically, we discuss the use of species' geographic distributions, the choice of candidates under economic pressure, and the use of predator–prey interactions between the species in a community to define viability constraints. Despite such optimization problems falling into the area of NP hard problems, it is possible to solve them in a reasonable amount of time using integer programming. We apply integer linear programming to a variety of models for conservation prioritization that incorporate the SD measure. We exemplarily show the results for two data sets: the Cape region of South Africa and a Caribbean coral reef community. Finally, we provide user-friendly software at http://www.cibiv.at/software/pda.

Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture - Henzinger, Monika H; Krinninger, Sebastian; Nanongkai, Danupon; Saranurak, Thatchaphol (47th Annual ACM Symposium on Theory of Computing)
Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an n x n matrix M and will receive n column-vectors of size n, denoted by v1, ..., vn, one by one. After seeing each vector vi, we have to output the product Mvi before we can see the next vector. A naive algorithm can solve this problem using O(n3) time in total, and its running time can be slightly improved to O(n3/log2 n) [Williams SODA'07]. We show that a conjecture that there is no truly subcubic (O(n3-ε)) time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, d-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term "combinatorial algorithms" is interpreted as "Strassen-like algorithms" [Ballard et al. SPAA'11]. The conjecture also leads to hardness results for problems that were previously based on diverse problems and conjectures -- such as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and multiphase -- thus providing a uniform way to prove polynomial hardness results for dynamic algorithms; some of the new proofs are also simpler or even become trivial. The conjecture also leads to stronger and new, non-trivial, hardness results, e.g., for the fully-dynamic densest subgraph and diameter problems.

Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams - Bhattacharya, Sayan; Henzinger, Monika H; Nanongkai, Danupon; Tsourakakis, Charalampos (47th Annual ACM Symposium on Theory of Computing)
While in many graph mining applications it is crucial to handle a stream of updates efficiently in terms of both time and space, not much was known about achieving such type of algorithm. In this paper we study this issue for a problem which lies at the core of many graph mining applications called densest subgraph problem. We develop an algorithm that achieves time- and space-efficiency for this problem simultaneously. It is one of the first of its kind for graph problems to the best of our knowledge. Given an input graph, the densest subgraph is the subgraph that maximizes the ratio between the number of edges and the number of nodes. For any ε>0, our algorithm can, with high probability, maintain a (4+ε)-approximate solution under edge insertions and deletions using ~O(n) space and ~O(1) amortized time per update; here, $n$ is the number of nodes in the graph and ~O hides the O(polylog_{1+ε} n) term. The approximation ratio can be improved to (2+ε) with more time. It can be extended to a (2+ε)-approximation sublinear-time algorithm and a distributed-streaming algorithm. Our algorithm is the first streaming algorithm that can maintain the densest subgraph in one pass. Prior to this, no algorithm could do so even in the special case of an incremental stream and even when there is no time restriction. The previously best algorithm in this setting required O(log n) passes [BahmaniKV12]. The space required by our algorithm is tight up to a polylogarithmic factor.

Welfare maximization with friends-of-friends network externalities - Bhattacharya, Sayan; Dvorák, Wolfgang; Henzinger, Monika H; Starnberger, Martin (32nd International Symposium on Theoretical Aspects of Computer Science)
Online social networks allow the collection of large amounts of data about the influence between users connected by a friendship-like relationship. When distributing items among agents forming a social network, this information allows us to exploit network externalities that each agent receives from his neighbors that get the same item. In this paper we consider Friends-of-Friends (2-hop) network externalities, i.e., externalities that not only depend on the neighbors that get the same item but also on neighbors of neighbors. For these externalities we study a setting where multiple different items are assigned to unit-demand agents. Specifically, we study the problem of welfare maximization under different types of externality functions. Let n be the number of agents and m be the number of items. Our contributions are the following: (1) We show that welfare maximization is APX-hard; we show that even for step functions with 2-hop (and also with 1-hop) externalities it is NP-hard to approximate social welfare better than (1-1/e). (2) On the positive side we present (i) an O(sqrt n)-approximation algorithm for general concave externality functions, (ii) an O(\log m)-approximation algorithm for linear externality functions, and (iii) an (1-1/e)\frac{1}{6}-approximation algorithm for 2-hop step function externalities. We also improve the result from [6] for 1-hop step function externalities by giving a (1-1/e)/2-approximation algorithm.

Truthful unit-demand auctions with budgets revisited - Henzinger, Monika H; Loitzenbauer, Veronika (Theoretical Computer Science)
We consider auctions of indivisible items to unit-demand bidders with budgets. This setting was suggested as an expressive model for single sponsored search auctions. Prior work presented mechanisms that compute bidder-optimal outcomes and are truthful for a restricted set of inputs, i.e., inputs in so-called general position. This condition is easily violated. We provide the first mechanism that is truthful in expectation for all inputs and achieves for each bidder no worse utility than the bidder-optimal outcome. Additionally we give a complete characterization for which inputs mechanisms that compute bidder-optimal outcomes are truthful.

Origami multistability: From single vertices to metasheets - Waitukaitis, Scott R; Menaut, Rémi; Chen, Bryan; Van Hecke, Martin (APS Physics, Physical Review Letters)
We show that the simplest building blocks of origami-based materials - rigid, degree-four vertices - are generically multistable. The existence of two distinct branches of folding motion emerging from the flat state suggests at least bistability, but we show how nonlinearities in the folding motions allow generic vertex geometries to have as many as five stable states. In special geometries with collinear folds and symmetry, more branches emerge leading to as many as six stable states. Tuning the fold energy parameters, we show how monostability is also possible. Finally, we show how to program the stability features of a single vertex into a periodic fold tessellation. The resulting metasheets provide a previously unanticipated functionality - tunable and switchable shape and size via multistability.

V-ATPase activity in the TGN/EE is required for exocytosis and recycling in Arabidopsis - Yu, Luo; Scholl, Stefan; Doering, Anett; Yi, Zhang; Irani, Niloufer; Di Rubbo, Simone; Neumetzler, Lutz; Krishnamoorthy, Praveen; Van Houtte, Isabelle; Mylle, Evelien; Bischoff, Volker; Vernhettes, Samantha; et al. (Nature Plants)
In plants, vacuolar H+-ATPase (V-ATPase) activity acidifies both the trans-Golgi network/early endosome (TGN/EE) and the vacuole. This dual V-ATPase function has impeded our understanding of how the pH homeostasis within the plant TGN/EE controls exo- and endocytosis. Here, we show that the weak V-ATPase mutant deetiolated3 (det3) displayed a pH increase in the TGN/EE, but not in the vacuole, strongly impairing secretion and recycling of the brassinosteroid receptor and the cellulose synthase complexes to the plasma membrane, in contrast to mutants lacking tonoplast-localized V-ATPase activity only. The brassinosteroid insensitivity and the cellulose deficiency defects in det3 were tightly correlated with reduced Golgi and TGN/EE motility. Thus, our results provide strong evidence that acidification of the TGN/EE, but not of the vacuole, is indispensable for functional secretion and recycling in plants.

Lifelong learning with non-i.i.d. tasks - Pentina, Anastasia; Lampert, Christoph
In this work we aim at extending the theoretical foundations of lifelong learning. Previous work analyzing this scenario is based on the assumption that learning tasks are sampled i.i.d. from a task environment or limited to strongly constrained data distributions. Instead, we study two scenarios when lifelong learning is possible, even though the observed tasks do not form an i.i.d. sample: first, when they are sampled from the same environment, but possibly with dependencies, and second, when the task environment is allowed to change over time in a consistent way. In the first case we prove a PAC-Bayesian theorem that can be seen as a direct generalization of the analogous previous result for the i.i.d. case. For the second scenario we propose to learn an inductive bias in form of a transfer procedure. We present a generalization bound and show on a toy example how it can be used to identify a beneficial transfer algorithm.