--- _id: '3250' 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. alternative_title: - LNCS author: - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 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' 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' 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. 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.' 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.' 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. conference: end_date: 2012-01-27 location: Špindlerův Mlýn, Czech Republic name: 'SOFSEM: Current Trends in Theory and Practice of Computer Science' start_date: 2012-01-21 date_created: 2018-12-11T12:02:15Z date_published: 2012-02-19T00:00:00Z date_updated: 2021-01-12T07:42:07Z day: '19' department: - _id: KrPi doi: 10.1007/978-3-642-27660-6_9 intvolume: ' 7147' language: - iso: eng month: '02' oa_version: None page: 99 - 114 publication_status: published publisher: Springer publist_id: '3407' quality_controlled: '1' scopus_import: 1 status: public title: Cryptography from learning parity with noise type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 7147 year: '2012' ... --- _id: '3256' 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. 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. author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Michael full_name: Kerber, Michael id: 36E4574A-F248-11E8-B48F-1D18A9856A87 last_name: Kerber orcid: 0000-0002-8030-9299 citation: 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 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 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. 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. ista: Edelsbrunner H, Kerber M. 2012. Dual complexes of cubical subdivisions of ℝn. Discrete & Computational Geometry. 47(2), 393–414. 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. date_created: 2018-12-11T12:02:17Z date_published: 2012-03-01T00:00:00Z date_updated: 2021-01-12T07:42:10Z day: '01' ddc: - '000' department: - _id: HeEd doi: 10.1007/s00454-011-9382-4 file: - access_level: open_access checksum: 76486f3b2c9e7fd81342f3832ca387e7 content_type: application/pdf creator: system date_created: 2018-12-12T10:08:15Z date_updated: 2020-07-14T12:46:05Z file_id: '4675' file_name: IST-2016-543-v1+1_2012-J-08-HierarchyCubeComplex.pdf file_size: 203636 relation: main_file file_date_updated: 2020-07-14T12:46:05Z has_accepted_license: '1' intvolume: ' 47' issue: '2' language: - iso: eng month: '03' oa: 1 oa_version: Submitted Version page: 393 - 414 publication: Discrete & Computational Geometry publication_status: published publisher: Springer publist_id: '3398' pubrep_id: '543' quality_controlled: '1' scopus_import: 1 status: public title: Dual complexes of cubical subdivisions of ℝn type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 47 year: '2012' ... --- _id: '3254' 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.' 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.' author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X citation: 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 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 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. ieee: K. Chatterjee, “The complexity of stochastic Müller games,” Information and Computation, vol. 211. Elsevier, pp. 29–48, 2012. ista: Chatterjee K. 2012. The complexity of stochastic Müller games. Information and Computation. 211, 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. short: K. Chatterjee, Information and Computation 211 (2012) 29–48. date_created: 2018-12-11T12:02:17Z date_published: 2012-02-01T00:00:00Z date_updated: 2021-01-12T07:42:09Z day: '01' department: - _id: KrCh doi: 10.1016/j.ic.2011.11.004 ec_funded: 1 intvolume: ' 211' language: - iso: eng main_file_link: - url: http://arise.or.at/pubpdf/The_complexity_of_stochastic_M___u_ller_games.pdf month: '02' oa_version: None page: 29 - 48 project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication: Information and Computation publication_status: published publisher: Elsevier publist_id: '3403' quality_controlled: '1' scopus_import: 1 status: public title: The complexity of stochastic Müller games type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 211 year: '2012' ... --- _id: '3253' 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. acknowledgement: This work was partly supported by the French National Research Agency (ANR) project Veridyc (ANR-09-SEGI-016). alternative_title: - LNCS author: - first_name: Ahmed full_name: Bouajjani, Ahmed last_name: Bouajjani - first_name: Cezara full_name: Dragoi, Cezara id: 2B2B5ED0-F248-11E8-B48F-1D18A9856A87 last_name: Dragoi - first_name: Constantin full_name: Enea, Constantin last_name: Enea - first_name: Mihaela full_name: Sighireanu, Mihaela last_name: Sighireanu 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: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' 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. 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.' 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. short: A. Bouajjani, C. Dragoi, C. Enea, M. Sighireanu, in:, Springer, 2012, pp. 1–22. conference: end_date: 2012-01-24 location: Philadelphia, PA, USA name: 'VMCAI: Verification, Model Checking and Abstract Interpretation' start_date: 2012-01-22 date_created: 2018-12-11T12:02:17Z date_published: 2012-02-26T00:00:00Z date_updated: 2021-01-12T07:42:09Z day: '26' department: - _id: ToHe doi: 10.1007/978-3-642-27940-9_1 intvolume: ' 7148' language: - iso: eng month: '02' oa_version: None page: 1 - 22 publication_status: published publisher: Springer publist_id: '3404' quality_controlled: '1' status: public title: Abstract domains for automated reasoning about list manipulating programs with infinite data type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 7148 year: '2012' ... --- _id: '3265' 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. article_number: '6126486' author: - first_name: Adrian full_name: Ion, Adrian id: 29F89302-F248-11E8-B48F-1D18A9856A87 last_name: Ion - first_name: Joao full_name: Carreira, Joao last_name: Carreira - first_name: Cristian full_name: Sminchisescu, Cristian last_name: Sminchisescu citation: 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' 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' 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. 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.' ista: 'Ion A, Carreira J, Sminchisescu C. 2012. Image segmentation by figure-ground composition into maximal cliques. ICCV: International Conference on Computer Vision, 6126486.' mla: Ion, Adrian, et al. Image Segmentation by Figure-Ground Composition into Maximal Cliques. 6126486, IEEE, 2012, doi:10.1109/ICCV.2011.6126486. short: A. Ion, J. Carreira, C. Sminchisescu, in:, IEEE, 2012. conference: end_date: 2011-11-13 location: Barcelona, Spain name: 'ICCV: International Conference on Computer Vision' start_date: 2011-11-06 date_created: 2018-12-11T12:02:21Z date_published: 2012-01-12T00:00:00Z date_updated: 2021-01-12T07:42:15Z day: '12' department: - _id: HeEd doi: 10.1109/ICCV.2011.6126486 language: - iso: eng month: '01' oa_version: None publication_status: published publisher: IEEE publist_id: '3382' quality_controlled: '1' status: public title: Image segmentation by figure-ground composition into maximal cliques type: conference user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87 year: '2012' ...