@article{866,
abstract = {Proteases play important roles in many biologic processes and are key mediators of cancer, inflammation, and thrombosis. However, comprehensive and quantitative techniques to define the substrate specificity profile of proteases are lacking. The metalloprotease ADAMTS13 regulates blood coagulation by cleaving von Willebrand factor (VWF), reducing its procoagulant activity. A mutagenized substrate phage display library based on a 73-amino acid fragment of VWF was constructed, and the ADAMTS13-dependent change in library complexity was evaluated over reaction time points, using high-throughput sequencing. Reaction rate constants (kcat/KM) were calculated for nearly every possible single amino acid substitution within this fragment. This massively parallel enzyme kinetics analysis detailed the specificity of ADAMTS13 and demonstrated the critical importance of the P1-P1' substrate residues while defining exosite binding domains. These data provided empirical evidence for the propensity for epistasis within VWF and showed strong correlation to conservation across orthologs, highlighting evolutionary selective pressures for VWF.},
author = {Kretz, Colin A and Dai, Manhong and Soylemez, Onuralp and Yee, Andrew and Desch, Karl C and Siemieniak, David R and Tomberg, Kärt and Fyodor Kondrashov and Meng, Fan and Ginsburg, David B},
journal = {PNAS},
number = {30},
pages = {9328 -- 9333},
publisher = {National Academy of Sciences},
title = {{Massively parallel enzyme kinetics reveals the substrate recognition landscape of the metalloprotease ADAMTS13}},
doi = {10.1073/pnas.1511328112},
volume = {112},
year = {2015},
}
@inproceedings{784,
abstract = {We demonstrate an optical switch design that can scale up to a thousand ports with high per-port bandwidth (25 Gbps+) and low switching latency (40 ns). Our design uses a broadcast and select architecture, based on a passive star coupler and fast tunable transceivers. In addition we employ time division multiplexing to achieve very low switching latency. Our demo shows the feasibility of the switch data plane using a small testbed, comprising two transmitters and a receiver, connected through a star coupler.},
author = {Alistarh, Dan-Adrian and Ballani, Hitesh and Costa, Paolo and Funnell, Adam and Benjamin, Joshua and Watts, Philip and Thomsen, Benn},
isbn = {978-1-4503-3542-3},
location = {London, United Kindgdom},
pages = {367 -- 368},
publisher = {ACM},
title = {{A high-radix, low-latency optical switch for data centers}},
doi = {10.1145/2785956.2790035},
year = {2015},
}
@article{924,
abstract = {This paper presents a numerical study of a Capillary Pumped Loop evaporator. A two-dimensional unsteady mathematical model of a flat evaporator is developed to simulate heat and mass transfer in unsaturated porous wick with phase change. The liquid-vapor phase change inside the porous wick is described by Langmuir's law. The governing equations are solved by the Finite Element Method. The results are presented then for a sintered nickel wick and methanol as a working fluid. The heat flux required to the transition from the all-liquid wick to the vapor-liquid wick is calculated. The dynamic and thermodynamic behavior of the working fluid in the capillary structure are discussed in this paper.},
author = {Boubaker, Riadh and Platel, Vincent and Bergès, Alexis and Bancelin, Mathieu and Hannezo, Edouard},
journal = {Applied Thermal Engineering},
pages = {1 -- 8},
publisher = {Elsevier},
title = {{Dynamic model of heat and mass transfer in an unsaturated porous wick of capillary pumped loop}},
doi = {10.1016/j.applthermaleng.2014.10.009},
volume = {76},
year = {2015},
}
@article{929,
abstract = {An essential question of morphogenesis is how patterns arise without preexisting positional information, as inspired by Turing. In the past few years, cytoskeletal flows in the cell cortex have been identified as a key mechanism of molecular patterning at the subcellular level. Theoretical and in vitro studies have suggested that biological polymers such as actomyosin gels have the property to self-organize, but the applicability of this concept in an in vivo setting remains unclear. Here, we report that the regular spacing pattern of supracellular actin rings in the Drosophila tracheal tubule is governed by a self-organizing principle. We propose a simple biophysical model where pattern formation arises from the interplay of myosin contractility and actin turnover. We validate the hypotheses of the model using photobleaching experiments and report that the formation of actin rings is contractility dependent. Moreover, genetic and pharmacological perturbations of the physical properties of the actomyosin gel modify the spacing of the pattern, as the model predicted. In addition, our model posited a role of cortical friction in stabilizing the spacing pattern of actin rings. Consistently, genetic depletion of apical extracellular matrix caused strikingly dynamic movements of actin rings, mirroring our model prediction of a transition from steady to chaotic actin patterns at low cortical friction. Our results therefore demonstrate quantitatively that a hydrodynamical instability of the actin cortex can trigger regular pattern formation and drive morphogenesis in an in vivo setting. },
author = {Hannezo, Edouard and Dong, Bo and Recho, Pierre and Joanny, Jean F and Hayashi, Shigeo},
journal = {PNAS},
number = {28},
pages = {8620 -- 8625},
publisher = {National Academy of Sciences},
title = {{Cortical instability drives periodic supracellular actin pattern formation in epithelial tubes}},
doi = {10.1073/pnas.1504762112},
volume = {112},
year = {2015},
}
@article{981,
abstract = {The tunability of topological surface states and controllable opening of the Dirac gap are of fundamental and practical interest in the field of topological materials. In the newly discovered topological crystalline insulators (TCIs), theory predicts that the Dirac node is protected by a crystalline symmetry and that the surface state electrons can acquire a mass if this symmetry is broken. Recent studies have detected signatures of a spontaneously generated Dirac gap in TCIs; however, the mechanism of mass formation remains elusive. In this work, we present scanning tunnelling microscopy (STM) measurements of the TCI Pb 1â'x Sn x Se for a wide range of alloy compositions spanning the topological and non-topological regimes. The STM topographies reveal a symmetry-breaking distortion on the surface, which imparts mass to the otherwise massless Dirac electrons-a mechanism analogous to the long sought-after Higgs mechanism in particle physics. Interestingly, the measured Dirac gap decreases on approaching the trivial phase, whereas the magnitude of the distortion remains nearly constant. Our data and calculations reveal that the penetration depth of Dirac surface states controls the magnitude of the Dirac mass. At the limit of the critical composition, the penetration depth is predicted to go to infinity, resulting in zero mass, consistent with our measurements. Finally, we discover the existence of surface states in the non-topological regime, which have the characteristics of gapped, double-branched Dirac fermions and could be exploited in realizing superconductivity in these materials.},
author = {Zeljkovic, Ilija and Okada, Yoshinori and Maksym Serbyn and Sankar, Raman and Walkup, Daniel and Zhou, Wenwen and Liu, Junwei and Chang, Guoqing and Wang, Yungjui and Hasan, Md Z and Chou, Fangcheng and Lin, Hsin and Bansil, Arun and Fu, Liang and Madhavan, Vidya},
journal = {Nature Materials},
number = {3},
pages = {318 -- 324},
publisher = {Nature Publishing Group},
title = {{Dirac mass generation from crystal symmetry breaking on the surfaces of topological crystalline insulators}},
doi = {10.1038/nmat4215},
volume = {14},
year = {2015},
}
@article{99,
abstract = {Quasiparticle excitations can compromise the performance of superconducting devices, causing high-frequency dissipation, decoherence in Josephson qubits, and braiding errors in proposed Majorana-based topological quantum computers. Quasiparticle dynamics have been studied in detail in metallic superconductors but remain relatively unexplored in semiconductor-superconductor structures, which are now being intensely pursued in the context of topological superconductivity. To this end, we use a system comprising a gate-confined semiconductor nanowire with an epitaxially grown superconductor layer, yielding an isolated, proximitized nanowire segment. We identify bound states in the semiconductor by means of bias spectroscopy, determine the characteristic temperatures and magnetic fields for quasiparticle excitations, and extract a parity lifetime (poisoning time) of the bound state in the semiconductor exceeding 10 ms.},
author = {Higginbotham, Andrew P and Albrecht, S M and Kiršanskas, Gediminas and Chang, W and Kuemmeth, Ferdinand and Krogstrup, Peter and Jespersen, Thomas and Nygård, Jesper and Flensberg, Karsten and Marcus, Charles},
journal = {Nature Physics},
number = {12},
pages = {1017 -- 1021},
publisher = {Nature Publishing Group},
title = {{Parity lifetime of bound states in a proximitized semiconductor nanowire}},
doi = {10.1038/nphys3461},
volume = {11},
year = {2015},
}
@misc{5437,
abstract = {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. },
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas},
issn = {2664-1690},
pages = {27},
publisher = {IST Austria},
title = {{Faster algorithms for quantitative verification in constant treewidth graphs}},
doi = {10.15479/AT:IST-2015-330-v2-1},
year = {2015},
}
@inproceedings{1606,
abstract = {In this paper, we present the first steps toward a runtime verification framework for monitoring hybrid and cyber-physical systems (CPS) development tools based on randomized differential testing. The development tools include hybrid systems reachability analysis tools, model-based development environments like Simulink/Stateflow (SLSF), etc. First, hybrid automaton models are randomly generated. Next, these hybrid automaton models are translated to a number of different tools (currently, SpaceEx, dReach, Flow*, HyCreate, and the MathWorks’ Simulink/Stateflow) using the HyST source transformation and translation tool. Then, the hybrid automaton models are executed in the different tools and their outputs are parsed. The final step is the differential comparison: the outputs of the different tools are compared. If the results do not agree (in the sense that an analysis or verification result from one tool does not match that of another tool, ignoring timeouts, etc.), a candidate bug is flagged and the model is saved for future analysis by the user. The process then repeats and the monitoring continues until the user terminates the process. We present preliminary results that have been useful in identifying a few bugs in the analysis methods of different development tools, and in an earlier version of HyST.},
author = {Nguyen, Luan and Schilling, Christian and Bogomolov, Sergiy and Johnson, Taylor},
location = {Vienna, Austria},
pages = {281 -- 286},
publisher = {Springer},
title = {{Runtime verification for hybrid analysis tools}},
doi = {10.1007/978-3-319-23820-3_19},
volume = {9333},
year = {2015},
}
@inproceedings{1670,
abstract = {Planning in hybrid domains poses a special challenge due to the involved mixed discrete-continuous dynamics. A recent solving approach for such domains is based on applying model checking techniques on a translation of PDDL+ planning problems to hybrid automata. However, the proposed translation is limited because must behavior is only overapproximated, and hence, processes and events are not reflected exactly. In this paper, we present the theoretical foundation of an exact PDDL+ translation. We propose a schema to convert a hybrid automaton with must transitions into an equivalent hybrid automaton featuring only may transitions.},
author = {Bogomolov, Sergiy and Magazzeni, Daniele and Minopoli, Stefano and Wehrle, Martin},
location = {Jerusalem, Israel},
pages = {42 -- 46},
publisher = {AAAI Press},
title = {{PDDL+ planning with hybrid automata: Foundations of translating must behavior}},
year = {2015},
}
@article{1810,
abstract = {Combining antibiotics is a promising strategy for increasing treatment efficacy and for controlling resistance evolution. When drugs are combined, their effects on cells may be amplified or weakened, that is the drugs may show synergistic or antagonistic interactions. Recent work revealed the underlying mechanisms of such drug interactions by elucidating the drugs'; joint effects on cell physiology. Moreover, new treatment strategies that use drug combinations to exploit evolutionary tradeoffs were shown to affect the rate of resistance evolution in predictable ways. High throughput studies have further identified drug candidates based on their interactions with established antibiotics and general principles that enable the prediction of drug interactions were suggested. Overall, the conceptual and technical foundation for the rational design of potent drug combinations is rapidly developing.},
author = {Bollenbach, Mark Tobias},
journal = {Current Opinion in Microbiology},
pages = {1 -- 9},
publisher = {Elsevier},
title = {{Antimicrobial interactions: Mechanisms and implications for drug discovery and resistance evolution}},
doi = {10.1016/j.mib.2015.05.008},
volume = {27},
year = {2015},
}
@inproceedings{1839,
abstract = {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.},
author = {Brázdil, Tomáš and Chatterjee, Krishnendu and Forejt, Vojtěch and Kučera, Antonín},
location = {London, United Kingdom},
pages = {181 -- 187},
publisher = {Springer},
title = {{Multigain: A controller synthesis tool for MDPs with multiple mean-payoff objectives}},
doi = {10.1007/978-3-662-46681-0_12},
volume = {9035},
year = {2015},
}
@article{2034,
abstract = {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.},
author = {Bérard, Béatrice and Chatterjee, Krishnendu and Sznajder, Nathalie},
journal = { Information Processing Letters},
number = {1},
pages = {52 -- 59},
publisher = {Elsevier},
title = {{Probabilistic opacity for Markov decision processes}},
doi = {10.1016/j.ipl.2014.09.001},
volume = {115},
year = {2015},
}
@article{1694,
abstract = {
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.
},
author = {Chatterjee, Krishnendu and Prabhu, Vinayak},
journal = {IEEE Transactions on Automatic Control},
number = {9},
pages = {2291 -- 2306},
publisher = {IEEE},
title = {{Quantitative temporal simulation and refinement distances for timed systems}},
doi = {10.1109/TAC.2015.2404612},
volume = {60},
year = {2015},
}
@inproceedings{1656,
abstract = {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.},
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan},
booktitle = {Proceedings - Symposium on Logic in Computer Science},
location = {Kyoto, Japan},
publisher = {IEEE},
title = {{Nested weighted automata}},
doi = {10.1109/LICS.2015.72},
volume = {2015-July},
year = {2015},
}
@article{7457,
abstract = {A new organic–inorganic ferroelectric hybrid capacitor designed by uniformly incorporating surface modified monodisperse 15 nm ferroelectric BaTiO3 nanocubes into non-polar polymer blends of poly(methyl methacrylate) (PMMA) polymer and acrylonitrile-butadiene-styrene (ABS) terpolymer is described. The investigation of spatial distribution of nanofillers via a non-distractive thermal pulse method illustrates that the surface functionalization of nanocubes plays a key role in the uniform distribution of charge polarization within the polymer matrix. The discharged energy density of the nanocomposite with 30 vol% BaTiO3 nanocubes is ∼44 × 10−3 J cm−3, which is almost six times higher than that of the neat polymer. The facile processing, along with the superior mechanical and electrical properties of the BaTiO3/PMMA–ABS nanocomposites make them suitable for implementation into capacitive electrical energy storage devices.},
author = {Parizi, Saman Salemizadeh and Conley, Gavin and Costanzo, Tommaso and Howell, Bob and Mellinger, Axel and Caruntu, Gabriel},
issn = {2046-2069},
journal = {RSC Advances},
number = {93},
pages = {76356--76362},
publisher = {RSC},
title = {{Fabrication of barium titanate/acrylonitrile-butadiene styrene/poly(methyl methacrylate) nanocomposite films for hybrid ferroelectric capacitors}},
doi = {10.1039/c5ra11347d},
volume = {5},
year = {2015},
}
@inproceedings{1512,
abstract = {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.},
author = {Goaoc, Xavier and Paták, Pavel and Patakova, Zuzana and Tancer, Martin and Wagner, Uli},
location = {Eindhoven, Netherlands},
pages = {507 -- 521},
publisher = {ACM},
title = {{Bounding Helly numbers via Betti numbers}},
doi = {10.4230/LIPIcs.SOCG.2015.507},
volume = {34},
year = {2015},
}
@article{1598,
abstract = {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.},
author = {Chatterjee, Krishnendu and Joglekar, Manas and Shah, Nisarg},
journal = {Theoretical Computer Science},
number = {3},
pages = {71 -- 89},
publisher = {Elsevier},
title = {{Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives}},
doi = {10.1016/j.tcs.2015.01.050},
volume = {573},
year = {2015},
}
@article{7767,
abstract = {We present a model of soft active particles that leads to a rich array of collective behavior found also in dense biological swarms of bacteria and other unicellular organisms. Our model uses only local interactions, such as Vicsek-type nearest-neighbor alignment, short-range repulsion, and a local boundary term. Changing the relative strength of these interactions leads to migrating swarms, rotating swarms, and jammed swarms, as well as swarms that exhibit run-and-tumble motion, alternating between migration and either rotating or jammed states. Interestingly, although a migrating swarm moves slower than an individual particle, the diffusion constant can be up to three orders of magnitude larger, suggesting that collective motion can be highly advantageous, for example, when searching for food.},
author = {van Drongelen, Ruben and Pal, Anshuman and Goodrich, Carl Peter and Idema, Timon},
issn = {1539-3755},
journal = {Physical Review E},
number = {3},
publisher = {American Physical Society},
title = {{Collective dynamics of soft active particles}},
doi = {10.1103/physreve.91.032706},
volume = {91},
year = {2015},
}
@unpublished{7779,
abstract = {The fact that a disordered material is not constrained in its properties in
the same way as a crystal presents significant and yet largely untapped
potential for novel material design. However, unlike their crystalline
counterparts, disordered solids are not well understood. One of the primary
obstacles is the lack of a theoretical framework for thinking about disorder
and its relation to mechanical properties. To this end, we study an idealized
system of frictionless athermal soft spheres that, when compressed, undergoes a
jamming phase transition with diverging length scales and clean power-law
signatures. This critical point is the cornerstone of a much larger "jamming
scenario" that has the potential to provide the essential theoretical
foundation necessary for a unified understanding of the mechanics of disordered
solids. We begin by showing that jammed sphere packings have a valid linear
regime despite the presence of "contact nonlinearities." We then investigate
the critical nature of the transition, focusing on diverging length scales and
finite-size effects. Next, we argue that jamming plays the same role for
disordered solids as the perfect crystal plays for crystalline solids. Not only
can it be considered an idealized starting point for understanding disordered
materials, but it can even influence systems that have a relatively high amount
of crystalline order. The behavior of solids can thus be thought of as existing
on a spectrum, with the perfect crystal and the jamming transition at opposing
ends. Finally, we introduce a new principle wherein the contribution of an
individual bond to one global property is independent of its contribution to
another. This principle allows the different global responses of a disordered
system to be manipulated independently and provides a great deal of flexibility
in designing materials with unique, textured and tunable properties.},
author = {Goodrich, Carl Peter},
booktitle = {arXiv:1510.08820},
pages = {242},
title = {{Unearthing the anticrystal: Criticality in the linear response of disordered solids}},
year = {2015},
}
@inproceedings{1714,
abstract = {We present a flexible framework for the automated competitive analysis of on-line scheduling algorithms for firm-deadline real-time tasks based on multi-objective graphs: Given a task set and an on-line scheduling algorithm specified as a labeled transition system, along with some optional safety, liveness, and/or limit-average constraints for the adversary, we automatically compute the competitive ratio of the algorithm w.r.t. A clairvoyant scheduler. We demonstrate the flexibility and power of our approach by comparing the competitive ratio of several on-line algorithms, including Dover, that have been proposed in the past, for various task sets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are task sets where other schedulers provide better performance. Our framework is hence a very useful design tool for selecting optimal algorithms for a given application.},
author = {Chatterjee, Krishnendu and Pavlogiannis, Andreas and Kößler, Alexander and Schmid, Ulrich},
booktitle = {Real-Time Systems Symposium},
location = {Rome, Italy},
number = {January},
pages = {118 -- 127},
publisher = {IEEE},
title = {{A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks}},
doi = {10.1109/RTSS.2014.9},
volume = {2015},
year = {2015},
}
@inproceedings{1601,
abstract = {We propose a flexible exchange format for ω-automata, as typically used in formal verification, and implement support for it in a range of established tools. Our aim is to simplify the interaction of tools, helping the research community to build upon other people’s work. A key feature of the format is the use of very generic acceptance conditions, specified by Boolean combinations of acceptance primitives, rather than being limited to common cases such as Büchi, Streett, or Rabin. Such flexibility in the choice of acceptance conditions can be exploited in applications, for example in probabilistic model checking, and furthermore encourages the development of acceptance-agnostic tools for automata manipulations. The format allows acceptance conditions that are either state-based or transition-based, and also supports alternating automata.},
author = {Babiak, Tomáš and Blahoudek, František and Duret Lutz, Alexandre and Klein, Joachim and Kretinsky, Jan and Mueller, Daniel and Parker, David and Strejček, Jan},
location = {San Francisco, CA, United States},
pages = {479 -- 486},
publisher = {Springer},
title = {{The Hanoi omega-automata format}},
doi = {10.1007/978-3-319-21690-4_31},
volume = {9206},
year = {2015},
}
@article{1846,
abstract = {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.},
author = {Beneš, Nikola and Kretinsky, Jan and Larsen, Kim and Möller, Mikael and Sickert, Salomon and Srba, Jiří},
journal = {Acta Informatica},
number = {2-3},
pages = {269 -- 297},
publisher = {Springer},
title = {{Refinement checking on parametric modal transition systems}},
doi = {10.1007/s00236-015-0215-4},
volume = {52},
year = {2015},
}
@article{1555,
abstract = {We show that incorporating spatial dispersal of individuals into a simple vaccination epidemic model may give rise to a model that exhibits rich dynamical behavior. Using an SIVS (susceptible-infected-vaccinated-susceptible) model as a basis, we describe the spread of an infectious disease in a population split into two regions. In each subpopulation, both forward and backward bifurcations can occur. This implies that for disconnected regions the two-patch system may admit several steady states. We consider traveling between the regions and investigate the impact of spatial dispersal of individuals on the model dynamics. We establish conditions for the existence of multiple nontrivial steady states in the system, and we study the structure of the equilibria. The mathematical analysis reveals an unusually rich dynamical behavior, not normally found in the simple epidemic models. In addition to the disease-free equilibrium, eight endemic equilibria emerge from backward transcritical and saddle-node bifurcation points, forming an interesting bifurcation diagram. Stability of steady states, their bifurcations, and the global dynamics are investigated with analytical tools, numerical simulations, and rigorous set-oriented numerical computations.},
author = {Knipl, Diána and Pilarczyk, Pawel and Röst, Gergely},
issn = {1536-0040},
journal = {SIAM Journal on Applied Dynamical Systems},
number = {2},
pages = {980 -- 1017},
publisher = {Society for Industrial and Applied Mathematics },
title = {{Rich bifurcation structure in a two patch vaccination model}},
doi = {10.1137/140993934},
volume = {14},
year = {2015},
}
@article{1311,
abstract = {In this paper, we develop an energy method to study finite speed of propagation and waiting time phenomena for the stochastic porous media equation with linear multiplicative noise in up to three spatial dimensions. Based on a novel iteration technique and on stochastic counterparts of weighted integral estimates used in the deterministic setting, we formulate a sufficient criterion on the growth of initial data which locally guarantees a waiting time phenomenon to occur almost surely. Up to a logarithmic factor, this criterion coincides with the optimal criterion known from the deterministic setting. Our technique can be modified to prove finite speed of propagation as well.},
author = {Julian Fischer and Grün, Günther},
journal = {SIAM Journal on Mathematical Analysis},
number = {1},
pages = {825 -- 854},
publisher = {Society for Industrial and Applied Mathematics },
title = {{Finite speed of propagation and waiting times for the stochastic porous medium equation: A unifying approach}},
doi = {10.1137/140960578},
volume = {47},
year = {2015},
}
@article{1316,
abstract = {In the present work we introduce the notion of a renormalized solution for reaction–diffusion systems with entropy-dissipating reactions. We establish the global existence of renormalized solutions. In the case of integrable reaction terms our notion of a renormalized solution reduces to the usual notion of a weak solution. Our existence result in particular covers all reaction–diffusion systems involving a single reversible reaction with mass-action kinetics and (possibly species-dependent) Fick-law diffusion; more generally, it covers the case of systems of reversible reactions with mass-action kinetics which satisfy the detailed balance condition. For such equations the existence of any kind of solution in general was an open problem, thereby motivating the study of renormalized solutions.},
author = {Julian Fischer},
journal = {Archive for Rational Mechanics and Analysis},
number = {1},
pages = {553 -- 587},
publisher = {Springer},
title = {{Global existence of renormalized solutions to entropy-dissipating reaction–diffusion systems}},
doi = {10.1007/s00205-015-0866-x},
volume = {218},
year = {2015},
}
@inproceedings{1424,
abstract = {We consider the problem of statistical computations with persistence diagrams, a summary representation of topological features in data. These diagrams encode persistent homology, a widely used invariant in topological data analysis. While several avenues towards a statistical treatment of the diagrams have been explored recently, we follow an alternative route that is motivated by the success of methods based on the embedding of probability measures into reproducing kernel Hilbert spaces. In fact, a positive definite kernel on persistence diagrams has recently been proposed, connecting persistent homology to popular kernel-based learning techniques such as support vector machines. However, important properties of that kernel enabling a principled use in the context of probability measure embeddings remain to be explored. Our contribution is to close this gap by proving universality of a variant of the original kernel, and to demonstrate its effective use in twosample hypothesis testing on synthetic as well as real-world data.},
author = {Kwitt, Roland and Huber, Stefan and Niethammer, Marc and Lin, Weili and Bauer, Ulrich},
location = {Montreal, Canada},
pages = {3070 -- 3078},
publisher = {Neural Information Processing Systems},
title = {{Statistical topological data analysis-A kernel perspective}},
volume = {28},
year = {2015},
}
@inbook{1544,
abstract = {Cell division in prokaryotes and eukaryotes is commonly initiated by the well-controlled binding of proteins to the cytoplasmic side of the cell membrane. However, a precise characterization of the spatiotemporal dynamics of membrane-bound proteins is often difficult to achieve in vivo. Here, we present protocols for the use of supported lipid bilayers to rebuild the cytokinetic machineries of cells with greatly different dimensions: the bacterium Escherichia coli and eggs of the vertebrate Xenopus laevis. Combined with total internal reflection fluorescence microscopy, these experimental setups allow for precise quantitative analyses of membrane-bound proteins. The protocols described to obtain glass-supported membranes from bacterial and vertebrate lipids can be used as starting points for other reconstitution experiments. We believe that similar biochemical assays will be instrumental to study the biochemistry and biophysics underlying a variety of complex cellular tasks, such as signaling, vesicle trafficking, and cell motility.},
author = {Nguyen, Phuong and Field, Christine and Groen, Aaron and Mitchison, Timothy and Loose, Martin},
booktitle = {Building a Cell from its Components Parts},
pages = {223 -- 241},
publisher = {Academic Press},
title = {{Using supported bilayers to study the spatiotemporal organization of membrane-bound proteins}},
doi = {10.1016/bs.mcb.2015.01.007},
volume = {128},
year = {2015},
}
@inbook{1549,
abstract = {Nature has incorporated small photochromic molecules, colloquially termed 'photoswitches', in photoreceptor proteins to sense optical cues in photo-taxis and vision. While Nature's ability to employ light-responsive functionalities has long been recognized, it was not until recently that scientists designed, synthesized and applied synthetic photochromes to manipulate many of which open rapidly and locally in their native cell types, biological processes with the temporal and spatial resolution of light. Ion channels in particular have come to the forefront of proteins that can be put under the designer control of synthetic photochromes. Photochromic ion channel controllers are comprised of three classes, photochromic soluble ligands (PCLs), photochromic tethered ligands (PTLs) and photochromic crosslinkers (PXs), and in each class ion channel functionality is controlled through reversible changes in photochrome structure. By acting as light-dependent ion channel agonists, antagonist or modulators, photochromic controllers effectively converted a wide range of ion channels, including voltage-gated ion channels, 'leak channels', tri-, tetra- and pentameric ligand-gated ion channels, and temperaturesensitive ion channels, into man-made photoreceptors. Control by photochromes can be reversible, unlike in the case of 'caged' compounds, and non-invasive with high spatial precision, unlike pharmacology and electrical manipulation. Here, we introduce design principles of emerging photochromic molecules that act on ion channels and discuss the impact that these molecules are beginning to have on ion channel biophysics and neuronal physiology.},
author = {Mckenzie, Catherine and Sanchez Romero, Inmaculada and Janovjak, Harald L},
booktitle = {Novel chemical tools to study ion channel biology},
isbn = {978-1-4939-2844-6},
pages = {101 -- 117},
publisher = {Springer},
title = {{Flipping the photoswitch: Ion channels under light control}},
doi = {10.1007/978-1-4939-2845-3_6},
volume = {869},
year = {2015},
}
@article{1551,
abstract = {Reciprocal coevolution between host and pathogen is widely seen as a major driver of evolution and biological innovation. Yet, to date, the underlying genetic mechanisms and associated trait functions that are unique to rapid coevolutionary change are generally unknown. We here combined experimental evolution of the bacterial biocontrol agent Bacillus thuringiensis and its nematode host Caenorhabditis elegans with large-scale phenotyping, whole genome analysis, and functional genetics to demonstrate the selective benefit of pathogen virulence and the underlying toxin genes during the adaptation process. We show that: (i) high virulence was specifically favoured during pathogen–host coevolution rather than pathogen one-sided adaptation to a nonchanging host or to an environment without host; (ii) the pathogen genotype BT-679 with known nematocidal toxin genes and high virulence specifically swept to fixation in all of the independent replicate populations under coevolution but only some under one-sided adaptation; (iii) high virulence in the BT-679-dominated populations correlated with elevated copy numbers of the plasmid containing the nematocidal toxin genes; (iv) loss of virulence in a toxin-plasmid lacking BT-679 isolate was reconstituted by genetic reintroduction or external addition of the toxins.We conclude that sustained coevolution is distinct from unidirectional selection in shaping the pathogen's genome and life history characteristics. To our knowledge, this study is the first to characterize the pathogen genes involved in coevolutionary adaptation in an animal host–pathogen interaction system.},
author = {El Masri, Leila and Branca, Antoine and Sheppard, Anna and Papkou, Andrei and Laehnemann, David and Guenther, Patrick and Prahl, Swantje and Saebelfeld, Manja and Hollensteiner, Jacqueline and Liesegang, Heiko and Brzuszkiewicz, Elzbieta and Daniel, Rolf and Michiels, Nico and Schulte, Rebecca and Kurtz, Joachim and Rosenstiel, Philip and Telschow, Arndt and Bornberg Bauer, Erich and Schulenburg, Hinrich},
journal = {PLoS Biology},
number = {6},
pages = {1 -- 30},
publisher = {Public Library of Science},
title = {{Host–pathogen coevolution: The selective advantage of Bacillus thuringiensis virulence and its cry toxin genes}},
doi = {10.1371/journal.pbio.1002169},
volume = {13},
year = {2015},
}
@article{1556,
abstract = {The elongator complex subunit 2 (ELP2) protein, one subunit of an evolutionarily conserved histone acetyltransferase complex, has been shown to participate in leaf patterning, plant immune and abiotic stress responses in Arabidopsis thaliana. Here, its role in root development was explored. Compared to the wild type, the elp2 mutant exhibited an accelerated differentiation of its root stem cells and cell division was more active in its quiescent centre (QC). The key transcription factors responsible for maintaining root stem cell and QC identity, such as AP2 transcription factors PLT1 (PLETHORA1) and PLT2 (PLETHORA2), GRAS transcription factors such as SCR (SCARECROW) and SHR (SHORT ROOT) and WUSCHEL-RELATED HOMEOBOX5 transcription factor WOX5, were all strongly down-regulated in the mutant. On the other hand, expression of the G2/M transition activator CYCB1 was substantially induced in elp2. The auxin efflux transporters PIN1 and PIN2 showed decreased protein levels and PIN1 also displayed mild polarity alterations in elp2, which resulted in a reduced auxin content in the root tip. Either the acetylation or methylation level of each of these genes differed between the mutant and the wild type, suggesting that the ELP2 regulation of root development involves the epigenetic modification of a range of transcription factors and other developmental regulators.},
author = {Jia, Yuebin and Tian, Huiyu and Li, Hongjiang and Yu, Qianqian and Wang, Lei and Friml, Jirí and Ding, Zhaojun},
journal = {Journal of Experimental Botany},
number = {15},
pages = {4631 -- 4642},
publisher = {Oxford University Press},
title = {{The Arabidopsis thaliana elongator complex subunit 2 epigenetically affects root development}},
doi = {10.1093/jxb/erv230},
volume = {66},
year = {2015},
}
@article{1563,
abstract = {For a given self-map $f$ of $M$, a closed smooth connected and simply-connected manifold of dimension $m\geq 4$, we provide an algorithm for estimating the values of the topological invariant $D^m_r[f]$, which equals the minimal number of $r$-periodic points in the smooth homotopy class of $f$. Our results are based on the combinatorial scheme for computing $D^m_r[f]$ introduced by G. Graff and J. Jezierski [J. Fixed Point Theory Appl. 13 (2013), 63-84]. An open-source implementation of the algorithm programmed in C++ is publicly available at {\tt http://www.pawelpilarczyk.com/combtop/}.},
author = {Graff, Grzegorz and Pilarczyk, Pawel},
journal = {Topological Methods in Nonlinear Analysis},
number = {1},
pages = {273 -- 286},
publisher = {Juliusz Schauder Center for Nonlinear Studies},
title = {{An algorithmic approach to estimating the minimal number of periodic points for smooth self-maps of simply-connected manifolds}},
doi = {10.12775/TMNA.2015.014},
volume = {45},
year = {2015},
}
@article{1513,
abstract = {Insects of the order Hemiptera (true bugs) use a wide range of mechanisms of sex determination, including genetic sex determination, paternal genome elimination, and haplodiploidy. Genetic sex determination, the prevalent mode, is generally controlled by a pair of XY sex chromosomes or by an XX/X0 system, but different configurations that include additional sex chromosomes are also present. Although this diversity of sex determining systems has been extensively studied at the cytogenetic level, only the X chromosome of the model pea aphid Acyrthosiphon pisum has been analyzed at the genomic level, and little is known about X chromosome biology in the rest of the order.
In this study, we take advantage of published DNA- and RNA-seq data from three additional Hemiptera species to perform a comparative analysis of the gene content and expression of the X chromosome throughout this clade. We find that, despite showing evidence of dosage compensation, the X chromosomes of these species show female-biased expression, and a deficit of male-biased genes, in direct contrast to the pea aphid X. We further detect an excess of shared gene content between these very distant species, suggesting that despite the diversity of sex determining systems, the same chromosomal element is used as the X throughout a large portion of the order. },
author = {Pal, Arka and Vicoso, Beatriz},
journal = {Genome Biology and Evolution},
number = {12},
pages = {3259 -- 3268},
publisher = {Oxford University Press},
title = {{The X chromosome of hemipteran insects: Conservation, dosage compensation and sex-biased expression}},
doi = {10.1093/gbe/evv215 },
volume = {7},
year = {2015},
}
@inproceedings{1520,
abstract = {Creating mechanical automata that can walk in stable and pleasing manners is a challenging task that requires both skill and expertise. We propose to use computational design to offset the technical difficulties of this process. A simple drag-and-drop interface allows casual users to create personalized walking toys from a library of pre-defined template mechanisms. Provided with this input, our method leverages physical simulation and evolutionary optimization to refine the mechanical designs such that the resulting toys are able to walk. The optimization process is guided by an intuitive set of objectives that measure the quality of the walking motions. We demonstrate our approach on a set of simulated mechanical toys with different numbers of legs and various distinct gaits. Two fabricated prototypes showcase the feasibility of our designs.},
author = {Bharaj, Gaurav and Coros, Stelian and Thomaszewski, Bernhard and Tompkin, James and Bickel, Bernd and Pfister, Hanspeter},
isbn = {978-1-4503-3496-9},
location = {Los Angeles, CA, United States},
pages = {93 -- 100},
publisher = {ACM},
title = {{Computational design of walking automata}},
doi = {10.1145/2786784.2786803},
year = {2015},
}
@article{1506,
abstract = {Consider the square random matrix An = (aij)n,n, where {aij:= a(n)ij , i, j = 1, . . . , n} is a collection of independent real random variables with means zero and variances one. Under the additional moment condition supn max1≤i,j ≤n Ea4ij <∞, we prove Girko's logarithmic law of det An in the sense that as n→∞ log | detAn| ? (1/2) log(n-1)! d/→√(1/2) log n N(0, 1).},
author = {Bao, Zhigang and Pan, Guangming and Zhou, Wang},
journal = {Bernoulli},
number = {3},
pages = {1600 -- 1628},
publisher = {Bernoulli Society for Mathematical Statistics and Probability},
title = {{The logarithmic law of random determinant}},
doi = {10.3150/14-BEJ615},
volume = {21},
year = {2015},
}
@article{1570,
abstract = {Grounding autonomous behavior in the nervous system is a fundamental challenge for neuroscience. In particular, self-organized behavioral development provides more questions than answers. Are there special functional units for curiosity, motivation, and creativity? This paper argues that these features can be grounded in synaptic plasticity itself, without requiring any higher-level constructs. We propose differential extrinsic plasticity (DEP) as a new synaptic rule for self-learning systems and apply it to a number of complex robotic systems as a test case. Without specifying any purpose or goal, seemingly purposeful and adaptive rhythmic behavior is developed, displaying a certain level of sensorimotor intelligence. These surprising results require no systemspecific modifications of the DEP rule. They rather arise from the underlying mechanism of spontaneous symmetry breaking,which is due to the tight brain body environment coupling. The new synaptic rule is biologically plausible and would be an interesting target for neurobiological investigation. We also argue that this neuronal mechanism may have been a catalyst in natural evolution.},
author = {Der, Ralf and Martius, Georg S},
journal = {PNAS},
number = {45},
pages = {E6224 -- E6232},
publisher = {National Academy of Sciences},
title = {{Novel plasticity rule can explain the development of sensorimotor intelligence}},
doi = {10.1073/pnas.1508400112},
volume = {112},
year = {2015},
}
@article{1575,
abstract = {The immune response relies on the migration of leukocytes and on their ability to stop in precise anatomical locations to fulfil their task. How leukocyte migration and function are coordinated is unknown. Here we show that in immature dendritic cells, which patrol their environment by engulfing extracellular material, cell migration and antigen capture are antagonistic. This antagonism results from transient enrichment of myosin IIA at the cell front, which disrupts the back-to-front gradient of the motor protein, slowing down locomotion but promoting antigen capture. We further highlight that myosin IIA enrichment at the cell front requires the MHC class II-associated invariant chain (Ii). Thus, by controlling myosin IIA localization, Ii imposes on dendritic cells an intermittent antigen capture behaviour that might facilitate environment patrolling. We propose that the requirement for myosin II in both cell migration and specific cell functions may provide a general mechanism for their coordination in time and space.},
author = {Chabaud, Mélanie and Heuzé, Mélina and Bretou, Marine and Vargas, Pablo and Maiuri, Paolo and Solanes, Paola and Maurin, Mathieu and Terriac, Emmanuel and Le Berre, Maël and Lankar, Danielle and Piolot, Tristan and Adelstein, Robert and Zhang, Yingfan and Sixt, Michael K and Jacobelli, Jordan and Bénichou, Olivier and Voituriez, Raphaël and Piel, Matthieu and Lennon Duménil, Ana},
journal = {Nature Communications},
publisher = {Nature Publishing Group},
title = {{Cell migration and antigen capture are antagonistic processes coupled by myosin II in dendritic cells}},
doi = {10.1038/ncomms8526},
volume = {6},
year = {2015},
}
@article{1582,
abstract = {We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights.},
author = {Biedl, Therese and Held, Martin and Huber, Stefan and Kaaser, Dominik and Palfrader, Peter},
journal = {Computational Geometry: Theory and Applications},
number = {2},
pages = {120 -- 133},
publisher = {Elsevier},
title = {{Weighted straight skeletons in the plane}},
doi = {10.1016/j.comgeo.2014.08.006},
volume = {48},
year = {2015},
}
@article{1638,
abstract = {The mitochondrial respiratory chain, also known as the electron transport chain (ETC), is crucial to life, and energy production in the form of ATP is the main mitochondrial function. Three proton-translocating enzymes of the ETC, namely complexes I, III and IV, generate proton motive force, which in turn drives ATP synthase (complex V). The atomic structures and basic mechanisms of most respiratory complexes have previously been established, with the exception of complex I, the largest complex in the ETC. Recently, the crystal structure of the entire complex I was solved using a bacterial enzyme. The structure provided novel insights into the core architecture of the complex, the electron transfer and proton translocation pathways, as well as the mechanism that couples these two processes.},
author = {Sazanov, Leonid A},
journal = {Nature Reviews Molecular Cell Biology},
number = {6},
pages = {375 -- 388},
publisher = {Nature Publishing Group},
title = {{A giant molecular proton pump: structure and mechanism of respiratory complex I}},
doi = {10.1038/nrm3997},
volume = {16},
year = {2015},
}
@inproceedings{1645,
abstract = {Secret-key constructions are often proved secure in a model where one or more underlying components are replaced by an idealized oracle accessible to the attacker. This model gives rise to information-theoretic security analyses, and several advances have been made in this area over the last few years. This paper provides a systematic overview of what is achievable in this model, and how existing works fit into this view.},
author = {Gazi, Peter and Tessaro, Stefano},
booktitle = {2015 IEEE Information Theory Workshop},
location = {Jerusalem, Israel},
publisher = {IEEE},
title = {{Secret-key cryptography from ideal primitives: A systematic verview}},
doi = {10.1109/ITW.2015.7133163},
year = {2015},
}
@inproceedings{1652,
abstract = {We develop new theoretical tools for proving lower-bounds on the (amortized) complexity of certain functions in models of parallel computation. We apply the tools to construct a class of functions with high amortized memory complexity in the parallel Random Oracle Model (pROM); a variant of the standard ROM allowing for batches of simultaneous queries. In particular we obtain a new, more robust, type of Memory-Hard Functions (MHF); a security primitive which has recently been gaining acceptance in practice as an effective means of countering brute-force attacks on security relevant functions. Along the way we also demonstrate an important shortcoming of previous definitions of MHFs and give a new definition addressing the problem. The tools we develop represent an adaptation of the powerful pebbling paradigm (initially introduced by Hewitt and Paterson [HP70] and Cook [Coo73]) to a simple and intuitive parallel setting. We define a simple pebbling game Gp over graphs which aims to abstract parallel computation in an intuitive way. As a conceptual contribution we define a measure of pebbling complexity for graphs called cumulative complexity (CC) and show how it overcomes a crucial shortcoming (in the parallel setting) exhibited by more traditional complexity measures used in the past. As a main technical contribution we give an explicit construction of a constant in-degree family of graphs whose CC in Gp approaches maximality to within a polylogarithmic factor for any graph of equal size (analogous to the graphs of Tarjan et. al. [PTC76, LT82] for sequential pebbling games). Finally, for a given graph G and related function fG, we derive a lower-bound on the amortized memory complexity of fG in the pROM in terms of the CC of G in the game Gp.},
author = {Alwen, Joel F and Serbinenko, Vladimir},
booktitle = {Proceedings of the 47th annual ACM symposium on Theory of computing},
location = {Portland, OR, United States},
pages = {595 -- 603},
publisher = {ACM},
title = {{High parallel complexity graphs and memory-hard functions}},
doi = {10.1145/2746539.2746622},
year = {2015},
}
@inproceedings{1626,
abstract = {This paper introduces "OmniAD," a novel data-driven pipeline to model and acquire the aerodynamics of three-dimensional rigid objects. Traditionally, aerodynamics are examined through elaborate wind tunnel experiments or expensive fluid dynamics computations, and are only measured for a small number of discrete wind directions. OmniAD allows the evaluation of aerodynamic forces, such as drag and lift, for any incoming wind direction using a novel representation based on spherical harmonics. Our datadriven technique acquires the aerodynamic properties of an object simply by capturing its falling motion using a single camera. Once model parameters are estimated, OmniAD enables realistic realtime simulation of rigid bodies, such as the tumbling and gliding of leaves, without simulating the surrounding air. In addition, we propose an intuitive user interface based on OmniAD to interactively design three-dimensional kites that actually fly. Various nontraditional kites were designed to demonstrate the physical validity of our model.},
author = {Martin, Tobias and Umetani, Nobuyuki and Bickel, Bernd},
location = {Los Angeles, CA, United States},
number = {4},
publisher = {ACM},
title = {{OmniAD: Data-driven omni-directional aerodynamics}},
doi = {10.1145/2766919},
volume = {34},
year = {2015},
}
@article{1695,
abstract = {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.},
author = {Kaczmarczyk, Jan and Schickling, Tobias and Bünemann, Jörg},
journal = {Physica Status Solidi (B): Basic Solid State Physics},
number = {9},
pages = {2059 -- 2071},
publisher = {Wiley},
title = {{Evaluation techniques for Gutzwiller wave functions in finite dimensions}},
doi = {10.1002/pssb.201552082},
volume = {252},
year = {2015},
}
@article{1703,
abstract = {Vegetation clearing and land-use change have depleted many natural plant communities to the point where restoration is required. A major impediment to the success of rebuilding complex vegetation communities is having regular access to sufficient quantities of high-quality seed. Seed-production areas (SPAs) can help generate this seed, but these must be underpinned by a broad genetic base to maximise the evolutionary potential of restored populations. However, genetic bottlenecks can occur at the collection, establishment and production stages in SPAs, requiring genetic evaluation. This is especially relevant for species that may take many years before a return on SPA investment is realised. Two recently established yellow box (Eucalyptus melliodora A.Cunn. ex Schauer, Myrtaceae) SPAs were evaluated to determine whether genetic bottlenecks had occurred between seed collection and SPA establishment. No evidence was found to suggest that a significant loss of genetic diversity had occurred at this stage, although there was a significant difference in diversity between the two SPAs. Complex population genetic structure was also observed in the seed used to source the SPAs, with up to eight groups identified. Plant survival in the SPAs was influenced by seed collection location but not by SPA location and was not associated with genetic diversity. There were also no associations between genetic diversity and plant growth. These data highlighted the importance of chance events when establishing SPAs and indicated that the two yellow box SPAs are likely to provide genetically diverse seed sources for future restoration projects, especially by pooling seed from both SPAs.},
author = {Broadhurst, Linda and Fifield, Graham and Vanzella, Bindi and Pickup, Melinda},
journal = {Australian Journal of Botany},
number = {5},
pages = {455 -- 466},
publisher = {CSIRO},
title = {{An evaluation of the genetic structure of seed sources and the maintenance of genetic diversity during establishment of two yellow box (Eucalyptus melliodora) seed-production areas}},
doi = {10.1071/BT15023},
volume = {63},
year = {2015},
}
@inproceedings{1669,
abstract = {Computational notions of entropy (a.k.a. pseudoentropy) have found many applications, including leakage-resilient cryptography, deterministic encryption or memory delegation. The most important tools to argue about pseudoentropy are chain rules, which quantify by how much (in terms of quantity and quality) the pseudoentropy of a given random variable X decreases when conditioned on some other variable Z (think for example of X as a secret key and Z as information leaked by a side-channel). In this paper we give a very simple and modular proof of the chain rule for HILL pseudoentropy, improving best known parameters. Our version allows for increasing the acceptable length of leakage in applications up to a constant factor compared to the best previous bounds. As a contribution of independent interest, we provide a comprehensive study of all known versions of the chain rule, comparing their worst-case strength and limitations.},
author = {Pietrzak, Krzysztof Z and Skórski, Maciej},
location = {Guadalajara, Mexico},
pages = {81 -- 98},
publisher = {Springer},
title = {{The chain rule for HILL pseudoentropy, revisited}},
doi = {10.1007/978-3-319-22174-8_5},
volume = {9230},
year = {2015},
}
@inproceedings{1671,
abstract = {This paper studies the concrete security of PRFs and MACs obtained by keying hash functions based on the sponge paradigm. One such hash function is KECCAK, selected as NIST’s new SHA-3 standard. In contrast to other approaches like HMAC, the exact security of keyed sponges is not well understood. Indeed, recent security analyses delivered concrete security bounds which are far from existing attacks. This paper aims to close this gap. We prove (nearly) exact bounds on the concrete PRF security of keyed sponges using a random permutation. These bounds are tight for the most relevant ranges of parameters, i.e., for messages of length (roughly) l ≤ min{2n/4, 2r} blocks, where n is the state size and r is the desired output length; and for l ≤ q queries (to the construction or the underlying permutation). Moreover, we also improve standard-model bounds. As an intermediate step of independent interest, we prove tight bounds on the PRF security of the truncated CBC-MAC construction, which operates as plain CBC-MAC, but only returns a prefix of the output.},
author = {Gazi, Peter and Pietrzak, Krzysztof Z and Tessaro, Stefano},
location = {Santa Barbara, CA, United States},
pages = {368 -- 387},
publisher = {Springer},
title = {{The exact PRF security of truncation: Tight bounds for keyed sponges and truncated CBC}},
doi = {10.1007/978-3-662-47989-6_18},
volume = {9215},
year = {2015},
}
@article{1683,
abstract = {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.},
author = {Letts, Jame A and Sazanov, Leonid A},
journal = {Current Opinion in Structural Biology},
number = {8},
pages = {135 -- 145},
publisher = {Elsevier},
title = {{Gaining mass: The structure of respiratory complex I-from bacterial towards mitochondrial versions}},
doi = {10.1016/j.sbi.2015.08.008},
volume = {33},
year = {2015},
}
@article{1688,
abstract = {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.},
author = {Karasev, Roman and Kynčl, Jan and Paták, Pavel and Patakova, Zuzana and Tancer, Martin},
journal = {Discrete & Computational Geometry},
number = {3},
pages = {610 -- 636},
publisher = {Springer},
title = {{Bounds for Pach's selection theorem and for the minimum solid angle in a simplex}},
doi = {10.1007/s00454-015-9720-z},
volume = {54},
year = {2015},
}
@article{1664,
abstract = {Over a century of research into the origin of turbulence in wall-bounded shear flows has resulted in a puzzling picture in which turbulence appears in a variety of different states competing with laminar background flow. At moderate flow speeds, turbulence is confined to localized patches; it is only at higher speeds that the entire flow becomes turbulent. The origin of the different states encountered during this transition, the front dynamics of the turbulent regions and the transformation to full turbulence have yet to be explained. By combining experiments, theory and computer simulations, here we uncover a bifurcation scenario that explains the transformation to fully turbulent pipe flow and describe the front dynamics of the different states encountered in the process. Key to resolving this problem is the interpretation of the flow as a bistable system with nonlinear propagation (advection) of turbulent fronts. These findings bridge the gap between our understanding of the onset of turbulence and fully turbulent flows.},
author = {Barkley, Dwight and Song, Baofang and Vasudevan, Mukund and Lemoult, Grégoire M and Avila, Marc and Hof, Björn},
journal = {Nature},
number = {7574},
pages = {550 -- 553},
publisher = {Nature Publishing Group},
title = {{The rise of fully turbulent flow}},
doi = {10.1038/nature15701},
volume = {526},
year = {2015},
}
@article{1710,
abstract = {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 → ∞.},
author = {Akopyan, Arseniy and Plakhov, Alexander},
journal = {Society for Industrial and Applied Mathematics},
number = {4},
pages = {2754 -- 2769},
publisher = {SIAM},
title = {{Minimal resistance of curves under the single impact assumption}},
doi = {10.1137/140993843},
volume = {47},
year = {2015},
}
@article{1676,
author = {Sixt, Michael K and Raz, Erez},
journal = {Current Opinion in Cell Biology},
number = {10},
pages = {4 -- 6},
publisher = {Elsevier},
title = {{Editorial overview: Cell adhesion and migration}},
doi = {10.1016/j.ceb.2015.09.004},
volume = {36},
year = {2015},
}
@article{1734,
abstract = {Facial appearance capture is now firmly established within academic research and used extensively across various application domains, perhaps most prominently in the entertainment industry through the design of virtual characters in video games and films. While significant progress has occurred over the last two decades, no single survey currently exists that discusses the similarities, differences, and practical considerations of the available appearance capture techniques as applied to human faces. A central difficulty of facial appearance capture is the way light interacts with skin-which has a complex multi-layered structure-and the interactions that occur below the skin surface can, by definition, only be observed indirectly. In this report, we distinguish between two broad strategies for dealing with this complexity. "Image-based methods" try to exhaustively capture the exact face appearance under different lighting and viewing conditions, and then render the face through weighted image combinations. "Parametric methods" instead fit the captured reflectance data to some parametric appearance model used during rendering, allowing for a more lightweight and flexible representation but at the cost of potentially increased rendering complexity or inexact reproduction. The goal of this report is to provide an overview that can guide practitioners and researchers in assessing the tradeoffs between current approaches and identifying directions for future advances in facial appearance capture.},
author = {Klehm, Oliver and Rousselle, Fabrice and Papas, Marios and Bradley, Derek and Hery, Christophe and Bickel, Bernd and Jarosz, Wojciech and Beeler, Thabo},
journal = {Computer Graphics Forum},
number = {2},
pages = {709 -- 733},
publisher = {Wiley-Blackwell},
title = {{Recent advances in facial appearance capture}},
doi = {10.1111/cgf.12594},
volume = {34},
year = {2015},
}
@article{1789,
abstract = {Intellectual disability (ID) has an estimated prevalence of 2-3%. Due to its extreme heterogeneity, the genetic basis of ID remains elusive in many cases. Recently, whole exome sequencing (WES) studies revealed that a large proportion of sporadic cases are caused by de novo gene variants. To identify further genes involved in ID, we performed WES in 250 patients with unexplained ID and their unaffected parents and included exomes of 51 previously sequenced child-parents trios in the analysis. Exome analysis revealed de novo intragenic variants in SET domain-containing 5 (SETD5) in two patients. One patient carried a nonsense variant, and the other an 81 bp deletion located across a splice-donor site. Chromosomal microarray diagnostics further identified four de novo non-recurrent microdeletions encompassing SETD5. CRISPR/Cas9 mutation modelling of the two intragenic variants demonstrated nonsense-mediated decay of the resulting transcripts, pointing to a loss-of-function (LoF) and haploinsufficiency as the common disease-causing mechanism of intragenic SETD5 sequence variants and SETD5-containing microdeletions. In silico domain prediction of SETD5, a predicted SET domain-containing histone methyltransferase (HMT), substantiated the presence of a SET domain and identified a novel putative PHD domain, strengthening a functional link to well-known histone-modifying ID genes. All six patients presented with ID and certain facial dysmorphisms, suggesting that SETD5 sequence variants contribute substantially to the microdeletion 3p25.3 phenotype. The present report of two SETD5 LoF variants in 301 patients demonstrates a prevalence of 0.7% and thus SETD5 variants as a relatively frequent cause of ID.},
author = {Kuechler, Alma and Zink, Alexander and Wieland, Thomas and Lüdecke, Hermann and Cremer, Kirsten and Salviati, Leonardo and Magini, Pamela and Najafi, Kimia and Zweier, Christiane and Czeschik, Johanna and Aretz, Stefan and Endele, Sabine and Tamburrino, Federica and Pinato, Claudia and Clementi, Maurizio and Gundlach, Jasmin and Maylahn, Carina and Mazzanti, Laura and Wohlleber, Eva and Schwarzmayr, Thomas and Kariminejad, Roxana and Schlessinger, Avner and Wieczorek, Dagmar and Strom, Tim and Novarino, Gaia and Engels, Hartmut},
journal = {European Journal of Human Genetics},
number = {6},
pages = {753 -- 760},
publisher = {Nature Publishing Group},
title = {{Loss-of-function variants of SETD5 cause intellectual disability and the core phenotype of microdeletion 3p25.3 syndrome}},
doi = {10.1038/ejhg.2014.165},
volume = {23},
year = {2015},
}
@article{1830,
abstract = {To prevent epidemics, insect societies have evolved collective disease defences that are highly effective at curing exposed individuals and limiting disease transmission to healthy group members. Grooming is an important sanitary behaviour—either performed towards oneself (self-grooming) or towards others (allogrooming)—to remove infectious agents from the body surface of exposed individuals, but at the risk of disease contraction by the groomer. We use garden ants (Lasius neglectus) and the fungal pathogen Metarhizium as a model system to study how pathogen presence affects self-grooming and allogrooming between exposed and healthy individuals. We develop an epidemiological SIS model to explore how experimentally observed grooming patterns affect disease spread within the colony, thereby providing a direct link between the expression and direction of sanitary behaviours, and their effects on colony-level epidemiology. We find that fungus-exposed ants increase self-grooming, while simultaneously decreasing allogrooming. This behavioural modulation seems universally adaptive and is predicted to contain disease spread in a great variety of host–pathogen systems. In contrast, allogrooming directed towards pathogen-exposed individuals might both increase and decrease disease risk. Our model reveals that the effect of allogrooming depends on the balance between pathogen infectiousness and efficiency of social host defences, which are likely to vary across host–pathogen systems.},
author = {Theis, Fabian and Ugelvig, Line V and Marr, Carsten and Cremer, Sylvia},
journal = {Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences},
number = {1669},
publisher = {Royal Society, The},
title = {{Opposing effects of allogrooming on disease transmission in ant societies}},
doi = {10.1098/rstb.2014.0108},
volume = {370},
year = {2015},
}
@article{1809,
abstract = {Background: Indirect genetic effects (IGEs) occur when genes expressed in one individual alter the expression of traits in social partners. Previous studies focused on the evolutionary consequences and evolutionary dynamics of IGEs, using equilibrium solutions to predict phenotypes in subsequent generations. However, whether or not such steady states may be reached may depend on the dynamics of interactions themselves. Results: In our study, we focus on the dynamics of social interactions and indirect genetic effects and investigate how they modify phenotypes over time. Unlike previous IGE studies, we do not analyse evolutionary dynamics; rather we consider within-individual phenotypic changes, also referred to as phenotypic plasticity. We analyse iterative interactions, when individuals interact in a series of discontinuous events, and investigate the stability of steady state solutions and the dependence on model parameters, such as population size, strength, and the nature of interactions. We show that for interactions where a feedback loop occurs, the possible parameter space of interaction strength is fairly limited, affecting the evolutionary consequences of IGEs. We discuss the implications of our results for current IGE model predictions and their limitations.},
author = {Trubenova, Barbora and Novak, Sebastian and Hager, Reinmar},
journal = {PLoS One},
number = {5},
publisher = {Public Library of Science},
title = {{Indirect genetic effects and the dynamics of social interactions}},
doi = {10.1371/journal.pone.0126907},
volume = {10},
year = {2015},
}
@article{1811,
abstract = {Atomic form factors are widely used for the characterization of targets and specimens, from crystallography to biology. By using recent mathematical results, here we derive an analytical expression for the atomic form factor within the independent particle model constructed from nonrelativistic screened hydrogenic wave functions. The range of validity of this analytical expression is checked by comparing the analytically obtained form factors with the ones obtained within the Hartee-Fock method. As an example, we apply our analytical expression for the atomic form factor to evaluate the differential cross section for Rayleigh scattering off neutral atoms.},
author = {Safari, Laleh and Santos, José and Amaro, Pedro and Jänkälä, Kari and Fratini, Filippo},
journal = {Journal of Mathematical Physics},
number = {5},
publisher = {American Institute of Physics},
title = {{Analytical evaluation of atomic form factors: Application to Rayleigh scattering}},
doi = {10.1063/1.4921227},
volume = {56},
year = {2015},
}
@article{1804,
abstract = {It is known that in classical fluids turbulence typically occurs at high Reynolds numbers. But can turbulence occur at low Reynolds numbers? Here we investigate the transition to turbulence in the classic Taylor-Couette system in which the rotating fluids are manufactured ferrofluids with magnetized nanoparticles embedded in liquid carriers. We find that, in the presence of a magnetic field transverse to the symmetry axis of the system, turbulence can occur at Reynolds numbers that are at least one order of magnitude smaller than those in conventional fluids. This is established by extensive computational ferrohydrodynamics through a detailed investigation of transitions in the flow structure, and characterization of behaviors of physical quantities such as the energy, the wave number, and the angular momentum through the bifurcations. A finding is that, as the magnetic field is increased, onset of turbulence can be determined accurately and reliably. Our results imply that experimental investigation of turbulence may be feasible by using ferrofluids. Our study of transition to and evolution of turbulence in the Taylor-Couette ferrofluidic flow system provides insights into the challenging problem of turbulence control.},
author = {Altmeyer, Sebastian and Do, Younghae and Lai, Ying},
journal = {Scientific Reports},
publisher = {Nature Publishing Group},
title = {{Transition to turbulence in Taylor-Couette ferrofluidic flow}},
doi = {10.1038/srep10781},
volume = {5},
year = {2015},
}
@inproceedings{1859,
abstract = {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. },
author = {Shah, Neel and Kolmogorov, Vladimir and Lampert, Christoph},
location = {Boston, MA, USA},
pages = {2737 -- 2745},
publisher = {IEEE},
title = {{A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle}},
doi = {10.1109/CVPR.2015.7298890},
year = {2015},
}
@article{1861,
abstract = {Continuous-time Markov chains are commonly used in practice for modeling biochemical reaction networks in which the inherent randomness of themolecular interactions cannot be ignored. This has motivated recent research effort into methods for parameter inference and experiment design for such models. The major difficulty is that such methods usually require one to iteratively solve the chemical master equation that governs the time evolution of the probability distribution of the system. This, however, is rarely possible, and even approximation techniques remain limited to relatively small and simple systems. An alternative explored in this article is to base methods on only some low-order moments of the entire probability distribution. We summarize the theory behind such moment-based methods for parameter inference and experiment design and provide new case studies where we investigate their performance.},
author = {Ruess, Jakob and Lygeros, John},
journal = {ACM Transactions on Modeling and Computer Simulation},
number = {2},
publisher = {ACM},
title = {{Moment-based methods for parameter inference and experiment design for stochastic biochemical reaction networks}},
doi = {10.1145/2688906},
volume = {25},
year = {2015},
}
@article{1866,
author = {Henzinger, Thomas A and Raskin, Jean},
journal = {Communications of the ACM},
number = {2},
pages = {86--86},
publisher = {ACM},
title = {{The equivalence problem for finite automata: Technical perspective}},
doi = {10.1145/2701001},
volume = {58},
year = {2015},
}
@article{1873,
abstract = {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.},
author = {Chatterjee, Krishnendu and Chmelik, Martin},
journal = {Artificial Intelligence},
pages = {46 -- 72},
publisher = {Elsevier},
title = {{POMDPs under probabilistic semantics}},
doi = {10.1016/j.artint.2014.12.009},
volume = {221},
year = {2015},
}
@article{1878,
abstract = {Petrocoptis is a small genus of chasmophytic plants endemic to the Iberian Peninsula, with some localized populations in the French Pyrenees. Within the genus, a dozen species have been recognized based on morphological diversity, most of them with limited distribution area, in small populations and frequently with potential threats to their survival. To date, however, a molecular evaluation of the current systematic treatments has not been carried out. The aim of the present study is to infer phylogenetic relationships among its subordinate taxa by using plastidial rps16 intron and nuclear internal transcribed spacer (ITS) DNA sequences; and evaluate the phylogenetic placement of the genus Petrocoptis within the family Caryophyllaceae. The monophyly of Petrocoptis is supported by both ITS and rps16 intron sequence analyses. Furthermore, time estimates using BEAST analyses indicate a Middle to Late Miocene diversification (10.59 Myr, 6.44–15.26 Myr highest posterior densities [HPD], for ITS; 14.30 Myr, 8.61–21.00 Myr HPD, for rps16 intron).},
author = {Cires Rodriguez, Eduardo and Prieto, José},
journal = {Journal of Plant Research},
number = {2},
pages = {223 -- 238},
publisher = {Springer},
title = {{Phylogenetic relationships of Petrocoptis A. Braun ex Endl. (Caryophyllaceae), a discussed genus from the Iberian Peninsula}},
doi = {10.1007/s10265-014-0691-6},
volume = {128},
year = {2015},
}
@article{1880,
abstract = {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},
author = {Könenberg, Martin and Moser, Thomas and Seiringer, Robert and Yngvason, Jakob},
journal = {New Journal of Physics},
publisher = {IOP Publishing Ltd.},
title = {{Superfluid behavior of a Bose-Einstein condensate in a random potential}},
doi = {10.1088/1367-2630/17/1/013022},
volume = {17},
year = {2015},
}
@article{1885,
abstract = {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. },
author = {Tkacik, Gasper and Dubuis, Julien and Petkova, Mariela and Gregor, Thomas},
journal = {Genetics},
number = {1},
pages = {39 -- 59},
publisher = {Genetics Society of America},
title = {{Positional information, positional error, and readout precision in morphogenesis: A mathematical framework}},
doi = {10.1534/genetics.114.171850},
volume = {199},
year = {2015},
}
@article{1993,
abstract = {The fitness effects of symbionts on their hosts can be context-dependent, with usually benign symbionts causing detrimental effects when their hosts are stressed, or typically parasitic symbionts providing protection towards their hosts (e.g. against pathogen infection). Here, we studied the novel association between the invasive garden ant Lasius neglectus and its fungal ectosymbiont Laboulbenia formicarum for potential costs and benefits. We tested ants with different Laboulbenia levels for their survival and immunity under resource limitation and exposure to the obligate killing entomopathogen Metarhizium brunneum. While survival of L. neglectus workers under starvation was significantly decreased with increasing Laboulbenia levels, host survival under Metarhizium exposure increased with higher levels of the ectosymbiont, suggesting a symbiont-mediated anti-pathogen protection, which seems to be driven mechanistically by both improved sanitary behaviours and an upregulated immune system. Ants with high Laboulbenia levels showed significantly longer self-grooming and elevated expression of immune genes relevant for wound repair and antifungal responses (β-1,3-glucan binding protein, Prophenoloxidase), compared with ants carrying low Laboulbenia levels. This suggests that the ectosymbiont Laboulbenia formicarum weakens its ant host by either direct resource exploitation or the costs of an upregulated behavioural and immunological response, which, however, provides a prophylactic protection upon later exposure to pathogens. },
author = {Konrad, Matthias and Grasse, Anna V and Tragust, Simon and Cremer, Sylvia},
journal = {Proceedings of the Royal Society of London Series B Biological Sciences},
number = {1799},
publisher = {Royal Society},
title = {{Anti-pathogen protection versus survival costs mediated by an ectosymbiont in an ant host}},
doi = {10.1098/rspb.2014.1976},
volume = {282},
year = {2015},
}
@article{1847,
author = {Grones, Peter and Friml, Jiřĺ},
journal = {Molecular Plant},
number = {3},
pages = {356 -- 358},
publisher = {Elsevier},
title = {{ABP1: Finally docking}},
doi = {10.1016/j.molp.2014.12.013},
volume = {8},
year = {2015},
}
@article{2030,
abstract = {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.},
author = {Shi, Liang and Rampp, Markus and Hof, Björn and Avila, Marc},
journal = {Computers and Fluids},
number = {1},
pages = {1 -- 11},
publisher = {Elsevier},
title = {{A hybrid MPI-OpenMP parallel implementation for pseudospectral simulations with application to Taylor-Couette flow}},
doi = {10.1016/j.compfluid.2014.09.021},
volume = {106},
year = {2015},
}
@article{2035,
abstract = {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.
},
author = {Edelsbrunner, Herbert and Jablonski, Grzegorz and Mrozek, Marian},
journal = {Foundations of Computational Mathematics},
number = {5},
pages = {1213 -- 1244},
publisher = {Springer},
title = {{The persistent homology of a self-map}},
doi = {10.1007/s10208-014-9223-y},
volume = {15},
year = {2015},
}
@article{2085,
abstract = {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. },
author = {Nam, Phan and Seiringer, Robert},
journal = {Archive for Rational Mechanics and Analysis},
number = {2},
pages = {381 -- 417},
publisher = {Springer},
title = {{Collective excitations of Bose gases in the mean-field regime}},
doi = {10.1007/s00205-014-0781-6},
volume = {215},
year = {2015},
}
@article{259,
abstract = {The Hasse principle and weak approximation is established for non-singular cubic hypersurfaces X over the function field },
author = {Timothy Browning and Vishe, Pankaj},
journal = {Geometric and Functional Analysis},
number = {3},
pages = {671 -- 732},
publisher = {Birkhäuser},
title = {{Rational points on cubic hypersurfaces over F_q(t) }},
doi = {10.1007/s00039-015-0328-5},
volume = {25},
year = {2015},
}
@article{362,
abstract = {Monodisperse Pd2Sn nanorods with tuned size and aspect ratio were prepared by co-reduction of metal salts in the presence of trioctylphosphine, amine, and chloride ions. Asymmetric Pd2Sn nanostructures were achieved by the selective desorption of a surfactant mediated by chlorine ions. A preliminary evaluation of the geometry influence on catalytic properties evidenced Pd2Sn nanorods to have improved catalytic performance. In view of these results, Pd2Sn nanorods were also evaluated for water denitration. },
author = {Lu, ZhiShan and Ibanez, Maria and Antolín, Ana M and Genç, Aziz and Shavel, Alexey and Contreras, Sandra and Medina, Francesc and Arbiol, Jordi and Cabot, Andreu},
journal = {Langmuir},
number = {13},
pages = {3952 -- 3957},
publisher = {American Chemical Society},
title = {{Size and aspect ratio control of Pd inf 2 inf Sn nanorods and their water denitration properties}},
doi = {10.1021/la504906q},
volume = {31},
year = {2015},
}
@misc{5440,
abstract = {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.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Nowak, Martin},
issn = {2664-1690},
pages = {18},
publisher = {IST Austria},
title = {{The complexity of evolutionary games on graphs}},
doi = {10.15479/AT:IST-2015-323-v2-2},
year = {2015},
}
@inproceedings{778,
abstract = {Several Hybrid Transactional Memory (HyTM) schemes have recently been proposed to complement the fast, but best-effort nature of Hardware Transactional Memory (HTM) with a slow, reliable software backup. However, the costs of providing concurrency between hardware and software transactions in HyTM are still not well understood. In this paper, we propose a general model for HyTM implementations, which captures the ability of hardware transactions to buffer memory accesses. The model allows us to formally quantify and analyze the amount of overhead (instrumentation) caused by the potential presence of software transactions.We prove that (1) it is impossible to build a strictly serializable HyTM implementation that has both uninstrumented reads and writes, even for very weak progress guarantees, and (2) the instrumentation cost incurred by a hardware transaction in any progressive opaque HyTM is linear in the size of the transaction’s data set.We further describe two implementations which exhibit optimal instrumentation costs for two different progress conditions. In sum, this paper proposes the first formal HyTM model and captures for the first time the trade-off between the degree of hardware-software TM concurrency and the amount of instrumentation overhead.},
author = {Alistarh, Dan-Adrian and Kopinsky, Justin and Kuznetsov, Petr and Ravi, Srivatsan and Shavit, Nir},
pages = {185 -- 199},
publisher = {Springer},
title = {{Inherent limitations of hybrid transactional memory}},
doi = {10.1007/978-3-662-48653-5_13},
volume = {9363},
year = {2015},
}
@inproceedings{780,
abstract = {Population protocols are networks of finite-state agents, interacting randomly, and updating their states using simple rules. Despite their extreme simplicity, these systems have been shown to cooperatively perform complex computational tasks, such as simulating register machines to compute standard arithmetic functions. The election of a unique leader agent is a key requirement in such computational constructions. Yet, the fastest currently known population protocol for electing a leader only has linear convergence time, and it has recently been shown that no population protocol using a constant number of states per node may overcome this linear bound. In this paper, we give the first population protocol for leader election with polylogarithmic convergence time, using polylogarithmic memory states per node. The protocol structure is quite simple: each node has an associated value, and is either a leader (still in contention) or a minion (following some leader). A leader keeps incrementing its value and “defeats” other leaders in one-to-one interactions, and will drop from contention and become a minion if it meets a leader with higher value. Importantly, a leader also drops out if it meets a minion with higher absolute value. While these rules are quite simple, the proof that this algorithm achieves polylogarithmic convergence time is non-trivial. In particular, the argument combines careful use of concentration inequalities with anti-concentration bounds, showing that the leaders’ values become spread apart as the execution progresses, which in turn implies that straggling leaders get quickly eliminated. We complement our analysis with empirical results, showing that our protocol converges extremely fast, even for large network sizes.},
author = {Alistarh, Dan-Adrian and Gelashvili, Rati},
pages = {479 -- 491},
publisher = {Springer},
title = {{Polylogarithmic-time leader election in population protocols}},
doi = {10.1007/978-3-662-47666-6_38},
volume = {9135},
year = {2015},
}
@article{886,
abstract = {The factors that determine the tempo and mode of protein evolution continue to be a central question in molecular evolution. Traditionally, studies of protein evolution focused on the rates of amino acid substitutions. More recently, with the availability of sequence data and advanced experimental techniques, the focus of attention has shifted toward the study of evolutionary trajectories and the overall layout of protein fitness landscapes. In this review we describe the effect of epistasis on the topology of evolutionary pathways that are likely to be found in fitness landscapes and develop a simple theory to connect the number of maladapted genotypes to the topology of fitness landscapes with epistatic interactions. Finally, we review recent studies that have probed the extent of epistatic interactions and have begun to chart the fitness landscapes in protein sequence space.},
author = {Kondrashov, Dmitry A and Fyodor Kondrashov},
journal = {Trends in Genetics},
number = {1},
pages = {24 -- 33},
publisher = {Elsevier},
title = {{Topological features of rugged fitness landscapes in sequence space}},
doi = {10.1016/j.tig.2014.09.009},
volume = {31},
year = {2015},
}
@article{906,
abstract = {The origin and evolution of novel biochemical functions remains one of the key questions in molecular evolution. We study recently emerged methacrylate reductase function that is thought to have emerged in the last century and reported in Geobacter sulfurreducens strain AM-1. We report the sequence and study the evolution of the operon coding for the flavin-containing methacrylate reductase (Mrd) and tetraheme cytochrome (Mcc) in the genome of G. sulfurreducens AM-1. Different types of signal peptides in functionally interlinked proteins Mrd and Mcc suggest a possible complex mechanism of biogenesis for chromoproteids of the methacrylate redox system. The homologs of the Mrd and Mcc sequence found in δ-Proteobacteria and Deferribacteres are also organized into an operon and their phylogenetic distribution suggested that these two genes tend to be horizontally transferred together. Specifically, the mrd and mcc genes from G. sulfurreducens AM-1 are not monophyletic with any of the homologs found in other Geobacter genomes. The acquisition of methacrylate reductase function by G. sulfurreducens AM-1 appears linked to a horizontal gene transfer event. However, the new function of the products of mrd and mcc may have evolved either prior or subsequent to their acquisition by G. sulfurreducens AM-1.},
author = {Arkhipova, Oksana V and Meer, Margarita V and Mikoulinskaia, Galina V and Zakharova, Marina V and Galushko, Alexander S and Akimenko, Vasilii K and Fyodor Kondrashov},
journal = {PLoS One},
number = {5},
publisher = {Public Library of Science},
title = {{Recent origin of the methacrylate redox system in Geobacter sulfurreducens AM-1 through horizontal gene transfer}},
doi = {10.1371/journal.pone.0125888},
volume = {10},
year = {2015},
}
@article{848,
abstract = {The nature of factors governing the tempo and mode of protein evolution is a fundamental issue in evolutionary biology. Specifically, whether or not interactions between different sites, or epistasis, are important in directing the course of evolution became one of the central questions. Several recent reports have scrutinized patterns of long-term protein evolution claiming them to be compatible only with an epistatic fitness landscape. However, these claims have not yet been substantiated with a formal model of protein evolution. Here, we formulate a simple covarion-like model of protein evolution focusing on the rate at which the fitness impact of amino acids at a site changes with time. We then apply the model to the data on convergent and divergent protein evolution to test whether or not the incorporation of epistatic interactions is necessary to explain the data. We find that convergent evolution cannot be explained without the incorporation of epistasis and the rate at which an amino acid state switches from being acceptable at a site to being deleterious is faster than the rate of amino acid substitution. Specifically, for proteins that have persisted in modern prokaryotic organisms since the last universal common ancestor for one amino acid substitution approximately ten amino acid states switch from being accessible to being deleterious, or vice versa. Thus, molecular evolution can only be perceived in the context of rapid turnover of which amino acids are available for evolution.},
author = {Usmanova, Dinara and Ferretti, Luca and Povolotskaya, Inna and Vlasov, Peter and Kondrashov, Fyodor},
journal = {Molecular Biology and Evolution},
number = {2},
pages = {542 -- 554},
publisher = {Oxford University Press},
title = {{A model of substitution trajectories in sequence space and long-term protein evolution}},
doi = {10.1093/molbev/msu318},
volume = {32},
year = {2015},
}
@inproceedings{1633,
abstract = {We present a method for simulating brittle fracture under the assumptions of quasi-static linear elastic fracture mechanics (LEFM). Using the boundary element method (BEM) and Lagrangian crack-fronts, we produce highly detailed fracture surfaces. The computational cost of the BEM is alleviated by using a low-resolution mesh and interpolating the resulting stress intensity factors when propagating the high-resolution crack-front.
Our system produces physics-based fracture surfaces with high spatial and temporal resolution, taking spatial variation of material toughness and/or strength into account. It also allows for crack initiation to be handled separately from crack propagation, which is not only more reasonable from a physics perspective, but can also be used to control the simulation.
Separating the resolution of the crack-front from the resolution of the computational mesh increases the efficiency and therefore the amount of visual detail on the resulting fracture surfaces. The BEM also allows us to re-use previously computed blocks of the system matrix.},
author = {Hahn, David and Wojtan, Christopher J},
location = {Los Angeles, CA, United States},
number = {4},
publisher = {ACM},
title = {{High-resolution brittle fracture simulation with boundary elements}},
doi = {10.1145/2766896},
volume = {34},
year = {2015},
}
@article{982,
abstract = {We propose a new approach to probing ergodicity and its breakdown in one-dimensional quantum manybody systems based on their response to a local perturbation. We study the distribution of matrix elements of a local operator between the system's eigenstates, finding a qualitatively different behavior in the manybody localized (MBL) and ergodic phases. To characterize how strongly a local perturbation modifies the eigenstates, we introduce the parameter g(L) = (In (Vnm/δ)) which represents the disorder-averaged ratio of a typical matrix element of a local operator V to energy level spacing δ this parameter is reminiscent of the Thouless conductance in the single-particle localization. We show that the parameter g(L) decreases with system size L in the MBL phase and grows in the ergodic phase. We surmise that the delocalization transition occurs when g(L) is independent of system size, g(L)=gc ~ 1. We illustrate our approach by studying the many-body localization transition and resolving the many-body mobility edge in a disordered one-dimensional XXZ spin-1=2 chain using exact diagonalization and time-evolving block-decimation methods. Our criterion for the MBL transition gives insights into microscopic details of transition. Its direct physical consequences, in particular, logarithmically slow transport at the transition and extensive entanglement entropy of the eigenstates, are consistent with recent renormalization-group predictions.},
author = {Maksym Serbyn and Papić, Zlatko and Abanin, Dmitry A},
journal = {Physical Review X},
number = {4},
publisher = {American Physical Society},
title = {{Criterion for many-body localization-delocalization phase transition}},
doi = {10.1103/PhysRevX.5.041047},
volume = {5},
year = {2015},
}
@inproceedings{1498,
abstract = {Fault-tolerant distributed algorithms play an important role in many critical/high-availability applications. These algorithms are notoriously difficult to implement correctly, due to asynchronous communication and the occurrence of faults, such as the network dropping messages or computers crashing. Nonetheless there is surprisingly little language and verification support to build distributed systems based on fault-tolerant algorithms. In this paper, we present some of the challenges that a designer has to overcome to implement a fault-tolerant distributed system. Then we review different models that have been proposed to reason about distributed algorithms and sketch how such a model can form the basis for a domain-specific programming language. Adopting a high-level programming model can simplify the programmer's life and make the code amenable to automated verification, while still compiling to efficiently executable code. We conclude by summarizing the current status of an ongoing language design and implementation project that is based on this idea.},
author = {Dragoi, Cezara and Henzinger, Thomas A and Zufferey, Damien},
isbn = {978-3-939897-80-4 },
location = {Asilomar, CA, United States},
pages = {90 -- 102},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{The need for language support for fault-tolerant distributed systems}},
doi = {10.4230/LIPIcs.SNAPL.2015.90},
volume = {32},
year = {2015},
}
@article{1501,
abstract = {We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability. We introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph algorithms with quadratic complexity to compute the simulation relation. We present an automated technique for assume-guarantee style reasoning for compositional analysis of two-player games by giving a counterexample guided abstraction-refinement approach to compute our new simulation relation. We show a tight link between two-player games and MDPs, and as a consequence the results for games are lifted to MDPs with qualitative properties. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. },
author = {Chatterjee, Krishnendu and Chmelik, Martin and Daca, Przemyslaw},
journal = {Formal Methods in System Design},
number = {2},
pages = {230 -- 264},
publisher = {Springer},
title = {{CEGAR for compositional analysis of qualitative properties in Markov decision processes}},
doi = {10.1007/s10703-015-0235-2},
volume = {47},
year = {2015},
}
@inproceedings{1594,
abstract = {Quantitative extensions of temporal logics have recently attracted significant attention. In this work, we study frequency LTL (fLTL), an extension of LTL which allows to speak about frequencies of events along an execution. Such an extension is particularly useful for probabilistic systems that often cannot fulfil strict qualitative guarantees on the behaviour. It has been recently shown that controller synthesis for Markov decision processes and fLTL is decidable when all the bounds on frequencies are 1. As a step towards a complete quantitative solution, we show that the problem is decidable for the fragment fLTL\GU, where U does not occur in the scope of G (but still F can). Our solution is based on a novel translation of such quantitative formulae into equivalent deterministic automata.},
author = {Forejt, Vojtěch and Krčál, Jan and Kretinsky, Jan},
location = {Suva, Fiji},
pages = {162 -- 177},
publisher = {Springer},
title = {{Controller synthesis for MDPs and frequency LTL\GU}},
doi = {10.1007/978-3-662-48899-7_12},
volume = {9450},
year = {2015},
}
@article{1537,
abstract = {3D amoeboid cell migration is central to many developmental and disease-related processes such as cancer metastasis. Here, we identify a unique prototypic amoeboid cell migration mode in early zebrafish embryos, termed stable-bleb migration. Stable-bleb cells display an invariant polarized balloon-like shape with exceptional migration speed and persistence. Progenitor cells can be reversibly transformed into stable-bleb cells irrespective of their primary fate and motile characteristics by increasing myosin II activity through biochemical or mechanical stimuli. Using a combination of theory and experiments, we show that, in stable-bleb cells, cortical contractility fluctuations trigger a stochastic switch into amoeboid motility, and a positive feedback between cortical flows and gradients in contractility maintains stable-bleb cell polarization. We further show that rearward cortical flows drive stable-bleb cell migration in various adhesive and non-adhesive environments, unraveling a highly versatile amoeboid migration phenotype.},
author = {Ruprecht, Verena and Wieser, Stefan and Callan Jones, Andrew and Smutny, Michael and Morita, Hitoshi and Sako, Keisuke and Barone, Vanessa and Ritsch Marte, Monika and Sixt, Michael K and Voituriez, Raphaël and Heisenberg, Carl-Philipp J},
journal = {Cell},
number = {4},
pages = {673 -- 685},
publisher = {Cell Press},
title = {{Cortical contractility triggers a stochastic switch to fast amoeboid cell motility}},
doi = {10.1016/j.cell.2015.01.008},
volume = {160},
year = {2015},
}
@article{1640,
abstract = {Auxin and cytokinin are key endogenous regulators of plant development. Although cytokinin-mediated modulation of auxin distribution is a developmentally crucial hormonal interaction, its molecular basis is largely unknown. Here we show a direct regulatory link between cytokinin signalling and the auxin transport machinery uncovering a mechanistic framework for cytokinin-auxin cross-talk. We show that the CYTOKININ RESPONSE FACTORS (CRFs), transcription factors downstream of cytokinin perception, transcriptionally control genes encoding PIN-FORMED (PIN) auxin transporters at a specific PIN CYTOKININ RESPONSE ELEMENT (PCRE) domain. Removal of this cis-regulatory element effectively uncouples PIN transcription from the CRF-mediated cytokinin regulation and attenuates plant cytokinin sensitivity. We propose that CRFs represent a missing cross-talk component that fine-tunes auxin transport capacity downstream of cytokinin signalling to control plant development.},
author = {Šimášková, Mária and O'Brien, José and Khan-Djamei, Mamoona and Van Noorden, Giel and Ötvös, Krisztina and Vieten, Anne and De Clercq, Inge and Van Haperen, Johanna and Cuesta, Candela and Hoyerová, Klára and Vanneste, Steffen and Marhavy, Peter and Wabnik, Krzysztof T and Van Breusegem, Frank and Nowack, Moritz and Murphy, Angus and Friml, Jiřĺ and Weijers, Dolf and Beeckman, Tom and Benková, Eva},
journal = {Nature Communications},
publisher = {Nature Publishing Group},
title = {{Cytokinin response factors regulate PIN-FORMED auxin transporters}},
doi = {10.1038/ncomms9717},
volume = {6},
year = {2015},
}
@article{1614,
abstract = {GABAergic perisoma-inhibiting fast-spiking interneurons (PIIs) effectively control the activity of large neuron populations by their wide axonal arborizations. It is generally assumed that the output of one PII to its target cells is strong and rapid. Here, we show that, unexpectedly, both strength and time course of PII-mediated perisomatic inhibition change with distance between synaptically connected partners in the rodent hippocampus. Synaptic signals become weaker due to lower contact numbers and decay more slowly with distance, very likely resulting from changes in GABAA receptor subunit composition. When distance-dependent synaptic inhibition is introduced to a rhythmically active neuronal network model, randomly driven principal cell assemblies are strongly synchronized by the PIIs, leading to higher precision in principal cell spike times than in a network with uniform synaptic inhibition. },
author = {Strüber, Michael and Jonas, Peter M and Bartos, Marlene},
journal = {PNAS},
number = {4},
pages = {1220 -- 1225},
publisher = {National Academy of Sciences},
title = {{Strength and duration of perisomatic GABAergic inhibition depend on distance between synaptically connected cells}},
doi = {10.1073/pnas.1412996112},
volume = {112},
year = {2015},
}
@inproceedings{1835,
abstract = {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.},
author = {Giacobbe, Mirco and Guet, Calin C and Gupta, Ashutosh and Henzinger, Thomas A and Paixao, Tiago and Petrov, Tatjana},
location = {London, United Kingdom},
pages = {469 -- 483},
publisher = {Springer},
title = {{Model checking gene regulatory networks}},
doi = {10.1007/978-3-662-46681-0_47},
volume = {9035},
year = {2015},
}
@article{1823,
abstract = {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.},
author = {Chevereau, Guillaume and Bollenbach, Mark Tobias},
journal = {Molecular Systems Biology},
number = {4},
publisher = {Nature Publishing Group},
title = {{Systematic discovery of drug interaction mechanisms}},
doi = {10.15252/msb.20156098},
volume = {11},
year = {2015},
}
@inproceedings{1690,
abstract = {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.},
author = {Bak, Stanley and Bogomolov, Sergiy and Johnson, Taylor},
location = {Seattle, WA, United States},
pages = {128 -- 133},
publisher = {Springer},
title = {{HYST: A source transformation and translation tool for hybrid automaton models}},
doi = {10.1145/2728606.2728630},
year = {2015},
}
@inproceedings{1657,
abstract = {We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. There exist 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 optimization with respect to both objectives at once, thus unifying the existing semantics. Precisely, the goal is to optimize the expectation while ensuring the satisfaction constraint. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., Ensure certain probabilistic guarantee). Our main results are as follows: First, we present algorithms for the decision problems, 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. Second, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem. },
author = {Chatterjee, Krishnendu and Komárková, Zuzana and Kretinsky, Jan},
location = {Kyoto, Japan},
pages = {244 -- 256},
publisher = {IEEE},
title = {{Unifying two views on multiple mean-payoff objectives in Markov decision processes}},
doi = {10.1109/LICS.2015.32},
year = {2015},
}
@misc{5438,
abstract = {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. },
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Ibsen-Jensen, Rasmus and Otop, Jan},
issn = {2664-1690},
pages = {15},
publisher = {IST Austria},
title = {{Edit distance for pushdown automata}},
doi = {10.15479/AT:IST-2015-334-v1-1},
year = {2015},
}
@article{1602,
abstract = {Interprocedural analysis is at the heart of numerous applications in programming languages, such as alias analysis, constant propagation, etc. Recursive state machines (RSMs) are standard models for interprocedural analysis. We consider a general framework with RSMs where the transitions are labeled from a semiring, and path properties are algebraic with semiring operations. RSMs with algebraic path properties can model interprocedural dataflow analysis problems, the shortest path problem, the most probable path problem, etc. The traditional algorithms for interprocedural analysis focus on path properties where the starting point is fixed as the entry point of a specific method. In this work, we consider possible multiple queries as required in many applications such as in alias analysis. The study of multiple queries allows us to bring in a very important algorithmic distinction between the resource usage of the one-time preprocessing vs for each individual query. The second aspect that we consider is that the control flow graphs for most programs have constant treewidth. Our main contributions are simple and implementable algorithms that supportmultiple queries for algebraic path properties for RSMs that have constant treewidth. Our theoretical results show that our algorithms have small additional one-time preprocessing, but can answer subsequent queries significantly faster as compared to the current best-known solutions for several important problems, such as interprocedural reachability and shortest path. We provide a prototype implementation for interprocedural reachability and intraprocedural shortest path that gives a significant speed-up on several benchmarks.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas and Goyal, Prateesh},
journal = {ACM SIGPLAN Notices},
location = {Mumbai, India},
number = {1},
pages = {97 -- 109},
publisher = {ACM},
title = {{Faster algorithms for algebraic path properties in recursive state machines with constant treewidth}},
doi = {10.1145/2676726.2676979},
volume = {50},
year = {2015},
}
@inproceedings{1607,
abstract = {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 ϵ 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|))=O(n⋅log(n⋅W)), when the output is ab, as compared to the previously best known algorithm with running time O(n2⋅log(n⋅W)). Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O(n2⋅m) time and the associated decision problem can be solved in O(n⋅m) time, improving the previous known O(n3⋅m⋅log(n⋅W)) and O(n2⋅m) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O(n⋅logn) time, improving the previous known O(n4⋅log(n⋅W)) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas},
location = {San Francisco, CA, USA},
pages = {140 -- 157},
publisher = {Springer},
title = {{Faster algorithms for quantitative verification in constant treewidth graphs}},
doi = {10.1007/978-3-319-21690-4_9},
volume = {9206},
year = {2015},
}
@article{1619,
abstract = {The emergence of drug resistant pathogens is a serious public health problem. It is a long-standing goal to predict rates of resistance evolution and design optimal treatment strategies accordingly. To this end, it is crucial to reveal the underlying causes of drug-specific differences in the evolutionary dynamics leading to resistance. However, it remains largely unknown why the rates of resistance evolution via spontaneous mutations and the diversity of mutational paths vary substantially between drugs. Here we comprehensively quantify the distribution of fitness effects (DFE) of mutations, a key determinant of evolutionary dynamics, in the presence of eight antibiotics representing the main modes of action. Using precise high-throughput fitness measurements for genome-wide Escherichia coli gene deletion strains, we find that the width of the DFE varies dramatically between antibiotics and, contrary to conventional wisdom, for some drugs the DFE width is lower than in the absence of stress. We show that this previously underappreciated divergence in DFE width among antibiotics is largely caused by their distinct drug-specific dose-response characteristics. Unlike the DFE, the magnitude of the changes in tolerated drug concentration resulting from genome-wide mutations is similar for most drugs but exceptionally small for the antibiotic nitrofurantoin, i.e., mutations generally have considerably smaller resistance effects for nitrofurantoin than for other drugs. A population genetics model predicts that resistance evolution for drugs with this property is severely limited and confined to reproducible mutational paths. We tested this prediction in laboratory evolution experiments using the “morbidostat”, a device for evolving bacteria in well-controlled drug environments. Nitrofurantoin resistance indeed evolved extremely slowly via reproducible mutations—an almost paradoxical behavior since this drug causes DNA damage and increases the mutation rate. Overall, we identified novel quantitative characteristics of the evolutionary landscape that provide the conceptual foundation for predicting the dynamics of drug resistance evolution.},
author = {Chevereau, Guillaume and Dravecka, Marta and Batur, Tugce and Guvenek, Aysegul and Ayhan, Dilay and Toprak, Erdal and Bollenbach, Mark Tobias},
journal = {PLoS Biology},
number = {11},
publisher = {Public Library of Science},
title = {{Quantifying the determinants of evolutionary dynamics leading to drug resistance}},
doi = {10.1371/journal.pbio.1002299},
volume = {13},
year = {2015},
}
@article{1828,
abstract = {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.},
author = {Akopyan, Arseniy and Pirogov, Sergey and Rybko, Aleksandr},
journal = {Journal of Statistical Physics},
number = {1},
pages = {163 -- 167},
publisher = {Springer},
title = {{Invariant measures of genetic recombination process}},
doi = {10.1007/s10955-015-1238-5},
volume = {160},
year = {2015},
}
@inproceedings{1481,
abstract = {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. },
author = {Ahmed, Umair and Chatterjee, Krishnendu and Gulwani, Sumit},
booktitle = {Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence},
location = {Austin, TX, USA},
pages = {745 -- 752},
publisher = {AAAI Press},
title = {{Automatic generation of alternative starting positions for simple traditional board games}},
volume = {2},
year = {2015},
}
@article{1525,
abstract = {Based on 16 recommendations, efforts should be made to achieve the following goal: By 2025, all scholarly publication activity in Austria should be Open Access. In other words, the final versions of all scholarly publications resulting from the support of public resources must be freely accessible on the Internet without delay (Gold Open Access). The resources required to meet this obligation shall be provided to the authors, or the cost of the publication venues shall be borne directly by the research organisations.},
author = {Bauer, Bruno and Blechl, Guido and Bock, Christoph and Danowski, Patrick and Ferus, Andreas and Graschopf, Anton and König, Thomas and Mayer, Katja and Reckling, Falk and Rieck, Katharina and Seitz, Peter and Stöger, Herwig and Welzig, Elvira},
journal = {VÖB Mitteilungen},
number = {3},
pages = {580 -- 607},
publisher = {Verein Österreichischer Bibliothekare},
title = {{Arbeitsgruppe „Nationale Strategie“ des Open Access Network Austria OANA}},
doi = {10.5281/zenodo.33178},
volume = {68},
year = {2015},
}
@inproceedings{1474,
abstract = {Cryptographic access control offers selective access to encrypted data via a combination of key management and functionality-rich cryptographic schemes, such as attribute-based encryption. Using this approach, publicly available meta-data may inadvertently leak information on the access policy that is enforced by cryptography, which renders cryptographic access control unusable in settings where this information is highly sensitive. We begin to address this problem by presenting rigorous definitions for policy privacy in cryptographic access control. For concreteness we set our results in the model of Role-Based Access Control (RBAC), where we identify and formalize several different flavors of privacy, however, our framework should serve as inspiration for other models of access control. Based on our insights we propose a new system which significantly improves on the privacy properties of state-of-the-art constructions. Our design is based on a novel type of privacy-preserving attribute-based encryption, which we introduce and show how to instantiate. We present our results in the context of a cryptographic RBAC system by Ferrara et al. (CSF'13), which uses cryptography to control read access to files, while write access is still delegated to trusted monitors. We give an extension of the construction that permits cryptographic control over write access. Our construction assumes that key management uses out-of-band channels between the policy enforcer and the users but eliminates completely the need for monitoring read/write access to the data.},
author = {Ferrara, Anna and Fuchsbauer, Georg and Liu, Bin and Warinschi, Bogdan},
location = {Verona, Italy},
pages = {46--60},
publisher = {IEEE},
title = {{Policy privacy in cryptographic access control}},
doi = {10.1109/CSF.2015.11},
year = {2015},
}
@phdthesis{1400,
abstract = {Cancer results from an uncontrolled growth of abnormal cells. Sequentially accumulated genetic and epigenetic alterations decrease cell death and increase cell replication. We used mathematical models to quantify the effect of driver gene mutations. The recently developed targeted therapies can lead to dramatic regressions. However, in solid cancers, clinical responses are often short-lived because resistant cancer cells evolve. We estimated that approximately 50 different mutations can confer resistance to a typical targeted therapeutic agent. We find that resistant cells are likely to be present in expanded subclones before the start of the treatment. The dominant strategy to prevent the evolution of resistance is combination therapy. Our analytical results suggest that in most patients, dual therapy, but not monotherapy, can result in long-term disease control. However, long-term control can only occur if there are no possible mutations in the genome that can cause cross-resistance to both drugs. Furthermore, we showed that simultaneous therapy with two drugs is much more likely to result in long-term disease control than sequential therapy with the same drugs. To improve our understanding of the underlying subclonal evolution we reconstruct the evolutionary history of a patient's cancer from next-generation sequencing data of spatially-distinct DNA samples. Using a quantitative measure of genetic relatedness, we found that pancreatic cancers and their metastases demonstrated a higher level of relatedness than that expected for any two cells randomly taken from a normal tissue. This minimal amount of genetic divergence among advanced lesions indicates that genetic heterogeneity, when quantitatively defined, is not a fundamental feature of the natural history of untreated pancreatic cancers. Our newly developed, phylogenomic tool Treeomics finds evidence for seeding patterns of metastases and can directly be used to discover rules governing the evolution of solid malignancies to transform cancer into a more predictable disease.},
author = {Reiter, Johannes},
pages = {183},
publisher = {IST Austria},
title = {{The subclonal evolution of cancer}},
year = {2015},
}
@article{1587,
abstract = {We investigate the quantum interference shifts between energetically close states, where the state structure is observed by laser spectroscopy. We report a compact and analytical expression that models the quantum interference induced shift for any admixture of circular polarization of the incident laser and angle of observation. An experimental scenario free of quantum interference can thus be predicted with this formula. Although this study is exemplified here for muonic deuterium, it can be applied to any other laser spectroscopy measurement of ns-n′p frequencies of a nonrelativistic atomic system, via an ns→n′p→n′′s scheme.},
author = {Amaro, Pedro and Fratini, Filippo and Safari, Laleh and Antognini, Aldo and Indelicato, Paul and Pohl, Randolf and Santos, José},
journal = {Physical Review A - Atomic, Molecular, and Optical Physics},
number = {6},
publisher = {American Physical Society},
title = {{Quantum interference shifts in laser spectroscopy with elliptical polarization}},
doi = {10.1103/PhysRevA.92.062506},
volume = {92},
year = {2015},
}
@inproceedings{1568,
abstract = {Aiming at the automatic diagnosis of tumors from narrow band imaging (NBI) magnifying endoscopy (ME) images of the stomach, we combine methods from image processing, computational topology, and machine learning to classify patterns into normal, tubular, vessel. Training the algorithm on a small number of images of each type, we achieve a high rate of correct classifications. The analysis of the learning algorithm reveals that a handful of geometric and topological features are responsible for the overwhelming majority of decisions.},
author = {Dunaeva, Olga and Edelsbrunner, Herbert and Lukyanov, Anton and Machin, Michael and Malkova, Daria},
booktitle = {Proceedings - 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing},
location = {Timisoara, Romania},
pages = {7034731},
publisher = {IEEE},
title = {{The classification of endoscopy images with persistent homology}},
doi = {10.1109/SYNASC.2014.81},
year = {2015},
}
@inproceedings{1425,
abstract = {In this work we aim at extending the theoretical foundations of lifelong learning. Previous work analyzing this scenario is based on the assumption that learning tasks are sampled i.i.d. from a task environment or limited to strongly constrained data distributions. Instead, we study two scenarios when lifelong learning is possible, even though the observed tasks do not form an i.i.d. sample: first, when they are sampled from the same environment, but possibly with dependencies, and second, when the task environment is allowed to change over time in a consistent way. In the first case we prove a PAC-Bayesian theorem that can be seen as a direct generalization of the analogous previous result for the i.i.d. case. For the second scenario we propose to learn an inductive bias in form of a transfer procedure. We present a generalization bound and show on a toy example how it can be used to identify a beneficial transfer algorithm.},
author = {Pentina, Anastasia and Lampert, Christoph},
location = {Montreal, Canada},
pages = {1540 -- 1548},
publisher = {Neural Information Processing Systems},
title = {{Lifelong learning with non-i.i.d. tasks}},
volume = {2015},
year = {2015},
}