TY - CONF
AB - We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of computational complexity. The extension problem asks, given topological spaces X; Y , a subspace A ⊆ X, and a (continuous) map f : A → Y , whether f can be extended to a map X → Y . For computational purposes, we assume that X and Y are represented as finite simplicial complexes, A is a subcomplex of X, and f is given as a simplicial map. In this generality the problem is undecidable, as follows from Novikov's result from the 1950s on uncomputability of the fundamental group π1(Y ). We thus study the problem under the assumption that, for some k ≥ 2, Y is (k - 1)-connected; informally, this means that Y has \no holes up to dimension k-1" (a basic example of such a Y is the sphere Sk). We prove that, on the one hand, this problem is still undecidable for dimX = 2k. On the other hand, for every fixed k ≥ 2, we obtain an algorithm that solves the extension problem in polynomial time assuming Y (k - 1)-connected and dimX ≤ 2k - 1. For dimX ≤ 2k - 2, the algorithm also provides a classification of all extensions up to homotopy (continuous deformation). This relies on results of our SODA 2012 paper, and the main new ingredient is a machinery of objects with polynomial-time homology, which is a polynomial-time analog of objects with effective homology developed earlier by Sergeraert et al. We also consider the computation of the higher homotopy groups πk(Y ), k ≥ 2, for a 1-connected Y . Their computability was established by Brown in 1957; we show that πk(Y ) can be computed in polynomial time for every fixed k ≥ 2. On the other hand, Anick proved in 1989 that computing πk(Y ) is #P-hard if k is a part of input, where Y is a cell complex with certain rather compact encoding. We strengthen his result to #P-hardness for Y given as a simplicial complex.
AU - Čadek, Martin
AU - Krcál, Marek
AU - Matoušek, Jiří
AU - Vokřínek, Lukáš
AU - Wagner, Uli
ID - 2807
T2 - 45th Annual ACM Symposium on theory of computing
TI - Extending continuous maps: Polynomiality and undecidability
ER -
TY - JOUR
AB - In order to establish a reference for analysis of the function of auxin and the auxin biosynthesis regulators SHORT INTERNODE/ STYLISH (SHI/STY) during Physcomitrella patens reproductive development, we have described male (antheridial) and female (archegonial) development in detail, including temporal and positional information of organ initiation. This has allowed us to define discrete stages of organ morphogenesis and to show that reproductive organ development in P. patens is highly organized and that organ phyllotaxis differs between vegetative and reproductive development. Using the PpSHI1 and PpSHI2 reporter and knockout lines, the auxin reporters GmGH3pro:GUS and PpPINApro:GFP-GUS, and the auxin-conjugating transgene PpSHI2pro:IAAL, we could show that the PpSHI genes, and by inference also auxin, play important roles for reproductive organ development in moss. The PpSHI genes are required for the apical opening of the reproductive organs, the final differentiation of the egg cell, and the progression of canal cells into a cell death program. The apical cells of the archegonium, the canal cells, and the egg cell are also sites of auxin responsiveness and are affected by reduced levels of active auxin, suggesting that auxin mediates PpSHI function in the reproductive organs.
AU - Landberg, Katarina
AU - Pederson, Eric
AU - Viaene, Tom
AU - Bozorg, Behruz
AU - Friml, Jirí
AU - Jönsson, Henrik
AU - Thelander, Mattias
AU - Sundberg, Eva
ID - 2808
IS - 3
JF - Plant Physiology
TI - The moss physcomitrella patens reproductive organ development is highly organized, affected by the two SHI/STY genes and by the level of active auxin in the SHI/STY expression domain
VL - 162
ER -
TY - JOUR
AB - The epistatic interactions that underlie evolutionary constraint have mainly been studied for constant external conditions. However, environmental changes may modulate epistasis and hence affect genetic constraints. Here we investigate genetic constraints in the adaptive evolution of a novel regulatory function in variable environments, using the lac repressor, LacI, as a model system. We have systematically reconstructed mutational trajectories from wild type LacI to three different variants that each exhibit an inverse response to the inducing ligand IPTG, and analyzed the higher-order interactions between genetic and environmental changes. We find epistasis to depend strongly on the environment. As a result, mutational steps essential to inversion but inaccessible by positive selection in one environment, become accessible in another. We present a graphical method to analyze the observed complex higher-order interactions between multiple mutations and environmental change, and show how the interactions can be explained by a combination of mutational effects on allostery and thermodynamic stability. This dependency of genetic constraint on the environment should fundamentally affect evolutionary dynamics and affects the interpretation of phylogenetic data.
AU - De Vos, Marjon
AU - Poelwijk, Frank
AU - Battich, Nico
AU - Ndika, Joseph
AU - Tans, Sander
ID - 2810
IS - 6
JF - PLoS Genetics
TI - Environmental dependence of genetic constraint
VL - 9
ER -
TY - JOUR
AB - In pipe, channel, and boundary layer flows turbulence first occurs intermittently in space and time: at moderate Reynolds numbers domains of disordered turbulent motion are separated by quiescent laminar regions. Based on direct numerical simulations of pipe flow we argue here that the spatial intermittency has its origin in a nearest neighbor interaction between turbulent regions. We further show that in this regime turbulent flows are intrinsically intermittent with a well-defined equilibrium turbulent fraction but without ever assuming a steady pattern. This transition scenario is analogous to that found in simple models such as coupled map lattices. The scaling observed implies that laminar intermissions of the turbulent flow will persist to arbitrarily large Reynolds numbers.
AU - Avila, Marc
AU - Hof, Björn
ID - 2811
IS - 6
JF - Physical Review E
TI - Nature of laminar-turbulence intermittency in shear flows
VL - 87
ER -
TY - CONF
AB - We consider the problem of deciding whether the persistent homology group of a simplicial pair (K, L) can be realized as the homology H* (X) of some complex X with L ⊂ X ⊂ K. We show that this problem is NP-complete even if K is embedded in ℝ3. As a consequence, we show that it is NP-hard to simplify level and sublevel sets of scalar functions on S3 within a given tolerance constraint. This problem has relevance to the visualization of medical images by isosurfaces. We also show an implication to the theory of well groups of scalar functions: not every well group can be realized by some level set, and deciding whether a well group can be realized is NP-hard.
AU - Attali, Dominique
AU - Bauer, Ulrich
AU - Devillers, Olivier
AU - Glisse, Marc
AU - Lieutier, André
ID - 2812
T2 - Proceedings of the 29th annual symposium on Computational Geometry
TI - Homological reconstruction and simplification in R3
ER -