@article{3045, abstract = {Dynamically polarized membrane proteins define different cell boundaries and have an important role in intercellular communication - a vital feature of multicellular development. Efflux carriers for the signalling molecule auxin from the PIN family are landmarks of cell polarity in plants and have a crucial involvement in auxin distribution-dependent development including embryo patterning, organogenesis and tropisms. Polar PIN localization determines the direction of intercellular auxin flow, yet the mechanisms generating PIN polarity remain unclear. Here we identify an endocytosis-dependent mechanism of PIN polarity generation and analyse its developmental implications. Real-time PIN tracking showed that after synthesis, PINs are initially delivered to the plasma membrane in a non-polar manner and their polarity is established by subsequent endocytic recycling. Interference with PIN endocytosis either by auxin or by manipulation of the Arabidopsis Rab5 GTPase pathway prevents PIN polarization. Failure of PIN polarization transiently alters asymmetric auxin distribution during embryogenesis and increases the local auxin response in apical embryo regions. This results in ectopic expression of auxin pathway-associated root-forming master regulators in embryonic leaves and promotes homeotic transformation of leaves to roots. Our results indicate a two-step mechanism for the generation of PIN polar localization and the essential role of endocytosis in this process. It also highlights the link between endocytosis-dependent polarity of individual cells and auxin distribution-dependent cell fate establishment for multicellular patterning.}, author = {Dhonukshe, Pankaj and Tanaka, Hirokazu and Goh, Tatsuaki and Ebine, Kazuo and Mähönen, Ari Pekka and Prasad, Kalika and Blilou, Ikram and Geldner, Niko and Xu, Jian and Uemura, Tomohiro and Chory, Joanne and Ueda, Takashi and Nakano, Akihiko and Scheres, Ben and Jirí Friml}, journal = {Nature}, number = {7224}, pages = {962 -- 966}, publisher = {Nature Publishing Group}, title = {{Generation of cell polarity in plants links endocytosis auxin distribution and cell fate decisions}}, doi = {10.1038/nature07409}, volume = {456}, year = {2008}, } @inproceedings{3194, abstract = {We consider the problem of optimizing multilabel MRFs, which is in general NP-hard and ubiquitous in low-level computer vision. One approach for its solution is to formulate it as an integer linear programming and relax the integrality constraints. The approach we consider in this paper is to first convert the multi-label MRF into an equivalent binary-label MRF and then to relax it. The resulting relaxation can be efficiently solved using a maximum flow algorithm. Its solution provides us with a partially optimal labelling of the binary variables. This partial labelling is then easily transferred to the multi-label problem. We study the theoretical properties of the new relaxation and compare it with the standard one. Specifically, we compare tightness, and characterize a subclass of problems where the two relaxations coincide. We propose several combined algorithms based on the technique and demonstrate their performance on challenging computer vision problems.}, author = {Kohli, Pushmeet and Shekhovtsov, Alexander and Rother, Carsten and Vladimir Kolmogorov and Torr, Philip H}, pages = {480 -- 487}, publisher = {Omnipress}, title = {{On partial optimality in multi label MRFs}}, doi = {10.1145/1390156.1390217}, year = {2008}, } @inproceedings{3195, abstract = {Graph cut is a popular technique for interactive image segmentation. However, it has certain shortcomings. In particular, graph cut has problems with segmenting thin elongated objects due to the ldquoshrinking biasrdquo. To overcome this problem, we propose to impose an additional connectivity prior, which is a very natural assumption about objects. We formulate several versions of the connectivity constraint and show that the corresponding optimization problems are all NP-hard. For some of these versions we propose two optimization algorithms: (i) a practical heuristic technique which we call DijkstraGC, and (ii) a slow method based on problem decomposition which provides a lower bound on the problem. We use the second technique to verify that for some practical examples DijkstraGC is able to find the global minimum.}, author = {Vicente, Sara and Vladimir Kolmogorov and Rother, Carsten}, publisher = {IEEE}, title = {{Graph cut based image segmentation with connectivity priors}}, doi = {10.1109/CVPR.2008.4587440}, year = {2008}, } @article{3196, abstract = {Among the most exciting advances in early vision has been the development of efficient energy minimization algorithms for pixel-labeling tasks such as depth or texture computation. It has been known for decades that such problems can be elegantly expressed as Markov random fields, yet the resulting energy minimization problems have been widely viewed as intractable. Algorithms such as graph cuts and loopy belief propagation (LBP) have proven to be very powerful: For example, such methods form the basis for almost all the top-performing stereo methods. However, the trade-offs among different energy minimization algorithms are still not well understood. In this paper, we describe a set of energy minimization benchmarks and use them to compare the solution quality and runtime of several common energy minimization algorithms. We investigate three promising methods-graph cuts, LBP, and tree-reweighted message passing-in addition to the well-known older iterated conditional mode (ICM) algorithm. Our benchmark problems are drawn from published energy functions used for stereo, image stitching, interactive segmentation, and denoising. We also provide a general-purpose software interface that allows vision researchers to easily switch between optimization methods. The benchmarks, code, images, and results are available at http://vision.middlebury.edu/MRF/.}, author = {Szeliski, Richard S and Zabih, Ramin and Scharstein, Daniel and Veksler, Olga and Vladimir Kolmogorov and Agarwala, Aseem and Tappen, Marshall F and Rother, Carsten}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, number = {6}, pages = {1068 -- 1080}, publisher = {IEEE}, title = {{A comparative study of energy minimization methods for Markov random fields with smoothness-based priors}}, doi = {10.1109/TPAMI.2007.70844}, volume = {30}, year = {2008}, } @inproceedings{3198, abstract = {In this paper we present a new approach for establishing correspondences between sparse image features related by an unknown non-rigid mapping and corrupted by clutter and occlusion, such as points extracted from a pair of images containing a human figure in distinct poses. We formulate this matching task as an energy minimization problem by defining a complex objective function of the appearance and the spatial arrangement of the features. Optimization of this energy is an instance of graph matching, which is in general a NP-hard problem. We describe a novel graph matching optimization technique, which we refer to as dual decomposition (DD), and demonstrate on a variety of examples that this method outperforms existing graph matching algorithms. In the majority of our examples DD is able to find the global minimum within a minute. The ability to globally optimize the objective allows us to accurately learn the parameters of our matching model from training examples. We show on several matching tasks that our learned model yields results superior to those of state-of-the-art methods. }, author = {Torresani, Lorenzo and Vladimir Kolmogorov and Rother, Carsten}, pages = {596 -- 609}, publisher = {Springer}, title = {{Feature correspondence via graph matching: Models and global optimization}}, doi = {10.1007/978-3-540-88688-4_44}, volume = {5303}, year = {2008}, } @inproceedings{3224, abstract = {We propose a new mode of operation, enciphered CBC, for domain extension of length-preserving functions (like block ciphers), which is a variation on the popular CBC mode of operation. Our new mode is twice slower than CBC, but has many (property-preserving) properties not enjoyed by CBC and other known modes. Most notably, it yields the first constant-rate Variable Input Length (VIL) MAC from any length preserving Fixed Input Length (FIL) MAC. This answers the question of Dodis and Puniya from Eurocrypt 2007. Further, our mode is a secure domain extender for PRFs (with basically the same security as encrypted CBC). This provides a hedge against the security of the block cipher: if the block cipher is pseudorandom, one gets a VIL-PRF, while if it is "only" unpredictable, one "at least" gets a VIL-MAC. Additionally, our mode yields a VIL random oracle (and, hence, a collision-resistant hash function) when instantiated with length-preserving random functions, or even random permutations (which can be queried from both sides). This means that one does not have to re-key the block cipher during the computation, which was critically used in most previous constructions (analyzed in the ideal cipher model). }, author = {Dodis, Yevgeniy and Krzysztof Pietrzak and Puniya, Prashant}, pages = {198 -- 219}, publisher = {Springer}, title = {{A new mode of operation for block ciphers and length preserving MACs}}, doi = {10.1007/978-3-540-78967-3_12}, volume = {4965}, year = {2008}, } @inproceedings{3225, abstract = {A robust multi-property combiner for a set of security properties merges two hash functions such that the resulting function satisfies each of the properties which at least one of the two starting functions has. Fischlin and Lehmann (TCC 2008) recently constructed a combiner which simultaneously preserves collision-resistance, target collision-resistance, message authentication, pseudorandomness and indifferentiability from a random oracle (IRO). Their combiner produces outputs of 5n bits, where n denotes the output length of the underlying hash functions. In this paper we propose improved combiners with shorter outputs. By sacrificing the indifferentiability from random oracles we obtain a combiner which preserves all of the other aforementioned properties but with output length 2n only. This matches a lower bound for black-box combiners for collision-resistance as the only property, showing that the other properties can be achieved without penalizing the length of the hash values. We then propose a combiner which also preserves the IRO property, slightly increasing the output length to 2n + ω(logn). Finally, we show that a twist on our combiners also makes them robust for one-wayness (but at the price of a fixed input length). }, author = {Fischlin, Marc and Lehmann, Anja and Krzysztof Pietrzak}, number = {PART 2}, pages = {655 -- 666}, publisher = {Springer}, title = {{Robust multi property combiners for hash functions revisited}}, doi = {10.1007/978-3-540-70583-3_53}, volume = {5126}, year = {2008}, } @inproceedings{3226, abstract = {A family of functions is weakly pseudorandom if a random member of the family is indistinguishable from a uniform random function when queried on random inputs. We point out a subtle ambiguity in the definition of weak PRFs: there are natural weak PRFs whose security breaks down if the randomness used to sample the inputs is revealed. To capture this ambiguity we distinguish between public-coin and secret-coin weak PRFs. We show that the existence of a secret-coin weak PRF which is not also a public-coin weak PRF implies the existence of two pass key-agreement (i.e. public-key encryption). So in Minicrypt, i.e. under the assumption that one-way functions exist but public-key cryptography does not, the notion of public- and secret-coin weak PRFs coincide. Previous to this paper all positive cryptographic statements known to hold exclusively in Minicrypt concerned the adaptive security of constructions using non-adaptively secure components. Weak PRFs give rise to a new set of statements having this property. As another example we consider the problem of range extension for weak PRFs. We show that in Minicrypt one can beat the best possible range expansion factor (using a fixed number of distinct keys) for a very general class of constructions (in particular, this class contains all constructions that are known today). }, author = {Krzysztof Pietrzak and Sjödin, Johan}, number = {PART 2}, pages = {423 -- 436}, publisher = {Springer}, title = {{Weak pseudorandom functions in minicrypt}}, doi = {10.1007/978-3-540-70583-3_35}, volume = {5126}, year = {2008}, } @article{3227, abstract = {Large amount of data management can cause a lot of troubles which can be solved by dedicated computer system. To facilitate management of measurement data which are gathered in Institute of Power Engineering - Insulation Department a special system called Elektrowiz® was developed. It allows storing measurement results which concern partial discharges in insulation of turbo- and hydrogenerators in power stations. Multilayer architecture of the system allows reaching gathered data independently on user localization. There are possible different access methods to the system and dependency on current requirements data exploration can be realized with read-only or edit rights.}, author = {Zubielik, Piotr and Nadaczny, Jerzy and Krzysztof Pietrzak and Lawenda, Marcin}, journal = {Przeglad Elektrotechniczny}, number = {10}, pages = {239 -- 242}, publisher = {SIGMA-NOT}, title = {{Elektrowiz – system of measurement data management}}, volume = {84}, year = {2008}, } @inproceedings{3228, abstract = { A black-box combiner for collision resistant hash functions (CRHF) is a construction which given black-box access to two hash functions is collision resistant if at least one of the components is collision resistant. In this paper we prove a lower bound on the output length of black-box combiners for CRHFs. The bound we prove is basically tight as it is achieved by a recent construction of Canetti et al [Crypto'07]. The best previously known lower bounds only ruled out a very restricted class of combiners having a very strong security reduction: the reduction was required to output collisions for both underlying candidate hash-functions given a single collision for the combiner (Canetti et al [Crypto'07] building on Boneh and Boyen [Crypto'06] and Pietrzak [Eurocrypt'07]). Our proof uses a lemma similar to the elegant "reconstruction lemma" of Gennaro and Trevisan [FOCS'00], which states that any function which is not one-way is compressible (and thus uniformly random function must be one-way). In a similar vein we show that a function which is not collision resistant is compressible. We also borrow ideas from recent work by Haitner et al. [FOCS'07], who show that one can prove the reconstruction lemma even relative to some very powerful oracles (in our case this will be an exponential time collision-finding oracle). © 2008 Springer-Verlag Berlin Heidelberg.}, author = {Krzysztof Pietrzak}, pages = {413 -- 432}, publisher = {Springer}, title = {{Compression from collisions or why CRHF combiners have a long output}}, doi = {10.1007/978-3-540-85174-5_23}, volume = {5157}, year = {2008}, } @inproceedings{3229, abstract = {We construct a stream-cipher S whose implementation is secure even if a bounded amount of arbitrary (adversarially chosen) information on the internal state ofS is leaked during computation. This captures all possible side-channel attacks on S where the amount of information leaked in a given period is bounded, but overall can be arbitrary large. The only other assumption we make on the implementation of S is that only data that is accessed during computation leaks information. The stream-cipher S generates its output in chunks K1, K2, . . . and arbitrary but bounded information leakage is modeled by allowing the adversary to adaptively chose a function fl : {0,1}* rarr {0, 1}lambda before Kl is computed, she then gets fl(taul) where taul is the internal state ofS that is accessed during the computation of Kg. One notion of security we prove for S is that Kg is indistinguishable from random when given K1,..., K1-1,f1(tau1 ),..., fl-1(taul-1) and also the complete internal state of S after Kg has been computed (i.e. S is forward-secure). The construction is based on alternating extraction (used in the intrusion-resilient secret-sharing scheme from FOCS'07). We move this concept to the computational setting by proving a lemma that states that the output of any PRG has high HILLpseudoentropy (i.e. is indistinguishable from some distribution with high min-entropy) even if arbitrary information about the seed is leaked. The amount of leakage lambda that we can tolerate in each step depends on the strength of the underlying PRG, it is at least logarithmic, but can be as large as a constant fraction of the internal state of S if the PRG is exponentially hard.}, author = {Dziembowski, Stefan and Krzysztof Pietrzak}, pages = {293 -- 302}, publisher = {IEEE}, title = {{Leakage resilient cryptography}}, doi = {10.1109/FOCS.2008.56}, year = {2008}, } @article{3291, abstract = {The filamentous fungus Aspergillus fumigatus is responsible for a lethal disease called Invasive Aspergillosis that affects immunocompromised patients. This disease, like other human fungal diseases, is generally treated by compounds targeting the primary fungal cell membrane sterol. Recently, glucan synthesis inhibitors were added to the limited antifungal arsenal and encouraged the search for novel targets in cell wall biosynthesis. Although galactomannan is a major component of the A. fumigatus cell wall and extracellular matrix, the biosynthesis and role of galactomannan are currently unknown. By a targeted gene deletion approach, we demonstrate that UDP-galactopyranose mutase, a key enzyme of galactofuranose metabolism, controls the biosynthesis of galactomannan and galactofuranose containing glycoconjugates. The glfA deletion mutant generated in this study is devoid of galactofuranose and displays attenuated virulence in a low-dose mouse model of invasive aspergillosis that likely reflects the impaired growth of the mutant at mammalian body temperature. Furthermore, the absence of galactofuranose results in a thinner cell wall that correlates with an increased susceptibility to several antifungal agents. The UDP-galactopyranose mutase thus appears to be an appealing adjunct therapeutic target in combination with other drugs against A. fumigatus. Its absence from mammalian cells indeed offers a considerable advantage to achieve therapeutic selectivity. }, author = {Philipp Schmalhorst and Krappmann, Sven and Vervecken, Wouter and Rohde, Manfred and Müller, Meike and Braus, Gerhard H. and Contreras, Roland and Braun, Armin and Bakker, Hans and Routier, Françoise H}, journal = {Eukaryotic Cell}, number = {8}, pages = {1268 -- 1277}, publisher = {American Society for Microbiology}, title = {{Contribution of galactofuranose to the virulence of the opportunistic pathogen Aspergillus fumigatus}}, doi = {10.1128/EC.00065-08}, volume = {7}, year = {2008}, } @article{3307, abstract = {A complete mitochondrial (mt) genome sequence was reconstructed from a 38,000 year-old Neandertal individual with 8341 mtDNA sequences identified among 4.8 Gb of DNA generated from ∼0.3 g of bone. Analysis of the assembled sequence unequivocally establishes that the Neandertal mtDNA falls outside the variation of extant human mtDNAs, and allows an estimate of the divergence date between the two mtDNA lineages of 660,000 ± 140,000 years. Of the 13 proteins encoded in the mtDNA, subunit 2 of cytochrome c oxidase of the mitochondrial electron transport chain has experienced the largest number of amino acid substitutions in human ancestors since the separation from Neandertals. There is evidence that purifying selection in the Neandertal mtDNA was reduced compared with other primate lineages, suggesting that the effective population size of Neandertals was small.}, author = {Green, Richard E and Malaspinas, Anna-Sapfo and Krause, Johannes and Briggs, Adrian W and Johnson, Philip L and Caroline Uhler and Meyer, Matthias and Good, Jeffrey M and Maricic, Tomislav and Stenzel, Udo and Prüfer, Kay and Siebauer, Michael F and Burbano, Hernän A and Ronan, Michael T and Rothberg, Jonathan M and Egholm, Michael and Rudan, Pavao and Brajković, Dejana and Kućan, Željko and Gušić, Ivan and Wikström, Mårten K and Laakkonen, Liisa J and Kelso, Janet F and Slatkin, Montgomery and Pääbo, Svante H}, journal = {Cell}, pages = {416 -- 426}, publisher = {Cell Press}, title = {{A complete neandertal mitochondrial genome sequence determined by highhhroughput sequencing}}, doi = {10.1016/j.cell.2008.06.021}, volume = {134}, year = {2008}, } @article{3409, abstract = {With the introduction of single-molecule force spectroscopy (SMFS) it has become possible to directly access the interactions of various molecular systems. A bottleneck in conventional SMFS is collecting the large amount of data required for statistically meaningful analysis. Currently, atomic force microscopy (AFM)-based SMFS requires the user to tediously 'fish' for single molecules. In addition, most experimental and environmental conditions must be manually adjusted. Here, we developed a fully automated single-molecule force spectroscope. The instrument is able to perform SMFS while monitoring and regulating experimental conditions such as buffer composition and temperature. Cantilever alignment and calibration can also be automatically performed during experiments. This, combined with in-line data analysis, enables the instrument, once set up, to perform complete SMFS experiments autonomously.}, author = {Struckmeier, Jens and Wahl, Reiner and Leuschner, Mirko and Nunes, Joao and Harald Janovjak and Geisler, Ulrich and Hofmann, Gerd and Jähnke, Torsten and Mueller, Daniel J}, journal = {Nanotechnology}, number = {38}, publisher = {IOP Publishing Ltd.}, title = {{Fully automated single-molecule force spectroscopy for screening applications}}, doi = {10.1088/0957-4484/19/38/384020}, volume = {19}, year = {2008}, } @misc{3410, abstract = {Membrane proteins are involved in essential biological processes such as energy conversion, signal transduction, solute transport and secretion. All biological processes, also those involving membrane proteins, are steered by molecular interactions. Molecular interactions guide the folding and stability of membrane proteins, determine their assembly, switch their functional states or mediate signal transduction. The sequential steps of molecular interactions driving these processes can be described by dynamic energy landscapes. The conceptual energy landscape allows to follow the complex reaction pathways of membrane proteins while its modifications describe why and how pathways are changed. Single-molecule force spectroscopy (SMFS) detects, quantifies and locates interactions within and between membrane proteins. SMFS helps to determine how these interactions change with temperature, point mutations, oligomerization and the functional states of membrane proteins. Applied in different modes, SMFS explores the co-existence and population of reaction pathways in the energy landscape of the protein and thus reveals detailed insights into local mechanisms, determining its structural and functional relationships. Here we review how SMFS extracts the defining parameters of an energy landscape such as the barrier position, reaction kinetics and roughness with high precision.}, author = {Harald Janovjak and Sapra, Tanuj K and Kedrov, Alexej and Mueller, Daniel J}, booktitle = {ChemPhysChem}, number = {7}, pages = {954 -- 966}, publisher = {Wiley-Blackwell}, title = {{From valleys to ridges: Exploring the energy landscape of single membrane proteins}}, doi = {10.1002/cphc.200700662}, volume = {9}, year = {2008}, } @article{3435, abstract = {We develop a new method for estimating effective population sizes, Ne, and selection coefficients, s, from time-series data of allele frequencies sampled from a single diallelic locus. The method is based on calculating transition probabilities, using a numerical solution of the diffusion process, and assuming independent binomial sampling from this diffusion process at each time point. We apply the method in two example applications. First, we estimate selection coefficients acting on the CCR5-Δ32 mutation on the basis of published samples of contemporary and ancient human DNA. We show that the data are compatible with the assumption of s = 0, although moderate amounts of selection acting on this mutation cannot be excluded. In our second example, we estimate the selection coefficient acting on a mutation segregating in an experimental phage population. We show that the selection coefficient acting on this mutation is ~0.43.}, author = {Jonathan Bollback and York, Thomas L and Nielsen, Rasmus}, journal = {Genetics}, number = {1}, pages = {497 -- 502}, publisher = {Genetics Society of America}, title = {{Estimation of 2Nes From Temporal Allele Frequency Data}}, doi = {10.1534/genetics.107.085019}, volume = {179}, year = {2008}, } @inproceedings{3501, abstract = {The Wikipedia is a collaborative encyclopedia: anyone can contribute to its articles simply by clicking on an "edit" button. The open nature of the Wikipedia has been key to its success, but has also created a challenge: how can readers develop an informed opinion on its reliability? We propose a system that computes quantitative values of trust for the text in Wikipedia articles; these trust values provide an indication of text reliability. The system uses as input the revision history of each article, as well as information about the reputation of the contributing authors, as provided by a reputation system. The trust of a word in an article is computed on the basis of the reputation of the original author of the word, as well as the reputation of all authors who edited text near the word. The algorithm computes word trust values that vary smoothly across the text; the trust values can be visualized using varying text-background colors. The algorithm ensures that all changes to an article's text are reflected in the trust values, preventing surreptitious content changes. We have implemented the proposed system, and we have used it to compute and display the trust of the text of thousands of articles of the English Wikipedia. To validate our trust-computation algorithms, we show that text labeled as low-trust has a significantly higher probability of being edited in the future than text labeled as high-trust.}, author = {Adler, B Thomas and Krishnendu Chatterjee and de Alfaro, Luca and Faella, Marco and Pye, Ian and Raman, Vishwanath}, publisher = {ACM}, title = {{Assigning trust to Wikipedia content}}, doi = {10.1145/1822258.1822293}, year = {2008}, } @inproceedings{3502, abstract = {In content-driven reputation systems for collaborative content, users gain or lose reputation according to how their contributions fare: authors of long-lived contributions gain reputation, while authors of reverted contributions lose reputation. Existing content-driven systems are prone to Sybil attacks, in which multiple identities, controlled by the same person, perform coordinated actions to increase their reputation. We show that content-driven reputation systems can be made resistant to such attacks by taking advantage of thefact that the reputation increments and decrements depend on content modifications, which are visible to all. We present an algorithm for content-driven reputation that prevents a set of identities from increasing their maximum reputation without doing any useful work. Here, work is considered useful if it causes content to evolve in a direction that is consistent with the actions of high-reputation users. We argue that the content modifications that require no effort, such as the insertion or deletion of arbitrary text, are invariably non-useful. We prove a truthfullness result for the resulting system, stating that users who wish to perform a contribution do not gain by employing complex contribution schemes, compared to simply performing the contribution at once. In particular, splitting the contribution in multiple portions, or employing the coordinated actions of multiple identities, do not yield additional reputation. Taken together, these results indicate that content-driven systems can be made robust with respect to Sybil attacks. Copyright 2008 ACM.}, author = {Krishnendu Chatterjee and de Alfaro, Luca and Pye, Ian}, pages = {33 -- 42}, publisher = {ACM}, title = {{Robust content-driven reputation}}, doi = {10.1145/1456377.1456387 }, year = {2008}, } @inproceedings{3504, abstract = {Simulation and bisimulation metrics for stochastic systems provide a quantitative gen- eralization of the classical simulation and bisimulation relations. These metrics capture the similarity of states with respect to quantitative specifications written in the quantitative μ-calculus and related probabilistic logics. We present algorithms for computing the metrics on Markov decision processes (MDPs), turn- based stochastic games, and concurrent games. For turn-based games and MDPs, we provide a polynomial-time algorithm based on linear programming for the computation of the one-step metric distance between states. The algorithm improves on the previously known exponential-time algo- rithm based on a reduction to the theory of reals. We then present PSPACE algorithms for both the decision problem and the problem of approximating the metric distance between two states, matching the best known bound for Markov chains. For the bisimulation kernel of the metric, which corresponds to probabilistic bisimulation, our algorithm works in time O(n4) for both turn-based games and MDPs; improving the previously best known O(n9 · log(n)) time algorithm for MDPs. For a concurrent game G, we show that computing the exact distance between states is at least as hard as computing the value of concurrent reachability games and the square-root-sum problem in computational geometry. We show that checking whether the metric distance is bounded by a rational r, can be accomplished via a reduction to the theory of real closed fields, involving a formula with three quantifier alternations, yielding O(|G|O(|G|5)) time complexity, improving the previously known reduction with O(|G|O(|G|7)) time complexity. These algorithms can be iterated to approximate the metrics using binary search.}, author = {Chatterjee, Krishnendu and De Alfaro, Luca and Majumdar, Ritankar and Raman, Vishwanath}, pages = {107 -- 118}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Algorithms for game metrics}}, doi = {10.4230/LIPIcs.FSTTCS.2008.1745}, volume = {2}, year = {2008}, } @article{3516, abstract = {Temporal coding is a means of representing information by the time, as opposed to the rate, at which neurons fire. Evidence of temporal coding in the hippocampus comes from place cells, whose spike times relative to theta oscillations reflect a rat's position while running along stereotyped trajectories. This arises from the backwards shift in cell firing relative to local theta oscillations (phase precession). Here we demonstrate phase precession during place-field crossings in an open-field foraging task. This produced spike sequences in each theta cycle that disambiguate the rat's trajectory through two-dimensional space and can be used to predict movement direction. Furthermore, position and movement direction were maximally predicted from firing in the early and late portions of the theta cycle, respectively. This represents the first direct evidence of a combined representation of position, trajectory and heading in the hippocampus, organized on a fine temporal scale by theta oscillations.}, author = {Huxter,John R and Senior,Timothy J and Allen, Kevin and Jozsef Csicsvari}, journal = {Nature Neuroscience}, number = {5}, pages = {587 -- 594}, publisher = {Nature Publishing Group}, title = {{Theta phase-specific codes for two-dimensional position, trajectory and heading in the hippocampus}}, doi = {10.1038/nn.2106}, volume = {11}, year = {2008}, }