@misc{5417,
  abstract     = {We define the model-measuring problem: given a model M and specification φ, what is the maximal distance ρ such that all models M'within distance ρ from M satisfy (or violate)φ. The model measuring problem presupposes a distance function on models. We concentrate on automatic distance functions, which are defined by weighted automata.
The model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, quantitative model-checking problems that measure the degree of satisfaction of a specification, and robustness problems that measure how much a model can be perturbed without violating the specification.
We show that for automatic distance functions, and ω-regular linear-time and branching-time specifications, the model-measuring problem can be solved.
We use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for standard word and tree automata by the optimal-weight question for the weighted versions of these automata. We consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging. 
We give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications.},
  author       = {Henzinger, Thomas A and Otop, Jan},
  issn         = {2664-1690},
  pages        = {14},
  publisher    = {IST Austria},
  title        = {{From model checking to model measuring}},
  doi          = {10.15479/AT:IST-2014-172-v1-1},
  year         = {2014},
}

@misc{5418,
  abstract     = {We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. Our results have tight connections with partial-observation stochastic games for which we derive new complexity results.},
  author       = {Chatterjee, Krishnendu and Doyen, Laurent},
  issn         = {2664-1690},
  pages        = {18},
  publisher    = {IST Austria},
  title        = {{Games with a weak adversary}},
  doi          = {10.15479/AT:IST-2014-176-v1-1},
  year         = {2014},
}

@misc{5419,
  abstract     = {We consider the reachability and shortest path problems on low tree-width graphs, with n nodes, m edges, and tree-width t, on a standard RAM with wordsize W. We use O to hide polynomial factors of the inverse of the Ackermann function. Our main contributions are three fold:
1. For reachability, we present an algorithm that requires O(n·t2·log(n/t)) preprocessing time, O(n·(t·log(n/t))/W) space, and O(t/W) time for pair queries and O((n·t)/W) time for single-source queries. Note that for constant t our algorithm uses O(n·logn) time for preprocessing; and O(n/W) time for single-source queries, which is faster than depth first search/breath first search (after the preprocessing).
2. We present an algorithm for shortest path that requires O(n·t2) preprocessing time, O(n·t) space, and O(t2) time for pair queries and O(n·t) time single-source queries.
3. We give a space versus query time trade-off algorithm for shortest path that, given any constant >0, requires O(n·t2) preprocessing time, O(n·t2) space, and O(n1−·t2) time for pair queries.
Our algorithms improve all existing results, and use very simple data structures.},
  author       = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas},
  issn         = {2664-1690},
  pages        = {34},
  publisher    = {IST Austria},
  title        = {{Improved algorithms for reachability and shortest path on low tree-width graphs}},
  doi          = {10.15479/AT:IST-2014-187-v1-1},
  year         = {2014},
}

@misc{5420,
  abstract     = {We consider concurrent mean-payoff games, a very well-studied class of two-player (player 1 vs player 2) zero-sum games on finite-state graphs where every transition is assigned a reward between 0 and 1, and the payoff function is the long-run average of the rewards. The value is the maximal expected payoff that player 1 can guarantee against all strategies of player 2. We consider the computation of the set of states with value 1 under finite-memory strategies for player 1, and our main results for the problem are as follows: (1) we present a polynomial-time algorithm; (2) we show that whenever there is a finite-memory strategy, there is a stationary strategy that does not need memory at all; and (3) we present an optimal bound (which is double exponential) on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy).},
  author       = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus},
  issn         = {2664-1690},
  pages        = {49},
  publisher    = {IST Austria},
  title        = {{The value 1 problem for concurrent mean-payoff games}},
  doi          = {10.15479/AT:IST-2014-191-v1-1},
  year         = {2014},
}

