@inproceedings{497, abstract = {One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n 3·m) time as compared to the previous known O(n 6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n·m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm. © Krishnendu Chatterjee, Siddhesh Chaubal, and Pritish Kamath.}, author = {Chatterjee, Krishnendu and Chaubal, Siddhesh and Kamath, Pritish}, location = {Fontainebleau, France}, pages = {167 -- 182}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Faster algorithms for alternating refinement relations}}, doi = {10.4230/LIPIcs.CSL.2012.167}, volume = {16}, year = {2012}, } @article{498, abstract = {Understanding patterns and correlates of local adaptation in heterogeneous landscapes can provide important information in the selection of appropriate seed sources for restoration. We assessed the extent of local adaptation of fitness components in 12 population pairs of the perennial herb Rutidosis leptorrhynchoides (Asteraceae) and examined whether spatial scale (0.7-600 km), environmental distance, quantitative (QST) and neutral (FST) genetic differentiation, and size of the local and foreign populations could predict patterns of adaptive differentiation. Local adaptation varied among populations and fitness components. Including all population pairs, local adaptation was observed for seedling survival, but not for biomass, while foreign genotype advantage was observed for reproduction (number of inflorescences). Among population pairs, local adaptation increased with QST and local population size for biomass. QST was associated with environmental distance, suggesting ecological selection for phenotypic divergence. However, low FST and variation in population structure in small populations demonstrates the interaction of gene flow and drift in constraining local adaptation in R. leptorrhynchoides. Our study indicates that for species in heterogeneous landscapes, collecting seed from large populations from similar environments to candidate sites is likely to provide the most appropriate seed sources for restoration.}, author = {Pickup, Melinda and Field, David and Rowell, David and Young, Andrew}, journal = {Evolutionary Applications}, number = {8}, pages = {913 -- 924}, publisher = {Wiley-Blackwell}, title = {{Predicting local adaptation in fragmented plant populations: Implications for restoration genetics}}, doi = {10.1111/j.1752-4571.2012.00284.x}, volume = {5}, year = {2012}, } @article{506, author = {Sixt, Michael K}, journal = {Journal of Cell Biology}, number = {3}, pages = {347 -- 349}, publisher = {Rockefeller University Press}, title = {{Cell migration: Fibroblasts find a new way to get ahead}}, doi = {10.1083/jcb.201204039}, volume = {197}, year = {2012}, } @misc{5377, 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 can 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, namely, mean-payoff objectives. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation, but 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 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 = {2664-1690}, pages = {33}, publisher = {IST Austria}, title = {{Mean-payoff pushdown games}}, doi = {10.15479/AT:IST-2012-0002}, year = {2012}, } @misc{5378, abstract = {One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n3 · m) time as compared to the previous known O(n6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n · m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm.}, author = {Chatterjee, Krishnendu and Chaubal, Siddhesh and Kamath, Pritish}, issn = {2664-1690}, pages = {21}, publisher = {IST Austria}, title = {{Faster algorithms for alternating refinement relations}}, doi = {10.15479/AT:IST-2012-0001}, year = {2012}, } @article{2073, abstract = {Background: Drosophila albomicans is a unique model organism for studying both sex chromosome and B chromosome evolution. A pair of its autosomes comprising roughly 40% of the whole genome has fused to the ancient X and Y chromosomes only about 0.12 million years ago, thereby creating the youngest and most gene-rich neo-sex system reported to date. This species also possesses recently derived B chromosomes that show non-Mendelian inheritance and significantly influence fertility.Methods: We sequenced male flies with B chromosomes at 124.5-fold genome coverage using next-generation sequencing. To characterize neo-Y specific changes and B chromosome sequences, we also sequenced inbred female flies derived from the same strain but without B's at 28.5-fold.Results: We assembled a female genome and placed 53% of the sequence and 85% of the annotated proteins into specific chromosomes, by comparison with the 12 Drosophila genomes. Despite its very recent origin, the non-recombining neo-Y chromosome shows various signs of degeneration, including a significant enrichment of non-functional genes compared to the neo-X, and an excess of tandem duplications relative to other chromosomes. We also characterized a B-chromosome linked scaffold that contains an actively transcribed unit and shows sequence similarity to the subcentromeric regions of both the ancient X and the neo-X chromosome.Conclusions: Our results provide novel insights into the very early stages of sex chromosome evolution and B chromosome origination, and suggest an unprecedented connection between the births of these two systems in D. albomicans.}, author = {Zhou, Qi and Zhu, Hongmei and Huang, Quanfei and Zhao, Li and Zhang, Guo J and Roy, Scott W and Beatriz Vicoso and Xuan, Zhaolin and Ruan, Jue and Zhang, Yue and Zhao, Ruoping and Ye, Chen and Zhang, Xiuqing and Wang, Jùn and Wang, Wen and Bachtrog, Doris}, journal = {BMC Genomics}, number = {1}, publisher = {BioMed Central}, title = {{Deciphering neo-sex and B chromosome evolution by the draft genome of Drosophila albomicans}}, doi = {10.1186/1471-2164-13-109}, volume = {13}, year = {2012}, } @article{2079, abstract = {We introduce an algorithm and representation for fabricating 3D shape abstractions using mutually intersecting planar cut-outs. The planes have prefabricated slits at their intersections and are assembled by sliding them together. Often such abstractions are used as a sculptural art form or in architecture and are colloquially called ‘cardboard sculptures’. Based on an analysis of construction rules, we propose an extended binary space partitioning tree as an efficient representation of such cardboard models which allows us to quickly evaluate the feasibility of newly added planar elements. The complexity of insertion order quickly increases with the number of planar elements and manual analysis becomes intractable. We provide tools for generating cardboard sculptures with guaranteed constructibility. In combination with a simple optimization and sampling strategy for new elements, planar shape abstraction models can be designed by iteratively adding elements. As an output, we obtain a fabrication plan that can be printed or sent to a laser cutter. We demonstrate the complete process by designing and fabricating cardboard models of various well-known 3D shapes.}, author = {Hildebrand, Kristian and Bernd Bickel and Alexa, Marc}, journal = {Computer Graphics Forum}, number = {2pt3}, pages = {583 -- 592}, publisher = {Wiley-Blackwell}, title = {{crdbrd: Shape fabrication by sliding planar slices}}, doi = {10.1111/j.1467-8659.2012.03037.x}, volume = {31}, year = {2012}, } @article{2101, abstract = {Articulated deformable characters are widespread in computer animation. Unfortunately, we lack methods for their automatic fabrication using modern additive manufacturing (AM) technologies. We propose a method that takes a skinned mesh as input, then estimates a fabricatable single-material model that approximates the 3D kinematics of the corresponding virtual articulated character in a piecewise linear manner. We first extract a set of potential joint locations. From this set, together with optional, user-specified range constraints, we then estimate mechanical friction joints that satisfy inter-joint non-penetration and other fabrication constraints. To avoid brittle joint designs, we place joint centers on an approximate medial axis representation of the input geometry, and maximize each joint's minimal cross-sectional area. We provide several demonstrations, manufactured as single, assembled pieces using 3D printers. }, author = {Bac̈her, Moritz and Bernd Bickel and James, Doug L and Pfister, Hanspeter}, journal = {ACM Transactions on Graphics}, number = {4}, publisher = {ACM}, title = {{Fabricating articulated characters from skinned meshes}}, doi = {10.1145/2185520.2185543}, volume = {31}, year = {2012}, } @article{2102, abstract = {We propose a complete process for designing, simulating, and fabricating synthetic skin for an animatronics character that mimics the face of a given subject and its expressions. The process starts with measuring the elastic properties of a material used to manufacture synthetic soft tissue. Given these measurements we use physicsbased simulation to predict the behavior of a face when it is driven by the underlying robotic actuation. Next, we capture 3D facial expressions for a given target subject. As the key component of our process, we present a novel optimization scheme that determines the shape of the synthetic skin as well as the actuation parameters that provide the best match to the target expressions. We demonstrate this computational skin design by physically cloning a real human face onto an animatronics figure. }, author = {Bernd Bickel and Kaufmann, Peter and Skouras, Mélina and Thomaszewski, Bernhard and Bradley, Derek J and Beeler, Thabo and Jackson, Philip V and Marschner, Steve and Matusik, Wojciech and Groß, Markus S}, journal = {ACM Transactions on Graphics}, number = {4}, publisher = {ACM}, title = {{Physical face cloning}}, doi = {10.1145/2185520.2185614}, volume = {31}, year = {2012}, } @article{2103, abstract = {Although facial hair plays an important role in individual expression, facial-hair reconstruction is not addressed by current facecapture systems. Our research addresses this limitation with an algorithm that treats hair and skin surface capture together in a coupled fashion so that a high-quality representation of hair fibers as well as the underlying skin surface can be reconstructed. We propose a passive, camera-based system that is robust against arbitrary motion since all data is acquired within the time period of a single exposure. Our reconstruction algorithm detects and traces hairs in the captured images and reconstructs them in 3D using a multiview stereo approach. Our coupled skin-reconstruction algorithm uses information about the detected hairs to deliver a skin surface that lies underneath all hairs irrespective of occlusions. In dense regions like eyebrows, we employ a hair-synthesis method to create hair fibers that plausibly match the image data. We demonstrate our scanning system on a number of individuals and show that it can successfully reconstruct a variety of facial-hair styles together with the underlying skin surface.}, author = {Beeler, Thabo and Bernd Bickel and Noris, Gioacchino and Beardsley, Paul A and Marschner, Steve and Sumner, Robert W and Groß, Markus S}, journal = {ACM Transactions on Graphics}, number = {4}, publisher = {ACM}, title = {{Coupled 3D reconstruction of sparse facial hair and skin}}, doi = {10.1145/2185520.2185613}, volume = {31}, year = {2012}, } @inproceedings{2104, abstract = {In recent years, various methods have been introduced to exploit pre-recorded data to improve the performance and/or realism of dynamic deformations, but their differences and similarities have not been adequately analyzed or discussed. So far, the proposed methods have been explored mainly in the research context. They have not been adopted by the computer graphics industry. This course bridges the gap between research labs and industry to present a unifying theory and understanding of data-driven methods for dynamic deformations that may inspire development of novel solutions. It focuses on application of data-driven methods to three areas of computer animation: dynamic deformation of faces, soft volumetric tissue, and cloth. And it describes how to approach these challenges in a data-driven manner, classifies the various methods, and demonstrates how data-driven methods can work in other settings. }, author = {Otaduy, Miguel A and Bernd Bickel and Bradley, Derek J and Wang, Huamin}, publisher = {ACM}, title = {{Data-driven simulation methods in computer graphics: Cloth, tissue and faces}}, doi = {10.1145/2343483.2343495}, year = {2012}, } @inproceedings{2105, author = {Skouras, Mélina and Thomaszewski, Bernhard and Bernd Bickel and Groß, Markus S}, number = {2}, pages = {835 -- 844}, publisher = {Wiley-Blackwell}, title = {{Computational design of rubber balloons}}, doi = {10.1111/j.1467-8659.2012.03064.x}, volume = {31}, year = {2012}, } @inproceedings{2106, abstract = {Progress in cloth simulation for computer animation and apparel design has led to a multitude of deformation models, each with its own way of relating geometry, deformation, and forces. As simulators improve, differences between these models become more important, but it is difficult to choose a model and a set of parameters to match a given real material simply by looking at simulation results. This paper provides measurement and fitting methods that allow nonlinear models to be fit to the observed deformation of a particular cloth sample. Unlike standard textile testing, our system measures complex 3D deformations of a sheet of cloth, not just one-dimensional force-displacement curves, so it works under a wider range of deformation conditions. The fitted models are then evaluated by comparison to measured deformations with motions very different from those used for fitting.}, author = {Miguel, Eder and Bradley, Derek J and Thomaszewski, Bernhard and Bernd Bickel and Matusik, Wojciech and Otaduy, Miguel A and Marschner, Steve}, number = {2}, pages = {519 -- 528}, publisher = {Wiley-Blackwell}, title = {{Data-driven estimation of cloth simulation models}}, doi = {10.1111/j.1467-8659.2012.03031.x}, volume = {31}, year = {2012}, } @article{2125, abstract = {We consider a class of stochastic PDEs of Burgers type in spatial dimension 1, driven by space–time white noise. Even though it is well known that these equations are well posed, it turns out that if one performs a spatial discretization of the nonlinearity in the “wrong” way, then the sequence of approximate equations does converge to a limit, but this limit exhibits an additional correction term. This correction term is proportional to the local quadratic cross-variation (in space) of the gradient of the conserved quantity with the solution itself. This can be understood as a consequence of the fact that for any fixed time, the law of the solution is locally equivalent to Wiener measure, where space plays the role of time. In this sense, the correction term is similar to the usual Itô–Stratonovich correction term that arises when one considers different temporal discretizations of stochastic ODEs.}, author = {Hairer, Martin M and Jan Maas}, journal = {Annals of Probability}, number = {4}, pages = {1675 -- 1714}, publisher = {Institute of Mathematical Statistics}, title = {{A spatial version of the Itô-Stratonovich correction}}, doi = {10.1214/11-AOP662}, volume = {40}, year = {2012}, } @article{2127, abstract = {We study a new notion of Ricci curvature that applies to Markov chains on discrete spaces. This notion relies on geodesic convexity of the entropy and is analogous to the one introduced by Lott, Sturm, and Villani for geodesic measure spaces. In order to apply to the discrete setting, the role of the Wasserstein metric is taken over by a different metric, having the property that continuous time Markov chains are gradient flows of the entropy. Using this notion of Ricci curvature we prove discrete analogues of fundamental results by Bakry–Émery and Otto–Villani. Further, we show that Ricci curvature bounds are preserved under tensorisation. As a special case we obtain the sharp Ricci curvature lower bound for the discrete hypercube.}, author = {Erbar, Matthias and Jan Maas}, journal = {Archive for Rational Mechanics and Analysis}, number = {3}, pages = {997 -- 1038}, publisher = {Springer}, title = {{Ricci curvature of finite Markov chains via convexity of the entropy}}, doi = {10.1007/s00205-012-0554-z}, volume = {206}, year = {2012}, } @article{2128, abstract = {We introduce a technique for handling Whitney decompositions in Gaussian harmonic analysis and apply it to the study of Gaussian analogues of the classical tent spaces T 1,q of Coifman–Meyer–Stein.}, author = {Jan Maas and van Neerven, Jan M and Portal, Pierre}, journal = {Arkiv för Matematik}, number = {2}, pages = {379 -- 395}, publisher = {Springer}, title = {{Whitney coverings and the tent spaces T 1,q (γ) for the Gaussian measure}}, doi = {10.1007/s11512-010-0143-z}, volume = {50}, year = {2012}, } @article{2201, abstract = {We study the growth dynamics of ordered structures of strongly interacting polar molecules in optical lattices. Using a dipole blockade of microwave excitations, we map the system onto an interacting spin-1/2 model possessing ground states with crystalline order, and describe a way to prepare these states by nonadiabatically driving the transitions between molecular rotational levels. The proposed technique bypasses the need to cross a phase transition and allows for the creation of ordered domains of considerably larger size compared to approaches relying on adiabatic preparation.}, author = {Lemeshko, Mikhail and Krems, Roman and Weimer, Hendrik}, journal = {Physical Review Letters}, number = {3}, publisher = {American Physical Society}, title = {{Nonadiabatic preparation of spin crystals with ultracold polar molecules}}, doi = {10.1103/PhysRevLett.109.035301}, volume = {109}, year = {2012}, } @article{2202, abstract = {We propose a method for sensitive parallel detection of low-frequency electromagnetic fields based on the fine structure interactions in paramagnetic polar molecules. Compared to the recently implemented scheme employing ultracold 87Rb atoms by Böhi, the technique based on molecules offers a 100-fold higher sensitivity, the possibility to measure both the electric and magnetic field components, and a probe of a wide range of frequencies from the dc limit to the THz regime.}, author = {Alyabyshev, Sergey V and Mikhail Lemeshko and Krems, Roman V}, journal = {Physical Review A - Atomic, Molecular, and Optical Physics}, number = {1}, publisher = {American Physical Society}, title = {{Sensitive imaging of electromagnetic fields with paramagnetic polar molecules}}, doi = {10.1103/PhysRevA.86.013409}, volume = {86}, year = {2012}, } @article{2203, abstract = {We show that the electric dipole-dipole interaction between a pair of polar molecules undergoes an all-out transformation when superimposed by a far-off-resonant optical field. The combined interaction potential becomes tunable by variation of wavelength, polarisation and intensity of the optical field and its dependence on the intermolecular separation exhibits a crossover from an inverse-power to an oscillating behaviour. The ability thereby offered to control molecular interactions opens up avenues toward the creation and manipulation of novel phases of ultracold polar gases among whose characteristics is a long-range entanglement of the dipoles' mutual orientation. We devised an accurate analytic model of such optical-field-dressed dipole-dipole interaction potentials, which enables a straightforward access to the optical-field parameters required for the design of intermolecular interactions in the laboratory.}, author = {Mikhail Lemeshko and Friedrich, Břetislav}, journal = {Molecular Physics}, number = {15-16}, pages = {1873 -- 1881}, publisher = {Taylor & Francis}, title = {{Interaction between polar molecules subject to a far-off-resonant optical field: Entangled dipoles up- or down-holding each other}}, doi = {10.1080/00268976.2012.689868}, volume = {110}, year = {2012}, } @article{2262, abstract = {Mosaic Analysis with Double Markers (MADM) is a method for generating genetically mosaic mice, in which sibling mutant and wild-type cells are labeled with different fluorescent markers. It is a powerful tool that enables analysis of gene function at the single cell level in vivo. It requires transgenic cassettes to be located between the centromere and the mutation in the gene of interest on the same chromosome. Here we compare procedures for introduction of MADM cassettes into new loci in the mouse genome, and describe new approaches for expanding the utility of MADM. We show that: 1) Targeted homologous recombination outperforms random transgenesis in generation of reliably expressed MADM cassettes, 2) MADM cassettes in new genomic loci need to be validated for biallelic and ubiquitous expression, 3) Recombination between MADM cassettes on different chromosomes can be used to study reciprocal chromosomal deletions/duplications, and 4) MADM can be modified to permit transgene expression by combining it with a binary expression system. The advances described in this study expand current, and enable new and more versatile applications of MADM.}, author = {Tasic, Bosiljka and Miyamichi, Kazunari and Simon Hippenmeyer and Dani, Vardhan S. and Zeng, H. and Joo, William and Zong, Hui and Chen-Tsai, Yanru and Luo, Liqun}, journal = {PLoS One}, number = {3}, publisher = {Public Library of Science}, title = {{Extensions of MADM (Mosaic Analysis with Double Markers) in Mice }}, doi = {10.1371/journal.pone.0033332}, volume = {7}, year = {2012}, }