[{"year":"2012","ec_funded":1,"oa_version":"Submitted Version","status":"public","page":"548 - 563","author":[{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654"}],"abstract":[{"lang":"eng","text":"The (decisional) learning with errors problem (LWE) asks to distinguish &quot;noisy&quot; inner products of a secret vector with random vectors from uniform. The learning parities with noise problem (LPN) is the special case where the elements of the vectors are bits. In recent years, the LWE and LPN problems have found many applications in cryptography. In this paper we introduce a (seemingly) much stronger adaptive assumption, called &quot;subspace LWE&quot; (SLWE), where the adversary can learn the inner product of the secret and random vectors after they were projected into an adaptively and adversarially chosen subspace. We prove that, surprisingly, the SLWE problem mapping into subspaces of dimension d is almost as hard as LWE using secrets of length d (the other direction is trivial.) This result immediately implies that several existing cryptosystems whose security is based on the hardness of the LWE/LPN problems are provably secure in a much stronger sense than anticipated. As an illustrative example we show that the standard way of using LPN for symmetric CPA secure encryption is even secure against a very powerful class of related key attacks. "}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"oa":1,"_id":"3280","conference":{"name":"TCC: Theory of Cryptography Conference","end_date":"2012-03-21","start_date":"2012-03-19","location":"Taormina, Sicily, Italy"},"main_file_link":[{"url":"http://www.iacr.org/archive/tcc2012/71940166/71940166.pdf","open_access":"1"}],"volume":7194,"project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Provable Security for Physical Cryptography","grant_number":"259668"}],"doi":"10.1007/978-3-642-28914-9_31","date_created":"2018-12-11T12:02:26Z","date_updated":"2021-01-12T07:42:21Z","department":[{"_id":"KrPi"}],"publist_id":"3366","intvolume":"      7194","month":"05","acknowledgement":"Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC).","citation":{"ieee":"K. Z. Pietrzak, “Subspace LWE,” presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy, 2012, vol. 7194, pp. 548–563.","short":"K.Z. Pietrzak, in:, Springer, 2012, pp. 548–563.","mla":"Pietrzak, Krzysztof Z. <i>Subspace LWE</i>. Vol. 7194, Springer, 2012, pp. 548–63, doi:<a href=\"https://doi.org/10.1007/978-3-642-28914-9_31\">10.1007/978-3-642-28914-9_31</a>.","chicago":"Pietrzak, Krzysztof Z. “Subspace LWE,” 7194:548–63. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-28914-9_31\">https://doi.org/10.1007/978-3-642-28914-9_31</a>.","ista":"Pietrzak KZ. 2012. Subspace LWE. TCC: Theory of Cryptography Conference, LNCS, vol. 7194, 548–563.","apa":"Pietrzak, K. Z. (2012). Subspace LWE (Vol. 7194, pp. 548–563). Presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy: Springer. <a href=\"https://doi.org/10.1007/978-3-642-28914-9_31\">https://doi.org/10.1007/978-3-642-28914-9_31</a>","ama":"Pietrzak KZ. Subspace LWE. In: Vol 7194. Springer; 2012:548-563. doi:<a href=\"https://doi.org/10.1007/978-3-642-28914-9_31\">10.1007/978-3-642-28914-9_31</a>"},"type":"conference","publication_status":"published","quality_controlled":"1","publisher":"Springer","alternative_title":["LNCS"],"title":"Subspace LWE","date_published":"2012-05-04T00:00:00Z","day":"04"},{"conference":{"start_date":"2012-03-19","location":"Taormina, Sicily, Italy","end_date":"2012-03-21","name":"TCC: Theory of Cryptography Conference"},"year":"2012","_id":"3281","doi":"10.1007/978-3-642-28914-9_26","volume":7194,"main_file_link":[{"url":"http://www.iacr.org/archive/tcc2012/tcc2012-index.html"}],"intvolume":"      7194","status":"public","publist_id":"3365","oa_version":"None","department":[{"_id":"KrPi"}],"date_updated":"2021-01-12T07:42:22Z","date_created":"2018-12-11T12:02:26Z","citation":{"chicago":"Pietrzak, Krzysztof Z, Alon Rosen, and Gil Segev. “Lossy Functions Do Not Amplify Well,” 7194:458–75. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-28914-9_26\">https://doi.org/10.1007/978-3-642-28914-9_26</a>.","mla":"Pietrzak, Krzysztof Z., et al. <i>Lossy Functions Do Not Amplify Well</i>. Vol. 7194, Springer, 2012, pp. 458–75, doi:<a href=\"https://doi.org/10.1007/978-3-642-28914-9_26\">10.1007/978-3-642-28914-9_26</a>.","short":"K.Z. Pietrzak, A. Rosen, G. Segev, in:, Springer, 2012, pp. 458–475.","ieee":"K. Z. Pietrzak, A. Rosen, and G. Segev, “Lossy functions do not amplify well,” presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy, 2012, vol. 7194, pp. 458–475.","ama":"Pietrzak KZ, Rosen A, Segev G. Lossy functions do not amplify well. In: Vol 7194. Springer; 2012:458-475. doi:<a href=\"https://doi.org/10.1007/978-3-642-28914-9_26\">10.1007/978-3-642-28914-9_26</a>","apa":"Pietrzak, K. Z., Rosen, A., &#38; Segev, G. (2012). Lossy functions do not amplify well (Vol. 7194, pp. 458–475). Presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy: Springer. <a href=\"https://doi.org/10.1007/978-3-642-28914-9_26\">https://doi.org/10.1007/978-3-642-28914-9_26</a>","ista":"Pietrzak KZ, Rosen A, Segev G. 2012. Lossy functions do not amplify well. TCC: Theory of Cryptography Conference, LNCS, vol. 7194, 458–475."},"acknowledgement":"We would like to thank Oded Goldreich and Omer Rein- gold for discussions at an early stage of this project, and Scott Aaronson for clarifications regarding the collision problem.\r\n","author":[{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z"},{"first_name":"Alon","full_name":"Rosen, Alon","last_name":"Rosen"},{"last_name":"Segev","full_name":"Segev, Gil","first_name":"Gil"}],"page":"458 - 475","month":"05","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publisher":"Springer","abstract":[{"lang":"eng","text":"We consider the problem of amplifying the &quot;lossiness&quot; of functions. We say that an oracle circuit C*: {0,1} m → {0,1}* amplifies relative lossiness from ℓ/n to L/m if for every function f:{0,1} n → {0,1} n it holds that 1 If f is injective then so is C f. 2 If f has image size of at most 2 n-ℓ, then C f has image size at most 2 m-L. The question is whether such C* exists for L/m ≫ ℓ/n. This problem arises naturally in the context of cryptographic &quot;lossy functions,&quot; where the relative lossiness is the key parameter. We show that for every circuit C* that makes at most t queries to f, the relative lossiness of C f is at most L/m ≤ ℓ/n + O(log t)/n. In particular, no black-box method making a polynomial t = poly(n) number of queries can amplify relative lossiness by more than an O(logn)/n additive term. We show that this is tight by giving a simple construction (cascading with some randomization) that achieves such amplification."}],"type":"conference","publication_status":"published","quality_controlled":"1","alternative_title":["LNCS"],"language":[{"iso":"eng"}],"day":"04","date_published":"2012-05-04T00:00:00Z","title":"Lossy functions do not amplify well"},{"has_accepted_license":"1","alternative_title":["LNCS"],"quality_controlled":"1","publication_status":"published","type":"conference","publisher":"Springer","day":"10","license":"https://creativecommons.org/licenses/by/4.0/","title":"Message authentication, revisited","date_published":"2012-03-10T00:00:00Z","file":[{"creator":"system","file_name":"IST-2016-686-v1+1_059.pdf","file_size":372292,"checksum":"8557c17a8c2586d06ebfe62d934f5c5f","file_id":"5074","relation":"main_file","date_created":"2018-12-12T10:14:23Z","access_level":"open_access","date_updated":"2020-07-14T12:46:06Z","content_type":"application/pdf"}],"volume":7237,"doi":"10.1007/978-3-642-29011-4_22","project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","name":"Provable Security for Physical Cryptography","grant_number":"259668","call_identifier":"FP7"}],"conference":{"name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","end_date":"2012-04-19","location":"Cambridge, UK","start_date":"2012-04-15"},"_id":"3282","month":"03","citation":{"ista":"Dodis Y, Pietrzak KZ, Kiltz E, Wichs D. 2012. Message authentication, revisited. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 7237, 355–374.","apa":"Dodis, Y., Pietrzak, K. Z., Kiltz, E., &#38; Wichs, D. (2012). Message authentication, revisited (Vol. 7237, pp. 355–374). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Cambridge, UK: Springer. <a href=\"https://doi.org/10.1007/978-3-642-29011-4_22\">https://doi.org/10.1007/978-3-642-29011-4_22</a>","ama":"Dodis Y, Pietrzak KZ, Kiltz E, Wichs D. Message authentication, revisited. In: Vol 7237. Springer; 2012:355-374. doi:<a href=\"https://doi.org/10.1007/978-3-642-29011-4_22\">10.1007/978-3-642-29011-4_22</a>","ieee":"Y. Dodis, K. Z. Pietrzak, E. Kiltz, and D. Wichs, “Message authentication, revisited,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Cambridge, UK, 2012, vol. 7237, pp. 355–374.","short":"Y. Dodis, K.Z. Pietrzak, E. Kiltz, D. Wichs, in:, Springer, 2012, pp. 355–374.","mla":"Dodis, Yevgeniy, et al. <i>Message Authentication, Revisited</i>. Vol. 7237, Springer, 2012, pp. 355–74, doi:<a href=\"https://doi.org/10.1007/978-3-642-29011-4_22\">10.1007/978-3-642-29011-4_22</a>.","chicago":"Dodis, Yevgeniy, Krzysztof Z Pietrzak, Eike Kiltz, and Daniel Wichs. “Message Authentication, Revisited,” 7237:355–74. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-29011-4_22\">https://doi.org/10.1007/978-3-642-29011-4_22</a>."},"acknowledgement":"Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC)","publist_id":"3364","department":[{"_id":"KrPi"}],"date_created":"2018-12-11T12:02:27Z","date_updated":"2021-01-12T07:42:22Z","intvolume":"      7237","file_date_updated":"2020-07-14T12:46:06Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"Traditionally, symmetric-key message authentication codes (MACs) are easily built from pseudorandom functions (PRFs). In this work we propose a wide variety of other approaches to building efficient MACs, without going through a PRF first. In particular, unlike deterministic PRF-based MACs, where each message has a unique valid tag, we give a number of probabilistic MAC constructions from various other primitives/assumptions. Our main results are summarized as follows: We show several new probabilistic MAC constructions from a variety of general assumptions, including CCA-secure encryption, Hash Proof Systems and key-homomorphic weak PRFs. By instantiating these frameworks under concrete number theoretic assumptions, we get several schemes which are more efficient than just using a state-of-the-art PRF instantiation under the corresponding assumption. For probabilistic MACs, unlike deterministic ones, unforgeability against a chosen message attack (uf-cma ) alone does not imply security if the adversary can additionally make verification queries (uf-cmva ). We give an efficient generic transformation from any uf-cma secure MAC which is &quot;message-hiding&quot; into a uf-cmva secure MAC. This resolves the main open problem of Kiltz et al. from Eurocrypt'11; By using our transformation on their constructions, we get the first efficient MACs from the LPN assumption. While all our new MAC constructions immediately give efficient actively secure, two-round symmetric-key identification schemes, we also show a very simple, three-round actively secure identification protocol from any weak PRF. In particular, the resulting protocol is much more efficient than the trivial approach of building a regular PRF from a weak PRF. © 2012 International Association for Cryptologic Research."}],"ddc":["000","004"],"oa":1,"language":[{"iso":"eng"}],"ec_funded":1,"tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"pubrep_id":"686","year":"2012","author":[{"first_name":"Yevgeniy","last_name":"Dodis","full_name":"Dodis, Yevgeniy"},{"orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kiltz, Eike","last_name":"Kiltz","first_name":"Eike"},{"first_name":"Daniel","last_name":"Wichs","full_name":"Wichs, Daniel"}],"page":"355 - 374","oa_version":"Submitted Version","status":"public"},{"publication_status":"published","quality_controlled":"1","type":"journal_article","scopus_import":1,"publisher":"ASM","day":"01","date_published":"2012-01-01T00:00:00Z","title":"A vaccinia virus-driven interplay between the MKK4/7-JNK1/2 pathway and cytoskeleton reorganization","publication":"Journal of Virology","main_file_link":[{"url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3255887/","open_access":"1"}],"volume":86,"doi":"10.1128/JVI.05638-11","issue":"1","_id":"3289","month":"01","citation":{"apa":"Pereira, A., Leite, F., Brasil, B., Soares Martins, J., Torres, A., Pimenta, P., … Bonjardim, C. (2012). A vaccinia virus-driven interplay between the MKK4/7-JNK1/2 pathway and cytoskeleton reorganization. <i>Journal of Virology</i>. ASM. <a href=\"https://doi.org/10.1128/JVI.05638-11\">https://doi.org/10.1128/JVI.05638-11</a>","ama":"Pereira A, Leite F, Brasil B, et al. A vaccinia virus-driven interplay between the MKK4/7-JNK1/2 pathway and cytoskeleton reorganization. <i>Journal of Virology</i>. 2012;86(1):172-184. doi:<a href=\"https://doi.org/10.1128/JVI.05638-11\">10.1128/JVI.05638-11</a>","ista":"Pereira A, Leite F, Brasil B, Soares Martins J, Torres A, Pimenta P, Souto Padrón T, Tranktman P, Ferreira P, Kroon E, Bonjardim C. 2012. A vaccinia virus-driven interplay between the MKK4/7-JNK1/2 pathway and cytoskeleton reorganization. Journal of Virology. 86(1), 172–184.","chicago":"Pereira, Anna, Flávia Leite, Bruno Brasil, Jamaria Soares Martins, Alice Torres, Paulo Pimenta, Thais Souto Padrón, et al. “A Vaccinia Virus-Driven Interplay between the MKK4/7-JNK1/2 Pathway and Cytoskeleton Reorganization.” <i>Journal of Virology</i>. ASM, 2012. <a href=\"https://doi.org/10.1128/JVI.05638-11\">https://doi.org/10.1128/JVI.05638-11</a>.","ieee":"A. Pereira <i>et al.</i>, “A vaccinia virus-driven interplay between the MKK4/7-JNK1/2 pathway and cytoskeleton reorganization,” <i>Journal of Virology</i>, vol. 86, no. 1. ASM, pp. 172–184, 2012.","short":"A. Pereira, F. Leite, B. Brasil, J. Soares Martins, A. Torres, P. Pimenta, T. Souto Padrón, P. Tranktman, P. Ferreira, E. Kroon, C. Bonjardim, Journal of Virology 86 (2012) 172–184.","mla":"Pereira, Anna, et al. “A Vaccinia Virus-Driven Interplay between the MKK4/7-JNK1/2 Pathway and Cytoskeleton Reorganization.” <i>Journal of Virology</i>, vol. 86, no. 1, ASM, 2012, pp. 172–84, doi:<a href=\"https://doi.org/10.1128/JVI.05638-11\">10.1128/JVI.05638-11</a>."},"acknowledgement":"This work was supported by grants from Fundação de Amparo a Pesquisa do Estado de Minas Gerais (FAPEMIG), the Brazilian Federal Agency for Support and Evaluation of Graduate Education (CAPES), and the National Council for Scientific and Technological Development (CNPq). A.C.T.C.P., B.S.A.F.B., F.G.G.L., and J.A.P.S.-M. were recipients of predoctoral fellowships from CNPq. C.A.B., E.G.K., T.S.-P., P.F.P.P., and P.C.P.F. are recipients of research fellowships from CNPq. \r\n\r\n\r\nWe are grateful to Angela S. Lopes, Ilda M. V. Gama, João R. dos Santos, and Andreza A. Carvalho for their secretarial/technical assistance and to Fernanda Gambogi for help with immunofluorescence microscopy. We also thank M. C. Sogayar (Department of Biochemistry, University of São Paulo, São Paulo, Brazil), who kindly provided us with the A31 cell line, and R. Davis (Howard Hughes Medical Institute, University of Massachusetts Medical School, Worcester, MA) for the WT and JNK1/2-, MKK4-, MKK7-, and MKK4/7-KO cells. VACV WR was from C. Jungwirth (Universität Würzburg, Würzburg, Germany). The recombinant VACV vF13L-GFP and the rabbit polyclonal antibodies against viral proteins, B5R, D8L, L1R, and A36R, were from B. Moss (NIAID, Bethesda, MD). The pcDNA3-Myc-JNK2-MKK7 WT plasmid was from Eugen Kerkhoff (Universität Würzburg, Würzburg, Germany). We also thank Flávio G. da Fonseca (UFMG, Belo Horizonte, MG, Brazil) and Kathleen A. Boyle (Medical College of Wisconsin, Milwaukee, WI) for critically reading the manuscript.","department":[{"_id":"JoBo"}],"publist_id":"3356","date_updated":"2021-01-12T07:42:25Z","date_created":"2018-12-11T12:02:29Z","intvolume":"        86","external_id":{"pmid":["22031940"]},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"Viral manipulation of transduction pathways associated with key cellular functions such as survival, response to microbial infection, and cytoskeleton reorganization can provide the supportive milieu for a productive infection. Here, we demonstrate that vaccinia virus (VACV) infection leads to activation of the stress-activated protein kinase (SAPK)/extracellular signal-regulated kinase (ERK) 4/7 (MKK4/7)-c-Jun N-terminal protein kinase 1/2 (JNK1/2) pathway; further, the stimulation of this pathway requires postpenetration, prereplicative events in the viral replication cycle. Although the formation of intracellular mature virus (IMV) was not affected in MKK4/7- or JNK1/2-knockout (KO) cells, we did note an accentuated deregulation of microtubule and actin network organization in infected JNK1/2-KO cells. This was followed by deregulated viral trafficking to the periphery and enhanced enveloped particle release. Furthermore, VACV infection induced alterations in the cell contractility and morphology, and cell migration was reduced in the JNK-KO cells. In addition, phosphorylation of proteins implicated with early cell contractility and cell migration, such as microtubule-associated protein 1B and paxillin, respectively, was not detected in the VACV-infected KO cells. In sum, our findings uncover a regulatory role played by the MKK4/7-JNK1/2 pathway in cytoskeleton reorganization during VACV infection.\r\n"}],"oa":1,"pmid":1,"language":[{"iso":"eng"}],"year":"2012","author":[{"first_name":"Anna","last_name":"Pereira","full_name":"Pereira, Anna"},{"full_name":"Leite, Flávia","last_name":"Leite","id":"36705F98-F248-11E8-B48F-1D18A9856A87","first_name":"Flávia"},{"full_name":"Brasil, Bruno","last_name":"Brasil","first_name":"Bruno"},{"first_name":"Jamaria","last_name":"Soares Martins","full_name":"Soares Martins, Jamaria"},{"first_name":"Alice","full_name":"Torres, Alice","last_name":"Torres"},{"last_name":"Pimenta","full_name":"Pimenta, Paulo","first_name":"Paulo"},{"last_name":"Souto Padrón","full_name":"Souto Padrón, Thais","first_name":"Thais"},{"last_name":"Tranktman","full_name":"Tranktman, Paula","first_name":"Paula"},{"full_name":"Ferreira, Paulo","last_name":"Ferreira","first_name":"Paulo"},{"last_name":"Kroon","full_name":"Kroon, Erna","first_name":"Erna"},{"first_name":"Cláudio","last_name":"Bonjardim","full_name":"Bonjardim, Cláudio"}],"page":"172 - 184","oa_version":"Submitted Version","status":"public"},{"author":[{"full_name":"Bendich, Paul","last_name":"Bendich","first_name":"Paul","id":"43F6EC54-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Cabello","full_name":"Cabello, Sergio","first_name":"Sergio"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner"}],"page":"1436 - 1444","status":"public","oa_version":"Submitted Version","year":"2012","pubrep_id":"542","oa":1,"ddc":["000"],"language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:06Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"The theory of persistent homology opens up the possibility to reason about topological features of a space or a function quantitatively and in combinatorial terms. We refer to this new angle at a classical subject within algebraic topology as a point calculus, which we present for the family of interlevel sets of a real-valued function. Our account of the subject is expository, devoid of proofs, and written for non-experts in algebraic topology."}],"citation":{"apa":"Bendich, P., Cabello, S., &#38; Edelsbrunner, H. (2012). A point calculus for interlevel set homology. <i>Pattern Recognition Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.patrec.2011.10.007\">https://doi.org/10.1016/j.patrec.2011.10.007</a>","ama":"Bendich P, Cabello S, Edelsbrunner H. A point calculus for interlevel set homology. <i>Pattern Recognition Letters</i>. 2012;33(11):1436-1444. doi:<a href=\"https://doi.org/10.1016/j.patrec.2011.10.007\">10.1016/j.patrec.2011.10.007</a>","ista":"Bendich P, Cabello S, Edelsbrunner H. 2012. A point calculus for interlevel set homology. Pattern Recognition Letters. 33(11), 1436–1444.","chicago":"Bendich, Paul, Sergio Cabello, and Herbert Edelsbrunner. “A Point Calculus for Interlevel Set Homology.” <i>Pattern Recognition Letters</i>. Elsevier, 2012. <a href=\"https://doi.org/10.1016/j.patrec.2011.10.007\">https://doi.org/10.1016/j.patrec.2011.10.007</a>.","ieee":"P. Bendich, S. Cabello, and H. Edelsbrunner, “A point calculus for interlevel set homology,” <i>Pattern Recognition Letters</i>, vol. 33, no. 11. Elsevier, pp. 1436–1444, 2012.","mla":"Bendich, Paul, et al. “A Point Calculus for Interlevel Set Homology.” <i>Pattern Recognition Letters</i>, vol. 33, no. 11, Elsevier, 2012, pp. 1436–44, doi:<a href=\"https://doi.org/10.1016/j.patrec.2011.10.007\">10.1016/j.patrec.2011.10.007</a>.","short":"P. Bendich, S. Cabello, H. Edelsbrunner, Pattern Recognition Letters 33 (2012) 1436–1444."},"acknowledgement":"Research by the third author is partially supported by the National Science Foundation (NSF) under grant DBI-0820624.","month":"08","intvolume":"        33","publist_id":"3330","department":[{"_id":"HeEd"}],"date_updated":"2021-01-12T07:42:34Z","date_created":"2018-12-11T12:02:36Z","doi":"10.1016/j.patrec.2011.10.007","file":[{"file_name":"IST-2016-542-v1+1_2012-J-01-Poinculus.pdf","file_size":280280,"creator":"system","content_type":"application/pdf","file_id":"5116","checksum":"d65f79775b51258a604ca5ec741297cc","access_level":"open_access","relation":"main_file","date_updated":"2020-07-14T12:46:06Z","date_created":"2018-12-12T10:15:00Z"}],"volume":33,"_id":"3310","issue":"11","publication":"Pattern Recognition Letters","day":"01","title":"A point calculus for interlevel set homology","date_published":"2012-08-01T00:00:00Z","has_accepted_license":"1","publisher":"Elsevier","publication_status":"published","quality_controlled":"1","type":"journal_article","scopus_import":1},{"quality_controlled":"1","scopus_import":1,"type":"journal_article","publication_status":"published","publisher":"World Scientific Publishing","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"We introduce two-level discounted and mean-payoff games played by two players on a perfect-information stochastic game graph. The upper level game is a discounted or mean-payoff game and the lower level game is a (undiscounted) reachability game. Two-level games model hierarchical and sequential decision making under uncertainty across different time scales. For both discounted and mean-payoff two-level games, we show the existence of pure memoryless optimal strategies for both players and an ordered field property. We show that if there is only one player (Markov decision processes), then the values can be computed in polynomial time. It follows that whether the value of a player is equal to a given rational constant in two-level discounted or mean-payoff games can be decided in NP ∩ coNP. We also give an alternate strategy improvement algorithm to compute the value. © 2012 World Scientific Publishing Company.","lang":"eng"}],"day":"01","title":"Discounting and averaging in games across time scales","date_published":"2012-04-01T00:00:00Z","publication":"International Journal of Foundations of Computer Science","language":[{"iso":"eng"}],"issue":"3","year":"2012","_id":"3314","volume":23,"doi":"10.1142/S0129054112400308","project":[{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"oa_version":"None","department":[{"_id":"KrCh"}],"publist_id":"3326","date_updated":"2021-01-12T07:42:35Z","date_created":"2018-12-11T12:02:37Z","intvolume":"        23","status":"public","author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Majumdar, Ritankar","last_name":"Majumdar","first_name":"Ritankar"}],"month":"04","page":"609 - 625","citation":{"ista":"Chatterjee K, Majumdar R. 2012. Discounting and averaging in games across time scales. International Journal of Foundations of Computer Science. 23(3), 609–625.","ama":"Chatterjee K, Majumdar R. Discounting and averaging in games across time scales. <i>International Journal of Foundations of Computer Science</i>. 2012;23(3):609-625. doi:<a href=\"https://doi.org/10.1142/S0129054112400308\">10.1142/S0129054112400308</a>","apa":"Chatterjee, K., &#38; Majumdar, R. (2012). Discounting and averaging in games across time scales. <i>International Journal of Foundations of Computer Science</i>. World Scientific Publishing. <a href=\"https://doi.org/10.1142/S0129054112400308\">https://doi.org/10.1142/S0129054112400308</a>","mla":"Chatterjee, Krishnendu, and Ritankar Majumdar. “Discounting and Averaging in Games across Time Scales.” <i>International Journal of Foundations of Computer Science</i>, vol. 23, no. 3, World Scientific Publishing, 2012, pp. 609–25, doi:<a href=\"https://doi.org/10.1142/S0129054112400308\">10.1142/S0129054112400308</a>.","short":"K. Chatterjee, R. Majumdar, International Journal of Foundations of Computer Science 23 (2012) 609–625.","ieee":"K. Chatterjee and R. Majumdar, “Discounting and averaging in games across time scales,” <i>International Journal of Foundations of Computer Science</i>, vol. 23, no. 3. World Scientific Publishing, pp. 609–625, 2012.","chicago":"Chatterjee, Krishnendu, and Ritankar Majumdar. “Discounting and Averaging in Games across Time Scales.” <i>International Journal of Foundations of Computer Science</i>. World Scientific Publishing, 2012. <a href=\"https://doi.org/10.1142/S0129054112400308\">https://doi.org/10.1142/S0129054112400308</a>."}},{"quality_controlled":"1","publication_status":"published","scopus_import":"1","type":"book_chapter","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Springer","abstract":[{"text":"Under physiological conditions the brain, via the purine salvage pathway, reuses the preformed purine bases hypoxanthine, derived from ATP degradation, and adenine (Ade), derived from polyamine synthesis, to restore its ATP pool. However, the massive degradation of ATP during ischemia, although providing valuable neuroprotective adenosine, results in the accumulation and loss of diffusible purine metabolites and thereby leads to a protracted reduction in the post-ischemic ATP pool size. In vivo, this may both limit the ability to deploy ATP-dependent reparative mechanisms and reduce the subsequent availability of adenosine, whilst in brain slices results in tissue with substantially lower levels of ATP than in vivo. In the present review, we describe the mechanisms by which brain tissue replenishes its ATP, how this can be improved with the clinically tolerated chemicals D-ribose and adenine, and the functional, and potential therapeutic, implications of doing so.","lang":"eng"}],"edition":"1","article_processing_charge":"No","day":"23","date_published":"2012-07-23T00:00:00Z","title":"The double-edged sword: Gaining Adenosine at the expense of ATP. How to balance the books","language":[{"iso":"eng"}],"publication":"Adenosine","place":"New York","year":"2012","_id":"10896","doi":"10.1007/978-1-4614-3903-5_6","publication_identifier":{"isbn":["9781461439028"],"eisbn":["9781461439035"]},"oa_version":"None","department":[{"_id":"HaJa"}],"date_created":"2022-03-21T07:16:12Z","date_updated":"2022-06-21T11:51:58Z","status":"public","author":[{"first_name":"Stephanie","id":"3C77F464-F248-11E8-B48F-1D18A9856A87","full_name":"zur Nedden, Stephanie","last_name":"zur Nedden"},{"full_name":"Doney, Alexander S.","last_name":"Doney","first_name":"Alexander S."},{"first_name":"Bruno G.","last_name":"Frenguelli","full_name":"Frenguelli, Bruno G."}],"page":"109-129","month":"07","citation":{"chicago":"Nedden, Stephanie zur, Alexander S. Doney, and Bruno G. Frenguelli. “The Double-Edged Sword: Gaining Adenosine at the Expense of ATP. How to Balance the Books.” In <i>Adenosine</i>, edited by Susan Masino and Detlev Boison, 1st ed., 109–29. New York: Springer, 2012. <a href=\"https://doi.org/10.1007/978-1-4614-3903-5_6\">https://doi.org/10.1007/978-1-4614-3903-5_6</a>.","short":"S. zur Nedden, A.S. Doney, B.G. Frenguelli, in:, S. Masino, D. Boison (Eds.), Adenosine, 1st ed., Springer, New York, 2012, pp. 109–129.","mla":"zur Nedden, Stephanie, et al. “The Double-Edged Sword: Gaining Adenosine at the Expense of ATP. How to Balance the Books.” <i>Adenosine</i>, edited by Susan Masino and Detlev Boison, 1st ed., Springer, 2012, pp. 109–29, doi:<a href=\"https://doi.org/10.1007/978-1-4614-3903-5_6\">10.1007/978-1-4614-3903-5_6</a>.","ieee":"S. zur Nedden, A. S. Doney, and B. G. Frenguelli, “The double-edged sword: Gaining Adenosine at the expense of ATP. How to balance the books,” in <i>Adenosine</i>, 1st ed., S. Masino and D. Boison, Eds. New York: Springer, 2012, pp. 109–129.","ama":"zur Nedden S, Doney AS, Frenguelli BG. The double-edged sword: Gaining Adenosine at the expense of ATP. How to balance the books. In: Masino S, Boison D, eds. <i>Adenosine</i>. 1st ed. New York: Springer; 2012:109-129. doi:<a href=\"https://doi.org/10.1007/978-1-4614-3903-5_6\">10.1007/978-1-4614-3903-5_6</a>","apa":"zur Nedden, S., Doney, A. S., &#38; Frenguelli, B. G. (2012). The double-edged sword: Gaining Adenosine at the expense of ATP. How to balance the books. In S. Masino &#38; D. Boison (Eds.), <i>Adenosine</i> (1st ed., pp. 109–129). New York: Springer. <a href=\"https://doi.org/10.1007/978-1-4614-3903-5_6\">https://doi.org/10.1007/978-1-4614-3903-5_6</a>","ista":"zur Nedden S, Doney AS, Frenguelli BG. 2012.The double-edged sword: Gaining Adenosine at the expense of ATP. How to balance the books. In: Adenosine. , 109–129."},"editor":[{"first_name":"Susan","full_name":"Masino, Susan","last_name":"Masino"},{"full_name":"Boison, Detlev","last_name":"Boison","first_name":"Detlev"}],"acknowledgement":"We are grateful to Research into Ageing/Ageing UK and The Dunhill Trust for funding SzN’s graduate studies, and to Prof Nicholas Dale for his valuable input."},{"_id":"10903","conference":{"location":"Thiruvananthapuram, India","start_date":"2012-10-03","end_date":"2012-10-06","name":"ATVA: Automated Technology for Verification and Analysis"},"volume":7561,"doi":"10.1007/978-3-642-33386-6_14","date_created":"2022-03-21T07:58:39Z","date_updated":"2023-09-05T14:07:24Z","department":[{"_id":"ToHe"}],"intvolume":"      7561","month":"10","acknowledgement":"This work has been partially supported by the French ANR project Veridyc","citation":{"apa":"Bouajjani, A., Dragoi, C., Enea, C., &#38; Sighireanu, M. (2012). Accurate invariant checking for programs manipulating lists and arrays with infinite data. In <i>Automated Technology for Verification and Analysis</i> (Vol. 7561, pp. 167–182). Berlin, Heidelberg: Springer. <a href=\"https://doi.org/10.1007/978-3-642-33386-6_14\">https://doi.org/10.1007/978-3-642-33386-6_14</a>","ama":"Bouajjani A, Dragoi C, Enea C, Sighireanu M. Accurate invariant checking for programs manipulating lists and arrays with infinite data. In: <i>Automated Technology for Verification and Analysis</i>. Vol 7561. LNCS. Berlin, Heidelberg: Springer; 2012:167-182. doi:<a href=\"https://doi.org/10.1007/978-3-642-33386-6_14\">10.1007/978-3-642-33386-6_14</a>","ista":"Bouajjani A, Dragoi C, Enea C, Sighireanu M. 2012. Accurate invariant checking for programs manipulating lists and arrays with infinite data. Automated Technology for Verification and Analysis. ATVA: Automated Technology for Verification and AnalysisLNCS, LNCS, vol. 7561, 167–182.","chicago":"Bouajjani, Ahmed, Cezara Dragoi, Constantin Enea, and Mihaela Sighireanu. “Accurate Invariant Checking for Programs Manipulating Lists and Arrays with Infinite Data.” In <i>Automated Technology for Verification and Analysis</i>, 7561:167–82. LNCS. Berlin, Heidelberg: Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-33386-6_14\">https://doi.org/10.1007/978-3-642-33386-6_14</a>.","ieee":"A. Bouajjani, C. Dragoi, C. Enea, and M. Sighireanu, “Accurate invariant checking for programs manipulating lists and arrays with infinite data,” in <i>Automated Technology for Verification and Analysis</i>, Thiruvananthapuram, India, 2012, vol. 7561, pp. 167–182.","short":"A. Bouajjani, C. Dragoi, C. Enea, M. Sighireanu, in:, Automated Technology for Verification and Analysis, Springer, Berlin, Heidelberg, 2012, pp. 167–182.","mla":"Bouajjani, Ahmed, et al. “Accurate Invariant Checking for Programs Manipulating Lists and Arrays with Infinite Data.” <i>Automated Technology for Verification and Analysis</i>, vol. 7561, Springer, 2012, pp. 167–82, doi:<a href=\"https://doi.org/10.1007/978-3-642-33386-6_14\">10.1007/978-3-642-33386-6_14</a>."},"publication_status":"published","scopus_import":"1","type":"conference","quality_controlled":"1","publisher":"Springer","alternative_title":["LNCS"],"title":"Accurate invariant checking for programs manipulating lists and arrays with infinite data","date_published":"2012-10-15T00:00:00Z","day":"15","publication":"Automated Technology for Verification and Analysis","year":"2012","publication_identifier":{"isbn":["9783642333859"],"eisbn":["9783642333866"],"issn":["0302-9743"],"eissn":["1611-3349"]},"series_title":"LNCS","oa_version":"None","status":"public","page":"167-182","author":[{"first_name":"Ahmed","last_name":"Bouajjani","full_name":"Bouajjani, Ahmed"},{"full_name":"Dragoi, Cezara","last_name":"Dragoi","first_name":"Cezara","id":"2B2B5ED0-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Constantin","last_name":"Enea","full_name":"Enea, Constantin"},{"first_name":"Mihaela","last_name":"Sighireanu","full_name":"Sighireanu, Mihaela"}],"abstract":[{"lang":"eng","text":"We propose a logic-based framework for automated reasoning about sequential programs manipulating singly-linked lists and arrays with unbounded data. We introduce the logic SLAD, which allows combining shape constraints, written in a fragment of Separation Logic, with data and size constraints. We address the problem of checking the entailment between SLAD formulas, which is crucial in performing pre-post condition reasoning. Although this problem is undecidable in general for SLAD, we propose a sound and powerful procedure that is able to solve this problem for a large class of formulas, beyond the capabilities of existing techniques and tools. We prove that this procedure is complete, i.e., it is actually a decision procedure for this problem, for an important fragment of SLAD including known decidable logics. We implemented this procedure and shown its preciseness and its efficiency on a significant benchmark of formulas."}],"article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","language":[{"iso":"eng"}],"place":"Berlin, Heidelberg"},{"year":"2012","ec_funded":1,"publication_identifier":{"issn":["0302-9743","1611-3349"],"isbn":["9783642329395"],"eisbn":["9783642329401"]},"oa_version":"Preprint","status":"public","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"last_name":"Randour","full_name":"Randour, Mickael","first_name":"Mickael"},{"first_name":"Jean-François","last_name":"Raskin","full_name":"Raskin, Jean-François"}],"page":"115-131","editor":[{"full_name":"Koutny, Maciej","last_name":"Koutny","first_name":"Maciej"},{"first_name":"Irek","full_name":"Ulidowski, Irek","last_name":"Ulidowski"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"2716"}]},"external_id":{"arxiv":["1201.5073"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"Multi-dimensional mean-payoff and energy games provide the mathematical foundation for the quantitative study of reactive systems, and play a central role in the emerging quantitative theory of verification and synthesis. In this work, we study the strategy synthesis problem for games with such multi-dimensional objectives along with a parity condition, a canonical way to express ω-regular conditions. While in general, the winning strategies in such games may require infinite memory, for synthesis the most relevant problem is the construction of a finite-memory winning strategy (if one exists). Our main contributions are as follows. First, we show a tight exponential bound (matching upper and lower bounds) on the memory required for finite-memory winning strategies in both multi-dimensional mean-payoff and energy games along with parity objectives. This significantly improves the triple exponential upper bound for multi energy games (without parity) that could be derived from results in literature for games on VASS (vector addition systems with states). Second, we present an optimal symbolic and incremental algorithm to compute a finite-memory winning strategy (if one exists) in such games. Finally, we give a complete characterization of when finite memory of strategies can be traded off for randomness. In particular, we show that for one-dimension mean-payoff parity games, randomized memoryless strategies are as powerful as their pure finite-memory counterparts."}],"article_processing_charge":"No","language":[{"iso":"eng"}],"place":"Berlin, Heidelberg","conference":{"name":"CONCUR: Conference on Concurrency Theory","end_date":"2012-09-07","location":"Newcastle upon Tyne, United Kingdom","start_date":"2012-09-04"},"_id":"10904","volume":7454,"doi":"10.1007/978-3-642-32940-1_10","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"department":[{"_id":"KrCh"}],"date_created":"2022-03-21T08:00:21Z","date_updated":"2023-02-23T10:55:06Z","intvolume":"      7454","month":"09","citation":{"mla":"Chatterjee, Krishnendu, et al. “Strategy Synthesis for Multi-Dimensional Quantitative Objectives.” <i>CONCUR 2012 - Concurrency Theory</i>, edited by Maciej Koutny and Irek Ulidowski, vol. 7454, Springer, 2012, pp. 115–31, doi:<a href=\"https://doi.org/10.1007/978-3-642-32940-1_10\">10.1007/978-3-642-32940-1_10</a>.","short":"K. Chatterjee, M. Randour, J.-F. Raskin, in:, M. Koutny, I. Ulidowski (Eds.), CONCUR 2012 - Concurrency Theory, Springer, Berlin, Heidelberg, 2012, pp. 115–131.","ieee":"K. Chatterjee, M. Randour, and J.-F. Raskin, “Strategy synthesis for multi-dimensional quantitative objectives,” in <i>CONCUR 2012 - Concurrency Theory</i>, Newcastle upon Tyne, United Kingdom, 2012, vol. 7454, pp. 115–131.","chicago":"Chatterjee, Krishnendu, Mickael Randour, and Jean-François Raskin. “Strategy Synthesis for Multi-Dimensional Quantitative Objectives.” In <i>CONCUR 2012 - Concurrency Theory</i>, edited by Maciej Koutny and Irek Ulidowski, 7454:115–31. Berlin, Heidelberg: Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-32940-1_10\">https://doi.org/10.1007/978-3-642-32940-1_10</a>.","ista":"Chatterjee K, Randour M, Raskin J-F. 2012. Strategy synthesis for multi-dimensional quantitative objectives. CONCUR 2012 - Concurrency Theory. CONCUR: Conference on Concurrency Theory, LNCS, vol. 7454, 115–131.","ama":"Chatterjee K, Randour M, Raskin J-F. Strategy synthesis for multi-dimensional quantitative objectives. In: Koutny M, Ulidowski I, eds. <i>CONCUR 2012 - Concurrency Theory</i>. Vol 7454. Berlin, Heidelberg: Springer; 2012:115-131. doi:<a href=\"https://doi.org/10.1007/978-3-642-32940-1_10\">10.1007/978-3-642-32940-1_10</a>","apa":"Chatterjee, K., Randour, M., &#38; Raskin, J.-F. (2012). Strategy synthesis for multi-dimensional quantitative objectives. In M. Koutny &#38; I. Ulidowski (Eds.), <i>CONCUR 2012 - Concurrency Theory</i> (Vol. 7454, pp. 115–131). Berlin, Heidelberg: Springer. <a href=\"https://doi.org/10.1007/978-3-642-32940-1_10\">https://doi.org/10.1007/978-3-642-32940-1_10</a>"},"acknowledgement":"Author supported by Austrian Science Fund (FWF) Grant No P 23499-N23, FWF NFN Grant No S11407 (RiSE), ERC Start Grant (279307: Graph Games), Microsoft faculty fellowship.","publication_status":"published","type":"conference","scopus_import":"1","quality_controlled":"1","publisher":"Springer","arxiv":1,"alternative_title":["LNCS"],"day":"15","date_published":"2012-09-15T00:00:00Z","title":"Strategy synthesis for multi-dimensional quantitative objectives","publication":"CONCUR 2012 - Concurrency Theory"},{"month":"10","citation":{"ista":"Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. 2012. Polynomial-time algorithms for energy games with special weight structures. Algorithms – ESA 2012. ESA: European Symposium on Algorithms, LNCS, vol. 7501, 301–312.","apa":"Chatterjee, K., Henzinger, M. H., Krinninger, S., &#38; Nanongkai, D. (2012). Polynomial-time algorithms for energy games with special weight structures. In <i>Algorithms – ESA 2012</i> (Vol. 7501, pp. 301–312). Ljubljana, Slovenia: Springer. <a href=\"https://doi.org/10.1007/978-3-642-33090-2_27\">https://doi.org/10.1007/978-3-642-33090-2_27</a>","ama":"Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. Polynomial-time algorithms for energy games with special weight structures. In: <i>Algorithms – ESA 2012</i>. Vol 7501. Springer; 2012:301-312. doi:<a href=\"https://doi.org/10.1007/978-3-642-33090-2_27\">10.1007/978-3-642-33090-2_27</a>","ieee":"K. Chatterjee, M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Polynomial-time algorithms for energy games with special weight structures,” in <i>Algorithms – ESA 2012</i>, Ljubljana, Slovenia, 2012, vol. 7501, pp. 301–312.","short":"K. Chatterjee, M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, Algorithms – ESA 2012, Springer, 2012, pp. 301–312.","mla":"Chatterjee, Krishnendu, et al. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” <i>Algorithms – ESA 2012</i>, vol. 7501, Springer, 2012, pp. 301–12, doi:<a href=\"https://doi.org/10.1007/978-3-642-33090-2_27\">10.1007/978-3-642-33090-2_27</a>.","chicago":"Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” In <i>Algorithms – ESA 2012</i>, 7501:301–12. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-33090-2_27\">https://doi.org/10.1007/978-3-642-33090-2_27</a>."},"acknowledgement":"Supported by the Austrian Science Fund (FWF): P23499-N23, the Austrian Science Fund (FWF): S11407-N23 (RiSE), an ERC Start Grant (279307: Graph Games), and a Microsoft Faculty Fellows Award","department":[{"_id":"KrCh"}],"date_created":"2022-03-21T08:01:45Z","date_updated":"2023-09-05T14:09:30Z","intvolume":"      7501","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1604.08234"}],"volume":7501,"doi":"10.1007/978-3-642-33090-2_27","project":[{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407","call_identifier":"FWF"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"conference":{"end_date":"2012-09-12","name":"ESA: European Symposium on Algorithms","location":"Ljubljana, Slovenia","start_date":"2012-09-10"},"_id":"10905","day":"01","title":"Polynomial-time algorithms for energy games with special weight structures","date_published":"2012-10-01T00:00:00Z","publication":"Algorithms – ESA 2012","arxiv":1,"alternative_title":["LNCS"],"quality_controlled":"1","type":"conference","scopus_import":"1","publication_status":"published","publisher":"Springer","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Sebastian","last_name":"Krinninger","full_name":"Krinninger, Sebastian"},{"full_name":"Nanongkai, Danupon","last_name":"Nanongkai","first_name":"Danupon"}],"page":"301-312","related_material":{"record":[{"id":"535","status":"public","relation":"later_version"}]},"oa_version":"Preprint","status":"public","ec_funded":1,"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783642330896"],"eisbn":["9783642330902"]},"year":"2012","oa":1,"language":[{"iso":"eng"}],"external_id":{"arxiv":["1604.08234"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","abstract":[{"lang":"eng","text":"Energy games belong to a class of turn-based two-player infinite-duration games played on a weighted directed graph. It is one of the rare and intriguing combinatorial problems that lie in NP ∩ co−NP, but are not known to be in P. While the existence of polynomial-time algorithms has been a major open problem for decades, there is no algorithm that solves any non-trivial subclass in polynomial time.\r\nIn this paper, we give several results based on the weight structures of the graph. First, we identify a notion of penalty and present a polynomial-time algorithm when the penalty is large. Our algorithm is the first polynomial-time algorithm on a large class of weighted graphs. It includes several counter examples that show that many previous algorithms, such as value iteration and random facet algorithms, require at least sub-exponential time. Our main technique is developing the first non-trivial approximation algorithm and showing how to convert it to an exact algorithm. Moreover, we show that in a practical case in verification where weights are clustered around a constant number of values, the energy game problem can be solved in polynomial time. We also show that the problem is still as hard as in general when the clique-width is bounded or the graph is strongly ergodic, suggesting that restricting graph structures need not help."}]},{"alternative_title":["LNCS"],"publisher":"Springer","type":"conference","quality_controlled":"1","scopus_import":"1","publication_status":"published","publication":"Tools and Algorithms for the Construction and Analysis of Systems","day":"01","date_published":"2012-04-01T00:00:00Z","title":"HSF(C): A software verifier based on Horn clauses","doi":"10.1007/978-3-642-28756-5_46","volume":7214,"main_file_link":[{"url":"https://doi.org/10.1007/978-3-642-28756-5_46","open_access":"1"}],"conference":{"location":"Tallinn, Estonia","start_date":"2012-03-24","name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","end_date":"2012-04-01"},"_id":"10906","citation":{"ista":"Grebenshchikov S, Gupta A, Lopes NP, Popeea C, Rybalchenko A. 2012. HSF(C): A software verifier based on Horn clauses. Tools and Algorithms for the Construction and Analysis of Systems. TACAS: Tools and Algorithms for the Construction and Analysis of SystemsLNCS, LNCS, vol. 7214, 549–551.","apa":"Grebenshchikov, S., Gupta, A., Lopes, N. P., Popeea, C., &#38; Rybalchenko, A. (2012). HSF(C): A software verifier based on Horn clauses. In C. Flanagan &#38; B. König (Eds.), <i>Tools and Algorithms for the Construction and Analysis of Systems</i> (Vol. 7214, pp. 549–551). Berlin, Heidelberg: Springer. <a href=\"https://doi.org/10.1007/978-3-642-28756-5_46\">https://doi.org/10.1007/978-3-642-28756-5_46</a>","ama":"Grebenshchikov S, Gupta A, Lopes NP, Popeea C, Rybalchenko A. HSF(C): A software verifier based on Horn clauses. In: Flanagan C, König B, eds. <i>Tools and Algorithms for the Construction and Analysis of Systems</i>. Vol 7214. LNCS. Berlin, Heidelberg: Springer; 2012:549-551. doi:<a href=\"https://doi.org/10.1007/978-3-642-28756-5_46\">10.1007/978-3-642-28756-5_46</a>","ieee":"S. Grebenshchikov, A. Gupta, N. P. Lopes, C. Popeea, and A. Rybalchenko, “HSF(C): A software verifier based on Horn clauses,” in <i>Tools and Algorithms for the Construction and Analysis of Systems</i>, Tallinn, Estonia, 2012, vol. 7214, pp. 549–551.","short":"S. Grebenshchikov, A. Gupta, N.P. Lopes, C. Popeea, A. Rybalchenko, in:, C. Flanagan, B. König (Eds.), Tools and Algorithms for the Construction and Analysis of Systems, Springer, Berlin, Heidelberg, 2012, pp. 549–551.","mla":"Grebenshchikov, Sergey, et al. “HSF(C): A Software Verifier Based on Horn Clauses.” <i>Tools and Algorithms for the Construction and Analysis of Systems</i>, edited by Cormac Flanagan and Barbara König, vol. 7214, Springer, 2012, pp. 549–51, doi:<a href=\"https://doi.org/10.1007/978-3-642-28756-5_46\">10.1007/978-3-642-28756-5_46</a>.","chicago":"Grebenshchikov, Sergey, Ashutosh Gupta, Nuno P. Lopes, Corneliu Popeea, and Andrey Rybalchenko. “HSF(C): A Software Verifier Based on Horn Clauses.” In <i>Tools and Algorithms for the Construction and Analysis of Systems</i>, edited by Cormac Flanagan and Barbara König, 7214:549–51. LNCS. Berlin, Heidelberg: Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-28756-5_46\">https://doi.org/10.1007/978-3-642-28756-5_46</a>."},"month":"04","intvolume":"      7214","department":[{"_id":"ToHe"}],"date_created":"2022-03-21T08:03:30Z","date_updated":"2023-09-05T14:09:54Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","abstract":[{"text":"HSF(C) is a tool that automates verification of safety and liveness properties for C programs. This paper describes the verification approach taken by HSF(C) and provides instructions on how to install and use the tool.","lang":"eng"}],"oa":1,"place":"Berlin, Heidelberg","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783642287558"],"eisbn":["9783642287565"]},"year":"2012","editor":[{"last_name":"Flanagan","full_name":"Flanagan, Cormac","first_name":"Cormac"},{"full_name":"König, Barbara","last_name":"König","first_name":"Barbara"}],"author":[{"first_name":"Sergey","full_name":"Grebenshchikov, Sergey","last_name":"Grebenshchikov"},{"full_name":"Gupta, Ashutosh","last_name":"Gupta","id":"335E5684-F248-11E8-B48F-1D18A9856A87","first_name":"Ashutosh"},{"full_name":"Lopes, Nuno P.","last_name":"Lopes","first_name":"Nuno P."},{"last_name":"Popeea","full_name":"Popeea, Corneliu","first_name":"Corneliu"},{"first_name":"Andrey","full_name":"Rybalchenko, Andrey","last_name":"Rybalchenko"}],"page":"549-551","status":"public","series_title":"LNCS","oa_version":"Published Version"},{"oa":1,"ddc":["000","005"],"language":[{"iso":"eng"}],"day":"16","title":"Energy and mean-payoff parity Markov decision processes","date_published":"2011-02-16T00:00:00Z","file_date_updated":"2020-07-14T12:46:41Z","has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","abstract":[{"text":"We consider Markov Decision Processes (MDPs) with mean-payoff parity and energy parity objectives. In system design, the parity objective is used to encode ω-regular specifications, and the mean-payoff and energy objectives can be used to model quantitative resource constraints. The energy condition re- quires that the resource level never drops below 0, and the mean-payoff condi- tion requires that the limit-average value of the resource consumption is within a threshold. While these two (energy and mean-payoff) classical conditions are equivalent for two-player games, we show that they differ for MDPs. We show that the problem of deciding whether a state is almost-sure winning (i.e., winning with probability 1) in energy parity MDPs is in NP ∩ coNP, while for mean- payoff parity MDPs, the problem is solvable in polynomial time, improving a recent PSPACE bound.","lang":"eng"}],"type":"technical_report","publication_status":"published","citation":{"chicago":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Energy and Mean-Payoff Parity Markov Decision Processes</i>. IST Austria, 2011. <a href=\"https://doi.org/10.15479/AT:IST-2011-0001\">https://doi.org/10.15479/AT:IST-2011-0001</a>.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Energy and Mean-Payoff Parity Markov Decision Processes</i>. IST Austria, 2011, doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0001\">10.15479/AT:IST-2011-0001</a>.","short":"K. Chatterjee, L. Doyen, Energy and Mean-Payoff Parity Markov Decision Processes, IST Austria, 2011.","ieee":"K. Chatterjee and L. Doyen, <i>Energy and mean-payoff parity Markov decision processes</i>. IST Austria, 2011.","ama":"Chatterjee K, Doyen L. <i>Energy and Mean-Payoff Parity Markov Decision Processes</i>. IST Austria; 2011. doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0001\">10.15479/AT:IST-2011-0001</a>","apa":"Chatterjee, K., &#38; Doyen, L. (2011). <i>Energy and mean-payoff parity Markov decision processes</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2011-0001\">https://doi.org/10.15479/AT:IST-2011-0001</a>","ista":"Chatterjee K, Doyen L. 2011. Energy and mean-payoff parity Markov decision processes, IST Austria, 20p."},"related_material":{"record":[{"id":"3345","relation":"later_version","status":"public"}]},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"}],"page":"20","month":"02","status":"public","oa_version":"Published Version","department":[{"_id":"KrCh"}],"date_created":"2018-12-12T11:39:02Z","date_updated":"2023-02-23T11:23:11Z","doi":"10.15479/AT:IST-2011-0001","publication_identifier":{"issn":["2664-1690"]},"file":[{"creator":"system","file_name":"IST-2011-0001_IST-2011-0001.pdf","file_size":329976,"checksum":"824d6c70e6d3feb3e836b009e0b3cf73","file_id":"5458","date_updated":"2020-07-14T12:46:41Z","access_level":"open_access","date_created":"2018-12-12T11:52:57Z","relation":"main_file","content_type":"application/pdf"}],"year":"2011","_id":"5387","pubrep_id":"23"},{"issue":"10","_id":"6496","volume":101,"main_file_link":[{"open_access":"1","url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3218319/"}],"doi":"10.1016/j.bpj.2011.09.040","department":[{"_id":"CaGu"}],"date_updated":"2021-04-16T11:54:49Z","date_created":"2019-05-28T11:54:29Z","intvolume":"       101","month":"11","citation":{"chicago":"Park, Heungwon, Panos Oikonomou, Calin C Guet, and Philippe Cluzel. “Noise Underlies Switching Behavior of the Bacterial Flagellum.” <i>Biophysical Journal</i>. Elsevier, 2011. <a href=\"https://doi.org/10.1016/j.bpj.2011.09.040\">https://doi.org/10.1016/j.bpj.2011.09.040</a>.","ieee":"H. Park, P. Oikonomou, C. C. Guet, and P. Cluzel, “Noise underlies switching behavior of the bacterial flagellum,” <i>Biophysical Journal</i>, vol. 101, no. 10. Elsevier, pp. 2336–2340, 2011.","short":"H. Park, P. Oikonomou, C.C. Guet, P. Cluzel, Biophysical Journal 101 (2011) 2336–2340.","mla":"Park, Heungwon, et al. “Noise Underlies Switching Behavior of the Bacterial Flagellum.” <i>Biophysical Journal</i>, vol. 101, no. 10, Elsevier, 2011, pp. 2336–40, doi:<a href=\"https://doi.org/10.1016/j.bpj.2011.09.040\">10.1016/j.bpj.2011.09.040</a>.","apa":"Park, H., Oikonomou, P., Guet, C. C., &#38; Cluzel, P. (2011). Noise underlies switching behavior of the bacterial flagellum. <i>Biophysical Journal</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.bpj.2011.09.040\">https://doi.org/10.1016/j.bpj.2011.09.040</a>","ama":"Park H, Oikonomou P, Guet CC, Cluzel P. Noise underlies switching behavior of the bacterial flagellum. <i>Biophysical Journal</i>. 2011;101(10):2336-2340. doi:<a href=\"https://doi.org/10.1016/j.bpj.2011.09.040\">10.1016/j.bpj.2011.09.040</a>","ista":"Park H, Oikonomou P, Guet CC, Cluzel P. 2011. Noise underlies switching behavior of the bacterial flagellum. Biophysical Journal. 101(10), 2336–2340."},"quality_controlled":"1","publication_status":"published","scopus_import":"1","type":"journal_article","publisher":"Elsevier","day":"16","title":"Noise underlies switching behavior of the bacterial flagellum","date_published":"2011-11-16T00:00:00Z","publication":"Biophysical Journal","year":"2011","publication_identifier":{"issn":["0006-3495"]},"oa_version":"Published Version","status":"public","author":[{"first_name":"Heungwon","last_name":"Park","full_name":"Park, Heungwon"},{"first_name":"Panos","full_name":"Oikonomou, Panos","last_name":"Oikonomou"},{"id":"47F8433E-F248-11E8-B48F-1D18A9856A87","first_name":"Calin C","last_name":"Guet","full_name":"Guet, Calin C","orcid":"0000-0001-6220-2052"},{"last_name":"Cluzel","full_name":"Cluzel, Philippe","first_name":"Philippe"}],"page":"2336-2340","external_id":{"pmid":["22098731"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","abstract":[{"lang":"eng","text":"We report the switching behavior of the full bacterial flagellum system that includes the filament and the motor in wild-type Escherichia coli cells. In sorting the motor behavior by the clockwise bias, we find that the distributions of the clockwise (CW) and counterclockwise (CCW) intervals are either exponential or nonexponential with long tails. At low bias, CW intervals are exponentially distributed and CCW intervals exhibit long tails. At intermediate CW bias (0.5) both CW and CCW intervals are mainly exponentially distributed. A simple model suggests that these two distinct switching behaviors are governed by the presence of signaling noise within the chemotaxis network. Low noise yields exponentially distributed intervals, whereas large noise yields nonexponential behavior with long tails. These drastically different motor statistics may play a role in optimizing bacterial behavior for a wide range of environmental conditions."}],"pmid":1,"language":[{"iso":"eng"}],"oa":1},{"abstract":[{"text":"In this paper, we establish a correspondence between the incremental algorithm for computing AT-models [8,9] and the one for computing persistent homology [6,14,15]. We also present a decremental algorithm for computing AT-models that allows to extend the persistence computation to a wider setting. Finally, we show how to combine incremental and decremental techniques for persistent homology computation.","lang":"eng"}],"article_processing_charge":"No","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","oa":1,"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9783642236716"],"issn":["03029743"],"eissn":["16113349"]},"year":"2011","page":"286-293","author":[{"first_name":"Rocio","last_name":"Gonzalez-Diaz","full_name":"Gonzalez-Diaz, Rocio"},{"last_name":"Ion","full_name":"Ion, Adrian","first_name":"Adrian","id":"29F89302-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Jimenez","full_name":"Jimenez, Maria Jose","first_name":"Maria Jose"},{"first_name":"Regina","last_name":"Poyatos","full_name":"Poyatos, Regina"}],"status":"public","oa_version":"Published Version","alternative_title":["LNCS"],"publisher":"Springer Nature","publication_status":"published","scopus_import":"1","type":"conference","quality_controlled":"1","publication":"Computer Analysis of Images and Patterns","date_published":"2011-08-01T00:00:00Z","title":"Incremental-decremental algorithm for computing AT-models and persistent homology","day":"01","doi":"10.1007/978-3-642-23672-3_35","main_file_link":[{"open_access":"1","url":"http://hdl.handle.net/11441/30766"}],"volume":6854,"_id":"9648","conference":{"name":"CAIP: International Conference on Computer Analysis of Images and Patterns","end_date":"2011-08-31","start_date":"2011-08-29","location":"Seville, Spain"},"citation":{"apa":"Gonzalez-Diaz, R., Ion, A., Jimenez, M. J., &#38; Poyatos, R. (2011). Incremental-decremental algorithm for computing AT-models and persistent homology. In <i>Computer Analysis of Images and Patterns</i> (Vol. 6854, pp. 286–293). Seville, Spain: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-642-23672-3_35\">https://doi.org/10.1007/978-3-642-23672-3_35</a>","ama":"Gonzalez-Diaz R, Ion A, Jimenez MJ, Poyatos R. Incremental-decremental algorithm for computing AT-models and persistent homology. In: <i>Computer Analysis of Images and Patterns</i>. Vol 6854. Springer Nature; 2011:286-293. doi:<a href=\"https://doi.org/10.1007/978-3-642-23672-3_35\">10.1007/978-3-642-23672-3_35</a>","ista":"Gonzalez-Diaz R, Ion A, Jimenez MJ, Poyatos R. 2011. Incremental-decremental algorithm for computing AT-models and persistent homology. Computer Analysis of Images and Patterns. CAIP: International Conference on Computer Analysis of Images and Patterns, LNCS, vol. 6854, 286–293.","chicago":"Gonzalez-Diaz, Rocio, Adrian Ion, Maria Jose Jimenez, and Regina Poyatos. “Incremental-Decremental Algorithm for Computing AT-Models and Persistent Homology.” In <i>Computer Analysis of Images and Patterns</i>, 6854:286–93. Springer Nature, 2011. <a href=\"https://doi.org/10.1007/978-3-642-23672-3_35\">https://doi.org/10.1007/978-3-642-23672-3_35</a>.","ieee":"R. Gonzalez-Diaz, A. Ion, M. J. Jimenez, and R. Poyatos, “Incremental-decremental algorithm for computing AT-models and persistent homology,” in <i>Computer Analysis of Images and Patterns</i>, Seville, Spain, 2011, vol. 6854, pp. 286–293.","short":"R. Gonzalez-Diaz, A. Ion, M.J. Jimenez, R. Poyatos, in:, Computer Analysis of Images and Patterns, Springer Nature, 2011, pp. 286–293.","mla":"Gonzalez-Diaz, Rocio, et al. “Incremental-Decremental Algorithm for Computing AT-Models and Persistent Homology.” <i>Computer Analysis of Images and Patterns</i>, vol. 6854, Springer Nature, 2011, pp. 286–93, doi:<a href=\"https://doi.org/10.1007/978-3-642-23672-3_35\">10.1007/978-3-642-23672-3_35</a>."},"month":"08","intvolume":"      6854","date_created":"2021-07-11T22:01:19Z","date_updated":"2021-08-12T13:53:17Z","department":[{"_id":"HeEd"}]},{"year":"2011","_id":"9762","doi":"10.5061/dryad.299h8","main_file_link":[{"url":"https://doi.org/10.5061/dryad.299h8","open_access":"1"}],"status":"public","department":[{"_id":"NiBa"}],"oa_version":"Published Version","date_created":"2021-08-02T07:11:19Z","date_updated":"2023-02-23T11:25:25Z","citation":{"ama":"Palero F, Abello P, Macpherson E, Beaumont M, Pascual M. Data from: Effect of oceanographic barriers and overfishing on the population genetic structure of the European spiny lobster (Palinurus elephas). 2011. doi:<a href=\"https://doi.org/10.5061/dryad.299h8\">10.5061/dryad.299h8</a>","apa":"Palero, F., Abello, P., Macpherson, E., Beaumont, M., &#38; Pascual, M. (2011). Data from: Effect of oceanographic barriers and overfishing on the population genetic structure of the European spiny lobster (Palinurus elephas). IST Austria. <a href=\"https://doi.org/10.5061/dryad.299h8\">https://doi.org/10.5061/dryad.299h8</a>","ista":"Palero F, Abello P, Macpherson E, Beaumont M, Pascual M. 2011. Data from: Effect of oceanographic barriers and overfishing on the population genetic structure of the European spiny lobster (Palinurus elephas), IST Austria, <a href=\"https://doi.org/10.5061/dryad.299h8\">10.5061/dryad.299h8</a>.","chicago":"Palero, Ferran, Pere Abello, Enrique Macpherson, Mark Beaumont, and Marta Pascual. “Data from: Effect of Oceanographic Barriers and Overfishing on the Population Genetic Structure of the European Spiny Lobster (Palinurus Elephas).” IST Austria, 2011. <a href=\"https://doi.org/10.5061/dryad.299h8\">https://doi.org/10.5061/dryad.299h8</a>.","mla":"Palero, Ferran, et al. <i>Data from: Effect of Oceanographic Barriers and Overfishing on the Population Genetic Structure of the European Spiny Lobster (Palinurus Elephas)</i>. IST Austria, 2011, doi:<a href=\"https://doi.org/10.5061/dryad.299h8\">10.5061/dryad.299h8</a>.","short":"F. Palero, P. Abello, E. Macpherson, M. Beaumont, M. Pascual, (2011).","ieee":"F. Palero, P. Abello, E. Macpherson, M. Beaumont, and M. Pascual, “Data from: Effect of oceanographic barriers and overfishing on the population genetic structure of the European spiny lobster (Palinurus elephas).” IST Austria, 2011."},"related_material":{"record":[{"relation":"used_in_publication","status":"public","id":"3395"}]},"author":[{"id":"3F0E2A22-F248-11E8-B48F-1D18A9856A87","first_name":"Ferran","orcid":"0000-0002-0343-8329","last_name":"Palero","full_name":"Palero, Ferran"},{"first_name":"Pere","full_name":"Abello, Pere","last_name":"Abello"},{"last_name":"Macpherson","full_name":"Macpherson, Enrique","first_name":"Enrique"},{"last_name":"Beaumont","full_name":"Beaumont, Mark","first_name":"Mark"},{"first_name":"Marta","last_name":"Pascual","full_name":"Pascual, Marta"}],"month":"05","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","publisher":"IST Austria","abstract":[{"text":"Defining population structure and genetic diversity levels is of the utmost importance for developing efficient conservation strategies. Overfishing has caused mean annual catches of the European spiny lobster (Palinurus elephas) to decrease alarmingly along its distribution area. In this context, there is a need for comprehensive studies to evaluate the genetic health of the exploited populations. The present work is based on a set of 10 nuclear markers amplified in 331 individuals from 10 different localities covering most of P. elephas distribution area. Samples from Atlantic and Mediterranean basins showed small but significant differences, indicating that P. elephas populations do not behave as a single panmictic unit but form two partially-overlapping groups. Despite intense overfishing, our dataset did not recover a recent bottleneck signal, and showed a large and stable historical effective size instead. This result could be accounted for by specific life history traits (reproduction and longevity) and the limitations of molecular markers in covering very recent timescales for non temporal samples. Our study emphasizes the necessity of integrating information on effective population sizes and life history parameters when evaluating population connectivity levels from genetic data.","lang":"eng"}],"article_processing_charge":"No","type":"research_data_reference","day":"12","title":"Data from: Effect of oceanographic barriers and overfishing on the population genetic structure of the European spiny lobster (Palinurus elephas)","date_published":"2011-05-12T00:00:00Z","oa":1},{"publisher":"Nature Publishing Group","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"Parvalbumin is thought to act in a manner similar to EGTA, but how a slow Ca2+ buffer affects nanodomain-coupling regimes at GABAergic synapses is unclear. Direct measurements of parvalbumin concentration and paired recordings in rodent hippocampus and cerebellum revealed that parvalbumin affects synaptic dynamics only when expressed at high levels. Modeling suggests that, in high concentrations, parvalbumin may exert BAPTA-like effects, modulating nanodomain coupling via competition with local saturation of endogenous fixed buffers."}],"publication_status":"published","quality_controlled":"1","scopus_import":1,"type":"journal_article","publication":"Nature Neuroscience","language":[{"iso":"eng"}],"day":"04","date_published":"2011-12-04T00:00:00Z","title":"How the “slow” Ca(2+) buffer parvalbumin affects transmitter release in nanodomain coupling regimes at GABAergic synapses","oa":1,"_id":"3318","year":"2011","doi":"10.1038/nn.3002","main_file_link":[{"open_access":"1","url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3631701/"}],"volume":15,"intvolume":"        15","status":"public","department":[{"_id":"PeJo"}],"publist_id":"3321","oa_version":"Submitted Version","date_created":"2018-12-11T12:02:38Z","date_updated":"2021-01-12T07:42:37Z","citation":{"apa":"Eggermann, E., &#38; Jonas, P. M. (2011). How the “slow” Ca(2+) buffer parvalbumin affects transmitter release in nanodomain coupling regimes at GABAergic synapses. <i>Nature Neuroscience</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/nn.3002\">https://doi.org/10.1038/nn.3002</a>","ama":"Eggermann E, Jonas PM. How the “slow” Ca(2+) buffer parvalbumin affects transmitter release in nanodomain coupling regimes at GABAergic synapses. <i>Nature Neuroscience</i>. 2011;15:20-22. doi:<a href=\"https://doi.org/10.1038/nn.3002\">10.1038/nn.3002</a>","ista":"Eggermann E, Jonas PM. 2011. How the “slow” Ca(2+) buffer parvalbumin affects transmitter release in nanodomain coupling regimes at GABAergic synapses. Nature Neuroscience. 15, 20–22.","chicago":"Eggermann, Emmanuel, and Peter M Jonas. “How the ‘Slow’ Ca(2+) Buffer Parvalbumin Affects Transmitter Release in Nanodomain Coupling Regimes at GABAergic Synapses.” <i>Nature Neuroscience</i>. Nature Publishing Group, 2011. <a href=\"https://doi.org/10.1038/nn.3002\">https://doi.org/10.1038/nn.3002</a>.","ieee":"E. Eggermann and P. M. Jonas, “How the ‘slow’ Ca(2+) buffer parvalbumin affects transmitter release in nanodomain coupling regimes at GABAergic synapses,” <i>Nature Neuroscience</i>, vol. 15. Nature Publishing Group, pp. 20–22, 2011.","short":"E. Eggermann, P.M. Jonas, Nature Neuroscience 15 (2011) 20–22.","mla":"Eggermann, Emmanuel, and Peter M. Jonas. “How the ‘Slow’ Ca(2+) Buffer Parvalbumin Affects Transmitter Release in Nanodomain Coupling Regimes at GABAergic Synapses.” <i>Nature Neuroscience</i>, vol. 15, Nature Publishing Group, 2011, pp. 20–22, doi:<a href=\"https://doi.org/10.1038/nn.3002\">10.1038/nn.3002</a>."},"author":[{"first_name":"Emmanuel","full_name":"Eggermann, Emmanuel","last_name":"Eggermann"},{"orcid":"0000-0001-5001-4804","last_name":"Jonas","full_name":"Jonas, Peter M","id":"353C1B58-F248-11E8-B48F-1D18A9856A87","first_name":"Peter M"}],"month":"12","page":"20 - 22"},{"publication_status":"published","type":"conference","scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"ML Research Press","article_processing_charge":"No","abstract":[{"text":"We address the problem of metric learning for multi-view data, namely the construction of embedding projections from data in different representations into a shared feature space, such that the Euclidean distance in this space provides a meaningful within-view as well as between-view similarity. Our motivation stems from the problem of cross-media retrieval tasks, where the availability of a joint Euclidean distance function is a pre-requisite to allow fast, in particular hashing-based, nearest neighbor queries. We formulate an objective function that expresses the intuitive concept that matching samples are mapped closely together in the output space, whereas non-matching samples are pushed apart, no matter in which view they are available. The resulting optimization problem is not convex, but it can be decomposed explicitly into a convex and a concave part, thereby allowing efficient optimization using the convex-concave procedure. Experiments on an image retrieval task show that nearest-neighbor based cross-view retrieval is indeed possible, and the proposed technique improves the retrieval accuracy over baseline techniques.","lang":"eng"}],"day":"01","date_published":"2011-01-01T00:00:00Z","title":"Learning multi-view neighborhood preserving projections","language":[{"iso":"eng"}],"conference":{"start_date":"2011-06-28","location":"Bellevue, United States","end_date":"2011-07-02","name":"ICML: International Conference on Machine Learning"},"_id":"3319","year":"2011","oa_version":"None","department":[{"_id":"ChLa"}],"publist_id":"3316","date_updated":"2023-10-17T11:59:50Z","date_created":"2018-12-11T12:02:39Z","status":"public","author":[{"full_name":"Quadrianto, Novi","last_name":"Quadrianto","first_name":"Novi"},{"first_name":"Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","last_name":"Lampert","full_name":"Lampert, Christoph","orcid":"0000-0001-8622-7887"}],"page":"425 - 432","month":"01","citation":{"apa":"Quadrianto, N., &#38; Lampert, C. (2011). Learning multi-view neighborhood preserving projections (pp. 425–432). Presented at the ICML: International Conference on Machine Learning, Bellevue, United States: ML Research Press.","ama":"Quadrianto N, Lampert C. Learning multi-view neighborhood preserving projections. In: ML Research Press; 2011:425-432.","ista":"Quadrianto N, Lampert C. 2011. Learning multi-view neighborhood preserving projections. ICML: International Conference on Machine Learning, 425–432.","chicago":"Quadrianto, Novi, and Christoph Lampert. “Learning Multi-View Neighborhood Preserving Projections,” 425–32. ML Research Press, 2011.","ieee":"N. Quadrianto and C. Lampert, “Learning multi-view neighborhood preserving projections,” presented at the ICML: International Conference on Machine Learning, Bellevue, United States, 2011, pp. 425–432.","mla":"Quadrianto, Novi, and Christoph Lampert. <i>Learning Multi-View Neighborhood Preserving Projections</i>. ML Research Press, 2011, pp. 425–32.","short":"N. Quadrianto, C. Lampert, in:, ML Research Press, 2011, pp. 425–432."}},{"_id":"3320","issue":"3-4","doi":"10.1561/0600000033","file":[{"date_updated":"2020-07-14T12:46:07Z","relation":"main_file","date_created":"2020-05-14T14:34:47Z","access_level":"open_access","file_id":"7837","checksum":"f1043ef389f1558e2a226bb51568511f","content_type":"application/pdf","creator":"dernst","file_size":3745064,"file_name":"2011_CompGraphicsVision_Nowozin.pdf"}],"volume":6,"intvolume":"         6","department":[{"_id":"ChLa"}],"publist_id":"3315","date_updated":"2023-10-17T11:52:46Z","date_created":"2018-12-11T12:02:39Z","citation":{"ama":"Nowozin S, Lampert C. Structured learning and prediction in computer vision. <i>Foundations and Trends in Computer Graphics and Vision</i>. 2011;6(3-4):185-365. doi:<a href=\"https://doi.org/10.1561/0600000033\">10.1561/0600000033</a>","apa":"Nowozin, S., &#38; Lampert, C. (2011). Structured learning and prediction in computer vision. <i>Foundations and Trends in Computer Graphics and Vision</i>. Now Publishers. <a href=\"https://doi.org/10.1561/0600000033\">https://doi.org/10.1561/0600000033</a>","ista":"Nowozin S, Lampert C. 2011. Structured learning and prediction in computer vision. Foundations and Trends in Computer Graphics and Vision. 6(3–4), 185–365.","chicago":"Nowozin, Sebastian, and Christoph Lampert. “Structured Learning and Prediction in Computer Vision.” <i>Foundations and Trends in Computer Graphics and Vision</i>. Now Publishers, 2011. <a href=\"https://doi.org/10.1561/0600000033\">https://doi.org/10.1561/0600000033</a>.","short":"S. Nowozin, C. Lampert, Foundations and Trends in Computer Graphics and Vision 6 (2011) 185–365.","mla":"Nowozin, Sebastian, and Christoph Lampert. “Structured Learning and Prediction in Computer Vision.” <i>Foundations and Trends in Computer Graphics and Vision</i>, vol. 6, no. 3–4, Now Publishers, 2011, pp. 185–365, doi:<a href=\"https://doi.org/10.1561/0600000033\">10.1561/0600000033</a>.","ieee":"S. Nowozin and C. Lampert, “Structured learning and prediction in computer vision,” <i>Foundations and Trends in Computer Graphics and Vision</i>, vol. 6, no. 3–4. Now Publishers, pp. 185–365, 2011."},"article_type":"original","month":"05","publisher":"Now Publishers","scopus_import":"1","type":"journal_article","publication_status":"published","quality_controlled":"1","has_accepted_license":"1","publication":"Foundations and Trends in Computer Graphics and Vision","day":"23","date_published":"2011-05-23T00:00:00Z","title":"Structured learning and prediction in computer vision","year":"2011","status":"public","oa_version":"Published Version","author":[{"first_name":"Sebastian","full_name":"Nowozin, Sebastian","last_name":"Nowozin"},{"orcid":"0000-0001-8622-7887","last_name":"Lampert","full_name":"Lampert, Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","first_name":"Christoph"}],"page":"185 - 365","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"Powerful statistical models that can be learned efficiently from large amounts of data are currently revolutionizing computer vision. These models possess a rich internal structure reflecting task-specific relations and constraints. This monograph introduces the reader to the most popular classes of structured models in computer vision. Our focus is discrete undirected graphical models which we cover in detail together with a description of algorithms for both probabilistic inference and maximum a posteriori inference. We discuss separately recently successful techniques for prediction in general structured models. In the second part of this monograph we describe methods for parameter learning where we distinguish the classic maximum likelihood based methods from the more recent prediction-based parameter learning methods. We highlight developments to enhance current models and discuss kernelized models and latent variable models. To make the monograph more practical and to provide links to further study we provide examples of successful application of many methods in the computer vision literature.","lang":"eng"}],"article_processing_charge":"No","file_date_updated":"2020-07-14T12:46:07Z","language":[{"iso":"eng"}],"oa":1,"ddc":["000"]},{"status":"public","date_created":"2018-12-11T12:02:40Z","date_updated":"2023-10-17T11:47:36Z","department":[{"_id":"ChLa"}],"publist_id":"3313","oa_version":"None","related_material":{"record":[{"id":"3163","relation":"earlier_version","status":"public"}]},"citation":{"ama":"Lampert C. <i>Maximum Margin Multi Label Structured Prediction</i>. Neural Information Processing Systems Foundation; 2011.","apa":"Lampert, C. (2011). <i>Maximum margin multi label structured prediction</i>. <i>NIPS: Neural Information Processing Systems</i>. Neural Information Processing Systems Foundation.","ista":"Lampert C. 2011. Maximum margin multi label structured prediction, Neural Information Processing Systems Foundation,p.","chicago":"Lampert, Christoph. <i>Maximum Margin Multi Label Structured Prediction</i>. <i>NIPS: Neural Information Processing Systems</i>. Neural Information Processing Systems Foundation, 2011.","short":"C. Lampert, Maximum Margin Multi Label Structured Prediction, Neural Information Processing Systems Foundation, 2011.","mla":"Lampert, Christoph. “Maximum Margin Multi Label Structured Prediction.” <i>NIPS: Neural Information Processing Systems</i>, Neural Information Processing Systems Foundation, 2011.","ieee":"C. Lampert, <i>Maximum margin multi label structured prediction</i>. Neural Information Processing Systems Foundation, 2011."},"month":"12","author":[{"first_name":"Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","full_name":"Lampert, Christoph","last_name":"Lampert","orcid":"0000-0001-8622-7887"}],"_id":"3322","year":"2011","language":[{"iso":"eng"}],"publication":"NIPS: Neural Information Processing Systems","title":"Maximum margin multi label structured prediction","date_published":"2011-12-13T00:00:00Z","day":"13","article_processing_charge":"No","abstract":[{"text":"We study multi-label prediction for structured output spaces, a problem that occurs, for example, in object detection in images, secondary structure prediction in computational biology, and graph matching with symmetries. Conventional multi-label classification techniques are typically not applicable in this situation, because they require explicit enumeration of the label space, which is infeasible in case of structured outputs. Relying on techniques originally designed for single- label structured prediction, in particular structured support vector machines, results in reduced prediction accuracy, or leads to infeasible optimization problems. In this work we derive a maximum-margin training formulation for multi-label structured prediction that remains computationally tractable while achieving high prediction accuracy. It also shares most beneficial properties with single-label maximum-margin approaches, in particular a formulation as a convex optimization problem, efficient working set training, and PAC-Bayesian generalization bounds.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Neural Information Processing Systems Foundation","publication_status":"published","type":"conference_poster"},{"publication_status":"published","type":"conference","scopus_import":1,"quality_controlled":"1","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publisher":"Springer","abstract":[{"text":"We present a new decidable logic called TREX for expressing constraints about imperative tree data structures. In particular, TREX supports a transitive closure operator that can express reachability constraints, which often appear in data structure invariants. We show that our logic is closed under weakest precondition computation, which enables its use for automated software verification. We further show that satisfiability of formulas in TREX is decidable in NP. The low complexity makes it an attractive alternative to more expensive logics such as monadic second-order logic (MSOL) over trees, which have been traditionally used for reasoning about tree data structures.","lang":"eng"}],"alternative_title":["LNAI "],"day":"19","title":"An efficient decision procedure for imperative tree data structures","date_published":"2011-07-19T00:00:00Z","language":[{"iso":"eng"}],"conference":{"location":"Wrocław, Poland","start_date":"2011-07-31","end_date":"2011-08-05","name":"CADE 23: Automated Deduction "},"_id":"3323","year":"2011","volume":6803,"doi":"10.1007/978-3-642-22438-6_36","oa_version":"None","publist_id":"3312","department":[{"_id":"ToHe"}],"date_created":"2018-12-11T12:02:40Z","date_updated":"2023-02-23T12:23:48Z","intvolume":"      6803","status":"public","author":[{"id":"447BFB88-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas","full_name":"Wies, Thomas","last_name":"Wies"},{"first_name":"Marco","last_name":"Muñiz","full_name":"Muñiz, Marco"},{"last_name":"Kuncak","full_name":"Kuncak, Viktor","first_name":"Viktor"}],"page":"476 - 491","month":"07","citation":{"chicago":"Wies, Thomas, Marco Muñiz, and Viktor Kuncak. “An Efficient Decision Procedure for Imperative Tree Data Structures,” 6803:476–91. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-22438-6_36\">https://doi.org/10.1007/978-3-642-22438-6_36</a>.","short":"T. Wies, M. Muñiz, V. Kuncak, in:, Springer, 2011, pp. 476–491.","mla":"Wies, Thomas, et al. <i>An Efficient Decision Procedure for Imperative Tree Data Structures</i>. Vol. 6803, Springer, 2011, pp. 476–91, doi:<a href=\"https://doi.org/10.1007/978-3-642-22438-6_36\">10.1007/978-3-642-22438-6_36</a>.","ieee":"T. Wies, M. Muñiz, and V. Kuncak, “An efficient decision procedure for imperative tree data structures,” presented at the CADE 23: Automated Deduction , Wrocław, Poland, 2011, vol. 6803, pp. 476–491.","ama":"Wies T, Muñiz M, Kuncak V. An efficient decision procedure for imperative tree data structures. In: Vol 6803. Springer; 2011:476-491. doi:<a href=\"https://doi.org/10.1007/978-3-642-22438-6_36\">10.1007/978-3-642-22438-6_36</a>","apa":"Wies, T., Muñiz, M., &#38; Kuncak, V. (2011). An efficient decision procedure for imperative tree data structures (Vol. 6803, pp. 476–491). Presented at the CADE 23: Automated Deduction , Wrocław, Poland: Springer. <a href=\"https://doi.org/10.1007/978-3-642-22438-6_36\">https://doi.org/10.1007/978-3-642-22438-6_36</a>","ista":"Wies T, Muñiz M, Kuncak V. 2011. An efficient decision procedure for imperative tree data structures. CADE 23: Automated Deduction , LNAI , vol. 6803, 476–491."},"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5383"}]}}]