@inproceedings{1729, abstract = {We present a computer-aided programming approach to concurrency. The approach allows programmers to program assuming a friendly, non-preemptive scheduler, and our synthesis procedure inserts synchronization to ensure that the final program works even with a preemptive scheduler. The correctness specification is implicit, inferred from the non-preemptive behavior. Let us consider sequences of calls that the program makes to an external interface. The specification requires that any such sequence produced under a preemptive scheduler should be included in the set of such sequences produced under a non-preemptive scheduler. The solution is based on a finitary abstraction, an algorithm for bounded language inclusion modulo an independence relation, and rules for inserting synchronization. We apply the approach to device-driver programming, where the driver threads call the software interface of the device and the API provided by the operating system. Our experiments demonstrate that our synthesis method is precise and efficient, and, since it does not require explicit specifications, is more practical than the conventional approach based on user-provided assertions.}, author = {Cerny, Pavol and Clarke, Edmund and Henzinger, Thomas A and Radhakrishna, Arjun and Ryzhyk, Leonid and Samanta, Roopsha and Tarrach, Thorsten}, location = {San Francisco, CA, United States}, pages = {180 -- 197}, publisher = {Springer}, title = {{From non-preemptive to preemptive scheduling using synchronization synthesis}}, doi = {10.1007/978-3-319-21668-3_11}, volume = {9207}, year = {2015}, } @article{1730, abstract = {How much cutting is needed to simplify the topology of a surface? We provide bounds for several instances of this question, for the minimum length of topologically non-trivial closed curves, pants decompositions, and cut graphs with a given combinatorial map in triangulated combinatorial surfaces (or their dual cross-metric counterpart). Our work builds upon Riemannian systolic inequalities, which bound the minimum length of non-trivial closed curves in terms of the genus and the area of the surface. We first describe a systematic way to translate Riemannian systolic inequalities to a discrete setting, and vice-versa. This implies a conjecture by Przytycka and Przytycki (Graph structure theory. Contemporary Mathematics, vol. 147, 1993), a number of new systolic inequalities in the discrete setting, and the fact that a theorem of Hutchinson on the edge-width of triangulated surfaces and Gromov’s systolic inequality for surfaces are essentially equivalent. We also discuss how these proofs generalize to higher dimensions. Then we focus on topological decompositions of surfaces. Relying on ideas of Buser, we prove the existence of pants decompositions of length O(g^(3/2)n^(1/2)) for any triangulated combinatorial surface of genus g with n triangles, and describe an O(gn)-time algorithm to compute such a decomposition. Finally, we consider the problem of embedding a cut graph (or more generally a cellular graph) with a given combinatorial map on a given surface. Using random triangulations, we prove (essentially) that, for any choice of a combinatorial map, there are some surfaces on which any cellular embedding with that combinatorial map has length superlinear in the number of triangles of the triangulated combinatorial surface. There is also a similar result for graphs embedded on polyhedral triangulations.}, author = {Colin De Verdière, Éric and Hubard, Alfredo and De Mesmay, Arnaud N}, journal = {Discrete & Computational Geometry}, number = {3}, pages = {587 -- 620}, publisher = {Springer}, title = {{Discrete systolic inequalities and decompositions of triangulated surfaces}}, doi = {10.1007/s00454-015-9679-9}, volume = {53}, year = {2015}, } @article{1731, abstract = {We consider two-player zero-sum games on graphs. These games can be classified on the basis of the information of the players and on the mode of interaction between them. On the basis of information the classification is as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided complete-observation (one player has complete observation); and (c) complete-observation (both players have complete view of the game). On the basis of mode of interaction we have the following classification: (a) concurrent (both players interact simultaneously); and (b) turn-based (both players interact in turn). The two sources of randomness in these games are randomness in transition function and randomness in strategies. In general, randomized strategies are more powerful than deterministic strategies, and randomness in transitions gives more general classes of games. In this work we present a complete characterization for the classes of games where randomness is not helpful in: (a) the transition function probabilistic transition can be simulated by deterministic transition); and (b) strategies (pure strategies are as powerful as randomized strategies). As consequence of our characterization we obtain new undecidability results for these games. }, author = {Chatterjee, Krishnendu and Doyen, Laurent and Gimbert, Hugo and Henzinger, Thomas A}, journal = {Information and Computation}, number = {12}, pages = {3 -- 16}, publisher = {Elsevier}, title = {{Randomness for free}}, doi = {10.1016/j.ic.2015.06.003}, volume = {245}, year = {2015}, } @inproceedings{1732, abstract = {We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty.}, author = {Chatterjee, Krishnendu and Chmelik, Martin and Gupta, Raghav and Kanodia, Ayush}, location = {Seattle, WA, United States}, pages = {325 -- 330}, publisher = {IEEE}, title = {{Qualitative analysis of POMDPs with temporal logic specifications for robotics applications}}, doi = {10.1109/ICRA.2015.7139019}, year = {2015}, } @article{1734, abstract = {Facial appearance capture is now firmly established within academic research and used extensively across various application domains, perhaps most prominently in the entertainment industry through the design of virtual characters in video games and films. While significant progress has occurred over the last two decades, no single survey currently exists that discusses the similarities, differences, and practical considerations of the available appearance capture techniques as applied to human faces. A central difficulty of facial appearance capture is the way light interacts with skin-which has a complex multi-layered structure-and the interactions that occur below the skin surface can, by definition, only be observed indirectly. In this report, we distinguish between two broad strategies for dealing with this complexity. "Image-based methods" try to exhaustively capture the exact face appearance under different lighting and viewing conditions, and then render the face through weighted image combinations. "Parametric methods" instead fit the captured reflectance data to some parametric appearance model used during rendering, allowing for a more lightweight and flexible representation but at the cost of potentially increased rendering complexity or inexact reproduction. The goal of this report is to provide an overview that can guide practitioners and researchers in assessing the tradeoffs between current approaches and identifying directions for future advances in facial appearance capture.}, author = {Klehm, Oliver and Rousselle, Fabrice and Papas, Marios and Bradley, Derek and Hery, Christophe and Bickel, Bernd and Jarosz, Wojciech and Beeler, Thabo}, journal = {Computer Graphics Forum}, number = {2}, pages = {709 -- 733}, publisher = {Wiley-Blackwell}, title = {{Recent advances in facial appearance capture}}, doi = {10.1111/cgf.12594}, volume = {34}, year = {2015}, } @article{1735, abstract = {This work presents a method for efficiently simplifying the pressure projection step in a liquid simulation. We first devise a straightforward dimension reduction technique that dramatically reduces the cost of solving the pressure projection. Next, we introduce a novel change of basis that satisfies free-surface boundary conditions exactly, regardless of the accuracy of the pressure solve. When combined, these ideas greatly reduce the computational complexity of the pressure solve without compromising free surface boundary conditions at the highest level of detail. Our techniques are easy to parallelize, and they effectively eliminate the computational bottleneck for large liquid simulations.}, author = {Ando, Ryoichi and Thürey, Nils and Wojtan, Christopher J}, journal = {Computer Graphics Forum}, number = {2}, pages = {473 -- 480}, publisher = {Wiley}, title = {{A dimension-reduced pressure solver for liquid simulations}}, doi = {10.1111/cgf.12576}, volume = {34}, year = {2015}, } @article{1788, abstract = {We fabricate and characterize a microscale silicon opto-electromechanical system whose mechanical motion is coupled capacitively to an electrical circuit and optically via radiation pressure to a photonic crystal cavity. To achieve large electromechanical interaction strength, we implement an inverse shadow mask fabrication scheme which obtains capacitor gaps as small as 30 nm while maintaining a silicon surface quality necessary for minimizing optical loss. Using the sensitive optical read-out of the photonic crystal cavity, we characterize the linear and nonlinear capacitive coupling to the fundamental ωm=2π = 63 MHz in-plane flexural motion of the structure, showing that the large electromechanical coupling in such devices may be suitable for realizing efficient microwave-to-optical signal conversion.}, author = {Pitanti, Alessandro and Johannes Fink and Safavi-Naeini, Amir H and Hill, Jeff T and Lei, Chan U and Tredicucci, Alessandro and Painter, Oskar J}, journal = {Optics Express}, number = {3}, pages = {3196 -- 3208}, publisher = {Optical Society of America}, title = {{Strong opto-electro-mechanical coupling in a silicon photonic crystal cavity}}, doi = {10.1364/OE.23.003196}, volume = {23}, year = {2015}, } @article{1789, abstract = {Intellectual disability (ID) has an estimated prevalence of 2-3%. Due to its extreme heterogeneity, the genetic basis of ID remains elusive in many cases. Recently, whole exome sequencing (WES) studies revealed that a large proportion of sporadic cases are caused by de novo gene variants. To identify further genes involved in ID, we performed WES in 250 patients with unexplained ID and their unaffected parents and included exomes of 51 previously sequenced child-parents trios in the analysis. Exome analysis revealed de novo intragenic variants in SET domain-containing 5 (SETD5) in two patients. One patient carried a nonsense variant, and the other an 81 bp deletion located across a splice-donor site. Chromosomal microarray diagnostics further identified four de novo non-recurrent microdeletions encompassing SETD5. CRISPR/Cas9 mutation modelling of the two intragenic variants demonstrated nonsense-mediated decay of the resulting transcripts, pointing to a loss-of-function (LoF) and haploinsufficiency as the common disease-causing mechanism of intragenic SETD5 sequence variants and SETD5-containing microdeletions. In silico domain prediction of SETD5, a predicted SET domain-containing histone methyltransferase (HMT), substantiated the presence of a SET domain and identified a novel putative PHD domain, strengthening a functional link to well-known histone-modifying ID genes. All six patients presented with ID and certain facial dysmorphisms, suggesting that SETD5 sequence variants contribute substantially to the microdeletion 3p25.3 phenotype. The present report of two SETD5 LoF variants in 301 patients demonstrates a prevalence of 0.7% and thus SETD5 variants as a relatively frequent cause of ID.}, author = {Kuechler, Alma and Zink, Alexander and Wieland, Thomas and Lüdecke, Hermann and Cremer, Kirsten and Salviati, Leonardo and Magini, Pamela and Najafi, Kimia and Zweier, Christiane and Czeschik, Johanna and Aretz, Stefan and Endele, Sabine and Tamburrino, Federica and Pinato, Claudia and Clementi, Maurizio and Gundlach, Jasmin and Maylahn, Carina and Mazzanti, Laura and Wohlleber, Eva and Schwarzmayr, Thomas and Kariminejad, Roxana and Schlessinger, Avner and Wieczorek, Dagmar and Strom, Tim and Novarino, Gaia and Engels, Hartmut}, journal = {European Journal of Human Genetics}, number = {6}, pages = {753 -- 760}, publisher = {Nature Publishing Group}, title = {{Loss-of-function variants of SETD5 cause intellectual disability and the core phenotype of microdeletion 3p25.3 syndrome}}, doi = {10.1038/ejhg.2014.165}, volume = {23}, year = {2015}, } @article{1792, abstract = {Motivated by recent ideas of Harman (Unif. Distrib. Theory, 2010) we develop a new concept of variation of multivariate functions on a compact Hausdorff space with respect to a collection D of subsets. We prove a general version of the Koksma-Hlawka theorem that holds for this notion of variation and discrepancy with respect to D. As special cases, we obtain Koksma-Hlawka inequalities for classical notions, such as extreme or isotropic discrepancy. For extreme discrepancy, our result coincides with the usual Koksma-Hlawka theorem. We show that the space of functions of bounded D-variation contains important discontinuous functions and is closed under natural algebraic operations. Finally, we illustrate the results on concrete integration problems from integral geometry and stereology.}, author = {Pausinger, Florian and Svane, Anne}, journal = {Journal of Complexity}, number = {6}, pages = {773 -- 797}, publisher = {Academic Press}, title = {{A Koksma-Hlawka inequality for general discrepancy systems}}, doi = {10.1016/j.jco.2015.06.002}, volume = {31}, year = {2015}, } @article{1793, abstract = {We present a software platform for reconstructing and analyzing the growth of a plant root system from a time-series of 3D voxelized shapes. It aligns the shapes with each other, constructs a geometric graph representation together with the function that records the time of growth, and organizes the branches into a hierarchy that reflects the order of creation. The software includes the automatic computation of structural and dynamic traits for each root in the system enabling the quantification of growth on fine-scale. These are important advances in plant phenotyping with applications to the study of genetic and environmental influences on growth.}, author = {Symonova, Olga and Topp, Christopher and Edelsbrunner, Herbert}, journal = {PLoS One}, number = {6}, publisher = {Public Library of Science}, title = {{DynamicRoots: A software platform for the reconstruction and analysis of growing plant roots}}, doi = {10.1371/journal.pone.0127657}, volume = {10}, year = {2015}, } @article{1802, abstract = {Noncoding variants in the human MIR137 gene locus increase schizophrenia risk with genome-wide significance. However, the functional consequence of these risk alleles is unknown. Here we examined induced human neurons harboring the minor alleles of four disease-associated single nucleotide polymorphisms in MIR137. We observed increased MIR137 levels compared to those in major allele–carrying cells. microRNA-137 gain of function caused downregulation of the presynaptic target genes complexin-1 (Cplx1), Nsf and synaptotagmin-1 (Syt1), leading to impaired vesicle release. In vivo, miR-137 gain of function resulted in changes in synaptic vesicle pool distribution, impaired induction of mossy fiber long-term potentiation and deficits in hippocampus-dependent learning and memory. By sequestering endogenous miR-137, we were able to ameliorate the synaptic phenotypes. Moreover, reinstatement of Syt1 expression partially restored synaptic plasticity, demonstrating the importance of Syt1 as a miR-137 target. Our data provide new insight into the mechanism by which miR-137 dysregulation can impair synaptic plasticity in the hippocampus.}, author = {Sandra Siegert and Seo, Jinsoo and Kwon, Ester J and Rudenko, Andrii and Cho, Sukhee and Wang, Wenyuan and Flood, Zachary C and Martorell, Anthony J and Ericsson, Maria and Mungenast, Alison E and Tsai, Lihuei}, journal = {Nature Neuroscience}, pages = {1008 -- 1016}, publisher = {Nature Publishing Group}, title = {{The schizophrenia risk gene product miR-137 alters presynaptic plasticity}}, doi = {10.1038/nn.4023}, volume = {18}, year = {2015}, } @article{1803, abstract = {Repeated stress has been suggested to underlie learning and memory deficits via the basolateral amygdala (BLA) and the hippocampus; however, the functional contribution of BLA inputs to the hippocampus and their molecular repercussions are not well understood. Here we show that repeated stress is accompanied by generation of the Cdk5 (cyclin-dependent kinase 5)-activator p25, up-regulation and phosphorylation of glucocorticoid receptors, increased HDAC2 expression, and reduced expression of memoryrelated genes in the hippocampus. A combination of optogenetic and pharmacosynthetic approaches shows that BLA activation is both necessary and sufficient for stress-associated molecular changes and memory impairments. Furthermore, we show that this effect relies on direct glutamatergic projections from the BLA to the dorsal hippocampus. Finally, we show that p25 generation is necessary for the stress-induced memory dysfunction. Taken together, our data provide a neural circuit model for stress-induced hippocampal memory deficits through BLA activity-dependent p25 generation.}, author = {Rei, Damien and Mason, Xenos and Seo, Jinsoo and Gräff, Johannes and Rudenko, Andrii and Wang, Jùn and Rueda, Richard and Sandra Siegert and Cho, Sukhee and Canter, Rebecca G and Mungenast, Alison E and Deisseroth, Karl A and Tsai, Lihuei}, journal = {PNAS}, number = {23}, pages = {7291 -- 7296}, publisher = {National Academy of Sciences}, title = {{Basolateral amygdala bidirectionally modulates stress induced hippocampal learning and memory deficits through a p25/Cdk5-dependent pathway}}, doi = {10.1073/pnas.1415845112}, volume = {112}, year = {2015}, } @article{1804, abstract = {It is known that in classical fluids turbulence typically occurs at high Reynolds numbers. But can turbulence occur at low Reynolds numbers? Here we investigate the transition to turbulence in the classic Taylor-Couette system in which the rotating fluids are manufactured ferrofluids with magnetized nanoparticles embedded in liquid carriers. We find that, in the presence of a magnetic field transverse to the symmetry axis of the system, turbulence can occur at Reynolds numbers that are at least one order of magnitude smaller than those in conventional fluids. This is established by extensive computational ferrohydrodynamics through a detailed investigation of transitions in the flow structure, and characterization of behaviors of physical quantities such as the energy, the wave number, and the angular momentum through the bifurcations. A finding is that, as the magnetic field is increased, onset of turbulence can be determined accurately and reliably. Our results imply that experimental investigation of turbulence may be feasible by using ferrofluids. Our study of transition to and evolution of turbulence in the Taylor-Couette ferrofluidic flow system provides insights into the challenging problem of turbulence control.}, author = {Altmeyer, Sebastian and Do, Younghae and Lai, Ying}, journal = {Scientific Reports}, publisher = {Nature Publishing Group}, title = {{Transition to turbulence in Taylor-Couette ferrofluidic flow}}, doi = {10.1038/srep10781}, volume = {5}, year = {2015}, } @article{1805, abstract = {We consider the problem of deciding whether the persistent homology group of a simplicial pair (K,L) can be realized as the homology H∗(X) of some complex X with L ⊂ X ⊂ K. We show that this problem is NP-complete even if K is embedded in double-struck R3. As a consequence, we show that it is NP-hard to simplify level and sublevel sets of scalar functions on double-struck S3 within a given tolerance constraint. This problem has relevance to the visualization of medical images by isosurfaces. We also show an implication to the theory of well groups of scalar functions: not every well group can be realized by some level set, and deciding whether a well group can be realized is NP-hard.}, author = {Attali, Dominique and Bauer, Ulrich and Devillers, Olivier and Glisse, Marc and Lieutier, André}, journal = {Computational Geometry: Theory and Applications}, number = {8}, pages = {606 -- 621}, publisher = {Elsevier}, title = {{Homological reconstruction and simplification in R3}}, doi = {10.1016/j.comgeo.2014.08.010}, volume = {48}, year = {2015}, } @article{1807, abstract = {We study a double Cahn-Hilliard type functional related to the Gross-Pitaevskii energy of two-components Bose-Einstein condensates. In the case of large but same order intercomponent and intracomponent coupling strengths, we prove Γ-convergence to a perimeter minimisation functional with an inhomogeneous surface tension. We study the asymptotic behavior of the surface tension as the ratio between the intercomponent and intracomponent coupling strengths becomes very small or very large and obtain good agreement with the physical literature. We obtain as a consequence, symmetry breaking of the minimisers for the harmonic potential.}, author = {Goldman, Michael and Royo-Letelier, Jimena}, journal = {ESAIM - Control, Optimisation and Calculus of Variations}, number = {3}, pages = {603 -- 624}, publisher = {EDP Sciences}, title = {{Sharp interface limit for two components Bose-Einstein condensates}}, doi = {10.1051/cocv/2014040}, volume = {21}, year = {2015}, } @article{1808, author = {Gupta, Ashutosh and Henzinger, Thomas A}, journal = {ACM Transactions on Modeling and Computer Simulation}, number = {2}, publisher = {ACM}, title = {{Guest editors' introduction to special issue on computational methods in systems biology}}, doi = {10.1145/2745799}, volume = {25}, year = {2015}, } @article{1809, abstract = {Background: Indirect genetic effects (IGEs) occur when genes expressed in one individual alter the expression of traits in social partners. Previous studies focused on the evolutionary consequences and evolutionary dynamics of IGEs, using equilibrium solutions to predict phenotypes in subsequent generations. However, whether or not such steady states may be reached may depend on the dynamics of interactions themselves. Results: In our study, we focus on the dynamics of social interactions and indirect genetic effects and investigate how they modify phenotypes over time. Unlike previous IGE studies, we do not analyse evolutionary dynamics; rather we consider within-individual phenotypic changes, also referred to as phenotypic plasticity. We analyse iterative interactions, when individuals interact in a series of discontinuous events, and investigate the stability of steady state solutions and the dependence on model parameters, such as population size, strength, and the nature of interactions. We show that for interactions where a feedback loop occurs, the possible parameter space of interaction strength is fairly limited, affecting the evolutionary consequences of IGEs. We discuss the implications of our results for current IGE model predictions and their limitations.}, author = {Trubenova, Barbora and Novak, Sebastian and Hager, Reinmar}, journal = {PLoS One}, number = {5}, publisher = {Public Library of Science}, title = {{Indirect genetic effects and the dynamics of social interactions}}, doi = {10.1371/journal.pone.0126907}, volume = {10}, year = {2015}, } @article{1810, abstract = {Combining antibiotics is a promising strategy for increasing treatment efficacy and for controlling resistance evolution. When drugs are combined, their effects on cells may be amplified or weakened, that is the drugs may show synergistic or antagonistic interactions. Recent work revealed the underlying mechanisms of such drug interactions by elucidating the drugs'; joint effects on cell physiology. Moreover, new treatment strategies that use drug combinations to exploit evolutionary tradeoffs were shown to affect the rate of resistance evolution in predictable ways. High throughput studies have further identified drug candidates based on their interactions with established antibiotics and general principles that enable the prediction of drug interactions were suggested. Overall, the conceptual and technical foundation for the rational design of potent drug combinations is rapidly developing.}, author = {Bollenbach, Mark Tobias}, journal = {Current Opinion in Microbiology}, pages = {1 -- 9}, publisher = {Elsevier}, title = {{Antimicrobial interactions: Mechanisms and implications for drug discovery and resistance evolution}}, doi = {10.1016/j.mib.2015.05.008}, volume = {27}, year = {2015}, } @article{1811, abstract = {Atomic form factors are widely used for the characterization of targets and specimens, from crystallography to biology. By using recent mathematical results, here we derive an analytical expression for the atomic form factor within the independent particle model constructed from nonrelativistic screened hydrogenic wave functions. The range of validity of this analytical expression is checked by comparing the analytically obtained form factors with the ones obtained within the Hartee-Fock method. As an example, we apply our analytical expression for the atomic form factor to evaluate the differential cross section for Rayleigh scattering off neutral atoms.}, author = {Safari, Laleh and Santos, José and Amaro, Pedro and Jänkälä, Kari and Fratini, Filippo}, journal = {Journal of Mathematical Physics}, number = {5}, publisher = {American Institute of Physics}, title = {{Analytical evaluation of atomic form factors: Application to Rayleigh scattering}}, doi = {10.1063/1.4921227}, volume = {56}, year = {2015}, } @article{1812, abstract = {We investigate the occurrence of rotons in a quadrupolar Bose–Einstein condensate confined to two dimensions. Depending on the particle density, the ratio of the contact and quadrupole–quadrupole interactions, and the alignment of the quadrupole moments with respect to the confinement plane, the dispersion relation features two or four point-like roton minima or one ring-shaped minimum. We map out the entire parameter space of the roton behavior and identify the instability regions. We propose to observe the exotic rotons by monitoring the characteristic density wave dynamics resulting from a short local perturbation, and discuss the possibilities to detect the predicted effects in state-of-the-art experiments with ultracold homonuclear molecules. }, author = {Lahrz, Martin and Lemeshko, Mikhail and Mathey, Ludwig}, journal = {New Journal of Physics}, number = {4}, publisher = {IOP Publishing Ltd.}, title = {{Exotic roton excitations in quadrupolar Bose–Einstein condensates }}, doi = {10.1088/1367-2630/17/4/045005}, volume = {17}, year = {2015}, }