TY - JOUR
AB - Guided cell movement is essential for development and integrity of animals and crucially involved in cellular immune responses. Leukocytes are professional migratory cells that can navigate through most types of tissues and sense a wide range of directional cues. The responses of these cells to attractants have been mainly explored in tissue culture settings. How leukocytes make directional decisions in situ, within the challenging environment of a tissue maze, is less understood. Here we review recent advances in how leukocytes sense chemical cues in complex tissue settings and make links with paradigms of directed migration in development and Dictyostelium discoideum amoebae.
AU - Sarris, Milka
AU - Sixt, Michael K
ID - 1687
IS - 10
JF - Current Opinion in Cell Biology
TI - Navigating in tissue mazes: Chemoattractant interpretation in complex environments
VL - 36
ER -
TY - CONF
AB - Given a graph G cellularly embedded on a surface Σ of genus g, a cut graph is a subgraph of G such that cutting Σ along G yields a topological disk. We provide a fixed parameter tractable approximation scheme for the problem of computing the shortest cut graph, that is, for any ε > 0, we show how to compute a (1 + ε) approximation of the shortest cut graph in time f(ε, g)n3.
Our techniques first rely on the computation of a spanner for the problem using the technique of brick decompositions, to reduce the problem to the case of bounded tree-width. Then, to solve the bounded tree-width case, we introduce a variant of the surface-cut decomposition of Rué, Sau and Thilikos, which may be of independent interest.
AU - Cohen Addad, Vincent
AU - De Mesmay, Arnaud N
ID - 1685
TI - A fixed parameter tractable approximation scheme for the optimal cut graph of a surface
VL - 9294
ER -
TY - JOUR
AB - We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer d, there is a constant (Formula presented.) such that whenever (Formula presented.) are n-element subsets of (Formula presented.), we can find a point (Formula presented.) and subsets (Formula presented.) for every i∈[d+1], each of size at least cdn, such that p belongs to all rainbowd-simplices determined by (Formula presented.) simplices with one vertex in each Yi. We show a super-exponentially decreasing upper bound (Formula presented.). The ideas used in the proof of the upper bound also help us to prove Pach’s theorem with (Formula presented.), which is a lower bound doubly exponentially decreasing in d (up to some polynomial in the exponent). For comparison, Pach’s original approach yields a triply exponentially decreasing lower bound. On the other hand, Fox, Pach, and Suk recently obtained a hypergraph density result implying a proof of Pach’s theorem with (Formula presented.). In our construction for the upper bound, we use the fact that the minimum solid angle of every d-simplex is super-exponentially small. This fact was previously unknown and might be of independent interest. For the lower bound, we improve the ‘separation’ part of the argument by showing that in one of the key steps only d+1 separations are necessary, compared to 2d separations in the original proof. We also provide a measure version of Pach’s theorem.
AU - Karasev, Roman
AU - Kynčl, Jan
AU - Paták, Pavel
AU - Patakova, Zuzana
AU - Tancer, Martin
ID - 1688
IS - 3
JF - Discrete & Computational Geometry
TI - Bounds for Pach's selection theorem and for the minimum solid angle in a simplex
VL - 54
ER -
TY - JOUR
AB - We study the problem of robust satisfiability of systems of nonlinear equations, namely, whether for a given continuous function f:K→ ℝn on a finite simplicial complex K and α > 0, it holds that each function g: K → ℝn such that ||g - f || ∞ < α, has a root in K. Via a reduction to the extension problem of maps into a sphere, we particularly show that this problem is decidable in polynomial time for every fixed n, assuming dimK ≤ 2n - 3. This is a substantial extension of previous computational applications of topological degree and related concepts in numerical and interval analysis. Via a reverse reduction, we prove that the problem is undecidable when dim K > 2n - 2, where the threshold comes from the stable range in homotopy theory. For the lucidity of our exposition, we focus on the setting when f is simplexwise linear. Such functions can approximate general continuous functions, and thus we get approximation schemes and undecidability of the robust satisfiability in other possible settings.
AU - Franek, Peter
AU - Krcál, Marek
ID - 1682
IS - 4
JF - Journal of the ACM
TI - Robust satisfiability of systems of equations
VL - 62
ER -
TY - CONF
AB - We consider the problem of computing the set of initial states of a dynamical system such that there exists a control strategy to ensure that the trajectories satisfy a temporal logic specification with probability 1 (almost-surely). We focus on discrete-time, stochastic linear dynamics and specifications given as formulas of the Generalized Reactivity(1) fragment of Linear Temporal Logic over linear predicates in the states of the system. We propose a solution based on iterative abstraction-refinement, and turn-based 2-player probabilistic games. While the theoretical guarantee of our algorithm after any finite number of iterations is only a partial solution, we show that if our algorithm terminates, then the result is the set of satisfying initial states. Moreover, for any (partial) solution our algorithm synthesizes witness control strategies to ensure almost-sure satisfaction of the temporal logic specification. We demonstrate our approach on an illustrative case study.
AU - Svoreňová, Mária
AU - Kretinsky, Jan
AU - Chmelik, Martin
AU - Chatterjee, Krishnendu
AU - Cěrná, Ivana
AU - Belta, Cǎlin
ID - 1689
T2 - Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control
TI - Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games
ER -
TY - JOUR
AB - Quantum interference between energetically close states is theoretically investigated, with the state structure being observed via laser spectroscopy. In this work, we focus on hyperfine states of selected hydrogenic muonic isotopes, and on how quantum interference affects the measured Lamb shift. The process of photon excitation and subsequent photon decay is implemented within the framework of nonrelativistic second-order perturbation theory. Due to its experimental interest, calculations are performed for muonic hydrogen, deuterium, and helium-3. We restrict our analysis to the case of photon scattering by incident linear polarized photons and the polarization of the scattered photons not being observed. We conclude that while quantum interference effects can be safely neglected in muonic hydrogen and helium-3, in the case of muonic deuterium there are resonances with close proximity, where quantum interference effects can induce shifts up to a few percent of the linewidth, assuming a pointlike detector. However, by taking into account the geometry of the setup used by the CREMA collaboration, this effect is reduced to less than 0.2% of the linewidth in all possible cases, which makes it irrelevant at the present level of accuracy. © 2015 American Physical Society.
AU - Amaro, Pedro
AU - Franke, Beatrice
AU - Krauth, Julian
AU - Diepold, Marc
AU - Fratini, Filippo
AU - Safari, Laleh
AU - Machado, Jorge
AU - Antognini, Aldo
AU - Kottmann, Franz
AU - Indelicato, Paul
AU - Pohl, Randolf
AU - Santos, José
ID - 1693
IS - 2
JF - Physical Review A
TI - Quantum interference effects in laser spectroscopy of muonic hydrogen, deuterium, and helium-3
VL - 92
ER -
TY - JOUR
AB - We give a comprehensive introduction into a diagrammatic method that allows for the evaluation of Gutzwiller wave functions in finite spatial dimensions. We discuss in detail some numerical schemes that turned out to be useful in the real-space evaluation of the diagrams. The method is applied to the problem of d-wave superconductivity in a two-dimensional single-band Hubbard model. Here, we discuss in particular the role of long-range contributions in our diagrammatic expansion. We further reconsider our previous analysis on the kinetic energy gain in the superconducting state.
AU - Kaczmarczyk, Jan
AU - Schickling, Tobias
AU - Bünemann, Jörg
ID - 1695
IS - 9
JF - Physica Status Solidi (B): Basic Solid State Physics
TI - Evaluation techniques for Gutzwiller wave functions in finite dimensions
VL - 252
ER -
TY - JOUR
AB - Motion tracking is a challenge the visual system has to solve by reading out the retinal population. It is still unclear how the information from different neurons can be combined together to estimate the position of an object. Here we recorded a large population of ganglion cells in a dense patch of salamander and guinea pig retinas while displaying a bar moving diffusively. We show that the bar’s position can be reconstructed from retinal activity with a precision in the hyperacuity regime using a linear decoder acting on 100+ cells. We then took advantage of this unprecedented precision to explore the spatial structure of the retina’s population code. The classical view would have suggested that the firing rates of the cells form a moving hill of activity tracking the bar’s position. Instead, we found that most ganglion cells in the salamander fired sparsely and idiosyncratically, so that their neural image did not track the bar. Furthermore, ganglion cell activity spanned an area much larger than predicted by their receptive fields, with cells coding for motion far in their surround. As a result, population redundancy was high, and we could find multiple, disjoint subsets of neurons that encoded the trajectory with high precision. This organization allows for diverse collections of ganglion cells to represent high-accuracy motion information in a form easily read out by downstream neural circuits.
AU - Marre, Olivier
AU - Botella Soler, Vicente
AU - Simmons, Kristina
AU - Mora, Thierry
AU - Tkacik, Gasper
AU - Berry, Michael
ID - 1697
IS - 7
JF - PLoS Computational Biology
TI - High accuracy decoding of dynamical motion from a large retinal population
VL - 11
ER -
TY - JOUR
AB - By hybridization and backcrossing, alleles can surmount species boundaries and be incorporated into the genome of a related species. This introgression of genes is of particular evolutionary relevance if it involves the transfer of adaptations between populations. However, any beneficial allele will typically be associated with other alien alleles that are often deleterious and hamper the introgression process. In order to describe the introgression of an adaptive allele, we set up a stochastic model with an explicit genetic makeup of linked and unlinked deleterious alleles. Based on the theory of reducible multitype branching processes, we derive a recursive expression for the establishment probability of the beneficial allele after a single hybridization event. We furthermore study the probability that slightly deleterious alleles hitchhike to fixation. The key to the analysis is a split of the process into a stochastic phase in which the advantageous alleles establishes and a deterministic phase in which it sweeps to fixation. We thereafter apply the theory to a set of biologically relevant scenarios such as introgression in the presence of many unlinked or few closely linked deleterious alleles. A comparison to computer simulations shows that the approximations work well over a large parameter range.
AU - Uecker, Hildegard
AU - Setter, Derek
AU - Hermisson, Joachim
ID - 1699
IS - 7
JF - Journal of Mathematical Biology
TI - Adaptive gene introgression after secondary contact
VL - 70
ER -
TY - JOUR
AB - The recently proposed diagrammatic expansion (DE) technique for the full Gutzwiller wave function (GWF) is applied to the Anderson lattice model. This approach allows for a systematic evaluation of the expectation values with full Gutzwiller wave function in finite-dimensional systems. It introduces results extending in an essential manner those obtained by means of the standard Gutzwiller approximation (GA), which is variationally exact only in infinite dimensions. Within the DE-GWF approach we discuss the principal paramagnetic properties and their relevance to heavy-fermion systems. We demonstrate the formation of an effective, narrow f band originating from atomic f-electron states and subsequently interpret this behavior as a direct itineracy of f electrons; it represents a combined effect of both the hybridization and the correlations induced by the Coulomb repulsive interaction. Such a feature is absent on the level of GA, which is equivalent to the zeroth order of our expansion. Formation of the hybridization- and electron-concentration-dependent narrow f band rationalizes the common assumption of such dispersion of f levels in the phenomenological modeling of the band structure of CeCoIn5. Moreover, it is shown that the emerging f-electron direct itineracy leads in a natural manner to three physically distinct regimes within a single model that are frequently discussed for 4f- or 5f-electron compounds as separate model situations. We identify these regimes as (i) the mixed-valence regime, (ii) Kondo/almost-Kondo insulating regime, and (iii) the Kondo-lattice limit when the f-electron occupancy is very close to the f-state half filling, ⟨nˆf⟩→1. The nonstandard features of the emerging correlated quantum liquid state are stressed.
AU - Wysokiński, Marcin
AU - Kaczmarczyk, Jan
AU - Spałek, Jozef
ID - 1696
IS - 12
JF - Physical Review B
TI - Gutzwiller wave function solution for Anderson lattice model: Emerging universal regimes of heavy quasiparticle states
VL - 92
ER -
TY - JOUR
AB - The activity of a neural network is defined by patterns of spiking and silence from the individual neurons. Because spikes are (relatively) sparse, patterns of activity with increasing numbers of spikes are less probable, but, with more spikes, the number of possible patterns increases. This tradeoff between probability and numerosity is mathematically equivalent to the relationship between entropy and energy in statistical physics. We construct this relationship for populations of up to N = 160 neurons in a small patch of the vertebrate retina, using a combination of direct and model-based analyses of experiments on the response of this network to naturalistic movies. We see signs of a thermodynamic limit, where the entropy per neuron approaches a smooth function of the energy per neuron as N increases. The form of this function corresponds to the distribution of activity being poised near an unusual kind of critical point. We suggest further tests of criticality, and give a brief discussion of its functional significance.
AU - Tkacik, Gasper
AU - Mora, Thierry
AU - Marre, Olivier
AU - Amodei, Dario
AU - Palmer, Stephanie
AU - Berry Ii, Michael
AU - Bialek, William
ID - 1701
IS - 37
JF - PNAS
TI - Thermodynamics and signatures of criticality in a network of neurons
VL - 112
ER -
TY - JOUR
AB - In mean-payoff games, the objective of the protagonist is to ensure that the limit average of an infinite sequence of numeric weights is nonnegative. In energy games, the objective is to ensure that the running sum of weights is always nonnegative. Multi-mean-payoff and multi-energy games replace individual weights by tuples, and the limit average (resp., running sum) of each coordinate must be (resp., remain) nonnegative. We prove finite-memory determinacy of multi-energy games and show inter-reducibility of multi-mean-payoff and multi-energy games for finite-memory strategies. We improve the computational complexity for solving both classes with finite-memory strategies: we prove coNP-completeness improving the previous known EXPSPACE bound. For memoryless strategies, we show that deciding the existence of a winning strategy for the protagonist is NP-complete. We present the first solution of multi-mean-payoff games with infinite-memory strategies: we show that mean-payoff-sup objectives can be decided in NP∩coNP, whereas mean-payoff-inf objectives are coNP-complete.
AU - Velner, Yaron
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Henzinger, Thomas A
AU - Rabinovich, Alexander
AU - Raskin, Jean
ID - 1698
IS - 4
JF - Information and Computation
TI - The complexity of multi-mean-payoff and multi-energy games
VL - 241
ER -
TY - JOUR
AB - We use the dual boson approach to reveal the phase diagram of the Fermi-Hubbard model with long-range dipole-dipole interactions. By using a large-scale finite-temperature calculation on a 64×64 square lattice we demonstrate the existence of a novel phase, possessing an "ultralong-range" order. The fingerprint of this phase - the density correlation function - features a nontrivial behavior on a scale of tens of lattice sites. We study the properties and the stability of the ultralong-range-ordered phase, and show that it is accessible in modern experiments with ultracold polar molecules and magnetic atoms.
AU - Van Loon, Erik
AU - Katsnelson, Mikhail
AU - Lemeshko, Mikhail
ID - 1700
IS - 8
JF - Physical Review B
TI - Ultralong-range order in the Fermi-Hubbard model with long-range interactions
VL - 92
ER -
TY - JOUR
AB - The competition for resources among cells, individuals or species is a fundamental characteristic of evolution. Biological all-pay auctions have been used to model situations where multiple individuals compete for a single resource. However, in many situations multiple resources with various values exist and single reward auctions are not applicable. We generalize the model to multiple rewards and study the evolution of strategies. In biological all-pay auctions the bid of an individual corresponds to its strategy and is equivalent to its payment in the auction. The decreasingly ordered rewards are distributed according to the decreasingly ordered bids of the participating individuals. The reproductive success of an individual is proportional to its fitness given by the sum of the rewards won minus its payments. Hence, successful bidding strategies spread in the population. We find that the results for the multiple reward case are very different from the single reward case. While the mixed strategy equilibrium in the single reward case with more than two players consists of mostly low-bidding individuals, we show that the equilibrium can convert to many high-bidding individuals and a few low-bidding individuals in the multiple reward case. Some reward values lead to a specialization among the individuals where one subpopulation competes for the rewards and the other subpopulation largely avoids costly competitions. Whether the mixed strategy equilibrium is an evolutionarily stable strategy (ESS) depends on the specific values of the rewards.
AU - Reiter, Johannes
AU - Kanodia, Ayush
AU - Gupta, Raghav
AU - Nowak, Martin
AU - Chatterjee, Krishnendu
ID - 1709
IS - 1812
JF - Proceedings of the Royal Society of London Series B Biological Sciences
TI - Biological auctions with multiple rewards
VL - 282
ER -
TY - JOUR
AB - Given a convex function (Formula presented.) and two hermitian matrices A and B, Lewin and Sabin study in (Lett Math Phys 104:691–705, 2014) the relative entropy defined by (Formula presented.). Among other things, they prove that the so-defined quantity is monotone if and only if (Formula presented.) is operator monotone. The monotonicity is then used to properly define (Formula presented.) for bounded self-adjoint operators acting on an infinite-dimensional Hilbert space by a limiting procedure. More precisely, for an increasing sequence of finite-dimensional projections (Formula presented.) with (Formula presented.) strongly, the limit (Formula presented.) is shown to exist and to be independent of the sequence of projections (Formula presented.). The question whether this sequence converges to its "obvious" limit, namely (Formula presented.), has been left open. We answer this question in principle affirmatively and show that (Formula presented.). If the operators A and B are regular enough, that is (A − B), (Formula presented.) and (Formula presented.) are trace-class, the identity (Formula presented.) holds.
AU - Deuchert, Andreas
AU - Hainzl, Christian
AU - Seiringer, Robert
ID - 1704
IS - 10
JF - Letters in Mathematical Physics
TI - Note on a family of monotone quantum relative entropies
VL - 105
ER -
TY - CONF
AB - We consider a problem of learning kernels for use in SVM classification in the multi-task and lifelong scenarios and provide generalization bounds on the error of a large margin classifier. Our results show that, under mild conditions on the family of kernels used for learning, solving several related tasks simultaneously is beneficial over single task learning. In particular, as the number of observed tasks grows, assuming that in the considered family of kernels there exists one that yields low approximation error on all tasks, the overhead associated with learning such a kernel vanishes and the complexity converges to that of learning when this good kernel is given to the learner.
AU - Pentina, Anastasia
AU - Ben David, Shai
ID - 1706
TI - Multi-task and lifelong learning of kernels
VL - 9355
ER -
TY - JOUR
AB - The majority of immune cells in Drosophila melanogaster are plasmatocytes; they carry out similar functions to vertebrate macrophages, influencing development as well as protecting against infection and cancer. Plasmatocytes, sometimes referred to with the broader term of hemocytes, migrate widely during embryonic development and cycle in the larvae between sessile and circulating positions. Here we discuss the similarities of plasmatocyte developmental migration and its functions to that of vertebrate macrophages, considering the recent controversy regarding the functions of Drosophila PDGF/VEGF related ligands. We also examine recent findings on the significance of adhesion for plasmatocyte migration in the embryo, as well as proliferation, trans-differentiation, and tumor responses in the larva. We spotlight parallels throughout to vertebrate immune responses.
AU - Ratheesh, Aparna
AU - Belyaeva, Vera
AU - Siekhaus, Daria E
ID - 1712
IS - 10
JF - Current Opinion in Cell Biology
TI - Drosophila immune cell migration and adhesion during embryonic development and larval immune responses
VL - 36
ER -
TY - JOUR
AB - We consider the hollow on the half-plane {(x, y) : y ≤ 0} ⊂ ℝ2 defined by a function u : (-1, 1) → ℝ, u(x) < 0, and a vertical flow of point particles incident on the hollow. It is assumed that u satisfies the so-called single impact condition (SIC): each incident particle is elastically reflected by graph(u) and goes away without hitting the graph of u anymore. We solve the problem: find the function u minimizing the force of resistance created by the flow. We show that the graph of the minimizer is formed by two arcs of parabolas symmetric to each other with respect to the y-axis. Assuming that the resistance of u ≡ 0 equals 1, we show that the minimal resistance equals π/2 - 2arctan(1/2) ≈ 0.6435. This result completes the previously obtained result [SIAM J. Math. Anal., 46 (2014), pp. 2730-2742] stating in particular that the minimal resistance of a hollow in higher dimensions equals 0.5. We additionally consider a similar problem of minimal resistance, where the hollow in the half-space {(x1,...,xd,y) : y ≤ 0} ⊂ ℝd+1 is defined by a radial function U satisfying the SIC, U(x) = u(|x|), with x = (x1,...,xd), u(ξ) < 0 for 0 ≤ ξ < 1, and u(ξ) = 0 for ξ ≥ 1, and the flow is parallel to the y-axis. The minimal resistance is greater than 0.5 (and coincides with 0.6435 when d = 1) and converges to 0.5 as d → ∞.
AU - Akopyan, Arseniy
AU - Plakhov, Alexander
ID - 1710
IS - 4
JF - Society for Industrial and Applied Mathematics
TI - Minimal resistance of curves under the single impact assumption
VL - 47
ER -
TY - JOUR
AB - 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.
AU - Colin De Verdière, Éric
AU - Hubard, Alfredo
AU - De Mesmay, Arnaud N
ID - 1730
IS - 3
JF - Discrete & Computational Geometry
TI - Discrete systolic inequalities and decompositions of triangulated surfaces
VL - 53
ER -
TY - JOUR
AB - 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.
AU - Ando, Ryoichi
AU - Thürey, Nils
AU - Wojtan, Christopher J
ID - 1735
IS - 2
JF - Computer Graphics Forum
TI - A dimension-reduced pressure solver for liquid simulations
VL - 34
ER -
TY - JOUR
AB - 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.
AU - Kuechler, Alma
AU - Zink, Alexander
AU - Wieland, Thomas
AU - Lüdecke, Hermann
AU - Cremer, Kirsten
AU - Salviati, Leonardo
AU - Magini, Pamela
AU - Najafi, Kimia
AU - Zweier, Christiane
AU - Czeschik, Johanna
AU - Aretz, Stefan
AU - Endele, Sabine
AU - Tamburrino, Federica
AU - Pinato, Claudia
AU - Clementi, Maurizio
AU - Gundlach, Jasmin
AU - Maylahn, Carina
AU - Mazzanti, Laura
AU - Wohlleber, Eva
AU - Schwarzmayr, Thomas
AU - Kariminejad, Roxana
AU - Schlessinger, Avner
AU - Wieczorek, Dagmar
AU - Strom, Tim
AU - Novarino, Gaia
AU - Engels, Hartmut
ID - 1789
IS - 6
JF - European Journal of Human Genetics
TI - Loss-of-function variants of SETD5 cause intellectual disability and the core phenotype of microdeletion 3p25.3 syndrome
VL - 23
ER -
TY - JOUR
AB - 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.
AU - Altmeyer, Sebastian
AU - Do, Younghae
AU - Lai, Ying
ID - 1804
JF - Scientific Reports
TI - Transition to turbulence in Taylor-Couette ferrofluidic flow
VL - 5
ER -
TY - JOUR
AB - 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.
AU - Goldman, Michael
AU - Royo-Letelier, Jimena
ID - 1807
IS - 3
JF - ESAIM - Control, Optimisation and Calculus of Variations
TI - Sharp interface limit for two components Bose-Einstein condensates
VL - 21
ER -
TY - JOUR
AB - 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.
AU - Bollenbach, Mark Tobias
ID - 1810
JF - Current Opinion in Microbiology
TI - Antimicrobial interactions: Mechanisms and implications for drug discovery and resistance evolution
VL - 27
ER -
TY - JOUR
AB - 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.
AU - Lahrz, Martin
AU - Lemeshko, Mikhail
AU - Mathey, Ludwig
ID - 1812
IS - 4
JF - New Journal of Physics
TI - Exotic roton excitations in quadrupolar Bose–Einstein condensates
VL - 17
ER -
TY - JOUR
AB - 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.
AU - Safari, Laleh
AU - Santos, José
AU - Amaro, Pedro
AU - Jänkälä, Kari
AU - Fratini, Filippo
ID - 1811
IS - 5
JF - Journal of Mathematical Physics
TI - Analytical evaluation of atomic form factors: Application to Rayleigh scattering
VL - 56
ER -
TY - JOUR
AB - We develop a microscopic theory describing a quantum impurity whose rotational degree of freedom is coupled to a many-particle bath. We approach the problem by introducing the concept of an “angulon”—a quantum rotor dressed by a quantum field—and reveal its quasiparticle properties using a combination of variational and diagrammatic techniques. Our theory predicts renormalization of the impurity rotational structure, such as that observed in experiments with molecules in superfluid helium droplets, in terms of a rotational Lamb shift induced by the many-particle environment. Furthermore, we discover a rich many-body-induced fine structure, emerging in rotational spectra due to a redistribution of angular momentum within the quantum many-body system.
AU - Schmidt, Richard
AU - Lemeshko, Mikhail
ID - 1813
IS - 20
JF - Physical Review Letters
TI - Rotation of quantum impurities in the presence of a many-body environment
VL - 114
ER -
TY - JOUR
AB - Vertebrates have a unique 3D body shape in which correct tissue and organ shape and alignment are essential for function. For example, vision requires the lens to be centred in the eye cup which must in turn be correctly positioned in the head. Tissue morphogenesis depends on force generation, force transmission through the tissue, and response of tissues and extracellular matrix to force. Although a century ago D'Arcy Thompson postulated that terrestrial animal body shapes are conditioned by gravity, there has been no animal model directly demonstrating how the aforementioned mechano-morphogenetic processes are coordinated to generate a body shape that withstands gravity. Here we report a unique medaka fish (Oryzias latipes) mutant, hirame (hir), which is sensitive to deformation by gravity. hir embryos display a markedly flattened body caused by mutation of YAP, a nuclear executor of Hippo signalling that regulates organ size. We show that actomyosin-mediated tissue tension is reduced in hir embryos, leading to tissue flattening and tissue misalignment, both of which contribute to body flattening. By analysing YAP function in 3D spheroids of human cells, we identify the Rho GTPase activating protein ARHGAP18 as an effector of YAP in controlling tissue tension. Together, these findings reveal a previously unrecognised function of YAP in regulating tissue shape and alignment required for proper 3D body shape. Understanding this morphogenetic function of YAP could facilitate the use of embryonic stem cells to generate complex organs requiring correct alignment of multiple tissues.
AU - Porazinski, Sean
AU - Wang, Huijia
AU - Asaoka, Yoichi
AU - Behrndt, Martin
AU - Miyamoto, Tatsuo
AU - Morita, Hitoshi
AU - Hata, Shoji
AU - Sasaki, Takashi
AU - Krens, Gabriel
AU - Osada, Yumi
AU - Asaka, Satoshi
AU - Momoi, Akihiro
AU - Linton, Sarah
AU - Miesfeld, Joel
AU - Link, Brian
AU - Senga, Takeshi
AU - Castillo Morales, Atahualpa
AU - Urrutia, Araxi
AU - Shimizu, Nobuyoshi
AU - Nagase, Hideaki
AU - Matsuura, Shinya
AU - Bagby, Stefan
AU - Kondoh, Hisato
AU - Nishina, Hiroshi
AU - Heisenberg, Carl-Philipp J
AU - Furutani Seiki, Makoto
ID - 1817
IS - 7551
JF - Nature
TI - YAP is essential for tissue tension to ensure vertebrate 3D body shape
VL - 521
ER -
TY - CONF
AB - We consider partially observable Markov decision processes (POMDPs) with a set of target states and every transition is associated with an integer cost. The optimization objec- tive we study asks to minimize the expected total cost till the target set is reached, while ensuring that the target set is reached almost-surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost and the bound is double exponential; (ii) we show that the problem of approximating the optimal cost is decidable and present ap- proximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst- case running time of our algorithm is double exponential, we present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Gupta, Raghav
AU - Kanodia, Ayush
ID - 1820
T2 - Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence
TI - Optimal cost almost-sure reachability in POMDPs
VL - 5
ER -
TY - JOUR
AB - We present an efficient wavefront tracking algorithm for animating bodies of water that interact with their environment. Our contributions include: a novel wavefront tracking technique that enables dispersion, refraction, reflection, and diffraction in the same simulation; a unique multivalued function interpolation method that enables our simulations to elegantly sidestep the Nyquist limit; a dispersion approximation for efficiently amplifying the number of simulated waves by several orders of magnitude; and additional extensions that allow for time-dependent effects and interactive artistic editing of the resulting animation. Our contributions combine to give us multitudes more wave details than similar algorithms, while maintaining high frame rates and allowing close camera zooms.
AU - Jeschke, Stefan
AU - Wojtan, Christopher J
ID - 1814
IS - 3
JF - ACM Transactions on Graphics
TI - Water wave animation via wavefront parameter interpolation
VL - 34
ER -
TY - JOUR
AB - Why do species not adapt to ever-wider ranges of conditions, gradually expanding their ecological niche and geographic range? Gene flow across environments has two conflicting effects: although it increases genetic variation, which is a prerequisite for adaptation, gene flow may swamp adaptation to local conditions. In 1956, Haldane proposed that, when the environment varies across space, "swamping" by gene flow creates a positive feedback between low population size and maladaptation, leading to a sharp range margin. However, current deterministic theory shows that, when variance can evolve, there is no such limit. Using simple analytical tools and simulations, we show that genetic drift can generate a sharp margin to a species' range, by reducing genetic variance below the level needed for adaptation to spatially variable conditions. Aided by separation of ecological and evolutionary timescales, the identified effective dimensionless parameters reveal a simple threshold that predicts when adaptation at the range margin fails. Two observable parameters determine the threshold: (i) the effective environmental gradient, which can be measured by the loss of fitness due to dispersal to a different environment; and (ii) the efficacy of selection relative to genetic drift. The theory predicts sharp range margins even in the absence of abrupt changes in the environment. Furthermore, it implies that gradual worsening of conditions across a species' habitat may lead to a sudden range fragmentation, when adaptation to a wide span of conditions within a single species becomes impossible.
AU - Polechova, Jitka
AU - Barton, Nicholas H
ID - 1818
IS - 20
JF - PNAS
TI - Limits to adaptation along environmental gradients
VL - 112
ER -
TY - JOUR
AB - Abstract Drug combinations are increasingly important in disease treatments, for combating drug resistance, and for elucidating fundamental relationships in cell physiology. When drugs are combined, their individual effects on cells may be amplified or weakened. Such drug interactions are crucial for treatment efficacy, but their underlying mechanisms remain largely unknown. To uncover the causes of drug interactions, we developed a systematic approach based on precise quantification of the individual and joint effects of antibiotics on growth of genome-wide Escherichia coli gene deletion strains. We found that drug interactions between antibiotics representing the main modes of action are highly robust to genetic perturbation. This robustness is encapsulated in a general principle of bacterial growth, which enables the quantitative prediction of mutant growth rates under drug combinations. Rare violations of this principle exposed recurring cellular functions controlling drug interactions. In particular, we found that polysaccharide and ATP synthesis control multiple drug interactions with previously unexplained mechanisms, and small molecule adjuvants targeting these functions synthetically reshape drug interactions in predictable ways. These results provide a new conceptual framework for the design of multidrug combinations and suggest that there are universal mechanisms at the heart of most drug interactions. Synopsis A general principle of bacterial growth enables the prediction of mutant growth rates under drug combinations. Rare violations of this principle expose cellular functions that control drug interactions and can be targeted by small molecules to alter drug interactions in predictable ways. Drug interactions between antibiotics are highly robust to genetic perturbations. A general principle of bacterial growth enables the prediction of mutant growth rates under drug combinations. Rare violations of this principle expose cellular functions that control drug interactions. Diverse drug interactions are controlled by recurring cellular functions, including LPS synthesis and ATP synthesis. A general principle of bacterial growth enables the prediction of mutant growth rates under drug combinations. Rare violations of this principle expose cellular functions that control drug interactions and can be targeted by small molecules to alter drug interactions in predictable ways.
AU - Chevereau, Guillaume
AU - Bollenbach, Mark Tobias
ID - 1823
IS - 4
JF - Molecular Systems Biology
TI - Systematic discovery of drug interaction mechanisms
VL - 11
ER -
TY - JOUR
AB - Condensation phenomena arise through a collective behaviour of particles. They are observed in both classical and quantum systems, ranging from the formation of traffic jams in mass transport models to the macroscopic occupation of the energetic ground state in ultra-cold bosonic gases (Bose-Einstein condensation). Recently, it has been shown that a driven and dissipative system of bosons may form multiple condensates. Which states become the condensates has, however, remained elusive thus far. The dynamics of this condensation are described by coupled birth-death processes, which also occur in evolutionary game theory. Here we apply concepts from evolutionary game theory to explain the formation of multiple condensates in such driven-dissipative bosonic systems. We show that the vanishing of relative entropy production determines their selection. The condensation proceeds exponentially fast, but the system never comes to rest. Instead, the occupation numbers of condensates may oscillate, as we demonstrate for a rock-paper-scissors game of condensates.
AU - Knebel, Johannes
AU - Weber, Markus
AU - Krüger, Torben H
AU - Frey, Erwin
ID - 1824
JF - Nature Communications
TI - Evolutionary games of condensates in coupled birth-death processes
VL - 6
ER -
TY - JOUR
AB - This paper introduces a theme issue presenting the latest developments in research on the impacts of sociality on health and fitness. The articles that follow cover research on societies ranging from insects to humans. Variation in measures of fitness (i.e. survival and reproduction) has been linked to various aspects of sociality in humans and animals alike, and variability in individual health and condition has been recognized as a key mediator of these relationships. Viewed from a broad evolutionary perspective, the evolutionary transitions from a solitary lifestyle to group living have resulted in several new health-related costs and benefits of sociality. Social transmission of parasites within groups represents a major cost of group living, but some behavioural mechanisms, such as grooming, have evolved repeatedly to reduce this cost. Group living also has created novel costs in terms of altered susceptibility to infectious and non-infectious disease as a result of the unavoidable physiological consequences of social competition and integration, which are partly alleviated by social buffering in some vertebrates. Here, we define the relevant aspects of sociality, summarize their health-related costs and benefits, and discuss possible fitness measures in different study systems. Given the pervasive effects of social factors on health and fitness, we propose a synthesis of existing conceptual approaches in disease ecology, ecological immunology and behavioural neurosciences by adding sociality as a key factor, with the goal to generate a broader framework for organismal integration of health-related research.
AU - Kappeler, Peter
AU - Cremer, Sylvia
AU - Nunn, Charles
ID - 1831
IS - 1669
JF - Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences
TI - Sociality and health: Impacts of sociality on disease susceptibility and transmission in animal and human societies
VL - 370
ER -
TY - JOUR
AB - We construct a non-linear Markov process connected with a biological model of a bacterial genome recombination. The description of invariant measures of this process gives us the solution of one problem in elementary probability theory.
AU - Akopyan, Arseniy
AU - Pirogov, Sergey
AU - Rybko, Aleksandr
ID - 1828
IS - 1
JF - Journal of Statistical Physics
TI - Invariant measures of genetic recombination process
VL - 160
ER -
TY - CONF
AB - The behaviour of gene regulatory networks (GRNs) is typically analysed using simulation-based statistical testing-like methods. In this paper, we demonstrate that we can replace this approach by a formal verification-like method that gives higher assurance and scalability. We focus on Wagner’s weighted GRN model with varying weights, which is used in evolutionary biology. In the model, weight parameters represent the gene interaction strength that may change due to genetic mutations. For a property of interest, we synthesise the constraints over the parameter space that represent the set of GRNs satisfying the property. We experimentally show that our parameter synthesis procedure computes the mutational robustness of GRNs –an important problem of interest in evolutionary biology– more efficiently than the classical simulation method. We specify the property in linear temporal logics. We employ symbolic bounded model checking and SMT solving to compute the space of GRNs that satisfy the property, which amounts to synthesizing a set of linear constraints on the weights.
AU - Giacobbe, Mirco
AU - Guet, Calin C
AU - Gupta, Ashutosh
AU - Henzinger, Thomas A
AU - Paixao, Tiago
AU - Petrov, Tatjana
ID - 1835
TI - Model checking gene regulatory networks
VL - 9035
ER -
TY - JOUR
AB - Huge body of evidences demonstrated that volatile anesthetics affect the hippocampal neurogenesis and neurocognitive functions, and most of them showed impairment at anesthetic dose. Here, we investigated the effect of low dose (1.8%) sevoflurane on hippocampal neurogenesis and dentate gyrus-dependent learning. Neonatal rats at postnatal day 4 to 6 (P4-6) were treated with 1.8% sevoflurane for 6 hours. Neurogenesis was quantified by bromodeoxyuridine labeling and electrophysiology recording. Four and seven weeks after treatment, the Morris water maze and contextual-fear discrimination learning tests were performed to determine the influence on spatial learning and pattern separation. A 6-hour treatment with 1.8% sevoflurane promoted hippocampal neurogenesis and increased the survival of newborn cells and the proportion of immature granular cells in the dentate gyrus of neonatal rats. Sevoflurane-treated rats performed better during the training days of the Morris water maze test and in contextual-fear discrimination learning test. These results suggest that a subanesthetic dose of sevoflurane promotes hippocampal neurogenesis in neonatal rats and facilitates their performance in dentate gyrus-dependent learning tasks.
AU - Chen, Chong
AU - Wang, Chao
AU - Zhao, Xuan
AU - Zhou, Tao
AU - Xu, Dao
AU - Wang, Zhi
AU - Wang, Ying
ID - 1834
IS - 2
JF - ASN Neuro
TI - Low-dose sevoflurane promoteshippocampal neurogenesis and facilitates the development of dentate gyrus-dependent learning in neonatal rats
VL - 7
ER -
TY - CONF
AB - Synthesis of program parts is particularly useful for concurrent systems. However, most approaches do not support common design tasks, like modifying a single process without having to re-synthesize or verify the whole system. Assume-guarantee synthesis (AGS) provides robustness against modifications of system parts, but thus far has been limited to the perfect information setting. This means that local variables cannot be hidden from other processes, which renders synthesis results cumbersome or even impossible to realize.We resolve this shortcoming by defining AGS under partial information. We analyze the complexity and decidability in different settings, showing that the problem has a high worstcase complexity and is undecidable in many interesting cases. Based on these observations, we present a pragmatic algorithm based on bounded synthesis, and demonstrate its practical applicability on several examples.
AU - Bloem, Roderick
AU - Chatterjee, Krishnendu
AU - Jacobs, Swen
AU - Könighofer, Robert
ID - 1838
TI - Assume-guarantee synthesis for concurrent reactive programs with partial information
VL - 9035
ER -
TY - CONF
AB - We present MultiGain, a tool to synthesize strategies for Markov decision processes (MDPs) with multiple mean-payoff objectives. Our models are described in PRISM, and our tool uses the existing interface and simulator of PRISM. Our tool extends PRISM by adding novel algorithms for multiple mean-payoff objectives, and also provides features such as (i) generating strategies and exploring them for simulation, and checking them with respect to other properties; and (ii) generating an approximate Pareto curve for two mean-payoff objectives. In addition, we present a new practical algorithm for the analysis of MDPs with multiple mean-payoff objectives under memoryless strategies.
AU - Brázdil, Tomáš
AU - Chatterjee, Krishnendu
AU - Forejt, Vojtěch
AU - Kučera, Antonín
ID - 1839
TI - Multigain: A controller synthesis tool for MDPs with multiple mean-payoff objectives
VL - 9035
ER -
TY - JOUR
AB - Transition to turbulence in straight pipes occurs in spite of the linear stability of the laminar Hagen-Poiseuille flow if both the amplitude of flow perturbations and the Reynolds number Re exceed a minimum threshold (subcritical transition). As the pipe curvature increases, centrifugal effects become important, modifying the basic flow as well as the most unstable linear modes. If the curvature (tube-to-coiling diameter d/D) is sufficiently large, a Hopf bifurcation (supercritical instability) is encountered before turbulence can be excited (subcritical instability). We trace the instability thresholds in the Re - d/D parameter space in the range 0.01 ≤ d/D\ ≤ 0.1 by means of laser-Doppler velocimetry and determine the point where the subcritical and supercritical instabilities meet. Two different experimental set-ups are used: a closed system where the pipe forms an axisymmetric torus and an open system employing a helical pipe. Implications for the measurement of friction factors in curved pipes are discussed.
AU - Kühnen, Jakob
AU - Braunshier, P
AU - Schwegel, M
AU - Kuhlmann, Hendrik
AU - Hof, Björn
ID - 1837
IS - 5
JF - Journal of Fluid Mechanics
TI - Subcritical versus supercritical transition to turbulence in curved pipes
VL - 770
ER -
TY - JOUR
AB - The ability to escape apoptosis is a hallmark of cancer-initiating cells and a key factor of resistance to oncolytic therapy. Here, we identify FAM96A as a ubiquitous, evolutionarily conserved apoptosome-activating protein and investigate its potential pro-apoptotic tumor suppressor function in gastrointestinal stromal tumors (GISTs). Interaction between FAM96A and apoptotic peptidase activating factor 1 (APAF1) was identified in yeast two-hybrid screen and further studied by deletion mutants, glutathione-S-transferase pull-down, co-immunoprecipitation and immunofluorescence. Effects of FAM96A overexpression and knock-down on apoptosis sensitivity were examined in cancer cells and zebrafish embryos. Expression of FAM96A in GISTs and histogenetically related cells including interstitial cells of Cajal (ICCs), “fibroblast-like cells” (FLCs) and ICC stem cells (ICC-SCs) was investigated by Northern blotting, reverse transcription—polymerase chain reaction, immunohistochemistry and Western immunoblotting. Tumorigenicity of GIST cells and transformed murine ICC-SCs stably transduced to re-express FAM96A was studied by xeno- and allografting into immunocompromised mice. FAM96A was found to bind APAF1 and to enhance the induction of mitochondrial apoptosis. FAM96A protein or mRNA was dramatically reduced or lost in 106 of 108 GIST samples representing three independent patient cohorts. Whereas ICCs, ICC-SCs and FLCs, the presumed normal counterparts of GIST, were found to robustly express FAM96A protein and mRNA, FAM96A expression was much reduced in tumorigenic ICC-SCs. Re-expression of FAM96A in GIST cells and transformed ICC-SCs increased apoptosis sensitivity and diminished tumorigenicity. Our data suggest FAM96A is a novel pro-apoptotic tumor suppressor that is lost during GIST tumorigenesis.
AU - Schwamb, Bettina
AU - Pick, Robert
AU - Fernández, Sara
AU - Völp, Kirsten
AU - Heering, Jan
AU - Dötsch, Volker
AU - Bösser, Susanne
AU - Jung, Jennifer
AU - Beinoravičiute Kellner, Rasa
AU - Wesely, Josephine
AU - Zörnig, Inka
AU - Hammerschmidt, Matthias
AU - Nowak, Matthias
AU - Penzel, Roland
AU - Zatloukal, Kurt
AU - Joos, Stefan
AU - Rieker, Ralf
AU - Agaimy, Abbas
AU - Söder, Stephan
AU - Reid Lombardo, Kmarie
AU - Kendrick, Michael
AU - Bardsley, Michael
AU - Hayashi, Yujiro
AU - Asuzu, David
AU - Syed, Sabriya
AU - Ördög, Tamás
AU - Zörnig, Martin
ID - 1848
IS - 6
JF - International Journal of Cancer
TI - FAM96A is a novel pro-apoptotic tumor suppressor in gastrointestinal stromal tumors
VL - 137
ER -
TY - JOUR
AB - Modal transition systems (MTS) is a well-studied specification formalism of reactive systems supporting a step-wise refinement methodology. Despite its many advantages, the formalism as well as its currently known extensions are incapable of expressing some practically needed aspects in the refinement process like exclusive, conditional and persistent choices. We introduce a new model called parametric modal transition systems (PMTS) together with a general modal refinement notion that overcomes many of the limitations. We investigate the computational complexity of modal and thorough refinement checking on PMTS and its subclasses and provide a direct encoding of the modal refinement problem into quantified Boolean formulae, allowing us to employ state-of-the-art QBF solvers for modal refinement checking. The experiments we report on show that the feasibility of refinement checking is more influenced by the degree of nondeterminism rather than by the syntactic restrictions on the types of formulae allowed in the description of the PMTS.
AU - Beneš, Nikola
AU - Kretinsky, Jan
AU - Larsen, Kim
AU - Möller, Mikael
AU - Sickert, Salomon
AU - Srba, Jiří
ID - 1846
IS - 2-3
JF - Acta Informatica
TI - Refinement checking on parametric modal transition systems
VL - 52
ER -
TY - JOUR
AB - Based on extrapolation from excitatory synapses, it is often assumed that depletion of the releasable pool of synaptic vesicles is the main factor underlying depression at inhibitory synapses. In this issue of Neuron, using subcellular patch-clamp recording from inhibitory presynaptic terminals, Kawaguchi and Sakaba (2015) show that at Purkinje cell-deep cerebellar nuclei neuron synapses, changes in presynaptic action potential waveform substantially contribute to synaptic depression. Based on extrapolation from excitatory synapses, it is often assumed that depletion of the releasable pool of synaptic vesicles is the main factor underlying depression at inhibitory synapses. In this issue of Neuron, using subcellular patch-clamp recording from inhibitory presynaptic terminals, Kawaguchi and Sakaba (2015) show that at Purkinje cell-deep cerebellar nuclei neuron synapses, changes in presynaptic action potential waveform substantially contribute to synaptic depression.
AU - Vandael, David H
AU - Espinoza Martinez, Claudia
AU - Jonas, Peter M
ID - 1845
IS - 6
JF - Neuron
TI - Excitement about inhibitory presynaptic terminals
VL - 85
ER -
TY - JOUR
AB - In this paper, we present a method for reducing a regular, discrete-time Markov chain (DTMC) to another DTMC with a given, typically much smaller number of states. The cost of reduction is defined as the Kullback-Leibler divergence rate between a projection of the original process through a partition function and a DTMC on the correspondingly partitioned state space. Finding the reduced model with minimal cost is computationally expensive, as it requires an exhaustive search among all state space partitions, and an exact evaluation of the reduction cost for each candidate partition. Our approach deals with the latter problem by minimizing an upper bound on the reduction cost instead of minimizing the exact cost. The proposed upper bound is easy to compute and it is tight if the original chain is lumpable with respect to the partition. Then, we express the problem in the form of information bottleneck optimization, and propose using the agglomerative information bottleneck algorithm for searching a suboptimal partition greedily, rather than exhaustively. The theory is illustrated with examples and one application scenario in the context of modeling bio-molecular interactions.
AU - Geiger, Bernhard
AU - Petrov, Tatjana
AU - Kubin, Gernot
AU - Koeppl, Heinz
ID - 1840
IS - 4
JF - IEEE Transactions on Automatic Control
SN - 0018-9286
TI - Optimal Kullback-Leibler aggregation via information bottleneck
VL - 60
ER -
TY - JOUR
AB - We propose a new family of message passing techniques for MAP estimation in graphical models which we call Sequential Reweighted Message Passing (SRMP). Special cases include well-known techniques such as Min-Sum Diffusion (MSD) and a faster Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation is simpler than the original derivation of TRW-S, and does not involve a decomposition into trees. This allows easy generalizations. The new family of algorithms can be viewed as a generalization of TRW-S from pairwise to higher-order graphical models. We test SRMP on several real-world problems with promising results.
AU - Kolmogorov, Vladimir
ID - 1841
IS - 5
JF - IEEE Transactions on Pattern Analysis and Machine Intelligence
TI - A new look at reweighted message passing
VL - 37
ER -
TY - JOUR
AB - Entomopathogenic fungi are potent biocontrol agents that are widely used against insect pests, many of which are social insects. Nevertheless, theoretical investigations of their particular life history are scarce. We develop a model that takes into account the main distinguishing features between traditionally studied diseases and obligate killing pathogens, like the (biocontrol-relevant) insect-pathogenic fungi Metarhizium and Beauveria. First, obligate killing entomopathogenic fungi produce new infectious particles (conidiospores) only after host death and not yet on the living host. Second, the killing rates of entomopathogenic fungi depend strongly on the initial exposure dosage, thus we explicitly consider the pathogen load of individual hosts. Further, we make the model applicable not only to solitary host species, but also to group living species by incorporating social interactions between hosts, like the collective disease defences of insect societies. Our results identify the optimal killing rate for the pathogen that minimises its invasion threshold. Furthermore, we find that the rate of contact between hosts has an ambivalent effect: dense interaction networks between individuals are considered to facilitate disease outbreaks because of increased pathogen transmission. In social insects, this is compensated by their collective disease defences, i.e., social immunity. For the type of pathogens considered here, we show that even without social immunity, high contact rates between live individuals dilute the pathogen in the host colony and hence can reduce individual pathogen loads below disease-causing levels.
AU - Novak, Sebastian
AU - Cremer, Sylvia
ID - 1850
IS - 5
JF - Journal of Theoretical Biology
TI - Fungal disease dynamics in insect societies: Optimal killing rates and the ambivalent effect of high social interaction rates
VL - 372
ER -
TY - JOUR
AB - We consider mating strategies for females who search for males sequentially during a season of limited length. We show that the best strategy rejects a given male type if encountered before a time-threshold but accepts him after. For frequency-independent benefits, we obtain the optimal time-thresholds explicitly for both discrete and continuous distributions of males, and allow for mistakes being made in assessing the correct male type. When the benefits are indirect (genes for the offspring) and the population is under frequency-dependent ecological selection, the benefits depend on the mating strategy of other females as well. This case is particularly relevant to speciation models that seek to explore the stability of reproductive isolation by assortative mating under frequency-dependent ecological selection. We show that the indirect benefits are to be quantified by the reproductive values of couples, and describe how the evolutionarily stable time-thresholds can be found. We conclude with an example based on the Levene model, in which we analyze the evolutionarily stable assortative mating strategies and the strength of reproductive isolation provided by them.
AU - Priklopil, Tadeas
AU - Kisdi, Eva
AU - Gyllenberg, Mats
ID - 1851
IS - 4
JF - Evolution
SN - 0014-3820
TI - Evolutionarily stable mating decisions for sequentially searching females and the stability of reproductive isolation by assortative mating
VL - 69
ER -
TY - CONF
AB - Structural support vector machines (SSVMs) are amongst the best performing models for structured computer vision tasks, such as semantic image segmentation or human pose estimation. Training SSVMs, however, is computationally costly, because it requires repeated calls to a structured prediction subroutine (called \emph{max-oracle}), which has to solve an optimization problem itself, e.g. a graph cut.
In this work, we introduce a new algorithm for SSVM training that is more efficient than earlier techniques when the max-oracle is computationally expensive, as it is frequently the case in computer vision tasks. The main idea is to (i) combine the recent stochastic Block-Coordinate Frank-Wolfe algorithm with efficient hyperplane caching, and (ii) use an automatic selection rule for deciding whether to call the exact max-oracle or to rely on an approximate one based on the cached hyperplanes.
We show experimentally that this strategy leads to faster convergence to the optimum with respect to the number of requires oracle calls, and that this translates into faster convergence with respect to the total runtime when the max-oracle is slow compared to the other steps of the algorithm.
AU - Shah, Neel
AU - Kolmogorov, Vladimir
AU - Lampert, Christoph
ID - 1859
TI - A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle
ER -
TY - CONF
AB - Classifiers for object categorization are usually evaluated by their accuracy on a set of i.i.d. test examples. This provides us with an estimate of the expected error when applying the classifiers to a single new image. In real application, however, classifiers are rarely only used for a single image and then discarded. Instead, they are applied sequentially to many images, and these are typically not i.i.d. samples from a fixed data distribution, but they carry dependencies and their class distribution varies over time. In this work, we argue that the phenomenon of correlated data at prediction time is not a nuisance, but a blessing in disguise. We describe a probabilistic method for adapting classifiers at prediction time without having to retrain them. We also introduce a framework for creating realistically distributed image sequences, which offers a way to benchmark classifier adaptation methods, such as the one we propose. Experiments on the ILSVRC2010 and ILSVRC2012 datasets show that adapting object classification systems at prediction time can significantly reduce their error rate, even with no additional human feedback.
AU - Royer, Amélie
AU - Lampert, Christoph
ID - 1860
TI - Classifier adaptation at prediction time
ER -
TY - CONF
AB - We study the problem of predicting the future, though only in the probabilistic sense of estimating a future state of a time-varying probability distribution. This is not only an interesting academic problem, but solving this extrapolation problem also has many practical application, e.g. for training classifiers that have to operate under time-varying conditions. Our main contribution is a method for predicting the next step of the time-varying distribution from a given sequence of sample sets from earlier time steps. For this we rely on two recent machine learning techniques: embedding probability distributions into a reproducing kernel Hilbert space, and learning operators by vector-valued regression. We illustrate the working principles and the practical usefulness of our method by experiments on synthetic and real data. We also highlight an exemplary application: training a classifier in a domain adaptation setting without having access to examples from the test time distribution at training time.
AU - Lampert, Christoph
ID - 1858
TI - Predicting the future behavior of a time-varying probability distribution
ER -
TY - CONF
AB - Sharing information between multiple tasks enables algorithms to achieve good generalization performance even from small amounts of training data. However, in a realistic scenario of multi-task learning not all tasks are equally related to each other, hence it could be advantageous to transfer information only between the most related tasks. In this work we propose an approach that processes multiple tasks in a sequence with sharing between subsequent tasks instead of solving all tasks jointly. Subsequently, we address the question of curriculum learning of tasks, i.e. finding the best order of tasks to be learned. Our approach is based on a generalization bound criterion for choosing the task order that optimizes the average expected classification performance over all tasks. Our experimental results show that learning multiple related tasks sequentially can be more effective than learning them jointly, the order in which tasks are being solved affects the overall performance, and that our model is able to automatically discover the favourable order of tasks.
AU - Pentina, Anastasia
AU - Sharmanska, Viktoriia
AU - Lampert, Christoph
ID - 1857
TI - Curriculum learning of multiple tasks
ER -
TY - JOUR
AB - The Altshuler–Shklovskii formulas (Altshuler and Shklovskii, BZh Eksp Teor Fiz 91:200, 1986) predict, for any disordered quantum system in the diffusive regime, a universal power law behaviour for the correlation functions of the mesoscopic eigenvalue density. In this paper and its companion (Erdős and Knowles, The Altshuler–Shklovskii formulas for random band matrices I: the unimodular case, 2013), we prove these formulas for random band matrices. In (Erdős and Knowles, The Altshuler–Shklovskii formulas for random band matrices I: the unimodular case, 2013) we introduced a diagrammatic approach and presented robust estimates on general diagrams under certain simplifying assumptions. In this paper, we remove these assumptions by giving a general estimate of the subleading diagrams. We also give a precise analysis of the leading diagrams which give rise to the Altschuler–Shklovskii power laws. Moreover, we introduce a family of general random band matrices which interpolates between real symmetric (β = 1) and complex Hermitian (β = 2) models, and track the transition for the mesoscopic density–density correlation. Finally, we address the higher-order correlation functions by proving that they behave asymptotically according to a Gaussian process whose covariance is given by the Altshuler–Shklovskii formulas.
AU - Erdös, László
AU - Knowles, Antti
ID - 1864
IS - 3
JF - Annales Henri Poincare
TI - The Altshuler–Shklovskii formulas for random band matrices II: The general case
VL - 16
ER -
TY - JOUR
AB - The plant hormone auxin is a key regulator of plant growth and development. Differences in auxin distribution within tissues are mediated by the polar auxin transport machinery, and cellular auxin responses occur depending on changes in cellular auxin levels. Multiple receptor systems at the cell surface and in the interior operate to sense and interpret fluctuations in auxin distribution that occur during plant development. Until now, three proteins or protein complexes that can bind auxin have been identified. SCFTIR1 [a SKP1-cullin-1-F-box complex that contains transport inhibitor response 1 (TIR1) as the F-box protein] and S-phase-kinaseassociated protein 2 (SKP2) localize to the nucleus, whereas auxinbinding protein 1 (ABP1), predominantly associates with the endoplasmic reticulum and cell surface. In this Cell Science at a Glance article, we summarize recent discoveries in the field of auxin transport and signaling that have led to the identification of new components of these pathways, as well as their mutual interaction.
AU - Grones, Peter
AU - Friml, Jirí
ID - 1871
IS - 1
JF - Journal of Cell Science
TI - Auxin transporters and binding proteins at a glance
VL - 128
ER -
TY - JOUR
AB - We consider partially observable Markov decision processes (POMDPs) with limit-average payoff, where a reward value in the interval [0,1] is associated with every transition, and the payoff of an infinite path is the long-run average of the rewards. We consider two types of path constraints: (i) a quantitative constraint defines the set of paths where the payoff is at least a given threshold λ1ε(0,1]; and (ii) a qualitative constraint which is a special case of the quantitative constraint with λ1=1. We consider the computation of the almost-sure winning set, where the controller needs to ensure that the path constraint is satisfied with probability 1. Our main results for qualitative path constraints are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative path constraints we show that the problem of deciding the existence of a finite-memory controller is undecidable. We also present a prototype implementation of our EXPTIME algorithm and experimental results on several examples.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
ID - 1873
JF - Artificial Intelligence
TI - POMDPs under probabilistic semantics
VL - 221
ER -
TY - JOUR
AB - When electron microscopy (EM) was introduced in the 1930s it gave scientists their first look into the nanoworld of cells. Over the last 80 years EM has vastly increased our understanding of the complex cellular structures that underlie the diverse functions that cells need to maintain life. One drawback that has been difficult to overcome was the inherent lack of volume information, mainly due to the limit on the thickness of sections that could be viewed in a transmission electron microscope (TEM). For many years scientists struggled to achieve three-dimensional (3D) EM using serial section reconstructions, TEM tomography, and scanning EM (SEM) techniques such as freeze-fracture. Although each technique yielded some special information, they required a significant amount of time and specialist expertise to obtain even a very small 3D EM dataset. Almost 20 years ago scientists began to exploit SEMs to image blocks of embedded tissues and perform serial sectioning of these tissues inside the SEM chamber. Using first focused ion beams (FIB) and subsequently robotic ultramicrotomes (serial block-face, SBF-SEM) microscopists were able to collect large volumes of 3D EM information at resolutions that could address many important biological questions, and do so in an efficient manner. We present here some examples of 3D EM taken from the many diverse specimens that have been imaged in our core facility. We propose that the next major step forward will be to efficiently correlate functional information obtained using light microscopy (LM) with 3D EM datasets to more completely investigate the important links between cell structures and their functions.
AU - Kremer, A
AU - Lippens, Stefaan
AU - Bartunkova, Sonia
AU - Asselbergh, Bob
AU - Blanpain, Cendric
AU - Fendrych, Matyas
AU - Goossens, A
AU - Holt, Matthew
AU - Janssens, Sophie
AU - Krols, Michiel
AU - Larsimont, Jean
AU - Mc Guire, Conor
AU - Nowack, Moritz
AU - Saelens, Xavier
AU - Schertel, Andreas
AU - Schepens, B
AU - Slezak, M
AU - Timmerman, Vincent
AU - Theunis, Clara
AU - Van Brempt, Ronald
AU - Visser, Y
AU - Guérin, Christophe
ID - 1879
IS - 2
JF - Journal of Microscopy
TI - Developing 3D SEM in a broad biological context
VL - 259
ER -
TY - JOUR
AB - We investigate the relation between Bose-Einstein condensation (BEC) and superfluidity in the ground state of a one-dimensional model of interacting bosons in a strong random potential. We prove rigorously that in a certain parameter regime the superfluid fraction can be arbitrarily small while complete BEC prevails. In another regime there is both complete BEC and complete superfluidity, despite the strong disorder
AU - Könenberg, Martin
AU - Moser, Thomas
AU - Seiringer, Robert
AU - Yngvason, Jakob
ID - 1880
JF - New Journal of Physics
TI - Superfluid behavior of a Bose-Einstein condensate in a random potential
VL - 17
ER -
TY - CONF
AB - We provide a framework for compositional and iterative design and verification of systems with quantitative information, such as rewards, time or energy. It is based on disjunctive modal transition systems where we allow actions to bear various types of quantitative information. Throughout the design process the actions can be further refined and the information made more precise. We show how to compute the results of standard operations on the systems, including the quotient (residual), which has not been previously considered for quantitative non-deterministic systems. Our quantitative framework has close connections to the modal nu-calculus and is compositional with respect to general notions of distances between systems and the standard operations.
AU - Fahrenberg, Uli
AU - Kretinsky, Jan
AU - Legay, Axel
AU - Traonouez, Louis
ID - 1882
TI - Compositionality for quantitative specifications
VL - 8997
ER -
TY - JOUR
AB - We introduce a one-parametric family of tree growth models, in which branching probabilities decrease with branch age τ as τ-α. Depending on the exponent α, the scaling of tree depth with tree size n displays a transition between the logarithmic scaling of random trees and an algebraic growth. At the transition (α=1) tree depth grows as (logn)2. This anomalous scaling is in good agreement with the trend observed in evolution of biological species, thus providing a theoretical support for age-dependent speciation and associating it to the occurrence of a critical point.
AU - Keller-Schmidt, Stephanie
AU - Tugrul, Murat
AU - Eguíluz, Víctor
AU - Hernandez Garcia, Emilio
AU - Klemm, Konstantin
ID - 1883
IS - 2
JF - Physical Review E Statistical Nonlinear and Soft Matter Physics
TI - Anomalous scaling in an age-dependent branching model
VL - 91
ER -
TY - JOUR
AB - The concept of positional information is central to our understanding of how cells determine their location in a multicellular structure and thereby their developmental fates. Nevertheless, positional information has neither been defined mathematically nor quantified in a principled way. Here we provide an information-theoretic definition in the context of developmental gene expression patterns and examine the features of expression patterns that affect positional information quantitatively. We connect positional information with the concept of positional error and develop tools to directly measure information and error from experimental data. We illustrate our framework for the case of gap gene expression patterns in the early Drosophila embryo and show how information that is distributed among only four genes is sufficient to determine developmental fates with nearly single-cell resolution. Our approach can be generalized to a variety of different model systems; procedures and examples are discussed in detail.
AU - Tkacik, Gasper
AU - Dubuis, Julien
AU - Petkova, Mariela
AU - Gregor, Thomas
ID - 1885
IS - 1
JF - Genetics
TI - Positional information, positional error, and readout precision in morphogenesis: A mathematical framework
VL - 199
ER -
TY - JOUR
AB - We typically think of cells as responding to external signals independently by regulating their gene expression levels, yet they often locally exchange information and coordinate. Can such spatial coupling be of benefit for conveying signals subject to gene regulatory noise? Here we extend our information-theoretic framework for gene regulation to spatially extended systems. As an example, we consider a lattice of nuclei responding to a concentration field of a transcriptional regulator (the "input") by expressing a single diffusible target gene. When input concentrations are low, diffusive coupling markedly improves information transmission; optimal gene activation functions also systematically change. A qualitatively new regulatory strategy emerges where individual cells respond to the input in a nearly step-like fashion that is subsequently averaged out by strong diffusion. While motivated by early patterning events in the Drosophila embryo, our framework is generically applicable to spatially coupled stochastic gene expression models.
AU - Sokolowski, Thomas R
AU - Tkacik, Gasper
ID - 1940
IS - 6
JF - Physical Review E Statistical Nonlinear and Soft Matter Physics
TI - Optimizing information flow in small genetic networks. IV. Spatial coupling
VL - 91
ER -
TY - CONF
AB - We present a method and a tool for generating succinct representations of sets of concurrent traces. We focus on trace sets that contain all correct or all incorrect permutations of events from a given trace. We represent trace sets as HB-Formulas that are Boolean combinations of happens-before constraints between events. To generate a representation of incorrect interleavings, our method iteratively explores interleavings that violate the specification and gathers generalizations of the discovered interleavings into an HB-Formula; its complement yields a representation of correct interleavings.
We claim that our trace set representations can drive diverse verification, fault localization, repair, and synthesis techniques for concurrent programs. We demonstrate this by using our tool in three case studies involving synchronization synthesis, bug summarization, and abstraction refinement based verification. In each case study, our initial experimental results have been promising.
In the first case study, we present an algorithm for inferring missing synchronization from an HB-Formula representing correct interleavings of a given trace. The algorithm applies rules to rewrite specific patterns in the HB-Formula into locks, barriers, and wait-notify constructs. In the second case study, we use an HB-Formula representing incorrect interleavings for bug summarization. While the HB-Formula itself is a concise counterexample summary, we present additional inference rules to help identify specific concurrency bugs such as data races, define-use order violations, and two-stage access bugs. In the final case study, we present a novel predicate learning procedure that uses HB-Formulas representing abstract counterexamples to accelerate counterexample-guided abstraction refinement (CEGAR). In each iteration of the CEGAR loop, the procedure refines the abstraction to eliminate multiple spurious abstract counterexamples drawn from the HB-Formula.
AU - Gupta, Ashutosh
AU - Henzinger, Thomas A
AU - Radhakrishna, Arjun
AU - Samanta, Roopsha
AU - Tarrach, Thorsten
ID - 1992
SN - 978-1-4503-3300-9
TI - Succinct representation of concurrent trace sets
ER -
TY - JOUR
AB - We prove that the three-state toric homogeneous Markov chain model has Markov degree two. In algebraic terminology this means, that a certain class of toric ideals is generated by quadratic binomials. This was conjectured by Haws, Martin del Campo, Takemura and Yoshida, who proved that they are generated by degree six binomials.
AU - Noren, Patrik
ID - 1997
IS - May-June
JF - Journal of Symbolic Computation
TI - The three-state toric homogeneous Markov chain model has Markov degree two
VL - 68/Part 2
ER -
TY - JOUR
AB - The paper describes a generalized iterative proportional fitting procedure that can be used for maximum likelihood estimation in a special class of the general log-linear model. The models in this class, called relational, apply to multivariate discrete sample spaces that do not necessarily have a Cartesian product structure and may not contain an overall effect. When applied to the cell probabilities, the models without the overall effect are curved exponential families and the values of the sufficient statistics are reproduced by the MLE only up to a constant of proportionality. The paper shows that Iterative Proportional Fitting, Generalized Iterative Scaling, and Improved Iterative Scaling fail to work for such models. The algorithm proposed here is based on iterated Bregman projections. As a by-product, estimates of the multiplicative parameters are also obtained. An implementation of the algorithm is available as an R-package.
AU - Klimova, Anna
AU - Rudas, Tamás
ID - 2008
IS - 3
JF - Scandinavian Journal of Statistics
TI - Iterative scaling in curved exponential families
VL - 42
ER -
TY - JOUR
AB - The monotone secant conjecture posits a rich class of polynomial systems, all of whose solutions are real. These systems come from the Schubert calculus on flag manifolds, and the monotone secant conjecture is a compelling generalization of the Shapiro conjecture for Grassmannians (Theorem of Mukhin, Tarasov, and Varchenko). We present some theoretical evidence for this conjecture, as well as computational evidence obtained by 1.9 teraHertz-years of computing, and we discuss some of the phenomena we observed in our data.
AU - Hein, Nicolas
AU - Hillar, Christopher
AU - Martin Del Campo Sanchez, Abraham
AU - Sottile, Frank
AU - Teitler, Zach
ID - 2006
IS - 3
JF - Experimental Mathematics
TI - The monotone secant conjecture in the real Schubert calculus
VL - 24
ER -
TY - JOUR
AB - The concepts of faithfulness and strong-faithfulness are important for statistical learning of graphical models. Graphs are not sufficient for describing the association structure of a discrete distribution. Hypergraphs representing hierarchical log-linear models are considered instead, and the concept of parametric (strong-) faithfulness with respect to a hypergraph is introduced. Strong-faithfulness ensures the existence of uniformly consistent parameter estimators and enables building uniformly consistent procedures for a hypergraph search. The strength of association in a discrete distribution can be quantified with various measures, leading to different concepts of strong-faithfulness. Lower and upper bounds for the proportions of distributions that do not satisfy strong-faithfulness are computed for different parameterizations and measures of association.
AU - Klimova, Anna
AU - Uhler, Caroline
AU - Rudas, Tamás
ID - 2014
IS - 7
JF - Computational Statistics & Data Analysis
TI - Faithfulness and learning hypergraphs from discrete distributions
VL - 87
ER -
TY - JOUR
AB - Small GTP-binding proteins of the Ras superfamily play diverse roles in intracellular trafficking. Among them, the Rab, Arf, and Rho families function in successive steps of vesicle transport, in forming vesicles from donor membranes, directing vesicle trafficking toward target membranes and docking vesicles onto target membranes. These proteins act as molecular switches that are controlled by a cycle of GTP binding and hydrolysis regulated by guanine nucleotide exchange factors (GEFs) and GTPase-activating proteins (GAPs). In this study we explored the role of GAPs in the regulation of the endocytic pathway using fluorescently labeled yeast mating pheromone α-factor. Among 25 non-essential GAP mutants, we found that deletion of the GLO3 gene, encoding Arf-GAP protein, caused defective internalization of fluorescently labeled α-factor. Quantitative analysis revealed that glo3Δ cells show defective α-factor binding to the cell surface. Interestingly, Ste2p, the α-factor receptor, was mis-localized from the plasma membrane to the vacuole in glo3Δ cells. Domain deletion mutants of Glo3p revealed that a GAP-independent function, as well as the GAP activity, of Glo3p is important for both α-factor binding and Ste2p localization at the cell surface. Additionally, we found that deletion of the GLO3 gene affects the size and number of Arf1p-residing Golgi compartments and causes a defect in transport from the TGN to the plasma membrane. Furthermore, we demonstrated that glo3Δ cells were defective in the late endosome-to-TGN transport pathway, but not in the early endosome-to-TGN transport pathway. These findings suggest novel roles for Arf-GAP Glo3p in endocytic recycling of cell surface proteins.
AU - Kawada, Daiki
AU - Kobayashi, Hiromu
AU - Tomita, Tsuyoshi
AU - Nakata, Eisuke
AU - Nagano, Makoto
AU - Siekhaus, Daria E
AU - Toshima, Junko
AU - Toshimaa, Jiro
ID - 2025
IS - 1
JF - Biochimica et Biophysica Acta - Molecular Cell Research
TI - The yeast Arf-GAP Glo3p is required for the endocytic recycling of cell surface proteins
VL - 1853
ER -
TY - JOUR
AB - A hybrid-parallel direct-numerical-simulation method with application to turbulent Taylor-Couette flow is presented. The Navier-Stokes equations are discretized in cylindrical coordinates with the spectral Fourier-Galerkin method in the axial and azimuthal directions, and high-order finite differences in the radial direction. Time is advanced by a second-order, semi-implicit projection scheme, which requires the solution of five Helmholtz/Poisson equations, avoids staggered grids and renders very small slip velocities. Nonlinear terms are evaluated with the pseudospectral method. The code is parallelized using a hybrid MPI-OpenMP strategy, which, compared with a flat MPI parallelization, is simpler to implement, allows to reduce inter-node communications and MPI overhead that become relevant at high processor-core counts, and helps to contain the memory footprint. A strong scaling study shows that the hybrid code maintains scalability up to more than 20,000 processor cores and thus allows to perform simulations at higher resolutions than previously feasible. In particular, it opens up the possibility to simulate turbulent Taylor-Couette flows at Reynolds numbers up to O(105). This enables to probe hydrodynamic turbulence in Keplerian flows in experimentally relevant regimes.
AU - Shi, Liang
AU - Rampp, Markus
AU - Hof, Björn
AU - Avila, Marc
ID - 2030
IS - 1
JF - Computers and Fluids
TI - A hybrid MPI-OpenMP parallel implementation for pseudospectral simulations with application to Taylor-Couette flow
VL - 106
ER -
TY - JOUR
AB - Considering a continuous self-map and the induced endomorphism on homology, we study the eigenvalues and eigenspaces of the latter. Taking a filtration of representations, we define the persistence of the eigenspaces, effectively introducing a hierarchical organization of the map. The algorithm that computes this information for a finite sample is proved to be stable, and to give the correct answer for a sufficiently dense sample. Results computed with an implementation of the algorithm provide evidence of its practical utility.
AU - Edelsbrunner, Herbert
AU - Jablonski, Grzegorz
AU - Mrozek, Marian
ID - 2035
IS - 5
JF - Foundations of Computational Mathematics
TI - The persistent homology of a self-map
VL - 15
ER -
TY - JOUR
AB - Opacity is a generic security property, that has been defined on (non-probabilistic) transition systems and later on Markov chains with labels. For a secret predicate, given as a subset of runs, and a function describing the view of an external observer, the value of interest for opacity is a measure of the set of runs disclosing the secret. We extend this definition to the richer framework of Markov decision processes, where non-deterministicchoice is combined with probabilistic transitions, and we study related decidability problems with partial or complete observation hypotheses for the schedulers. We prove that all questions are decidable with complete observation and ω-regular secrets. With partial observation, we prove that all quantitative questions are undecidable but the question whether a system is almost surely non-opaquebecomes decidable for a restricted class of ω-regular secrets, as well as for all ω-regular secrets under finite-memory schedulers.
AU - Bérard, Béatrice
AU - Chatterjee, Krishnendu
AU - Sznajder, Nathalie
ID - 2034
IS - 1
JF - Information Processing Letters
TI - Probabilistic opacity for Markov decision processes
VL - 115
ER -
TY - JOUR
AB - We study the spectrum of a large system of N identical bosons interacting via a two-body potential with strength 1/N. In this mean-field regime, Bogoliubov's theory predicts that the spectrum of the N-particle Hamiltonian can be approximated by that of an effective quadratic Hamiltonian acting on Fock space, which describes the fluctuations around a condensed state. Recently, Bogoliubov's theory has been justified rigorously in the case that the low-energy eigenvectors of the N-particle Hamiltonian display complete condensation in the unique minimizer of the corresponding Hartree functional. In this paper, we shall justify Bogoliubov's theory for the high-energy part of the spectrum of the N-particle Hamiltonian corresponding to (non-linear) excited states of the Hartree functional. Moreover, we shall extend the existing results on the excitation spectrum to the case of non-uniqueness and/or degeneracy of the Hartree minimizer. In particular, the latter covers the case of rotating Bose gases, when the rotation speed is large enough to break the symmetry and to produce multiple quantized vortices in the Hartree minimizer.
AU - Nam, Phan
AU - Seiringer, Robert
ID - 2085
IS - 2
JF - Archive for Rational Mechanics and Analysis
TI - Collective excitations of Bose gases in the mean-field regime
VL - 215
ER -
TY - JOUR
AB - We consider the spectral statistics of large random band matrices on mesoscopic energy scales. We show that the correlation function of the local eigenvalue density exhibits a universal power law behaviour that differs from the Wigner-Dyson- Mehta statistics. This law had been predicted in the physics literature by Altshuler and Shklovskii in (Zh Eksp Teor Fiz (Sov Phys JETP) 91(64):220(127), 1986); it describes the correlations of the eigenvalue density in general metallic sampleswith weak disorder. Our result rigorously establishes the Altshuler-Shklovskii formulas for band matrices. In two dimensions, where the leading term vanishes owing to an algebraic cancellation, we identify the first non-vanishing term and show that it differs substantially from the prediction of Kravtsov and Lerner in (Phys Rev Lett 74:2563-2566, 1995). The proof is given in the current paper and its companion (Ann. H. Poincaré. arXiv:1309.5107, 2014).
AU - Erdös, László
AU - Knowles, Antti
ID - 2166
IS - 3
JF - Communications in Mathematical Physics
TI - The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case
VL - 333
ER -
TY - JOUR
AB - Linearizability of concurrent data structures is usually proved by monolithic simulation arguments relying on the identification of the so-called linearization points. Regrettably, such proofs, whether manual or automatic, are often complicated and scale poorly to advanced non-blocking concurrency patterns, such as helping and optimistic updates. In response, we propose a more modular way of checking linearizability of concurrent queue algorithms that does not involve identifying linearization points. We reduce the task of proving linearizability with respect to the queue specification to establishing four basic properties, each of which can be proved independently by simpler arguments. As a demonstration of our approach, we verify the Herlihy and Wing queue, an algorithm that is challenging to verify by a simulation proof.
AU - Chakraborty, Soham
AU - Henzinger, Thomas A
AU - Sezgin, Ali
AU - Vafeiadis, Viktor
ID - 1832
IS - 1
JF - Logical Methods in Computer Science
TI - Aspect-oriented linearizability proofs
VL - 11
ER -
TY - JOUR
AB - A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. Finite-valued constraint languages contain functions that take on rational costs and general-valued constraint languages contain functions that take on rational or infinite costs. An instance of the problem is specified by a sum of functions from the language with the goal to minimise the sum. This framework includes and generalises well-studied constraint satisfaction problems (CSPs) and maximum constraint satisfaction problems (Max-CSPs).
Our main result is a precise algebraic characterisation of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation (BLP). For a general-valued constraint language Γ, BLP is a decision procedure for Γ if and only if Γ admits a symmetric fractional polymorphism of every arity. For a finite-valued constraint language Γ, BLP is a decision procedure if and only if Γ admits a symmetric fractional polymorphism of some arity, or equivalently, if Γ admits a symmetric fractional polymorphism of arity 2.
Using these results, we obtain tractability of several novel and previously widely-open classes of VCSPs, including problems over valued constraint languages that are: (1) submodular on arbitrary lattices; (2) bisubmodular (also known as k-submodular) on arbitrary finite domains; (3) weakly (and hence strongly) tree-submodular on arbitrary trees.
AU - Kolmogorov, Vladimir
AU - Thapper, Johan
AU - Živný, Stanislav
ID - 2271
IS - 1
JF - SIAM Journal on Computing
TI - The power of linear programming for general-valued CSPs
VL - 44
ER -
TY - JOUR
AB - We consider Markov decision processes (MDPs) with specifications given as Büchi (liveness) objectives, and examine the problem of computing the set of almost-sure winning vertices such that the objective can be ensured with probability 1 from these vertices. We study for the first time the average-case complexity of the classical algorithm for computing the set of almost-sure winning vertices for MDPs with Büchi objectives. Our contributions are as follows: First, we show that for MDPs with constant out-degree the expected number of iterations is at most logarithmic and the average-case running time is linear (as compared to the worst-case linear number of iterations and quadratic time complexity). Second, for the average-case analysis over all MDPs we show that the expected number of iterations is constant and the average-case running time is linear (again as compared to the worst-case linear number of iterations and quadratic time complexity). Finally we also show that when all MDPs are equally likely, the probability that the classical algorithm requires more than a constant number of iterations is exponentially small.
AU - Chatterjee, Krishnendu
AU - Joglekar, Manas
AU - Shah, Nisarg
ID - 1598
IS - 3
JF - Theoretical Computer Science
TI - Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives
VL - 573
ER -
TY - JOUR
AB - 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.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Gimbert, Hugo
AU - Henzinger, Thomas A
ID - 1731
IS - 12
JF - Information and Computation
TI - Randomness for free
VL - 245
ER -
TY - JOUR
AB - High-throughput live-cell screens are intricate elements of systems biology studies and drug discovery pipelines. Here, we demonstrate an optogenetics-assisted method that avoids the need for chemical activators and reporters, reduces the number of operational steps and increases information content in a cell-based small-molecule screen against human protein kinases, including an orphan receptor tyrosine kinase. This blueprint for all-optical screening can be adapted to many drug targets and cellular processes.
AU - Inglés Prieto, Álvaro
AU - Gschaider-Reichhart, Eva
AU - Muellner, Markus
AU - Nowak, Matthias
AU - Nijman, Sebastian
AU - Grusch, Michael
AU - Janovjak, Harald L
ID - 1678
IS - 12
JF - Nature Chemical Biology
TI - Light-assisted small-molecule screening against protein kinases
VL - 11
ER -
TY - CONF
AB - We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b,d) such that the following holds. If F is a finite family of subsets of R^d such that the ith reduced Betti number (with Z_2 coefficients in singular homology) of the intersection of any proper subfamily G of F is at most b for every non-negative integer i less or equal to (d-1)/2, then F has Helly number at most h(b,d). These topological conditions are sharp: not controlling any of these first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map from C_*(K) to C_*(R^d). Both techniques are of independent interest.
AU - Goaoc, Xavier
AU - Paták, Pavel
AU - Patakova, Zuzana
AU - Tancer, Martin
AU - Wagner, Uli
ID - 1512
TI - Bounding Helly numbers via Betti numbers
VL - 34
ER -
TY - JOUR
AB - The traditional synthesis question given a specification asks for the automatic construction of a system that satisfies the specification, whereas often there exists a preference order among the different systems that satisfy the given specification. Under a probabilistic assumption about the possible inputs, such a preference order is naturally expressed by a weighted automaton, which assigns to each word a value, such that a system is preferred if it generates a higher expected value. We solve the following optimal synthesis problem: given an omega-regular specification, a Markov chain that describes the distribution of inputs, and a weighted automaton that measures how well a system satisfies the given specification under the input assumption, synthesize a system that optimizes the measured value. For safety specifications and quantitative measures that are defined by mean-payoff automata, the optimal synthesis problem reduces to finding a strategy in a Markov decision process (MDP) that is optimal for a long-run average reward objective, which can be achieved in polynomial time. For general omega-regular specifications along with mean-payoff automata, the solution rests on a new, polynomial-time algorithm for computing optimal strategies in MDPs with mean-payoff parity objectives. Our algorithm constructs optimal strategies that consist of two memoryless strategies and a counter. The counter is in general not bounded. To obtain a finite-state system, we show how to construct an ε-optimal strategy with a bounded counter, for all ε > 0. Furthermore, we show how to decide in polynomial time if it is possible to construct an optimal finite-state system (i.e., a system without a counter) for a given specification. We have implemented our approach and the underlying algorithms in a tool that takes qualitative and quantitative specifications and automatically constructs a system that satisfies the qualitative specification and optimizes the quantitative specification, if such a system exists. We present some experimental results showing optimal systems that were automatically generated in this way.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Jobstmann, Barbara
AU - Singh, Rohit
ID - 1856
IS - 1
JF - Journal of the ACM
TI - Measuring and synthesizing systems in probabilistic environments
VL - 62
ER -
TY - CONF
AB - The computation of the winning set for one-pair Streett objectives and for k-pair Streett objectives in (standard) graphs as well as in game graphs are central problems in computer-aided verification, with application to the verification of closed systems with strong fairness conditions, the verification of open systems, checking interface compatibility, well-formed ness of specifications, and the synthesis of reactive systems. We give faster algorithms for the computation of the winning set for (1) one-pair Streett objectives (aka parity-3 problem) in game graphs and (2) for k-pair Streett objectives in graphs. For both problems this represents the first improvement in asymptotic running time in 15 years.
AU - Chatterjee, Krishnendu
AU - Henzinger, Monika H
AU - Loitzenbauer, Veronika
ID - 1661
T2 - Proceedings - Symposium on Logic in Computer Science
TI - Improved algorithms for one-pair and k-pair Streett objectives
VL - 2015-July
ER -
TY - JOUR
AB - We prove that nonlinear Gibbs measures can be obtained from the corresponding many-body, grand-canonical, quantum Gibbs states, in a mean-field limit where the temperature T diverges and the interaction strength behaves as 1/T. We proceed by characterizing the interacting Gibbs state as minimizing a functional counting the free-energy relatively to the non-interacting case. We then perform an infinite-dimensional analogue of phase-space semiclassical analysis, using fine properties of the quantum relative entropy, the link between quantum de Finetti measures and upper/lower symbols in a coherent state basis, as well as Berezin-Lieb type inequalities. Our results cover the measure built on the defocusing nonlinear Schrödinger functional on a finite interval, as well as smoother interactions in dimensions d 2.
AU - Lewin, Mathieu
AU - Phan Thanh, Nam
AU - Rougerie, Nicolas
ID - 473
JF - Journal de l'Ecole Polytechnique - Mathematiques
TI - Derivation of nonlinear gibbs measures from many-body quantum mechanics
VL - 2
ER -
TY - JOUR
AB - We consider two-player games played on weighted directed graphs with mean-payoff and total-payoff objectives, two classical quantitative objectives. While for single-dimensional games the complexity and memory bounds for both objectives coincide, we show that in contrast to multi-dimensional mean-payoff games that are known to be coNP-complete, multi-dimensional total-payoff games are undecidable. We introduce conservative approximations of these objectives, where the payoff is considered over a local finite window sliding along a play, instead of the whole play. For single dimension, we show that (i) if the window size is polynomial, deciding the winner takes polynomial time, and (ii) the existence of a bounded window can be decided in NP ∩ coNP, and is at least as hard as solving mean-payoff games. For multiple dimensions, we show that (i) the problem with fixed window size is EXPTIME-complete, and (ii) there is no primitive-recursive algorithm to decide the existence of a bounded window.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Randour, Mickael
AU - Raskin, Jean
ID - 523
IS - 6
JF - Information and Computation
TI - Looking at mean-payoff and total-payoff through windows
VL - 242
ER -
TY - JOUR
AB - We consider concurrent games played by two players on a finite-state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study the most fundamental objective for concurrent games, namely, mean-payoff or limit-average objective, where a reward is associated to each transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite (i.e., the games are zero-sum). The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it; or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Almost-sure winning with qualitative constraint exactly corresponds to the question of whether there exists a strategy to ensure that the payoff is the maximal reward of the game. Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show that for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies, or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of the algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imply a solution to a long-standing open problem (of solving the value problem of turn-based deterministic mean-payoff games) that is not known to be solvable in polynomial time.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
ID - 524
IS - 6
JF - Information and Computation
TI - Qualitative analysis of concurrent mean payoff games
VL - 242
ER -
TY - CONF
AB - Simple board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in the development of mathematical and logical skills, but also in the emotional and social development. In this paper, we address the problem of generating targeted starting positions for such games. This can facilitate new approaches for bringing novice players to mastery, and also leads to discovery of interesting game variants. We present an approach that generates starting states of varying hardness levels for player 1 in a two-player board game, given rules of the board game, the desired number of steps required for player 1 to win, and the expertise levels of the two players. Our approach leverages symbolic methods and iterative simulation to efficiently search the extremely large state space. We present experimental results that include discovery of states of varying hardness levels for several simple grid-based board games. The presence of such states for standard game variants like 4×4 Tic-Tac-Toe opens up new games to be played that have never been played as the default start state is heavily biased.
AU - Ahmed, Umair
AU - Chatterjee, Krishnendu
AU - Gulwani, Sumit
ID - 1481
T2 - Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence
TI - Automatic generation of alternative starting positions for simple traditional board games
VL - 2
ER -
TY - CONF
AB - 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.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Gupta, Raghav
AU - Kanodia, Ayush
ID - 1732
TI - Qualitative analysis of POMDPs with temporal logic specifications for robotics applications
ER -
TY - GEN
AB - We consider finite-state concurrent stochastic games, played by k>=2 players for an infinite number of rounds, where in every round, each player simultaneously and independently of the other players chooses an action, whereafter the successor state is determined by a probability distribution given by the current state and the chosen actions. We consider reachability objectives that given a target set of states require that some state in the target set is visited, and the dual safety objectives that given a target set require that only states in the target set are visited. We are interested in the complexity of stationary strategies measured by their patience, which is defined as the inverse of the smallest non-zero probability employed.
Our main results are as follows: We show that in two-player zero-sum concurrent stochastic games (with reachability objective for one player and the complementary safety objective for the other player): (i) the optimal bound on the patience of optimal and epsilon-optimal strategies, for both players is doubly exponential; and (ii) even in games with a single non-absorbing state exponential (in the number of actions) patience is necessary. In general we study the class of non-zero-sum games admitting epsilon-Nash equilibria. We show that if there is at least one player with reachability objective, then doubly-exponential patience is needed in general for epsilon-Nash equilibrium strategies, whereas in contrast if all players have safety objectives, then the optimal bound on patience for epsilon-Nash equilibrium strategies is only exponential.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Hansen, Kristoffer
ID - 5431
SN - 2664-1690
TI - The patience of concurrent stochastic games with safety and reachability objectives
ER -
TY - GEN
AB - DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. DEC-POMDPs have been studied with finite-horizon and infinite-horizon discounted-sum objectives, and there exist solvers both for exact and approximate solutions. In this work we consider Goal-DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new method to solve the problem that extends methods for finite-horizon DEC- POMDPs and the RTDP-Bel approach for POMDPs. We present experimental results on several examples, and show our approach presents promising results.
AU - Anonymous, 1
AU - Anonymous, 2
ID - 5434
SN - 2664-1690
TI - Optimal cost indefinite-horizon reachability in goal DEC-POMDPs
ER -
TY - GEN
AB - We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives.
There have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector.
We consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics.
Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee).
Our main results are algorithms for the decision problem which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions.
Finally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem.
AU - Chatterjee, Krishnendu
AU - Komarkova, Zuzana
AU - Kretinsky, Jan
ID - 5429
SN - 2664-1690
TI - Unifying two views on multiple mean-payoff objectives in Markov decision processes
ER -
TY - GEN
AB - We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives.
There have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector.
We consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee).
Our main results are algorithms for the decision problem which are always polynomial in the size of the MDP.
We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions. Finally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem.
AU - Chatterjee, Krishnendu
AU - Komarkova, Zuzana
AU - Kretinsky, Jan
ID - 5435
SN - 2664-1690
TI - Unifying two views on multiple mean-payoff objectives in Markov decision processes
ER -
TY - GEN
AB - Recently there has been a significant effort to handle quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, some basic system properties such as average response time cannot be expressed using weighted automata, nor in any other know decidable formalism. In this work, we introduce nested weighted automata as a natural extension of weighted automata which makes it possible to express important quantitative properties such as average response time.
In nested weighted automata, a master automaton spins off and collects results from weighted slave automata, each of which computes a quantity along a finite portion of an infinite word. Nested weighted automata can be viewed as the quantitative analogue of monitor automata, which are used in run-time verification. We establish an almost complete decidability picture for the basic decision problems about nested weighted automata, and illustrate their applicability in several domains. In particular, nested weighted automata can be used to decide average response time properties.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 5436
SN - 2664-1690
TI - Nested weighted automata
ER -
TY - CONF
AB - The target discounted-sum problem is the following: Given a rational discount factor 0 < λ < 1 and three rational values a, b, and t, does there exist a finite or an infinite sequence w ε(a, b)∗ or w ε(a, b)w, such that Σ|w| i=0 w(i)λi equals t? The problem turns out to relate to many fields of mathematics and computer science, and its decidability question is surprisingly hard to solve. We solve the finite version of the problem, and show the hardness of the infinite version, linking it to various areas and open problems in mathematics and computer science: β-expansions, discounted-sum automata, piecewise affine maps, and generalizations of the Cantor set. We provide some partial results to the infinite version, among which are solutions to its restriction to eventually-periodic sequences and to the cases that λ λ 1/2 or λ = 1/n, for every n ε N. We use our results for solving some open problems on discounted-sum automata, among which are the exact-value problem for nondeterministic automata over finite words and the universality and inclusion problems for functional automata.
AU - Boker, Udi
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 1659
SN - 1043-6871
T2 - LICS
TI - The target discounted-sum problem
ER -
TY - CONF
AB - The edit distance between two words w1, w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages L1,L2, where the edit distance is the minimal number k such that for every word from L1 there exists a word in L2 with edit distance at most k. We study the edit distance computation problem between pushdown automata and their subclasses. The problem of computing edit distance to pushdown automata is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Ibsen-Jensen, Rasmus
AU - Otop, Jan
ID - 1610
IS - Part II
SN - 978-3-662-47665-9
T2 - 42nd International Colloquium
TI - Edit distance for pushdown automata
VL - 9135
ER -
TY - GEN
AB - We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff property, the ratio property, and the minimum initial credit for energy property.
The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let $n$ denote the number of nodes of a graph, $m$ the number of edges (for constant treewidth graphs $m=O(n)$) and $W$ the largest absolute value of the weights.
Our main theoretical results are as follows.
First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of $\epsilon$ in time $O(n \cdot \log (n/\epsilon))$ and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time $O(n \cdot \log (|a\cdot b|))=O(n\cdot\log (n\cdot W))$, when the output is $\frac{a}{b}$, as compared to the previously best known algorithm with running time $O(n^2 \cdot \log (n\cdot W))$. Third, for the minimum initial credit problem we show that (i)~for general graphs the problem can be solved in $O(n^2\cdot m)$ time and the associated decision problem can be solved in $O(n\cdot m)$ time, improving the previous known $O(n^3\cdot m\cdot \log (n\cdot W))$ and $O(n^2 \cdot m)$ bounds, respectively; and (ii)~for constant treewidth graphs we present an algorithm that requires $O(n\cdot \log n)$ time, improving the previous known $O(n^4 \cdot \log (n \cdot W))$ bound.
We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Pavlogiannis, Andreas
ID - 5437
SN - 2664-1690
TI - Faster algorithms for quantitative verification in constant treewidth graphs
ER -
TY - GEN
AB - We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean- payoff property, the ratio property, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let n denote the number of nodes of a graph, m the number of edges (for constant treewidth graphs m = O ( n ) ) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a mul- tiplicative factor of ∊ in time O ( n · log( n/∊ )) and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time O ( n · log( | a · b · n | )) = O ( n · log( n · W )) , when the output is a b , as compared to the previously best known algorithm with running time O ( n 2 · log( n · W )) . Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O ( n 2 · m ) time and the associated decision problem can be solved in O ( n · m ) time, improving the previous known O ( n 3 · m · log( n · W )) and O ( n 2 · m ) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O ( n · log n ) time, improving the previous known O ( n 4 · log( n · W )) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Pavlogiannis, Andreas
ID - 5430
SN - 2664-1690
TI - Faster algorithms for quantitative verification in constant treewidth graphs
ER -
TY - GEN
AB - The target discounted-sum problem is the following: Given a rational discount factor 0 < λ < 1 and three rational values a, b, and t, does there exist a finite or an infinite sequence w ε(a, b)∗ or w ε(a, b)w, such that Σ|w| i=0 w(i)λi equals t? The problem turns out to relate to many fields of mathematics and computer science, and its decidability question is surprisingly hard to solve. We solve the finite version of the problem, and show the hardness of the infinite version, linking it to various areas and open problems in mathematics and computer science: β-expansions, discounted-sum automata, piecewise affine maps, and generalizations of the Cantor set. We provide some partial results to the infinite version, among which are solutions to its restriction to eventually-periodic sequences and to the cases that λ λ 1/2 or λ = 1/n, for every n ε N. We use our results for solving some open problems on discounted-sum automata, among which are the exact-value problem for nondeterministic automata over finite words and the universality and inclusion problems for functional automata.
AU - Boker, Udi
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 5439
SN - 2664-1690
TI - The target discounted-sum problem
ER -
TY - GEN
AB - The edit distance between two words w1, w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages L1, L2, where the edit distance is the minimal number k such that for every word from L1 there exists a word in L2 with edit distance at most k. We study the edit distance computation problem between pushdown automata and their subclasses.
The problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Ibsen-Jensen, Rasmus
AU - Otop, Jan
ID - 5438
SN - 2664-1690
TI - Edit distance for pushdown automata
ER -
TY - GEN
AB - Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom for payoff in the context of evolution. The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. The fitness (or the reproductive rate) is a non-negative number, and depends on the payoff. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are as follows: First, we consider a special case of the general problem, where the residents do not reproduce. We show that the qualitative question is NP-complete, and the quantitative approximation question is #P-complete, and the hardness results hold even in the special case where the interaction and the replacement graphs coincide. Second, we show that in general both the qualitative and the quantitative approximation questions are PSPACE-complete. The PSPACE-hardness result for quantitative approximation holds even when the fitness is always positive.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Nowak, Martin
ID - 5440
SN - 2664-1690
TI - The complexity of evolutionary games on graphs
ER -
TY - GEN
AB - Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom in the context of evolution.The replacement graph specifies who competes with whom for reproduction.
The vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability.
Our main results are:
(1) We show that the qualitative question is NP-complete and the quantitative approximation question is #P-hard in the special case when the interaction and the replacement graphs coincide and even with the restriction that the resident individuals do not reproduce (which corresponds to an invading population taking over an empty structure).
(2) We show that in general the qualitative question is PSPACE-complete and the quantitative approximation question is PSPACE-hard and can be solved in exponential time.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Nowak, Martin
ID - 5432
SN - 2664-1690
TI - The complexity of evolutionary games on graphs
ER -
TY - GEN
AB - A comprehensive understanding of the clonal evolution of cancer is critical for understanding neoplasia. Genome-wide sequencing data enables evolutionary studies at unprecedented depth. However, classical phylogenetic methods often struggle with noisy sequencing data of impure DNA samples and fail to detect subclones that have different evolutionary trajectories. We have developed a tool, called Treeomics, that allows us to reconstruct the phylogeny of a cancer with commonly available sequencing technologies. Using Bayesian inference and Integer Linear Programming, robust phylogenies consistent with the biological processes underlying cancer evolution were obtained for pancreatic, ovarian, and prostate cancers. Furthermore, Treeomics correctly identified sequencing artifacts such as those resulting from low statistical power; nearly 7% of variants were misclassified by conventional statistical methods. These artifacts can skew phylogenies by creating illusory tumor heterogeneity among distinct samples. Importantly, we show that the evolutionary trees generated with Treeomics are mathematically optimal.
AU - Reiter, Johannes
AU - Makohon-Moore, Alvin
AU - Gerold, Jeffrey
AU - Bozic, Ivana
AU - Chatterjee, Krishnendu
AU - Iacobuzio-Donahue, Christine
AU - Vogelstein, Bert
AU - Nowak, Martin
ID - 5444
SN - 2664-1690
TI - Reconstructing robust phylogenies of metastatic cancers
ER -
TY - GEN
AB - POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIME-complete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Davies, Jessica
ID - 5443
SN - 2664-1690
TI - A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs
ER -
TY - CONF
AB - For deterministic systems, a counterexample to a property can simply be an error trace, whereas counterexamples in probabilistic systems are necessarily more complex. For instance, a set of erroneous traces with a sufficient cumulative probability mass can be used. Since these are too large objects to understand and manipulate, compact representations such as subchains have been considered. In the case of probabilistic systems with non-determinism, the situation is even more complex. While a subchain for a given strategy (or scheduler, resolving non-determinism) is a straightforward choice, we take a different approach. Instead, we focus on the strategy itself, and extract the most important decisions it makes, and present its succinct representation.
The key tools we employ to achieve this are (1) introducing a concept of importance of a state w.r.t. the strategy, and (2) learning using decision trees. There are three main consequent advantages of our approach. Firstly, it exploits the quantitative information on states, stressing the more important decisions. Secondly, it leads to a greater variability and degree of freedom in representing the strategies. Thirdly, the representation uses a self-explanatory data structure. In summary, our approach produces more succinct and more explainable strategies, as opposed to e.g. binary decision diagrams. Finally, our experimental results show that we can extract several rules describing the strategy even for very large systems that do not fit in memory, and based on the rules explain the erroneous behaviour.
AU - Brázdil, Tomáš
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Fellner, Andreas
AU - Kretinsky, Jan
ID - 1603
TI - Counterexample explanation by learning small strategies in Markov decision processes
VL - 9206
ER -