@misc{5421,
  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 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. 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: (1) We show that the qualitative question is NP-complete and the quantitative approximation question is #P-hard in the special case when the interaction and the replacement graphs coincide and even with the restriction that the resident individuals do not reproduce (which corresponds to an invading population taking over an empty structure). (2) We show that in general the qualitative question is PSPACE-complete and the quantitative approximation question is PSPACE-hard and can be solved in exponential time.},
  author       = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Nowak, Martin},
  issn         = {2664-1690},
  pages        = {27},
  publisher    = {IST Austria},
  title        = {{The complexity of evolution on graphs}},
  doi          = {10.15479/AT:IST-2014-190-v2-2},
  year         = {2014},
}

@techreport{5422,
  abstract     = {Notes from the Third Plenary for the Research Data Alliance in Dublin, Ireland on March 26 to 28, 2014 with focus on starting an institutional research data repository.},
  author       = {Porsche, Jana},
  publisher    = {none},
  title        = {{Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland}},
  year         = {2014},
}

@misc{5423,
  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 taskset 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 D(over), that have been proposed in the past, for various tasksets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are tasksets 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 Kössler, Alexander and Pavlogiannis, Andreas and Schmid, Ulrich},
  issn         = {2664-1690},
  pages        = {14},
  publisher    = {IST Austria},
  title        = {{A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks}},
  doi          = {10.15479/AT:IST-2014-300-v1-1},
  year         = {2014},
}

@misc{5424,
  abstract     = {We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty.},
  author       = {Chatterjee, Krishnendu and Chmelik, Martin and Gupta, Raghav and Kanodia, Ayush},
  issn         = {2664-1690},
  pages        = {12},
  publisher    = {IST Austria},
  title        = {{Qualitative analysis of POMDPs with temporal logic specifications for robotics applications}},
  doi          = {10.15479/AT:IST-2014-305-v1-1},
  year         = {2014},
}

@misc{5425,
  abstract     = { We consider partially observable Markov decision processes (POMDPs) with a set of target states and every transition is associated with an integer cost. The optimization objective we study asks to minimize the expected total cost till the target set is reached, while ensuring that the target set is reached almost-surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost and the bound is double exponential; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst-case running time of our algorithm is double exponential, we also present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples of interest.},
  author       = {Anonymous, 1 and Anonymous, 2 and Anonymous, 3 and Anonymous, 4},
  issn         = {2664-1690},
  pages        = {22},
  publisher    = {IST Austria},
  title        = {{Optimal cost almost-sure reachability in POMDPs}},
  year         = {2014},
}

@misc{5426,
  abstract     = {We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty.},
  author       = {Chatterjee, Krishnendu and Chmelik, Martin and Gupta, Raghav and Kanodia, Ayush},
  issn         = {2664-1690},
  pages        = {10},
  publisher    = {IST Austria},
  title        = {{Qualitative analysis of POMDPs with temporal logic specifications for robotics applications}},
  doi          = {10.15479/AT:IST-2014-305-v2-1},
  year         = {2014},
}

@misc{5427,
  abstract     = {We consider graphs with n nodes together with their tree-decomposition that has b = O ( n ) bags and width t , on the standard RAM computational model with wordsize W = Θ (log n ) . Our contributions are two-fold: Our first contribution is an algorithm that given a graph and its tree-decomposition as input, computes a binary and balanced tree-decomposition of width at most 4 · t + 3 of the graph in O ( b ) time and space, improving a long-standing (from 1992) bound of O ( n · log n ) time for constant treewidth graphs. Our second contribution is on reachability queries for low treewidth graphs. We build on our tree-balancing algorithm and present a data-structure for graph reachability that requires O ( n · t 2 ) preprocessing time, O ( n · t ) space, and O ( d t/ log n e ) time for pair queries, and O ( n · t · log t/ log n ) time for single-source queries. For constant t our data-structure uses O ( n ) time for preprocessing, O (1) time for pair queries, and O ( n/ log n ) time for single-source queries. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries.},
  author       = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas},
  issn         = {2664-1690},
  pages        = {24},
  publisher    = {IST Austria},
  title        = {{Optimal tree-decomposition balancing and reachability on low treewidth graphs}},
  doi          = {10.15479/AT:IST-2014-314-v1-1},
  year         = {2014},
}

