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 consider the satisfiability problem for modal logic over first-order definable classes of frames.We confirm the conjecture from Hemaspaandra and Schnoor [2008] that modal logic is decidable over classes definable by universal Horn formulae. We provide a full classification of Horn formulae with respect to the complexity of the corresponding satisfiability problem. It turns out, that except for the trivial case of inconsistent formulae, local satisfiability is eitherNP-complete or PSPACE-complete, and global satisfiability is NP-complete, PSPACE-complete, or ExpTime-complete. We also show that the finite satisfiability problem for modal logic over Horn definable classes of frames is decidable. On the negative side, we show undecidability of two related problems. First, we exhibit a simple universal three-variable formula defining the class of frames over which modal logic is undecidable. Second, we consider the satisfiability problem of bimodal logic over Horn definable classes of frames, and also present a formula leading to undecidability. AU - Michaliszyn, Jakub AU - Otop, Jan AU - Kieroňski, Emanuel ID - 1680 IS - 1 JF - ACM Transactions on Computational Logic TI - On the decidability of elementary modal logics VL - 17 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 - JOUR AB - The 1 MDa, 45-subunit proton-pumping NADH-ubiquinone oxidoreductase (complex I) is the largest complex of the mitochondrial electron transport chain. The molecular mechanism of complex I is central to the metabolism of cells, but has yet to be fully characterized. The last two years have seen steady progress towards this goal with the first atomic-resolution structure of the entire bacterial complex I, a 5 Å cryo-electron microscopy map of bovine mitochondrial complex I and a ∼3.8 Å resolution X-ray crystallographic study of mitochondrial complex I from yeast Yarrowia lipotytica. In this review we will discuss what we have learned from these studies and what remains to be elucidated. AU - Letts, Jame A AU - Sazanov, Leonid A ID - 1683 IS - 8 JF - Current Opinion in Structural Biology TI - Gaining mass: The structure of respiratory complex I-from bacterial towards mitochondrial versions VL - 33 ER - TY - JOUR AU - Kiermaier, Eva AU - Sixt, Michael K ID - 1686 IS - 6252 JF - Science TI - Fragmented communication between immune cells: Neutrophils blaze a trail with migratory cues for T cells to follow to sites of infection VL - 349 ER - TY - CONF AB - Computing an approximation of the reachable states of a hybrid system is a challenge, mainly because overapproximating the solutions of ODEs with a finite number of sets does not scale well. Using template polyhedra can greatly reduce the computational complexity, since it replaces complex operations on sets with a small number of optimization problems. However, the use of templates may make the over-approximation too conservative. Spurious transitions, which are falsely considered reachable, are particularly detrimental to performance and accuracy, and may exacerbate the state explosion problem. In this paper, we examine how spurious transitions can be avoided with minimal computational effort. To this end, detecting spurious transitions is reduced to the well-known problem of showing that two convex sets are disjoint by finding a hyperplane that separates them. We generalize this to owpipes by considering hyperplanes that evolve with time in correspondence to the dynamics of the system. The approach is implemented in the model checker SpaceEx and demonstrated on examples. AU - Frehse, Goran AU - Bogomolov, Sergiy AU - Greitschus, Marius AU - Strump, Thomas AU - Podelski, Andreas ID - 1692 SN - 978-1-4503-3433-4 T2 - Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control TI - Eliminating spurious transitions in reachability with support functions 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 - CONF AB - A number of powerful and scalable hybrid systems model checkers have recently emerged. Although all of them honor roughly the same hybrid systems semantics, they have drastically different model description languages. This situation (a) makes it difficult to quickly evaluate a specific hybrid automaton model using the different tools, (b) obstructs comparisons of reachability approaches, and (c) impedes the widespread application of research results that perform model modification and could benefit many of the tools. In this paper, we present Hyst, a Hybrid Source Transformer. Hyst is a source-to-source translation tool, currently taking input in the SpaceEx model format, and translating to the formats of HyCreate, Flow∗, or dReach. Internally, the tool supports generic model-to-model transformation passes that serve to both ease the translation and potentially improve reachability results for the supported tools. Although these model transformation passes could be implemented within each tool, the Hyst approach provides a single place for model modification, generating modified input sources for the unmodified target tools. Our evaluation demonstrates Hyst is capable of automatically translating benchmarks in several classes (including affine and nonlinear hybrid automata) to the input formats of several tools. Additionally, we illustrate a general model transformation pass based on pseudo-invariants implemented in Hyst that illustrates the reachability improvement. AU - Bak, Stanley AU - Bogomolov, Sergiy AU - Johnson, Taylor ID - 1690 TI - HYST: A source transformation and translation tool for hybrid automaton models ER - TY - CONF AB - We consider a case study of the problem of deploying an autonomous air vehicle in a partially observable, dynamic, indoor environment from a specification given as a linear temporal logic (LTL) formula over regions of interest. We model the motion and sensing capabilities of the vehicle as a partially observable Markov decision process (POMDP). We adapt recent results for solving POMDPs with parity objectives to generate a control policy. We also extend the existing framework with a policy minimization technique to obtain a better implementable policy, while preserving its correctness. The proposed techniques are illustrated in an experimental setup involving an autonomous quadrotor performing surveillance in a dynamic environment. AU - Svoreňová, Mária AU - Chmelik, Martin AU - Leahy, Kevin AU - Eniser, Hasan AU - Chatterjee, Krishnendu AU - Cěrná, Ivana AU - Belta, Cǎlin ID - 1691 T2 - Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control TI - Temporal logic motion planning using POMDPs with parity objectives: Case study paper ER - TY - JOUR AB - We introduce quantitative timed refinement and timed simulation (directed) metrics, incorporating zenoness checks, for timed systems. These metrics assign positive real numbers which quantify the timing mismatches between two timed systems, amongst non-zeno runs. We quantify timing mismatches in three ways: (1) the maximal timing mismatch that can arise, (2) the “steady-state” maximal timing mismatches, where initial transient timing mismatches are ignored; and (3) the (long-run) average timing mismatches amongst two systems. These three kinds of mismatches constitute three important types of timing differences. Our event times are the global times, measured from the start of the system execution, not just the time durations of individual steps. We present algorithms over timed automata for computing the three quantitative simulation distances to within any desired degree of accuracy. In order to compute the values of the quantitative simulation distances, we use a game theoretic formulation. We introduce two new kinds of objectives for two player games on finite-state game graphs: (1) eventual debit-sum level objectives, and (2) average debit-sum level objectives. We present algorithms for computing the optimal values for these objectives in graph games, and then use these algorithms to compute the values of the timed simulation distances over timed automata. AU - Chatterjee, Krishnendu AU - Prabhu, Vinayak ID - 1694 IS - 9 JF - IEEE Transactions on Automatic Control TI - Quantitative temporal simulation and refinement distances for timed systems VL - 60 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 - 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 -