TY - JOUR AB - We introduce for each quiver Q and each algebraic oriented cohomology theory A, the cohomological Hall algebra (CoHA) of Q, as the A-homology of the moduli of representations of the preprojective algebra of Q. This generalizes the K-theoretic Hall algebra of commuting varieties defined by Schiffmann-Vasserot. When A is the Morava K-theory, we show evidence that this algebra is a candidate for Lusztig's reformulated conjecture on modular representations of algebraic groups. We construct an action of the preprojective CoHA on the A-homology of Nakajima quiver varieties. We compare this with the action of the Borel subalgebra of Yangian when A is the intersection theory. We also give a shuffle algebra description of this CoHA in terms of the underlying formal group law of A. As applications, we obtain a shuffle description of the Yangian. AU - Yang, Yaping AU - Zhao, Gufang ID - 5999 IS - 5 JF - Proceedings of the London Mathematical Society SN - 0024-6115 TI - The cohomological Hall algebra of a preprojective algebra VL - 116 ER - TY - JOUR AB - Schistosomes are the causative agents of schistosomiasis, a neglected tropical disease affecting over 230 million people worldwide.Additionally to their major impact on human health, they are also models of choice in evolutionary biology. These parasitic flatwormsare unique among the common hermaphroditic trematodes as they have separate sexes. This so-called “evolutionary scandal”displays a female heterogametic genetic sex-determination system (ZZ males and ZW females), as well as a pronounced adult sexualdimorphism. These phenotypic differences are determined by a shared set of genes in both sexes, potentially leading to intralocussexual conflicts. To resolve these conflicts in sexually selected traits, molecular mechanisms such as sex-biased gene expression couldoccur, but parent-of-origin gene expression also provides an alternative. In this work we investigated the latter mechanism, that is,genes expressed preferentially from either the maternal or the paternal allele, inSchistosoma mansonispecies. To this end, tran-scriptomes from male and female hybrid adults obtained by strain crosses were sequenced. Strain-specific single nucleotide poly-morphism (SNP) markers allowed us to discriminate the parental origin, while reciprocal crosses helped to differentiate parentalexpression from strain-specific expression. We identified genes containing SNPs expressed in a parent-of-origin manner consistentwith paternal and maternal imprints. Although the majority of the SNPs was identified in mitochondrial and Z-specific loci, theremaining SNPs found in male and female transcriptomes were situated in genes that have the potential to explain sexual differencesin schistosome parasites. Furthermore, we identified and validated four new Z-specific scaffolds. AU - Kincaid-Smith, Julien AU - Picard, Marion A L AU - Cosseau, Céline AU - Boissier, Jérôme AU - Severac, Dany AU - Grunau, Christoph AU - Toulza, Eve ID - 5989 IS - 3 JF - Genome Biology and Evolution SN - 1759-6653 TI - Parent-of-Origin-Dependent Gene Expression in Male and Female Schistosome Parasites VL - 10 ER - TY - CONF AB - Partially observable Markov decision processes (POMDPs) are the standard models for planning under uncertainty with both finite and infinite horizon. Besides the well-known discounted-sum objective, indefinite-horizon objective (aka Goal-POMDPs) is another classical objective for POMDPs. In this case, given a set of target states and a positive cost for each transition, the optimization objective is to minimize the expected total cost until a target state is reached. In the literature, RTDP-Bel or heuristic search value iteration (HSVI) have been used for solving Goal-POMDPs. Neither of these algorithms has theoretical convergence guarantees, and HSVI may even fail to terminate its trials. We give the following contributions: (1) We discuss the challenges introduced in Goal-POMDPs and illustrate how they prevent the original HSVI from converging. (2) We present a novel algorithm inspired by HSVI, termed Goal-HSVI, and show that our algorithm has convergence guarantees. (3) We show that Goal-HSVI outperforms RTDP-Bel on a set of well-known examples. AU - Horák, Karel AU - Bošanský, Branislav AU - Chatterjee, Krishnendu ID - 25 T2 - Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence TI - Goal-HSVI: Heuristic search value iteration for goal-POMDPs VL - 2018-July ER - TY - CONF AB - Partially-observable Markov decision processes (POMDPs) with discounted-sum payoff are a standard framework to model a wide range of problems related to decision making under uncertainty. Traditionally, the goal has been to obtain policies that optimize the expectation of the discounted-sum payoff. A key drawback of the expectation measure is that even low probability events with extreme payoff can significantly affect the expectation, and thus the obtained policies are not necessarily risk-averse. An alternate approach is to optimize the probability that the payoff is above a certain threshold, which allows obtaining risk-averse policies, but ignores optimization of the expectation. We consider the expectation optimization with probabilistic guarantee (EOPG) problem, where the goal is to optimize the expectation ensuring that the payoff is above a given threshold with at least a specified probability. We present several results on the EOPG problem, including the first algorithm to solve it. AU - Chatterjee, Krishnendu AU - Elgyütt, Adrian AU - Novotny, Petr AU - Rouillé, Owen ID - 24 TI - Expectation optimization with probabilistic guarantees in POMDPs with discounted-sum objectives VL - 2018 ER - TY - CONF AB - Partially observable Markov decision processes (POMDPs) are widely used in probabilistic planning problems in which an agent interacts with an environment using noisy and imprecise sensors. We study a setting in which the sensors are only partially defined and the goal is to synthesize “weakest” additional sensors, such that in the resulting POMDP, there is a small-memory policy for the agent that almost-surely (with probability 1) satisfies a reachability objective. We show that the problem is NP-complete, and present a symbolic algorithm by encoding the problem into SAT instances. We illustrate trade-offs between the amount of memory of the policy and the number of additional sensors on a simple example. We have implemented our approach and consider three classical POMDP examples from the literature, and show that in all the examples the number of sensors can be significantly decreased (as compared to the existing solutions in the literature) without increasing the complexity of the policies. AU - Chatterjee, Krishnendu AU - Chemlík, Martin AU - Topcu, Ufuk ID - 34 TI - Sensor synthesis for POMDPs with reachability objectives VL - 2018 ER -