TY - JOUR AB - We consider finite-state and recursive game graphs with multidimensional mean-payoff objectives. In recursive games two types of strategies are relevant: global strategies and modular strategies. Our contributions are: (1) We show that finite-state multidimensional mean-payoff games can be solved in polynomial time if the number of dimensions and the maximal absolute value of weights are fixed; whereas for arbitrary dimensions the problem is coNP-complete. (2) We show that one-player recursive games with multidimensional mean-payoff objectives can be solved in polynomial time. Both above algorithms are based on hyperplane separation technique. (3) For recursive games we show that under modular strategies the multidimensional problem is undecidable. We show that if the number of modules, exits, and the maximal absolute value of the weights are fixed, then one-dimensional recursive mean-payoff games under modular strategies can be solved in polynomial time, whereas for unbounded number of exits or modules the problem is NP-hard. AU - Chatterjee, Krishnendu AU - Velner, Yaron ID - 717 JF - Journal of Computer and System Sciences TI - Hyperplane separation technique for multidimensional mean-payoff games VL - 88 ER - TY - JOUR AB - The ubiquity of computation in modern machines and devices imposes a need to assert the correctness of their behavior. Especially in the case of safety-critical systems, their designers need to take measures that enforce their safe operation. Formal methods has emerged as a research field that addresses this challenge: by rigorously proving that all system executions adhere to their specifications, the correctness of an implementation under concern can be assured. To achieve this goal, a plethora of techniques are nowadays available, all of which are optimized for different system types and application domains. AU - Chatterjee, Krishnendu AU - Ehlers, Rüdiger ID - 719 IS - 6 JF - Acta Informatica SN - 00015903 TI - Special issue: Synthesis and SYNT 2014 VL - 54 ER - TY - JOUR AB - Advances in multi-unit recordings pave the way for statistical modeling of activity patterns in large neural populations. Recent studies have shown that the summed activity of all neurons strongly shapes the population response. A separate recent finding has been that neural populations also exhibit criticality, an anomalously large dynamic range for the probabilities of different population activity patterns. Motivated by these two observations, we introduce a class of probabilistic models which takes into account the prior knowledge that the neural population could be globally coupled and close to critical. These models consist of an energy function which parametrizes interactions between small groups of neurons, and an arbitrary positive, strictly increasing, and twice differentiable function which maps the energy of a population pattern to its probability. We show that: 1) augmenting a pairwise Ising model with a nonlinearity yields an accurate description of the activity of retinal ganglion cells which outperforms previous models based on the summed activity of neurons; 2) prior knowledge that the population is critical translates to prior expectations about the shape of the nonlinearity; 3) the nonlinearity admits an interpretation in terms of a continuous latent variable globally coupling the system whose distribution we can infer from data. Our method is independent of the underlying system’s state space; hence, it can be applied to other systems such as natural scenes or amino acid sequences of proteins which are also known to exhibit criticality. AU - Humplik, Jan AU - Tkacik, Gasper ID - 720 IS - 9 JF - PLoS Computational Biology SN - 1553734X TI - Probabilistic models for neural populations that naturally capture global coupling and criticality VL - 13 ER - TY - JOUR AB - Let S be a positivity-preserving symmetric linear operator acting on bounded functions. The nonlinear equation -1/m=z+Sm with a parameter z in the complex upper half-plane ℍ has a unique solution m with values in ℍ. We show that the z-dependence of this solution can be represented as the Stieltjes transforms of a family of probability measures v on ℝ. Under suitable conditions on S, we show that v has a real analytic density apart from finitely many algebraic singularities of degree at most 3. Our motivation comes from large random matrices. The solution m determines the density of eigenvalues of two prominent matrix ensembles: (i) matrices with centered independent entries whose variances are given by S and (ii) matrices with correlated entries with a translation-invariant correlation structure. Our analysis shows that the limiting eigenvalue density has only square root singularities or cubic root cusps; no other singularities occur. AU - Ajanki, Oskari H AU - Krüger, Torben H AU - Erdös, László ID - 721 IS - 9 JF - Communications on Pure and Applied Mathematics SN - 00103640 TI - Singularities of solutions to quadratic vector equations on the complex upper half plane VL - 70 ER - TY - JOUR AB - Plants are sessile organisms rooted in one place. The soil resources that plants require are often distributed in a highly heterogeneous pattern. To aid foraging, plants have evolved roots whose growth and development are highly responsive to soil signals. As a result, 3D root architecture is shaped by myriad environmental signals to ensure resource capture is optimised and unfavourable environments are avoided. The first signals sensed by newly germinating seeds — gravity and light — direct root growth into the soil to aid seedling establishment. Heterogeneous soil resources, such as water, nitrogen and phosphate, also act as signals that shape 3D root growth to optimise uptake. Root architecture is also modified through biotic interactions that include soil fungi and neighbouring plants. This developmental plasticity results in a ‘custom-made’ 3D root system that is best adapted to forage for resources in each soil environment that a plant colonises. AU - Morris, Emily AU - Griffiths, Marcus AU - Golebiowska, Agata AU - Mairhofer, Stefan AU - Burr Hersey, Jasmine AU - Goh, Tatsuaki AU - Von Wangenheim, Daniel AU - Atkinson, Brian AU - Sturrock, Craig AU - Lynch, Jonathan AU - Vissenberg, Kris AU - Ritz, Karl AU - Wells, Darren AU - Mooney, Sacha AU - Bennett, Malcolm ID - 722 IS - 17 JF - Current Biology SN - 09609822 TI - Shaping 3D root system architecture VL - 27 ER - TY - JOUR AB - Individual computations and social interactions underlying collective behavior in groups of animals are of great ethological, behavioral, and theoretical interest. While complex individual behaviors have successfully been parsed into small dictionaries of stereotyped behavioral modes, studies of collective behavior largely ignored these findings; instead, their focus was on inferring single, mode-independent social interaction rules that reproduced macroscopic and often qualitative features of group behavior. Here, we bring these two approaches together to predict individual swimming patterns of adult zebrafish in a group. We show that fish alternate between an “active” mode, in which they are sensitive to the swimming patterns of conspecifics, and a “passive” mode, where they ignore them. Using a model that accounts for these two modes explicitly, we predict behaviors of individual fish with high accuracy, outperforming previous approaches that assumed a single continuous computation by individuals and simple metric or topological weighing of neighbors’ behavior. At the group level, switching between active and passive modes is uncorrelated among fish, but correlated directional swimming behavior still emerges. Our quantitative approach for studying complex, multi-modal individual behavior jointly with emergent group behavior is readily extensible to additional behavioral modes and their neural correlates as well as to other species. AU - Harpaz, Roy AU - Tkacik, Gasper AU - Schneidman, Elad ID - 725 IS - 38 JF - PNAS SN - 00278424 TI - Discrete modes of social information processing predict individual behavior of fish in a group VL - 114 ER - TY - JOUR AB - We investigate the stationary and dynamical behavior of an Anderson localized chain coupled to a single central bound state. Although this coupling partially dilutes the Anderson localized peaks towards nearly resonant sites, the most weight of the original peaks remains unchanged. This leads to multifractal wave functions with a frozen spectrum of fractal dimensions, which is characteristic for localized phases in models with power-law hopping. Using a perturbative approach we identify two different dynamical regimes. At weak couplings to the central site, the transport of particles and information is logarithmic in time, a feature usually attributed to many-body localization. We connect such transport to the persistence of the Poisson statistics of level spacings in parts of the spectrum. In contrast, at stronger couplings the level repulsion is established in the entire spectrum, the problem can be mapped to the Fano resonance, and the transport is ballistic. AU - Hetterich, Daniel AU - Serbyn, Maksym AU - Domínguez, Fernando AU - Pollmann, Frank AU - Trauzettel, Björn ID - 724 IS - 10 JF - Physical Review B SN - 24699950 TI - Noninteracting central site model localization and logarithmic entanglement growth VL - 96 ER - TY - JOUR AB - Genetic variations in the oxytocin receptor gene affect patients with ASD and ADHD differently. AU - Novarino, Gaia ID - 731 IS - 411 JF - Science Translational Medicine SN - 19466234 TI - The science of love in ASD and ADHD VL - 9 ER - TY - JOUR AB - Inflammation, which is a highly regulated host response against danger signals, may be harmful if it is excessive and deregulated. Ideally, anti-inflammatory therapy should autonomously commence as soon as possible after the onset of inflammation, should be controllable by a physician, and should not systemically block beneficial immune response in the long term. We describe a genetically encoded anti-inflammatory mammalian cell device based on a modular engineered genetic circuit comprising a sensor, an amplifier, a “thresholder” to restrict activation of a positive-feedback loop, a combination of advanced clinically used biopharmaceutical proteins, and orthogonal regulatory elements that linked modules into the functional device. This genetic circuit was autonomously activated by inflammatory signals, including endogenous cecal ligation and puncture (CLP)-induced inflammation in mice and serum from a systemic juvenile idiopathic arthritis (sIJA) patient, and could be reset externally by a chemical signal. The microencapsulated anti-inflammatory device significantly reduced the pathology in dextran sodium sulfate (DSS)-induced acute murine colitis, demonstrating a synthetic immunological approach for autonomous anti-inflammatory therapy. AU - Smole, Anže AU - Lainšček, Duško AU - Bezeljak, Urban AU - Horvat, Simon AU - Jerala, Roman ID - 7360 IS - 1 JF - Molecular Therapy SN - 1525-0016 TI - A synthetic mammalian therapeutic gene circuit for sensing and suppressing inflammation VL - 25 ER - TY - CONF AB - Modern communication technologies allow first responders to contact thousands of potential volunteers simultaneously for support during a crisis or disaster event. However, such volunteer efforts must be well coordinated and monitored, in order to offer an effective relief to the professionals. In this paper we extend earlier work on optimally assigning volunteers to selected landmark locations. In particular, we emphasize the aspect that obtaining good assignments requires not only advanced computational tools, but also a realistic measure of distance between volunteers and landmarks. Specifically, we propose the use of the Open Street Map (OSM) driving distance instead of he previously used flight distance. We find the OSM driving distance to be better aligned with the interests of volunteers and first responders. Furthermore, we show that relying on the flying distance leads to a substantial underestimation of the number of required volunteers, causing negative side effects in case of an actual crisis situation. AU - Pielorz, Jasmin AU - Prandtstetter, Matthias AU - Straub, Markus AU - Lampert, Christoph ID - 750 SN - 978-153862714-3 T2 - 2017 IEEE International Conference on Big Data TI - Optimal geospatial volunteer allocation needs realistic distances ER -