@inproceedings{1327,
  abstract     = {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. },
  author       = {Brázdil, Tomáš and Chatterjee, Krishnendu and Chmelik, Martin and Gupta, Anchit and Novotny, Petr},
  booktitle    = {Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems},
  location     = {Singapore},
  pages        = {1465 -- 1466},
  publisher    = {ACM},
  title        = {{Stochastic shortest path with energy constraints in POMDPs}},
  year         = {2016},
}

@article{1328,
  abstract     = {Hole spins have gained considerable interest in the past few years due to their potential for fast electrically controlled qubits. Here, we study holes confined in Ge hut wires, a so-far unexplored type of nanostructure. Low-temperature magnetotransport measurements reveal a large anisotropy between the in-plane and out-of-plane g-factors of up to 18. Numerical simulations verify that this large anisotropy originates from a confined wave function of heavy-hole character. A light-hole admixture of less than 1% is estimated for the states of lowest energy, leading to a surprisingly large reduction of the out-of-plane g-factors compared with those for pure heavy holes. Given this tiny light-hole contribution, the spin lifetimes are expected to be very long, even in isotopically nonpurified samples.},
  author       = {Watzinger, Hannes and Kloeffel, Christoph and Vukusic, Lada and Rossell, Marta and Sessi, Violetta and Kukucka, Josip and Kirchschlager, Raimund and Lausecker, Elisabeth and Truhlar, Alisha and Glaser, Martin and Rastelli, Armando and Fuhrer, Andreas and Loss, Daniel and Katsaros, Georgios},
  journal      = {Nano Letters},
  number       = {11},
  pages        = {6879 -- 6885},
  publisher    = {American Chemical Society},
  title        = {{Heavy-hole states in germanium hut wires}},
  doi          = {10.1021/acs.nanolett.6b02715},
  volume       = {16},
  year         = {2016},
}

@article{1329,
  abstract     = {Daphnia species have become models for ecological genomics and exhibit interesting features, such as high phenotypic plasticity and a densely packed genome with many lineage-specific genes. They are also cyclic parthenogenetic, with alternating asexual and sexual cycles and environmental sex determination. Here, we present a de novo transcriptome assembly of over 32,000 D. galeata genes and use it to investigate gene expression in females and spontaneously produced males of two clonal lines derived from lakes in Germany and the Czech Republic. We find that only a low percentage (18%) of genes shows sex-biased expression and that there are many more female-biased gene (FBG) than male-biased gene (MBG). Furthermore, FBGs tend to be more conserved between species than MBGs in both sequence and expression. These patterns may be a consequence of cyclic parthenogenesis leading to a relaxation of purifying selection on MBGs. The two clonal lines show considerable differences in both number and identity of sex-biased genes, suggesting that they may have reproductive strategies differing in their investment in sexual reproduction. Orthologs of key genes in the sex determination and juvenile hormone pathways, which are thought to be important for the transition from asexual to sexual reproduction, are present in D. galeata and highly conserved among Daphnia species.},
  author       = {Huylmans, Ann K and López Ezquerra, Alberto and Parsch, John and Cordellier, Mathilde},
  journal      = {Genome Biology and Evolution},
  number       = {10},
  pages        = {3120 -- 3139},
  publisher    = {Oxford University Press},
  title        = {{De novo transcriptome assembly and sex-biased gene expression in the cyclical parthenogenetic Daphnia galeata}},
  doi          = {10.1093/gbe/evw221},
  volume       = {8},
  year         = {2016},
}

@article{1330,
  abstract     = {In this paper we investigate the existence of closed billiard trajectories in not necessarily smooth convex bodies. In particular, we show that if a body K ⊂ Rd has the property that the tangent cone of every non-smooth point q ∉ ∂K is acute (in a certain sense), then there is a closed billiard trajectory in K.},
  author       = {Akopyan, Arseniy and Balitskiy, Alexey},
  journal      = {Israel Journal of Mathematics},
  number       = {2},
  pages        = {833 -- 845},
  publisher    = {Springer},
  title        = {{Billiards in convex bodies with acute angles}},
  doi          = {10.1007/s11856-016-1429-z},
  volume       = {216},
  year         = {2016},
}

