@inproceedings{3133,
abstract = {This note contributes to the point calculus of persistent homology by extending Alexander duality from spaces to real-valued functions. Given a perfect Morse function f: S n+1 →[0, 1 and a decomposition S n+1 = U ∪ V into two (n + 1)-manifolds with common boundary M, we prove elementary relationships between the persistence diagrams of f restricted to U, to V, and to M. },
author = {Edelsbrunner, Herbert and Kerber, Michael},
booktitle = {Proceedings of the twenty-eighth annual symposium on Computational geometry },
location = {Chapel Hill, NC, USA},
pages = {249 -- 258},
publisher = {ACM},
title = {{Alexander duality for functions: The persistent behavior of land and water and shore}},
doi = {10.1145/2261250.2261287},
year = {2012},
}
@inproceedings{3134,
abstract = {It has been an open question whether the sum of finitely many isotropic Gaussian kernels in n ≥ 2 dimensions can have more modes than kernels, until in 2003 Carreira-Perpiñán and Williams exhibited n +1 isotropic Gaussian kernels in ℝ n with n + 2 modes. We give a detailed analysis of this example, showing that it has exponentially many critical points and that the resilience of the extra mode grows like √n. In addition, we exhibit finite configurations of isotropic Gaussian kernels with superlinearly many modes. },
author = {Edelsbrunner, Herbert and Fasy, Brittany and Rote, Günter},
booktitle = {Proceedings of the twenty-eighth annual symposium on Computational geometry },
location = {Chapel Hill, NC, USA},
pages = {91 -- 100},
publisher = {ACM},
title = {{Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions}},
doi = {10.1145/2261250.2261265},
year = {2012},
}
@inproceedings{3135,
abstract = {We introduce consumption games, a model for discrete interactive system with multiple resources that are consumed or reloaded independently. More precisely, a consumption game is a finite-state graph where each transition is labeled by a vector of resource updates, where every update is a non-positive number or ω. The ω updates model the reloading of a given resource. Each vertex belongs either to player □ or player ◇, where the aim of player □ is to play so that the resources are never exhausted. We consider several natural algorithmic problems about consumption games, and show that although these problems are computationally hard in general, they are solvable in polynomial time for every fixed number of resource types (i.e., the dimension of the update vectors) and bounded resource updates. },
author = {Brázdil, Brázdil and Chatterjee, Krishnendu and Kučera, Antonín and Novotny, Petr},
location = {Berkeley, CA, USA},
pages = {23 -- 38},
publisher = {Springer},
title = {{Efficient controller synthesis for consumption games with multiple resource types}},
doi = {10.1007/978-3-642-31424-7_8},
volume = {7358},
year = {2012},
}
@inproceedings{3136,
abstract = {Continuous-time Markov chains (CTMC) with their rich theory and efficient simulation algorithms have been successfully used in modeling stochastic processes in diverse areas such as computer science, physics, and biology. However, systems that comprise non-instantaneous events cannot be accurately and efficiently modeled with CTMCs. In this paper we define delayed CTMCs, an extension of CTMCs that allows for the specification of a lower bound on the time interval between an event's initiation and its completion, and we propose an algorithm for the computation of their behavior. Our algorithm effectively decomposes the computation into two stages: a pure CTMC governs event initiations while a deterministic process guarantees lower bounds on event completion times. Furthermore, from the nature of delayed CTMCs, we obtain a parallelized version of our algorithm. We use our formalism to model genetic regulatory circuits (biological systems where delayed events are common) and report on the results of our numerical algorithm as run on a cluster. We compare performance and accuracy of our results with results obtained by using pure CTMCs. © 2012 Springer-Verlag.},
author = {Guet, Calin C and Gupta, Ashutosh and Henzinger, Thomas A and Mateescu, Maria and Sezgin, Ali},
location = {Berkeley, CA, USA},
pages = {294 -- 309},
publisher = {Springer},
title = {{Delayed continuous time Markov chains for genetic regulatory circuits}},
doi = {10.1007/978-3-642-31424-7_24},
volume = {7358 },
year = {2012},
}
@inproceedings{3155,
abstract = {We propose synchronous interfaces, a new interface theory for discrete-time systems. We use an application to time-triggered scheduling to drive the design choices for our formalism; in particular, additionally to deriving useful mathematical properties, we focus on providing a syntax which is adapted to natural high-level system modeling. As a result, we develop an interface model that relies on a guarded-command based language and is equipped with shared variables and explicit discrete-time clocks. We define all standard interface operations: compatibility checking, composition, refinement, and shared refinement. Apart from the synchronous interface model, the contribution of this paper is the establishment of a formal relation between interface theories and real-time scheduling, where we demonstrate a fully automatic framework for the incremental computation of time-triggered schedules.},
author = {Delahaye, Benoît and Fahrenberg, Uli and Henzinger, Thomas A and Legay, Axel and Nickovic, Dejan},
location = {Stockholm, Sweden},
pages = {203 -- 218},
publisher = {Springer},
title = {{Synchronous interface theories and time triggered scheduling}},
doi = {10.1007/978-3-642-30793-5_13},
volume = {7273},
year = {2012},
}
@article{3156,
abstract = {Dispersal is crucial for gene flow and often determines the long-term stability of meta-populations, particularly in rare species with specialized life cycles. Such species are often foci of conservation efforts because they suffer disproportionally from degradation and fragmentation of their habitat. However, detailed knowledge of effective gene flow through dispersal is often missing, so that conservation strategies have to be based on mark-recapture observations that are suspected to be poor predictors of long-distance dispersal. These constraints have been especially severe in the study of butterfly populations, where microsatellite markers have been difficult to develop. We used eight microsatellite markers to analyse genetic population structure of the Large Blue butterfly Maculinea arion in Sweden. During recent decades, this species has become an icon of insect conservation after massive decline throughout Europe and extinction in Britain followed by reintroduction of a seed population from the Swedish island of Öland. We find that populations are highly structured genetically, but that gene flow occurs over distances 15 times longer than the maximum distance recorded from mark-recapture studies, which can only be explained by maximum dispersal distances at least twice as large as previously accepted. However, we also find evidence that gaps between sites with suitable habitat exceeding ∼ 20 km induce genetic erosion that can be detected from bottleneck analyses. Although further work is needed, our results suggest that M. arion can maintain fully functional metapopulations when they consist of optimal habitat patches that are no further apart than ∼10 km.},
author = {Ugelvig, Line V and Andersen, Anne and Boomsma, Jacobus and Nash, David},
journal = {Molecular Ecology},
number = {13},
pages = {3224 -- 3236},
publisher = {Wiley-Blackwell},
title = {{Dispersal and gene flow in the rare parasitic Large Blue butterfly Maculinea arion}},
doi = {10.1111/j.1365-294X.2012.05592.x},
volume = {21},
year = {2012},
}
@article{3157,
abstract = {Colorectal tumours that are wild type for KRAS are often sensitive to EGFR blockade, but almost always develop resistance within several months of initiating therapy. The mechanisms underlying this acquired resistance to anti-EGFR antibodies are largely unknown. This situation is in marked contrast to that of small-molecule targeted agents, such as inhibitors of ABL, EGFR, BRAF and MEK, in which mutations in the genes encoding the protein targets render the tumours resistant to the effects of the drugs. The simplest hypothesis to account for the development of resistance to EGFR blockade is that rare cells with KRAS mutations pre-exist at low levels in tumours with ostensibly wild-type KRAS genes. Although this hypothesis would seem readily testable, there is no evidence in pre-clinical models to support it, nor is there data from patients. To test this hypothesis, we determined whether mutant KRAS DNA could be detected in the circulation of 28 patients receiving monotherapy with panitumumab, a therapeutic anti-EGFR antibody. We found that 9 out of 24 (38%) patients whose tumours were initially KRAS wild type developed detectable mutations in KRAS in their sera, three of which developed multiple different KRAS mutations. The appearance of these mutations was very consistent, generally occurring between 5 and 6months following treatment. Mathematical modelling indicated that the mutations were present in expanded subclones before the initiation of panitumumab treatment. These results suggest that the emergence of KRAS mutations is a mediator of acquired resistance to EGFR blockade and that these mutations can be detected in a non-invasive manner. They explain why solid tumours develop resistance to targeted therapies in a highly reproducible fashion.},
author = {Diaz Jr, Luis and Williams, Richard and Wu, Jian and Kinde, Isaac and Hecht, Joel and Berlin, Jordan and Allen, Benjamin and Božić, Ivana and Reiter, Johannes and Nowak, Martin and Kinzler, Kenneth and Oliner, Kelly and Vogelstein, Bert},
journal = {Nature},
number = {7404},
pages = {537 -- 540},
publisher = {Nature Publishing Group},
title = {{The molecular evolution of acquired resistance to targeted EGFR blockade in colorectal cancers}},
doi = {10.1038/nature11219},
volume = {486},
year = {2012},
}
@article{3158,
abstract = {We describe here the development and characterization of a conditionally inducible mouse model expressing Lifeact-GFP, a peptide that reports the dynamics of filamentous actin. We have used this model to study platelets, megakaryocytes and melanoblasts and we provide evidence that Lifeact-GFP is a useful reporter in these cell types ex vivo. In the case of platelets and megakaryocytes, these cells are not transfectable by traditional methods, so conditional activation of Lifeact allows the study of actin dynamics in these cells live. We studied melanoblasts in native skin explants from embryos, allowing the visualization of live actin dynamics during cytokinesis and migration. Our study revealed that melanoblasts lacking the small GTPase Rac1 show a delay in the formation of new pseudopodia following cytokinesis that accounts for the previously reported cytokinesis delay in these cells. Thus, through use of this mouse model, we were able to gain insights into the actin dynamics of cells that could only previously be studied using fixed specimens or following isolation from their native tissue environment.},
author = {Schachtner, Hannah and Li, Ang and Stevenson, David and Calaminus, Simon and Thomas, Steven and Watson, Steve and Sixt, Michael K and Wedlich Söldner, Roland and Strathdee, Douglas and Machesky, Laura},
journal = {European Journal of Cell Biology},
number = {11-12},
pages = {923 -- 929},
publisher = {Elsevier},
title = {{Tissue inducible Lifeact expression allows visualization of actin dynamics in vivo and ex vivo}},
doi = {10.1016/j.ejcb.2012.04.002},
volume = {91},
year = {2012},
}
@article{3159,
abstract = {The structure of hierarchical networks in biological and physical systems has long been characterized using the Horton-Strahler ordering scheme. The scheme assigns an integer order to each edge in the network based on the topology of branching such that the order increases from distal parts of the network (e.g., mountain streams or capillaries) to the "root" of the network (e.g., the river outlet or the aorta). However, Horton-Strahler ordering cannot be applied to networks with loops because they they create a contradiction in the edge ordering in terms of which edge precedes another in the hierarchy. Here, we present a generalization of the Horton-Strahler order to weighted planar reticular networks, where weights are assumed to correlate with the importance of network edges, e.g., weights estimated from edge widths may correlate to flow capacity. Our method assigns hierarchical levels not only to edges of the network, but also to its loops, and classifies the edges into reticular edges, which are responsible for loop formation, and tree edges. In addition, we perform a detailed and rigorous theoretical analysis of the sensitivity of the hierarchical levels to weight perturbations. In doing so, we show that the ordering of the reticular edges is more robust to noise in weight estimation than is the ordering of the tree edges. We discuss applications of this generalized Horton-Strahler ordering to the study of leaf venation and other biological networks.},
author = {Mileyko, Yuriy and Edelsbrunner, Herbert and Price, Charles and Weitz, Joshua},
journal = {PLoS One},
number = {6},
publisher = {Public Library of Science},
title = {{Hierarchical ordering of reticular networks}},
doi = {10.1371/journal.pone.0036715},
volume = {7},
year = {2012},
}
@article{3160,
abstract = {There is a long-running controversy about how early cell fate decisions are made in the developing mammalian embryo. 1,2 In particular, it is controversial when the first events that can predict the establishment of the pluripotent and extra-embryonic lineages in the blastocyst of the pre-implantation embryo occur. It has long been proposed that the position and polarity of cells at the 16- to 32-cell stage embryo influence their decision to either give rise to the pluripotent cell lineage that eventually contributes to the inner cell mass (ICM), comprising the primitive endoderm (PE) and the epiblast (EPI), or the extra-embryonic trophectoderm (TE) surrounding the blastocoel. The positioning of cells in the embryo at this developmental stage could largely be the result of random events, making this a stochastic model of cell lineage allocation. Contrary to such a stochastic model, some studies have detected putative differences in the lineage potential of individual blastomeres before compaction, indicating that the first cell fate decisions may occur as early as at the 4-cell stage. Using a non-invasive, quantitative in vivo imaging assay to study the kinetic behavior of Oct4 (also known as POU5F1), a key transcription factor (TF) controlling pre-implantation development in the mouse embryo, 3-5 a recent study identifies Oct4 kinetics as a predictive measure of cell lineage patterning in the early mouse embryo. 6 Here, we discuss the implications of such molecular heterogeneities in early development and offer potential avenues toward a mechanistic understanding of these observations, contributing to the resolution of the controversy of developmental cell lineage allocation.},
author = {Pantazis, Periklis and Bollenbach, Tobias},
journal = {Cell Cycle},
number = {11},
pages = {2055 -- 2058},
publisher = {Taylor and Francis},
title = {{Transcription factor kinetics and the emerging asymmetry in the early mammalian embryo}},
doi = {10.4161/cc.20118},
volume = {11},
year = {2012},
}
@article{3161,
abstract = {Some inflammatory stimuli trigger activation of the NLRP3 inflammasome by inducing efflux of cellular potassium. Loss of cellular potassium is known to potently suppress protein synthesis, leading us to test whether the inhibition of protein synthesis itself serves as an activating signal for the NLRP3 inflammasome. Murine bone marrow-derived macrophages, either primed by LPS or unprimed, were exposed to a panel of inhibitors of ribosomal function: ricin, cycloheximide, puromycin, pactamycin, and anisomycin. Macrophages were also exposed to nigericin, ATP, monosodium urate (MSU), and poly I:C. Synthesis of pro-IL-ß and release of IL-1ß from cells in response to these agents was detected by immunoblotting and ELISA. Release of intracellular potassium was measured by mass spectrometry. Inhibition of translation by each of the tested translation inhibitors led to processing of IL-1ß, which was released from cells. Processing and release of IL-1ß was reduced or absent from cells deficient in NLRP3, ASC, or caspase-1, demonstrating the role of the NLRP3 inflammasome. Despite the inability of these inhibitors to trigger efflux of intracellular potassium, the addition of high extracellular potassium suppressed activation of the NLRP3 inflammasome. MSU and double-stranded RNA, which are known to activate the NLRP3 inflammasome, also substantially inhibited protein translation, supporting a close association between inhibition of translation and inflammasome activation. These data demonstrate that translational inhibition itself constitutes a heretofore-unrecognized mechanism underlying IL-1ß dependent inflammatory signaling and that other physical, chemical, or pathogen-associated agents that impair translation may lead to IL-1ß-dependent inflammation through activation of the NLRP3 inflammasome. For agents that inhibit translation through decreased cellular potassium, the application of high extracellular potassium restores protein translation and suppresses activation of the NLRP inflammasome. For agents that inhibit translation through mechanisms that do not involve loss of potassium, high extracellular potassium suppresses IL-1ß processing through a mechanism that remains undefined.},
author = {Vyleta, Meghan and Wong, John and Magun, Bruce},
journal = {PLoS One},
number = {5},
publisher = {Public Library of Science},
title = {{Suppression of ribosomal function triggers innate immune signaling through activation of the NLRP3 inflammasome}},
doi = {10.1371/journal.pone.0036044},
volume = {7},
year = {2012},
}
@inproceedings{3162,
abstract = {Given a dense-time real-valued signal and a parameterized temporal logic formula with both magnitude and timing parameters, we compute the subset of the parameter space that renders the formula satisfied by the trace. We provide two preliminary implementations, one which follows the exact semantics and attempts to compute the validity domain by quantifier elimination in linear arithmetics and one which conducts adaptive search in the parameter space.},
author = {Asarin, Eugene and Donzé, Alexandre and Maler, Oded and Nickovic, Dejan},
location = {San Francisco, CA, United States},
pages = {147 -- 160},
publisher = {Springer},
title = {{Parametric identification of temporal properties}},
doi = {10.1007/978-3-642-29860-8_12},
volume = {7186},
year = {2012},
}
@article{3164,
abstract = {Overview of the Special Issue on structured prediction and inference.},
author = {Blaschko, Matthew and Lampert, Christoph},
journal = {International Journal of Computer Vision},
number = {3},
pages = {257 -- 258},
publisher = {Springer},
title = {{Guest editorial: Special issue on structured prediction and inference}},
doi = {10.1007/s11263-012-0530-y},
volume = {99},
year = {2012},
}
@inproceedings{3165,
abstract = {Computing the winning set for Büchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is Õ(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the Õ(n·m) boundary by presenting a new technique that reduces the running time to O(n 2). This bound also leads to O(n 2) time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of Õ(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n 3)), and (3) in Markov decision processes (improving for m > n 4/3 an earlier bound of O(min(m 1.5, m·n 2/3)). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n 2), which is an improvement over earlier bounds for m > n 4/3. Finally, we show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.},
author = {Chatterjee, Krishnendu and Henzinger, Monika},
booktitle = {Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms},
location = {Kyoto, Japan},
pages = {1386 -- 1399},
publisher = {SIAM},
title = {{An O(n2) time algorithm for alternating Büchi games}},
doi = {10.1137/1.9781611973099.109},
year = {2012},
}
@article{3166,
abstract = {There is evidence that the genetic code was established prior to the existence of proteins, when metabolism was powered by ribozymes. Also, early proto-organisms had to rely on simple anaerobic bioenergetic processes. In this work I propose that amino acid fermentation powered metabolism in the RNA world, and that this was facilitated by proto-adapters, the precursors of the tRNAs. Amino acids were used as carbon sources rather than as catalytic or structural elements. In modern bacteria, amino acid fermentation is known as the Stickland reaction. This pathway involves two amino acids: the first undergoes oxidative deamination, and the second acts as an electron acceptor through reductive deamination. This redox reaction results in two keto acids that are employed to synthesise ATP via substrate-level phosphorylation. The Stickland reaction is the basic bioenergetic pathway of some bacteria of the genus Clostridium. Two other facts support Stickland fermentation in the RNA world. First, several Stickland amino acid pairs are synthesised in abiotic amino acid synthesis. This suggests that amino acids that could be used as an energy substrate were freely available. Second, anticodons that have complementary sequences often correspond to amino acids that form Stickland pairs. The main hypothesis of this paper is that pairs of complementary proto-adapters were assigned to Stickland amino acids pairs. There are signatures of this hypothesis in the genetic code. Furthermore, it is argued that the proto-adapters formed double strands that brought amino acid pairs into proximity to facilitate their mutual redox reaction, structurally constraining the anticodon pairs that are assigned to these amino acid pairs. Significance tests which randomise the code are performed to study the extent of the variability of the energetic (ATP) yield. Random assignments can lead to a substantial yield of ATP and maintain enough variability, thus selection can act and refine the assignments into a proto-code that optimises the energetic yield. Monte Carlo simulations are performed to evaluate the establishment of these simple proto-codes, based on amino acid substitutions and codon swapping. In all cases, donor amino acids are assigned to anticodons composed of U+G, and have low redundancy (1-2 codons), whereas acceptor amino acids are assigned to the the remaining codons. These bioenergetic and structural constraints allow for a metabolic role for amino acids before their co-option as catalyst cofactors. Reviewers: this article was reviewed by Prof. William Martin, Prof. Eors Szathmary (nominated by Dr. Gaspar Jekely) and Dr. Adam Kun (nominated by Dr. Sandor Pongor)},
author = {Vladar, Harold},
journal = {Biology Direct},
publisher = {BioMed Central},
title = {{Amino acid fermentation at the origin of the genetic code}},
doi = {10.1186/1745-6150-7-6},
volume = {7},
year = {2012},
}
@article{3167,
author = {Weber, Michele},
journal = {Science},
number = {6077},
pages = {32--34},
publisher = {American Association for the Advancement of Science},
title = {{NextGen speaks 13 }},
doi = {10.1126/science.336.6077.32},
volume = {336},
year = {2012},
}
@article{3168,
abstract = {The induction of a signaling pathway is characterized by transient complex formation and mutual posttranslational modification of proteins. To faithfully capture this combinatorial process in a mathematical model is an important challenge in systems biology. Exploiting the limited context on which most binding and modification events are conditioned, attempts have been made to reduce the combinatorial complexity by quotienting the reachable set of molecular species into species aggregates while preserving the deterministic semantics of the thermodynamic limit. Recently, we proposed a quotienting that also preserves the stochastic semantics and that is complete in the sense that the semantics of individual species can be recovered from the aggregate semantics. In this paper, we prove that this quotienting yields a sufficient condition for weak lumpability (that is to say that the quotient system is still Markovian for a given set of initial distributions) and that it gives rise to a backward Markov bisimulation between the original and aggregated transition system (which means that the conditional probability of being in a given state in the original system knowing that we are in its equivalence class is an invariant of the system). We illustrate the framework on a case study of the epidermal growth factor (EGF)/insulin receptor crosstalk.},
author = {Feret, Jérôme and Henzinger, Thomas A and Koeppl, Heinz and Petrov, Tatjana},
journal = {Theoretical Computer Science},
pages = {137 -- 164},
publisher = {Elsevier},
title = {{Lumpability abstractions of rule based systems}},
doi = {10.1016/j.tcs.2011.12.059},
volume = {431},
year = {2012},
}
@article{3241,
abstract = {We prove a negative result concerning error reduction by parallel repetition for computationally sound protocols, e.g., interactive arguments. Our main result is a complete and computationally sound eight round interactive argument for which k-fold parallel repetition does not reduce the error below a constant for any polynomial k. The starting point for our construction is the work of Bellare, Impagliazzo and Naor (FOCS'97). For any fixed k, they construct a four round protocol for which k-fold parallel repetition does not lower the soundness error. The communication complexity of this protocol is linear in k. By using universal arguments due to Barak and Goldreich (CCC 2002), we turn this protocol into an eight-round protocol whose complexity is basically independent of k. },
author = {Krzysztof Pietrzak and Wikström, Douglas},
journal = {Journal of Cryptology},
number = {1},
pages = {116 -- 135},
publisher = {Springer},
title = {{Parallel repetition of computationally sound protocols revisited}},
doi = {10.1007/s00145-010-9090-x},
volume = {25},
year = {2012},
}
@article{3242,
abstract = {Due to the omnipresent risk of epidemics, insect societies have evolved sophisticated disease defences at the individual and colony level. An intriguing yet little understood phenomenon is that social contact to pathogen-exposed individuals reduces susceptibility of previously naive nestmates to this pathogen. We tested whether such social immunisation in Lasius ants against the entomopathogenic fungus Metarhizium anisopliae is based on active upregulation of the immune system of nestmates following contact to an infectious individual or passive protection via transfer of immune effectors among group members—that is, active versus passive immunisation. We found no evidence for involvement of passive immunisation via transfer of antimicrobials among colony members. Instead, intensive allogrooming behaviour between naive and pathogen-exposed ants before fungal conidia firmly attached to their cuticle suggested passage of the pathogen from the exposed individuals to their nestmates. By tracing fluorescence-labelled conidia we indeed detected frequent pathogen transfer to the nestmates, where they caused low-level infections as revealed by growth of small numbers of fungal colony forming units from their dissected body content. These infections rarely led to death, but instead promoted an enhanced ability to inhibit fungal growth and an active upregulation of immune genes involved in antifungal defences (defensin and prophenoloxidase, PPO). Contrarily, there was no upregulation of the gene cathepsin L, which is associated with antibacterial and antiviral defences, and we found no increased antibacterial activity of nestmates of fungus-exposed ants. This indicates that social immunisation after fungal exposure is specific, similar to recent findings for individual-level immune priming in invertebrates. Epidemiological modeling further suggests that active social immunisation is adaptive, as it leads to faster elimination of the disease and lower death rates than passive immunisation. Interestingly, humans have also utilised the protective effect of low-level infections to fight smallpox by intentional transfer of low pathogen doses (“variolation” or “inoculation”).},
author = {Konrad, Matthias and Vyleta, Meghan and Theis, Fabian and Stock, Miriam and Tragust, Simon and Klatt, Martina and Drescher, Verena and Marr, Carsten and Ugelvig, Line V and Cremer, Sylvia},
journal = {PLoS Biology},
number = {4},
publisher = {Public Library of Science},
title = {{Social transfer of pathogenic fungus promotes active immunisation in ant colonies}},
doi = {10.1371/journal.pbio.1001300},
volume = {10},
year = {2012},
}
@article{3243,
author = {Danowski, Patrick},
journal = {Büchereiperspektiven},
pages = {11},
publisher = {Buchereiverband Österreichs},
title = {{Zwischen Technologie und Information}},
volume = {1/2012},
year = {2012},
}
@article{3244,
author = {Danowski, Patrick},
journal = {BuB – Forum Bibliothek und Information},
number = {4},
pages = {284},
publisher = {Bock & Herchen Verlag},
title = {{Die Zeit des Abwartens ist vorbei!}},
volume = {64},
year = {2012},
}
@article{3245,
abstract = {How cells orchestrate their behavior during collective migration is a long-standing question. Using magnetic tweezers to apply mechanical stimuli to Xenopus mesendoderm cells, Weber etal. (2012) now reveal, in this issue of Developmental Cell, a cadherin-mediated mechanosensitive response that promotes cell polarization and movement persistence during the collective mesendoderm migration in gastrulation.},
author = {Behrndt, Martin and Heisenberg, Carl-Philipp J},
journal = {Developmental Cell},
number = {1},
pages = {3 -- 4},
publisher = {Cell Press},
title = {{Spurred by resistance mechanosensation in collective migration}},
doi = {10.1016/j.devcel.2011.12.018},
volume = {22},
year = {2012},
}
@article{3246,
abstract = {Visualizing and analyzing shape changes at various scales, ranging from single molecules to whole organisms, are essential for understanding complex morphogenetic processes, such as early embryonic development. Embryo morphogenesis relies on the interplay between different tissues, the properties of which are again determined by the interaction between their constituent cells. Cell interactions, on the other hand, are controlled by various molecules, such as signaling and adhesion molecules, which in order to exert their functions need to be spatiotemporally organized within and between the interacting cells. In this review, we will focus on the role of cell adhesion functioning at different scales to organize cell, tissue and embryo morphogenesis. We will specifically ask how the subcellular distribution of adhesion molecules controls the formation of cell-cell contacts, how cell-cell contacts determine tissue shape, and how tissue interactions regulate embryo morphogenesis.},
author = {Barone, Vanessa and Heisenberg, Carl-Philipp J},
journal = {Current Opinion in Cell Biology},
number = {1},
pages = {148 -- 153},
publisher = {Elsevier},
title = {{Cell adhesion in embryo morphogenesis}},
doi = {10.1016/j.ceb.2011.11.006},
volume = {24},
year = {2012},
}
@article{3247,
abstract = {The Brazilian Merganser is a very rare and threatened species that nowadays inhabits only a few protected areas and their surroundings in the Brazilian territory. In order to estimate the remaining genetic diversity and population structure in this species, two mitochondrial genes were sequenced in 39 individuals belonging to two populations and in one individual collected in Argentina in 1950. We found a highly significant divergence between two major remaining populations of Mergus octosetaceus, which suggests a historical population structure in this species. Furthermore, two deeply divergent lineages were found in a single location, which could due to current or historical secondary contact. Based on the available genetic data, we point out future directions which would contribute to design strategies for conservation and management of this threatened species.},
author = {Vilaça, Sibelle and Fernandes Redondo, Rodrigo A and Lins, Lívia and Santos, Fabrício},
journal = {Conservation Genetics},
number = {1},
pages = {293 -- 298},
publisher = {Springer},
title = {{Remaining genetic diversity in Brazilian Merganser (Mergus octosetaceus)}},
doi = {10.1007/s10592-011-0262-5},
volume = {13},
year = {2012},
}
@article{3248,
abstract = {We describe RTblob, a high speed vision system that detects objects in cluttered scenes based on their color and shape at a speed of over 800 frames/s. Because the system is available as open-source software and relies only on off-the-shelf PC hardware components, it can provide the basis for multiple application scenarios. As an illustrative example, we show how RTblob can be used in a robotic table tennis scenario to estimate ball trajectories through 3D space simultaneously from four cameras images at a speed of 200 Hz.},
author = {Lampert, Christoph and Peters, Jan},
journal = {Journal of Real-Time Image Processing},
number = {1},
pages = {31 -- 41},
publisher = {Springer},
title = {{Real-time detection of colored objects in multiple camera streams with off-the-shelf hardware components}},
doi = {10.1007/s11554-010-0168-3},
volume = {7},
year = {2012},
}
@article{3249,
abstract = {Boolean notions of correctness are formalized by preorders on systems. Quantitative measures of correctness can be formalized by real-valued distance functions between systems, where the distance between implementation and specification provides a measure of "fit" or "desirability". We extend the simulation preorder to the quantitative setting by making each player of a simulation game pay a certain price for her choices. We use the resulting games with quantitative objectives to define three different simulation distances. The correctness distance measures how much the specification must be changed in order to be satisfied by the implementation. The coverage distance measures how much the implementation restricts the degrees of freedom offered by the specification. The robustness distance measures how much a system can deviate from the implementation description without violating the specification. We consider these distances for safety as well as liveness specifications. The distances can be computed in polynomial time for safety specifications, and for liveness specifications given by weak fairness constraints. We show that the distance functions satisfy the triangle inequality, that the distance between two systems does not increase under parallel composition with a third system, and that the distance between two systems can be bounded from above and below by distances between abstractions of the two systems. These properties suggest that our simulation distances provide an appropriate basis for a quantitative theory of discrete systems. We also demonstrate how the robustness distance can be used to measure how many transmission errors are tolerated by error correcting codes.},
author = {Cerny, Pavol and Henzinger, Thomas A and Radhakrishna, Arjun},
journal = {Theoretical Computer Science},
number = {1},
pages = {21 -- 35},
publisher = {Elsevier},
title = {{Simulation distances}},
doi = {10.1016/j.tcs.2011.08.002},
volume = {413},
year = {2012},
}
@inproceedings{3250,
abstract = {The Learning Parity with Noise (LPN) problem has recently found many applications in cryptography as the hardness assumption underlying the constructions of "provably secure" cryptographic schemes like encryption or authentication protocols. Being provably secure means that the scheme comes with a proof showing that the existence of an efficient adversary against the scheme implies that the underlying hardness assumption is wrong. LPN based schemes are appealing for theoretical and practical reasons. On the theoretical side, LPN based schemes offer a very strong security guarantee. The LPN problem is equivalent to the problem of decoding random linear codes, a problem that has been extensively studied in the last half century. The fastest known algorithms run in exponential time and unlike most number-theoretic problems used in cryptography, the LPN problem does not succumb to known quantum algorithms. On the practical side, LPN based schemes are often extremely simple and efficient in terms of code-size as well as time and space requirements. This makes them prime candidates for light-weight devices like RFID tags, which are too weak to implement standard cryptographic primitives like the AES block-cipher. This talk will be a gentle introduction to provable security using simple LPN based schemes as examples. Starting from pseudorandom generators and symmetric key encryption, over secret-key authentication protocols, and, if time admits, touching on recent constructions of public-key identification, commitments and zero-knowledge proofs.},
author = {Pietrzak, Krzysztof Z},
location = {Špindlerův Mlýn, Czech Republic},
pages = {99 -- 114},
publisher = {Springer},
title = {{Cryptography from learning parity with noise}},
doi = {10.1007/978-3-642-27660-6_9},
volume = {7147},
year = {2012},
}
@inproceedings{3252,
abstract = {We study the automatic synthesis of fair non-repudiation protocols, a class of fair exchange protocols, used for digital contract signing. First, we show how to specify the objectives of the participating agents, the trusted third party (TTP) and the protocols as path formulas in Linear Temporal Logic (LTL) and prove that the satisfaction of the objectives of the agents and the TTP imply satisfaction of the protocol objectives. We then show that weak (co-operative) co-synthesis and classical (strictly competitive) co-synthesis fail in synthesizing these protocols, whereas assume-guarantee synthesis (AGS) succeeds. We demonstrate the success of assume-guarantee synthesis as follows: (a) any solution of assume-guarantee synthesis is attack-free; no subset of participants can violate the objectives of the other participants without violating their own objectives; (b) the Asokan-Shoup-Waidner (ASW) certified mail protocol that has known vulnerabilities is not a solution of AGS; and (c) the Kremer-Markowitch (KM) non-repudiation protocol is a solution of AGS. To our knowledge this is the first application of synthesis to fair non-repudiation protocols, and our results show how synthesis can generate correct protocols and automatically discover vulnerabilities. The solution to assume-guarantee synthesis can be computed efficiently as the secure equilibrium solution of three-player graph games. © 2012 Springer-Verlag.},
author = {Chatterjee, Krishnendu and Raman, Vishwanath},
location = {Philadelphia, PA, USA},
pages = {152 -- 168},
publisher = {Springer},
title = {{Synthesizing protocols for digital contract signing}},
doi = {10.1007/978-3-642-27940-9_11},
volume = {7148},
year = {2012},
}
@inproceedings{3253,
abstract = {We describe a framework for reasoning about programs with lists carrying integer numerical data. We use abstract domains to describe and manipulate complex constraints on configurations of these programs mixing constraints on the shape of the heap, sizes of the lists, on the multisets of data stored in these lists, and on the data at their different positions. Moreover, we provide powerful techniques for automatic validation of Hoare-triples and invariant checking, as well as for automatic synthesis of invariants and procedure summaries using modular inter-procedural analysis. The approach has been implemented in a tool called Celia and experimented successfully on a large benchmark of programs.},
author = {Bouajjani, Ahmed and Dragoi, Cezara and Enea, Constantin and Sighireanu, Mihaela},
location = {Philadelphia, PA, USA},
pages = {1 -- 22},
publisher = {Springer},
title = {{Abstract domains for automated reasoning about list manipulating programs with infinite data}},
doi = {10.1007/978-3-642-27940-9_1},
volume = {7148},
year = {2012},
}
@article{3254,
abstract = {The theory of graph games with ω-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the qualitative problem asks for the set of states from which a player can win with probability 1 (almost-sure winning); and the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We consider ω-regular winning conditions formalized as Müller winning conditions. We present optimal memory bounds for pure (deterministic) almost-sure winning and optimal winning strategies in stochastic graph games with Müller winning conditions. We also study the complexity of stochastic Müller games and show that both the qualitative and quantitative analysis problems are PSPACE-complete. Our results are relevant in synthesis of stochastic reactive processes.},
author = {Chatterjee, Krishnendu},
journal = {Information and Computation},
pages = {29 -- 48},
publisher = {Elsevier},
title = {{The complexity of stochastic Müller games}},
doi = {10.1016/j.ic.2011.11.004},
volume = {211},
year = {2012},
}
@inproceedings{3255,
abstract = {In this paper we survey results of two-player games on graphs and Markov decision processes with parity, mean-payoff and energy objectives, and the combination of mean-payoff and energy objectives with parity objectives. These problems have applications in verification and synthesis of reactive systems in resource-constrained environments.},
author = {Chatterjee, Krishnendu and Doyen, Laurent},
location = {Lednice, Czech Republic},
pages = {37 -- 46},
publisher = {Springer},
title = {{Games and Markov decision processes with mean payoff parity and energy parity objectives}},
doi = {10.1007/978-3-642-25929-6_3},
volume = {7119},
year = {2012},
}
@article{3256,
abstract = {We use a distortion to define the dual complex of a cubical subdivision of ℝ n as an n-dimensional subcomplex of the nerve of the set of n-cubes. Motivated by the topological analysis of high-dimensional digital image data, we consider such subdivisions defined by generalizations of quad- and oct-trees to n dimensions. Assuming the subdivision is balanced, we show that mapping each vertex to the center of the corresponding n-cube gives a geometric realization of the dual complex in ℝ n.},
author = {Edelsbrunner, Herbert and Kerber, Michael},
journal = {Discrete & Computational Geometry},
number = {2},
pages = {393 -- 414},
publisher = {Springer},
title = {{Dual complexes of cubical subdivisions of ℝn}},
doi = {10.1007/s00454-011-9382-4},
volume = {47},
year = {2012},
}
@article{3257,
abstract = {Consider a convex relaxation f̂ of a pseudo-Boolean function f. We say that the relaxation is totally half-integral if f̂(x) is a polyhedral function with half-integral extreme points x, and this property is preserved after adding an arbitrary combination of constraints of the form x i=x j, x i=1-x j, and x i=γ where γ∈{0,1,1/2} is a constant. A well-known example is the roof duality relaxation for quadratic pseudo-Boolean functions f. We argue that total half-integrality is a natural requirement for generalizations of roof duality to arbitrary pseudo-Boolean functions. Our contributions are as follows. First, we provide a complete characterization of totally half-integral relaxations f̂ by establishing a one-to-one correspondence with bisubmodular functions. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally half-integral relaxations and relaxations based on the roof duality. On the conceptual level, our results show that bisubmodular functions provide a natural generalization of the roof duality approach to higher-order terms. This can be viewed as a non-submodular analogue of the fact that submodular functions generalize the s-t minimum cut problem with non-negative weights to higher-order terms.},
author = {Kolmogorov, Vladimir},
journal = {Discrete Applied Mathematics},
number = {4-5},
pages = {416 -- 426},
publisher = {Elsevier},
title = {{Generalized roof duality and bisubmodular functions}},
doi = {10.1016/j.dam.2011.10.026},
volume = {160},
year = {2012},
}
@article{3258,
abstract = {CA3 pyramidal neurons are important for memory formation and pattern completion in the hippocampal network. It is generally thought that proximal synapses from the mossy fibers activate these neurons most efficiently, whereas distal inputs from the perforant path have a weaker modulatory influence. We used confocally targeted patch-clamp recording from dendrites and axons to map the activation of rat CA3 pyramidal neurons at the subcellular level. Our results reveal two distinct dendritic domains. In the proximal domain, action potentials initiated in the axon backpropagate actively with large amplitude and fast time course. In the distal domain, Na+ channel–mediated dendritic spikes are efficiently initiated by waveforms mimicking synaptic events. CA3 pyramidal neuron dendrites showed a high Na+-to-K+ conductance density ratio, providing ideal conditions for active backpropagation and dendritic spike initiation. Dendritic spikes may enhance the computational power of CA3 pyramidal neurons in the hippocampal network.},
author = {Kim, Sooyun and Guzmán, José and Hu, Hua and Jonas, Peter M},
journal = {Nature Neuroscience},
number = {4},
pages = {600 -- 606},
publisher = {Nature Publishing Group},
title = {{Active dendrites support efficient initiation of dendritic spikes in hippocampal CA3 pyramidal neurons}},
doi = {10.1038/nn.3060},
volume = {15},
year = {2012},
}
@article{3260,
abstract = {Many scenarios in the living world, where individual organisms compete for winning positions (or resources), have properties of auctions. Here we study the evolution of bids in biological auctions. For each auction, n individuals are drawn at random from a population of size N. Each individual makes a bid which entails a cost. The winner obtains a benefit of a certain value. Costs and benefits are translated into reproductive success (fitness). Therefore, successful bidding strategies spread in the population. We compare two types of auctions. In “biological all-pay auctions”, the costs are the bid for every participating individual. In “biological second price all-pay auctions”, the cost for everyone other than the winner is the bid, but the cost for the winner is the second highest bid. Second price all-pay auctions are generalizations of the “war of attrition” introduced by Maynard Smith. We study evolutionary dynamics in both types of auctions. We calculate pairwise invasion plots and evolutionarily stable distributions over the continuous strategy space. We find that the average bid in second price all-pay auctions is higher than in all-pay auctions, but the average cost for the winner is similar in both auctions. In both cases, the average bid is a declining function of the number of participants, n. The more individuals participate in an auction the smaller is the chance of winning, and thus expensive bids must be avoided.
},
author = {Chatterjee, Krishnendu and Reiter, Johannes and Nowak, Martin},
journal = {Theoretical Population Biology},
number = {1},
pages = {69 -- 80},
publisher = {Academic Press},
title = {{Evolutionary dynamics of biological auctions}},
doi = {10.1016/j.tpb.2011.11.003},
volume = {81},
year = {2012},
}
@article{3262,
abstract = {Living cells must control the reading out or "expression" of information encoded in their genomes, and this regulation often is mediated by transcription factors--proteins that bind to DNA and either enhance or repress the expression of nearby genes. But the expression of transcription factor proteins is itself regulated, and many transcription factors regulate their own expression in addition to responding to other input signals. Here we analyze the simplest of such self-regulatory circuits, asking how parameters can be chosen to optimize information transmission from inputs to outputs in the steady state. Some nonzero level of self-regulation is almost always optimal, with self-activation dominant when transcription factor concentrations are low and self-repression dominant when concentrations are high. In steady state the optimal self-activation is never strong enough to induce bistability, although there is a limit in which the optimal parameters are very close to the critical point.},
author = {Tkacik, Gasper and Walczak, Aleksandra and Bialek, William},
journal = { Physical Review E statistical nonlinear and soft matter physics },
number = {4},
publisher = {American Institute of Physics},
title = {{Optimizing information flow in small genetic networks. III. A self-interacting gene}},
doi = {10.1103/PhysRevE.85.041903},
volume = {85},
year = {2012},
}
@inproceedings{3265,
abstract = {We propose a mid-level statistical model for image segmentation that composes multiple figure-ground hypotheses (FG) obtained by applying constraints at different locations and scales, into larger interpretations (tilings) of the entire image. Inference is cast as optimization over sets of maximal cliques sampled from a graph connecting all non-overlapping figure-ground segment hypotheses. Potential functions over cliques combine unary, Gestalt-based figure qualities, and pairwise compatibilities among spatially neighboring segments, constrained by T-junctions and the boundary interface statistics of real scenes. Learning the model parameters is based on maximum likelihood, alternating between sampling image tilings and optimizing their potential function parameters. State of the art results are reported on the Berkeley and Stanford segmentation datasets, as well as VOC2009, where a 28% improvement was achieved.},
author = {Ion, Adrian and Carreira, Joao and Sminchisescu, Cristian},
location = {Barcelona, Spain},
publisher = {IEEE},
title = {{Image segmentation by figure-ground composition into maximal cliques}},
doi = {10.1109/ICCV.2011.6126486},
year = {2012},
}
@article{3274,
abstract = {A boundary element model of a tunnel running through horizontally layered soil with anisotropic material properties is presented. Since there is no analytical fundamental solution for wave propagation inside a layered orthotropic medium in 3D, the fundamental displacements and stresses have to be calculated numerically. In our model this is done in the Fourier domain with respect to space and time. The assumption of a straight tunnel with infinite extension in the x direction makes it possible to decouple the system for every wave number kx, leading to a 2.5D-problem, which is suited for parallel computation. The special form of the fundamental solution, resulting from our Fourier ansatz, and the fact, that the calculation of the boundary integral equation is performed in the Fourier domain, enhances the stability and efficiency of the numerical calculations.},
author = {Rieckh, Georg and Kreuzer, Wolfgang and Waubke, Holger and Balazs, Peter},
journal = { Engineering Analysis with Boundary Elements},
number = {6},
pages = {960 -- 967},
publisher = {Elsevier},
title = {{A 2.5D-Fourier-BEM model for vibrations in a tunnel running through layered anisotropic soil}},
doi = {10.1016/j.enganabound.2011.12.014},
volume = {36},
year = {2012},
}
@inbook{3277,
abstract = {The problem of the origin of metazoa is becoming more urgent in the context of astrobiology. By now it is clear that clues to the understanding of this crucial transition in the evolution of life can arise in a fourth pathway besides the three possibilities in the quest for simplicity outlined by Bonner in his classical book. In other words, solar system exploration seems to be one way in the long-term to elucidate the simplicity of evolutionary development. We place these ideas in the context of different inheritance systems, namely the genotypic and phenotypic replicators with limited or unlimited heredity, and ask which of these can support multicellular development, and to which degree of complexity. However, the quest for evidence on the evolution of biotas from planets around other stars does not seem to be feasible with present technology with direct visualization of living organisms on exoplanets. But this may be attempted on the Galilean moons of Jupiter where there is a possibility of detecting reliable biomarkers in the next decade with the Europa Jupiter System Mission, in view of recent progress by landing micropenetrators on planetary, or satellite surfaces. Mars is a second possibility in the inner Solar System, in spite of the multiple difficulties faced by the fleet of past, present and future missions. We discuss a series of preliminary ideas for elucidating the origin of metazoan analogues with available instrumentation in potential payloads of feasible space missions to the Galilean moons.},
author = {de Vladar, Harold and Chela Flores, Julian},
booktitle = {Life on Earth and other planetary bodies},
pages = {387 -- 405},
publisher = {Springer},
title = {{Can the evolution of multicellularity be anticipated in the exploration of the solar system?}},
doi = {10.1007/978-94-007-4966-5_22},
volume = {24},
year = {2012},
}
@inproceedings{3279,
abstract = {We show a hardness-preserving construction of a PRF from any length doubling PRG which improves upon known constructions whenever we can put a non-trivial upper bound q on the number of queries to the PRF. Our construction requires only O(logq) invocations to the underlying PRG with each query. In comparison, the number of invocations by the best previous hardness-preserving construction (GGM using Levin's trick) is logarithmic in the hardness of the PRG. For example, starting from an exponentially secure PRG {0,1} n → {0,1} 2n, we get a PRF which is exponentially secure if queried at most q = exp(√n)times and where each invocation of the PRF requires Θ(√n) queries to the underlying PRG. This is much less than the Θ(n) required by known constructions.
},
author = {Jain, Abhishek and Pietrzak, Krzysztof Z and Tentes, Aris},
location = {Taormina, Sicily, Italy},
pages = {369 -- 382},
publisher = {Springer},
title = {{Hardness preserving constructions of pseudorandom functions}},
doi = {10.1007/978-3-642-28914-9_21},
volume = {7194},
year = {2012},
}
@inproceedings{3280,
abstract = {The (decisional) learning with errors problem (LWE) asks to distinguish "noisy" inner products of a secret vector with random vectors from uniform. The learning parities with noise problem (LPN) is the special case where the elements of the vectors are bits. In recent years, the LWE and LPN problems have found many applications in cryptography. In this paper we introduce a (seemingly) much stronger adaptive assumption, called "subspace LWE" (SLWE), where the adversary can learn the inner product of the secret and random vectors after they were projected into an adaptively and adversarially chosen subspace. We prove that, surprisingly, the SLWE problem mapping into subspaces of dimension d is almost as hard as LWE using secrets of length d (the other direction is trivial.) This result immediately implies that several existing cryptosystems whose security is based on the hardness of the LWE/LPN problems are provably secure in a much stronger sense than anticipated. As an illustrative example we show that the standard way of using LPN for symmetric CPA secure encryption is even secure against a very powerful class of related key attacks. },
author = {Pietrzak, Krzysztof Z},
location = {Taormina, Sicily, Italy},
pages = {548 -- 563},
publisher = {Springer},
title = {{Subspace LWE}},
doi = {10.1007/978-3-642-28914-9_31},
volume = {7194},
year = {2012},
}
@inproceedings{3281,
abstract = {We consider the problem of amplifying the "lossiness" of functions. We say that an oracle circuit C*: {0,1} m → {0,1}* amplifies relative lossiness from ℓ/n to L/m if for every function f:{0,1} n → {0,1} n it holds that 1 If f is injective then so is C f. 2 If f has image size of at most 2 n-ℓ, then C f has image size at most 2 m-L. The question is whether such C* exists for L/m ≫ ℓ/n. This problem arises naturally in the context of cryptographic "lossy functions," where the relative lossiness is the key parameter. We show that for every circuit C* that makes at most t queries to f, the relative lossiness of C f is at most L/m ≤ ℓ/n + O(log t)/n. In particular, no black-box method making a polynomial t = poly(n) number of queries can amplify relative lossiness by more than an O(logn)/n additive term. We show that this is tight by giving a simple construction (cascading with some randomization) that achieves such amplification.},
author = {Pietrzak, Krzysztof Z and Rosen, Alon and Segev, Gil},
location = {Taormina, Sicily, Italy},
pages = {458 -- 475},
publisher = {Springer},
title = {{Lossy functions do not amplify well}},
doi = {10.1007/978-3-642-28914-9_26},
volume = {7194},
year = {2012},
}
@inproceedings{3282,
abstract = {Traditionally, symmetric-key message authentication codes (MACs) are easily built from pseudorandom functions (PRFs). In this work we propose a wide variety of other approaches to building efficient MACs, without going through a PRF first. In particular, unlike deterministic PRF-based MACs, where each message has a unique valid tag, we give a number of probabilistic MAC constructions from various other primitives/assumptions. Our main results are summarized as follows: We show several new probabilistic MAC constructions from a variety of general assumptions, including CCA-secure encryption, Hash Proof Systems and key-homomorphic weak PRFs. By instantiating these frameworks under concrete number theoretic assumptions, we get several schemes which are more efficient than just using a state-of-the-art PRF instantiation under the corresponding assumption. For probabilistic MACs, unlike deterministic ones, unforgeability against a chosen message attack (uf-cma ) alone does not imply security if the adversary can additionally make verification queries (uf-cmva ). We give an efficient generic transformation from any uf-cma secure MAC which is "message-hiding" into a uf-cmva secure MAC. This resolves the main open problem of Kiltz et al. from Eurocrypt'11; By using our transformation on their constructions, we get the first efficient MACs from the LPN assumption. While all our new MAC constructions immediately give efficient actively secure, two-round symmetric-key identification schemes, we also show a very simple, three-round actively secure identification protocol from any weak PRF. In particular, the resulting protocol is much more efficient than the trivial approach of building a regular PRF from a weak PRF. © 2012 International Association for Cryptologic Research.},
author = {Dodis, Yevgeniy and Pietrzak, Krzysztof Z and Kiltz, Eike and Wichs, Daniel},
location = {Cambridge, UK},
pages = {355 -- 374},
publisher = {Springer},
title = {{Message authentication, revisited}},
doi = {10.1007/978-3-642-29011-4_22},
volume = {7237},
year = {2012},
}
@inproceedings{3284,
abstract = {We study the complexity of valued constraint satisfaction problems (VCSP). A problem from VCSP is characterised by a constraint language, a fixed set of cost functions over a finite domain. An instance of the problem is specified by a sum of cost functions from the language and the goal is to minimise the sum. Under the unique games conjecture, the approximability of finite-valued VCSPs is well-understood, see Raghavendra [FOCS’08]. However, there is no characterisation of finite-valued VCSPs, let alone general-valued VCSPs, that can be solved exactly in polynomial time, thus giving insights from a combinatorial optimisation perspective.
We consider the case of languages containing all possible unary cost functions. In the case of languages consisting of only {0, ∞}-valued cost functions (i.e. relations), such languages have been called conservative and studied by Bulatov [LICS’03] and recently by Barto [LICS’11]. Since we study valued languages, we call a language conservative if it contains all finite-valued unary cost functions. The computational complexity of conservative valued languages has been studied by Cohen et al. [AIJ’06] for languages over Boolean domains, by Deineko et al. [JACM’08] for {0,1}-valued languages (a.k.a Max-CSP), and by Takhanov [STACS’10] for {0,∞}-valued languages containing all finite- valued unary cost functions (a.k.a. Min-Cost-Hom).
We prove a Schaefer-like dichotomy theorem for conservative valued languages: if all cost functions in the language satisfy a certain condition (specified by a complementary combination of STP and MJN multimorphisms), then any instance can be solved in polynomial time (via a new algorithm developed in this paper), otherwise the language is NP-hard. This is the first complete complexity classification of general-valued constraint languages over non-Boolean domains. It is a common phenomenon that complexity classifications of problems over non-Boolean domains is significantly harder than the Boolean case. The polynomial-time algorithm we present for the tractable cases is a generalisation of the submodular minimisation problem and a result of Cohen et al. [TCS’08].
Our results generalise previous results by Takhanov [STACS’10] and (a subset of results) by Cohen et al. [AIJ’06] and Deineko et al. [JACM’08]. Moreover, our results do not rely on any computer-assisted search as in Deineko et al. [JACM’08], and provide a powerful tool for proving hardness of finite-valued and general-valued languages.},
author = {Vladimir Kolmogorov and Živný, Stanislav},
pages = {750 -- 759},
publisher = {SIAM},
title = {{The complexity of conservative valued CSPs}},
year = {2012},
}
@article{3289,
abstract = {Viral manipulation of transduction pathways associated with key cellular functions such as survival, response to microbial infection, and cytoskeleton reorganization can provide the supportive milieu for a productive infection. Here, we demonstrate that vaccinia virus (VACV) infection leads to activation of the stress-activated protein kinase (SAPK)/extracellular signal-regulated kinase (ERK) 4/7 (MKK4/7)-c-Jun N-terminal protein kinase 1/2 (JNK1/2) pathway; further, the stimulation of this pathway requires postpenetration, prereplicative events in the viral replication cycle. Although the formation of intracellular mature virus (IMV) was not affected in MKK4/7- or JNK1/2-knockout (KO) cells, we did note an accentuated deregulation of microtubule and actin network organization in infected JNK1/2-KO cells. This was followed by deregulated viral trafficking to the periphery and enhanced enveloped particle release. Furthermore, VACV infection induced alterations in the cell contractility and morphology, and cell migration was reduced in the JNK-KO cells. In addition, phosphorylation of proteins implicated with early cell contractility and cell migration, such as microtubule-associated protein 1B and paxillin, respectively, was not detected in the VACV-infected KO cells. In sum, our findings uncover a regulatory role played by the MKK4/7-JNK1/2 pathway in cytoskeleton reorganization during VACV infection.
},
author = {Pereira, Anna and Leite, Flávia and Brasil, Bruno and Soares Martins, Jamaria and Torres, Alice and Pimenta, Paulo and Souto Padrón, Thais and Tranktman, Paula and Ferreira, Paulo and Kroon, Erna and Bonjardim, Cláudio},
journal = {Journal of Virology},
number = {1},
pages = {172 -- 184},
publisher = {ASM},
title = {{A vaccinia virus-driven interplay between the MKK4/7-JNK1/2 pathway and cytoskeleton reorganization}},
doi = {10.1128/JVI.05638-11},
volume = {86},
year = {2012},
}
@article{330,
abstract = {A procedure for the continuous production of Cu 2ZnSnS 4 (CZTS) nanoparticles with controlled composition is presented. CZTS nanoparticles were prepared through the reaction of the metals' amino complexes with elemental sulfur in a continuous-flow reactor at moderate temperatures (300-330 °C). High-resolution transmission electron microscopy and X-ray diffraction analysis showed the nanocrystals to have a crystallographic structure compatible with that of the kesterite. Chemical characterization of the materials showed the presence of the four elements in each individual nanocrystal. Composition control was achieved by adjusting the solution flow rate through the reactor and the proper choice of the nominal precursor concentration within the flowing solution. Single-particle analysis revealed a composition distribution within each sample, which was optimized at the highest synthesis temperatures used. },
author = {Shavel, Alexey and Cadavid, Doris and Ibáñez, Maria and Carrete, Alex and Cabot, Andreu},
journal = {Journal of the American Chemical Society},
number = {3},
pages = {1438 -- 1441},
publisher = {ACS},
title = {{Continuous production of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor}},
doi = {10.1021/ja209688a},
volume = {134},
year = {2012},
}
@article{3310,
abstract = {The theory of persistent homology opens up the possibility to reason about topological features of a space or a function quantitatively and in combinatorial terms. We refer to this new angle at a classical subject within algebraic topology as a point calculus, which we present for the family of interlevel sets of a real-valued function. Our account of the subject is expository, devoid of proofs, and written for non-experts in algebraic topology.},
author = {Bendich, Paul and Cabello, Sergio and Edelsbrunner, Herbert},
journal = {Pattern Recognition Letters},
number = {11},
pages = {1436 -- 1444},
publisher = {Elsevier},
title = {{A point calculus for interlevel set homology}},
doi = {10.1016/j.patrec.2011.10.007},
volume = {33},
year = {2012},
}
@article{3314,
abstract = {We introduce two-level discounted and mean-payoff games played by two players on a perfect-information stochastic game graph. The upper level game is a discounted or mean-payoff game and the lower level game is a (undiscounted) reachability game. Two-level games model hierarchical and sequential decision making under uncertainty across different time scales. For both discounted and mean-payoff two-level games, we show the existence of pure memoryless optimal strategies for both players and an ordered field property. We show that if there is only one player (Markov decision processes), then the values can be computed in polynomial time. It follows that whether the value of a player is equal to a given rational constant in two-level discounted or mean-payoff games can be decided in NP ∩ coNP. We also give an alternate strategy improvement algorithm to compute the value. © 2012 World Scientific Publishing Company.},
author = {Chatterjee, Krishnendu and Majumdar, Ritankar},
journal = {International Journal of Foundations of Computer Science},
number = {3},
pages = {609 -- 625},
publisher = {World Scientific Publishing},
title = {{Discounting and averaging in games across time scales}},
doi = {10.1142/S0129054112400308},
volume = {23},
year = {2012},
}
@article{3317,
abstract = {The physical distance between presynaptic Ca2+ channels and the Ca2+ sensors that trigger exocytosis of neurotransmitter-containing vesicles is a key determinant of the signalling properties of synapses in the nervous system. Recent functional analysis indicates that in some fast central synapses, transmitter release is triggered by a small number of Ca2+ channels that are coupled to Ca2+ sensors at the nanometre scale. Molecular analysis suggests that this tight coupling is generated by protein–protein interactions involving Ca2+ channels, Ca2+ sensors and various other synaptic proteins. Nanodomain coupling has several functional advantages, as it increases the efficacy, speed and energy efficiency of synaptic transmission.},
author = {Eggermann, Emmanuel and Bucurenciu, Iancu and Goswami, Sarit and Jonas, Peter M},
journal = {Nature Reviews Neuroscience},
number = {1},
pages = {7 -- 21},
publisher = {Nature Publishing Group},
title = {{Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses}},
doi = {10.1038/nrn3125},
volume = {13},
year = {2012},
}
@article{3331,
abstract = {Computing the topology of an algebraic plane curve C means computing a combinatorial graph that is isotopic to C and thus represents its topology in R2. We prove that, for a polynomial of degree n with integer coefficients bounded by 2ρ, the topology of the induced curve can be computed with bit operations ( indicates that we omit logarithmic factors). Our analysis improves the previous best known complexity bounds by a factor of n2. The improvement is based on new techniques to compute and refine isolating intervals for the real roots of polynomials, and on the consequent amortized analysis of the critical fibers of the algebraic curve.},
author = {Kerber, Michael and Sagraloff, Michael},
journal = { Journal of Symbolic Computation},
number = {3},
pages = {239 -- 258},
publisher = {Elsevier},
title = {{A worst case bound for topology computation of algebraic curves}},
doi = {10.1016/j.jsc.2011.11.001},
volume = {47},
year = {2012},
}