@misc{5428,
  abstract     = {Simulation is an attractive alternative for language inclusion for automata as it is an under-approximation of language inclusion, but usually has much lower complexity. For non-deterministic automata, while language inclusion is PSPACE-complete, simulation can be computed in polynomial time. Simulation has also been extended in two orthogonal directions, namely, (1) fair simulation, for simulation over specified set of infinite runs; and (2) quantitative simulation, for simulation between weighted automata. Again, while fair trace inclusion is PSPACE-complete, fair simulation can be computed in polynomial time. For weighted automata, the (quantitative) language inclusion problem is undecidable for mean-payoff automata and the decidability is open for discounted-sum automata, whereas the (quantitative) simulation reduce to mean-payoff games and discounted-sum games, which admit pseudo-polynomial time algorithms.

In this work, we study (quantitative) simulation for weighted automata with Büchi acceptance conditions, i.e., we generalize fair simulation from non-weighted automata to weighted automata. We show that imposing Büchi acceptance conditions on weighted automata changes many fundamental properties of the simulation games. For example, whereas for mean-payoff and discounted-sum games, the players do not need memory to play optimally; we show in contrast that for simulation games with Büchi acceptance conditions, (i) for mean-payoff objectives, optimal strategies for both players require infinite memory in general, and (ii) for discounted-sum objectives, optimal strategies need not exist for both players. While the simulation games with Büchi acceptance conditions are more complicated (e.g., due to infinite-memory requirements for mean-payoff objectives) as compared to their counterpart without Büchi acceptance conditions, we still present pseudo-polynomial time algorithms to solve simulation games with Büchi acceptance conditions for both weighted mean-payoff and weighted discounted-sum automata.},
  author       = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan and Velner, Yaron},
  issn         = {2664-1690},
  pages        = {26},
  publisher    = {IST Austria},
  title        = {{Quantitative fair simulation games}},
  doi          = {10.15479/AT:IST-2014-315-v1-1},
  year         = {2014},
}

@article{5813,
  abstract     = {We consider homogeneous Bose gas in a large cubic box with periodic boundary conditions, at zero temperature. We analyze its excitation spectrum in a certain kind of a mean-field infinite-volume limit. We prove that under appropriate conditions the excitation spectrum has the form predicted by the Bogoliubov approximation. Our result can be viewed as an extension of the result of Seiringer (Commun. Math. Phys.306:565–578, 2011) to large volumes.},
  author       = {Dereziński, Jan and Napiórkowski, Marcin M},
  issn         = {1424-0637},
  journal      = {Annales Henri Poincaré},
  number       = {12},
  pages        = {2409--2439},
  publisher    = {Springer Nature},
  title        = {{Excitation spectrum of interacting bosons in the Mean-Field Infinite-Volume limit}},
  doi          = {10.1007/s00023-013-0302-4},
  volume       = {15},
  year         = {2014},
}

@article{589,
  abstract     = {We demonstrate a many-atom-cavity system with a high-finesse dual-wavelength standing wave cavity in which all participating rubidium atoms are nearly identically coupled to a 780-nm cavity mode. This homogeneous coupling is enforced by a one-dimensional optical lattice formed by the field of a 1560-nm cavity mode.},
  author       = {Lee, Jongmin and Vrijsen, Geert and Teper, Igor and Onur Hosten and Kasevich, Mark A},
  journal      = {Optics Letters},
  number       = {13},
  pages        = {4005 -- 4008},
  publisher    = {OSA},
  title        = {{Many-atom-cavity QED system with homogeneous atom-cavity coupling}},
  doi          = {10.1364/OL.39.004005},
  volume       = {39},
  year         = {2014},
}