@article{1331,
  abstract     = {Cytokinin is a phytohormone that is well known for its roles in numerous plant growth and developmental processes, yet it has also been linked to abiotic stress response in a less defined manner. Arabidopsis (Arabidopsis thaliana) Cytokinin Response Factor 6 (CRF6) is a cytokinin-responsive AP2/ERF-family transcription factor that, through the cytokinin signaling pathway, plays a key role in the inhibition of dark-induced senescence. CRF6 expression is also induced by oxidative stress, and here we show a novel function for CRF6 in relation to oxidative stress and identify downstream transcriptional targets of CRF6 that are repressed in response to oxidative stress. Analysis of transcriptomic changes in wild-type and crf6 mutant plants treated with H2O2 identified CRF6-dependent differentially expressed transcripts, many of which were repressed rather than induced. Moreover, many repressed genes also show decreased expression in 35S:CRF6 overexpressing plants. Together, these findings suggest that CRF6 functions largely as a transcriptional repressor. Interestingly, among the H2O2 repressed CRF6-dependent transcripts was a set of five genes associated with cytokinin processes: (signaling) ARR6, ARR9, ARR11, (biosynthesis) LOG7, and (transport) ABCG14. We have examined mutants of these cytokinin-associated target genes to reveal novel connections to oxidative stress. Further examination of CRF6-DNA interactions indicated that CRF6 may regulate its targets both directly and indirectly. Together, this shows that CRF6 functions during oxidative stress as a negative regulator to control this cytokinin-associated module of CRF6- dependent genes and establishes a novel connection between cytokinin and oxidative stress response.},
  author       = {Zwack, Paul and De Clercq, Inge and Howton, Timothy and Hallmark, H Tucker and Hurny, Andrej and Keshishian, Erika and Parish, Alyssa and Benková, Eva and Mukhtar, M Shahid and Van Breusegem, Frank and Rashotte, Aaron},
  issn         = {1532-2548},
  journal      = {Plant Physiology},
  number       = {2},
  pages        = {1249 -- 1258},
  publisher    = {American Society of Plant Biologists},
  title        = {{Cytokinin response factor 6 represses cytokinin-associated genes during oxidative stress}},
  doi          = {10.1104/pp.16.00415},
  volume       = {172},
  year         = {2016},
}

@article{1332,
  abstract     = {Antibiotic-sensitive and -resistant bacteria coexist in natural environments with low, if detectable, antibiotic concentrations. Except possibly around localized antibiotic sources, where resistance can provide a strong advantage, bacterial fitness is dominated by stresses unaffected by resistance to the antibiotic. How do such mixed and heterogeneous conditions influence the selective advantage or disadvantage of antibiotic resistance? Here we find that sub-inhibitory levels of tetracyclines potentiate selection for or against tetracycline resistance around localized sources of almost any toxin or stress. Furthermore, certain stresses generate alternating rings of selection for and against resistance around a localized source of the antibiotic. In these conditions, localized antibiotic sources, even at high strengths, can actually produce a net selection against resistance to the antibiotic. Our results show that interactions between the effects of an antibiotic and other stresses in inhomogeneous environments can generate pervasive, complex patterns of selection both for and against antibiotic resistance.},
  author       = {Chait, Remy P and Palmer, Adam and Yelin, Idan and Kishony, Roy},
  journal      = {Nature Communications},
  publisher    = {Nature Publishing Group},
  title        = {{Pervasive selection for and against antibiotic resistance in inhomogeneous multistress environments}},
  doi          = {10.1038/ncomms10333},
  volume       = {7},
  year         = {2016},
}

@article{1333,
  abstract     = {Social dilemmas force players to balance between personal and collective gain. In many dilemmas, such as elected governments negotiating climate-change mitigation measures, the decisions are made not by individual players but by their representatives. However, the behaviour of representatives in social dilemmas has not been investigated experimentally. Here inspired by the negotiations for greenhouse-gas emissions reductions, we experimentally study a collective-risk social dilemma that involves representatives deciding on behalf of their fellow group members. Representatives can be re-elected or voted out after each consecutive collective-risk game. Selfish players are preferentially elected and are hence found most frequently in the "representatives" treatment. Across all treatments, we identify the selfish players as extortioners. As predicted by our mathematical model, their steadfast strategies enforce cooperation from fair players who finally compensate almost completely the deficit caused by the extortionate co-players. Everybody gains, but the extortionate representatives and their groups gain the most.},
  author       = {Milinski, Manfred and Hilbe, Christian and Semmann, Dirk and Sommerfeld, Ralf and Marotzke, Jochem},
  journal      = {Nature Communications},
  publisher    = {Nature Publishing Group},
  title        = {{Humans choose representatives who enforce cooperation in social dilemmas through extortion}},
  doi          = {10.1038/ncomms10915},
  volume       = {7},
  year         = {2016},
}

