@inproceedings{688, abstract = {We show that the framework of topological data analysis can be extended from metrics to general Bregman divergences, widening the scope of possible applications. Examples are the Kullback - Leibler divergence, which is commonly used for comparing text and images, and the Itakura - Saito divergence, popular for speech and sound. In particular, we prove that appropriately generalized čech and Delaunay (alpha) complexes capture the correct homotopy type, namely that of the corresponding union of Bregman balls. Consequently, their filtrations give the correct persistence diagram, namely the one generated by the uniformly growing Bregman balls. Moreover, we show that unlike the metric setting, the filtration of Vietoris-Rips complexes may fail to approximate the persistence diagram. We propose algorithms to compute the thus generalized čech, Vietoris-Rips and Delaunay complexes and experimentally test their efficiency. Lastly, we explain their surprisingly good performance by making a connection with discrete Morse theory. }, author = {Edelsbrunner, Herbert and Wagner, Hubert}, issn = {1868-8969}, location = {Brisbane, Australia}, pages = {391--3916}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Topological data analysis with Bregman divergences}}, doi = {10.4230/LIPIcs.SoCG.2017.39}, volume = {77}, year = {2017}, } @article{689, abstract = {Rett syndrome modeling in monkey mirrors the human disorder.}, author = {Novarino, Gaia}, issn = {1946-6234}, journal = {Science Translational Medicine}, number = {393}, publisher = {American Association for the Advancement of Science}, title = {{Rett syndrome modeling goes simian}}, doi = {10.1126/scitranslmed.aan8196}, volume = {9}, year = {2017}, } @article{693, abstract = {Many central synapses contain a single presynaptic active zone and a single postsynaptic density. Vesicular release statistics at such “simple synapses” indicate that they contain a small complement of docking sites where vesicles repetitively dock and fuse. In this work, we investigate functional and morphological aspects of docking sites at simple synapses made between cerebellar parallel fibers and molecular layer interneurons. Using immunogold labeling of SDS-treated freeze-fracture replicas, we find that Cav2.1 channels form several clusters per active zone with about nine channels per cluster. The mean value and range of intersynaptic variation are similar for Cav2.1 cluster numbers and for functional estimates of docking-site numbers obtained from the maximum numbers of released vesicles per action potential. Both numbers grow in relation with synaptic size and decrease by a similar extent with age between 2 wk and 4 wk postnatal. Thus, the mean docking-site numbers were 3.15 at 2 wk (range: 1–10) and 2.03 at 4 wk (range: 1–4), whereas the mean numbers of Cav2.1 clusters were 2.84 at 2 wk (range: 1–8) and 2.37 at 4 wk (range: 1–5). These changes were accompanied by decreases of miniature current amplitude (from 93 pA to 56 pA), active-zone surface area (from 0.0427 μm2 to 0.0234 μm2), and initial success rate (from 0.609 to 0.353), indicating a tightening of synaptic transmission with development. Altogether, these results suggest a close correspondence between the number of functionally defined vesicular docking sites and that of clusters of voltage-gated calcium channels. }, author = {Miki, Takafumi and Kaufmann, Walter and Malagon, Gerardo and Gomez, Laura and Tabuchi, Katsuhiko and Watanabe, Masahiko and Shigemoto, Ryuichi and Marty, Alain}, issn = {0027-8424}, journal = {PNAS}, number = {26}, pages = {E5246 -- E5255}, publisher = {National Academy of Sciences}, title = {{Numbers of presynaptic Ca2+ channel clusters match those of functionally defined vesicular docking sites in single central synapses}}, doi = {10.1073/pnas.1704470114}, volume = {114}, year = {2017}, } @inproceedings{6932, abstract = {LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of O(1), Θ(log* n), or Θ(n), and the design of optimal algorithms can be fully automated. This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: O(1), Θ(log* n), and Θ(n). However, given an LCL problem it is undecidable whether its complexity is Θ(log* n) or Θ(n) in 2-dimensional grids. Nevertheless, if we correctly guess that the complexity of a problem is Θ(log* n), we can completely automate the design of optimal algorithms. For any problem we can find an algorithm that is of a normal form A' o Sk, where A' is a finite function, Sk is an algorithm for finding a maximal independent set in kth power of the grid, and k is a constant. Finally, partially with the help of automated design tools, we classify the complexity of several concrete LCL problems related to colourings and orientations.}, author = {Brandt, Sebastian and Hirvonen, Juho and Korhonen, Janne H. and Lempiäinen, Tuomo and Östergård, Patric R.J. and Purcell, Christopher and Rybicki, Joel and Suomela, Jukka and Uznański, Przemysław}, isbn = {9781450349925}, location = {Washington, DC, United States}, pages = {101--110}, publisher = {ACM}, title = {{LCL problems on grids}}, doi = {10.1145/3087801.3087833}, year = {2017}, } @article{694, abstract = {A change regarding the extent of adhesion - hereafter referred to as adhesion plasticity - between adhesive and less-adhesive states of mammalian cells is important for their behavior. To investigate adhesion plasticity, we have selected a stable isogenic subpopulation of human MDA-MB-468 breast carcinoma cells growing in suspension. These suspension cells are unable to re-adhere to various matrices or to contract three-dimensional collagen lattices. By using transcriptome analysis, we identified the focal adhesion protein tensin3 (Tns3) as a determinant of adhesion plasticity. Tns3 is strongly reduced at mRNA and protein levels in suspension cells. Furthermore, by transiently challenging breast cancer cells to grow under non-adherent conditions markedly reduces Tns3 protein expression, which is regained upon re-adhesion. Stable knockdown of Tns3 in parental MDA-MB-468 cells results in defective adhesion, spreading and migration. Tns3-knockdown cells display impaired structure and dynamics of focal adhesion complexes as determined by immunostaining. Restoration of Tns3 protein expression in suspension cells partially rescues adhesion and focal contact composition. Our work identifies Tns3 as a crucial focal adhesion component regulated by, and functionally contributing to, the switch between adhesive and non-adhesive states in MDA-MB-468 cancer cells.}, author = {Veß, Astrid and Blache, Ulrich and Leitner, Laura and Kurz, Angela and Ehrenpfordt, Anja and Sixt, Michael K and Posern, Guido}, issn = {0021-9533}, journal = {Journal of Cell Science}, number = {13}, pages = {2172 -- 2184}, publisher = {Company of Biologists}, title = {{A dual phenotype of MDA MB 468 cancer cells reveals mutual regulation of tensin3 and adhesion plasticity}}, doi = {10.1242/jcs.200899}, volume = {130}, year = {2017}, } @article{695, abstract = {It has been known since Stefan Vogel's observations in 1969 that solitary female oil bees collect fatty floral oils from specialized oil-secreting plants with the aid of hairy patches on either their legs or abdomen, a reward used as food for their larvae and/or to line their brood cells. Similar adaptations are also known from male oil bees, although the purpose of their oil-collecting behavior has not yet been clarified. Here, we describe a novel pollination system involving male Paratetrapedia oil bees and the tropical herb Anthurium acutifolium. We present ultrastructural morphological details of bee and plant structures involved in this interaction and the composition of floral scents likely mediating pollinator attraction. Inflorescences of A. acutifolium were visited almost exclusively by male P. chocoensis oil bees. The bees mopped with a hairy patch of their abdominal sterna 3 across the inflorescence surface. During this activity on both staminate and pistillate stage inflorescences, bees’ abdomens and legs became loaded with pollen and contacted receptive stigmas. In contrast to what has been observed in other angiosperms visited for the collection of fatty floral oils, the inflorescences/flowers of A. acutifolium do not have structures specialized in oil secretion, i.e., elaiophores. These inflorescences, nonetheless, were strongly scented during the time interval they were visited by the bees. Gas chromatography/mass spectrometry (GC/MS) analyses of dynamic headspace floral samples revealed that inflorescences of both anthetic phases emitted scent bouquets consisting mainly of aliphatic esters, indole and uncommmon terpenoids (megastigmanes). Interestingly enough, our data suggest that the unusual floral scent of A. acutifolium is a perfume reward collected by male P. chocoensis oil bees. This pollination system thus bears a remarkable resemblence with the interactions between perfume-collecting male euglossine bees and their preferred flowers, discovered by Stefan Vogel half a century ago.}, author = {Etl, Florian and Franschitz, Anna and Aguiar, Antonio and Schönenberger, Jürg and Dötterl, Stefan}, issn = {03672530}, journal = {Flora: Morphology, Distribution, Functional Ecology of Plants}, pages = {7 -- 15}, publisher = {Elsevier}, title = {{A perfume collecting male oil bee? Evidences of a novel pollination system involving Anthurium acutifolium Araceae and Paratetrapedia chocoensis Apidae Tapinotaspidini}}, doi = {10.1016/j.flora.2017.02.020}, volume = {232}, year = {2017}, } @inproceedings{697, abstract = {De, Trevisan and Tulsiani [CRYPTO 2010] show that every distribution over n-bit strings which has constant statistical distance to uniform (e.g., the output of a pseudorandom generator mapping n-1 to n bit strings), can be distinguished from the uniform distribution with advantage epsilon by a circuit of size O( 2^n epsilon^2). We generalize this result, showing that a distribution which has less than k bits of min-entropy, can be distinguished from any distribution with k bits of delta-smooth min-entropy with advantage epsilon by a circuit of size O(2^k epsilon^2/delta^2). As a special case, this implies that any distribution with support at most 2^k (e.g., the output of a pseudoentropy generator mapping k to n bit strings) can be distinguished from any given distribution with min-entropy k+1 with advantage epsilon by a circuit of size O(2^k epsilon^2). Our result thus shows that pseudoentropy distributions face basically the same non-uniform attacks as pseudorandom distributions. }, author = {Pietrzak, Krzysztof Z and Skórski, Maciej}, issn = {1868-8969}, location = {Warsaw, Poland}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Non uniform attacks against pseudoentropy}}, doi = {10.4230/LIPIcs.ICALP.2017.39}, volume = {80}, year = {2017}, } @article{698, abstract = {Extracellular matrix signals from the microenvironment regulate gene expression patterns and cell behavior. Using a combination of experiments and geometric models, we demonstrate correlations between cell geometry, three-dimensional (3D) organization of chromosome territories, and gene expression. Fluorescence in situ hybridization experiments showed that micropatterned fibroblasts cultured on anisotropic versus isotropic substrates resulted in repositioning of specific chromosomes, which contained genes that were differentially regulated by cell geometries. Experiments combined with ellipsoid packing models revealed that the mechanosensitivity of chromosomes was correlated with their orientation in the nucleus. Transcription inhibition experiments suggested that the intermingling degree was more sensitive to global changes in transcription than to chromosome radial positioning and its orientations. These results suggested that cell geometry modulated 3D chromosome arrangement, and their neighborhoods correlated with gene expression patterns in a predictable manner. This is central to understanding geometric control of genetic programs involved in cellular homeostasis and the associated diseases. }, author = {Wang, Yejun and Nagarajan, Mallika and Uhler, Caroline and Shivashankar, Gv}, issn = {1059-1524}, journal = {Molecular Biology of the Cell}, number = {14}, pages = {1997 -- 2009}, publisher = {American Society for Cell Biology}, title = {{Orientation and repositioning of chromosomes correlate with cell geometry dependent gene expression}}, doi = {10.1091/mbc.E16-12-0825}, volume = {28}, year = {2017}, } @article{699, abstract = {In antagonistic symbioses, such as host–parasite interactions, one population’s success is the other’s loss. In mutualistic symbioses, such as division of labor, both parties can gain, but they might have different preferences over the possible mutualistic arrangements. The rates of evolution of the two populations in a symbiosis are important determinants of which population will be more successful: Faster evolution is thought to be favored in antagonistic symbioses (the “Red Queen effect”), but disfavored in certain mutualistic symbioses (the “Red King effect”). However, it remains unclear which biological parameters drive these effects. Here, we analyze the effects of the various determinants of evolutionary rate: generation time, mutation rate, population size, and the intensity of natural selection. Our main results hold for the case where mutation is infrequent. Slower evolution causes a long-term advantage in an important class of mutualistic interactions. Surprisingly, less intense selection is the strongest driver of this Red King effect, whereas relative mutation rates and generation times have little effect. In antagonistic interactions, faster evolution by any means is beneficial. Our results provide insight into the demographic evolution of symbionts. }, author = {Veller, Carl and Hayward, Laura and Nowak, Martin and Hilbe, Christian}, issn = {0027-8424}, journal = {PNAS}, number = {27}, pages = {E5396 -- E5405}, publisher = {National Academy of Sciences}, title = {{The red queen and king in finite populations}}, doi = {10.1073/pnas.1702020114}, volume = {114}, year = {2017}, } @article{702, abstract = {Leading autism-associated mutation in mouse partially mimics human disorder. }, author = {Novarino, Gaia}, issn = {1946-6234}, journal = {Science Translational Medicine}, number = {399}, pages = {eaao0972}, publisher = {American Association for the Advancement of Science}, title = {{The riddle of CHD8 haploinsufficiency in autism spectrum disorder}}, doi = {10.1126/scitranslmed.aao0972}, volume = {9}, year = {2017}, } @article{706, abstract = {A hippocampal mossy fiber synapse has a complex structure and is implicated in learning and memory. In this synapse, the mossy fiber boutons attach to the dendritic shaft by puncta adherentia junctions and wrap around a multiply-branched spine, forming synaptic junctions. We have recently shown using transmission electron microscopy, immunoelectron microscopy and serial block face-scanning electron microscopy that atypical puncta adherentia junctions are formed in the afadin-deficient mossy fiber synapse and that the complexity of postsynaptic spines and mossy fiber boutons, the number of spine heads, the area of postsynaptic densities and the density of synaptic vesicles docked to active zones are decreased in the afadin-deficient synapse. We investigated here the roles of afadin in the functional differentiations of the mossy fiber synapse using the afadin-deficient mice. The electrophysiological studies showed that both the release probability of glutamate and the postsynaptic responsiveness to glutamate were markedly reduced, but not completely lost, in the afadin-deficient mossy fiber synapse, whereas neither long-term potentiation nor long-term depression was affected. These results indicate that afadin plays roles in the functional differentiations of the presynapse and the postsynapse of the hippocampal mossy fiber synapse.}, author = {Geng, Xiaoqi and Maruo, Tomohiko and Mandai, Kenji and Supriyanto, Irwan and Miyata, Muneaki and Sakakibara, Shotaro and Mizoguchi, Akira and Takai, Yoshimi and Mori, Masahiro}, issn = {1356-9597}, journal = {Genes to Cells}, number = {8}, pages = {715 -- 722}, publisher = {Wiley-Blackwell}, title = {{Roles of afadin in functional differentiations of hippocampal mossy fiber synapse}}, doi = {10.1111/gtc.12508}, volume = {22}, year = {2017}, } @article{707, abstract = {We answer a question of M. Gromov on the waist of the unit ball.}, author = {Akopyan, Arseniy and Karasev, Roman}, issn = {0024-6093}, journal = {Bulletin of the London Mathematical Society}, number = {4}, pages = {690 -- 693}, publisher = {Wiley}, title = {{A tight estimate for the waist of the ball }}, doi = {10.1112/blms.12062}, volume = {49}, year = {2017}, } @article{709, abstract = {Adipose tissues play key roles in energy homeostasis. Brown adipocytes and beige adipocytes in white adipose tissue (WAT) share the similar characters of thermogenesis, both of them could be potential targets for obesity management. Several thermo-sensitive transient receptor potential channels (thermoTRPs) are shown to be involved in adipocyte biology. However, the expression pattern of thermoTRPs in adipose tissues from obese mice is still unknown. The mRNA expression of thermoTRPs in subcutaneous WAT (sWAT) and interscapular brown adipose tissue (iBAT) from lean and obese mice were measured using reverse transcriptase-quantitative PCRs (RT-qPCR). The results demonstrated that all 10 thermoTRPs are expressed in both iBAT and sWAT, and without significant difference in the mRNA expression level of thermoTRPs between these two tissues. Moreover, Trpv1 and Trpv3 mRNA expression levels in both iBAT and sWAT were significantly decreased in high fat diet (HFD)-induced obese mice and db/db (leptin receptor deficient) mice. Trpm2 mRNA expression level was significantly decreased only in sWAT from HFD-induced obese mice and db/db mice. On the other hand, Trpv2 and Trpv4 mRNA expression levels in iBAT and sWAT were significantly increased in HFD-induced obese mice and db/db mice. Taken together, we conclude that all 10 thermoTRPs are expressed in iBAT and sWAT. And several thermoTRPs differentially expressed in adipose tissues from HFD-induced obese mice and db/db mice, suggesting a potential involvement in anti-obesity regulations.}, author = {Sun, Wuping and Li, Chen and Zhang, Yonghong and Jiang, Changyu and Zhai, Ming-Zhu and Zhou, Qian and Xiao, Lizu and Deng, Qiwen}, issn = {1065-6995}, journal = {Cell Biology International}, number = {8}, pages = {908 -- 913}, publisher = {Wiley-Blackwell}, title = {{Gene expression changes of thermo sensitive transient receptor potential channels in obese mice}}, doi = {10.1002/cbin.10783}, volume = {41}, year = {2017}, } @inproceedings{711, abstract = {Nested weighted automata (NWA) present a robust and convenient automata-theoretic formalism for quantitative specifications. Previous works have considered NWA that processed input words only in the forward direction. It is natural to allow the automata to process input words backwards as well, for example, to measure the maximal or average time between a response and the preceding request. We therefore introduce and study bidirectional NWA that can process input words in both directions. First, we show that bidirectional NWA can express interesting quantitative properties that are not expressible by forward-only NWA. Second, for the fundamental decision problems of emptiness and universality, we establish decidability and complexity results for the new framework which match the best-known results for the special case of forward-only NWA. Thus, for NWA, the increased expressiveness of bidirectionality is achieved at no additional computational complexity. This is in stark contrast to the unweighted case, where bidirectional finite automata are no more expressive but exponentially more succinct than their forward-only counterparts.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan}, issn = {1868-8969}, location = {Berlin, Germany}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Bidirectional nested weighted automata}}, doi = {10.4230/LIPIcs.CONCUR.2017.5}, volume = {85}, year = {2017}, } @article{712, abstract = {We establish a weak–strong uniqueness principle for solutions to entropy-dissipating reaction–diffusion equations: As long as a strong solution to the reaction–diffusion equation exists, any weak solution and even any renormalized solution must coincide with this strong solution. Our assumptions on the reaction rates are just the entropy condition and local Lipschitz continuity; in particular, we do not impose any growth restrictions on the reaction rates. Therefore, our result applies to any single reversible reaction with mass-action kinetics as well as to systems of reversible reactions with mass-action kinetics satisfying the detailed balance condition. Renormalized solutions are known to exist globally in time for reaction–diffusion equations with entropy-dissipating reaction rates; in contrast, the global-in-time existence of weak solutions is in general still an open problem–even for smooth data–, thereby motivating the study of renormalized solutions. The key ingredient of our result is a careful adjustment of the usual relative entropy functional, whose evolution cannot be controlled properly for weak solutions or renormalized solutions.}, author = {Fischer, Julian L}, issn = {0362-546X}, journal = {Nonlinear Analysis: Theory, Methods and Applications}, pages = {181 -- 207}, publisher = {Elsevier}, title = {{Weak–strong uniqueness of solutions to entropy dissipating reaction–diffusion equations}}, doi = {10.1016/j.na.2017.03.001}, volume = {159}, year = {2017}, } @article{713, abstract = {To determine the dynamics of allelic-specific expression during mouse development, we analyzed RNA-seq data from 23 F1 tissues from different developmental stages, including 19 female tissues allowing X chromosome inactivation (XCI) escapers to also be detected. We demonstrate that allelic expression arising from genetic or epigenetic differences is highly tissue-specific. We find that tissue-specific strain-biased gene expression may be regulated by tissue-specific enhancers or by post-transcriptional differences in stability between the alleles. We also find that escape from X-inactivation is tissue-specific, with leg muscle showing an unexpectedly high rate of XCI escapers. By surveying a range of tissues during development, and performing extensive validation, we are able to provide a high confidence list of mouse imprinted genes including 18 novel genes. This shows that cluster size varies dynamically during development and can be substantially larger than previously thought, with the Igf2r cluster extending over 10 Mb in placenta.}, author = {Andergassen, Daniel and Dotter, Christoph and Wenzel, Dyniel and Sigl, Verena and Bammer, Philipp and Muckenhuber, Markus and Mayer, Daniela and Kulinski, Tomasz and Theussl, Hans and Penninger, Josef and Bock, Christoph and Barlow, Denise and Pauler, Florian and Hudson, Quanah}, issn = {2050-084X}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{Mapping the mouse Allelome reveals tissue specific regulation of allelic expression}}, doi = {10.7554/eLife.25125}, volume = {6}, year = {2017}, } @article{714, abstract = {Background HIV-1 infection and drug abuse are frequently co-morbid and their association greatly increases the severity of HIV-1-induced neuropathology. While nucleus accumbens (NAcc) function is severely perturbed by drugs of abuse, little is known about how HIV-1 infection affects NAcc. Methods We used calcium and voltage imaging to investigate the effect of HIV-1 trans-activator of transcription (Tat) on rat NAcc. Based on previous neuronal studies, we hypothesized that Tat modulates intracellular Ca2+ homeostasis of NAcc neurons. Results We provide evidence that Tat triggers a Ca2+ signaling cascade in NAcc medium spiny neurons (MSN) expressing D1-like dopamine receptors leading to neuronal depolarization. Firstly, Tat induced inositol 1,4,5-trisphsophate (IP3) receptor-mediated Ca2+ release from endoplasmic reticulum, followed by Ca2+ and Na+ influx via transient receptor potential canonical channels. The influx of cations depolarizes the membrane promoting additional Ca2+ entry through voltage-gated P/Q-type Ca2+ channels and opening of tetrodotoxin-sensitive Na+ channels. By activating this mechanism, Tat elicits a feed-forward depolarization increasing the excitability of D1-phosphatidylinositol-linked NAcc MSN. We previously found that cocaine targets NAcc neurons directly (independent of the inhibition of dopamine transporter) only when IP3-generating mechanisms are concomitantly initiated. When tested here, cocaine produced a dose-dependent potentiation of the effect of Tat on cytosolic Ca2+. Conclusion We describe for the first time a HIV-1 Tat-triggered Ca2+ signaling in MSN of NAcc involving TRPC and depolarization and a potentiation of the effect of Tat by cocaine, which may be relevant for the reward axis in cocaine-abusing HIV-1-positive patients.}, author = {Brailoiu, Gabriela and Deliu, Elena and Barr, Jeffrey and Console Bram, Linda and Ciuciu, Alexandra and Abood, Mary and Unterwald, Ellen and Brǎiloiu, Eugen}, issn = {0376-8716}, journal = {Drug and Alcohol Dependence}, pages = {7 -- 14}, publisher = {Elsevier}, title = {{HIV Tat excites D1 receptor-like expressing neurons from rat nucleus accumbens}}, doi = {10.1016/j.drugalcdep.2017.04.015}, volume = {178}, year = {2017}, } @article{715, abstract = {D-cycloserine ameliorates breathing abnormalities and survival rate in a mouse model of Rett syndrome.}, author = {Novarino, Gaia}, issn = {1946-6234}, journal = {Science Translational Medicine}, number = {405}, publisher = {American Association for the Advancement of Science}, title = {{More excitation for Rett syndrome}}, doi = {10.1126/scitranslmed.aao4218}, volume = {9}, year = {2017}, } @article{716, abstract = {Two-player games on graphs are central in many problems in formal verification and program analysis, such as synthesis and verification of open systems. In this work, we consider solving recursive game graphs (or pushdown game graphs) that model the control flow of sequential programs with recursion.While pushdown games have been studied before with qualitative objectives-such as reachability and ?-regular objectives- in this work, we study for the first time such games with the most well-studied quantitative objective, the mean-payoff objective. In pushdown games, two types of strategies are relevant: (1) global strategies, which depend on the entire global history; and (2) modular strategies, which have only local memory and thus do not depend on the context of invocation but rather only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two-player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP-hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity by showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games and memoryless modular strategies are sufficient in two-player pushdown games. Finally, we also show that all the problems have the same complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded.}, author = {Chatterjee, Krishnendu and Velner, Yaron}, issn = {0004-5411}, journal = {Journal of the ACM}, number = {5}, pages = {34}, publisher = {ACM}, title = {{The complexity of mean-payoff pushdown games}}, doi = {10.1145/3121408}, volume = {64}, year = {2017}, } @misc{7163, abstract = {The de novo genome assemblies generated for this study, and the associated metadata.}, author = {Fraisse, Christelle}, publisher = {Institute of Science and Technology Austria}, title = {{Supplementary Files for "The deep conservation of the Lepidoptera Z chromosome suggests a non canonical origin of the W"}}, doi = {10.15479/AT:ISTA:7163}, year = {2017}, }