@article{6122,
  author       = {Linneweber, Gerit A. and Jacobson, Jake and Busch, Karl Emanuel and Hudry, Bruno and Christov, Christo P. and Dormann, Dirk and Yuan, Michaela and Otani, Tomoki and Knust, Elisabeth and de Bono, Mario and Miguel-Aliaga, Irene},
  issn         = {0092-8674},
  journal      = {Cell},
  number       = {1-2},
  pages        = {69--83},
  publisher    = {Elsevier},
  title        = {{Neuronal control of metabolism through nutrient-dependent modulation of tracheal branching}},
  doi          = {10.1016/j.cell.2013.12.008},
  volume       = {156},
  year         = {2014},
}

@article{6124,
  abstract     = {Despite the importance of G-protein coupled receptors (GPCRs) their biogenesis is poorly understood. Like vertebrates, C. elegans uses a large family of GPCRs as chemoreceptors. A subset of these receptors, such as ODR-10, requires the odr-4 and odr-8 genes to be appropriately localized to sensory cilia. The odr-4 gene encodes a conserved tail-anchored transmembrane protein; the molecular identity of odr-8 is unknown. Here, we show that odr-8 encodes the C. elegans ortholog of Ufm1-specific protease 2 (UfSP2). UfSPs are cysteine proteases identified biochemically by their ability to liberate the ubiquitin-like modifier Ufm1 from its pro-form and protein conjugates. ODR-8/UfSP2 and ODR-4 are expressed in the same set of twelve chemosensory neurons, and physically interact at the ER membrane. ODR-4 also binds ODR-10, suggesting that an ODR-4/ODR-8 complex promotes GPCR folding, maturation, or export from the ER. The physical interaction between human ODR4 and UfSP2 suggests that this complex's role in GPCR biogenesis may be evolutionarily conserved. Unexpectedly, mutant versions of ODR-8/UfSP2 lacking catalytic residues required for protease activity can rescue all odr-8 mutant phenotypes tested. Moreover, deleting C. elegans ufm-1 does not alter chemoreceptor traffic to cilia, either in wild type or in odr-8 mutants. Thus, UfSP2 proteins have protease- and Ufm1-independent functions in GPCR biogenesis.},
  author       = {Chen, Changchun and Itakura, Eisuke and Weber, Katherine P. and Hegde, Ramanujan S. and de Bono, Mario},
  issn         = {1553-7404},
  journal      = {PLoS Genetics},
  number       = {3},
  publisher    = {Public Library of Science (PLoS)},
  title        = {{An ER complex of ODR-4 and ODR-8/Ufm1 specific protease 2 promotes GPCR maturation by a Ufm1-independent mechanism}},
  doi          = {10.1371/journal.pgen.1004082},
  volume       = {10},
  year         = {2014},
}

@article{6126,
  abstract     = {Aerobic animals constantly monitor and adapt to changes in O2 levels. The molecular mechanisms involved in sensing O2 are, however, incompletely understood. Previous studies showed that a hexacoordinated globin called GLB-5 tunes the dynamic range of O2-sensing neurons in natural C. elegans isolates, but is defective in the N2 lab reference strain (McGrath et al., 2009; Persson et al., 2009). GLB-5 enables a sharp behavioral switch when O2 changes between 21 and 17%. Here, we show that GLB-5 also confers rapid behavioral and cellular recovery from exposure to hypoxia. Hypoxia reconfigures O2-evoked Ca2+ responses in the URX O2 sensors, and GLB-5 enables rapid recovery of these responses upon re-oxygenation. Forward genetic screens indicate that GLB-5's effects on O2 sensing require PDL-1, the C. elegans ortholog of mammalian PrBP/PDE6δ protein. In mammals, PDE6δ regulates the traffic and activity of prenylated proteins (Zhang et al., 2004; Norton et al., 2005). PDL-1 promotes localization of GCY-33 and GCY-35, atypical soluble guanylate cyclases that act as O2 sensors, to the dendritic endings of URX and BAG neurons, where they colocalize with GLB-5. Both GCY-33 and GCY-35 are predicted to be prenylated. Dendritic localization is not essential for GCY-35 to function as an O2 sensor, but disrupting pdl-1 alters the URX neuron's O2 response properties. Functional GLB-5 can restore dendritic localization of GCY-33 in pdl-1 mutants, suggesting GCY-33 and GLB-5 are in a complex. Our data suggest GLB-5 and the soluble guanylate cyclases operate in close proximity to sculpt O2 responses.},
  author       = {Gross, E. and Soltesz, Z. and Oda, S. and Zelmanovich, V. and Abergel, Z. and de Bono, Mario},
  issn         = {0270-6474},
  journal      = {Journal of Neuroscience},
  number       = {50},
  pages        = {16726--16738},
  publisher    = {Society for Neuroscience},
  title        = {{GLOBIN-5-dependent O2 responses are regulated by PDL-1/PrBP that targets prenylated soluble guanylate cyclases to dendritic endings}},
  doi          = {10.1523/jneurosci.5368-13.2014},
  volume       = {34},
  year         = {2014},
}

@article{6319,
  abstract     = {Nous étudions le comportement asymptotique du nombre de variétés dans une certaine classe ne satisfaisant pas le principe de Hasse. Cette étude repose sur des résultats récemmentobtenus par Colliot-Thélène.},
  author       = {Bretèche, Régis de la and Browning, Timothy D},
  issn         = {1246-7405},
  journal      = {Journal de Théorie des Nombres de Bordeaux},
  number       = {1},
  pages        = {25--44},
  publisher    = {Cellule MathDoc/CEDRAM},
  title        = {{Contre-exemples au principe de Hasse pour certains tores coflasques}},
  doi          = {10.5802/jtnb.857},
  volume       = {26},
  year         = {2014},
}

@article{6739,
  abstract     = {We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that “interpolates” between RM and polar codes, call this family C inter = {C α : α ∈ [0, 1j}, where C α|α=1 is the original polar code, and C α|α=0 is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of α. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family Cinter even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.},
  author       = {Mondelli, Marco and Hassani, Hamed and Urbanke, Rudiger},
  issn         = {0090-6778},
  journal      = {IEEE Transactions on Communications},
  number       = {9},
  pages        = {3084--3091},
  publisher    = {IEEE},
  title        = {{From polar to Reed-Muller codes: A technique to improve the finite-length performance}},
  doi          = {10.1109/tcomm.2014.2345069},
  volume       = {62},
  year         = {2014},
}

@inproceedings{6740,
  abstract     = {We describe coding techniques that achieve the capacity of a discrete memoryless asymmetric channel. To do so, we discuss how recent advances in coding for symmetric channels yield more efficient solutions also for the asymmetric case. In more detail, we consider three basic approaches. The first one is Gallager's scheme that concatenates a linear code with a non-linear mapper, in order to bias the input distribution. We explicitly show that both polar codes and spatially coupled codes can be employed in this scenario. Further, we derive a scaling law between the gap to capacity, the cardinality of channel input and output alphabets, and the required size of the mapper. The second one is an integrated approach in which the coding scheme is used both for source coding, in order to create codewords with the capacity-achieving distribution, and for channel coding, in order to provide error protection. Such a technique has been recently introduced by Honda and Yamamoto in the context of polar codes, and we show how to apply it also to the design of sparse graph codes. The third approach is based on an idea due to Böcherer and Mathar and separates completely the two tasks of source coding and channel coding by “chaining” together several codewords. We prove that we can combine any suitable source code with any suitable channel code in order to provide optimal schemes for asymmetric channels. In particular, polar codes and spatially coupled codes fulfill the required conditions.},
  author       = {Mondelli, Marco and Urbanke, Rudiger and Hassani, Hamed},
  booktitle    = {52nd Annual Allerton Conference on Communication, Control, and Computing},
  location     = {Monticello, IL, United States},
  pages        = {789--796},
  publisher    = {IEEE},
  title        = {{How to achieve the capacity of asymmetric channels}},
  doi          = {10.1109/allerton.2014.7028535},
  year         = {2014},
}