---
_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'
...