@article{1334,
  abstract     = {Hippocampal neurons encode a cognitive map of space. These maps are thought to be updated during learning and in response to changes in the environment through activity-dependent synaptic plasticity. Here we examine how changes in activity influence spatial coding in rats using halorhodopsin-mediated, spatially selective optogenetic silencing. Halorhoposin stimulation leads to light-induced suppression in many place cells and interneurons; some place cells increase their firing through disinhibition, whereas some show no effect. We find that place fields of the unaffected subpopulation remain stable. On the other hand, place fields of suppressed place cells were unstable, showing remapping across sessions before and after optogenetic inhibition. Disinhibited place cells had stable maps but sustained an elevated firing rate. These findings suggest that place representation in the hippocampus is constantly governed by activity-dependent processes, and that disinhibition may provide a mechanism for rate remapping.},
  author       = {Schönenberger, Philipp and O'Neill, Joseph and Csicsvari, Jozsef L},
  journal      = {Nature Communications},
  publisher    = {Nature Publishing Group},
  title        = {{Activity dependent plasticity of hippocampal place maps}},
  doi          = {10.1038/ncomms11824},
  volume       = {7},
  year         = {2016},
}

@inproceedings{1335,
  abstract     = {In this paper we review various automata-theoretic formalisms for expressing quantitative properties. We start with finite-state Boolean automata that express the traditional regular properties. We then consider weighted ω-automata that can measure the average density of events, which finite-state Boolean automata cannot. However, even weighted ω-automata cannot express basic performance properties like average response time. We finally consider two formalisms of weighted ω-automata with monitors, where the monitors are either (a) counters or (b) weighted automata themselves. We present a translation result to establish that these two formalisms are equivalent. Weighted ω-automata with monitors generalize weighted ω-automata, and can express average response time property. They present a natural, robust, and expressive framework for quantitative specifications, with important decidable properties.},
  author       = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan},
  location     = {Edinburgh, United Kingdom},
  pages        = {23 -- 38},
  publisher    = {Springer},
  title        = {{Quantitative monitor automata}},
  doi          = {10.1007/978-3-662-53413-7_2},
  volume       = {9837},
  year         = {2016},
}

@article{1339,
  abstract     = {We present a microelectromechanical system, in which a silicon beam is attached to a comb-drive
actuator, which is used to tune the tension in the silicon beam and thus its resonance frequency. By
measuring the resonance frequencies of the system, we show that the comb-drive actuator and the
silicon beam behave as two strongly coupled resonators. Interestingly, the effective coupling rate
(1.5 MHz) is tunable with the comb-drive actuator (10%) as well as with a side-gate (10%)
placed close to the silicon beam. In contrast, the effective spring constant of the system is insensitive
to either of them and changes only by 60.5%. Finally, we show that the comb-drive actuator
can be used to switch between different coupling rates with a frequency of at least 10 kHz.
},
  author       = {Verbiest, Gerard and Xu, Duo and Goldsche, Matthias and Khodkov, Timofiy and Barzanjeh, Shabir and Von Den Driesch, Nils and Buca, Dan and Stampfer, Christoph},
  journal      = {Applied  Physics Letter},
  publisher    = {American Institute of Physics},
  title        = {{Tunable mechanical coupling between driven microelectromechanical resonators}},
  doi          = {10.1063/1.4964122},
  volume       = {109},
  year         = {2016},
}

@inproceedings{1340,
  abstract     = {We study repeated games with absorbing states, a type of two-player, zero-sum concurrent mean-payoff games with the prototypical example being the Big Match of Gillete (1957). These games may not allow optimal strategies but they always have ε-optimal strategies. In this paper we design ε-optimal strategies for Player 1 in these games that use only O(log log T) space. Furthermore, we construct strategies for Player 1 that use space s(T), for an arbitrary small unbounded non-decreasing function s, and which guarantee an ε-optimal value for Player 1 in the limit superior sense. The previously known strategies use space Ω(log T) and it was known that no strategy can use constant space if it is ε-optimal even in the limit superior sense. We also give a complementary lower bound. Furthermore, we also show that no Markov strategy, even extended with finite memory, can ensure value greater than 0 in the Big Match, answering a question posed by Neyman [11].},
  author       = {Hansen, Kristoffer and Ibsen-Jensen, Rasmus and Koucký, Michal},
  location     = {Liverpool, United Kingdom},
  pages        = {64 -- 76},
  publisher    = {Springer},
  title        = {{The big match in small space}},
  doi          = {10.1007/978-3-662-53354-3_6},
  volume       = {9928},
  year         = {2016},
}

