TY - JOUR
AB - Aiming at the automatic diagnosis of tumors using narrow band imaging (NBI) magnifying endoscopic (ME) images of the stomach, we combine methods from image processing, topology, geometry, and machine learning to classify patterns into three classes: oval, tubular and irregular. 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.
AU - Dunaeva, Olga
AU - Edelsbrunner, Herbert
AU - Lukyanov, Anton
AU - Machin, Michael
AU - Malkova, Daria
AU - Kuvaev, Roman
AU - Kashin, Sergey
ID - 1289
IS - 1
JF - Pattern Recognition Letters
TI - The classification of endoscopy images with persistent homology
VL - 83
ER -
TY - JOUR
AB - We developed a competition-based screening strategy to identify compounds that invert the selective advantage of antibiotic resistance. Using our assay, we screened over 19,000 compounds for the ability to select against the TetA tetracycline-resistance efflux pump in Escherichia coli and identified two hits, β-thujaplicin and disulfiram. Treating a tetracycline-resistant population with β-thujaplicin selects for loss of the resistance gene, enabling an effective second-phase treatment with doxycycline.
AU - Stone, Laura
AU - Baym, Michael
AU - Lieberman, Tami
AU - Chait, Remy P
AU - Clardy, Jon
AU - Kishony, Roy
ID - 1290
IS - 11
JF - Nature Chemical Biology
TI - Compounds that select against the tetracycline-resistance efflux pump
VL - 12
ER -
TY - JOUR
AB - We consider Ising models in two and three dimensions, with short range ferromagnetic and long range, power-law decaying, antiferromagnetic interactions. We let J be the ratio between the strength of the ferromagnetic to antiferromagnetic interactions. The competition between these two kinds of interactions induces the system to form domains of minus spins in a background of plus spins, or vice versa. If the decay exponent p of the long range interaction is larger than dÂ +Â 1, with d the space dimension, this happens for all values of J smaller than a critical value Jc(p), beyond which the ground state is homogeneous. In this paper, we give a characterization of the infinite volume ground states of the system, for pÂ >Â 2d and J in a left neighborhood of Jc(p). In particular, we prove that the quasi-one-dimensional states consisting of infinite stripes (dÂ =Â 2) or slabs (dÂ =Â 3), all of the same optimal width and orientation, and alternating magnetization, are infinite volume ground states. Our proof is based on localization bounds combined with reflection positivity.
AU - Giuliani, Alessandro
AU - Seiringer, Robert
ID - 1291
IS - 3
JF - Communications in Mathematical Physics
TI - Periodic striped ground states in Ising models with competing interactions
VL - 347
ER -
TY - JOUR
AB - We give explicit formulas and algorithms for the computation of the Thurston–Bennequin invariant of a nullhomologous Legendrian knot on a page of a contact open book and on Heegaard surfaces in convex position. Furthermore, we extend the results to rationally nullhomologous knots in arbitrary 3-manifolds.
AU - Durst, Sebastian
AU - Kegel, Marc
AU - Klukas, Mirko D
ID - 1292
IS - 2
JF - Acta Mathematica Hungarica
TI - Computing the Thurston–Bennequin invariant in open books
VL - 150
ER -
TY - JOUR
AB - For a graph G with p vertices the closed convex cone S⪰0(G) consists of all real positive semidefinite p×p matrices whose sparsity pattern is given by G, that is, those matrices with zeros in the off-diagonal entries corresponding to nonedges of G. The extremal rays of this cone and their associated ranks have applications to matrix completion problems, maximum likelihood estimation in Gaussian graphical models in statistics, and Gauss elimination for sparse matrices. While the maximum rank of an extremal ray in S⪰0(G), known as the sparsity order of G, has been characterized for different classes of graphs, we here study all possible extremal ranks of S⪰0(G). We investigate when the geometry of the (±1)-cut polytope of G yields a polyhedral characterization of the set of extremal ranks of S⪰0(G). For a graph G without K5 minors, we show that appropriately chosen normal vectors to the facets of the (±1)-cut polytope of G specify the off-diagonal entries of extremal matrices in S⪰0(G). We also prove that for appropriately chosen scalars the constant term of the linear equation of each facet-supporting hyperplane is the rank of its corresponding extremal matrix in S⪰0(G). Furthermore, we show that if G is series-parallel then this gives a complete characterization of all possible extremal ranks of S⪰0(G). Consequently, the sparsity order problem for series-parallel graphs can be solved in terms of polyhedral geometry.
AU - Solus, Liam T
AU - Uhler, Caroline
AU - Yoshida, Ruriko
ID - 1293
JF - Linear Algebra and Its Applications
TI - Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without K5 minors
VL - 509
ER -
TY - JOUR
AB - Direct reciprocity is a major mechanism for the evolution of cooperation. Several classical studies have suggested that humans should quickly learn to adopt reciprocal strategies to establish mutual cooperation in repeated interactions. On the other hand, the recently discovered theory of ZD strategies has found that subjects who use extortionate strategies are able to exploit and subdue cooperators. Although such extortioners have been predicted to succeed in any population of adaptive opponents, theoretical follow-up studies questioned whether extortion can evolve in reality. However, most of these studies presumed that individuals have similar strategic possibilities and comparable outside options, whereas asymmetries are ubiquitous in real world applications. Here we show with a model and an economic experiment that extortionate strategies readily emerge once subjects differ in their strategic power. Our experiment combines a repeated social dilemma with asymmetric partner choice. In our main treatment there is one randomly chosen group member who is unilaterally allowed to exchange one of the other group members after every ten rounds of the social dilemma. We find that this asymmetric replacement opportunity generally promotes cooperation, but often the resulting payoff distribution reflects the underlying power structure. Almost half of the subjects in a better strategic position turn into extortioners, who quickly proceed to exploit their peers. By adapting their cooperation probabilities consistent with ZD theory, extortioners force their co-players to cooperate without being similarly cooperative themselves. Comparison to non-extortionate players under the same conditions indicates a substantial net gain to extortion. Our results thus highlight how power asymmetries can endanger mutually beneficial interactions, and transform them into exploitative relationships. In particular, our results indicate that the extortionate strategies predicted from ZD theory could play a more prominent role in our daily interactions than previously thought.
AU - Hilbe, Christian
AU - Hagel, Kristin
AU - Milinski, Manfred
ID - 1322
IS - 10
JF - PLoS One
TI - Asymmetric power boosts extortion in an economic experiment
VL - 11
ER -
TY - JOUR
AB - Mossy fiber synapses on CA3 pyramidal cells are 'conditional detonators' that reliably discharge postsynaptic targets. The 'conditional' nature implies that burst activity in dentate gyrus granule cells is required for detonation. Whether single unitary excitatory postsynaptic potentials (EPSPs) trigger spikes in CA3 neurons remains unknown. Mossy fiber synapses exhibit both pronounced short-term facilitation and uniquely large post-tetanic potentiation (PTP). We tested whether PTP could convert mossy fiber synapses from subdetonator into detonator mode, using a recently developed method to selectively and noninvasively stimulate individual presynaptic terminals in rat brain slices. Unitary EPSPs failed to initiate a spike in CA3 neurons under control conditions, but reliably discharged them after induction of presynaptic short-term plasticity. Remarkably, PTP switched mossy fiber synapses into full detonators for tens of seconds. Plasticity-dependent detonation may be critical for efficient coding, storage, and recall of information in the granule cell–CA3 cell network.
AU - Vyleta, Nicholas
AU - Borges Merjane, Carolina
AU - Jonas, Peter M
ID - 1323
JF - eLife
TI - Plasticity-dependent, full detonation at hippocampal mossy fiber–CA3 pyramidal neuron synapses
VL - 5
ER -
TY - CONF
AB - We study graphs and two-player games in which rewards are assigned to states, and the goal of the players is to satisfy or dissatisfy certain property of the generated outcome, given as a mean payoff property. Since the notion of mean-payoff does not reflect possible fluctuations from the mean-payoff along a run, we propose definitions and algorithms for capturing the stability of the system, and give algorithms for deciding if a given mean payoff and stability objective can be ensured in the system.
AU - Brázdil, Tomáš
AU - Forejt, Vojtěch
AU - Kučera, Antonín
AU - Novotny, Petr
ID - 1325
TI - Stability in graphs and games
VL - 59
ER -
TY - CONF
AB - Energy Markov Decision Processes (EMDPs) are finite-state Markov decision processes where each transition is assigned an integer counter update and a rational payoff. An EMDP configuration is a pair s(n), where s is a control state and n is the current counter value. The configurations are changed by performing transitions in the standard way. We consider the problem of computing a safe strategy (i.e., a strategy that keeps the counter non-negative) which maximizes the expected mean payoff.
AU - Brázdil, Tomáš
AU - Kučera, Antonín
AU - Novotny, Petr
ID - 1326
TI - Optimizing the expected mean payoff in Energy Markov Decision Processes
VL - 9938
ER -
TY - CONF
AB - We consider partially observable Markov decision processes (POMDPs) with a set of target states and positive integer costs associated with every transition. The traditional optimization objective (stochastic shortest path) asks to minimize the expected total cost until the target set is reached. We extend the traditional framework of POMDPs to model energy consumption, which represents a hard constraint. The energy levels may increase and decrease with transitions, and the hard constraint requires that the energy level must remain positive in all steps till the target is reached. First, we present a novel algorithm for solving POMDPs with energy levels, developing on existing POMDP solvers and using RTDP as its main method. Our second contribution is related to policy representation. For larger POMDP instances the policies computed by existing solvers are too large to be understandable. We present an automated procedure based on machine learning techniques that automatically extracts important decisions of the policy allowing us to compute succinct human readable policies. Finally, we show experimentally that our algorithm performs well and computes succinct policies on a number of POMDP instances from the literature that were naturally enhanced with energy levels.
AU - Brázdil, Tomáš
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Gupta, Anchit
AU - Novotny, Petr
ID - 1327
T2 - Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems
TI - Stochastic shortest path with energy constraints in POMDPs
ER -