[{"title":"Cryptography from learning parity with noise","publication_status":"published","status":"public","intvolume":" 7147","publisher":"Springer","department":[{"_id":"KrPi"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"3250","year":"2012","date_created":"2018-12-11T12:02:15Z","date_updated":"2021-01-12T07:42:07Z","volume":7147,"oa_version":"None","author":[{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"}],"alternative_title":["LNCS"],"type":"conference","abstract":[{"lang":"eng","text":"The Learning Parity with Noise (LPN) problem has recently found many applications in cryptography as the hardness assumption underlying the constructions of "provably secure" 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."}],"publist_id":"3407","quality_controlled":"1","page":"99 - 114","citation":{"ama":"Pietrzak KZ. Cryptography from learning parity with noise. In: Vol 7147. Springer; 2012:99-114. doi:10.1007/978-3-642-27660-6_9","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.","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. https://doi.org/10.1007/978-3-642-27660-6_9","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.","mla":"Pietrzak, Krzysztof Z. Cryptography from Learning Parity with Noise. Vol. 7147, Springer, 2012, pp. 99–114, doi:10.1007/978-3-642-27660-6_9.","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. https://doi.org/10.1007/978-3-642-27660-6_9."},"language":[{"iso":"eng"}],"conference":{"name":"SOFSEM: Current Trends in Theory and Practice of Computer Science","location":"Špindlerův Mlýn, Czech Republic","start_date":"2012-01-21","end_date":"2012-01-27"},"doi":"10.1007/978-3-642-27660-6_9","date_published":"2012-02-19T00:00:00Z","scopus_import":1,"day":"19","month":"02"},{"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."}],"issue":"2","type":"journal_article","oa_version":"Submitted Version","file":[{"file_size":203636,"content_type":"application/pdf","creator":"system","access_level":"open_access","file_name":"IST-2016-543-v1+1_2012-J-08-HierarchyCubeComplex.pdf","checksum":"76486f3b2c9e7fd81342f3832ca387e7","date_created":"2018-12-12T10:08:15Z","date_updated":"2020-07-14T12:46:05Z","relation":"main_file","file_id":"4675"}],"pubrep_id":"543","title":"Dual complexes of cubical subdivisions of ℝn","ddc":["000"],"status":"public","intvolume":" 47","_id":"3256","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","day":"01","has_accepted_license":"1","scopus_import":1,"date_published":"2012-03-01T00:00:00Z","page":"393 - 414","publication":"Discrete & Computational Geometry","citation":{"chicago":"Edelsbrunner, Herbert, and Michael Kerber. “Dual Complexes of Cubical Subdivisions of ℝn.” Discrete & Computational Geometry. Springer, 2012. https://doi.org/10.1007/s00454-011-9382-4.","mla":"Edelsbrunner, Herbert, and Michael Kerber. “Dual Complexes of Cubical Subdivisions of ℝn.” Discrete & Computational Geometry, vol. 47, no. 2, Springer, 2012, pp. 393–414, doi:10.1007/s00454-011-9382-4.","short":"H. Edelsbrunner, M. Kerber, Discrete & Computational Geometry 47 (2012) 393–414.","ista":"Edelsbrunner H, Kerber M. 2012. Dual complexes of cubical subdivisions of ℝn. Discrete & Computational Geometry. 47(2), 393–414.","ieee":"H. Edelsbrunner and M. Kerber, “Dual complexes of cubical subdivisions of ℝn,” Discrete & Computational Geometry, vol. 47, no. 2. Springer, pp. 393–414, 2012.","apa":"Edelsbrunner, H., & Kerber, M. (2012). Dual complexes of cubical subdivisions of ℝn. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-011-9382-4","ama":"Edelsbrunner H, Kerber M. Dual complexes of cubical subdivisions of ℝn. Discrete & Computational Geometry. 2012;47(2):393-414. doi:10.1007/s00454-011-9382-4"},"file_date_updated":"2020-07-14T12:46:05Z","publist_id":"3398","date_created":"2018-12-11T12:02:17Z","date_updated":"2021-01-12T07:42:10Z","volume":47,"author":[{"orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"full_name":"Kerber, Michael","first_name":"Michael","last_name":"Kerber","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8030-9299"}],"publication_status":"published","publisher":"Springer","department":[{"_id":"HeEd"}],"year":"2012","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.","month":"03","language":[{"iso":"eng"}],"doi":"10.1007/s00454-011-9382-4","quality_controlled":"1","oa":1},{"publication_status":"published","publisher":"Elsevier","department":[{"_id":"KrCh"}],"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.","date_created":"2018-12-11T12:02:17Z","date_updated":"2021-01-12T07:42:09Z","volume":211,"author":[{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"}],"publist_id":"3403","ec_funded":1,"quality_controlled":"1","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"main_file_link":[{"url":"http://arise.or.at/pubpdf/The_complexity_of_stochastic_M___u_ller_games.pdf"}],"language":[{"iso":"eng"}],"doi":"10.1016/j.ic.2011.11.004","month":"02","status":"public","title":"The complexity of stochastic Müller games","intvolume":" 211","_id":"3254","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa_version":"None","type":"journal_article","abstract":[{"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.","lang":"eng"}],"page":"29 - 48","publication":"Information and Computation","citation":{"short":"K. Chatterjee, Information and Computation 211 (2012) 29–48.","mla":"Chatterjee, Krishnendu. “The Complexity of Stochastic Müller Games.” Information and Computation, vol. 211, Elsevier, 2012, pp. 29–48, doi:10.1016/j.ic.2011.11.004.","chicago":"Chatterjee, Krishnendu. “The Complexity of Stochastic Müller Games.” Information and Computation. Elsevier, 2012. https://doi.org/10.1016/j.ic.2011.11.004.","ama":"Chatterjee K. The complexity of stochastic Müller games. Information and Computation. 2012;211:29-48. doi:10.1016/j.ic.2011.11.004","ieee":"K. Chatterjee, “The complexity of stochastic Müller games,” Information and Computation, vol. 211. Elsevier, pp. 29–48, 2012.","apa":"Chatterjee, K. (2012). The complexity of stochastic Müller games. Information and Computation. Elsevier. https://doi.org/10.1016/j.ic.2011.11.004","ista":"Chatterjee K. 2012. The complexity of stochastic Müller games. Information and Computation. 211, 29–48."},"date_published":"2012-02-01T00:00:00Z","scopus_import":1,"day":"01"},{"publist_id":"3404","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."}],"type":"conference","alternative_title":["LNCS"],"author":[{"first_name":"Ahmed","last_name":"Bouajjani","full_name":"Bouajjani, Ahmed"},{"first_name":"Cezara","last_name":"Dragoi","id":"2B2B5ED0-F248-11E8-B48F-1D18A9856A87","full_name":"Dragoi, Cezara"},{"full_name":"Enea, Constantin","first_name":"Constantin","last_name":"Enea"},{"first_name":"Mihaela","last_name":"Sighireanu","full_name":"Sighireanu, Mihaela"}],"volume":7148,"oa_version":"None","date_updated":"2021-01-12T07:42:09Z","date_created":"2018-12-11T12:02:17Z","acknowledgement":"This work was partly supported by the French National Research Agency (ANR) project Veridyc (ANR-09-SEGI-016).","_id":"3253","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","year":"2012","intvolume":" 7148","publisher":"Springer","department":[{"_id":"ToHe"}],"status":"public","title":"Abstract domains for automated reasoning about list manipulating programs with infinite data","publication_status":"published","month":"02","day":"26","date_published":"2012-02-26T00:00:00Z","doi":"10.1007/978-3-642-27940-9_1","conference":{"end_date":"2012-01-24","location":"Philadelphia, PA, USA","start_date":"2012-01-22","name":"VMCAI: Verification, Model Checking and Abstract Interpretation"},"language":[{"iso":"eng"}],"citation":{"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. https://doi.org/10.1007/978-3-642-27940-9_1.","short":"A. Bouajjani, C. Dragoi, C. Enea, M. Sighireanu, in:, Springer, 2012, pp. 1–22.","mla":"Bouajjani, Ahmed, et al. Abstract Domains for Automated Reasoning about List Manipulating Programs with Infinite Data. Vol. 7148, Springer, 2012, pp. 1–22, doi:10.1007/978-3-642-27940-9_1.","apa":"Bouajjani, A., Dragoi, C., Enea, C., & 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. https://doi.org/10.1007/978-3-642-27940-9_1","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.","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.","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:10.1007/978-3-642-27940-9_1"},"page":"1 - 22","quality_controlled":"1"},{"date_created":"2018-12-11T12:02:21Z","date_updated":"2021-01-12T07:42:15Z","oa_version":"None","author":[{"full_name":"Ion, Adrian","last_name":"Ion","first_name":"Adrian","id":"29F89302-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Joao","last_name":"Carreira","full_name":"Carreira, Joao"},{"last_name":"Sminchisescu","first_name":"Cristian","full_name":"Sminchisescu, Cristian"}],"status":"public","publication_status":"published","title":"Image segmentation by figure-ground composition into maximal cliques","department":[{"_id":"HeEd"}],"publisher":"IEEE","_id":"3265","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","year":"2012","abstract":[{"lang":"eng","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."}],"publist_id":"3382","article_number":"6126486","type":"conference","language":[{"iso":"eng"}],"conference":{"location":"Barcelona, Spain","start_date":"2011-11-06","end_date":"2011-11-13","name":"ICCV: International Conference on Computer Vision"},"date_published":"2012-01-12T00:00:00Z","doi":"10.1109/ICCV.2011.6126486","quality_controlled":"1","citation":{"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., & Sminchisescu, C. (2012). Image segmentation by figure-ground composition into maximal cliques. Presented at the ICCV: International Conference on Computer Vision, Barcelona, Spain: IEEE. https://doi.org/10.1109/ICCV.2011.6126486","ista":"Ion A, Carreira J, Sminchisescu C. 2012. Image segmentation by figure-ground composition into maximal cliques. ICCV: International Conference on Computer Vision, 6126486.","ama":"Ion A, Carreira J, Sminchisescu C. Image segmentation by figure-ground composition into maximal cliques. In: IEEE; 2012. doi:10.1109/ICCV.2011.6126486","chicago":"Ion, Adrian, Joao Carreira, and Cristian Sminchisescu. “Image Segmentation by Figure-Ground Composition into Maximal Cliques.” IEEE, 2012. https://doi.org/10.1109/ICCV.2011.6126486.","short":"A. Ion, J. Carreira, C. Sminchisescu, in:, IEEE, 2012.","mla":"Ion, Adrian, et al. Image Segmentation by Figure-Ground Composition into Maximal Cliques. 6126486, IEEE, 2012, doi:10.1109/ICCV.2011.6126486."},"month":"01","day":"12"},{"date_published":"2012-03-10T00:00:00Z","citation":{"short":"Y. Dodis, K.Z. Pietrzak, E. Kiltz, D. Wichs, in:, Springer, 2012, pp. 355–374.","mla":"Dodis, Yevgeniy, et al. Message Authentication, Revisited. Vol. 7237, Springer, 2012, pp. 355–74, doi:10.1007/978-3-642-29011-4_22.","chicago":"Dodis, Yevgeniy, Krzysztof Z Pietrzak, Eike Kiltz, and Daniel Wichs. “Message Authentication, Revisited,” 7237:355–74. Springer, 2012. https://doi.org/10.1007/978-3-642-29011-4_22.","ama":"Dodis Y, Pietrzak KZ, Kiltz E, Wichs D. Message authentication, revisited. In: Vol 7237. Springer; 2012:355-374. doi:10.1007/978-3-642-29011-4_22","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., & Wichs, D. (2012). Message authentication, revisited (Vol. 7237, pp. 355–374). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Cambridge, UK: Springer. https://doi.org/10.1007/978-3-642-29011-4_22","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."},"page":"355 - 374","day":"10","has_accepted_license":"1","pubrep_id":"686","file":[{"creator":"system","content_type":"application/pdf","file_size":372292,"file_name":"IST-2016-686-v1+1_059.pdf","access_level":"open_access","date_created":"2018-12-12T10:14:23Z","date_updated":"2020-07-14T12:46:06Z","checksum":"8557c17a8c2586d06ebfe62d934f5c5f","file_id":"5074","relation":"main_file"}],"oa_version":"Submitted Version","_id":"3282","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","ddc":["000","004"],"status":"public","title":"Message authentication, revisited","intvolume":" 7237","abstract":[{"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 "message-hiding" 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.","lang":"eng"}],"type":"conference","alternative_title":["LNCS"],"conference":{"end_date":"2012-04-19","location":"Cambridge, UK","start_date":"2012-04-15","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques"},"doi":"10.1007/978-3-642-29011-4_22","language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","project":[{"grant_number":"259668","_id":"258C570E-B435-11E9-9278-68D0E5697425","name":"Provable Security for Physical Cryptography","call_identifier":"FP7"}],"month":"03","author":[{"last_name":"Dodis","first_name":"Yevgeniy","full_name":"Dodis, Yevgeniy"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z"},{"first_name":"Eike","last_name":"Kiltz","full_name":"Kiltz, Eike"},{"full_name":"Wichs, Daniel","first_name":"Daniel","last_name":"Wichs"}],"date_created":"2018-12-11T12:02:27Z","date_updated":"2021-01-12T07:42:22Z","volume":7237,"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)","publication_status":"published","publisher":"Springer","department":[{"_id":"KrPi"}],"file_date_updated":"2020-07-14T12:46:06Z","ec_funded":1,"publist_id":"3364"},{"conference":{"name":"TCC: Theory of Cryptography Conference","location":"Taormina, Sicily, Italy","start_date":"2012-03-19","end_date":"2012-03-21"},"doi":"10.1007/978-3-642-28914-9_31","language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"open_access":"1","url":"http://www.iacr.org/archive/tcc2012/71940166/71940166.pdf"}],"quality_controlled":"1","project":[{"grant_number":"259668","_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Provable Security for Physical Cryptography"}],"month":"05","author":[{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"}],"date_created":"2018-12-11T12:02:26Z","date_updated":"2021-01-12T07:42:21Z","volume":7194,"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).","publication_status":"published","publisher":"Springer","department":[{"_id":"KrPi"}],"ec_funded":1,"publist_id":"3366","date_published":"2012-05-04T00:00:00Z","citation":{"apa":"Pietrzak, K. Z. (2012). Subspace LWE (Vol. 7194, pp. 548–563). Presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy: Springer. https://doi.org/10.1007/978-3-642-28914-9_31","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:10.1007/978-3-642-28914-9_31","chicago":"Pietrzak, Krzysztof Z. “Subspace LWE,” 7194:548–63. Springer, 2012. https://doi.org/10.1007/978-3-642-28914-9_31.","short":"K.Z. Pietrzak, in:, Springer, 2012, pp. 548–563.","mla":"Pietrzak, Krzysztof Z. Subspace LWE. Vol. 7194, Springer, 2012, pp. 548–63, doi:10.1007/978-3-642-28914-9_31."},"page":"548 - 563","day":"04","oa_version":"Submitted Version","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"3280","title":"Subspace LWE","status":"public","intvolume":" 7194","abstract":[{"lang":"eng","text":"The (decisional) learning with errors problem (LWE) asks to distinguish "noisy" 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 "subspace LWE" (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. "}],"type":"conference","alternative_title":["LNCS"]},{"language":[{"iso":"eng"}],"date_published":"2012-05-04T00:00:00Z","doi":"10.1007/978-3-642-28914-9_26","conference":{"name":"TCC: Theory of Cryptography Conference","location":"Taormina, Sicily, Italy","start_date":"2012-03-19","end_date":"2012-03-21"},"page":"458 - 475","quality_controlled":"1","citation":{"ama":"Pietrzak KZ, Rosen A, Segev G. Lossy functions do not amplify well. In: Vol 7194. Springer; 2012:458-475. doi:10.1007/978-3-642-28914-9_26","apa":"Pietrzak, K. Z., Rosen, A., & 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. https://doi.org/10.1007/978-3-642-28914-9_26","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.","ista":"Pietrzak KZ, Rosen A, Segev G. 2012. Lossy functions do not amplify well. TCC: Theory of Cryptography Conference, LNCS, vol. 7194, 458–475.","short":"K.Z. Pietrzak, A. Rosen, G. Segev, in:, Springer, 2012, pp. 458–475.","mla":"Pietrzak, Krzysztof Z., et al. Lossy Functions Do Not Amplify Well. Vol. 7194, Springer, 2012, pp. 458–75, doi:10.1007/978-3-642-28914-9_26.","chicago":"Pietrzak, Krzysztof Z, Alon Rosen, and Gil Segev. “Lossy Functions Do Not Amplify Well,” 7194:458–75. Springer, 2012. https://doi.org/10.1007/978-3-642-28914-9_26."},"main_file_link":[{"url":"http://www.iacr.org/archive/tcc2012/tcc2012-index.html"}],"month":"05","day":"04","volume":7194,"oa_version":"None","date_created":"2018-12-11T12:02:26Z","date_updated":"2021-01-12T07:42:22Z","author":[{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"},{"last_name":"Rosen","first_name":"Alon","full_name":"Rosen, Alon"},{"last_name":"Segev","first_name":"Gil","full_name":"Segev, Gil"}],"department":[{"_id":"KrPi"}],"publisher":"Springer","intvolume":" 7194","title":"Lossy functions do not amplify well","status":"public","publication_status":"published","_id":"3281","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","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publist_id":"3365","abstract":[{"text":"We consider the problem of amplifying the "lossiness" 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 "lossy functions," 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"}],"alternative_title":["LNCS"],"type":"conference"},{"type":"conference","publist_id":"3362","abstract":[{"text":"We study the complexity of valued constraint satisfaction problems (VCSP). A problem from VCSP is characterised by a constraint language, a fixed set of cost functions over a finite domain. An instance of the problem is specified by a sum of cost functions from the language and the goal is to minimise the sum. Under the unique games conjecture, the approximability of finite-valued VCSPs is well-understood, see Raghavendra [FOCS’08]. However, there is no characterisation of finite-valued VCSPs, let alone general-valued VCSPs, that can be solved exactly in polynomial time, thus giving insights from a combinatorial optimisation perspective.\nWe consider the case of languages containing all possible unary cost functions. In the case of languages consisting of only {0, ∞}-valued cost functions (i.e. relations), such languages have been called conservative and studied by Bulatov [LICS’03] and recently by Barto [LICS’11]. Since we study valued languages, we call a language conservative if it contains all finite-valued unary cost functions. The computational complexity of conservative valued languages has been studied by Cohen et al. [AIJ’06] for languages over Boolean domains, by Deineko et al. [JACM’08] for {0,1}-valued languages (a.k.a Max-CSP), and by Takhanov [STACS’10] for {0,∞}-valued languages containing all finite- valued unary cost functions (a.k.a. Min-Cost-Hom).\nWe prove a Schaefer-like dichotomy theorem for conservative valued languages: if all cost functions in the language satisfy a certain condition (specified by a complementary combination of STP and MJN multimorphisms), then any instance can be solved in polynomial time (via a new algorithm developed in this paper), otherwise the language is NP-hard. This is the first complete complexity classification of general-valued constraint languages over non-Boolean domains. It is a common phenomenon that complexity classifications of problems over non-Boolean domains is significantly harder than the Boolean case. The polynomial-time algorithm we present for the tractable cases is a generalisation of the submodular minimisation problem and a result of Cohen et al. [TCS’08].\nOur results generalise previous results by Takhanov [STACS’10] and (a subset of results) by Cohen et al. [AIJ’06] and Deineko et al. [JACM’08]. Moreover, our results do not rely on any computer-assisted search as in Deineko et al. [JACM’08], and provide a powerful tool for proving hardness of finite-valued and general-valued languages.","lang":"eng"}],"extern":1,"_id":"3284","year":"2012","acknowledgement":"Vladimir Kolmogorov is supported by the Royal Academy of Eng ineering/EPSRC.","publisher":"SIAM","title":"The complexity of conservative valued CSPs","status":"public","publication_status":"published","author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov","full_name":"Vladimir Kolmogorov"},{"last_name":"Živný","first_name":"Stanislav","full_name":"Živný, Stanislav"}],"date_created":"2018-12-11T12:02:27Z","date_updated":"2021-01-12T07:42:23Z","day":"01","month":"01","citation":{"chicago":"Kolmogorov, Vladimir, and Stanislav Živný. “The Complexity of Conservative Valued CSPs,” 750–59. SIAM, 2012.","mla":"Kolmogorov, Vladimir, and Stanislav Živný. The Complexity of Conservative Valued CSPs. SIAM, 2012, pp. 750–59.","short":"V. Kolmogorov, S. Živný, in:, SIAM, 2012, pp. 750–759.","ista":"Kolmogorov V, Živný S. 2012. The complexity of conservative valued CSPs. SODA: Symposium on Discrete Algorithms, 750–759.","apa":"Kolmogorov, V., & Živný, S. (2012). The complexity of conservative valued CSPs (pp. 750–759). Presented at the SODA: Symposium on Discrete Algorithms, SIAM.","ieee":"V. Kolmogorov and S. Živný, “The complexity of conservative valued CSPs,” presented at the SODA: Symposium on Discrete Algorithms, 2012, pp. 750–759.","ama":"Kolmogorov V, Živný S. The complexity of conservative valued CSPs. In: SIAM; 2012:750-759."},"oa":1,"main_file_link":[{"url":"http://arxiv.org/abs/1008.1555","open_access":"1"}],"page":"750 - 759","quality_controlled":0,"date_published":"2012-01-01T00:00:00Z","conference":{"name":"SODA: Symposium on Discrete Algorithms"}},{"day":"02","month":"01","article_processing_charge":"No","doi":"10.1021/ja209688a","date_published":"2012-01-02T00:00:00Z","language":[{"iso":"eng"}],"publication":"Journal of the American Chemical Society","citation":{"ama":"Shavel A, Cadavid D, Ibáñez M, Carrete A, Cabot A. Continuous production of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor. Journal of the American Chemical Society. 2012;134(3):1438-1441. doi:10.1021/ja209688a","ista":"Shavel A, Cadavid D, Ibáñez M, Carrete A, Cabot A. 2012. Continuous production of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor. Journal of the American Chemical Society. 134(3), 1438–1441.","apa":"Shavel, A., Cadavid, D., Ibáñez, M., Carrete, A., & Cabot, A. (2012). Continuous production of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor. Journal of the American Chemical Society. ACS. https://doi.org/10.1021/ja209688a","ieee":"A. Shavel, D. Cadavid, M. Ibáñez, A. Carrete, and A. Cabot, “Continuous production of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor,” Journal of the American Chemical Society, vol. 134, no. 3. ACS, pp. 1438–1441, 2012.","mla":"Shavel, Alexey, et al. “Continuous Production of Cu Inf 2 Inf ZnSnS Inf 4 Inf Nanocrystals in a Flow Reactor.” Journal of the American Chemical Society, vol. 134, no. 3, ACS, 2012, pp. 1438–41, doi:10.1021/ja209688a.","short":"A. Shavel, D. Cadavid, M. Ibáñez, A. Carrete, A. Cabot, Journal of the American Chemical Society 134 (2012) 1438–1441.","chicago":"Shavel, Alexey, Doris Cadavid, Maria Ibáñez, Alex Carrete, and Andreu Cabot. “Continuous Production of Cu Inf 2 Inf ZnSnS Inf 4 Inf Nanocrystals in a Flow Reactor.” Journal of the American Chemical Society. ACS, 2012. https://doi.org/10.1021/ja209688a."},"article_type":"original","quality_controlled":"1","page":"1438 - 1441","abstract":[{"text":"A procedure for the continuous production of Cu 2ZnSnS 4 (CZTS) nanoparticles with controlled composition is presented. CZTS nanoparticles were prepared through the reaction of the metals' amino complexes with elemental sulfur in a continuous-flow reactor at moderate temperatures (300-330 °C). High-resolution transmission electron microscopy and X-ray diffraction analysis showed the nanocrystals to have a crystallographic structure compatible with that of the kesterite. Chemical characterization of the materials showed the presence of the four elements in each individual nanocrystal. Composition control was achieved by adjusting the solution flow rate through the reactor and the proper choice of the nominal precursor concentration within the flowing solution. Single-particle analysis revealed a composition distribution within each sample, which was optimized at the highest synthesis temperatures used. ","lang":"eng"}],"publist_id":"7531","issue":"3","extern":"1","type":"journal_article","author":[{"last_name":"Shavel","first_name":"Alexey","full_name":"Shavel, Alexey"},{"last_name":"Cadavid","first_name":"Doris","full_name":"Cadavid, Doris"},{"last_name":"Ibáñez","first_name":"Maria","orcid":"0000-0001-5013-2843","id":"43C61214-F248-11E8-B48F-1D18A9856A87","full_name":"Ibáñez, Maria"},{"first_name":"Alex","last_name":"Carrete","full_name":"Carrete, Alex"},{"full_name":"Cabot, Andreu","last_name":"Cabot","first_name":"Andreu"}],"date_created":"2018-12-11T11:45:51Z","date_updated":"2021-01-12T07:42:29Z","oa_version":"None","volume":134,"_id":"330","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2012","status":"public","publication_status":"published","title":"Continuous production of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor","publisher":"ACS","intvolume":" 134"},{"scopus_import":1,"day":"01","has_accepted_license":"1","page":"7 - 21","publication":"Nature Reviews Neuroscience","citation":{"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.” Nature Reviews Neuroscience. Nature Publishing Group, 2012. https://doi.org/10.1038/nrn3125.","short":"E. Eggermann, I. Bucurenciu, S. Goswami, P.M. Jonas, Nature Reviews Neuroscience 13 (2012) 7–21.","mla":"Eggermann, Emmanuel, et al. “Nanodomain Coupling between Ca(2+) Channels and Sensors of Exocytosis at Fast Mammalian Synapses.” Nature Reviews Neuroscience, vol. 13, no. 1, Nature Publishing Group, 2012, pp. 7–21, doi:10.1038/nrn3125.","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,” Nature Reviews Neuroscience, vol. 13, no. 1. Nature Publishing Group, pp. 7–21, 2012.","apa":"Eggermann, E., Bucurenciu, I., Goswami, S., & Jonas, P. M. (2012). Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses. Nature Reviews Neuroscience. Nature Publishing Group. https://doi.org/10.1038/nrn3125","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.","ama":"Eggermann E, Bucurenciu I, Goswami S, Jonas PM. Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses. Nature Reviews Neuroscience. 2012;13(1):7-21. doi:10.1038/nrn3125"},"date_published":"2012-01-01T00:00:00Z","type":"journal_article","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"}],"issue":"1","ddc":["570"],"status":"public","title":"Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses","intvolume":" 13","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"3317","oa_version":"Submitted Version","file":[{"relation":"main_file","file_id":"4931","checksum":"4c1c86b2f6e4e1562f5bb800b457ea9f","date_created":"2018-12-12T10:12:13Z","date_updated":"2020-07-14T12:46:07Z","access_level":"open_access","file_name":"IST-2017-820-v1+1_17463_3_art_file_109404_ltmxbw.pdf","file_size":314246,"content_type":"application/pdf","creator":"system"},{"access_level":"open_access","file_name":"IST-2017-820-v1+2_17463_3_figure_109402_ltmwlp.pdf","file_size":1840216,"content_type":"application/pdf","creator":"system","relation":"main_file","file_id":"4932","checksum":"bceb2efdd49d115f4dde8486bc1be3f2","date_created":"2018-12-12T10:12:14Z","date_updated":"2020-07-14T12:46:07Z"}],"pubrep_id":"820","month":"01","quality_controlled":"1","project":[{"_id":"25BC64A8-B435-11E9-9278-68D0E5697425","grant_number":"JO_780/A5","name":"Synaptic Mechanisms of Neuronal Network Function"},{"name":"Glutamaterge synaptische Übertragung und Plastizität in hippocampalen Mikroschaltkreisen","grant_number":"SFB-TR3-TP10B","_id":"25BDE9A4-B435-11E9-9278-68D0E5697425"}],"oa":1,"language":[{"iso":"eng"}],"doi":"10.1038/nrn3125","file_date_updated":"2020-07-14T12:46:07Z","publist_id":"3322","publication_status":"published","publisher":"Nature Publishing Group","department":[{"_id":"PeJo"}],"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","date_created":"2018-12-11T12:02:38Z","date_updated":"2021-01-12T07:42:36Z","volume":13,"author":[{"full_name":"Eggermann, Emmanuel","last_name":"Eggermann","first_name":"Emmanuel","id":"34DACA34-E9AE-11E9-849C-D35BD8ADC20C"},{"full_name":"Bucurenciu, Iancu","first_name":"Iancu","last_name":"Bucurenciu","id":"4BD1D872-E9AE-11E9-9EE9-8BF4597A9E2A"},{"full_name":"Goswami, Sarit","id":"3A578F32-F248-11E8-B48F-1D18A9856A87","last_name":"Goswami","first_name":"Sarit"},{"id":"353C1B58-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5001-4804","first_name":"Peter M","last_name":"Jonas","full_name":"Jonas, Peter M"}]},{"scopus_import":1,"day":"01","month":"04","citation":{"ama":"Chatterjee K, Majumdar R. Discounting and averaging in games across time scales. International Journal of Foundations of Computer Science. 2012;23(3):609-625. doi:10.1142/S0129054112400308","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.","ieee":"K. Chatterjee and R. Majumdar, “Discounting and averaging in games across time scales,” International Journal of Foundations of Computer Science, vol. 23, no. 3. World Scientific Publishing, pp. 609–625, 2012.","apa":"Chatterjee, K., & Majumdar, R. (2012). Discounting and averaging in games across time scales. International Journal of Foundations of Computer Science. World Scientific Publishing. https://doi.org/10.1142/S0129054112400308","mla":"Chatterjee, Krishnendu, and Ritankar Majumdar. “Discounting and Averaging in Games across Time Scales.” International Journal of Foundations of Computer Science, vol. 23, no. 3, World Scientific Publishing, 2012, pp. 609–25, doi:10.1142/S0129054112400308.","short":"K. Chatterjee, R. Majumdar, International Journal of Foundations of Computer Science 23 (2012) 609–625.","chicago":"Chatterjee, Krishnendu, and Ritankar Majumdar. “Discounting and Averaging in Games across Time Scales.” International Journal of Foundations of Computer Science. World Scientific Publishing, 2012. https://doi.org/10.1142/S0129054112400308."},"publication":"International Journal of Foundations of Computer Science","project":[{"call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"page":"609 - 625","quality_controlled":"1","doi":"10.1142/S0129054112400308","date_published":"2012-04-01T00:00:00Z","language":[{"iso":"eng"}],"type":"journal_article","issue":"3","publist_id":"3326","abstract":[{"lang":"eng","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."}],"year":"2012","_id":"3314","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publisher":"World Scientific Publishing","department":[{"_id":"KrCh"}],"intvolume":" 23","status":"public","publication_status":"published","title":"Discounting and averaging in games across time scales","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"full_name":"Majumdar, Ritankar","first_name":"Ritankar","last_name":"Majumdar"}],"oa_version":"None","volume":23,"date_created":"2018-12-11T12:02:37Z","date_updated":"2021-01-12T07:42:35Z"},{"publist_id":"3584","related_material":{"record":[{"id":"3329","relation":"earlier_version","status":"public"}]},"author":[{"last_name":"Berberich","first_name":"Eric","full_name":"Berberich, Eric"},{"full_name":"Halperin, Dan","last_name":"Halperin","first_name":"Dan"},{"full_name":"Kerber, Michael","first_name":"Michael","last_name":"Kerber","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8030-9299"},{"first_name":"Roza","last_name":"Pogalnikova","full_name":"Pogalnikova, Roza"}],"volume":48,"date_updated":"2023-02-23T11:22:30Z","date_created":"2018-12-11T12:01:28Z","year":"2012","acknowledgement":"We thank Eyal Flato (Plataine Ltd.) for raising the offset-deconstruction problem in connection with wood cutting. We also thank Tim Bretl (UIUC) for suggesting the digital-pen offset-deconstruction problem. This work has been supported in part by the Israel Science Foundation (grant no. 1102/11), by the German–Israeli Foundation (grant no. 969/07), by the Hermann Minkowski–Minerva Center for Geometry at Tel Aviv University, and by the EU Project under Contract No. 255827 (CGL—Computational Geometry Learning).\r\n","publisher":"Springer","department":[{"_id":"HeEd"}],"publication_status":"published","month":"12","doi":"10.1007/s00454-012-9441-5","language":[{"iso":"eng"}],"external_id":{"arxiv":["1109.2158"]},"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1109.2158"}],"oa":1,"quality_controlled":"1","issue":"4","abstract":[{"lang":"eng","text":"We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance ε in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(nlogn)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. A variant of the algorithm, which we have implemented using the cgal library, is based on rational arithmetic and answers the same deconstruction problem up to an uncertainty parameter δ its running time additionally depends on δ. If the input shape is found to be approximable, this algorithm also computes an approximate solution for the problem. It also allows us to solve parameter-optimization problems induced by the offset-deconstruction problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution P with at most one more vertex than a vertex-minimal one."}],"type":"journal_article","oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"3115","intvolume":" 48","status":"public","title":"Deconstructing approximate offsets","day":"01","scopus_import":1,"date_published":"2012-12-01T00:00:00Z","citation":{"chicago":"Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Deconstructing Approximate Offsets.” Discrete & Computational Geometry. Springer, 2012. https://doi.org/10.1007/s00454-012-9441-5.","mla":"Berberich, Eric, et al. “Deconstructing Approximate Offsets.” Discrete & Computational Geometry, vol. 48, no. 4, Springer, 2012, pp. 964–89, doi:10.1007/s00454-012-9441-5.","short":"E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, Discrete & Computational Geometry 48 (2012) 964–989.","ista":"Berberich E, Halperin D, Kerber M, Pogalnikova R. 2012. Deconstructing approximate offsets. Discrete & Computational Geometry. 48(4), 964–989.","apa":"Berberich, E., Halperin, D., Kerber, M., & Pogalnikova, R. (2012). Deconstructing approximate offsets. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-012-9441-5","ieee":"E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Deconstructing approximate offsets,” Discrete & Computational Geometry, vol. 48, no. 4. Springer, pp. 964–989, 2012.","ama":"Berberich E, Halperin D, Kerber M, Pogalnikova R. Deconstructing approximate offsets. Discrete & Computational Geometry. 2012;48(4):964-989. doi:10.1007/s00454-012-9441-5"},"publication":"Discrete & Computational Geometry","page":"964 - 989"},{"publication":" Journal of Symbolic Computation","oa":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1104.1510"}],"citation":{"ieee":"M. Kerber and M. Sagraloff, “A worst case bound for topology computation of algebraic curves,” Journal of Symbolic Computation, vol. 47, no. 3. Elsevier, pp. 239–258, 2012.","apa":"Kerber, M., & Sagraloff, M. (2012). A worst case bound for topology computation of algebraic curves. Journal of Symbolic Computation. Elsevier. https://doi.org/10.1016/j.jsc.2011.11.001","ista":"Kerber M, Sagraloff M. 2012. A worst case bound for topology computation of algebraic curves. Journal of Symbolic Computation. 47(3), 239–258.","ama":"Kerber M, Sagraloff M. A worst case bound for topology computation of algebraic curves. Journal of Symbolic Computation. 2012;47(3):239-258. doi:10.1016/j.jsc.2011.11.001","chicago":"Kerber, Michael, and Michael Sagraloff. “A Worst Case Bound for Topology Computation of Algebraic Curves.” Journal of Symbolic Computation. Elsevier, 2012. https://doi.org/10.1016/j.jsc.2011.11.001.","short":"M. Kerber, M. Sagraloff, Journal of Symbolic Computation 47 (2012) 239–258.","mla":"Kerber, Michael, and Michael Sagraloff. “A Worst Case Bound for Topology Computation of Algebraic Curves.” Journal of Symbolic Computation, vol. 47, no. 3, Elsevier, 2012, pp. 239–58, doi:10.1016/j.jsc.2011.11.001."},"quality_controlled":"1","page":"239 - 258","date_published":"2012-03-01T00:00:00Z","doi":"10.1016/j.jsc.2011.11.001","language":[{"iso":"eng"}],"scopus_import":1,"month":"03","day":"01","_id":"3331","year":"2012","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","title":"A worst case bound for topology computation of algebraic curves","publication_status":"published","status":"public","intvolume":" 47","publisher":"Elsevier","department":[{"_id":"HeEd"}],"author":[{"full_name":"Kerber, Michael","orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","last_name":"Kerber","first_name":"Michael"},{"full_name":"Sagraloff, Michael","first_name":"Michael","last_name":"Sagraloff"}],"date_created":"2018-12-11T12:02:43Z","date_updated":"2021-01-12T07:42:43Z","oa_version":"Preprint","volume":47,"type":"journal_article","abstract":[{"lang":"eng","text":"Computing the topology of an algebraic plane curve C means computing a combinatorial graph that is isotopic to C and thus represents its topology in R2. We prove that, for a polynomial of degree n with integer coefficients bounded by 2ρ, the topology of the induced curve can be computed with bit operations ( indicates that we omit logarithmic factors). Our analysis improves the previous best known complexity bounds by a factor of n2. The improvement is based on new techniques to compute and refine isolating intervals for the real roots of polynomials, and on the consequent amortized analysis of the critical fibers of the algebraic curve."}],"publist_id":"3303","issue":"3"},{"author":[{"full_name":"Fan, Jiandong","last_name":"Fan","first_name":"Jiandong"},{"first_name":"Reza","last_name":"Zamani","full_name":"Zamani, Reza"},{"full_name":"Fábrega, Cristina","last_name":"Fábrega","first_name":"Cristina"},{"last_name":"Shavel","first_name":"Alexey","full_name":"Shavel, Alexey"},{"full_name":"Flox, Cristina","last_name":"Flox","first_name":"Cristina"},{"last_name":"Ibáñez","first_name":"Maria","orcid":"0000-0001-5013-2843","id":"43C61214-F248-11E8-B48F-1D18A9856A87","full_name":"Ibáñez, Maria"},{"full_name":"Andreu, Teresa","first_name":"Teresa","last_name":"Andreu"},{"full_name":"López, Amtonio","first_name":"Amtonio","last_name":"López"},{"first_name":"Jordi","last_name":"Arbiol","full_name":"Arbiol, Jordi"},{"full_name":"Morante, Joan","first_name":"Joan","last_name":"Morante"},{"full_name":"Cabot, Andreu","last_name":"Cabot","first_name":"Andreu"}],"volume":45,"oa_version":"None","date_updated":"2021-01-12T07:43:36Z","date_created":"2018-12-11T11:45:56Z","_id":"346","year":"2012","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"The research was supported by the European Regional Development Funds and the Spanish MICINN projects MAT2010-15138, MAT2010-21510 and CSD2009-00050. JF and AS thank the FI-DGR and BP grants from the Agència de Gestió d'Ajuts Universitaris i de Recerca (AGAUR) from the Catalan Government. MI and AC thank the Spanish MICINN for the PhD grant and the financial support through the Ramóny Cajal program.","publisher":"IOP Publishing Ltd.","intvolume":" 45","status":"public","publication_status":"published","title":"Solution-growth and optoelectronic performance of ZnO : Cl/TiO2 and ZnO : Cl/ZnxTiOy/TiO2 core–shell nanowires with tunable shell thickness","issue":"41","publist_id":"7486","abstract":[{"text":"Arrays of vertically aligned ZnO : Cl/TiO2 and ZnO : Cl/ZnxTiOy/TiO2 core–shell nanowires (NWs) were prepared by means of the combination of two solution-growth processes. First, single-crystal ZnO NWs with controlled n-type doping were grown on conducting substrates by a low-cost, high-yield and seed-free electrochemical route. These NWs were covered by a titanium oxide shell of tunable thickness mediating successive adsorption-hydrolysis-condensation steps. Using this atomic-layer growth procedure, titania shells with controlled thickness and the anatase TiO2 phase were obtained after sintering at 450 °C. Higher sintering temperatures resulted in the formation of ZnO : Cl/ZnxTiOy/TiO2 core–shell NWs by the interdiffusion of Zn and Ti ions at the ZnO–TiO2 interface. The performance of ZnO : Cl/TiO2 and ZnO : Cl/ZnxTiOy/TiO2 core–shell NWs towards photoelectrochemical (PEC) water splitting was investigated as a function of the titania shell thickness. Furthermore, the performance of such core–shell NWs as photoelectrodes in dye-sensitized solar cells was also characterized. The TiO2 presence at the ZnO : Cl surface promoted a two-fold increase on the produced photocurrent densities, probing their potential for PEC and optoelectronic applications. Electrochemical impedance spectroscopy was used to corroborate the lower resistance for charge transfer between the NWs and the electrolyte in the presence of the TiO2 shell.","lang":"eng"}],"extern":"1","type":"journal_article","doi":"10.1088/0022-3727/45/41/415301","date_published":"2012-10-17T00:00:00Z","language":[{"iso":"eng"}],"citation":{"apa":"Fan, J., Zamani, R., Fábrega, C., Shavel, A., Flox, C., Ibáñez, M., … Cabot, A. (2012). Solution-growth and optoelectronic performance of ZnO : Cl/TiO2 and ZnO : Cl/ZnxTiOy/TiO2 core–shell nanowires with tunable shell thickness. Journal of Physics D: Applied Physics. IOP Publishing Ltd. https://doi.org/10.1088/0022-3727/45/41/415301","ieee":"J. Fan et al., “Solution-growth and optoelectronic performance of ZnO : Cl/TiO2 and ZnO : Cl/ZnxTiOy/TiO2 core–shell nanowires with tunable shell thickness,” Journal of Physics D: Applied Physics, vol. 45, no. 41. IOP Publishing Ltd., 2012.","ista":"Fan J, Zamani R, Fábrega C, Shavel A, Flox C, Ibáñez M, Andreu T, López A, Arbiol J, Morante J, Cabot A. 2012. Solution-growth and optoelectronic performance of ZnO : Cl/TiO2 and ZnO : Cl/ZnxTiOy/TiO2 core–shell nanowires with tunable shell thickness. Journal of Physics D: Applied Physics. 45(41).","ama":"Fan J, Zamani R, Fábrega C, et al. Solution-growth and optoelectronic performance of ZnO : Cl/TiO2 and ZnO : Cl/ZnxTiOy/TiO2 core–shell nanowires with tunable shell thickness. Journal of Physics D: Applied Physics. 2012;45(41). doi:10.1088/0022-3727/45/41/415301","chicago":"Fan, Jiandong, Reza Zamani, Cristina Fábrega, Alexey Shavel, Cristina Flox, Maria Ibáñez, Teresa Andreu, et al. “Solution-Growth and Optoelectronic Performance of ZnO : Cl/TiO2 and ZnO : Cl/ZnxTiOy/TiO2 Core–Shell Nanowires with Tunable Shell Thickness.” Journal of Physics D: Applied Physics. IOP Publishing Ltd., 2012. https://doi.org/10.1088/0022-3727/45/41/415301.","short":"J. Fan, R. Zamani, C. Fábrega, A. Shavel, C. Flox, M. Ibáñez, T. Andreu, A. López, J. Arbiol, J. Morante, A. Cabot, Journal of Physics D: Applied Physics 45 (2012).","mla":"Fan, Jiandong, et al. “Solution-Growth and Optoelectronic Performance of ZnO : Cl/TiO2 and ZnO : Cl/ZnxTiOy/TiO2 Core–Shell Nanowires with Tunable Shell Thickness.” Journal of Physics D: Applied Physics, vol. 45, no. 41, IOP Publishing Ltd., 2012, doi:10.1088/0022-3727/45/41/415301."},"publication":"Journal of Physics D: Applied Physics","article_type":"original","quality_controlled":"1","article_processing_charge":"No","day":"17","month":"10"},{"day":"04","month":"05","scopus_import":1,"language":[{"iso":"eng"}],"doi":"10.1016/j.tcs.2011.12.059","date_published":"2012-05-04T00:00:00Z","page":"137 - 164","quality_controlled":"1","citation":{"short":"J. Feret, T.A. Henzinger, H. Koeppl, T. Petrov, Theoretical Computer Science 431 (2012) 137–164.","mla":"Feret, Jérôme, et al. “Lumpability Abstractions of Rule Based Systems.” Theoretical Computer Science, vol. 431, Elsevier, 2012, pp. 137–64, doi:10.1016/j.tcs.2011.12.059.","chicago":"Feret, Jérôme, Thomas A Henzinger, Heinz Koeppl, and Tatjana Petrov. “Lumpability Abstractions of Rule Based Systems.” Theoretical Computer Science. Elsevier, 2012. https://doi.org/10.1016/j.tcs.2011.12.059.","ama":"Feret J, Henzinger TA, Koeppl H, Petrov T. Lumpability abstractions of rule based systems. Theoretical Computer Science. 2012;431:137-164. doi:10.1016/j.tcs.2011.12.059","ieee":"J. Feret, T. A. Henzinger, H. Koeppl, and T. Petrov, “Lumpability abstractions of rule based systems,” Theoretical Computer Science, vol. 431. Elsevier, pp. 137–164, 2012.","apa":"Feret, J., Henzinger, T. A., Koeppl, H., & Petrov, T. (2012). Lumpability abstractions of rule based systems. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2011.12.059","ista":"Feret J, Henzinger TA, Koeppl H, Petrov T. 2012. Lumpability abstractions of rule based systems. Theoretical Computer Science. 431, 137–164."},"publication":"Theoretical Computer Science","publist_id":"3515","abstract":[{"lang":"eng","text":"The induction of a signaling pathway is characterized by transient complex formation and mutual posttranslational modification of proteins. To faithfully capture this combinatorial process in a mathematical model is an important challenge in systems biology. Exploiting the limited context on which most binding and modification events are conditioned, attempts have been made to reduce the combinatorial complexity by quotienting the reachable set of molecular species into species aggregates while preserving the deterministic semantics of the thermodynamic limit. Recently, we proposed a quotienting that also preserves the stochastic semantics and that is complete in the sense that the semantics of individual species can be recovered from the aggregate semantics. In this paper, we prove that this quotienting yields a sufficient condition for weak lumpability (that is to say that the quotient system is still Markovian for a given set of initial distributions) and that it gives rise to a backward Markov bisimulation between the original and aggregated transition system (which means that the conditional probability of being in a given state in the original system knowing that we are in its equivalence class is an invariant of the system). We illustrate the framework on a case study of the epidermal growth factor (EGF)/insulin receptor crosstalk."}],"type":"journal_article","volume":431,"oa_version":"None","date_updated":"2023-02-23T11:39:40Z","date_created":"2018-12-11T12:01:47Z","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"3719"}]},"pubrep_id":"73","author":[{"full_name":"Feret, Jérôme","first_name":"Jérôme","last_name":"Feret"},{"last_name":"Henzinger","first_name":"Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A"},{"full_name":"Koeppl, Heinz","first_name":"Heinz","last_name":"Koeppl"},{"orcid":"0000-0002-9041-0905","id":"3D5811FC-F248-11E8-B48F-1D18A9856A87","last_name":"Petrov","first_name":"Tatjana","full_name":"Petrov, Tatjana"}],"publisher":"Elsevier","intvolume":" 431","department":[{"_id":"ToHe"}],"status":"public","publication_status":"published","title":"Lumpability abstractions of rule based systems","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"3168","acknowledgement":"We would like to thank the anonymous reviewers for their comments on the different versions of the paper. We would also like to thank Ferdinanda Camporesi for her careful reading and the useful insights that she gave us about the paper.\r\nJérôme Feret’s contribution was partially supported by the AbstractCell ANR-Chair of Excellence. Heinz Koeppl’s research is supported by the Swiss National Science Foundation, grant no. 200020-117975/1. Tatjana Petrov’s research is supported by SystemsX.ch (the Swiss Initiative in Systems Biology).","year":"2012"},{"article_processing_charge":"No","day":"14","month":"11","language":[{"iso":"eng"}],"date_published":"2012-11-14T00:00:00Z","doi":"10.1021/cm303252q","page":"4615 - 4622","citation":{"ista":"Ibáñez M, Zamani R, Li W, Cadavid D, Gorse S, Katchoi N, Shavel A, López A, Morante J, Arbiol J, Cabot A. 2012. Crystallographic control at the nanoscale to enhance functionality: Polytypic Cu2GeSe3 nanoparticles as thermoelectric materials. Chemistry of Materials. 24(23), 4615–4622.","apa":"Ibáñez, M., Zamani, R., Li, W., Cadavid, D., Gorse, S., Katchoi, N., … Cabot, A. (2012). Crystallographic control at the nanoscale to enhance functionality: Polytypic Cu2GeSe3 nanoparticles as thermoelectric materials. Chemistry of Materials. American Chemical Society. https://doi.org/10.1021/cm303252q","ieee":"M. Ibáñez et al., “Crystallographic control at the nanoscale to enhance functionality: Polytypic Cu2GeSe3 nanoparticles as thermoelectric materials,” Chemistry of Materials, vol. 24, no. 23. American Chemical Society, pp. 4615–4622, 2012.","ama":"Ibáñez M, Zamani R, Li W, et al. Crystallographic control at the nanoscale to enhance functionality: Polytypic Cu2GeSe3 nanoparticles as thermoelectric materials. Chemistry of Materials. 2012;24(23):4615-4622. doi:10.1021/cm303252q","chicago":"Ibáñez, Maria, Reza Zamani, Wenhua Li, Doris Cadavid, Stéphane Gorse, Nebll Katchoi, Alexey Shavel, et al. “Crystallographic Control at the Nanoscale to Enhance Functionality: Polytypic Cu2GeSe3 Nanoparticles as Thermoelectric Materials.” Chemistry of Materials. American Chemical Society, 2012. https://doi.org/10.1021/cm303252q.","mla":"Ibáñez, Maria, et al. “Crystallographic Control at the Nanoscale to Enhance Functionality: Polytypic Cu2GeSe3 Nanoparticles as Thermoelectric Materials.” Chemistry of Materials, vol. 24, no. 23, American Chemical Society, 2012, pp. 4615–22, doi:10.1021/cm303252q.","short":"M. Ibáñez, R. Zamani, W. Li, D. Cadavid, S. Gorse, N. Katchoi, A. Shavel, A. López, J. Morante, J. Arbiol, A. Cabot, Chemistry of Materials 24 (2012) 4615–4622."},"publication":"Chemistry of Materials","extern":"1","publist_id":"7452","issue":"23","abstract":[{"text":"The potential to control the composition and crystal phase at the nanometer scale enable the production of nanocrystalline materials with enhanced functionalities and new applications. In the present work, we detail a novel colloidal synthesis route to prepare nanoparticles of the ternary semiconductor Cu2GeSe3 (CGSe) with nanometer-scale control over their crystal phases. We also demonstrate the structural effect on the thermoelectric properties of bottom-up-prepared CGSe nanomaterials. By careful adjustment of the nucleation and growth temperatures, pure orthorhombic CGSe nanoparticles with cationic order or polytypic CGSe nanoparticles with disordered cation positions can be produced. In this second type of nanoparticle, a high density of twins can be created to periodically change the atomic plane stacking, forming a hexagonal wurtzite CGSe phase. The high yield of the synthetic routes reported here allows the production of single-phase and multiphase CGSe nanoparticles in the gram scale, which permits characterization of the thermoelectric properties of these materials. Reduced thermal conductivities and a related 2.5-fold increase of the thermoelectric figure of merit for multiphase nanomaterials compared to pure-phase CGSe are systematically obtained. These results are discussed in terms of the density and efficiency of phonon scattering centers in both types of materials.","lang":"eng"}],"type":"journal_article","volume":24,"oa_version":"None","date_updated":"2021-01-12T07:52:04Z","date_created":"2018-12-11T11:46:07Z","author":[{"full_name":"Ibáñez, Maria","orcid":"0000-0001-5013-2843","id":"43C61214-F248-11E8-B48F-1D18A9856A87","last_name":"Ibáñez","first_name":"Maria"},{"first_name":"Reza","last_name":"Zamani","full_name":"Zamani, Reza"},{"first_name":"Wenhua","last_name":"Li","full_name":"Li, Wenhua"},{"full_name":"Cadavid, Doris","last_name":"Cadavid","first_name":"Doris"},{"last_name":"Gorse","first_name":"Stéphane","full_name":"Gorse, Stéphane"},{"full_name":"Katchoi, Nebll","first_name":"Nebll","last_name":"Katchoi"},{"full_name":"Shavel, Alexey","last_name":"Shavel","first_name":"Alexey"},{"last_name":"López","first_name":"Antonioo","full_name":"López, Antonioo"},{"first_name":"Joan","last_name":"Morante","full_name":"Morante, Joan"},{"first_name":"Jordi","last_name":"Arbiol","full_name":"Arbiol, Jordi"},{"full_name":"Cabot, Andreu","first_name":"Andreu","last_name":"Cabot"}],"intvolume":" 24","publisher":"American Chemical Society","status":"public","publication_status":"published","title":"Crystallographic control at the nanoscale to enhance functionality: Polytypic Cu2GeSe3 nanoparticles as thermoelectric materials","_id":"377","year":"2012","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"last_name":"Henzinger","first_name":"Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A"}],"date_updated":"2022-05-24T08:00:54Z","date_created":"2018-12-11T12:05:29Z","volume":78,"year":"2012","acknowledgement":"This research was supported in part by the ONR grant N00014-02-1-0671, by the AFOSR MURI grant F49620-00-1-0327, and by the NSF grants CCR-9988172, CCR-0085949, and CCR-0225610.","publication_status":"published","publisher":"Elsevier","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"file_date_updated":"2020-07-14T12:46:17Z","publist_id":"2341","doi":"10.1016/j.jcss.2011.05.002","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1016/j.jcss.2011.05.002"}],"oa":1,"quality_controlled":"1","month":"03","oa_version":"Submitted Version","file":[{"content_type":"application/pdf","file_size":336450,"creator":"kschuh","file_name":"a_survey_of_stochastic_omega-regular_games.pdf","access_level":"open_access","date_created":"2019-01-29T10:54:28Z","date_updated":"2020-07-14T12:46:17Z","checksum":"241b939deb4517cdd4426d49c67e3fa2","relation":"main_file","file_id":"5897"}],"_id":"3846","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","ddc":["000"],"title":"A survey of stochastic ω regular games","intvolume":" 78","abstract":[{"text":"We summarize classical and recent results about two-player games played on graphs with ω-regular objectives. These games have applications in the verification and synthesis of reactive systems. Important distinctions are whether a graph game is turn-based or concurrent; deterministic or stochastic; zero-sum or not. We cluster known results and open problems according to these classifications.","lang":"eng"}],"issue":"2","type":"journal_article","date_published":"2012-03-02T00:00:00Z","publication":"Journal of Computer and System Sciences","citation":{"ama":"Chatterjee K, Henzinger TA. A survey of stochastic ω regular games. Journal of Computer and System Sciences. 2012;78(2):394-413. doi:10.1016/j.jcss.2011.05.002","ieee":"K. Chatterjee and T. A. Henzinger, “A survey of stochastic ω regular games,” Journal of Computer and System Sciences, vol. 78, no. 2. Elsevier, pp. 394–413, 2012.","apa":"Chatterjee, K., & Henzinger, T. A. (2012). A survey of stochastic ω regular games. Journal of Computer and System Sciences. Elsevier. https://doi.org/10.1016/j.jcss.2011.05.002","ista":"Chatterjee K, Henzinger TA. 2012. A survey of stochastic ω regular games. Journal of Computer and System Sciences. 78(2), 394–413.","short":"K. Chatterjee, T.A. Henzinger, Journal of Computer and System Sciences 78 (2012) 394–413.","mla":"Chatterjee, Krishnendu, and Thomas A. Henzinger. “A Survey of Stochastic ω Regular Games.” Journal of Computer and System Sciences, vol. 78, no. 2, Elsevier, 2012, pp. 394–413, doi:10.1016/j.jcss.2011.05.002.","chicago":"Chatterjee, Krishnendu, and Thomas A Henzinger. “A Survey of Stochastic ω Regular Games.” Journal of Computer and System Sciences. Elsevier, 2012. https://doi.org/10.1016/j.jcss.2011.05.002."},"article_type":"original","page":"394 - 413","day":"02","article_processing_charge":"No","has_accepted_license":"1","scopus_import":"1"},{"abstract":[{"text":"In this Letter we present detailed study of the density of states near defects in Bi 2Se 3. In particular, we present data on the commonly found triangular defects in this system. While we do not find any measurable quasiparticle scattering interference effects, we do find localized resonances, which can be well fitted by theory once the potential is taken to be extended to properly account for the observed defects. The data together with the fits confirm that while the local density of states around the Dirac point of the electronic spectrum at the surface is significantly disrupted near the impurity by the creation of low-energy resonance state, the Dirac point is not locally destroyed. We discuss our results in terms of the expected protected surface state of topological insulators. © 2012 American Physical Society.","lang":"eng"}],"issue":"20","publist_id":"7442","extern":"1","type":"journal_article","author":[{"last_name":"Alpichshev","first_name":"Zhanybek","orcid":"0000-0002-7183-5203","id":"45E67A2A-F248-11E8-B48F-1D18A9856A87","full_name":"Alpichshev, Zhanybek"},{"full_name":"Biswas, Rudro","first_name":"Rudro","last_name":"Biswas"},{"last_name":"Balatsky","first_name":"Alexander","full_name":"Balatsky, Alexander"},{"last_name":"Analytis","first_name":"James","full_name":"Analytis, James"},{"first_name":"Jiunhaw","last_name":"Chu","full_name":"Chu, Jiunhaw"},{"full_name":"Fisher, Ian","last_name":"Fisher","first_name":"Ian"},{"last_name":"Kapitulnik","first_name":"Aharon","full_name":"Kapitulnik, Aharon"}],"date_updated":"2021-01-12T07:52:49Z","date_created":"2018-12-11T11:46:11Z","volume":108,"oa_version":"None","_id":"387","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2012","title":"STM imaging of impurity resonances on Bi 2Se 3","publication_status":"published","status":"public","intvolume":" 108","publisher":"American Physical Society","month":"01","day":"01","doi":"10.1103/PhysRevLett.108.206402","date_published":"2012-01-01T00:00:00Z","language":[{"iso":"eng"}],"publication":"Physical Review Letters","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1108.0022"}],"citation":{"chicago":"Alpichshev, Zhanybek, Rudro Biswas, Alexander Balatsky, James Analytis, Jiunhaw Chu, Ian Fisher, and Aharon Kapitulnik. “STM Imaging of Impurity Resonances on Bi 2Se 3.” Physical Review Letters. American Physical Society, 2012. https://doi.org/10.1103/PhysRevLett.108.206402.","short":"Z. Alpichshev, R. Biswas, A. Balatsky, J. Analytis, J. Chu, I. Fisher, A. Kapitulnik, Physical Review Letters 108 (2012).","mla":"Alpichshev, Zhanybek, et al. “STM Imaging of Impurity Resonances on Bi 2Se 3.” Physical Review Letters, vol. 108, no. 20, American Physical Society, 2012, doi:10.1103/PhysRevLett.108.206402.","ieee":"Z. Alpichshev et al., “STM imaging of impurity resonances on Bi 2Se 3,” Physical Review Letters, vol. 108, no. 20. American Physical Society, 2012.","apa":"Alpichshev, Z., Biswas, R., Balatsky, A., Analytis, J., Chu, J., Fisher, I., & Kapitulnik, A. (2012). STM imaging of impurity resonances on Bi 2Se 3. Physical Review Letters. American Physical Society. https://doi.org/10.1103/PhysRevLett.108.206402","ista":"Alpichshev Z, Biswas R, Balatsky A, Analytis J, Chu J, Fisher I, Kapitulnik A. 2012. STM imaging of impurity resonances on Bi 2Se 3. Physical Review Letters. 108(20).","ama":"Alpichshev Z, Biswas R, Balatsky A, et al. STM imaging of impurity resonances on Bi 2Se 3. Physical Review Letters. 2012;108(20). doi:10.1103/PhysRevLett.108.206402"},"oa":1},{"day":"01","month":"06","publication":"Plant Cell","citation":{"ama":"Dai M, Zhang C, Kania U, et al. A PP6 type phosphatase holoenzyme directly regulates PIN phosphorylation and auxin efflux in Arabidopsis. Plant Cell. 2012;24(6):2497-2514. doi:10.1105/tpc.112.098905","apa":"Dai, M., Zhang, C., Kania, U., Chen, F., Xue, Q., Mccray, T., … Wang, H. (2012). A PP6 type phosphatase holoenzyme directly regulates PIN phosphorylation and auxin efflux in Arabidopsis. Plant Cell. American Society of Plant Biologists. https://doi.org/10.1105/tpc.112.098905","ieee":"M. Dai et al., “A PP6 type phosphatase holoenzyme directly regulates PIN phosphorylation and auxin efflux in Arabidopsis,” Plant Cell, vol. 24, no. 6. American Society of Plant Biologists, pp. 2497–2514, 2012.","ista":"Dai M, Zhang C, Kania U, Chen F, Xue Q, Mccray T, Li G, Qin G, Wakeley M, Terzaghi W, Wan J, Zhao Y, Xu J, Friml J, Deng X, Wang H. 2012. A PP6 type phosphatase holoenzyme directly regulates PIN phosphorylation and auxin efflux in Arabidopsis. Plant Cell. 24(6), 2497–2514.","short":"M. Dai, C. Zhang, U. Kania, F. Chen, Q. Xue, T. Mccray, G. Li, G. Qin, M. Wakeley, W. Terzaghi, J. Wan, Y. Zhao, J. Xu, J. Friml, X. Deng, H. Wang, Plant Cell 24 (2012) 2497–2514.","mla":"Dai, Mingqiu, et al. “A PP6 Type Phosphatase Holoenzyme Directly Regulates PIN Phosphorylation and Auxin Efflux in Arabidopsis.” Plant Cell, vol. 24, no. 6, American Society of Plant Biologists, 2012, pp. 2497–514, doi:10.1105/tpc.112.098905.","chicago":"Dai, Mingqiu, Chen Zhang, Urszula Kania, Fang Chen, Qin Xue, Tyra Mccray, Gang Li, et al. “A PP6 Type Phosphatase Holoenzyme Directly Regulates PIN Phosphorylation and Auxin Efflux in Arabidopsis.” Plant Cell. American Society of Plant Biologists, 2012. https://doi.org/10.1105/tpc.112.098905."},"quality_controlled":0,"page":"2497 - 2514","date_published":"2012-06-01T00:00:00Z","doi":"10.1105/tpc.112.098905","type":"journal_article","abstract":[{"lang":"eng","text":"The directional transport of the phytohormone auxin depends on the phosphorylation status and polar localization of PIN-FORMED (PIN) auxin efflux proteins. While PINIOD (PID) kinase is directly involved in the phosphorylation of PIN proteins, the phosphatase holoenzyme complexes that dephosphorylate PIN proteins remain elusive. Here, we demonstrate that mutations simultaneously disrupting the function of Arabidopsis thaliana FyPP1 (for Phytochrome-associated serine/threonine protein phosphatase1) and FyPP3, two homologous genes encoding the catalytic subunits of protein phosphatase6 (PP6), cause elevated accumulation of phosphorylated PIN proteins, correlating with a basal-to-apical shift in subcellular PIN localization. The changes in PIN polarity result in increased root basipetal auxin transport and severe defects, including shorter roots, fewer lateral roots, defective columella cells, root meristem collapse, abnormal cotyledons (small, cup-shaped, or fused cotyledons), and altered leaf venation. Our molecular, biochemical, and genetic data support the notion that FyPP1/3, SAL (for SAPS DOMAIN-LIKE), and PP2AA proteins (RCN1 [for ROOTS CURL IN NAPHTHYLPHTHALAMIC ACID1] or PP2AA1, PP2AA2, and PP2AA3) physically interact to form a novel PP6-type heterotrimeric holoenzyme complex. We also show that FyPP1/3, SAL, and PP2AA interact with a subset of PIN proteins and that for SAL the strength of the interaction depends on the PIN phosphorylation status. Thus, an Arabidopsis PP6-type phosphatase holoenzyme acts antagonistically with PID to direct auxin transport polarity and plant development by directly regulating PIN phosphorylation. "}],"publist_id":"3589","issue":"6","extern":1,"_id":"3110","year":"2012","publication_status":"published","status":"public","title":"A PP6 type phosphatase holoenzyme directly regulates PIN phosphorylation and auxin efflux in Arabidopsis","intvolume":" 24","publisher":"American Society of Plant Biologists","author":[{"full_name":"Dai, Mingqiu","first_name":"Mingqiu","last_name":"Dai"},{"full_name":"Zhang, Chen","last_name":"Zhang","first_name":"Chen"},{"last_name":"Kania","first_name":"Urszula","id":"4AE5C486-F248-11E8-B48F-1D18A9856A87","full_name":"Urszula Kania"},{"full_name":"Chen, Fang","last_name":"Chen","first_name":"Fang"},{"full_name":"Xue, Qin","last_name":"Xue","first_name":"Qin"},{"first_name":"Tyra","last_name":"Mccray","full_name":"McCray, Tyra"},{"full_name":"Li, Gang","first_name":"Gang","last_name":"Li"},{"full_name":"Qin, Genji","last_name":"Qin","first_name":"Genji"},{"full_name":"Wakeley, Michelle","first_name":"Michelle","last_name":"Wakeley"},{"first_name":"William","last_name":"Terzaghi","full_name":"Terzaghi, William"},{"full_name":"Wan, Jianmin","first_name":"Jianmin","last_name":"Wan"},{"last_name":"Zhao","first_name":"Yunde","full_name":"Zhao, Yunde"},{"full_name":"Xu, Jian","last_name":"Xu","first_name":"Jian"},{"orcid":"0000-0002-8302-7596","id":"4159519E-F248-11E8-B48F-1D18A9856A87","last_name":"Friml","first_name":"Jirí","full_name":"Jirí Friml"},{"first_name":"Xing","last_name":"Deng","full_name":"Deng, Xing W"},{"first_name":"Haiyang","last_name":"Wang","full_name":"Wang, Haiyang"}],"date_updated":"2021-01-12T07:41:08Z","date_created":"2018-12-11T12:01:27Z","volume":24}]