@inproceedings{1341,
  abstract     = {In resource allocation games, selfish players share resources that are needed in order to fulfill their objectives. The cost of using a resource depends on the load on it. In the traditional setting, the players make their choices concurrently and in one-shot. That is, a strategy for a player is a subset of the resources. We introduce and study dynamic resource allocation games. In this setting, the game proceeds in phases. In each phase each player chooses one resource. A scheduler dictates the order in which the players proceed in a phase, possibly scheduling several players to proceed concurrently. The game ends when each player has collected a set of resources that fulfills his objective. The cost for each player then depends on this set as well as on the load on the resources in it – we consider both congestion and cost-sharing games. We argue that the dynamic setting is the suitable setting for many applications in practice. We study the stability of dynamic resource allocation games, where the appropriate notion of stability is that of subgame perfect equilibrium, study the inefficiency incurred due to selfish behavior, and also study problems that are particular to the dynamic setting, like constraints on the order in which resources can be chosen or the problem of finding a scheduler that achieves stability.},
  author       = {Avni, Guy and Henzinger, Thomas A and Kupferman, Orna},
  location     = {Liverpool, United Kingdom},
  pages        = {153 -- 166},
  publisher    = {Springer},
  title        = {{Dynamic resource allocation games}},
  doi          = {10.1007/978-3-662-53354-3_13},
  volume       = {9928},
  year         = {2016},
}

@article{1342,
  abstract     = {A key aspect of bacterial survival is the ability to evolve while migrating across spatially varying environmental challenges. Laboratory experiments, however, often study evolution in well-mixed systems. Here, we introduce an experimental device, the microbial evolution and growth arena (MEGA)-plate, in which bacteria spread and evolved on a large antibiotic landscape (120 × 60 centimeters) that allowed visual observation of mutation and selection in a migrating bacterial front.While resistance increased consistently, multiple coexisting lineages diversified both phenotypically and genotypically. Analyzing mutants at and behind the propagating front,we found that evolution is not always led by the most resistant mutants; highly resistant mutants may be trapped behindmore sensitive lineages.TheMEGA-plate provides a versatile platformfor studying microbial adaption and directly visualizing evolutionary dynamics.},
  author       = {Baym, Michael and Lieberman, Tami and Kelsic, Eric and Chait, Remy P and Gross, Rotem and Yelin, Idan and Kishony, Roy},
  journal      = {Science},
  number       = {6304},
  pages        = {1147 -- 1151},
  publisher    = {American Association for the Advancement of Science},
  title        = {{Spatiotemporal microbial evolution on antibiotic landscapes}},
  doi          = {10.1126/science.aag0822},
  volume       = {353},
  year         = {2016},
}

@article{1343,
  abstract     = {The Fermi-Hubbard model is one of the key models of condensed matter physics, which holds a

potential for explaining the mystery of high-temperature superconductivity. Recent progress in

ultracold atoms in optical lattices has paved the way to studying the model’s phase diagram using

the tools of quantum simulation, which emerged as a promising alternative to the numerical

calculations plagued by the infamous sign problem. However, the temperatures achieved using

elaborate laser cooling protocols so far have been too high to show the appearance of

antiferromagnetic (AF) and superconducting quantum phases directly. In this work, we demonstrate

that using the machinery of dissipative quantum state engineering, one can observe the emergence of

the AF order in the Fermi-Hubbard model with fermions in optical lattices. The core of the approach

is to add incoherent laser scattering in such a way that the AF state emerges as the dark state of

the driven-dissipative dynamics. The proposed controlled dissipation channels described in this work

are straightforward to add to already existing experimental setups.},
  author       = {Kaczmarczyk, Jan and Weimer, Hendrik and Lemeshko, Mikhail},
  journal      = {New Journal of Physics},
  number       = {9},
  publisher    = {IOP Publishing Ltd.},
  title        = {{Dissipative preparation of antiferromagnetic order in the Fermi-Hubbard model}},
  doi          = {10.1088/1367-2630/18/9/093042},
  volume       = {18},
  year         = {2016},
}

