[{"doi":"10.1007/978-3-642-27660-6_9","fulldoi":"https://doi.org/10.1007/978-3-642-27660-6_9","type":"conference","title":"Cryptography from learning parity with noise","date_published":"2012-02-19T00:00:00Z","abstract":[{"text":"The Learning Parity with Noise (LPN) problem has recently found many applications in cryptography as the hardness assumption underlying the constructions of &quot;provably secure&quot; cryptographic schemes like encryption or authentication protocols. Being provably secure means that the scheme comes with a proof showing that the existence of an efficient adversary against the scheme implies that the underlying hardness assumption is wrong. LPN based schemes are appealing for theoretical and practical reasons. On the theoretical side, LPN based schemes offer a very strong security guarantee. The LPN problem is equivalent to the problem of decoding random linear codes, a problem that has been extensively studied in the last half century. The fastest known algorithms run in exponential time and unlike most number-theoretic problems used in cryptography, the LPN problem does not succumb to known quantum algorithms. On the practical side, LPN based schemes are often extremely simple and efficient in terms of code-size as well as time and space requirements. This makes them prime candidates for light-weight devices like RFID tags, which are too weak to implement standard cryptographic primitives like the AES block-cipher. This talk will be a gentle introduction to provable security using simple LPN based schemes as examples. Starting from pseudorandom generators and symmetric key encryption, over secret-key authentication protocols, and, if time admits, touching on recent constructions of public-key identification, commitments and zero-knowledge proofs.","lang":"eng"}],"author":[{"orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"corr_author":"1","conference":{"location":"Špindlerův Mlýn, Czech Republic","end_date":"2012-01-27","name":"SOFSEM: Current Trends in Theory and Practice of Computer Science","start_date":"2012-01-21"},"date_updated":"2024-10-09T20:54:42Z","alternative_title":["LNCS"],"publist_id":"3407","quality_controlled":"1","intvolume":"      7147","date_created":"2018-12-11T12:02:15Z","year":"2012","citation":{"mla":"Pietrzak, Krzysztof Z. <i>Cryptography from Learning Parity with Noise</i>. Vol. 7147, Springer, 2012, pp. 99–114, doi:<a href=\"https://doi.org/10.1007/978-3-642-27660-6_9\">10.1007/978-3-642-27660-6_9</a>.","short":"K.Z. Pietrzak, in:, Springer, 2012, pp. 99–114.","chicago":"Pietrzak, Krzysztof Z. “Cryptography from Learning Parity with Noise,” 7147:99–114. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-27660-6_9\">https://doi.org/10.1007/978-3-642-27660-6_9</a>.","apa":"Pietrzak, K. Z. (2012). Cryptography from learning parity with noise (Vol. 7147, pp. 99–114). Presented at the SOFSEM: Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic: Springer. <a href=\"https://doi.org/10.1007/978-3-642-27660-6_9\">https://doi.org/10.1007/978-3-642-27660-6_9</a>","ieee":"K. Z. Pietrzak, “Cryptography from learning parity with noise,” presented at the SOFSEM: Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, 2012, vol. 7147, pp. 99–114.","ama":"Pietrzak KZ. Cryptography from learning parity with noise. In: Vol 7147. Springer; 2012:99-114. doi:<a href=\"https://doi.org/10.1007/978-3-642-27660-6_9\">10.1007/978-3-642-27660-6_9</a>","ista":"Pietrzak KZ. 2012. Cryptography from learning parity with noise. SOFSEM: Current Trends in Theory and Practice of Computer Science, LNCS, vol. 7147, 99–114."},"publisher":"Springer","day":"19","month":"02","department":[{"_id":"KrPi"}],"volume":7147,"language":[{"iso":"eng"}],"oa_version":"None","publication_status":"published","_id":"3250","status":"public","page":"99 - 114"},{"alternative_title":["LNCS"],"publist_id":"3406","date_updated":"2026-04-09T14:35:23Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"Many infinite state systems can be seen as well-structured transition systems (WSTS), i.e., systems equipped with a well-quasi-ordering on states that is also a simulation relation. WSTS are an attractive target for formal analysis because there exist generic algorithms that decide interesting verification problems for this class. Among the most popular algorithms are acceleration-based forward analyses for computing the covering set. Termination of these algorithms can only be guaranteed for flattable WSTS. Yet, many WSTS of practical interest are not flattable and the question whether any given WSTS is flattable is itself undecidable. We therefore propose an analysis that computes the covering set and captures the essence of acceleration-based algorithms, but sacrifices precision for guaranteed termination. Our analysis is an abstract interpretation whose abstract domain builds on the ideal completion of the well-quasi-ordered state space, and a widening operator that mimics acceleration and controls the loss of precision of the analysis. We present instances of our framework for various classes of WSTS. Our experience with a prototype implementation indicates that, despite the inherent precision loss, our analysis often computes the precise covering set of the analyzed system."}],"ec_funded":1,"file_date_updated":"2020-07-14T12:46:05Z","date_published":"2012-01-01T00:00:00Z","has_accepted_license":"1","ddc":["000","005"],"fulldoi":"https://doi.org/10.1007/978-3-642-27940-9_29","_id":"3251","status":"public","oa_version":"Submitted Version","day":"01","publisher":"Springer","acknowledgement":"This research was supported in part by the European Research Council (ERC) Advanced Investigator Grant QUAREM and by the Austrian Science Fund (FWF) project S11402-N23.","year":"2012","citation":{"ieee":"D. Zufferey, T. Wies, and T. A. Henzinger, “Ideal abstractions for well structured transition systems,” presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia, PA, USA, 2012, vol. 7148, pp. 445–460.","apa":"Zufferey, D., Wies, T., &#38; Henzinger, T. A. (2012). Ideal abstractions for well structured transition systems (Vol. 7148, pp. 445–460). Presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia, PA, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-642-27940-9_29\">https://doi.org/10.1007/978-3-642-27940-9_29</a>","ama":"Zufferey D, Wies T, Henzinger TA. Ideal abstractions for well structured transition systems. In: Vol 7148. Springer; 2012:445-460. doi:<a href=\"https://doi.org/10.1007/978-3-642-27940-9_29\">10.1007/978-3-642-27940-9_29</a>","ista":"Zufferey D, Wies T, Henzinger TA. 2012. Ideal abstractions for well structured transition systems. VMCAI: Verification, Model Checking and Abstract Interpretation, LNCS, vol. 7148, 445–460.","mla":"Zufferey, Damien, et al. <i>Ideal Abstractions for Well Structured Transition Systems</i>. Vol. 7148, Springer, 2012, pp. 445–60, doi:<a href=\"https://doi.org/10.1007/978-3-642-27940-9_29\">10.1007/978-3-642-27940-9_29</a>.","short":"D. Zufferey, T. Wies, T.A. Henzinger, in:, Springer, 2012, pp. 445–460.","chicago":"Zufferey, Damien, Thomas Wies, and Thomas A Henzinger. “Ideal Abstractions for Well Structured Transition Systems,” 7148:445–60. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-27940-9_29\">https://doi.org/10.1007/978-3-642-27940-9_29</a>."},"intvolume":"      7148","file":[{"checksum":"f2f0d55efa32309ad1fe65a5fcaad90c","access_level":"open_access","relation":"main_file","creator":"system","date_updated":"2020-07-14T12:46:05Z","content_type":"application/pdf","file_id":"4759","date_created":"2018-12-12T10:09:35Z","file_size":217104,"file_name":"IST-2012-100-v1+1_Ideal_abstractions_for_well-structured_transition_systems.pdf"}],"conference":{"start_date":"2012-01-22","name":"VMCAI: Verification, Model Checking and Abstract Interpretation","end_date":"2012-01-24","location":"Philadelphia, PA, USA"},"scopus_import":"1","author":[{"last_name":"Zufferey","id":"4397AC76-F248-11E8-B48F-1D18A9856A87","full_name":"Zufferey, Damien","orcid":"0000-0002-3197-8736","first_name":"Damien"},{"last_name":"Wies","id":"447BFB88-F248-11E8-B48F-1D18A9856A87","full_name":"Wies, Thomas","first_name":"Thomas"},{"first_name":"Thomas A","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"oa":1,"title":"Ideal abstractions for well structured transition systems","type":"conference","doi":"10.1007/978-3-642-27940-9_29","page":"445 - 460","pubrep_id":"100","publication_status":"published","department":[{"_id":"ToHe"}],"language":[{"iso":"eng"}],"volume":7148,"month":"01","date_created":"2018-12-11T12:02:16Z","project":[{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","grant_number":"267989"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"}],"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"1405"}]},"quality_controlled":"1"},{"oa":1,"title":"Synthesizing protocols for digital contract signing","doi":"10.1007/978-3-642-27940-9_11","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1004.2697"}],"type":"conference","author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Raman, Vishwanath","last_name":"Raman","first_name":"Vishwanath"}],"conference":{"start_date":"2012-01-22","location":"Philadelphia, PA, USA","end_date":"2012-01-24","name":"VMCAI: Verification, Model Checking and Abstract Interpretation"},"scopus_import":"1","project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"quality_controlled":"1","date_created":"2018-12-11T12:02:16Z","article_processing_charge":"No","month":"01","page":"152 - 168","department":[{"_id":"KrCh"}],"language":[{"iso":"eng"}],"volume":7148,"publication_status":"published","date_published":"2012-01-20T00:00:00Z","fulldoi":"https://doi.org/10.1007/978-3-642-27940-9_11","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"We study the automatic synthesis of fair non-repudiation protocols, a class of fair exchange protocols, used for digital contract signing. First, we show how to specify the objectives of the participating agents, the trusted third party (TTP) and the protocols as path formulas in Linear Temporal Logic (LTL) and prove that the satisfaction of the objectives of the agents and the TTP imply satisfaction of the protocol objectives. We then show that weak (co-operative) co-synthesis and classical (strictly competitive) co-synthesis fail in synthesizing these protocols, whereas assume-guarantee synthesis (AGS) succeeds. We demonstrate the success of assume-guarantee synthesis as follows: (a) any solution of assume-guarantee synthesis is attack-free; no subset of participants can violate the objectives of the other participants without violating their own objectives; (b) the Asokan-Shoup-Waidner (ASW) certified mail protocol that has known vulnerabilities is not a solution of AGS; and (c) the Kremer-Markowitch (KM) non-repudiation protocol is a solution of AGS. To our knowledge this is the first application of synthesis to fair non-repudiation protocols, and our results show how synthesis can generate correct protocols and automatically discover vulnerabilities. The solution to assume-guarantee synthesis can be computed efficiently as the secure equilibrium solution of three-player graph games. © 2012 Springer-Verlag.","lang":"eng"}],"ec_funded":1,"date_updated":"2025-06-11T08:06:25Z","alternative_title":["LNCS"],"publist_id":"3405","external_id":{"arxiv":["1004.2697"]},"intvolume":"      7148","arxiv":1,"day":"20","acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No P 23499-N23 (Modern Graph Algorithmic Techniques in Formal Verification), FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.\r\nThe authors would like to thank Avik Chaudhuri for his invaluable help and feedback.","year":"2012","citation":{"chicago":"Chatterjee, Krishnendu, and Vishwanath Raman. “Synthesizing Protocols for Digital Contract Signing,” 7148:152–68. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-27940-9_11\">https://doi.org/10.1007/978-3-642-27940-9_11</a>.","short":"K. Chatterjee, V. Raman, in:, Springer, 2012, pp. 152–168.","mla":"Chatterjee, Krishnendu, and Vishwanath Raman. <i>Synthesizing Protocols for Digital Contract Signing</i>. Vol. 7148, Springer, 2012, pp. 152–68, doi:<a href=\"https://doi.org/10.1007/978-3-642-27940-9_11\">10.1007/978-3-642-27940-9_11</a>.","ama":"Chatterjee K, Raman V. Synthesizing protocols for digital contract signing. In: Vol 7148. Springer; 2012:152-168. doi:<a href=\"https://doi.org/10.1007/978-3-642-27940-9_11\">10.1007/978-3-642-27940-9_11</a>","ista":"Chatterjee K, Raman V. 2012. Synthesizing protocols for digital contract signing. VMCAI: Verification, Model Checking and Abstract Interpretation, LNCS, vol. 7148, 152–168.","apa":"Chatterjee, K., &#38; Raman, V. (2012). Synthesizing protocols for digital contract signing (Vol. 7148, pp. 152–168). Presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia, PA, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-642-27940-9_11\">https://doi.org/10.1007/978-3-642-27940-9_11</a>","ieee":"K. Chatterjee and V. Raman, “Synthesizing protocols for digital contract signing,” presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia, PA, USA, 2012, vol. 7148, pp. 152–168."},"publisher":"Springer","status":"public","_id":"3252","oa_version":"Preprint"},{"quality_controlled":"1","intvolume":"      7148","date_created":"2018-12-11T12:02:17Z","day":"26","month":"02","acknowledgement":"This work was partly supported by the French National Research Agency (ANR) project Veridyc (ANR-09-SEGI-016).","citation":{"ama":"Bouajjani A, Dragoi C, Enea C, Sighireanu M. Abstract domains for automated reasoning about list manipulating programs with infinite data. In: Vol 7148. Springer; 2012:1-22. doi:<a href=\"https://doi.org/10.1007/978-3-642-27940-9_1\">10.1007/978-3-642-27940-9_1</a>","ista":"Bouajjani A, Dragoi C, Enea C, Sighireanu M. 2012. Abstract domains for automated reasoning about list manipulating programs with infinite data. VMCAI: Verification, Model Checking and Abstract Interpretation, LNCS, vol. 7148, 1–22.","ieee":"A. Bouajjani, C. Dragoi, C. Enea, and M. Sighireanu, “Abstract domains for automated reasoning about list manipulating programs with infinite data,” presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia, PA, USA, 2012, vol. 7148, pp. 1–22.","apa":"Bouajjani, A., Dragoi, C., Enea, C., &#38; Sighireanu, M. (2012). Abstract domains for automated reasoning about list manipulating programs with infinite data (Vol. 7148, pp. 1–22). Presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia, PA, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-642-27940-9_1\">https://doi.org/10.1007/978-3-642-27940-9_1</a>","chicago":"Bouajjani, Ahmed, Cezara Dragoi, Constantin Enea, and Mihaela Sighireanu. “Abstract Domains for Automated Reasoning about List Manipulating Programs with Infinite Data,” 7148:1–22. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-27940-9_1\">https://doi.org/10.1007/978-3-642-27940-9_1</a>.","mla":"Bouajjani, Ahmed, et al. <i>Abstract Domains for Automated Reasoning about List Manipulating Programs with Infinite Data</i>. Vol. 7148, Springer, 2012, pp. 1–22, doi:<a href=\"https://doi.org/10.1007/978-3-642-27940-9_1\">10.1007/978-3-642-27940-9_1</a>.","short":"A. Bouajjani, C. Dragoi, C. Enea, M. Sighireanu, in:, Springer, 2012, pp. 1–22."},"year":"2012","publisher":"Springer","_id":"3253","page":"1 - 22","status":"public","volume":7148,"language":[{"iso":"eng"}],"department":[{"_id":"ToHe"}],"publication_status":"published","oa_version":"None","date_published":"2012-02-26T00:00:00Z","title":"Abstract domains for automated reasoning about list manipulating programs with infinite data","fulldoi":"https://doi.org/10.1007/978-3-642-27940-9_1","doi":"10.1007/978-3-642-27940-9_1","type":"conference","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Bouajjani","full_name":"Bouajjani, Ahmed","first_name":"Ahmed"},{"last_name":"Dragoi","id":"2B2B5ED0-F248-11E8-B48F-1D18A9856A87","full_name":"Dragoi, Cezara","first_name":"Cezara"},{"full_name":"Enea, Constantin","last_name":"Enea","first_name":"Constantin"},{"first_name":"Mihaela","full_name":"Sighireanu, Mihaela","last_name":"Sighireanu"}],"abstract":[{"lang":"eng","text":"We describe a framework for reasoning about programs with lists carrying integer numerical data. We use abstract domains to describe and manipulate complex constraints on configurations of these programs mixing constraints on the shape of the heap, sizes of the lists, on the multisets of data stored in these lists, and on the data at their different positions. Moreover, we provide powerful techniques for automatic validation of Hoare-triples and invariant checking, as well as for automatic synthesis of invariants and procedure summaries using modular inter-procedural analysis. The approach has been implemented in a tool called Celia and experimented successfully on a large benchmark of programs."}],"alternative_title":["LNCS"],"publist_id":"3404","conference":{"start_date":"2012-01-22","end_date":"2012-01-24","name":"VMCAI: Verification, Model Checking and Abstract Interpretation","location":"Philadelphia, PA, USA"},"date_updated":"2024-10-21T06:02:58Z","scopus_import":"1"},{"date_published":"2012-02-01T00:00:00Z","fulldoi":"https://doi.org/10.1016/j.ic.2011.11.004","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ec_funded":1,"abstract":[{"lang":"eng","text":"The theory of graph games with ω-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the qualitative problem asks for the set of states from which a player can win with probability 1 (almost-sure winning); and the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We consider ω-regular winning conditions formalized as Müller winning conditions. We present optimal memory bounds for pure (deterministic) almost-sure winning and optimal winning strategies in stochastic graph games with Müller winning conditions. We also study the complexity of stochastic Müller games and show that both the qualitative and quantitative analysis problems are PSPACE-complete. Our results are relevant in synthesis of stochastic reactive processes."}],"publist_id":"3403","date_updated":"2025-09-30T07:45:01Z","external_id":{"isi":["000300468000002"]},"intvolume":"       211","isi":1,"day":"01","publisher":"Elsevier","citation":{"ieee":"K. Chatterjee, “The complexity of stochastic Müller games,” <i>Information and Computation</i>, vol. 211. Elsevier, pp. 29–48, 2012.","apa":"Chatterjee, K. (2012). The complexity of stochastic Müller games. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2011.11.004\">https://doi.org/10.1016/j.ic.2011.11.004</a>","ista":"Chatterjee K. 2012. The complexity of stochastic Müller games. Information and Computation. 211, 29–48.","ama":"Chatterjee K. The complexity of stochastic Müller games. <i>Information and Computation</i>. 2012;211:29-48. doi:<a href=\"https://doi.org/10.1016/j.ic.2011.11.004\">10.1016/j.ic.2011.11.004</a>","short":"K. Chatterjee, Information and Computation 211 (2012) 29–48.","mla":"Chatterjee, Krishnendu. “The Complexity of Stochastic Müller Games.” <i>Information and Computation</i>, vol. 211, Elsevier, 2012, pp. 29–48, doi:<a href=\"https://doi.org/10.1016/j.ic.2011.11.004\">10.1016/j.ic.2011.11.004</a>.","chicago":"Chatterjee, Krishnendu. “The Complexity of Stochastic Müller Games.” <i>Information and Computation</i>. Elsevier, 2012. <a href=\"https://doi.org/10.1016/j.ic.2011.11.004\">https://doi.org/10.1016/j.ic.2011.11.004</a>."},"year":"2012","acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No. P 23499-N23, FWF NFN Grant No. S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","status":"public","_id":"3254","oa_version":"None","title":"The complexity of stochastic Müller games","type":"journal_article","main_file_link":[{"url":"http://arise.or.at/pubpdf/The_complexity_of_stochastic_M___u_ller_games.pdf"}],"doi":"10.1016/j.ic.2011.11.004","publication":"Information and Computation","author":[{"last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"}],"corr_author":"1","scopus_import":"1","project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23"},{"grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"quality_controlled":"1","article_processing_charge":"No","date_created":"2018-12-11T12:02:17Z","month":"02","page":"29 - 48","publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"KrCh"}],"volume":211},{"publist_id":"3400","date_updated":"2021-01-12T07:42:10Z","alternative_title":["LNCS"],"abstract":[{"text":"In this paper we survey results of two-player games on graphs and Markov decision processes with parity, mean-payoff and energy objectives, and the combination of mean-payoff and energy objectives with parity objectives. These problems have applications in verification and synthesis of reactive systems in resource-constrained environments.","lang":"eng"}],"file_date_updated":"2020-07-14T12:46:05Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.1007/978-3-642-25929-6_3","ddc":["000"],"has_accepted_license":"1","date_published":"2012-01-01T00:00:00Z","oa_version":"Submitted Version","status":"public","_id":"3255","citation":{"ama":"Chatterjee K, Doyen L. Games and Markov decision processes with mean payoff parity and energy parity objectives. In: Vol 7119. Springer; 2012:37-46. doi:<a href=\"https://doi.org/10.1007/978-3-642-25929-6_3\">10.1007/978-3-642-25929-6_3</a>","ista":"Chatterjee K, Doyen L. 2012. Games and Markov decision processes with mean payoff parity and energy parity objectives. MEMICS: Mathematical and Engineering Methods in Computer Science, LNCS, vol. 7119, 37–46.","apa":"Chatterjee, K., &#38; Doyen, L. (2012). Games and Markov decision processes with mean payoff parity and energy parity objectives (Vol. 7119, pp. 37–46). Presented at the MEMICS: Mathematical and Engineering Methods in Computer Science, Lednice, Czech Republic: Springer. <a href=\"https://doi.org/10.1007/978-3-642-25929-6_3\">https://doi.org/10.1007/978-3-642-25929-6_3</a>","ieee":"K. Chatterjee and L. Doyen, “Games and Markov decision processes with mean payoff parity and energy parity objectives,” presented at the MEMICS: Mathematical and Engineering Methods in Computer Science, Lednice, Czech Republic, 2012, vol. 7119, pp. 37–46.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Games and Markov Decision Processes with Mean Payoff Parity and Energy Parity Objectives,” 7119:37–46. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-25929-6_3\">https://doi.org/10.1007/978-3-642-25929-6_3</a>.","short":"K. Chatterjee, L. Doyen, in:, Springer, 2012, pp. 37–46.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games and Markov Decision Processes with Mean Payoff Parity and Energy Parity Objectives</i>. Vol. 7119, Springer, 2012, pp. 37–46, doi:<a href=\"https://doi.org/10.1007/978-3-642-25929-6_3\">10.1007/978-3-642-25929-6_3</a>."},"year":"2012","acknowledgement":"This work was partially supported by FWF NFN Grant S11407-N23 (RiSE) and a Microsoft faculty fellowship.","publisher":"Springer","day":"01","file":[{"creator":"dernst","date_updated":"2020-07-14T12:46:05Z","content_type":"application/pdf","access_level":"open_access","checksum":"eed2cc1e76b160418c977e76e8899a60","relation":"main_file","date_created":"2020-05-15T12:53:12Z","file_size":114060,"file_name":"2012_MEMICS_Chatterjee.pdf","file_id":"7863"}],"intvolume":"      7119","scopus_import":1,"conference":{"location":"Lednice, Czech Republic","name":"MEMICS: Mathematical and Engineering Methods in Computer Science","end_date":"2011-10-16","start_date":"2011-10-14"},"author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"}],"doi":"10.1007/978-3-642-25929-6_3","type":"conference","title":"Games and Markov decision processes with mean payoff parity and energy parity objectives","oa":1,"department":[{"_id":"KrCh"}],"language":[{"iso":"eng"}],"volume":7119,"publication_status":"published","page":"37 - 46","month":"01","date_created":"2018-12-11T12:02:17Z","article_processing_charge":"No","quality_controlled":"1","project":[{"grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF"}]},{"doi":"10.1007/s00454-011-9382-4","type":"journal_article","oa":1,"title":"Dual complexes of cubical subdivisions of ℝn","scopus_import":"1","corr_author":"1","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","orcid":"0000-0002-9823-6833"},{"full_name":"Kerber, Michael","last_name":"Kerber","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","orcid":"0000-0002-8030-9299"}],"publication":"Discrete & Computational Geometry","date_created":"2018-12-11T12:02:17Z","article_processing_charge":"No","quality_controlled":"1","volume":47,"department":[{"_id":"HeEd"}],"language":[{"iso":"eng"}],"publication_status":"published","pubrep_id":"543","page":"393 - 414","month":"03","fulldoi":"https://doi.org/10.1007/s00454-011-9382-4","ddc":["000"],"date_published":"2012-03-01T00:00:00Z","has_accepted_license":"1","publist_id":"3398","date_updated":"2025-09-30T07:43:46Z","abstract":[{"lang":"eng","text":"We use a distortion to define the dual complex of a cubical subdivision of ℝ n as an n-dimensional subcomplex of the nerve of the set of n-cubes. Motivated by the topological analysis of high-dimensional digital image data, we consider such subdivisions defined by generalizations of quad- and oct-trees to n dimensions. Assuming the subdivision is balanced, we show that mapping each vertex to the center of the corresponding n-cube gives a geometric realization of the dual complex in ℝ n."}],"file_date_updated":"2020-07-14T12:46:05Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","file":[{"access_level":"open_access","checksum":"76486f3b2c9e7fd81342f3832ca387e7","relation":"main_file","creator":"system","content_type":"application/pdf","date_updated":"2020-07-14T12:46:05Z","file_id":"4675","date_created":"2018-12-12T10:08:15Z","file_size":203636,"file_name":"IST-2016-543-v1+1_2012-J-08-HierarchyCubeComplex.pdf"}],"intvolume":"        47","external_id":{"isi":["000299057200010"]},"issue":"2","oa_version":"Submitted Version","status":"public","_id":"3256","year":"2012","citation":{"mla":"Edelsbrunner, Herbert, and Michael Kerber. “Dual Complexes of Cubical Subdivisions of ℝn.” <i>Discrete &#38; Computational Geometry</i>, vol. 47, no. 2, Springer, 2012, pp. 393–414, doi:<a href=\"https://doi.org/10.1007/s00454-011-9382-4\">10.1007/s00454-011-9382-4</a>.","short":"H. Edelsbrunner, M. Kerber, Discrete &#38; Computational Geometry 47 (2012) 393–414.","chicago":"Edelsbrunner, Herbert, and Michael Kerber. “Dual Complexes of Cubical Subdivisions of ℝn.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2012. <a href=\"https://doi.org/10.1007/s00454-011-9382-4\">https://doi.org/10.1007/s00454-011-9382-4</a>.","apa":"Edelsbrunner, H., &#38; Kerber, M. (2012). Dual complexes of cubical subdivisions of ℝn. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-011-9382-4\">https://doi.org/10.1007/s00454-011-9382-4</a>","ieee":"H. Edelsbrunner and M. Kerber, “Dual complexes of cubical subdivisions of ℝn,” <i>Discrete &#38; Computational Geometry</i>, vol. 47, no. 2. Springer, pp. 393–414, 2012.","ista":"Edelsbrunner H, Kerber M. 2012. Dual complexes of cubical subdivisions of ℝn. Discrete &#38; Computational Geometry. 47(2), 393–414.","ama":"Edelsbrunner H, Kerber M. Dual complexes of cubical subdivisions of ℝn. <i>Discrete &#38; Computational Geometry</i>. 2012;47(2):393-414. doi:<a href=\"https://doi.org/10.1007/s00454-011-9382-4\">10.1007/s00454-011-9382-4</a>"},"acknowledgement":"This research is partially supported by the Defense Advanced Research Projects Agency (DARPA) under grants HR0011-05-1-0057 and HR0011-09-0065 as well as the National Science Foundation (NSF) under grant DBI-0820624.","publisher":"Springer","day":"01","isi":1},{"main_file_link":[{"url":"http://arxiv.org/abs/1005.2305","open_access":"1"}],"doi":"10.1016/j.dam.2011.10.026","type":"journal_article","title":"Generalized roof duality and bisubmodular functions","oa":1,"scopus_import":"1","corr_author":"1","author":[{"last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir"}],"publication":"Discrete Applied Mathematics","date_created":"2018-12-11T12:02:18Z","article_processing_charge":"No","quality_controlled":"1","related_material":{"record":[{"relation":"earlier_version","id":"2934","status":"public"}]},"department":[{"_id":"VlKo"}],"volume":160,"language":[{"iso":"eng"}],"publication_status":"published","page":"416 - 426","month":"03","fulldoi":"https://doi.org/10.1016/j.dam.2011.10.026","date_published":"2012-03-01T00:00:00Z","date_updated":"2025-09-30T07:43:17Z","publist_id":"3397","abstract":[{"lang":"eng","text":"Consider a convex relaxation f̂ of a pseudo-Boolean function f. We say that the relaxation is totally half-integral if f̂(x) is a polyhedral function with half-integral extreme points x, and this property is preserved after adding an arbitrary combination of constraints of the form x i=x j, x i=1-x j, and x i=γ where γ∈{0,1,1/2} is a constant. A well-known example is the roof duality relaxation for quadratic pseudo-Boolean functions f. We argue that total half-integrality is a natural requirement for generalizations of roof duality to arbitrary pseudo-Boolean functions. Our contributions are as follows. First, we provide a complete characterization of totally half-integral relaxations f̂ by establishing a one-to-one correspondence with bisubmodular functions. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally half-integral relaxations and relaxations based on the roof duality. On the conceptual level, our results show that bisubmodular functions provide a natural generalization of the roof duality approach to higher-order terms. This can be viewed as a non-submodular analogue of the fact that submodular functions generalize the s-t minimum cut problem with non-negative weights to higher-order terms."}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","intvolume":"       160","external_id":{"arxiv":["1005.2305"],"isi":["000301211100006"]},"issue":"4-5","oa_version":"Preprint","status":"public","_id":"3257","year":"2012","citation":{"ama":"Kolmogorov V. Generalized roof duality and bisubmodular functions. <i>Discrete Applied Mathematics</i>. 2012;160(4-5):416-426. doi:<a href=\"https://doi.org/10.1016/j.dam.2011.10.026\">10.1016/j.dam.2011.10.026</a>","ista":"Kolmogorov V. 2012. Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. 160(4–5), 416–426.","ieee":"V. Kolmogorov, “Generalized roof duality and bisubmodular functions,” <i>Discrete Applied Mathematics</i>, vol. 160, no. 4–5. Elsevier, pp. 416–426, 2012.","apa":"Kolmogorov, V. (2012). Generalized roof duality and bisubmodular functions. <i>Discrete Applied Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.dam.2011.10.026\">https://doi.org/10.1016/j.dam.2011.10.026</a>","chicago":"Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.” <i>Discrete Applied Mathematics</i>. Elsevier, 2012. <a href=\"https://doi.org/10.1016/j.dam.2011.10.026\">https://doi.org/10.1016/j.dam.2011.10.026</a>.","short":"V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 416–426.","mla":"Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.” <i>Discrete Applied Mathematics</i>, vol. 160, no. 4–5, Elsevier, 2012, pp. 416–26, doi:<a href=\"https://doi.org/10.1016/j.dam.2011.10.026\">10.1016/j.dam.2011.10.026</a>."},"publisher":"Elsevier","arxiv":1,"day":"01","isi":1},{"publication":"Nature Neuroscience","author":[{"first_name":"Sooyun","last_name":"Kim","id":"394AB1C8-F248-11E8-B48F-1D18A9856A87","full_name":"Kim, Sooyun"},{"orcid":"0000-0003-2209-5242","first_name":"José","last_name":"Guzmán","id":"30CC5506-F248-11E8-B48F-1D18A9856A87","full_name":"Guzmán, José"},{"first_name":"Hua","full_name":"Hu, Hua","last_name":"Hu","id":"4AC0145C-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0001-5001-4804","first_name":"Peter M","last_name":"Jonas","id":"353C1B58-F248-11E8-B48F-1D18A9856A87","full_name":"Jonas, Peter M"}],"corr_author":"1","scopus_import":"1","title":"Active dendrites support efficient initiation of dendritic spikes in hippocampal CA3 pyramidal neurons","oa":1,"publication_identifier":{"issn":["1546-1726"]},"pmid":1,"type":"journal_article","main_file_link":[{"open_access":"1","url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3617474/"}],"doi":"10.1038/nn.3060","month":"04","page":"600 - 606","publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"PeJo"}],"volume":15,"project":[{"grant_number":"SFB-TR3-TP10B","_id":"25BDE9A4-B435-11E9-9278-68D0E5697425","name":"Glutamaterge synaptische Übertragung und Plastizität in hippocampalen Mikroschaltkreisen"}],"quality_controlled":"1","related_material":{"record":[{"relation":"dissertation_contains","id":"2964","status":"public"}]},"article_processing_charge":"No","date_created":"2018-12-11T12:02:18Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"CA3 pyramidal neurons are important for memory formation and pattern completion in the hippocampal network. It is generally thought that proximal synapses from the mossy fibers activate these neurons most efficiently, whereas distal inputs from the perforant path have a weaker modulatory influence. We used confocally targeted patch-clamp recording from dendrites and axons to map the activation of rat CA3 pyramidal neurons at the subcellular level. Our results reveal two distinct dendritic domains. In the proximal domain, action potentials initiated in the axon backpropagate actively with large amplitude and fast time course. In the distal domain, Na+ channel–mediated dendritic spikes are efficiently initiated by waveforms mimicking synaptic events. CA3 pyramidal neuron dendrites showed a high Na+-to-K+ conductance density ratio, providing ideal conditions for active backpropagation and dendritic spike initiation. Dendritic spikes may enhance the computational power of CA3 pyramidal neurons in the hippocampal network.","lang":"eng"}],"publist_id":"3390","date_updated":"2026-06-18T18:41:54Z","date_published":"2012-04-01T00:00:00Z","ddc":["570"],"article_type":"original","fulldoi":"https://doi.org/10.1038/nn.3060","isi":1,"day":"01","publisher":"Nature Publishing Group","acknowledgement":"This work was supported by the Deutsche Forschungsgemeinschaft (TR 3/B10) and the European Union (European Research Council Advanced grant to P.J.).","year":"2012","citation":{"ista":"Kim S, Guzmán J, Hu H, Jonas PM. 2012. Active dendrites support efficient initiation of dendritic spikes in hippocampal CA3 pyramidal neurons. Nature Neuroscience. 15(4), 600–606.","ama":"Kim S, Guzmán J, Hu H, Jonas PM. Active dendrites support efficient initiation of dendritic spikes in hippocampal CA3 pyramidal neurons. <i>Nature Neuroscience</i>. 2012;15(4):600-606. doi:<a href=\"https://doi.org/10.1038/nn.3060\">10.1038/nn.3060</a>","ieee":"S. Kim, J. Guzmán, H. Hu, and P. M. Jonas, “Active dendrites support efficient initiation of dendritic spikes in hippocampal CA3 pyramidal neurons,” <i>Nature Neuroscience</i>, vol. 15, no. 4. Nature Publishing Group, pp. 600–606, 2012.","apa":"Kim, S., Guzmán, J., Hu, H., &#38; Jonas, P. M. (2012). Active dendrites support efficient initiation of dendritic spikes in hippocampal CA3 pyramidal neurons. <i>Nature Neuroscience</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/nn.3060\">https://doi.org/10.1038/nn.3060</a>","chicago":"Kim, Sooyun, José Guzmán, Hua Hu, and Peter M Jonas. “Active Dendrites Support Efficient Initiation of Dendritic Spikes in Hippocampal CA3 Pyramidal Neurons.” <i>Nature Neuroscience</i>. Nature Publishing Group, 2012. <a href=\"https://doi.org/10.1038/nn.3060\">https://doi.org/10.1038/nn.3060</a>.","mla":"Kim, Sooyun, et al. “Active Dendrites Support Efficient Initiation of Dendritic Spikes in Hippocampal CA3 Pyramidal Neurons.” <i>Nature Neuroscience</i>, vol. 15, no. 4, Nature Publishing Group, 2012, pp. 600–06, doi:<a href=\"https://doi.org/10.1038/nn.3060\">10.1038/nn.3060</a>.","short":"S. Kim, J. Guzmán, H. Hu, P.M. Jonas, Nature Neuroscience 15 (2012) 600–606."},"_id":"3258","status":"public","oa_version":"Published Version","issue":"4","external_id":{"isi":["000302114500020"],"pmid":["22388958"]},"intvolume":"        15"},{"article_number":"6126486","fulldoi":"https://doi.org/10.1109/ICCV.2011.6126486","doi":"10.1109/ICCV.2011.6126486","type":"conference","date_published":"2012-01-12T00:00:00Z","title":"Image segmentation by figure-ground composition into maximal cliques","author":[{"id":"29F89302-F248-11E8-B48F-1D18A9856A87","last_name":"Ion","full_name":"Ion, Adrian","first_name":"Adrian"},{"full_name":"Carreira, Joao","last_name":"Carreira","first_name":"Joao"},{"last_name":"Sminchisescu","full_name":"Sminchisescu, Cristian","first_name":"Cristian"}],"abstract":[{"text":"We propose a mid-level statistical model for image segmentation that composes multiple figure-ground hypotheses (FG) obtained by applying constraints at different locations and scales, into larger interpretations (tilings) of the entire image. Inference is cast as optimization over sets of maximal cliques sampled from a graph connecting all non-overlapping figure-ground segment hypotheses. Potential functions over cliques combine unary, Gestalt-based figure qualities, and pairwise compatibilities among spatially neighboring segments, constrained by T-junctions and the boundary interface statistics of real scenes. Learning the model parameters is based on maximum likelihood, alternating between sampling image tilings and optimizing their potential function parameters. State of the art results are reported on the Berkeley and Stanford segmentation datasets, as well as VOC2009, where a 28% improvement was achieved.","lang":"eng"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T07:42:15Z","publist_id":"3382","conference":{"start_date":"2011-11-06","location":"Barcelona, Spain","name":"ICCV: International Conference on Computer Vision","end_date":"2011-11-13"},"quality_controlled":"1","date_created":"2018-12-11T12:02:21Z","citation":{"chicago":"Ion, Adrian, Joao Carreira, and Cristian Sminchisescu. “Image Segmentation by Figure-Ground Composition into Maximal Cliques.” IEEE, 2012. <a href=\"https://doi.org/10.1109/ICCV.2011.6126486\">https://doi.org/10.1109/ICCV.2011.6126486</a>.","short":"A. Ion, J. Carreira, C. Sminchisescu, in:, IEEE, 2012.","mla":"Ion, Adrian, et al. <i>Image Segmentation by Figure-Ground Composition into Maximal Cliques</i>. 6126486, IEEE, 2012, doi:<a href=\"https://doi.org/10.1109/ICCV.2011.6126486\">10.1109/ICCV.2011.6126486</a>.","ama":"Ion A, Carreira J, Sminchisescu C. Image segmentation by figure-ground composition into maximal cliques. In: IEEE; 2012. doi:<a href=\"https://doi.org/10.1109/ICCV.2011.6126486\">10.1109/ICCV.2011.6126486</a>","ista":"Ion A, Carreira J, Sminchisescu C. 2012. Image segmentation by figure-ground composition into maximal cliques. ICCV: International Conference on Computer Vision, 6126486.","ieee":"A. Ion, J. Carreira, and C. Sminchisescu, “Image segmentation by figure-ground composition into maximal cliques,” presented at the ICCV: International Conference on Computer Vision, Barcelona, Spain, 2012.","apa":"Ion, A., Carreira, J., &#38; Sminchisescu, C. (2012). Image segmentation by figure-ground composition into maximal cliques. Presented at the ICCV: International Conference on Computer Vision, Barcelona, Spain: IEEE. <a href=\"https://doi.org/10.1109/ICCV.2011.6126486\">https://doi.org/10.1109/ICCV.2011.6126486</a>"},"year":"2012","publisher":"IEEE","day":"12","month":"01","department":[{"_id":"HeEd"}],"language":[{"iso":"eng"}],"oa_version":"None","publication_status":"published","_id":"3265","status":"public"},{"_id":"3277","page":"387 - 405","status":"public","oa_version":"None","publication_status":"published","language":[{"iso":"eng"}],"volume":24,"department":[{"_id":"NiBa"}],"month":"01","day":"01","publisher":"Springer","citation":{"ieee":"H. de Vladar and J. Chela Flores, “Can the evolution of multicellularity be anticipated in the exploration of the solar system?,” in <i>Life on Earth and other planetary bodies</i>, vol. 24, Springer, 2012, pp. 387–405.","apa":"de Vladar, H., &#38; Chela Flores, J. (2012). Can the evolution of multicellularity be anticipated in the exploration of the solar system? In <i>Life on Earth and other planetary bodies</i> (Vol. 24, pp. 387–405). Springer. <a href=\"https://doi.org/10.1007/978-94-007-4966-5_22\">https://doi.org/10.1007/978-94-007-4966-5_22</a>","ama":"de Vladar H, Chela Flores J. Can the evolution of multicellularity be anticipated in the exploration of the solar system? In: <i>Life on Earth and Other Planetary Bodies</i>. Vol 24. Springer; 2012:387-405. doi:<a href=\"https://doi.org/10.1007/978-94-007-4966-5_22\">10.1007/978-94-007-4966-5_22</a>","ista":"de Vladar H, Chela Flores J. 2012.Can the evolution of multicellularity be anticipated in the exploration of the solar system? In: Life on Earth and other planetary bodies. Cellular Origin, Life in Extreme Habitats and Astrobiology, vol. 24, 387–405.","short":"H. de Vladar, J. Chela Flores, in:, Life on Earth and Other Planetary Bodies, Springer, 2012, pp. 387–405.","mla":"de Vladar, Harold, and Julian Chela Flores. “Can the Evolution of Multicellularity Be Anticipated in the Exploration of the Solar System?” <i>Life on Earth and Other Planetary Bodies</i>, vol. 24, Springer, 2012, pp. 387–405, doi:<a href=\"https://doi.org/10.1007/978-94-007-4966-5_22\">10.1007/978-94-007-4966-5_22</a>.","chicago":"Vladar, Harold de, and Julian Chela Flores. “Can the Evolution of Multicellularity Be Anticipated in the Exploration of the Solar System?” In <i>Life on Earth and Other Planetary Bodies</i>, 24:387–405. Springer, 2012. <a href=\"https://doi.org/10.1007/978-94-007-4966-5_22\">https://doi.org/10.1007/978-94-007-4966-5_22</a>."},"year":"2012","date_created":"2018-12-11T12:02:25Z","intvolume":"        24","quality_controlled":"1","date_updated":"2024-10-09T20:54:39Z","alternative_title":["Cellular Origin, Life in Extreme Habitats and Astrobiology"],"publist_id":"3369","corr_author":"1","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publication":"Life on Earth and other planetary bodies","abstract":[{"text":"The problem of the origin of metazoa is becoming more urgent in the context of astrobiology. By now it is clear that clues to the understanding of this crucial transition in the evolution of life can arise in a fourth pathway besides the three possibilities in the quest for simplicity outlined by Bonner in his classical book. In other words, solar system exploration seems to be one way in the long-term to elucidate the simplicity of evolutionary development. We place these ideas in the context of different inheritance systems, namely the genotypic and phenotypic replicators with limited or unlimited heredity, and ask which of these can support multicellular development, and to which degree of complexity. However, the quest for evidence on the evolution of biotas from planets around other stars does not seem to be feasible with present technology with direct visualization of living organisms on exoplanets. But this may be attempted on the Galilean moons of Jupiter where there is a possibility of detecting reliable biomarkers in the next decade with the Europa Jupiter System Mission, in view of recent progress by landing micropenetrators on planetary, or satellite surfaces. Mars is a second possibility in the inner Solar System, in spite of the multiple difficulties faced by the fleet of past, present and future missions. We discuss a series of preliminary ideas for elucidating the origin of metazoan analogues with available instrumentation in potential payloads of feasible space missions to the Galilean moons.","lang":"eng"}],"author":[{"full_name":"de Vladar, Harold","id":"2A181218-F248-11E8-B48F-1D18A9856A87","last_name":"de Vladar","orcid":"0000-0002-5985-7653","first_name":"Harold"},{"full_name":"Chela Flores, Julian","last_name":"Chela Flores","first_name":"Julian"}],"title":"Can the evolution of multicellularity be anticipated in the exploration of the solar system?","date_published":"2012-01-01T00:00:00Z","type":"book_chapter","doi":"10.1007/978-94-007-4966-5_22","fulldoi":"https://doi.org/10.1007/978-94-007-4966-5_22"},{"day":"04","publisher":"Springer","citation":{"apa":"Jain, A., Pietrzak, K. Z., &#38; Tentes, A. (2012). Hardness preserving constructions of pseudorandom functions (Vol. 7194, pp. 369–382). Presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy: Springer. <a href=\"https://doi.org/10.1007/978-3-642-28914-9_21\">https://doi.org/10.1007/978-3-642-28914-9_21</a>","ieee":"A. Jain, K. Z. Pietrzak, and A. Tentes, “Hardness preserving constructions of pseudorandom functions,” presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy, 2012, vol. 7194, pp. 369–382.","ista":"Jain A, Pietrzak KZ, Tentes A. 2012. Hardness preserving constructions of pseudorandom functions. TCC: Theory of Cryptography Conference, LNCS, vol. 7194, 369–382.","ama":"Jain A, Pietrzak KZ, Tentes A. Hardness preserving constructions of pseudorandom functions. In: Vol 7194. Springer; 2012:369-382. doi:<a href=\"https://doi.org/10.1007/978-3-642-28914-9_21\">10.1007/978-3-642-28914-9_21</a>","short":"A. Jain, K.Z. Pietrzak, A. Tentes, in:, Springer, 2012, pp. 369–382.","mla":"Jain, Abhishek, et al. <i>Hardness Preserving Constructions of Pseudorandom Functions</i>. Vol. 7194, Springer, 2012, pp. 369–82, doi:<a href=\"https://doi.org/10.1007/978-3-642-28914-9_21\">10.1007/978-3-642-28914-9_21</a>.","chicago":"Jain, Abhishek, Krzysztof Z Pietrzak, and Aris Tentes. “Hardness Preserving Constructions of Pseudorandom Functions,” 7194:369–82. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-28914-9_21\">https://doi.org/10.1007/978-3-642-28914-9_21</a>."},"year":"2012","acknowledgement":"Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC)","status":"public","_id":"3279","oa_version":"None","intvolume":"      7194","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"abstract":[{"lang":"eng","text":"We show a hardness-preserving construction of a PRF from any length doubling PRG which improves upon known constructions whenever we can put a non-trivial upper bound q on the number of queries to the PRF. Our construction requires only O(logq) invocations to the underlying PRG with each query. In comparison, the number of invocations by the best previous hardness-preserving construction (GGM using Levin's trick) is logarithmic in the hardness of the PRG. For example, starting from an exponentially secure PRG {0,1} n → {0,1} 2n, we get a PRF which is exponentially secure if queried at most q = exp(√n)times and where each invocation of the PRF requires Θ(√n) queries to the underlying PRG. This is much less than the Θ(n) required by known constructions. \r\n"}],"publist_id":"3367","alternative_title":["LNCS"],"date_updated":"2021-01-12T07:42:21Z","date_published":"2012-05-04T00:00:00Z","fulldoi":"https://doi.org/10.1007/978-3-642-28914-9_21","month":"05","page":"369 - 382","publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"KrPi"}],"volume":7194,"project":[{"call_identifier":"FP7","name":"Provable Security for Physical Cryptography","_id":"258C570E-B435-11E9-9278-68D0E5697425","grant_number":"259668"}],"quality_controlled":"1","date_created":"2018-12-11T12:02:25Z","author":[{"last_name":"Jain","full_name":"Jain, Abhishek","first_name":"Abhishek"},{"full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z"},{"first_name":"Aris","full_name":"Tentes, Aris","last_name":"Tentes"}],"conference":{"location":"Taormina, Sicily, Italy","name":"TCC: Theory of Cryptography Conference","end_date":"2012-03-21","start_date":"2012-03-19"},"scopus_import":1,"title":"Hardness preserving constructions of pseudorandom functions","type":"conference","doi":"10.1007/978-3-642-28914-9_21","main_file_link":[{"url":"http://www.iacr.org/archive/tcc2012/tcc2012-index.html"}]},{"month":"05","page":"548 - 563","volume":7194,"department":[{"_id":"KrPi"}],"language":[{"iso":"eng"}],"publication_status":"published","project":[{"grant_number":"259668","name":"Provable Security for Physical Cryptography","_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"quality_controlled":"1","date_created":"2018-12-11T12:02:26Z","author":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z"}],"corr_author":"1","conference":{"location":"Taormina, Sicily, Italy","end_date":"2012-03-21","name":"TCC: Theory of Cryptography Conference","start_date":"2012-03-19"},"scopus_import":"1","oa":1,"title":"Subspace LWE","main_file_link":[{"open_access":"1","url":"http://www.iacr.org/archive/tcc2012/71940166/71940166.pdf"}],"doi":"10.1007/978-3-642-28914-9_31","type":"conference","day":"04","citation":{"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>.","short":"K.Z. Pietrzak, in:, Springer, 2012, pp. 548–563.","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>.","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>","ieee":"K. Z. Pietrzak, “Subspace LWE,” presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy, 2012, vol. 7194, pp. 548–563.","ista":"Pietrzak KZ. 2012. Subspace LWE. TCC: Theory of Cryptography Conference, LNCS, vol. 7194, 548–563.","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>"},"acknowledgement":"Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC).","year":"2012","publisher":"Springer","_id":"3280","status":"public","oa_version":"Submitted Version","intvolume":"      7194","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","abstract":[{"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. ","lang":"eng"}],"ec_funded":1,"alternative_title":["LNCS"],"publist_id":"3366","date_updated":"2024-10-21T06:02:59Z","date_published":"2012-05-04T00:00:00Z","fulldoi":"https://doi.org/10.1007/978-3-642-28914-9_31"},{"alternative_title":["LNCS"],"publist_id":"3365","date_updated":"2024-10-21T06:03:00Z","abstract":[{"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.","lang":"eng"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.1007/978-3-642-28914-9_26","date_published":"2012-05-04T00:00:00Z","oa_version":"None","status":"public","_id":"3281","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>.","short":"K.Z. Pietrzak, A. Rosen, G. Segev, in:, Springer, 2012, pp. 458–475.","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>.","ista":"Pietrzak KZ, Rosen A, Segev G. 2012. Lossy functions do not amplify well. TCC: Theory of Cryptography Conference, LNCS, vol. 7194, 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>","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.","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>"},"year":"2012","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","publisher":"Springer","day":"04","intvolume":"      7194","scopus_import":"1","conference":{"start_date":"2012-03-19","name":"TCC: Theory of Cryptography Conference","end_date":"2012-03-21","location":"Taormina, Sicily, Italy"},"author":[{"full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654"},{"first_name":"Alon","last_name":"Rosen","full_name":"Rosen, Alon"},{"first_name":"Gil","full_name":"Segev, Gil","last_name":"Segev"}],"main_file_link":[{"url":"http://www.iacr.org/archive/tcc2012/tcc2012-index.html"}],"doi":"10.1007/978-3-642-28914-9_26","type":"conference","title":"Lossy functions do not amplify well","department":[{"_id":"KrPi"}],"volume":7194,"language":[{"iso":"eng"}],"publication_status":"published","page":"458 - 475","month":"05","date_created":"2018-12-11T12:02:26Z","quality_controlled":"1"},{"date_updated":"2024-10-21T06:02:59Z","alternative_title":["LNCS"],"publist_id":"3364","file_date_updated":"2020-07-14T12:46:06Z","ec_funded":1,"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."}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.1007/978-3-642-29011-4_22","date_published":"2012-03-10T00:00:00Z","has_accepted_license":"1","ddc":["000","004"],"oa_version":"Submitted Version","_id":"3282","status":"public","publisher":"Springer","acknowledgement":"Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC)","year":"2012","citation":{"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>","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.","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.","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>","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>.","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>.","short":"Y. Dodis, K.Z. Pietrzak, E. Kiltz, D. Wichs, in:, Springer, 2012, pp. 355–374."},"day":"10","intvolume":"      7237","file":[{"file_id":"5074","file_name":"IST-2016-686-v1+1_059.pdf","date_created":"2018-12-12T10:14:23Z","file_size":372292,"relation":"main_file","checksum":"8557c17a8c2586d06ebfe62d934f5c5f","access_level":"open_access","content_type":"application/pdf","date_updated":"2020-07-14T12:46:06Z","creator":"system"}],"scopus_import":"1","conference":{"location":"Cambridge, UK","end_date":"2012-04-19","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","start_date":"2012-04-15"},"author":[{"full_name":"Dodis, Yevgeniy","last_name":"Dodis","first_name":"Yevgeniy"},{"full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654"},{"full_name":"Kiltz, Eike","last_name":"Kiltz","first_name":"Eike"},{"last_name":"Wichs","full_name":"Wichs, Daniel","first_name":"Daniel"}],"type":"conference","doi":"10.1007/978-3-642-29011-4_22","title":"Message authentication, revisited","oa":1,"pubrep_id":"686","publication_status":"published","department":[{"_id":"KrPi"}],"volume":7237,"language":[{"iso":"eng"}],"page":"355 - 374","month":"03","date_created":"2018-12-11T12:02:27Z","quality_controlled":"1","project":[{"name":"Provable Security for Physical Cryptography","_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"259668"}]},{"issue":"1","external_id":{"pmid":["22031940"],"isi":["000298347700017"]},"intvolume":"        86","isi":1,"day":"01","publisher":"ASM","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.","citation":{"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.","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>","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>","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.","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>.","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>.","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."},"year":"2012","status":"public","_id":"3289","oa_version":"Submitted Version","date_published":"2012-01-01T00:00:00Z","fulldoi":"https://doi.org/10.1128/JVI.05638-11","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","abstract":[{"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","lang":"eng"}],"publist_id":"3356","date_updated":"2025-09-30T07:40:18Z","quality_controlled":"1","article_processing_charge":"No","date_created":"2018-12-11T12:02:29Z","month":"01","page":"172 - 184","publication_status":"published","volume":86,"language":[{"iso":"eng"}],"department":[{"_id":"JoBo"}],"oa":1,"title":"A vaccinia virus-driven interplay between the MKK4/7-JNK1/2 pathway and cytoskeleton reorganization","pmid":1,"type":"journal_article","main_file_link":[{"open_access":"1","url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3255887/"}],"doi":"10.1128/JVI.05638-11","publication":"Journal of Virology","author":[{"first_name":"Anna","full_name":"Pereira, Anna","last_name":"Pereira"},{"first_name":"Flávia","full_name":"Leite, Flávia","id":"36705F98-F248-11E8-B48F-1D18A9856A87","last_name":"Leite"},{"last_name":"Brasil","full_name":"Brasil, Bruno","first_name":"Bruno"},{"first_name":"Jamaria","full_name":"Soares Martins, Jamaria","last_name":"Soares Martins"},{"first_name":"Alice","last_name":"Torres","full_name":"Torres, Alice"},{"full_name":"Pimenta, Paulo","last_name":"Pimenta","first_name":"Paulo"},{"last_name":"Souto Padrón","full_name":"Souto Padrón, Thais","first_name":"Thais"},{"first_name":"Paula","last_name":"Tranktman","full_name":"Tranktman, Paula"},{"full_name":"Ferreira, Paulo","last_name":"Ferreira","first_name":"Paulo"},{"last_name":"Kroon","full_name":"Kroon, Erna","first_name":"Erna"},{"full_name":"Bonjardim, Cláudio","last_name":"Bonjardim","first_name":"Cláudio"}],"scopus_import":"1"},{"has_accepted_license":"1","date_published":"2012-08-01T00:00:00Z","ddc":["000"],"fulldoi":"https://doi.org/10.1016/j.patrec.2011.10.007","publist_id":"3330","date_updated":"2025-09-30T07:39:47Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","file_date_updated":"2020-07-14T12:46:06Z","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."}],"issue":"11","external_id":{"isi":["000307204300002"]},"intvolume":"        33","file":[{"file_id":"5116","file_name":"IST-2016-542-v1+1_2012-J-01-Poinculus.pdf","file_size":280280,"date_created":"2018-12-12T10:15:00Z","access_level":"open_access","checksum":"d65f79775b51258a604ca5ec741297cc","relation":"main_file","date_updated":"2020-07-14T12:46:06Z","content_type":"application/pdf","creator":"system"}],"_id":"3310","status":"public","oa_version":"Submitted Version","isi":1,"day":"01","publisher":"Elsevier","acknowledgement":"Research by the third author is partially supported by the National Science Foundation (NSF) under grant DBI-0820624.","citation":{"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>.","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.","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.","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>","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."},"year":"2012","oa":1,"title":"A point calculus for interlevel set homology","type":"journal_article","doi":"10.1016/j.patrec.2011.10.007","scopus_import":"1","publication":"Pattern Recognition Letters","author":[{"last_name":"Bendich","id":"43F6EC54-F248-11E8-B48F-1D18A9856A87","full_name":"Bendich, Paul","first_name":"Paul"},{"first_name":"Sergio","last_name":"Cabello","full_name":"Cabello, Sergio"},{"last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","first_name":"Herbert"}],"article_processing_charge":"No","date_created":"2018-12-11T12:02:36Z","quality_controlled":"1","page":"1436 - 1444","publication_status":"published","pubrep_id":"542","department":[{"_id":"HeEd"}],"volume":33,"language":[{"iso":"eng"}],"month":"08"},{"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"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publist_id":"3326","date_updated":"2025-09-30T07:38:00Z","fulldoi":"https://doi.org/10.1142/S0129054112400308","date_published":"2012-04-01T00:00:00Z","citation":{"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>.","short":"K. Chatterjee, R. Majumdar, International Journal of Foundations of Computer Science 23 (2012) 609–625.","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>.","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>","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.","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>","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."},"year":"2012","acknowledgement":"This research was funded in part by the US National Science Foundation grants CCF-0546170, CNS-0702881, DARPA grant HR0011-09-1-0037, Austrian Science Fund (FWF) NFN Grant S11407-N23 (RiSE) and a Microsoft faculty fellowship.","publisher":"World Scientific Publishing","day":"01","isi":1,"oa_version":"None","_id":"3314","status":"public","intvolume":"        23","external_id":{"isi":["000304003000004"]},"issue":"3","author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"first_name":"Ritankar","last_name":"Majumdar","full_name":"Majumdar, Ritankar"}],"publication":"International Journal of Foundations of Computer Science","scopus_import":"1","doi":"10.1142/S0129054112400308","type":"journal_article","title":"Discounting and averaging in games across time scales","month":"04","volume":23,"language":[{"iso":"eng"}],"department":[{"_id":"KrCh"}],"publication_status":"published","page":"609 - 625","quality_controlled":"1","project":[{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"date_created":"2018-12-11T12:02:37Z","article_processing_charge":"No"},{"page":"7 - 21","pubrep_id":"820","publication_status":"published","volume":13,"department":[{"_id":"PeJo"}],"language":[{"iso":"eng"}],"month":"01","article_processing_charge":"No","date_created":"2018-12-11T12:02:38Z","project":[{"_id":"25BC64A8-B435-11E9-9278-68D0E5697425","name":"Synaptic Mechanisms of Neuronal Network Function","grant_number":"JO_780/A5"},{"_id":"25BDE9A4-B435-11E9-9278-68D0E5697425","name":"Glutamaterge synaptische Übertragung und Plastizität in hippocampalen Mikroschaltkreisen","grant_number":"SFB-TR3-TP10B"}],"quality_controlled":"1","corr_author":"1","scopus_import":"1","publication":"Nature Reviews Neuroscience","author":[{"first_name":"Emmanuel","id":"34DACA34-E9AE-11E9-849C-D35BD8ADC20C","last_name":"Eggermann","full_name":"Eggermann, Emmanuel"},{"id":"4BD1D872-E9AE-11E9-9EE9-8BF4597A9E2A","last_name":"Bucurenciu","full_name":"Bucurenciu, Iancu","first_name":"Iancu"},{"first_name":"Sarit","id":"3A578F32-F248-11E8-B48F-1D18A9856A87","last_name":"Goswami","full_name":"Goswami, Sarit"},{"full_name":"Jonas, Peter M","id":"353C1B58-F248-11E8-B48F-1D18A9856A87","last_name":"Jonas","first_name":"Peter M","orcid":"0000-0001-5001-4804"}],"oa":1,"title":"Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses","type":"journal_article","doi":"10.1038/nrn3125","_id":"3317","status":"public","oa_version":"Submitted Version","isi":1,"day":"01","publisher":"Nature Publishing Group","citation":{"ama":"Eggermann E, Bucurenciu I, Goswami S, Jonas PM. Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses. <i>Nature Reviews Neuroscience</i>. 2012;13(1):7-21. doi:<a href=\"https://doi.org/10.1038/nrn3125\">10.1038/nrn3125</a>","ista":"Eggermann E, Bucurenciu I, Goswami S, Jonas PM. 2012. Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses. Nature Reviews Neuroscience. 13(1), 7–21.","ieee":"E. Eggermann, I. Bucurenciu, S. Goswami, and P. M. Jonas, “Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses,” <i>Nature Reviews Neuroscience</i>, vol. 13, no. 1. Nature Publishing Group, pp. 7–21, 2012.","apa":"Eggermann, E., Bucurenciu, I., Goswami, S., &#38; Jonas, P. M. (2012). Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses. <i>Nature Reviews Neuroscience</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/nrn3125\">https://doi.org/10.1038/nrn3125</a>","chicago":"Eggermann, Emmanuel, Iancu Bucurenciu, Sarit Goswami, and Peter M Jonas. “Nanodomain Coupling between Ca(2+) Channels and Sensors of Exocytosis at Fast Mammalian Synapses.” <i>Nature Reviews Neuroscience</i>. Nature Publishing Group, 2012. <a href=\"https://doi.org/10.1038/nrn3125\">https://doi.org/10.1038/nrn3125</a>.","mla":"Eggermann, Emmanuel, et al. “Nanodomain Coupling between Ca(2+) Channels and Sensors of Exocytosis at Fast Mammalian Synapses.” <i>Nature Reviews Neuroscience</i>, vol. 13, no. 1, Nature Publishing Group, 2012, pp. 7–21, doi:<a href=\"https://doi.org/10.1038/nrn3125\">10.1038/nrn3125</a>.","short":"E. Eggermann, I. Bucurenciu, S. Goswami, P.M. Jonas, Nature Reviews Neuroscience 13 (2012) 7–21."},"acknowledgement":"Work of the authors was funded by grants of the Deutsche Forschungsgemeinschaft to P.J. (grants SFB 780/A5, TR 3/B10 and the Leibniz programme), a European Research Council Advanced grant to P.J. and a Swiss National Foundation fellowship to E.E.\r\nWe thank D. Tsien and E. Neher for their comments on this Review, J. Guzmán and A. Pernía-Andrade for reading earlier versions and E. Kramberger for perfect editorial support. We apologize that owing to space constraints, not all relevant papers could be cited.\r\n","year":"2012","issue":"1","external_id":{"isi":["000298323200008"]},"intvolume":"        13","file":[{"file_size":314246,"date_created":"2018-12-12T10:12:13Z","file_name":"IST-2017-820-v1+1_17463_3_art_file_109404_ltmxbw.pdf","file_id":"4931","creator":"system","date_updated":"2020-07-14T12:46:07Z","content_type":"application/pdf","checksum":"4c1c86b2f6e4e1562f5bb800b457ea9f","access_level":"open_access","relation":"main_file"},{"file_id":"4932","file_name":"IST-2017-820-v1+2_17463_3_figure_109402_ltmwlp.pdf","file_size":1840216,"date_created":"2018-12-12T10:12:14Z","relation":"main_file","checksum":"bceb2efdd49d115f4dde8486bc1be3f2","access_level":"open_access","content_type":"application/pdf","date_updated":"2020-07-14T12:46:07Z","creator":"system"}],"date_updated":"2025-09-30T07:34:43Z","publist_id":"3322","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","abstract":[{"text":"The physical distance between presynaptic Ca2+ channels and the Ca2+ sensors that trigger exocytosis of neurotransmitter-containing vesicles is a key determinant of the signalling properties of synapses in the nervous system. Recent functional analysis indicates that in some fast central synapses, transmitter release is triggered by a small number of Ca2+ channels that are coupled to Ca2+ sensors at the nanometre scale. Molecular analysis suggests that this tight coupling is generated by protein–protein interactions involving Ca2+ channels, Ca2+ sensors and various other synaptic proteins. Nanodomain coupling has several functional advantages, as it increases the efficacy, speed and energy efficiency of synaptic transmission.","lang":"eng"}],"file_date_updated":"2020-07-14T12:46:07Z","has_accepted_license":"1","date_published":"2012-01-01T00:00:00Z","ddc":["570"],"fulldoi":"https://doi.org/10.1038/nrn3125"},{"date_created":"2018-12-11T12:02:46Z","project":[{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"related_material":{"record":[{"status":"public","id":"5382","relation":"earlier_version"}]},"quality_controlled":"1","page":"270 - 285","publication_status":"published","department":[{"_id":"KrCh"}],"volume":7213,"language":[{"iso":"eng"}],"month":"03","title":"Robustness of structurally equivalent concurrent parity games","oa":1,"type":"conference","doi":"10.1007/978-3-642-28729-9_18","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1107.2009"}],"conference":{"end_date":"2012-04-01","name":"FoSSaCS: Foundations of Software Science and Computation Structures","location":"Tallinn, Estonia","start_date":"2012-03-24"},"corr_author":"1","scopus_import":1,"author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"}],"external_id":{"arxiv":["1107.2009"]},"intvolume":"      7213","_id":"3341","status":"public","oa_version":"Preprint","day":"22","arxiv":1,"publisher":"Springer","year":"2012","citation":{"apa":"Chatterjee, K. (2012). Robustness of structurally equivalent concurrent parity games (Vol. 7213, pp. 270–285). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Tallinn, Estonia: Springer. <a href=\"https://doi.org/10.1007/978-3-642-28729-9_18\">https://doi.org/10.1007/978-3-642-28729-9_18</a>","ieee":"K. Chatterjee, “Robustness of structurally equivalent concurrent parity games,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Tallinn, Estonia, 2012, vol. 7213, pp. 270–285.","ama":"Chatterjee K. Robustness of structurally equivalent concurrent parity games. In: Vol 7213. Springer; 2012:270-285. doi:<a href=\"https://doi.org/10.1007/978-3-642-28729-9_18\">10.1007/978-3-642-28729-9_18</a>","ista":"Chatterjee K. 2012. Robustness of structurally equivalent concurrent parity games. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 7213, 270–285.","mla":"Chatterjee, Krishnendu. <i>Robustness of Structurally Equivalent Concurrent Parity Games</i>. Vol. 7213, Springer, 2012, pp. 270–85, doi:<a href=\"https://doi.org/10.1007/978-3-642-28729-9_18\">10.1007/978-3-642-28729-9_18</a>.","short":"K. Chatterjee, in:, Springer, 2012, pp. 270–285.","chicago":"Chatterjee, Krishnendu. “Robustness of Structurally Equivalent Concurrent Parity Games,” 7213:270–85. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-28729-9_18\">https://doi.org/10.1007/978-3-642-28729-9_18</a>."},"date_published":"2012-03-22T00:00:00Z","fulldoi":"https://doi.org/10.1007/978-3-642-28729-9_18","publist_id":"3284","date_updated":"2024-10-09T20:54:38Z","alternative_title":["LNCS"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"We consider two-player stochastic games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine a probability distribution over the successor states. We also consider the important special case of turn-based stochastic games where players make moves in turns, rather than concurrently. We study concurrent games with \\omega-regular winning conditions specified as parity objectives. The value for player 1 for a parity objective is the maximal probability with which the player can guarantee the satisfaction of the objective against all strategies of the opponent. We study the problem of continuity and robustness of the value function in concurrent and turn-based stochastic parity gameswith respect to imprecision in the transition probabilities. We present quantitative bounds on the difference of the value function (in terms of the imprecision of the transition probabilities) and show the value continuity for structurally equivalent concurrent games (two games are structurally equivalent if the support of the transition function is same and the probabilities differ). We also show robustness of optimal strategies for structurally equivalent turn-based stochastic parity games. Finally we show that the value continuity property breaks without the structurally equivalent assumption (even for Markov chains) and show that our quantitative bound is asymptotically optimal. Hence our results are tight (the assumption is both necessary and sufficient) and optimal (our quantitative bound is asymptotically optimal).","lang":"eng"}],"ec_funded":1}]