[{"year":"2008","type":"conference","title":"On partial optimality in multi label MRFs","extern":1,"_id":"3194","author":[{"full_name":"Kohli, Pushmeet","first_name":"Pushmeet","last_name":"Kohli"},{"full_name":"Shekhovtsov, Alexander","first_name":"Alexander","last_name":"Shekhovtsov"},{"full_name":"Rother, Carsten","first_name":"Carsten","last_name":"Rother"},{"last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","full_name":"Vladimir Kolmogorov"},{"full_name":"Torr, Philip H","first_name":"Philip","last_name":"Torr"}],"publisher":"Omnipress","date_created":"2018-12-11T12:01:56Z","publication_status":"published","conference":{"name":"ICML: International Conference on Machine Learning"},"day":"01","quality_controlled":0,"citation":{"chicago":"Kohli, Pushmeet, Alexander Shekhovtsov, Carsten Rother, Vladimir Kolmogorov, and Philip Torr. “On Partial Optimality in Multi Label MRFs,” 480–87. Omnipress, 2008. <a href=\"https://doi.org/10.1145/1390156.1390217\">https://doi.org/10.1145/1390156.1390217</a>.","ieee":"P. Kohli, A. Shekhovtsov, C. Rother, V. Kolmogorov, and P. Torr, “On partial optimality in multi label MRFs,” presented at the ICML: International Conference on Machine Learning, 2008, pp. 480–487.","apa":"Kohli, P., Shekhovtsov, A., Rother, C., Kolmogorov, V., &#38; Torr, P. (2008). On partial optimality in multi label MRFs (pp. 480–487). Presented at the ICML: International Conference on Machine Learning, Omnipress. <a href=\"https://doi.org/10.1145/1390156.1390217\">https://doi.org/10.1145/1390156.1390217</a>","ama":"Kohli P, Shekhovtsov A, Rother C, Kolmogorov V, Torr P. On partial optimality in multi label MRFs. In: Omnipress; 2008:480-487. doi:<a href=\"https://doi.org/10.1145/1390156.1390217\">10.1145/1390156.1390217</a>","mla":"Kohli, Pushmeet, et al. <i>On Partial Optimality in Multi Label MRFs</i>. Omnipress, 2008, pp. 480–87, doi:<a href=\"https://doi.org/10.1145/1390156.1390217\">10.1145/1390156.1390217</a>.","short":"P. Kohli, A. Shekhovtsov, C. Rother, V. Kolmogorov, P. Torr, in:, Omnipress, 2008, pp. 480–487.","ista":"Kohli P, Shekhovtsov A, Rother C, Kolmogorov V, Torr P. 2008. On partial optimality in multi label MRFs. ICML: International Conference on Machine Learning, 480–487."},"abstract":[{"lang":"eng","text":"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."}],"doi":"10.1145/1390156.1390217","status":"public","date_updated":"2021-01-12T07:41:42Z","publist_id":"3486","month":"01","page":"480 - 487","main_file_link":[{"open_access":"0","url":"http://research.microsoft.com/pubs/77356/icml08-partoptmrf.pdf"}],"date_published":"2008-01-01T00:00:00Z"},{"publist_id":"3487","date_updated":"2021-01-12T07:41:43Z","month":"08","main_file_link":[{"open_access":"0","url":"http://research.microsoft.com/pubs/80485/CVPR08-ConnectedGC.pdf"}],"date_published":"2008-08-05T00:00:00Z","date_created":"2018-12-11T12:01:57Z","_id":"3195","publisher":"IEEE","publication_status":"published","author":[{"last_name":"Vicente","first_name":"Sara","full_name":"Vicente, Sara"},{"first_name":"Vladimir","full_name":"Vladimir Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov"},{"first_name":"Carsten","full_name":"Rother, Carsten","last_name":"Rother"}],"extern":1,"quality_controlled":0,"day":"05","conference":{"name":"CVPR: Computer Vision and Pattern Recognition"},"citation":{"ieee":"S. Vicente, V. Kolmogorov, and C. Rother, “Graph cut based image segmentation with connectivity priors,” presented at the CVPR: Computer Vision and Pattern Recognition, 2008.","apa":"Vicente, S., Kolmogorov, V., &#38; Rother, C. (2008). Graph cut based image segmentation with connectivity priors. Presented at the CVPR: Computer Vision and Pattern Recognition, IEEE. <a href=\"https://doi.org/10.1109/CVPR.2008.4587440\">https://doi.org/10.1109/CVPR.2008.4587440</a>","chicago":"Vicente, Sara, Vladimir Kolmogorov, and Carsten Rother. “Graph Cut Based Image Segmentation with Connectivity Priors.” IEEE, 2008. <a href=\"https://doi.org/10.1109/CVPR.2008.4587440\">https://doi.org/10.1109/CVPR.2008.4587440</a>.","short":"S. Vicente, V. Kolmogorov, C. Rother, in:, IEEE, 2008.","ista":"Vicente S, Kolmogorov V, Rother C. 2008. Graph cut based image segmentation with connectivity priors. CVPR: Computer Vision and Pattern Recognition.","ama":"Vicente S, Kolmogorov V, Rother C. Graph cut based image segmentation with connectivity priors. In: IEEE; 2008. doi:<a href=\"https://doi.org/10.1109/CVPR.2008.4587440\">10.1109/CVPR.2008.4587440</a>","mla":"Vicente, Sara, et al. <i>Graph Cut Based Image Segmentation with Connectivity Priors</i>. IEEE, 2008, doi:<a href=\"https://doi.org/10.1109/CVPR.2008.4587440\">10.1109/CVPR.2008.4587440</a>."},"status":"public","doi":"10.1109/CVPR.2008.4587440","abstract":[{"text":"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.","lang":"eng"}],"year":"2008","type":"conference","title":"Graph cut based image segmentation with connectivity priors"},{"date_published":"2008-06-01T00:00:00Z","page":"1068 - 1080","intvolume":"        30","month":"06","date_updated":"2021-01-12T07:41:43Z","publist_id":"3488","volume":30,"abstract":[{"text":"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/.","lang":"eng"}],"doi":"10.1109/TPAMI.2007.70844","status":"public","citation":{"ista":"Szeliski R, Zabih R, Scharstein D, Veksler O, Kolmogorov V, Agarwala A, Tappen M, Rother C. 2008. A comparative study of energy minimization methods for Markov random fields with smoothness-based priors. IEEE Transactions on Pattern Analysis and Machine Intelligence. 30(6), 1068–1080.","short":"R. Szeliski, R. Zabih, D. Scharstein, O. Veksler, V. Kolmogorov, A. Agarwala, M. Tappen, C. Rother, IEEE Transactions on Pattern Analysis and Machine Intelligence 30 (2008) 1068–1080.","ama":"Szeliski R, Zabih R, Scharstein D, et al. A comparative study of energy minimization methods for Markov random fields with smoothness-based priors. <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>. 2008;30(6):1068-1080. doi:<a href=\"https://doi.org/10.1109/TPAMI.2007.70844\">10.1109/TPAMI.2007.70844</a>","mla":"Szeliski, Richard, et al. “A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors.” <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>, vol. 30, no. 6, IEEE, 2008, pp. 1068–80, doi:<a href=\"https://doi.org/10.1109/TPAMI.2007.70844\">10.1109/TPAMI.2007.70844</a>.","ieee":"R. Szeliski <i>et al.</i>, “A comparative study of energy minimization methods for Markov random fields with smoothness-based priors,” <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>, vol. 30, no. 6. IEEE, pp. 1068–1080, 2008.","apa":"Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., … Rother, C. (2008). A comparative study of energy minimization methods for Markov random fields with smoothness-based priors. <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>. IEEE. <a href=\"https://doi.org/10.1109/TPAMI.2007.70844\">https://doi.org/10.1109/TPAMI.2007.70844</a>","chicago":"Szeliski, Richard, Ramin Zabih, Daniel Scharstein, Olga Veksler, Vladimir Kolmogorov, Aseem Agarwala, Marshall Tappen, and Carsten Rother. “A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors.” <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>. IEEE, 2008. <a href=\"https://doi.org/10.1109/TPAMI.2007.70844\">https://doi.org/10.1109/TPAMI.2007.70844</a>."},"day":"01","quality_controlled":0,"extern":1,"_id":"3196","publisher":"IEEE","date_created":"2018-12-11T12:01:57Z","publication_status":"published","author":[{"first_name":"Richard","full_name":"Szeliski, Richard S","last_name":"Szeliski"},{"first_name":"Ramin","full_name":"Zabih, Ramin","last_name":"Zabih"},{"last_name":"Scharstein","full_name":"Scharstein, Daniel","first_name":"Daniel"},{"full_name":"Veksler, Olga","first_name":"Olga","last_name":"Veksler"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov","full_name":"Vladimir Kolmogorov","first_name":"Vladimir"},{"last_name":"Agarwala","full_name":"Agarwala, Aseem","first_name":"Aseem"},{"first_name":"Marshall","full_name":"Tappen, Marshall F","last_name":"Tappen"},{"last_name":"Rother","first_name":"Carsten","full_name":"Rother, Carsten"}],"title":"A comparative study of energy minimization methods for Markov random fields with smoothness-based priors","publication":"IEEE Transactions on Pattern Analysis and Machine Intelligence","type":"journal_article","year":"2008","issue":"6"},{"intvolume":"      5303","month":"01","date_updated":"2021-01-12T07:41:44Z","publist_id":"3485","date_published":"2008-01-01T00:00:00Z","alternative_title":["LNCS"],"main_file_link":[{"open_access":"0","url":"http://research-srv.microsoft.com/pubs/70610/eccv08-MatchingMRF.pdf"}],"page":"596 - 609","type":"conference","year":"2008","title":"Feature correspondence via graph matching: Models and global optimization","day":"01","conference":{"name":"ECCV: European Conference on Computer Vision"},"quality_controlled":0,"extern":1,"_id":"3198","author":[{"last_name":"Torresani","first_name":"Lorenzo","full_name":"Torresani, Lorenzo"},{"full_name":"Vladimir Kolmogorov","first_name":"Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Carsten","full_name":"Rother, Carsten","last_name":"Rother"}],"publication_status":"published","date_created":"2018-12-11T12:01:58Z","publisher":"Springer","volume":5303,"abstract":[{"text":"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. ","lang":"eng"}],"doi":"10.1007/978-3-540-88688-4_44","status":"public","citation":{"ista":"Torresani L, Kolmogorov V, Rother C. 2008. Feature correspondence via graph matching: Models and global optimization. ECCV: European Conference on Computer Vision, LNCS, vol. 5303, 596–609.","short":"L. Torresani, V. Kolmogorov, C. Rother, in:, Springer, 2008, pp. 596–609.","ama":"Torresani L, Kolmogorov V, Rother C. Feature correspondence via graph matching: Models and global optimization. In: Vol 5303. Springer; 2008:596-609. doi:<a href=\"https://doi.org/10.1007/978-3-540-88688-4_44\">10.1007/978-3-540-88688-4_44</a>","mla":"Torresani, Lorenzo, et al. <i>Feature Correspondence via Graph Matching: Models and Global Optimization</i>. Vol. 5303, Springer, 2008, pp. 596–609, doi:<a href=\"https://doi.org/10.1007/978-3-540-88688-4_44\">10.1007/978-3-540-88688-4_44</a>.","ieee":"L. Torresani, V. Kolmogorov, and C. Rother, “Feature correspondence via graph matching: Models and global optimization,” presented at the ECCV: European Conference on Computer Vision, 2008, vol. 5303, pp. 596–609.","apa":"Torresani, L., Kolmogorov, V., &#38; Rother, C. (2008). Feature correspondence via graph matching: Models and global optimization (Vol. 5303, pp. 596–609). Presented at the ECCV: European Conference on Computer Vision, Springer. <a href=\"https://doi.org/10.1007/978-3-540-88688-4_44\">https://doi.org/10.1007/978-3-540-88688-4_44</a>","chicago":"Torresani, Lorenzo, Vladimir Kolmogorov, and Carsten Rother. “Feature Correspondence via Graph Matching: Models and Global Optimization,” 5303:596–609. Springer, 2008. <a href=\"https://doi.org/10.1007/978-3-540-88688-4_44\">https://doi.org/10.1007/978-3-540-88688-4_44</a>."}},{"type":"conference","year":"2008","title":"A new mode of operation for block ciphers and length preserving MACs","quality_controlled":0,"conference":{"name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques"},"day":"28","_id":"3224","author":[{"first_name":"Yevgeniy","full_name":"Dodis, Yevgeniy","last_name":"Dodis"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Krzysztof Pietrzak","orcid":"0000-0002-9139-1654"},{"last_name":"Puniya","full_name":"Puniya, Prashant","first_name":"Prashant"}],"date_created":"2018-12-11T12:02:07Z","publication_status":"published","publisher":"Springer","extern":1,"status":"public","doi":"10.1007/978-3-540-78967-3_12","abstract":[{"lang":"eng","text":"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 &quot;only&quot; unpredictable, one &quot;at least&quot; 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). "}],"volume":4965,"citation":{"ista":"Dodis Y, Pietrzak KZ, Puniya P. 2008. A new mode of operation for block ciphers and length preserving MACs. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 4965, 198–219.","short":"Y. Dodis, K.Z. Pietrzak, P. Puniya, in:, Springer, 2008, pp. 198–219.","mla":"Dodis, Yevgeniy, et al. <i>A New Mode of Operation for Block Ciphers and Length Preserving MACs</i>. Vol. 4965, Springer, 2008, pp. 198–219, doi:<a href=\"https://doi.org/10.1007/978-3-540-78967-3_12\">10.1007/978-3-540-78967-3_12</a>.","ama":"Dodis Y, Pietrzak KZ, Puniya P. A new mode of operation for block ciphers and length preserving MACs. In: Vol 4965. Springer; 2008:198-219. doi:<a href=\"https://doi.org/10.1007/978-3-540-78967-3_12\">10.1007/978-3-540-78967-3_12</a>","apa":"Dodis, Y., Pietrzak, K. Z., &#38; Puniya, P. (2008). A new mode of operation for block ciphers and length preserving MACs (Vol. 4965, pp. 198–219). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Springer. <a href=\"https://doi.org/10.1007/978-3-540-78967-3_12\">https://doi.org/10.1007/978-3-540-78967-3_12</a>","ieee":"Y. Dodis, K. Z. Pietrzak, and P. Puniya, “A new mode of operation for block ciphers and length preserving MACs,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, 2008, vol. 4965, pp. 198–219.","chicago":"Dodis, Yevgeniy, Krzysztof Z Pietrzak, and Prashant Puniya. “A New Mode of Operation for Block Ciphers and Length Preserving MACs,” 4965:198–219. Springer, 2008. <a href=\"https://doi.org/10.1007/978-3-540-78967-3_12\">https://doi.org/10.1007/978-3-540-78967-3_12</a>."},"month":"04","intvolume":"      4965","publist_id":"3456","date_updated":"2021-01-12T07:41:55Z","alternative_title":["LNCS"],"date_published":"2008-04-28T00:00:00Z","page":"198 - 219"},{"date_updated":"2025-09-29T11:09:55Z","publist_id":"3454","intvolume":"      5126","month":"08","page":"655 - 666","date_published":"2008-08-06T00:00:00Z","alternative_title":["LNCS"],"extern":1,"_id":"3225","date_created":"2018-12-11T12:02:07Z","publisher":"Springer","author":[{"last_name":"Fischlin","full_name":"Fischlin, Marc","first_name":"Marc"},{"first_name":"Anja","full_name":"Lehmann, Anja","last_name":"Lehmann"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","full_name":"Krzysztof Pietrzak","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z"}],"publication_status":"published","day":"06","conference":{"name":"ICALP: Automata, Languages and Programming"},"related_material":{"record":[{"relation":"later_version","id":"2852","status":"public"}]},"quality_controlled":0,"citation":{"apa":"Fischlin, M., Lehmann, A., &#38; Pietrzak, K. Z. (2008). Robust multi property combiners for hash functions revisited (Vol. 5126, pp. 655–666). Presented at the ICALP: Automata, Languages and Programming, Springer. <a href=\"https://doi.org/10.1007/978-3-540-70583-3_53\">https://doi.org/10.1007/978-3-540-70583-3_53</a>","ieee":"M. Fischlin, A. Lehmann, and K. Z. Pietrzak, “Robust multi property combiners for hash functions revisited,” presented at the ICALP: Automata, Languages and Programming, 2008, vol. 5126, no. PART 2, pp. 655–666.","chicago":"Fischlin, Marc, Anja Lehmann, and Krzysztof Z Pietrzak. “Robust Multi Property Combiners for Hash Functions Revisited,” 5126:655–66. Springer, 2008. <a href=\"https://doi.org/10.1007/978-3-540-70583-3_53\">https://doi.org/10.1007/978-3-540-70583-3_53</a>.","short":"M. Fischlin, A. Lehmann, K.Z. Pietrzak, in:, Springer, 2008, pp. 655–666.","ista":"Fischlin M, Lehmann A, Pietrzak KZ. 2008. Robust multi property combiners for hash functions revisited. ICALP: Automata, Languages and Programming, LNCS, vol. 5126, 655–666.","mla":"Fischlin, Marc, et al. <i>Robust Multi Property Combiners for Hash Functions Revisited</i>. Vol. 5126, no. PART 2, Springer, 2008, pp. 655–66, doi:<a href=\"https://doi.org/10.1007/978-3-540-70583-3_53\">10.1007/978-3-540-70583-3_53</a>.","ama":"Fischlin M, Lehmann A, Pietrzak KZ. Robust multi property combiners for hash functions revisited. In: Vol 5126. Springer; 2008:655-666. doi:<a href=\"https://doi.org/10.1007/978-3-540-70583-3_53\">10.1007/978-3-540-70583-3_53</a>"},"volume":5126,"abstract":[{"text":"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). ","lang":"eng"}],"status":"public","doi":"10.1007/978-3-540-70583-3_53","year":"2008","type":"conference","issue":"PART 2","title":"Robust multi property combiners for hash functions revisited"},{"date_published":"2008-08-06T00:00:00Z","acknowledgement":"This work was partially supported by the Zurich Information Security Center.","alternative_title":["LNCS"],"page":"423 - 436","intvolume":"      5126","month":"08","date_updated":"2021-01-12T07:41:56Z","publist_id":"3455","abstract":[{"lang":"eng","text":"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). "}],"volume":5126,"doi":"10.1007/978-3-540-70583-3_35","status":"public","citation":{"mla":"Pietrzak, Krzysztof Z., and Johan Sjödin. <i>Weak Pseudorandom Functions in Minicrypt</i>. Vol. 5126, no. PART 2, Springer, 2008, pp. 423–36, doi:<a href=\"https://doi.org/10.1007/978-3-540-70583-3_35\">10.1007/978-3-540-70583-3_35</a>.","ama":"Pietrzak KZ, Sjödin J. Weak pseudorandom functions in minicrypt. In: Vol 5126. Springer; 2008:423-436. doi:<a href=\"https://doi.org/10.1007/978-3-540-70583-3_35\">10.1007/978-3-540-70583-3_35</a>","short":"K.Z. Pietrzak, J. Sjödin, in:, Springer, 2008, pp. 423–436.","ista":"Pietrzak KZ, Sjödin J. 2008. Weak pseudorandom functions in minicrypt. ICALP: Automata, Languages and Programming, LNCS, vol. 5126, 423–436.","chicago":"Pietrzak, Krzysztof Z, and Johan Sjödin. “Weak Pseudorandom Functions in Minicrypt,” 5126:423–36. Springer, 2008. <a href=\"https://doi.org/10.1007/978-3-540-70583-3_35\">https://doi.org/10.1007/978-3-540-70583-3_35</a>.","apa":"Pietrzak, K. Z., &#38; Sjödin, J. (2008). Weak pseudorandom functions in minicrypt (Vol. 5126, pp. 423–436). Presented at the ICALP: Automata, Languages and Programming, Springer. <a href=\"https://doi.org/10.1007/978-3-540-70583-3_35\">https://doi.org/10.1007/978-3-540-70583-3_35</a>","ieee":"K. Z. Pietrzak and J. Sjödin, “Weak pseudorandom functions in minicrypt,” presented at the ICALP: Automata, Languages and Programming, 2008, vol. 5126, no. PART 2, pp. 423–436."},"day":"06","conference":{"name":"ICALP: Automata, Languages and Programming"},"quality_controlled":0,"extern":1,"_id":"3226","publisher":"Springer","date_created":"2018-12-11T12:02:07Z","publication_status":"published","author":[{"first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","full_name":"Krzysztof Pietrzak","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Sjödin","full_name":"Sjödin,  Johan","first_name":"Johan"}],"title":"Weak pseudorandom functions in minicrypt","type":"conference","year":"2008","issue":"PART 2"},{"page":"239 - 242","main_file_link":[{"url":"http://pe.org.pl/abstract_pl.php?nid=1917","open_access":"0"}],"date_published":"2008-10-01T00:00:00Z","publist_id":"3452","date_updated":"2021-01-12T07:41:56Z","month":"10","intvolume":"        84","citation":{"ieee":"P. Zubielik, J. Nadaczny, K. Z. Pietrzak, and M. Lawenda, “Elektrowiz – system of measurement data management,” <i>Przeglad Elektrotechniczny</i>, vol. 84, no. 10. SIGMA-NOT, pp. 239–242, 2008.","apa":"Zubielik, P., Nadaczny, J., Pietrzak, K. Z., &#38; Lawenda, M. (2008). Elektrowiz – system of measurement data management. <i>Przeglad Elektrotechniczny</i>. SIGMA-NOT.","chicago":"Zubielik, Piotr, Jerzy Nadaczny, Krzysztof Z Pietrzak, and Marcin Lawenda. “Elektrowiz – System of Measurement Data Management.” <i>Przeglad Elektrotechniczny</i>. SIGMA-NOT, 2008.","ista":"Zubielik P, Nadaczny J, Pietrzak KZ, Lawenda M. 2008. Elektrowiz – system of measurement data management. Przeglad Elektrotechniczny. 84(10), 239–242.","short":"P. Zubielik, J. Nadaczny, K.Z. Pietrzak, M. Lawenda, Przeglad Elektrotechniczny 84 (2008) 239–242.","ama":"Zubielik P, Nadaczny J, Pietrzak KZ, Lawenda M. Elektrowiz – system of measurement data management. <i>Przeglad Elektrotechniczny</i>. 2008;84(10):239-242.","mla":"Zubielik, Piotr, et al. “Elektrowiz – System of Measurement Data Management.” <i>Przeglad Elektrotechniczny</i>, vol. 84, no. 10, SIGMA-NOT, 2008, pp. 239–42."},"status":"public","abstract":[{"lang":"eng","text":"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."}],"volume":84,"author":[{"full_name":"Zubielik, Piotr","first_name":"Piotr","last_name":"Zubielik"},{"last_name":"Nadaczny","first_name":"Jerzy","full_name":"Nadaczny, Jerzy"},{"last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Krzysztof Pietrzak","first_name":"Krzysztof Z"},{"last_name":"Lawenda","full_name":"Lawenda, Marcin","first_name":"Marcin"}],"_id":"3227","date_created":"2018-12-11T12:02:08Z","publisher":"SIGMA-NOT","publication_status":"published","extern":1,"quality_controlled":0,"day":"01","publication":"Przeglad Elektrotechniczny","title":"Elektrowiz – system of measurement data management","type":"journal_article","issue":"10","year":"2008"},{"year":"2008","type":"conference","title":"Compression from collisions or why CRHF combiners have a long output","extern":1,"_id":"3228","author":[{"first_name":"Krzysztof Z","full_name":"Krzysztof Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak"}],"publication_status":"published","publisher":"Springer","date_created":"2018-12-11T12:02:08Z","day":"11","conference":{"name":"CRYPTO: International Cryptology Conference"},"quality_controlled":0,"citation":{"apa":"Pietrzak, K. Z. (2008). Compression from collisions or why CRHF combiners have a long output (Vol. 5157, pp. 413–432). Presented at the CRYPTO: International Cryptology Conference, Springer. <a href=\"https://doi.org/10.1007/978-3-540-85174-5_23\">https://doi.org/10.1007/978-3-540-85174-5_23</a>","ieee":"K. Z. Pietrzak, “Compression from collisions or why CRHF combiners have a long output,” presented at the CRYPTO: International Cryptology Conference, 2008, vol. 5157, pp. 413–432.","chicago":"Pietrzak, Krzysztof Z. “Compression from Collisions or Why CRHF Combiners Have a Long Output,” 5157:413–32. Springer, 2008. <a href=\"https://doi.org/10.1007/978-3-540-85174-5_23\">https://doi.org/10.1007/978-3-540-85174-5_23</a>.","short":"K.Z. Pietrzak, in:, Springer, 2008, pp. 413–432.","ista":"Pietrzak KZ. 2008. Compression from collisions or why CRHF combiners have a long output. CRYPTO: International Cryptology Conference, LNCS, vol. 5157, 413–432.","mla":"Pietrzak, Krzysztof Z. <i>Compression from Collisions or Why CRHF Combiners Have a Long Output</i>. Vol. 5157, Springer, 2008, pp. 413–32, doi:<a href=\"https://doi.org/10.1007/978-3-540-85174-5_23\">10.1007/978-3-540-85174-5_23</a>.","ama":"Pietrzak KZ. Compression from collisions or why CRHF combiners have a long output. In: Vol 5157. Springer; 2008:413-432. doi:<a href=\"https://doi.org/10.1007/978-3-540-85174-5_23\">10.1007/978-3-540-85174-5_23</a>"},"abstract":[{"text":"\nA 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 &quot;reconstruction lemma&quot; 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.","lang":"eng"}],"volume":5157,"doi":"10.1007/978-3-540-85174-5_23","status":"public","date_updated":"2021-01-12T07:41:57Z","publist_id":"3453","intvolume":"      5157","month":"09","page":"413 - 432","date_published":"2008-09-11T00:00:00Z","alternative_title":["LNCS"]},{"citation":{"ieee":"S. Dziembowski and K. Z. Pietrzak, “Leakage resilient cryptography,” presented at the FOCS: Foundations of Computer Science, 2008, pp. 293–302.","apa":"Dziembowski, S., &#38; Pietrzak, K. Z. (2008). Leakage resilient cryptography (pp. 293–302). Presented at the FOCS: Foundations of Computer Science, IEEE. <a href=\"https://doi.org/10.1109/FOCS.2008.56\">https://doi.org/10.1109/FOCS.2008.56</a>","chicago":"Dziembowski, Stefan, and Krzysztof Z Pietrzak. “Leakage Resilient Cryptography,” 293–302. IEEE, 2008. <a href=\"https://doi.org/10.1109/FOCS.2008.56\">https://doi.org/10.1109/FOCS.2008.56</a>.","short":"S. Dziembowski, K.Z. Pietrzak, in:, IEEE, 2008, pp. 293–302.","ista":"Dziembowski S, Pietrzak KZ. 2008. Leakage resilient cryptography. FOCS: Foundations of Computer Science, 293–302.","ama":"Dziembowski S, Pietrzak KZ. Leakage resilient cryptography. In: IEEE; 2008:293-302. doi:<a href=\"https://doi.org/10.1109/FOCS.2008.56\">10.1109/FOCS.2008.56</a>","mla":"Dziembowski, Stefan, and Krzysztof Z. Pietrzak. <i>Leakage Resilient Cryptography</i>. IEEE, 2008, pp. 293–302, doi:<a href=\"https://doi.org/10.1109/FOCS.2008.56\">10.1109/FOCS.2008.56</a>."},"abstract":[{"lang":"eng","text":"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."}],"doi":"10.1109/FOCS.2008.56","status":"public","extern":1,"author":[{"last_name":"Dziembowski","full_name":"Dziembowski, Stefan","first_name":"Stefan"},{"last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","full_name":"Krzysztof Pietrzak"}],"_id":"3229","date_created":"2018-12-11T12:02:08Z","publication_status":"published","publisher":"IEEE","day":"28","conference":{"name":"FOCS: Foundations of Computer Science"},"quality_controlled":0,"title":"Leakage resilient cryptography","year":"2008","type":"conference","page":"293 - 302","date_published":"2008-10-28T00:00:00Z","date_updated":"2021-01-12T07:41:57Z","publist_id":"3451","month":"10"},{"day":"13","quality_controlled":0,"extern":1,"_id":"3291","publisher":"American Society for Microbiology","publication_status":"published","date_created":"2018-12-11T12:02:29Z","author":[{"first_name":"Philipp S","full_name":"Philipp Schmalhorst","orcid":"0000-0002-5795-0133","id":"309D50DA-F248-11E8-B48F-1D18A9856A87","last_name":"Schmalhorst"},{"last_name":"Krappmann","full_name":"Krappmann, Sven","first_name":"Sven"},{"full_name":"Vervecken, Wouter","first_name":"Wouter","last_name":"Vervecken"},{"last_name":"Rohde","first_name":"Manfred","full_name":"Rohde, Manfred"},{"first_name":"Meike","full_name":"Müller, Meike","last_name":"Müller"},{"last_name":"Braus","full_name":"Braus, Gerhard H.","first_name":"Gerhard"},{"last_name":"Contreras","first_name":"Roland","full_name":"Contreras, Roland"},{"first_name":"Armin","full_name":"Braun, Armin","last_name":"Braun"},{"full_name":"Bakker, Hans","first_name":"Hans","last_name":"Bakker"},{"full_name":"Routier, Françoise H","first_name":"Françoise","last_name":"Routier"}],"abstract":[{"text":"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. ","lang":"eng"}],"volume":7,"doi":"10.1128/EC.00065-08","status":"public","citation":{"mla":"Schmalhorst, Philipp S., et al. “Contribution of Galactofuranose to the Virulence of the Opportunistic Pathogen Aspergillus Fumigatus.” <i>Eukaryotic Cell</i>, vol. 7, no. 8, American Society for Microbiology, 2008, pp. 1268–77, doi:<a href=\"https://doi.org/10.1128/EC.00065-08\">10.1128/EC.00065-08</a>.","ama":"Schmalhorst PS, Krappmann S, Vervecken W, et al. Contribution of galactofuranose to the virulence of the opportunistic pathogen Aspergillus fumigatus. <i>Eukaryotic Cell</i>. 2008;7(8):1268-1277. doi:<a href=\"https://doi.org/10.1128/EC.00065-08\">10.1128/EC.00065-08</a>","short":"P.S. Schmalhorst, S. Krappmann, W. Vervecken, M. Rohde, M. Müller, G. Braus, R. Contreras, A. Braun, H. Bakker, F. Routier, Eukaryotic Cell 7 (2008) 1268–1277.","ista":"Schmalhorst PS, Krappmann S, Vervecken W, Rohde M, Müller M, Braus G, Contreras R, Braun A, Bakker H, Routier F. 2008. Contribution of galactofuranose to the virulence of the opportunistic pathogen Aspergillus fumigatus. Eukaryotic Cell. 7(8), 1268–1277.","chicago":"Schmalhorst, Philipp S, Sven Krappmann, Wouter Vervecken, Manfred Rohde, Meike Müller, Gerhard Braus, Roland Contreras, Armin Braun, Hans Bakker, and Françoise Routier. “Contribution of Galactofuranose to the Virulence of the Opportunistic Pathogen Aspergillus Fumigatus.” <i>Eukaryotic Cell</i>. American Society for Microbiology, 2008. <a href=\"https://doi.org/10.1128/EC.00065-08\">https://doi.org/10.1128/EC.00065-08</a>.","apa":"Schmalhorst, P. S., Krappmann, S., Vervecken, W., Rohde, M., Müller, M., Braus, G., … Routier, F. (2008). Contribution of galactofuranose to the virulence of the opportunistic pathogen Aspergillus fumigatus. <i>Eukaryotic Cell</i>. American Society for Microbiology. <a href=\"https://doi.org/10.1128/EC.00065-08\">https://doi.org/10.1128/EC.00065-08</a>","ieee":"P. S. Schmalhorst <i>et al.</i>, “Contribution of galactofuranose to the virulence of the opportunistic pathogen Aspergillus fumigatus,” <i>Eukaryotic Cell</i>, vol. 7, no. 8. American Society for Microbiology, pp. 1268–1277, 2008."},"year":"2008","issue":"8","type":"journal_article","title":"Contribution of galactofuranose to the virulence of the opportunistic pathogen Aspergillus fumigatus","publication":"Eukaryotic Cell","intvolume":"         7","month":"06","date_updated":"2021-01-12T07:42:26Z","publist_id":"3354","date_published":"2008-06-13T00:00:00Z","page":"1268 - 1277"},{"month":"08","intvolume":"       134","publist_id":"3333","date_updated":"2021-01-12T07:42:32Z","date_published":"2008-08-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2602844/"}],"page":"416 - 426","oa":1,"quality_controlled":0,"day":"01","publisher":"Cell Press","_id":"3307","date_created":"2018-12-11T12:02:35Z","publication_status":"published","author":[{"last_name":"Green","full_name":"Green, Richard E","first_name":"Richard"},{"full_name":"Malaspinas, Anna-Sapfo ","first_name":"Anna","last_name":"Malaspinas"},{"full_name":"Krause, Johannes","first_name":"Johannes","last_name":"Krause"},{"first_name":"Adrian","full_name":"Briggs, Adrian W","last_name":"Briggs"},{"last_name":"Johnson","full_name":"Johnson, Philip L","first_name":"Philip"},{"id":"49ADD78E-F248-11E8-B48F-1D18A9856A87","last_name":"Uhler","full_name":"Caroline Uhler","orcid":"0000-0002-7008-0216","first_name":"Caroline"},{"last_name":"Meyer","full_name":"Meyer, Matthias","first_name":"Matthias"},{"full_name":"Good, Jeffrey M","first_name":"Jeffrey","last_name":"Good"},{"last_name":"Maricic","first_name":"Tomislav","full_name":"Maricic, Tomislav"},{"full_name":"Stenzel, Udo","first_name":"Udo","last_name":"Stenzel"},{"last_name":"Prüfer","first_name":"Kay","full_name":"Prüfer, Kay"},{"first_name":"Michael","full_name":"Siebauer, Michael F","last_name":"Siebauer"},{"full_name":"Burbano, Hernän A","first_name":"Hernän","last_name":"Burbano"},{"first_name":"Michael","full_name":"Ronan, Michael T","last_name":"Ronan"},{"last_name":"Rothberg","full_name":"Rothberg, Jonathan M","first_name":"Jonathan"},{"full_name":"Egholm, Michael","first_name":"Michael","last_name":"Egholm"},{"first_name":"Pavao","full_name":"Rudan, Pavao","last_name":"Rudan"},{"full_name":"Brajković, Dejana","first_name":"Dejana","last_name":"Brajković"},{"full_name":"Kućan, Željko","first_name":"Željko","last_name":"Kućan"},{"last_name":"Gušić","first_name":"Ivan","full_name":"Gušić, Ivan"},{"full_name":"Wikström, Mårten K","first_name":"Mårten","last_name":"Wikström"},{"last_name":"Laakkonen","first_name":"Liisa","full_name":"Laakkonen, Liisa J"},{"full_name":"Kelso, Janet F","first_name":"Janet","last_name":"Kelso"},{"last_name":"Slatkin","first_name":"Montgomery","full_name":"Slatkin, Montgomery"},{"last_name":"Pääbo","first_name":"Svante","full_name":"Pääbo, Svante H"}],"extern":1,"status":"public","doi":"10.1016/j.cell.2008.06.021","abstract":[{"text":"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.","lang":"eng"}],"volume":134,"citation":{"chicago":"Green, Richard, Anna Malaspinas, Johannes Krause, Adrian Briggs, Philip Johnson, Caroline Uhler, Matthias Meyer, et al. “A Complete Neandertal Mitochondrial Genome Sequence Determined by Highhhroughput Sequencing.” <i>Cell</i>. Cell Press, 2008. <a href=\"https://doi.org/10.1016/j.cell.2008.06.021\">https://doi.org/10.1016/j.cell.2008.06.021</a>.","ieee":"R. Green <i>et al.</i>, “A complete neandertal mitochondrial genome sequence determined by highhhroughput sequencing,” <i>Cell</i>, vol. 134. Cell Press, pp. 416–426, 2008.","apa":"Green, R., Malaspinas, A., Krause, J., Briggs, A., Johnson, P., Uhler, C., … Pääbo, S. (2008). A complete neandertal mitochondrial genome sequence determined by highhhroughput sequencing. <i>Cell</i>. Cell Press. <a href=\"https://doi.org/10.1016/j.cell.2008.06.021\">https://doi.org/10.1016/j.cell.2008.06.021</a>","ama":"Green R, Malaspinas A, Krause J, et al. A complete neandertal mitochondrial genome sequence determined by highhhroughput sequencing. <i>Cell</i>. 2008;134:416-426. doi:<a href=\"https://doi.org/10.1016/j.cell.2008.06.021\">10.1016/j.cell.2008.06.021</a>","mla":"Green, Richard, et al. “A Complete Neandertal Mitochondrial Genome Sequence Determined by Highhhroughput Sequencing.” <i>Cell</i>, vol. 134, Cell Press, 2008, pp. 416–26, doi:<a href=\"https://doi.org/10.1016/j.cell.2008.06.021\">10.1016/j.cell.2008.06.021</a>.","ista":"Green R, Malaspinas A, Krause J, Briggs A, Johnson P, Uhler C, Meyer M, Good J, Maricic T, Stenzel U, Prüfer K, Siebauer M, Burbano H, Ronan M, Rothberg J, Egholm M, Rudan P, Brajković D, Kućan Ž, Gušić I, Wikström M, Laakkonen L, Kelso J, Slatkin M, Pääbo S. 2008. A complete neandertal mitochondrial genome sequence determined by highhhroughput sequencing. Cell. 134, 416–426.","short":"R. Green, A. Malaspinas, J. Krause, A. Briggs, P. Johnson, C. Uhler, M. Meyer, J. Good, T. Maricic, U. Stenzel, K. Prüfer, M. Siebauer, H. Burbano, M. Ronan, J. Rothberg, M. Egholm, P. Rudan, D. Brajković, Ž. Kućan, I. Gušić, M. Wikström, L. Laakkonen, J. Kelso, M. Slatkin, S. Pääbo, Cell 134 (2008) 416–426."},"type":"journal_article","year":"2008","publication":"Cell","title":"A complete neandertal mitochondrial genome sequence determined by highhhroughput sequencing"},{"day":"12","quality_controlled":0,"extern":1,"publication_status":"published","_id":"3409","publisher":"IOP Publishing Ltd.","date_created":"2018-12-11T12:03:11Z","author":[{"last_name":"Struckmeier","full_name":"Struckmeier, Jens","first_name":"Jens"},{"last_name":"Wahl","first_name":"Reiner","full_name":"Wahl, Reiner"},{"first_name":"Mirko","full_name":"Leuschner, Mirko","last_name":"Leuschner"},{"full_name":"Nunes, Joao","first_name":"Joao","last_name":"Nunes"},{"first_name":"Harald L","orcid":"0000-0002-8023-9315","full_name":"Harald Janovjak","last_name":"Janovjak","id":"33BA6C30-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Geisler","first_name":"Ulrich","full_name":"Geisler, Ulrich"},{"full_name":"Hofmann, Gerd","first_name":"Gerd","last_name":"Hofmann"},{"full_name":"Jähnke, Torsten","first_name":"Torsten","last_name":"Jähnke"},{"last_name":"Mueller","full_name":"Mueller, Daniel J","first_name":"Daniel"}],"volume":19,"abstract":[{"lang":"eng","text":"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."}],"status":"public","doi":"10.1088/0957-4484/19/38/384020","citation":{"apa":"Struckmeier, J., Wahl, R., Leuschner, M., Nunes, J., Janovjak, H. L., Geisler, U., … Mueller, D. (2008). Fully automated single-molecule force spectroscopy for screening applications. <i>Nanotechnology</i>. IOP Publishing Ltd. <a href=\"https://doi.org/10.1088/0957-4484/19/38/384020\">https://doi.org/10.1088/0957-4484/19/38/384020</a>","ieee":"J. Struckmeier <i>et al.</i>, “Fully automated single-molecule force spectroscopy for screening applications,” <i>Nanotechnology</i>, vol. 19, no. 38. IOP Publishing Ltd., 2008.","chicago":"Struckmeier, Jens, Reiner Wahl, Mirko Leuschner, Joao Nunes, Harald L Janovjak, Ulrich Geisler, Gerd Hofmann, Torsten Jähnke, and Daniel Mueller. “Fully Automated Single-Molecule Force Spectroscopy for Screening Applications.” <i>Nanotechnology</i>. IOP Publishing Ltd., 2008. <a href=\"https://doi.org/10.1088/0957-4484/19/38/384020\">https://doi.org/10.1088/0957-4484/19/38/384020</a>.","short":"J. Struckmeier, R. Wahl, M. Leuschner, J. Nunes, H.L. Janovjak, U. Geisler, G. Hofmann, T. Jähnke, D. Mueller, Nanotechnology 19 (2008).","ista":"Struckmeier J, Wahl R, Leuschner M, Nunes J, Janovjak HL, Geisler U, Hofmann G, Jähnke T, Mueller D. 2008. Fully automated single-molecule force spectroscopy for screening applications. Nanotechnology. 19(38).","mla":"Struckmeier, Jens, et al. “Fully Automated Single-Molecule Force Spectroscopy for Screening Applications.” <i>Nanotechnology</i>, vol. 19, no. 38, IOP Publishing Ltd., 2008, doi:<a href=\"https://doi.org/10.1088/0957-4484/19/38/384020\">10.1088/0957-4484/19/38/384020</a>.","ama":"Struckmeier J, Wahl R, Leuschner M, et al. Fully automated single-molecule force spectroscopy for screening applications. <i>Nanotechnology</i>. 2008;19(38). doi:<a href=\"https://doi.org/10.1088/0957-4484/19/38/384020\">10.1088/0957-4484/19/38/384020</a>"},"type":"journal_article","issue":"38","year":"2008","title":"Fully automated single-molecule force spectroscopy for screening applications","publication":"Nanotechnology","intvolume":"        19","month":"08","date_updated":"2021-01-12T07:43:17Z","publist_id":"2993","date_published":"2008-08-12T00:00:00Z"},{"type":"review","year":"2008","issue":"7","title":"From valleys to ridges: Exploring the energy landscape of single membrane proteins","publication":"ChemPhysChem","day":"02","quality_controlled":0,"extern":1,"publisher":"Wiley-Blackwell","_id":"3410","publication_status":"published","date_created":"2018-12-11T12:03:11Z","author":[{"first_name":"Harald L","orcid":"0000-0002-8023-9315","full_name":"Harald Janovjak","last_name":"Janovjak","id":"33BA6C30-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Sapra, Tanuj K","first_name":"Tanuj","last_name":"Sapra"},{"full_name":"Kedrov, Alexej","first_name":"Alexej","last_name":"Kedrov"},{"first_name":"Daniel","full_name":"Mueller, Daniel J","last_name":"Mueller"}],"abstract":[{"text":"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.","lang":"eng"}],"volume":9,"doi":"10.1002/cphc.200700662","status":"public","citation":{"ieee":"H. L. Janovjak, T. Sapra, A. Kedrov, and D. Mueller, “From valleys to ridges: Exploring the energy landscape of single membrane proteins,” <i>ChemPhysChem</i>, vol. 9, no. 7. Wiley-Blackwell, pp. 954–966, 2008.","apa":"Janovjak, H. L., Sapra, T., Kedrov, A., &#38; Mueller, D. (2008). From valleys to ridges: Exploring the energy landscape of single membrane proteins. <i>ChemPhysChem</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1002/cphc.200700662\">https://doi.org/10.1002/cphc.200700662</a>","chicago":"Janovjak, Harald L, Tanuj Sapra, Alexej Kedrov, and Daniel Mueller. “From Valleys to Ridges: Exploring the Energy Landscape of Single Membrane Proteins.” <i>ChemPhysChem</i>. Wiley-Blackwell, 2008. <a href=\"https://doi.org/10.1002/cphc.200700662\">https://doi.org/10.1002/cphc.200700662</a>.","ista":"Janovjak HL, Sapra T, Kedrov A, Mueller D. 2008. From valleys to ridges: Exploring the energy landscape of single membrane proteins. ChemPhysChem. 9(7), 954–966.","short":"H.L. Janovjak, T. Sapra, A. Kedrov, D. Mueller, ChemPhysChem 9 (2008) 954–966.","ama":"Janovjak HL, Sapra T, Kedrov A, Mueller D. From valleys to ridges: Exploring the energy landscape of single membrane proteins. <i>ChemPhysChem</i>. 2008;9(7):954-966. doi:<a href=\"https://doi.org/10.1002/cphc.200700662\">10.1002/cphc.200700662</a>","mla":"Janovjak, Harald L., et al. “From Valleys to Ridges: Exploring the Energy Landscape of Single Membrane Proteins.” <i>ChemPhysChem</i>, vol. 9, no. 7, Wiley-Blackwell, 2008, pp. 954–66, doi:<a href=\"https://doi.org/10.1002/cphc.200700662\">10.1002/cphc.200700662</a>."},"intvolume":"         9","month":"05","date_updated":"2019-04-26T07:22:27Z","publist_id":"2992","date_published":"2008-05-02T00:00:00Z","page":"954 - 966"},{"citation":{"chicago":"Bollback, Jonathan P, Thomas York, and Rasmus Nielsen. “Estimation of 2Nes From Temporal Allele Frequency Data.” <i>Genetics</i>. Genetics Society of America, 2008. <a href=\"https://doi.org/10.1534/genetics.107.085019\">https://doi.org/10.1534/genetics.107.085019</a>.","ieee":"J. P. Bollback, T. York, and R. Nielsen, “Estimation of 2Nes From Temporal Allele Frequency Data,” <i>Genetics</i>, vol. 179, no. 1. Genetics Society of America, pp. 497–502, 2008.","apa":"Bollback, J. P., York, T., &#38; Nielsen, R. (2008). Estimation of 2Nes From Temporal Allele Frequency Data. <i>Genetics</i>. Genetics Society of America. <a href=\"https://doi.org/10.1534/genetics.107.085019\">https://doi.org/10.1534/genetics.107.085019</a>","ama":"Bollback JP, York T, Nielsen R. Estimation of 2Nes From Temporal Allele Frequency Data. <i>Genetics</i>. 2008;179(1):497-502. doi:<a href=\"https://doi.org/10.1534/genetics.107.085019\">10.1534/genetics.107.085019</a>","mla":"Bollback, Jonathan P., et al. “Estimation of 2Nes From Temporal Allele Frequency Data.” <i>Genetics</i>, vol. 179, no. 1, Genetics Society of America, 2008, pp. 497–502, doi:<a href=\"https://doi.org/10.1534/genetics.107.085019\">10.1534/genetics.107.085019</a>.","short":"J.P. Bollback, T. York, R. Nielsen, Genetics 179 (2008) 497–502.","ista":"Bollback JP, York T, Nielsen R. 2008. Estimation of 2Nes From Temporal Allele Frequency Data. Genetics. 179(1), 497–502."},"volume":179,"abstract":[{"lang":"eng","text":"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."}],"doi":"10.1534/genetics.107.085019","status":"public","extern":1,"_id":"3435","publication_status":"published","date_created":"2018-12-11T12:03:19Z","author":[{"id":"2C6FA9CC-F248-11E8-B48F-1D18A9856A87","last_name":"Bollback","first_name":"Jonathan P","full_name":"Jonathan Bollback","orcid":"0000-0002-4624-4612"},{"last_name":"York","full_name":"York, Thomas L","first_name":"Thomas"},{"first_name":"Rasmus","full_name":"Nielsen, Rasmus","last_name":"Nielsen"}],"publisher":"Genetics Society of America","day":"01","quality_controlled":0,"title":"Estimation of 2Nes From Temporal Allele Frequency Data","publication":"Genetics","issue":"1","year":"2008","type":"journal_article","page":"497 - 502","main_file_link":[{"open_access":"1","url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2390626"}],"date_published":"2008-05-01T00:00:00Z","date_updated":"2021-01-12T07:43:27Z","publist_id":"2965","intvolume":"       179","month":"05","oa":1},{"title":"Assigning trust to Wikipedia content","year":"2008","type":"conference","citation":{"ama":"Adler BT, Chatterjee K, De Alfaro L, Faella M, Pye I, Raman V. Assigning trust to Wikipedia content. In: ACM; 2008. doi:<a href=\"https://doi.org/10.1145/1822258.1822293\">10.1145/1822258.1822293</a>","mla":"Adler, B. Thomas, et al. <i>Assigning Trust to Wikipedia Content</i>. ACM, 2008, doi:<a href=\"https://doi.org/10.1145/1822258.1822293\">10.1145/1822258.1822293</a>.","short":"B.T. Adler, K. Chatterjee, L. De Alfaro, M. Faella, I. Pye, V. Raman, in:, ACM, 2008.","ista":"Adler BT, Chatterjee K, De Alfaro L, Faella M, Pye I, Raman V. 2008. Assigning trust to Wikipedia content. WikiSym: International Symposium on Wikis.","chicago":"Adler, B Thomas, Krishnendu Chatterjee, Luca De Alfaro, Marco Faella, Ian Pye, and Vishwanath Raman. “Assigning Trust to Wikipedia Content.” ACM, 2008. <a href=\"https://doi.org/10.1145/1822258.1822293\">https://doi.org/10.1145/1822258.1822293</a>.","ieee":"B. T. Adler, K. Chatterjee, L. De Alfaro, M. Faella, I. Pye, and V. Raman, “Assigning trust to Wikipedia content,” presented at the WikiSym: International Symposium on Wikis, 2008.","apa":"Adler, B. T., Chatterjee, K., De Alfaro, L., Faella, M., Pye, I., &#38; Raman, V. (2008). Assigning trust to Wikipedia content. Presented at the WikiSym: International Symposium on Wikis, ACM. <a href=\"https://doi.org/10.1145/1822258.1822293\">https://doi.org/10.1145/1822258.1822293</a>"},"status":"public","doi":"10.1145/1822258.1822293","abstract":[{"text":"The Wikipedia is a collaborative encyclopedia: anyone can contribute to its articles simply by clicking on an &quot;edit&quot; 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.\n\nThe 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.\n\nWe 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.","lang":"eng"}],"_id":"3501","author":[{"first_name":"B Thomas","full_name":"Adler, B Thomas","last_name":"Adler"},{"full_name":"Krishnendu Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"full_name":"de Alfaro, Luca","first_name":"Luca","last_name":"De Alfaro"},{"full_name":"Faella, Marco","first_name":"Marco","last_name":"Faella"},{"full_name":"Pye, Ian","first_name":"Ian","last_name":"Pye"},{"first_name":"Vishwanath","full_name":"Raman, Vishwanath","last_name":"Raman"}],"publication_status":"published","date_created":"2018-12-11T12:03:40Z","publisher":"ACM","extern":1,"quality_controlled":0,"day":"10","conference":{"name":"WikiSym: International Symposium on Wikis"},"acknowledgement":"This research has been partially supported by the CITRIS: Center for Information Technology Research in the Interest of Society.","date_published":"2008-09-10T00:00:00Z","publist_id":"2886","date_updated":"2021-01-12T07:43:53Z","month":"09"},{"page":"33 - 42","acknowledgement":"This research has been partially supported by the CITRIS: Center for Information Technology Research in the Interest of Society.","date_published":"2008-10-31T00:00:00Z","date_updated":"2021-01-12T07:43:54Z","publist_id":"2885","month":"10","title":"Robust content-driven reputation","type":"conference","year":"2008","citation":{"ista":"Chatterjee K, De Alfaro L, Pye I. 2008. Robust content-driven reputation. AISec: Artificial Intelligence and Security, 33–42.","short":"K. Chatterjee, L. De Alfaro, I. Pye, in:, ACM, 2008, pp. 33–42.","mla":"Chatterjee, Krishnendu, et al. <i>Robust Content-Driven Reputation</i>. ACM, 2008, pp. 33–42, doi:<a href=\"https://doi.org/10.1145/1456377.1456387 \">10.1145/1456377.1456387 </a>.","ama":"Chatterjee K, De Alfaro L, Pye I. Robust content-driven reputation. In: ACM; 2008:33-42. doi:<a href=\"https://doi.org/10.1145/1456377.1456387 \">10.1145/1456377.1456387 </a>","apa":"Chatterjee, K., De Alfaro, L., &#38; Pye, I. (2008). Robust content-driven reputation (pp. 33–42). Presented at the AISec: Artificial Intelligence and Security, ACM. <a href=\"https://doi.org/10.1145/1456377.1456387 \">https://doi.org/10.1145/1456377.1456387 </a>","ieee":"K. Chatterjee, L. De Alfaro, and I. Pye, “Robust content-driven reputation,” presented at the AISec: Artificial Intelligence and Security, 2008, pp. 33–42.","chicago":"Chatterjee, Krishnendu, Luca De Alfaro, and Ian Pye. “Robust Content-Driven Reputation,” 33–42. ACM, 2008. <a href=\"https://doi.org/10.1145/1456377.1456387 \">https://doi.org/10.1145/1456377.1456387 </a>."},"abstract":[{"text":"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.","lang":"eng"}],"status":"public","doi":"10.1145/1456377.1456387 ","extern":1,"author":[{"last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Krishnendu Chatterjee"},{"last_name":"De Alfaro","first_name":"Luca","full_name":"de Alfaro, Luca"},{"last_name":"Pye","first_name":"Ian","full_name":"Pye, Ian"}],"_id":"3502","publication_status":"published","publisher":"ACM","date_created":"2018-12-11T12:03:40Z","conference":{"name":"AISec: Artificial Intelligence and Security"},"day":"31","quality_controlled":0},{"volume":2,"status":"public","citation":{"chicago":"Chatterjee, Krishnendu, Luca De Alfaro, Ritankar Majumdar, and Vishwanath Raman. “Algorithms for Game Metrics,” 2:107–18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2008. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1745\">https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1745</a>.","ieee":"K. Chatterjee, L. De Alfaro, R. Majumdar, and V. Raman, “Algorithms for game metrics,” presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, 2008, vol. 2, pp. 107–118.","apa":"Chatterjee, K., De Alfaro, L., Majumdar, R., &#38; Raman, V. (2008). Algorithms for game metrics (Vol. 2, pp. 107–118). Presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1745\">https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1745</a>","ama":"Chatterjee K, De Alfaro L, Majumdar R, Raman V. Algorithms for game metrics. In: Vol 2. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2008:107-118. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1745\">10.4230/LIPIcs.FSTTCS.2008.1745</a>","mla":"Chatterjee, Krishnendu, et al. <i>Algorithms for Game Metrics</i>. Vol. 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2008, pp. 107–18, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1745\">10.4230/LIPIcs.FSTTCS.2008.1745</a>.","ista":"Chatterjee K, De Alfaro L, Majumdar R, Raman V. 2008. Algorithms for game metrics. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 2, 107–118.","short":"K. Chatterjee, L. De Alfaro, R. Majumdar, V. Raman, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2008, pp. 107–118."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"relation":"later_version","id":"3868","status":"public"}]},"quality_controlled":"1","date_created":"2018-12-11T12:03:40Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)"},"title":"Algorithms for game metrics","language":[{"iso":"eng"}],"file":[{"date_updated":"2020-07-14T12:46:12Z","date_created":"2019-05-10T10:01:21Z","content_type":"application/pdf","file_size":442139,"relation":"main_file","checksum":"0a447454a24e273f7ddf51dbfe47f877","file_name":"2008_LIPIcs_Chatterjee.pdf","creator":"dernst","access_level":"open_access","file_id":"6398"}],"type":"conference","year":"2008","date_published":"2008-12-05T00:00:00Z","alternative_title":["LIPIcs"],"page":"107 - 118","intvolume":"         2","publist_id":"2883","license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","abstract":[{"text":"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.\r\nWe 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\r\nformula 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\r\nto approximate the metrics using binary search.","lang":"eng"}],"doi":"10.4230/LIPIcs.FSTTCS.2008.1745","day":"05","conference":{"name":"FSTTCS: Foundations of Software Technology and Theoretical Computer Science"},"extern":"1","_id":"3504","publication_status":"published","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"De Alfaro, Luca","first_name":"Luca","last_name":"De Alfaro"},{"last_name":"Majumdar","full_name":"Majumdar, Ritankar","first_name":"Ritankar"},{"full_name":"Raman, Vishwanath","first_name":"Vishwanath","last_name":"Raman"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","ddc":["000"],"acknowledgement":"This research was supported in part by the NSF grants CCR-0132780 and CNS-0720884.","month":"12","date_updated":"2025-09-30T09:31:30Z","has_accepted_license":"1","file_date_updated":"2020-07-14T12:46:12Z","oa_version":"Published Version","oa":1},{"day":"29","quality_controlled":0,"extern":1,"publication_status":"published","_id":"3516","author":[{"last_name":"Huxter","first_name":"John","full_name":"Huxter,John R"},{"full_name":"Senior,Timothy J","first_name":"Timothy","last_name":"Senior"},{"first_name":"Kevin","full_name":"Allen, Kevin","last_name":"Allen"},{"last_name":"Csicsvari","id":"3FA14672-F248-11E8-B48F-1D18A9856A87","first_name":"Jozsef L","orcid":"0000-0002-5193-4036","full_name":"Jozsef Csicsvari"}],"publisher":"Nature Publishing Group","date_created":"2018-12-11T12:03:44Z","abstract":[{"text":"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.","lang":"eng"}],"volume":11,"status":"public","doi":"10.1038/nn.2106","citation":{"apa":"Huxter, J., Senior, T., Allen, K., &#38; Csicsvari, J. L. (2008). Theta phase-specific codes for two-dimensional position, trajectory and heading in the hippocampus. <i>Nature Neuroscience</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/nn.2106\">https://doi.org/10.1038/nn.2106</a>","ieee":"J. Huxter, T. Senior, K. Allen, and J. L. Csicsvari, “Theta phase-specific codes for two-dimensional position, trajectory and heading in the hippocampus,” <i>Nature Neuroscience</i>, vol. 11, no. 5. Nature Publishing Group, pp. 587–594, 2008.","chicago":"Huxter, John, Timothy Senior, Kevin Allen, and Jozsef L Csicsvari. “Theta Phase-Specific Codes for Two-Dimensional Position, Trajectory and Heading in the Hippocampus.” <i>Nature Neuroscience</i>. Nature Publishing Group, 2008. <a href=\"https://doi.org/10.1038/nn.2106\">https://doi.org/10.1038/nn.2106</a>.","short":"J. Huxter, T. Senior, K. Allen, J.L. Csicsvari, Nature Neuroscience 11 (2008) 587–594.","ista":"Huxter J, Senior T, Allen K, Csicsvari JL. 2008. Theta phase-specific codes for two-dimensional position, trajectory and heading in the hippocampus. Nature Neuroscience. 11(5), 587–594.","mla":"Huxter, John, et al. “Theta Phase-Specific Codes for Two-Dimensional Position, Trajectory and Heading in the Hippocampus.” <i>Nature Neuroscience</i>, vol. 11, no. 5, Nature Publishing Group, 2008, pp. 587–94, doi:<a href=\"https://doi.org/10.1038/nn.2106\">10.1038/nn.2106</a>.","ama":"Huxter J, Senior T, Allen K, Csicsvari JL. Theta phase-specific codes for two-dimensional position, trajectory and heading in the hippocampus. <i>Nature Neuroscience</i>. 2008;11(5):587-594. doi:<a href=\"https://doi.org/10.1038/nn.2106\">10.1038/nn.2106</a>"},"type":"journal_article","issue":"5","year":"2008","title":"Theta phase-specific codes for two-dimensional position, trajectory and heading in the hippocampus","publication":"Nature Neuroscience","intvolume":"        11","month":"05","date_updated":"2021-01-12T07:44:00Z","publist_id":"2869","date_published":"2008-05-29T00:00:00Z","page":"587 - 594"},{"title":"Reactivation of experience-dependent cell assembly patterns in the hippocampus","publication":"Nature Neuroscience","year":"2008","issue":"2","type":"journal_article","abstract":[{"text":"The hippocampus is thought to be involved in episodic memory formation by reactivating traces of waking experience during sleep. Indeed, the joint firing of spatially tuned pyramidal cells encoding nearby places recur during sleep. We found that the sleep cofiring of rat CA1 pyramidal cells encoding similar places increased relative to the sleep session before exploration. This cofiring increase depended on the number of times that cells fired together with short latencies ( &lt; 50 ms) during exploration, and was strongest between cells representing the most visited places. This is indicative of a Hebbian learning rule in which changes in firing associations between cells are determined by the number of waking coincident firing events. In contrast, cells encoding different locations reduced their cofiring in proportion to the number of times that they fired independently. Together these data indicate that reactivated patterns are shaped by both positive and negative changes in cofiring, which are determined by recent behavior.","lang":"eng"}],"volume":11,"doi":"10.1038/nn2037","status":"public","citation":{"chicago":"O’Neill, Joseph, Timothy Senior, Kevin Allen, John Huxter, and Jozsef L Csicsvari. “Reactivation of Experience-Dependent Cell Assembly Patterns in the Hippocampus.” <i>Nature Neuroscience</i>. Nature Publishing Group, 2008. <a href=\"https://doi.org/10.1038/nn2037\">https://doi.org/10.1038/nn2037</a>.","apa":"O’Neill, J., Senior, T., Allen, K., Huxter, J., &#38; Csicsvari, J. L. (2008). Reactivation of experience-dependent cell assembly patterns in the hippocampus. <i>Nature Neuroscience</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/nn2037\">https://doi.org/10.1038/nn2037</a>","ieee":"J. O’Neill, T. Senior, K. Allen, J. Huxter, and J. L. Csicsvari, “Reactivation of experience-dependent cell assembly patterns in the hippocampus,” <i>Nature Neuroscience</i>, vol. 11, no. 2. Nature Publishing Group, pp. 209–215, 2008.","mla":"O’Neill, Joseph, et al. “Reactivation of Experience-Dependent Cell Assembly Patterns in the Hippocampus.” <i>Nature Neuroscience</i>, vol. 11, no. 2, Nature Publishing Group, 2008, pp. 209–15, doi:<a href=\"https://doi.org/10.1038/nn2037\">10.1038/nn2037</a>.","ama":"O’Neill J, Senior T, Allen K, Huxter J, Csicsvari JL. Reactivation of experience-dependent cell assembly patterns in the hippocampus. <i>Nature Neuroscience</i>. 2008;11(2):209-215. doi:<a href=\"https://doi.org/10.1038/nn2037\">10.1038/nn2037</a>","short":"J. O’Neill, T. Senior, K. Allen, J. Huxter, J.L. Csicsvari, Nature Neuroscience 11 (2008) 209–215.","ista":"O’Neill J, Senior T, Allen K, Huxter J, Csicsvari JL. 2008. Reactivation of experience-dependent cell assembly patterns in the hippocampus. Nature Neuroscience. 11(2), 209–215."},"day":"01","quality_controlled":0,"extern":1,"publisher":"Nature Publishing Group","_id":"3520","author":[{"full_name":"Joseph O'Neill","first_name":"Joseph","last_name":"O'Neill","id":"426376DC-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Timothy","full_name":"Senior,Timothy J","last_name":"Senior"},{"last_name":"Allen","full_name":"Allen, Kevin","first_name":"Kevin"},{"full_name":"Huxter,John R","first_name":"John","last_name":"Huxter"},{"last_name":"Csicsvari","id":"3FA14672-F248-11E8-B48F-1D18A9856A87","first_name":"Jozsef L","orcid":"0000-0002-5193-4036","full_name":"Jozsef Csicsvari"}],"publication_status":"published","date_created":"2018-12-11T12:03:46Z","date_published":"2008-02-01T00:00:00Z","page":"209 - 215","intvolume":"        11","month":"02","date_updated":"2021-01-12T07:44:02Z","publist_id":"2864"}]