@article{1344,
  abstract     = {Despite being composed of immobile cells, plants reorient along directional stimuli. The hormone auxin is redistributed in stimulated organs leading to differential growth and bending. Auxin application triggers rapid cell wall acidification and elongation of aerial organs of plants, but the molecular players mediating these effects are still controversial. Here we use genetically-encoded pH and auxin signaling sensors, pharmacological and genetic manipulations available for Arabidopsis etiolated hypocotyls to clarify how auxin is perceived and the downstream growth executed. We show that auxin-induced acidification occurs by local activation of H+-ATPases, which in the context of gravity response is restricted to the lower organ side. This auxin-stimulated acidification and growth require TIR1/AFB-Aux/IAA nuclear auxin perception. In addition, auxin-induced gene transcription and specifically SAUR proteins are crucial downstream mediators of this growth. Our study provides strong experimental support for the acid growth theory and clarified the contribution of the upstream auxin perception mechanisms.},
  author       = {Fendrych, Matyas and Leung, Jeffrey and Friml, Jirí},
  journal      = {eLife},
  publisher    = {eLife Sciences Publications},
  title        = {{TIR1 AFB Aux IAA auxin perception mediates rapid cell wall acidification and growth of Arabidopsis hypocotyls}},
  doi          = {10.7554/eLife.19048},
  volume       = {5},
  year         = {2016},
}

@article{1345,
  abstract     = {The electrostatic charge at the inner surface of the plasma membrane is strongly negative in higher organisms. A new study shows that phosphatidylinositol-4-phosphate plays a critical role in establishing plasma membrane surface charge in Arabidopsis, which regulates the correct localization of signalling components.},
  author       = {Molnar, Gergely and Fendrych, Matyas and Friml, Jirí},
  journal      = {Nature Plants},
  publisher    = {Nature Publishing Group},
  title        = {{Plasma membrane: Negative attraction}},
  doi          = {10.1038/nplants.2016.102},
  volume       = {2},
  year         = {2016},
}

@article{1346,
  abstract     = {ATP production requires the establishment of an electrochemical proton gradient across the inner mitochondrial membrane. Mitochondrial uncouplers dissipate this proton gradient and disrupt numerous cellular processes, including vesicular trafficking, mainly through energy depletion. Here we show that Endosidin9 (ES9), a novel mitochondrial uncoupler, is a potent inhibitor of clathrin-mediated endocytosis (CME) in different systems and that ES9 induces inhibition of CME not because of its effect on cellular ATP, but rather due to its protonophore activity that leads to cytoplasm acidification. We show that the known tyrosine kinase inhibitor tyrphostinA23, which is routinely used to block CME, displays similar properties, thus questioning its use as a specific inhibitor of cargo recognition by the AP-2 adaptor complex via tyrosine motif-based endocytosis signals. Furthermore, we show that cytoplasm acidification dramatically affects the dynamics and recruitment of clathrin and associated adaptors, and leads to reduction of phosphatidylinositol 4,5-biphosphate from the plasma membrane.},
  author       = {Dejonghe, Wim and Kuenen, Sabine and Mylle, Evelien and Vasileva, Mina K and Keech, Olivier and Viotti, Corrado and Swerts, Jef and Fendrych, Matyas and Ortiz Morea, Fausto and Mishev, Kiril and Delang, Simon and Scholl, Stefan and Zarza, Xavier and Heilmann, Mareike and Kourelis, Jiorgos and Kasprowicz, Jaroslaw and Nguyen, Le and Drozdzecki, Andrzej and Van Houtte, Isabelle and Szatmári, Anna and Majda, Mateusz and Baisa, Gary and Bednarek, Sebastian and Robert, Stéphanie and Audenaert, Dominique and Testerink, Christa and Munnik, Teun and Van Damme, Daniël and Heilmann, Ingo and Schumacher, Karin and Winne, Johan and Friml, Jirí and Verstreken, Patrik and Russinova, Eugenia},
  journal      = {Nature Communications},
  publisher    = {Nature Publishing Group},
  title        = {{Mitochondrial uncouplers inhibit clathrin-mediated endocytosis largely through cytoplasmic acidification}},
  doi          = {10.1038/ncomms11710},
  volume       = {7},
  year         = {2016},
}

@article{1347,
  abstract     = {During the past 70 years, the quantum theory of angular momentum has been successfully applied to describing the properties of nuclei, atoms, and molecules, and their interactions with each other as well as with external fields. Because of the properties of quantum rotations, the angular-momentum algebra can be of tremendous complexity even for a few interacting particles, such as valence electrons of an atom, not to mention larger many-particle systems. In this work, we study an example of the latter: A rotating quantum impurity coupled to a many-body bosonic bath. In the regime of strong impurity-bath couplings, the problem involves the addition of an infinite number of angular momenta, which renders it intractable using currently available techniques. Here, we introduce a novel canonical transformation that allows us to eliminate the complex angular-momentum algebra from such a class of many-body problems. In addition, the transformation exposes the problem's constants of motion, and renders it solvable exactly in the limit of a slowly rotating impurity. We exemplify the technique by showing that there exists a critical rotational speed at which the impurity suddenly acquires one quantum of angular momentum from the many-particle bath. Such an instability is accompanied by the deformation of the phonon density in the frame rotating along with the impurity.},
  author       = {Schmidt, Richard and Lemeshko, Mikhail},
  journal      = {Physical Review X},
  number       = {1},
  publisher    = {American Physical Society},
  title        = {{Deformation of a quantum many-particle system by a rotating impurity}},
  doi          = {10.1103/PhysRevX.6.011012},
  volume       = {6},
  year         = {2016},
}

@inproceedings{1348,
  abstract     = {A drawing in the plane (ℝ2) of a graph G = (V,E) equipped with a function γ : V → ℕ is x-bounded if (i) x(u) < x(v) whenever γ(u) < γ(v) and (ii) γ(u) ≤ γ(w) ≤ γ(v), where uv ∈ E and γ(u) ≤ γ(v), whenever x(w) ∈ x(uv), where x(.) denotes the projection to the xaxis.We prove a characterization of isotopy classes of embeddings of connected graphs equipped with γ in the plane containing an x-bounded embedding.Then we present an efficient algorithm, which relies on our result, for testing the existence of an x-bounded embedding if the given graph is a forest.This partially answers a question raised recently by Angelini et al.and Chang et al., and proves that c-planarity testing of flat clustered graphs with three clusters is tractable when the underlying abstract graph is a forest.},
  author       = {Fulek, Radoslav},
  location     = {Helsinki, Finland},
  pages        = {31 -- 42},
  publisher    = {Springer},
  title        = {{Bounded embeddings of graphs in the plane}},
  doi          = {10.1007/978-3-319-44543-4_3},
  volume       = {9843},
  year         = {2016},
}

@inproceedings{1349,
  abstract     = {Crossing fitness valleys is one of the major obstacles to function optimization. In this paper we investigate how the structure of the fitness valley, namely its depth d and length ℓ, influence the runtime of different strategies for crossing these valleys. We present a runtime comparison between the (1+1) EA and two non-elitist nature-inspired algorithms, Strong Selection Weak Mutation (SSWM) and the Metropolis algorithm. While the (1+1) EA has to jump across the valley to a point of higher fitness because it does not accept decreasing moves, the non-elitist algorithms may cross the valley by accepting worsening moves. We show that while the runtime of the (1+1) EA algorithm depends critically on the length of the valley, the runtimes of the non-elitist algorithms depend crucially only on the depth of the valley. In particular, the expected runtime of both SSWM and Metropolis is polynomial in ℓ and exponential in d while the (1+1) EA is efficient only for valleys of small length. Moreover, we show that both SSWM and Metropolis can also efficiently optimize a rugged function consisting of consecutive valleys.},
  author       = {Oliveto, Pietro and Paixao, Tiago and Heredia, Jorge and Sudholt, Dirk and Trubenova, Barbora},
  booktitle    = {Proceedings of the Genetic and Evolutionary Computation Conference 2016 },
  location     = {Denver, CO, USA},
  pages        = {1163 -- 1170},
  publisher    = {ACM},
  title        = {{When non-elitism outperforms elitism for crossing fitness valleys}},
  doi          = {10.1145/2908812.2908909},
  year         = {2016},
}