---
_id: '1054'
abstract:
- lang: eng
text: We investigate local three-body correlations for bosonic particles in three
dimensions and one dimension as a function of the interaction strength. The three-body
correlation function g(3) is determined by measuring the three-body recombination
rate in an ultracold gas of Cs atoms. In three dimensions, we measure the dependence
of g(3) on the gas parameter in a BEC, finding good agreement with the theoretical
prediction accounting for beyond-mean-field effects. In one dimension, we observe
a reduction of g( 3) by several orders of magnitude upon increasing interactions
from the weakly interacting BEC to the strongly interacting Tonks-Girardeau regime,
in good agreement with predictions from the Lieb-Liniger model for all strengths
of interaction.
acknowledgement: We thank R. Grimm for generous support. We gratefully acknowledge
funding by the Austrian Science Fund (FWF) within Project No. I153-N16 and within
the framework of the European Science Foundation (ESF) EuroQUASAR collective research
project QuDeGPM. G. P. acknowledges funding from the EU through NAME-QUAM and AQUTE.
article_processing_charge: No
arxiv: 1
author:
- first_name: Elmar
full_name: Haller, Elmar
last_name: Haller
- first_name: Mahmoud
full_name: Rabie, Mahmoud
last_name: Rabie
- first_name: Manfred
full_name: Mark, Manfred
last_name: Mark
- first_name: Johann G
full_name: Danzl, Johann G
id: 42EFD3B6-F248-11E8-B48F-1D18A9856A87
last_name: Danzl
orcid: 0000-0001-8559-3973
- first_name: Russell
full_name: Hart, Russell
last_name: Hart
- first_name: Katharina
full_name: Lauber, Katharina
last_name: Lauber
- first_name: Guido
full_name: Pupillo, Guido
last_name: Pupillo
- first_name: Hanns
full_name: Nägerl, Hanns
last_name: Nägerl
citation:
ama: Haller E, Rabie M, Mark M, et al. Three-body correlation functions and recombination
rates for bosons in three dimensions and one dimension. Physical Review Letters.
2011;107(23). doi:10.1103/PhysRevLett.107.230404
apa: Haller, E., Rabie, M., Mark, M., Danzl, J. G., Hart, R., Lauber, K., … Nägerl,
H. (2011). Three-body correlation functions and recombination rates for bosons
in three dimensions and one dimension. Physical Review Letters. American
Physical Society. https://doi.org/10.1103/PhysRevLett.107.230404
chicago: Haller, Elmar, Mahmoud Rabie, Manfred Mark, Johann G Danzl, Russell Hart,
Katharina Lauber, Guido Pupillo, and Hanns Nägerl. “Three-Body Correlation Functions
and Recombination Rates for Bosons in Three Dimensions and One Dimension.” Physical
Review Letters. American Physical Society, 2011. https://doi.org/10.1103/PhysRevLett.107.230404.
ieee: E. Haller et al., “Three-body correlation functions and recombination
rates for bosons in three dimensions and one dimension,” Physical Review Letters,
vol. 107, no. 23. American Physical Society, 2011.
ista: Haller E, Rabie M, Mark M, Danzl JG, Hart R, Lauber K, Pupillo G, Nägerl H.
2011. Three-body correlation functions and recombination rates for bosons in three
dimensions and one dimension. Physical Review Letters. 107(23).
mla: Haller, Elmar, et al. “Three-Body Correlation Functions and Recombination Rates
for Bosons in Three Dimensions and One Dimension.” Physical Review Letters,
vol. 107, no. 23, American Physical Society, 2011, doi:10.1103/PhysRevLett.107.230404.
short: E. Haller, M. Rabie, M. Mark, J.G. Danzl, R. Hart, K. Lauber, G. Pupillo,
H. Nägerl, Physical Review Letters 107 (2011).
date_created: 2018-12-11T11:49:54Z
date_published: 2011-12-02T00:00:00Z
date_updated: 2021-01-12T06:47:57Z
day: '02'
doi: 10.1103/PhysRevLett.107.230404
extern: '1'
external_id:
arxiv:
- '1107.4516'
intvolume: ' 107'
issue: '23'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1107.4516
month: '12'
oa: 1
oa_version: Preprint
publication: Physical Review Letters
publication_status: published
publisher: American Physical Society
publist_id: '6335'
status: public
title: Three-body correlation functions and recombination rates for bosons in three
dimensions and one dimension
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 107
year: '2011'
...
---
_id: '9648'
abstract:
- lang: eng
text: In this paper, we establish a correspondence between the incremental algorithm
for computing AT-models [8,9] and the one for computing persistent homology [6,14,15].
We also present a decremental algorithm for computing AT-models that allows to
extend the persistence computation to a wider setting. Finally, we show how to
combine incremental and decremental techniques for persistent homology computation.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Rocio
full_name: Gonzalez-Diaz, Rocio
last_name: Gonzalez-Diaz
- first_name: Adrian
full_name: Ion, Adrian
id: 29F89302-F248-11E8-B48F-1D18A9856A87
last_name: Ion
- first_name: Maria Jose
full_name: Jimenez, Maria Jose
last_name: Jimenez
- first_name: Regina
full_name: Poyatos, Regina
last_name: Poyatos
citation:
ama: 'Gonzalez-Diaz R, Ion A, Jimenez MJ, Poyatos R. Incremental-decremental algorithm
for computing AT-models and persistent homology. In: Computer Analysis of Images
and Patterns. Vol 6854. Springer Nature; 2011:286-293. doi:10.1007/978-3-642-23672-3_35'
apa: 'Gonzalez-Diaz, R., Ion, A., Jimenez, M. J., & Poyatos, R. (2011). Incremental-decremental
algorithm for computing AT-models and persistent homology. In Computer Analysis
of Images and Patterns (Vol. 6854, pp. 286–293). Seville, Spain: Springer
Nature. https://doi.org/10.1007/978-3-642-23672-3_35'
chicago: Gonzalez-Diaz, Rocio, Adrian Ion, Maria Jose Jimenez, and Regina Poyatos.
“Incremental-Decremental Algorithm for Computing AT-Models and Persistent Homology.”
In Computer Analysis of Images and Patterns, 6854:286–93. Springer Nature,
2011. https://doi.org/10.1007/978-3-642-23672-3_35.
ieee: R. Gonzalez-Diaz, A. Ion, M. J. Jimenez, and R. Poyatos, “Incremental-decremental
algorithm for computing AT-models and persistent homology,” in Computer Analysis
of Images and Patterns, Seville, Spain, 2011, vol. 6854, pp. 286–293.
ista: 'Gonzalez-Diaz R, Ion A, Jimenez MJ, Poyatos R. 2011. Incremental-decremental
algorithm for computing AT-models and persistent homology. Computer Analysis of
Images and Patterns. CAIP: International Conference on Computer Analysis of Images
and Patterns, LNCS, vol. 6854, 286–293.'
mla: Gonzalez-Diaz, Rocio, et al. “Incremental-Decremental Algorithm for Computing
AT-Models and Persistent Homology.” Computer Analysis of Images and Patterns,
vol. 6854, Springer Nature, 2011, pp. 286–93, doi:10.1007/978-3-642-23672-3_35.
short: R. Gonzalez-Diaz, A. Ion, M.J. Jimenez, R. Poyatos, in:, Computer Analysis
of Images and Patterns, Springer Nature, 2011, pp. 286–293.
conference:
end_date: 2011-08-31
location: Seville, Spain
name: 'CAIP: International Conference on Computer Analysis of Images and Patterns'
start_date: 2011-08-29
date_created: 2021-07-11T22:01:19Z
date_published: 2011-08-01T00:00:00Z
date_updated: 2026-06-18T19:56:17Z
day: '01'
ddc:
- '500'
department:
- _id: HeEd
doi: 10.1007/978-3-642-23672-3_35
intvolume: ' 6854'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://hdl.handle.net/11441/30766
month: '08'
oa: 1
oa_version: Published Version
page: 286-293
publication: Computer Analysis of Images and Patterns
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783642236716'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Incremental-decremental algorithm for computing AT-models and persistent homology
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6854
year: '2011'
...
---
_id: '9943'
abstract:
- lang: eng
text: Segmentation is the process of partitioning digital images into meaningful
regions. The analysis of biological high content images often requires segmentation
as a first step. We propose ilastik as an easy-to-use tool which allows the user
without expertise in image processing to perform segmentation and classification
in a unified way. ilastik learns from labels provided by the user through a convenient
mouse interface. Based on these labels, ilastik infers a problem specific segmentation.
A random forest classifier is used in the learning step, in which each pixel's
neighborhood is characterized by a set of generic (nonlinear) features. ilastik
supports up to three spatial plus one spectral dimension and makes use of all
dimensions in the feature calculation. ilastik provides realtime feedback that
enables the user to interactively refine the segmentation result and hence further
fine-tune the classifier. An uncertainty measure guides the user to ambiguous
regions in the images. Real time performance is achieved by multi-threading which
fully exploits the capabilities of modern multi-core machines. Once a classifier
has been trained on a set of representative images, it can be exported and used
to automatically process a very large number of images (e.g. using the CellProfiler
pipeline). ilastik is an open source project and released under the BSD license
at www.ilastik.org.
article_processing_charge: No
author:
- first_name: Christoph M
full_name: Sommer, Christoph M
id: 4DF26D8C-F248-11E8-B48F-1D18A9856A87
last_name: Sommer
orcid: 0000-0003-1216-9105
- first_name: Christoph
full_name: Straehle, Christoph
last_name: Straehle
- first_name: Ullrich
full_name: Köthe, Ullrich
last_name: Köthe
- first_name: Fred A.
full_name: Hamprecht, Fred A.
last_name: Hamprecht
citation:
ama: 'Sommer CM, Straehle C, Köthe U, Hamprecht FA. Ilastik: Interactive learning
and segmentation toolkit. In: 2011 IEEE International Symposium on Biomedical
Imaging: From Nano to Micro. Institute of Electrical and Electronics Engineers;
2011. doi:10.1109/isbi.2011.5872394'
apa: 'Sommer, C. M., Straehle, C., Köthe, U., & Hamprecht, F. A. (2011). Ilastik:
Interactive learning and segmentation toolkit. In 2011 IEEE International Symposium
on Biomedical Imaging: from Nano to Micro. Chicago, Illinois, USA: Institute
of Electrical and Electronics Engineers. https://doi.org/10.1109/isbi.2011.5872394'
chicago: 'Sommer, Christoph M, Christoph Straehle, Ullrich Köthe, and Fred A. Hamprecht.
“Ilastik: Interactive Learning and Segmentation Toolkit.” In 2011 IEEE International
Symposium on Biomedical Imaging: From Nano to Micro. Institute of Electrical
and Electronics Engineers, 2011. https://doi.org/10.1109/isbi.2011.5872394.'
ieee: 'C. M. Sommer, C. Straehle, U. Köthe, and F. A. Hamprecht, “Ilastik: Interactive
learning and segmentation toolkit,” in 2011 IEEE International Symposium on
Biomedical Imaging: from Nano to Micro, Chicago, Illinois, USA, 2011.'
ista: 'Sommer CM, Straehle C, Köthe U, Hamprecht FA. 2011. Ilastik: Interactive
learning and segmentation toolkit. 2011 IEEE International Symposium on Biomedical
Imaging: from Nano to Micro. ISBI: International Symposium on Biomedical Imaging.'
mla: 'Sommer, Christoph M., et al. “Ilastik: Interactive Learning and Segmentation
Toolkit.” 2011 IEEE International Symposium on Biomedical Imaging: From Nano
to Micro, Institute of Electrical and Electronics Engineers, 2011, doi:10.1109/isbi.2011.5872394.'
short: 'C.M. Sommer, C. Straehle, U. Köthe, F.A. Hamprecht, in:, 2011 IEEE International
Symposium on Biomedical Imaging: From Nano to Micro, Institute of Electrical and
Electronics Engineers, 2011.'
conference:
end_date: 2011-04-02
location: Chicago, Illinois, USA
name: 'ISBI: International Symposium on Biomedical Imaging'
start_date: 2011-03-30
date_created: 2021-08-19T11:49:58Z
date_published: 2011-06-09T00:00:00Z
date_updated: 2023-02-23T14:13:38Z
day: '09'
department:
- _id: Bio
doi: 10.1109/isbi.2011.5872394
extern: '1'
keyword:
- image segmentation
- biomedical imaging
- three dimensional displays
- neurons
- retina
- observers
- image color analysis
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.researchgate.net/publication/224241106_Ilastik_Interactive_learning_and_segmentation_toolkit
month: '06'
oa: 1
oa_version: Preprint
publication: '2011 IEEE International Symposium on Biomedical Imaging: from Nano to
Micro'
publication_identifier:
eissn:
- 1945-8452
isbn:
- 978-1-4244-4127-3
issn:
- 1945-7928
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
status: public
title: 'Ilastik: Interactive learning and segmentation toolkit'
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2011'
...
---
_id: '3965'
abstract:
- lang: eng
text: The elevation function on a smoothly embedded 2-manifold in R-3 reflects the
multiscale topography of cavities and protrusions as local maxima. The function
has been useful in identifying coarse docking configurations for protein pairs.
Transporting the concept from the smooth to the piecewise linear category, this
paper describes an algorithm for finding all local maxima. While its worst-case
running time is the same as of the algorithm used in prior work, its performance
in practice is orders of magnitudes superior. We cast light on this improvement
by relating the running time to the total absolute Gaussian curvature of the 2-manifold.
author:
- first_name: Bei
full_name: Wang, Bei
last_name: Wang
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Dmitriy
full_name: Morozov, Dmitriy
last_name: Morozov
citation:
ama: Wang B, Edelsbrunner H, Morozov D. Computing elevation maxima by searching
the Gauss sphere. Journal of Experimental Algorithmics. 2011;16(2.2):1-13.
doi:10.1145/1963190.1970375
apa: Wang, B., Edelsbrunner, H., & Morozov, D. (2011). Computing elevation maxima
by searching the Gauss sphere. Journal of Experimental Algorithmics. ACM.
https://doi.org/10.1145/1963190.1970375
chicago: Wang, Bei, Herbert Edelsbrunner, and Dmitriy Morozov. “Computing Elevation
Maxima by Searching the Gauss Sphere.” Journal of Experimental Algorithmics.
ACM, 2011. https://doi.org/10.1145/1963190.1970375.
ieee: B. Wang, H. Edelsbrunner, and D. Morozov, “Computing elevation maxima by searching
the Gauss sphere,” Journal of Experimental Algorithmics, vol. 16, no. 2.2.
ACM, pp. 1–13, 2011.
ista: Wang B, Edelsbrunner H, Morozov D. 2011. Computing elevation maxima by searching
the Gauss sphere. Journal of Experimental Algorithmics. 16(2.2), 1–13.
mla: Wang, Bei, et al. “Computing Elevation Maxima by Searching the Gauss Sphere.”
Journal of Experimental Algorithmics, vol. 16, no. 2.2, ACM, 2011, pp.
1–13, doi:10.1145/1963190.1970375.
short: B. Wang, H. Edelsbrunner, D. Morozov, Journal of Experimental Algorithmics
16 (2011) 1–13.
date_created: 2018-12-11T12:06:09Z
date_published: 2011-05-01T00:00:00Z
date_updated: 2021-01-12T07:53:31Z
day: '01'
department:
- _id: HeEd
doi: 10.1145/1963190.1970375
intvolume: ' 16'
issue: '2.2'
language:
- iso: eng
month: '05'
oa_version: None
page: 1 - 13
publication: Journal of Experimental Algorithmics
publication_status: published
publisher: ACM
publist_id: '2161'
quality_controlled: '1'
scopus_import: 1
status: public
title: Computing elevation maxima by searching the Gauss sphere
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 16
year: '2011'
...
---
_id: '531'
abstract:
- lang: eng
text: Software transactional memories (STM) are described in the literature with
assumptions of sequentially consistent program execution and atomicity of high
level operations like read, write, and abort. However, in a realistic setting,
processors use relaxed memory models to optimize hardware performance. Moreover,
the atomicity of operations depends on the underlying hardware. This paper presents
the first approach to verify STMs under relaxed memory models with atomicity of
32 bit loads and stores, and read-modify-write operations. We describe RML, a
simple language for expressing concurrent programs. We develop a semantics of
RML parametrized by a relaxed memory model. We then present our tool, FOIL, which
takes as input the RML description of an STM algorithm restricted to two threads
and two variables, and the description of a memory model, and automatically determines
the locations of fences, which if inserted, ensure the correctness of the restricted
STM algorithm under the given memory model. We use FOIL to verify DSTM, TL2, and
McRT STM under the memory models of sequential consistency, total store order,
partial store order, and relaxed memory order for two threads and two variables.
Finally, we extend the verification results for DSTM and TL2 to an arbitrary number
of threads and variables by manually proving that the structural properties of
STMs are satisfied at the hardware level of atomicity under the considered relaxed
memory models.
article_processing_charge: No
article_type: original
author:
- first_name: Rachid
full_name: Guerraoui, Rachid
last_name: Guerraoui
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Vasu
full_name: Singh, Vasu
id: 4DAE2708-F248-11E8-B48F-1D18A9856A87
last_name: Singh
citation:
ama: Guerraoui R, Henzinger TA, Singh V. Verification of STM on relaxed memory models.
Formal Methods in System Design. 2011;39(3):297-331. doi:10.1007/s10703-011-0131-3
apa: Guerraoui, R., Henzinger, T. A., & Singh, V. (2011). Verification of STM
on relaxed memory models. Formal Methods in System Design. Springer. https://doi.org/10.1007/s10703-011-0131-3
chicago: Guerraoui, Rachid, Thomas A Henzinger, and Vasu Singh. “Verification of
STM on Relaxed Memory Models.” Formal Methods in System Design. Springer,
2011. https://doi.org/10.1007/s10703-011-0131-3.
ieee: R. Guerraoui, T. A. Henzinger, and V. Singh, “Verification of STM on relaxed
memory models,” Formal Methods in System Design, vol. 39, no. 3. Springer,
pp. 297–331, 2011.
ista: Guerraoui R, Henzinger TA, Singh V. 2011. Verification of STM on relaxed memory
models. Formal Methods in System Design. 39(3), 297–331.
mla: Guerraoui, Rachid, et al. “Verification of STM on Relaxed Memory Models.” Formal
Methods in System Design, vol. 39, no. 3, Springer, 2011, pp. 297–331, doi:10.1007/s10703-011-0131-3.
short: R. Guerraoui, T.A. Henzinger, V. Singh, Formal Methods in System Design 39
(2011) 297–331.
corr_author: '1'
date_created: 2018-12-11T11:47:00Z
date_published: 2011-12-01T00:00:00Z
date_updated: 2025-09-30T09:23:08Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/s10703-011-0131-3
external_id:
isi:
- '000297596900004'
intvolume: ' 39'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://infoscience.epfl.ch/record/178042/files/art3A10.10072Fs10703-011-0131-3.pdf
month: '12'
oa: 1
oa_version: Published Version
page: 297 - 331
publication: Formal Methods in System Design
publication_status: published
publisher: Springer
publist_id: '7288'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Verification of STM on relaxed memory models
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 39
year: '2011'
...
---
_id: '5379'
abstract:
- lang: eng
text: Computing the winning set for Büchi objectives in alternating games on graphs
is a central problem in computer aided verification with a large number of applications.
The long standing best known upper bound for solving the problem is ̃O(n·m), where
n is the number of vertices and m is the number of edges in the graph. We are
the first to break the ̃O(n·m) boundary by presenting a new technique that reduces
the running time to O(n2). This bound also leads to O(n2) time algorithms for
computing the set of almost-sure winning vertices for Büchi objectives (1) in
alternating games with probabilistic transitions (improving an earlier bound of
O(n·m)), (2) in concurrent graph games with constant actions (improving an earlier
bound of O(n3)), and (3) in Markov decision processes (improving for m > n4/3
an earlier bound of O(min(m1.5, m·n2/3)). We also show that the same technique
can be used to compute the maximal end-component decomposition of a graph in time
O(n2), which is an improvement over earlier bounds for m > n4/3. Finally, we show
how to maintain the winning set for Büchi objectives in alternating games under
a sequence of edge insertions or a sequence of edge deletions in O(n) amortized
time per operation. This is the first dynamic algorithm for this problem.
alternative_title:
- IST Austria Technical Report
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: Chatterjee K, Henzinger M. An O(N2) Time Algorithm for Alternating Büchi
Games. IST Austria; 2011. doi:10.15479/AT:IST-2011-0009
apa: Chatterjee, K., & Henzinger, M. (2011). An O(n2) time algorithm for
alternating Büchi games. IST Austria. https://doi.org/10.15479/AT:IST-2011-0009
chicago: Chatterjee, Krishnendu, and Monika Henzinger. An O(N2) Time Algorithm
for Alternating Büchi Games. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0009.
ieee: K. Chatterjee and M. Henzinger, An O(n2) time algorithm for alternating
Büchi games. IST Austria, 2011.
ista: Chatterjee K, Henzinger M. 2011. An O(n2) time algorithm for alternating Büchi
games, IST Austria, 20p.
mla: Chatterjee, Krishnendu, and Monika Henzinger. An O(N2) Time Algorithm for
Alternating Büchi Games. IST Austria, 2011, doi:10.15479/AT:IST-2011-0009.
short: K. Chatterjee, M. Henzinger, An O(N2) Time Algorithm for Alternating Büchi
Games, IST Austria, 2011.
date_created: 2018-12-12T11:38:59Z
date_published: 2011-07-11T00:00:00Z
date_updated: 2025-07-10T11:52:28Z
day: '11'
ddc:
- '000'
- '004'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2011-0009
file:
- access_level: open_access
checksum: 0b354264229045d982332fd2cb5b9a26
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:43Z
date_updated: 2020-07-14T12:46:39Z
file_id: '5504'
file_name: IST-2011-0009_IST-2011-0009.pdf
file_size: 388665
relation: main_file
file_date_updated: 2020-07-14T12:46:39Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '20'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '15'
related_material:
record:
- id: '3165'
relation: later_version
status: public
status: public
title: An O(n2) time algorithm for alternating Büchi games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '5380'
abstract:
- lang: eng
text: 'We consider 2-player games played on a finite state space for an infinite
number of rounds. The games are concurrent: in each round, the two players (player
1 and player 2) choose their moves independently and simultaneously; the current
state and the two moves determine the successor state. We study concurrent games
with ω-regular winning conditions specified as parity objectives. We consider
the qualitative analysis problems: the computation of the almost-sure and limit-sure
winning set of states, where player 1 can ensure to win with probability 1 and
with probability arbitrarily close to 1, respectively. In general the almost-sure
and limit-sure winning strategies require both infinite-memory as well as infinite-precision
(to describe probabilities). We study the bounded-rationality problem for qualitative
analysis of concurrent parity games, where the strategy set for player 1 is restricted
to bounded-resource strategies. In terms of precision, strategies can be deterministic,
uniform, finite-precision or infinite-precision; and in terms of memory, strategies
can be memoryless, finite-memory or infinite-memory. We present a precise and
complete characterization of the qualitative winning sets for all combinations
of classes of strategies. In particular, we show that uniform memoryless strategies
are as powerful as finite-precision infinite-memory strategies, and infinite-precision
memoryless strategies are as powerful as infinite-precision finite-memory strategies. We
show that the winning sets can be computed in O(n2d+3) time, where n is the size
of the game structure and 2d is the number of priorities (or colors), and our
algorithms are symbolic. The membership problem of whether a state belongs to
a winning set can be decided in NP ∩ coNP. While this complexity is the same as
for the simpler class of turn-based parity games, where in each state only one
of the two players has a choice of moves, our algorithms,that are obtained by
characterization of the winning sets as μ-calculus formulas, are considerably
more involved than those for turn-based games.'
alternative_title:
- IST Austria Technical Report
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. Bounded Rationality in Concurrent Parity Games. IST Austria;
2011. doi:10.15479/AT:IST-2011-0008
apa: Chatterjee, K. (2011). Bounded rationality in concurrent parity games.
IST Austria. https://doi.org/10.15479/AT:IST-2011-0008
chicago: Chatterjee, Krishnendu. Bounded Rationality in Concurrent Parity Games.
IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0008.
ieee: K. Chatterjee, Bounded rationality in concurrent parity games. IST
Austria, 2011.
ista: Chatterjee K. 2011. Bounded rationality in concurrent parity games, IST Austria,
53p.
mla: Chatterjee, Krishnendu. Bounded Rationality in Concurrent Parity Games.
IST Austria, 2011, doi:10.15479/AT:IST-2011-0008.
short: K. Chatterjee, Bounded Rationality in Concurrent Parity Games, IST Austria,
2011.
date_created: 2018-12-12T11:39:00Z
date_published: 2011-07-11T00:00:00Z
date_updated: 2025-06-26T09:28:52Z
day: '11'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2011-0008
file:
- access_level: open_access
checksum: 0fd38186409be819a911c4990fa79d1f
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:22Z
date_updated: 2020-07-14T12:46:39Z
file_id: '5544'
file_name: IST-2011-0008_IST-2011-0008.pdf
file_size: 500399
relation: main_file
file_date_updated: 2020-07-14T12:46:39Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '53'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '16'
related_material:
record:
- id: '3338'
relation: later_version
status: public
status: public
title: Bounded rationality in concurrent parity games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '5381'
abstract:
- lang: eng
text: "In two-player finite-state stochastic games of partial obser- vation on graphs,
in every state of the graph, the players simultaneously choose an action, and
their joint actions determine a probability distri- bution over the successor
states. The game is played for infinitely many rounds and thus the players construct
an infinite path in the graph. We consider reachability objectives where the first
player tries to ensure a target state to be visited almost-surely (i.e., with
probability 1) or pos- itively (i.e., with positive probability), no matter the
strategy of the second player.\r\n\r\nWe classify such games according to the
information and to the power of randomization available to the players. On the
basis of information, the game can be one-sided with either (a) player 1, or (b)
player 2 having partial observation (and the other player has perfect observation),
or two- sided with (c) both players having partial observation. On the basis of
randomization, (a) the players may not be allowed to use randomization (pure strategies),
or (b) they may choose a probability distribution over actions but the actual
random choice is external and not visible to the player (actions invisible), or
(c) they may use full randomization.\r\n\r\nOur main results for pure strategies
are as follows: (1) For one-sided games with player 2 perfect observation we show
that (in contrast to full randomized strategies) belief-based (subset-construction
based) strate- gies are not sufficient, and present an exponential upper bound
on mem- ory both for almost-sure and positive winning strategies; we show that
the problem of deciding the existence of almost-sure and positive winning strategies
for player 1 is EXPTIME-complete and present symbolic algo- rithms that avoid
the explicit exponential construction. (2) For one-sided games with player 1 perfect
observation we show that non-elementary memory is both necessary and sufficient
for both almost-sure and posi- tive winning strategies. (3) We show that for the
general (two-sided) case finite-memory strategies are sufficient for both positive
and almost-sure winning, and at least non-elementary memory is required. We establish
the equivalence of the almost-sure winning problems for pure strategies and for
randomized strategies with actions invisible. Our equivalence re- sult exhibit
serious flaws in previous results in the literature: we show a non-elementary
memory lower bound for almost-sure winning whereas an exponential upper bound
was previously claimed."
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
citation:
ama: 'Chatterjee K, Doyen L. Partial-Observation Stochastic Games: How to Win
When Belief Fails. IST Austria; 2011. doi:10.15479/AT:IST-2011-0007'
apa: 'Chatterjee, K., & Doyen, L. (2011). Partial-observation stochastic
games: How to win when belief fails. IST Austria. https://doi.org/10.15479/AT:IST-2011-0007'
chicago: 'Chatterjee, Krishnendu, and Laurent Doyen. Partial-Observation Stochastic
Games: How to Win When Belief Fails. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0007.'
ieee: 'K. Chatterjee and L. Doyen, Partial-observation stochastic games: How
to win when belief fails. IST Austria, 2011.'
ista: 'Chatterjee K, Doyen L. 2011. Partial-observation stochastic games: How to
win when belief fails, IST Austria, 43p.'
mla: 'Chatterjee, Krishnendu, and Laurent Doyen. Partial-Observation Stochastic
Games: How to Win When Belief Fails. IST Austria, 2011, doi:10.15479/AT:IST-2011-0007.'
short: 'K. Chatterjee, L. Doyen, Partial-Observation Stochastic Games: How to Win
When Belief Fails, IST Austria, 2011.'
date_created: 2018-12-12T11:39:00Z
date_published: 2011-07-05T00:00:00Z
date_updated: 2025-09-30T08:08:45Z
day: '05'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2011-0007
file:
- access_level: open_access
checksum: 06bf6dfc97f6006e3fd0e9a3f31bc961
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:27Z
date_updated: 2020-07-14T12:46:39Z
file_id: '5488'
file_name: IST-2011-0007_IST-2011-0007.pdf
file_size: 574055
relation: main_file
file_date_updated: 2020-07-14T12:46:39Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '43'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '17'
related_material:
record:
- id: '1903'
relation: later_version
status: public
- id: '2211'
relation: later_version
status: public
- id: '2955'
relation: later_version
status: public
status: public
title: 'Partial-observation stochastic games: How to win when belief fails'
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '2975'
abstract:
- lang: eng
text: "Zero-knowledge proofs of knowledge (ZK-PoK) for discrete logarithms and related
problems are indispensable for practical cryptographic protocols. Recently, Camenisch,
Kiayias, and Yung provided a specification language (the CKY-language) for such
protocols which allows for a modular design and protocol analysis: for every zero-knowledge
proof specified in this language, protocol designers are ensured that there exists
an efficient protocol which indeed proves the specified statement.\n\nHowever,
the protocols resulting from their compilation techniques only satisfy the classical
notion of ZK-PoK, which is not retained are when they used as building blocks
for higher-level applications or composed with other protocols.\nThis problem
can be tackled by moving to the Universal Composability (UC) framework, which
guarantees retention of security when composing protocols in arbitrary ways. \nWhile
there exist generic transformations from $\\Sigma$-protocols to UC-secure protocols,
these transformation are often too inefficient for practice.\n \nIn this paper
we introduce a specification language akin to the CKY-language and a compiler
such that the resulting protocols are UC-secure and efficient. \nTo this end,
we propose an extension of the UC-framework addressing the \nissue that UC-secure
zero-knowledge proofs are by definition proofs of knowledge, and state a special
composition theorem which allows one to use the weaker -- but more efficient and
often sufficient -- notion of proofs of membership in the UC-framework. \nWe
believe that our contributions enable the design of practically efficient protocols
that are UC-secure and thus themselves can be used as building blocks."
acknowledgement: This work was in part funded by the Swiss Hasler Foundation, and
the EU FP7 grants 216483 and 216499, as well as by the NSF grant CNS-0716690.
alternative_title:
- LNCS
author:
- first_name: Jan
full_name: Camenisch, Jan
last_name: Camenisch
- first_name: Stephan
full_name: Stephan Krenn
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
- first_name: Victor
full_name: Shoup, Victor
last_name: Shoup
citation:
ama: 'Camenisch J, Krenn S, Shoup V. A Framework for Practical Universally Composable
Zero-Knowledge Protocols. In: Lee D, Wang X, eds. Vol 7073. Springer; 2011:449-467.
doi:10.1007/978-3-642-25385-0'
apa: 'Camenisch, J., Krenn, S., & Shoup, V. (2011). A Framework for Practical
Universally Composable Zero-Knowledge Protocols. In D. Lee & X. Wang (Eds.)
(Vol. 7073, pp. 449–467). Presented at the ASIACRYPT: Theory and Application of
Cryptology and Information Security, Springer. https://doi.org/10.1007/978-3-642-25385-0'
chicago: Camenisch, Jan, Stephan Krenn, and Victor Shoup. “A Framework for Practical
Universally Composable Zero-Knowledge Protocols.” edited by Dong Lee and Xiaoyun
Wang, 7073:449–67. Springer, 2011. https://doi.org/10.1007/978-3-642-25385-0.
ieee: 'J. Camenisch, S. Krenn, and V. Shoup, “A Framework for Practical Universally
Composable Zero-Knowledge Protocols,” presented at the ASIACRYPT: Theory and Application
of Cryptology and Information Security, 2011, vol. 7073, pp. 449–467.'
ista: 'Camenisch J, Krenn S, Shoup V. 2011. A Framework for Practical Universally
Composable Zero-Knowledge Protocols. ASIACRYPT: Theory and Application of Cryptology
and Information Security, LNCS, vol. 7073, 449–467.'
mla: Camenisch, Jan, et al. A Framework for Practical Universally Composable
Zero-Knowledge Protocols. Edited by Dong Lee and Xiaoyun Wang, vol. 7073,
Springer, 2011, pp. 449–67, doi:10.1007/978-3-642-25385-0.
short: J. Camenisch, S. Krenn, V. Shoup, in:, D. Lee, X. Wang (Eds.), Springer,
2011, pp. 449–467.
conference:
name: 'ASIACRYPT: Theory and Application of Cryptology and Information Security'
date_created: 2018-12-11T12:00:39Z
date_published: 2011-11-21T00:00:00Z
date_updated: 2021-01-12T07:40:11Z
day: '21'
doi: 10.1007/978-3-642-25385-0
editor:
- first_name: Dong
full_name: Lee, Dong Hoon
last_name: Lee
- first_name: Xiaoyun
full_name: Wang, Xiaoyun
last_name: Wang
extern: 1
intvolume: ' 7073'
main_file_link:
- open_access: '0'
url: http://eprint.iacr.org/2011/228.pdf
month: '11'
page: 449 - 467
publication_status: published
publisher: Springer
publist_id: '3728'
quality_controlled: 0
status: public
title: A Framework for Practical Universally Composable Zero-Knowledge Protocols
type: conference
volume: 7073
year: '2011'
...
---
_id: '3086'
abstract:
- lang: eng
text: PIN-FORMED (PIN)-dependent auxin transport is essential for plant development
and its modulation in response to the environment or endogenous signals. A NON-PHOTOTROPIC
HYPOCOTYL 3 (NPH3)-like protein, MACCHI-BOU 4 (MAB4), has been shown to control
PIN1 localization during organ formation, but its contribution is limited. The
Arabidopsis genome contains four genes, MAB4/ENP/NPY1-LIKE1 (MEL1), MEL2, MEL3
and MEL4, highly homologous to MAB4. Genetic analysis disclosed functional redundancy
between MAB4 and MEL genes in regulation of not only organ formation but also
of root gravitropism, revealing that NPH3 family proteins have a wider range of
functions than previously suspected. Multiple mutants showed severe reduction
in PIN abundance and PIN polar localization, leading to defective expression of
an auxin responsive marker DR5rev::GFP. Pharmacological analyses and fluorescence
recovery after photo-bleaching experiments showed that mel mutations increase
PIN2 internalization from the plasma membrane, but affect neither intracellular
PIN2 trafficking nor PIN2 lateral diffusion at the plasma membrane. Notably, all
MAB4 subfamily proteins show polar localization at the cell periphery in plants.
The MAB4 polarity was almost identical to PIN polarity. Our results suggest that
the MAB4 subfamily proteins specifically retain PIN proteins in a polarized manner
at the plasma membrane, thus controlling directional auxin transport and plant
development.
author:
- first_name: Masahiko
full_name: Furutani, Masahiko
last_name: Furutani
- first_name: Norihito
full_name: Sakamoto, Norihito
last_name: Sakamoto
- first_name: Shuhei
full_name: Yoshida, Shuhei
last_name: Yoshida
- first_name: Takahito
full_name: Kajiwara, Takahito
last_name: Kajiwara
- first_name: Hélène
full_name: Robert, Hélène S
last_name: Robert
- first_name: Jirí
full_name: Jirí Friml
id: 4159519E-F248-11E8-B48F-1D18A9856A87
last_name: Friml
orcid: 0000-0002-8302-7596
- first_name: Masao
full_name: Tasaka, Masao
last_name: Tasaka
citation:
ama: Furutani M, Sakamoto N, Yoshida S, et al. Polar localized NPH3-like proteins
regulate polarity and endocytosis of PIN-FORMED auxin efflux carriers. Development.
2011;138(10):2069-2078. doi:10.1242/dev.057745
apa: Furutani, M., Sakamoto, N., Yoshida, S., Kajiwara, T., Robert, H., Friml, J.,
& Tasaka, M. (2011). Polar localized NPH3-like proteins regulate polarity
and endocytosis of PIN-FORMED auxin efflux carriers. Development. Company
of Biologists. https://doi.org/10.1242/dev.057745
chicago: Furutani, Masahiko, Norihito Sakamoto, Shuhei Yoshida, Takahito Kajiwara,
Hélène Robert, Jiří Friml, and Masao Tasaka. “Polar Localized NPH3-like Proteins
Regulate Polarity and Endocytosis of PIN-FORMED Auxin Efflux Carriers.” Development.
Company of Biologists, 2011. https://doi.org/10.1242/dev.057745.
ieee: M. Furutani et al., “Polar localized NPH3-like proteins regulate polarity
and endocytosis of PIN-FORMED auxin efflux carriers,” Development, vol.
138, no. 10. Company of Biologists, pp. 2069–2078, 2011.
ista: Furutani M, Sakamoto N, Yoshida S, Kajiwara T, Robert H, Friml J, Tasaka M.
2011. Polar localized NPH3-like proteins regulate polarity and endocytosis of
PIN-FORMED auxin efflux carriers. Development. 138(10), 2069–2078.
mla: Furutani, Masahiko, et al. “Polar Localized NPH3-like Proteins Regulate Polarity
and Endocytosis of PIN-FORMED Auxin Efflux Carriers.” Development, vol.
138, no. 10, Company of Biologists, 2011, pp. 2069–78, doi:10.1242/dev.057745.
short: M. Furutani, N. Sakamoto, S. Yoshida, T. Kajiwara, H. Robert, J. Friml, M.
Tasaka, Development 138 (2011) 2069–2078.
date_created: 2018-12-11T12:01:17Z
date_published: 2011-05-01T00:00:00Z
date_updated: 2021-01-12T07:40:57Z
day: '01'
doi: 10.1242/dev.057745
extern: 1
intvolume: ' 138'
issue: '10'
month: '05'
page: 2069 - 2078
publication: Development
publication_status: published
publisher: Company of Biologists
publist_id: '3615'
quality_controlled: 0
status: public
title: Polar localized NPH3-like proteins regulate polarity and endocytosis of PIN-FORMED
auxin efflux carriers
type: journal_article
volume: 138
year: '2011'
...
---
_id: '3089'
abstract:
- lang: eng
text: The phytohormone auxin is an important determinant of plant development. Directional
auxin flow within tissues depends on polar localization of PIN auxin transporters.
To explore regulation of PIN-mediated auxin transport, we screened for suppressors
of PIN1 overexpression (supo) and identified an inositol polyphosphate 1-phosphatase
mutant (supo1), with elevated inositol trisphosphate (InsP 3) and cytosolic Ca
2+ levels. Pharmacological and genetic increases in InsP 3 or Ca 2+ levels also
suppressed the PIN1 gain-of-function phenotypes and caused defects in basal PIN
localization, auxin transport and auxin-mediated development. In contrast, the
reductions in InsP 3 levels and Ca 2+ signaling antagonized the effects of the
supo1 mutation and disrupted preferentially apical PIN localization. InsP 3 and
Ca 2+ are evolutionarily conserved second messengers involved in various cellular
functions, particularly stress responses. Our findings implicate them as modifiers
of cell polarity and polar auxin transport, and highlight a potential integration
point through which Ca 2+ signaling-related stimuli could influence auxin-mediated
development.
author:
- first_name: Jing
full_name: Zhang, Jing
last_name: Zhang
- first_name: Steffen
full_name: Vanneste, Steffen
last_name: Vanneste
- first_name: Philip
full_name: Brewer, Philip B
last_name: Brewer
- first_name: Marta
full_name: Michniewicz, Marta
last_name: Michniewicz
- first_name: Peter
full_name: Peter Grones
id: 399876EC-F248-11E8-B48F-1D18A9856A87
last_name: Grones
- first_name: Jürgen
full_name: Kleine-Vehn, Jürgen
last_name: Kleine Vehn
- first_name: Christian
full_name: Löfke, Christian
last_name: Löfke
- first_name: Thomas
full_name: Teichmann, Thomas
last_name: Teichmann
- first_name: Agnieszka
full_name: Bielach, Agnieszka
last_name: Bielach
- first_name: Bernard
full_name: Cannoot, Bernard
last_name: Cannoot
- first_name: Klára
full_name: Hoyerová, Klára
last_name: Hoyerová
- first_name: Xu
full_name: Xu Chen
id: 4E5ADCAA-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Hong
full_name: Xue, Hong-Wei
last_name: Xue
- first_name: Eva
full_name: Eva Benková
id: 38F4F166-F248-11E8-B48F-1D18A9856A87
last_name: Benková
orcid: 0000-0002-8510-9739
- first_name: Eva
full_name: Zažímalová, Eva
last_name: Zažímalová
- first_name: Jirí
full_name: Jirí Friml
id: 4159519E-F248-11E8-B48F-1D18A9856A87
last_name: Friml
orcid: 0000-0002-8302-7596
citation:
ama: Zhang J, Vanneste S, Brewer P, et al. Inositol trisphosphate-induced ca^2+
signaling modulates auxin transport and pin polarity. Developmental Cell.
2011;20(6):855-866. doi:10.1016/j.devcel.2011.05.013
apa: Zhang, J., Vanneste, S., Brewer, P., Michniewicz, M., Grones, P., Kleine Vehn,
J., … Friml, J. (2011). Inositol trisphosphate-induced ca^2+ signaling modulates
auxin transport and pin polarity. Developmental Cell. Cell Press. https://doi.org/10.1016/j.devcel.2011.05.013
chicago: Zhang, Jing, Steffen Vanneste, Philip Brewer, Marta Michniewicz, Peter
Grones, Jürgen Kleine Vehn, Christian Löfke, et al. “Inositol Trisphosphate-Induced
Ca^2+ Signaling Modulates Auxin Transport and Pin Polarity.” Developmental
Cell. Cell Press, 2011. https://doi.org/10.1016/j.devcel.2011.05.013.
ieee: J. Zhang et al., “Inositol trisphosphate-induced ca^2+ signaling modulates
auxin transport and pin polarity,” Developmental Cell, vol. 20, no. 6.
Cell Press, pp. 855–866, 2011.
ista: Zhang J, Vanneste S, Brewer P, Michniewicz M, Grones P, Kleine Vehn J, Löfke
C, Teichmann T, Bielach A, Cannoot B, Hoyerová K, Chen X, Xue H, Benková E, Zažímalová
E, Friml J. 2011. Inositol trisphosphate-induced ca^2+ signaling modulates auxin
transport and pin polarity. Developmental Cell. 20(6), 855–866.
mla: Zhang, Jing, et al. “Inositol Trisphosphate-Induced Ca^2+ Signaling Modulates
Auxin Transport and Pin Polarity.” Developmental Cell, vol. 20, no. 6,
Cell Press, 2011, pp. 855–66, doi:10.1016/j.devcel.2011.05.013.
short: J. Zhang, S. Vanneste, P. Brewer, M. Michniewicz, P. Grones, J. Kleine Vehn,
C. Löfke, T. Teichmann, A. Bielach, B. Cannoot, K. Hoyerová, X. Chen, H. Xue,
E. Benková, E. Zažímalová, J. Friml, Developmental Cell 20 (2011) 855–866.
date_created: 2018-12-11T12:01:18Z
date_published: 2011-06-14T00:00:00Z
date_updated: 2021-01-12T07:40:58Z
day: '14'
doi: 10.1016/j.devcel.2011.05.013
extern: 1
intvolume: ' 20'
issue: '6'
month: '06'
page: 855 - 866
publication: Developmental Cell
publication_status: published
publisher: Cell Press
publist_id: '3612'
quality_controlled: 0
status: public
title: Inositol trisphosphate-induced ca^2+ signaling modulates auxin transport and
pin polarity
type: journal_article
volume: 20
year: '2011'
...
---
_id: '3090'
abstract:
- lang: eng
text: The polarized transport of the phytohormone auxin [1], which is crucial for
the regulation of different stages of plant development [2, 3], depends on the
asymmetric plasma membrane distribution of the PIN-FORMED (PIN) auxin efflux carriers
[4, 5]. The PIN polar localization results from clathrin-mediated endocytosis
(CME) from the plasma membrane and subsequent polar recycling [6]. The Arabidopsis
genome encodes two groups of dynamin-related proteins (DRPs) that show homology
to mammalian dynamin - a protein required for fission of endocytic vesicles during
CME [7, 8]. Here we show by coimmunoprecipitation (coIP), bimolecular fluorescence
complementation (BiFC), and Förster resonance energy transfer (FRET) that members
of the DRP1 group closely associate with PIN proteins at the cell plate. Localization
and phenotypic analysis of novel drp1 mutants revealed a requirement for DRP1
function in correct PIN distribution and in auxin-mediated development. We propose
that rapid and specific internalization of PIN proteins mediated by the DRP1 proteins
and the associated CME machinery from the cell plate membranes during cytokinesis
is an important mechanism for proper polar PIN positioning in interphase cells.
author:
- first_name: Jozef
full_name: Mravec, Jozef
last_name: Mravec
- first_name: Jan
full_name: Petrášek, Jan
last_name: Petrášek
- first_name: Na
full_name: Li, Na
last_name: Li
- first_name: Sjef
full_name: Boeren, Sjef
last_name: Boeren
- first_name: Rumyana
full_name: Karlova, Rumyana
last_name: Karlova
- first_name: Saeko
full_name: Kitakura, Saeko
last_name: Kitakura
- first_name: Markéta
full_name: Pařezová, Markéta
last_name: Pařezová
- first_name: Satoshi
full_name: Naramoto, Satoshi
last_name: Naramoto
- first_name: Thomasz
full_name: Nodzyński, Thomasz
last_name: Nodzyński
- first_name: Pankaj
full_name: Dhonukshe, Pankaj
last_name: Dhonukshe
- first_name: Sebastian
full_name: Bednarek, Sebastian Y
last_name: Bednarek
- first_name: Eva
full_name: Zažímalová, Eva
last_name: Zažímalová
- first_name: Sacco
full_name: De Vries, Sacco
last_name: De Vries
- first_name: Jirí
full_name: Jirí Friml
id: 4159519E-F248-11E8-B48F-1D18A9856A87
last_name: Friml
orcid: 0000-0002-8302-7596
citation:
ama: Mravec J, Petrášek J, Li N, et al. Cell plate restricted association of DRP1A
and PIN proteins is required for cell polarity establishment in arabidopsis. Current
Biology. 2011;21(12):1055-1060. doi:10.1016/j.cub.2011.05.018
apa: Mravec, J., Petrášek, J., Li, N., Boeren, S., Karlova, R., Kitakura, S., …
Friml, J. (2011). Cell plate restricted association of DRP1A and PIN proteins
is required for cell polarity establishment in arabidopsis. Current Biology.
Cell Press. https://doi.org/10.1016/j.cub.2011.05.018
chicago: Mravec, Jozef, Jan Petrášek, Na Li, Sjef Boeren, Rumyana Karlova, Saeko
Kitakura, Markéta Pařezová, et al. “Cell Plate Restricted Association of DRP1A
and PIN Proteins Is Required for Cell Polarity Establishment in Arabidopsis.”
Current Biology. Cell Press, 2011. https://doi.org/10.1016/j.cub.2011.05.018.
ieee: J. Mravec et al., “Cell plate restricted association of DRP1A and PIN
proteins is required for cell polarity establishment in arabidopsis,” Current
Biology, vol. 21, no. 12. Cell Press, pp. 1055–1060, 2011.
ista: Mravec J, Petrášek J, Li N, Boeren S, Karlova R, Kitakura S, Pařezová M, Naramoto
S, Nodzyński T, Dhonukshe P, Bednarek S, Zažímalová E, De Vries S, Friml J. 2011.
Cell plate restricted association of DRP1A and PIN proteins is required for cell
polarity establishment in arabidopsis. Current Biology. 21(12), 1055–1060.
mla: Mravec, Jozef, et al. “Cell Plate Restricted Association of DRP1A and PIN Proteins
Is Required for Cell Polarity Establishment in Arabidopsis.” Current Biology,
vol. 21, no. 12, Cell Press, 2011, pp. 1055–60, doi:10.1016/j.cub.2011.05.018.
short: J. Mravec, J. Petrášek, N. Li, S. Boeren, R. Karlova, S. Kitakura, M. Pařezová,
S. Naramoto, T. Nodzyński, P. Dhonukshe, S. Bednarek, E. Zažímalová, S. De Vries,
J. Friml, Current Biology 21 (2011) 1055–1060.
date_created: 2018-12-11T12:01:19Z
date_published: 2011-06-21T00:00:00Z
date_updated: 2021-01-12T07:40:59Z
day: '21'
doi: 10.1016/j.cub.2011.05.018
extern: 1
intvolume: ' 21'
issue: '12'
month: '06'
page: 1055 - 1060
publication: Current Biology
publication_status: published
publisher: Cell Press
publist_id: '3611'
quality_controlled: 0
status: public
title: Cell plate restricted association of DRP1A and PIN proteins is required for
cell polarity establishment in arabidopsis
type: journal_article
volume: 21
year: '2011'
...
---
_id: '3101'
abstract:
- lang: eng
text: Subcellular trafficking is required for a multitude of functions in eukaryotic
cells. It involves regulation of cargo sorting, vesicle formation, trafficking
and fusion processes at multiple levels. Adaptor protein (AP) complexes are key
regulators of cargo sorting into vesicles in yeast and mammals but their existence
and function in plants have not been demonstrated. Here we report the identification
of the protein-affected trafficking 4 (pat4) mutant defective in the putative
δ subunit of the AP-3 complex. pat4 and pat2, a mutant isolated from the same
GFP imaging-based forward genetic screen that lacks a functional putative AP-3
β, as well as dominant negative AP-3 μ transgenic lines display undistinguishable
phenotypes characterized by largely normal morphology and development, but strong
intracellular accumulation of membrane proteins in aberrant vacuolar structures.
All mutants are defective in morphology and function of lytic and protein storage
vacuoles (PSVs) but show normal sorting of reserve proteins to PSVs. Immunoprecipitation
experiments and genetic studies revealed tight functional and physical associations
of putative AP-3 β and AP-3 δ subunits. Furthermore, both proteins are closely
linked with putative AP-3 μ and σ subunits and several components of the clathrin
and dynamin machineries. Taken together, these results demonstrate that AP complexes,
similar to those in other eukaryotes, exist in plants, and that AP-3 plays a specific
role in the regulation of biogenesis and function of vacuoles in plant cells.
© 2011 IBCB, SIBS, CAS All rights reserved
author:
- first_name: Marta
full_name: Zwiewka, Marta
last_name: Zwiewka
- first_name: Elena
full_name: Feraru, Elena
last_name: Feraru
- first_name: Barbara
full_name: Möller, Barbara
last_name: Möller
- first_name: Inhwan
full_name: Hwang, Inhwan
last_name: Hwang
- first_name: Mugurel
full_name: Feraru, Mugurel I
last_name: Feraru
- first_name: Jürgen
full_name: Kleine-Vehn, Jürgen
last_name: Kleine Vehn
- first_name: Dolf
full_name: Weijers, Dolf
last_name: Weijers
- first_name: Jirí
full_name: Jirí Friml
id: 4159519E-F248-11E8-B48F-1D18A9856A87
last_name: Friml
orcid: 0000-0002-8302-7596
citation:
ama: Zwiewka M, Feraru E, Möller B, et al. The AP 3 adaptor complex is required
for vacuolar function in Arabidopsis. Cell Research. 2011;21(12):1711-1722.
doi:10.1038/cr.2011.99
apa: Zwiewka, M., Feraru, E., Möller, B., Hwang, I., Feraru, M., Kleine Vehn, J.,
… Friml, J. (2011). The AP 3 adaptor complex is required for vacuolar function
in Arabidopsis. Cell Research. Nature Publishing Group. https://doi.org/10.1038/cr.2011.99
chicago: Zwiewka, Marta, Elena Feraru, Barbara Möller, Inhwan Hwang, Mugurel Feraru,
Jürgen Kleine Vehn, Dolf Weijers, and Jiří Friml. “The AP 3 Adaptor Complex Is
Required for Vacuolar Function in Arabidopsis.” Cell Research. Nature Publishing
Group, 2011. https://doi.org/10.1038/cr.2011.99.
ieee: M. Zwiewka et al., “The AP 3 adaptor complex is required for vacuolar
function in Arabidopsis,” Cell Research, vol. 21, no. 12. Nature Publishing
Group, pp. 1711–1722, 2011.
ista: Zwiewka M, Feraru E, Möller B, Hwang I, Feraru M, Kleine Vehn J, Weijers D,
Friml J. 2011. The AP 3 adaptor complex is required for vacuolar function in Arabidopsis.
Cell Research. 21(12), 1711–1722.
mla: Zwiewka, Marta, et al. “The AP 3 Adaptor Complex Is Required for Vacuolar Function
in Arabidopsis.” Cell Research, vol. 21, no. 12, Nature Publishing Group,
2011, pp. 1711–22, doi:10.1038/cr.2011.99.
short: M. Zwiewka, E. Feraru, B. Möller, I. Hwang, M. Feraru, J. Kleine Vehn, D.
Weijers, J. Friml, Cell Research 21 (2011) 1711–1722.
date_created: 2018-12-11T12:01:23Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:41:04Z
day: '01'
doi: 10.1038/cr.2011.99
extern: 1
intvolume: ' 21'
issue: '12'
main_file_link:
- open_access: '1'
url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3357998/
month: '01'
oa: 1
page: 1711 - 1722
publication: Cell Research
publication_status: published
publisher: Nature Publishing Group
publist_id: '3597'
quality_controlled: 0
status: public
title: The AP 3 adaptor complex is required for vacuolar function in Arabidopsis
type: journal_article
volume: 21
year: '2011'
...
---
_id: '3138'
abstract:
- lang: eng
text: Hippocampal sharp waves (SPWs) and associated fast ("ripple") oscillations
(SPW-Rs) in the CA1 region are among the most synchronous physiological patterns
in the mammalian brain. Using two-dimensional arrays of electrodes for recording
local field potentials and unit discharges in freely moving rats, we studied the
emergence of ripple oscillations (140-220 Hz) and compared their origin and cellular-synaptic
mechanisms with fast gamma oscillations (90-140 Hz). We show that (1) hippocampal
SPW-Rs and fast gamma oscillations are quantitatively distinct patterns but involve
the same networks and share similar mechanisms; (2) both the frequency and magnitude
of fast oscillations are positively correlated with the magnitude of SPWs; (3)
during both ripples and fast gamma oscillations the frequency of network oscillation
is higher in CA1 than in CA3; and (4) the emergence of CA3 population bursts,
a prerequisite for SPW-Rs, is biased by activity patterns in the dentate gyrus
and entorhinal cortex, with the highest probability of ripples associated with
an "optimum" level of dentate gamma power. We hypothesize that each
hippocampal subnetwork possesses distinct resonant properties, tuned by the magnitude
of the excitatory drive.
author:
- first_name: David
full_name: Sullivan, David W
last_name: Sullivan
- first_name: Jozsef L
full_name: Jozsef Csicsvari
id: 3FA14672-F248-11E8-B48F-1D18A9856A87
last_name: Csicsvari
orcid: 0000-0002-5193-4036
- first_name: Kenji
full_name: Mizuseki, Kenji
last_name: Mizuseki
- first_name: Sean
full_name: Montgomery, Sean M
last_name: Montgomery
- first_name: Kamran
full_name: Diba, Kamran
last_name: Diba
- first_name: György
full_name: Buzsáki, György
last_name: Buzsáki
citation:
ama: Sullivan D, Csicsvari JL, Mizuseki K, Montgomery S, Diba K, Buzsáki G. Relationships
between hippocampal sharp waves ripples and fast gamma oscillation Influence of
dentate and entorhinal cortical activity. Journal of Neuroscience. 2011;31(23):8605-8616.
doi:10.1523/JNEUROSCI.0294-11.2011
apa: Sullivan, D., Csicsvari, J. L., Mizuseki, K., Montgomery, S., Diba, K., &
Buzsáki, G. (2011). Relationships between hippocampal sharp waves ripples and
fast gamma oscillation Influence of dentate and entorhinal cortical activity.
Journal of Neuroscience. Society for Neuroscience. https://doi.org/10.1523/JNEUROSCI.0294-11.2011
chicago: Sullivan, David, Jozsef L Csicsvari, Kenji Mizuseki, Sean Montgomery, Kamran
Diba, and György Buzsáki. “Relationships between Hippocampal Sharp Waves Ripples
and Fast Gamma Oscillation Influence of Dentate and Entorhinal Cortical Activity.”
Journal of Neuroscience. Society for Neuroscience, 2011. https://doi.org/10.1523/JNEUROSCI.0294-11.2011.
ieee: D. Sullivan, J. L. Csicsvari, K. Mizuseki, S. Montgomery, K. Diba, and G.
Buzsáki, “Relationships between hippocampal sharp waves ripples and fast gamma
oscillation Influence of dentate and entorhinal cortical activity,” Journal
of Neuroscience, vol. 31, no. 23. Society for Neuroscience, pp. 8605–8616,
2011.
ista: Sullivan D, Csicsvari JL, Mizuseki K, Montgomery S, Diba K, Buzsáki G. 2011.
Relationships between hippocampal sharp waves ripples and fast gamma oscillation
Influence of dentate and entorhinal cortical activity. Journal of Neuroscience.
31(23), 8605–8616.
mla: Sullivan, David, et al. “Relationships between Hippocampal Sharp Waves Ripples
and Fast Gamma Oscillation Influence of Dentate and Entorhinal Cortical Activity.”
Journal of Neuroscience, vol. 31, no. 23, Society for Neuroscience, 2011,
pp. 8605–16, doi:10.1523/JNEUROSCI.0294-11.2011.
short: D. Sullivan, J.L. Csicsvari, K. Mizuseki, S. Montgomery, K. Diba, G. Buzsáki,
Journal of Neuroscience 31 (2011) 8605–8616.
date_created: 2018-12-11T12:01:36Z
date_published: 2011-06-08T00:00:00Z
date_updated: 2021-01-12T07:41:19Z
day: '08'
doi: 10.1523/JNEUROSCI.0294-11.2011
extern: 1
intvolume: ' 31'
issue: '23'
month: '06'
page: 8605 - 8616
publication: Journal of Neuroscience
publication_status: published
publisher: Society for Neuroscience
publist_id: '3559'
quality_controlled: 0
status: public
title: Relationships between hippocampal sharp waves ripples and fast gamma oscillation
Influence of dentate and entorhinal cortical activity
type: journal_article
volume: 31
year: '2011'
...
---
_id: '3204'
abstract:
- lang: eng
text: 'We introduce a new class of functions that can be minimized in polynomial
time in the value oracle model. These are functions f satisfying f(x) + f(y) ≥
f(x ∏ y) + f(x ∐ y) where the domain of each variable x i corresponds to nodes
of a rooted binary tree, and operations ∏,∐ are defined with respect to this tree.
Special cases include previously studied L-convex and bisubmodular functions,
which can be obtained with particular choices of trees. We present a polynomial-time
algorithm for minimizing functions in the new class. It combines Murota''s steepest
descent algorithm for L-convex functions with bisubmodular minimization algorithms. '
alternative_title:
- LNCS
author:
- first_name: Vladimir
full_name: Vladimir Kolmogorov
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Kolmogorov V. Submodularity on a tree: Unifying Submodularity on a tree: Unifying
L-convex and bisubmodular functions convex and bisubmodular functions. In: Vol
6907. Springer; 2011:400-411. doi:10.1007/978-3-642-22993-0_37'
apa: 'Kolmogorov, V. (2011). Submodularity on a tree: Unifying Submodularity on
a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions
(Vol. 6907, pp. 400–411). Presented at the MFCS: Mathematical Foundations of Computer
Science, Springer. https://doi.org/10.1007/978-3-642-22993-0_37'
chicago: 'Kolmogorov, Vladimir. “Submodularity on a Tree: Unifying Submodularity
on a Tree: Unifying L-Convex and Bisubmodular Functions Convex and Bisubmodular
Functions,” 6907:400–411. Springer, 2011. https://doi.org/10.1007/978-3-642-22993-0_37.'
ieee: 'V. Kolmogorov, “Submodularity on a tree: Unifying Submodularity on a tree:
Unifying L-convex and bisubmodular functions convex and bisubmodular functions,”
presented at the MFCS: Mathematical Foundations of Computer Science, 2011, vol.
6907, pp. 400–411.'
ista: 'Kolmogorov V. 2011. Submodularity on a tree: Unifying Submodularity on a
tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions.
MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 6907, 400–411.'
mla: 'Kolmogorov, Vladimir. Submodularity on a Tree: Unifying Submodularity on
a Tree: Unifying L-Convex and Bisubmodular Functions Convex and Bisubmodular Functions.
Vol. 6907, Springer, 2011, pp. 400–11, doi:10.1007/978-3-642-22993-0_37.'
short: V. Kolmogorov, in:, Springer, 2011, pp. 400–411.
conference:
name: 'MFCS: Mathematical Foundations of Computer Science'
date_created: 2018-12-11T12:02:00Z
date_published: 2011-08-09T00:00:00Z
date_updated: 2021-01-12T07:41:47Z
day: '09'
doi: 10.1007/978-3-642-22993-0_37
extern: 1
intvolume: ' 6907'
main_file_link:
- open_access: '0'
url: http://arxiv.org/pdf/1007.1229v3
month: '08'
page: 400 - 411
publication_status: published
publisher: Springer
publist_id: '3478'
quality_controlled: 0
status: public
title: 'Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex
and bisubmodular functions convex and bisubmodular functions'
type: conference
volume: 6907
year: '2011'
...
---
_id: '3236'
abstract:
- lang: eng
text: 'If a cryptographic primitive remains secure even if ℓ bits about the secret
key are leaked to the adversary, one would expect that at least one of n independent
instantiations of the scheme remains secure given n·ℓ bits of leakage. This intuition
has been proven true for schemes satisfying some special information-theoretic
properties by Alwen et al. [Eurocrypt''10]. On the negative side, Lewko and Waters
[FOCS''10] construct a CPA secure public-key encryption scheme for which this
intuition fails. The counterexample of Lewko and Waters leaves open the interesting
possibility that for any scheme there exists a constant c>0, such that n fold
repetition remains secure against c·n·ℓ bits of leakage. Furthermore, their counterexample
requires the n copies of the encryption scheme to share a common reference parameter,
leaving open the possibility that the intuition is true for all schemes without
common setup. In this work we give a stronger counterexample ruling out these
possibilities. We construct a signature scheme such that: 1. a single instantiation
remains secure given ℓ = log(k) bits of leakage where k is a security parameter.
2. any polynomial number of independent instantiations can be broken (in the strongest
sense of key-recovery) given ℓ′ = poly(k) bits of leakage. Note that ℓ does not
depend on the number of instances. The computational assumption underlying our
counterexample is that non-interactive computationally sound proofs exist. Moreover,
under a stronger (non-standard) assumption about such proofs, our counterexample
does not require a common reference parameter. The underlying idea of our counterexample
is rather generic and can be applied to other primitives like encryption schemes.
© 2011 International Association for Cryptologic Research.'
alternative_title:
- LNCS
author:
- first_name: Abhishek
full_name: Jain, Abhishek
last_name: Jain
- first_name: Krzysztof Z
full_name: Krzysztof Pietrzak
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Jain A, Pietrzak KZ. Parallel repetition for leakage resilience amplification
revisited. In: Vol 6597. Springer; 2011:58-69. doi:10.1007/978-3-642-19571-6_5'
apa: 'Jain, A., & Pietrzak, K. Z. (2011). Parallel repetition for leakage resilience
amplification revisited (Vol. 6597, pp. 58–69). Presented at the TCC: Theory of
Cryptography Conference, Springer. https://doi.org/10.1007/978-3-642-19571-6_5'
chicago: Jain, Abhishek, and Krzysztof Z Pietrzak. “Parallel Repetition for Leakage
Resilience Amplification Revisited,” 6597:58–69. Springer, 2011. https://doi.org/10.1007/978-3-642-19571-6_5.
ieee: 'A. Jain and K. Z. Pietrzak, “Parallel repetition for leakage resilience amplification
revisited,” presented at the TCC: Theory of Cryptography Conference, 2011, vol.
6597, pp. 58–69.'
ista: 'Jain A, Pietrzak KZ. 2011. Parallel repetition for leakage resilience amplification
revisited. TCC: Theory of Cryptography Conference, LNCS, vol. 6597, 58–69.'
mla: Jain, Abhishek, and Krzysztof Z. Pietrzak. Parallel Repetition for Leakage
Resilience Amplification Revisited. Vol. 6597, Springer, 2011, pp. 58–69,
doi:10.1007/978-3-642-19571-6_5.
short: A. Jain, K.Z. Pietrzak, in:, Springer, 2011, pp. 58–69.
conference:
name: 'TCC: Theory of Cryptography Conference'
date_created: 2018-12-11T12:02:11Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:00Z
day: '01'
doi: 10.1007/978-3-642-19571-6_5
extern: 1
month: '01'
page: 58 - 69
publication_status: published
publisher: Springer
publist_id: '3443'
quality_controlled: 0
status: public
title: Parallel repetition for leakage resilience amplification revisited
type: conference
volume: '6597 '
year: '2011'
...
---
_id: '3238'
abstract:
- lang: eng
text: We construct efficient authentication protocols and message-authentication
codes (MACs) whose security can be reduced to the learning parity with noise (LPN)
problem. Despite a large body of work - starting with the HB protocol of Hopper
and Blum in 2001 - until now it was not even known how to construct an efficient
authentication protocol from LPN which is secure against man-in-the-middle (MIM)
attacks. A MAC implies such a (two-round) protocol. © 2011 International Association
for Cryptologic Research
acknowledgement: The European Regional Development Fund (ERDF),Guardtime,Qualcomm,Swedbank
alternative_title:
- LNCS
author:
- first_name: Eike
full_name: Kiltz, Eike
last_name: Kiltz
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: David
full_name: Cash, David
last_name: Cash
- first_name: Abhishek
full_name: Jain, Abhishek
last_name: Jain
- first_name: Daniele
full_name: Venturi, Daniele
last_name: Venturi
citation:
ama: 'Kiltz E, Pietrzak KZ, Cash D, Jain A, Venturi D. Efficient authentication
from hard learning problems. In: Vol 6632. Springer; 2011:7-26. doi:10.1007/978-3-642-20465-4_3'
apa: 'Kiltz, E., Pietrzak, K. Z., Cash, D., Jain, A., & Venturi, D. (2011).
Efficient authentication from hard learning problems (Vol. 6632, pp. 7–26). Presented
at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Tallinn,
Estonia: Springer. https://doi.org/10.1007/978-3-642-20465-4_3'
chicago: Kiltz, Eike, Krzysztof Z Pietrzak, David Cash, Abhishek Jain, and Daniele
Venturi. “Efficient Authentication from Hard Learning Problems,” 6632:7–26. Springer,
2011. https://doi.org/10.1007/978-3-642-20465-4_3.
ieee: 'E. Kiltz, K. Z. Pietrzak, D. Cash, A. Jain, and D. Venturi, “Efficient authentication
from hard learning problems,” presented at the EUROCRYPT: Theory and Applications
of Cryptographic Techniques, Tallinn, Estonia, 2011, vol. 6632, pp. 7–26.'
ista: 'Kiltz E, Pietrzak KZ, Cash D, Jain A, Venturi D. 2011. Efficient authentication
from hard learning problems. EUROCRYPT: Theory and Applications of Cryptographic
Techniques, LNCS, vol. 6632, 7–26.'
mla: Kiltz, Eike, et al. Efficient Authentication from Hard Learning Problems.
Vol. 6632, Springer, 2011, pp. 7–26, doi:10.1007/978-3-642-20465-4_3.
short: E. Kiltz, K.Z. Pietrzak, D. Cash, A. Jain, D. Venturi, in:, Springer, 2011,
pp. 7–26.
conference:
end_date: 2011-05-19
location: Tallinn, Estonia
name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
start_date: 2011-05-15
date_created: 2018-12-11T12:02:11Z
date_published: 2011-05-01T00:00:00Z
date_updated: 2025-04-15T08:32:11Z
day: '01'
doi: 10.1007/978-3-642-20465-4_3
extern: '1'
intvolume: ' 6632'
language:
- iso: eng
month: '05'
oa_version: None
page: 7 - 26
publication_status: published
publisher: Springer
publist_id: '3442'
quality_controlled: '1'
related_material:
record:
- id: '1187'
relation: later_version
status: public
status: public
title: Efficient authentication from hard learning problems
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 6632
year: '2011'
...
---
_id: '3239'
abstract:
- lang: eng
text: Tampering attacks are cryptanalytic attacks on the implementation of cryptographic
algorithms (e.g., smart cards), where an adversary introduces faults with the
hope that the tampered device will reveal secret information. Inspired by the
work of Ishai et al. [Eurocrypt'06], we propose a compiler that transforms any
circuit into a new circuit with the same functionality, but which is resilient
against a well-defined and powerful tampering adversary. More concretely, our
transformed circuits remain secure even if the adversary can adaptively tamper
with every wire in the circuit as long as the tampering fails with some probability
δ>0. This additional requirement is motivated by practical tampering attacks,
where it is often difficult to guarantee the success of a specific attack. Formally,
we show that a q-query tampering attack against the transformed circuit can be
"simulated" with only black-box access to the original circuit and log(q)
bits of additional auxiliary information. Thus, if the implemented cryptographic
scheme is secure against log(q) bits of leakage, then our implementation is tamper-proof
in the above sense. Surprisingly, allowing for this small amount of information
leakage allows for much more efficient compilers, which moreover do not require
randomness during evaluation. Similar to earlier works our compiler requires small,
stateless and computation-independent tamper-proof gadgets. Thus, our result can
be interpreted as reducing the problem of shielding arbitrary complex computation
to protecting simple components. © 2011 Springer-Verlag.
alternative_title:
- LNCS
author:
- first_name: Sebastian
full_name: Faust, Sebastian
last_name: Faust
- first_name: Krzysztof Z
full_name: Krzysztof Pietrzak
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Daniele
full_name: Venturi, Daniele
last_name: Venturi
citation:
ama: 'Faust S, Pietrzak KZ, Venturi D. Tamper proof circuits How to trade leakage
for tamper resilience. In: Vol 6755. Springer; 2011:391-402. doi:10.1007/978-3-642-22006-7_33'
apa: 'Faust, S., Pietrzak, K. Z., & Venturi, D. (2011). Tamper proof circuits
How to trade leakage for tamper resilience (Vol. 6755, pp. 391–402). Presented
at the ICALP: Automata, Languages and Programming, Springer. https://doi.org/10.1007/978-3-642-22006-7_33'
chicago: Faust, Sebastian, Krzysztof Z Pietrzak, and Daniele Venturi. “Tamper Proof
Circuits How to Trade Leakage for Tamper Resilience,” 6755:391–402. Springer,
2011. https://doi.org/10.1007/978-3-642-22006-7_33.
ieee: 'S. Faust, K. Z. Pietrzak, and D. Venturi, “Tamper proof circuits How to trade
leakage for tamper resilience,” presented at the ICALP: Automata, Languages and
Programming, 2011, vol. 6755, no. Part 1, pp. 391–402.'
ista: 'Faust S, Pietrzak KZ, Venturi D. 2011. Tamper proof circuits How to trade
leakage for tamper resilience. ICALP: Automata, Languages and Programming, LNCS,
vol. 6755, 391–402.'
mla: Faust, Sebastian, et al. Tamper Proof Circuits How to Trade Leakage for
Tamper Resilience. Vol. 6755, no. Part 1, Springer, 2011, pp. 391–402, doi:10.1007/978-3-642-22006-7_33.
short: S. Faust, K.Z. Pietrzak, D. Venturi, in:, Springer, 2011, pp. 391–402.
conference:
name: 'ICALP: Automata, Languages and Programming'
date_created: 2018-12-11T12:02:12Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:02Z
day: '01'
doi: 10.1007/978-3-642-22006-7_33
extern: 1
issue: Part 1
month: '01'
page: 391 - 402
publication_status: published
publisher: Springer
publist_id: '3441'
quality_controlled: 0
status: public
title: Tamper proof circuits How to trade leakage for tamper resilience
type: conference
volume: '6755 '
year: '2011'
...
---
_id: '3240'
abstract:
- lang: eng
text: 'The famous Leftover Hash Lemma (LHL) states that (almost) universal hash
functions are good randomness extractors. Despite its numerous applications, LHL-based
extractors suffer from the following two limitations: - Large Entropy Loss: to
extract v bits from distribution X of min-entropy m which are ε-close to uniform,
one must set v ≤ m - 2log(1/ε), meaning that the entropy loss L = def m - v ≥
2 log(1/ε). For many applications, such entropy loss is too large. - Large Seed
Length: the seed length n of (almost) universal hash function required by the
LHL must be at least n ≥ min (u - v, v + 2log(1/ε)) - O(1), where u is the length
of the source, and must grow with the number of extracted bits. Quite surprisingly,
we show that both limitations of the LHL - large entropy loss and large seed -
can be overcome (or, at least, mitigated) in various important scenarios. First,
we show that entropy loss could be reduced to L = log(1/ε) for the setting of
deriving secret keys for a wide range of cryptographic applications. Specifically,
the security of these schemes with an LHL-derived key gracefully degrades from
ε to at most ε + √ε2-L. (Notice that, unlike standard LHL, this bound is meaningful
even when one extracts more bits than the min-entropy we have!) Based on these
results we build a general computational extractor that enjoys low entropy loss
and can be used to instantiate a generic key derivation function for any cryptographic
application. Second, we study the soundness of the natural expand-then-extract
approach, where one uses a pseudorandom generator (PRG) to expand a short "input
seed" S into a longer "output seed" S′, and then use the resulting
S′ as the seed required by the LHL (or, more generally, by any randomness extractor).
We show that, in general, the expand-then-extract approach is not sound if the
Decisional Diffie-Hellman assumption is true. Despite that, we show that it is
sound either: (1) when extracting a "small" (logarithmic in the security
of the PRG) number of bits; or (2) in minicrypt. Implication (2) suggests that
the expand-then-extract approach is likely secure when used with "practical"
PRGs, despite lacking a reductionist proof of security! © 2011 International Association
for Cryptologic Research.'
alternative_title:
- LNCS
author:
- first_name: Boaz
full_name: Barak, Boaz
last_name: Barak
- first_name: Yevgeniy
full_name: Dodis, Yevgeniy
last_name: Dodis
- first_name: Hugo
full_name: Krawczyk, Hugo
last_name: Krawczyk
- first_name: Olivier
full_name: Pereira, Olivier
last_name: Pereira
- first_name: Krzysztof Z
full_name: Krzysztof Pietrzak
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: François
full_name: Standaert, François-Xavier
last_name: Standaert
- first_name: Yu
full_name: Yu, Yu
last_name: Yu
citation:
ama: 'Barak B, Dodis Y, Krawczyk H, et al. Leftover hash lemma revisited. In: Vol
6841. Springer; 2011:1-20. doi:
10.1007/978-3-642-22792-9_1'
apa: 'Barak, B., Dodis, Y., Krawczyk, H., Pereira, O., Pietrzak, K. Z., Standaert,
F., & Yu, Y. (2011). Leftover hash lemma revisited (Vol. 6841, pp. 1–20).
Presented at the CRYPTO: International Cryptology Conference, Springer. https://doi.org/ 10.1007/978-3-642-22792-9_1'
chicago: Barak, Boaz, Yevgeniy Dodis, Hugo Krawczyk, Olivier Pereira, Krzysztof
Z Pietrzak, François Standaert, and Yu Yu. “Leftover Hash Lemma Revisited,” 6841:1–20.
Springer, 2011. https://doi.org/
10.1007/978-3-642-22792-9_1.
ieee: 'B. Barak et al., “Leftover hash lemma revisited,” presented at the
CRYPTO: International Cryptology Conference, 2011, vol. 6841, pp. 1–20.'
ista: 'Barak B, Dodis Y, Krawczyk H, Pereira O, Pietrzak KZ, Standaert F, Yu Y.
2011. Leftover hash lemma revisited. CRYPTO: International Cryptology Conference,
LNCS, vol. 6841, 1–20.'
mla: Barak, Boaz, et al. Leftover Hash Lemma Revisited. Vol. 6841, Springer,
2011, pp. 1–20, doi: 10.1007/978-3-642-22792-9_1.
short: B. Barak, Y. Dodis, H. Krawczyk, O. Pereira, K.Z. Pietrzak, F. Standaert,
Y. Yu, in:, Springer, 2011, pp. 1–20.
conference:
name: 'CRYPTO: International Cryptology Conference'
date_created: 2018-12-11T12:02:12Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:03Z
day: '01'
doi: ' 10.1007/978-3-642-22792-9_1'
extern: 1
intvolume: ' 6841'
month: '01'
page: 1 - 20
publication_status: published
publisher: Springer
publist_id: '3440'
quality_controlled: 0
status: public
title: Leftover hash lemma revisited
type: conference
volume: 6841
year: '2011'
...
---
_id: '3264'
abstract:
- lang: eng
text: Verification of programs with procedures, multi-threaded programs, and higher-order
functional programs can be effectively au- tomated using abstraction and refinement
schemes that rely on spurious counterexamples for abstraction discovery. The analysis
of counterexam- ples can be automated by a series of interpolation queries, or,
alterna- tively, as a constraint solving query expressed by a set of recursion
free Horn clauses. (A set of interpolation queries can be formulated as a single
constraint over Horn clauses with linear dependency structure between the unknown
relations.) In this paper we present an algorithm for solving recursion free Horn
clauses over a combined theory of linear real/rational arithmetic and uninterpreted
functions. Our algorithm performs resolu- tion to deal with the clausal structure
and relies on partial solutions to deal with (non-local) instances of functionality
axioms.
alternative_title:
- LNCS
author:
- first_name: Ashutosh
full_name: Gupta, Ashutosh
id: 335E5684-F248-11E8-B48F-1D18A9856A87
last_name: Gupta
- first_name: Corneliu
full_name: Popeea, Corneliu
last_name: Popeea
- first_name: Andrey
full_name: Rybalchenko, Andrey
last_name: Rybalchenko
citation:
ama: 'Gupta A, Popeea C, Rybalchenko A. Solving recursion-free Horn clauses over
LI+UIF. In: Yang H, ed. Vol 7078. Springer; 2011:188-203. doi:10.1007/978-3-642-25318-8_16'
apa: 'Gupta, A., Popeea, C., & Rybalchenko, A. (2011). Solving recursion-free
Horn clauses over LI+UIF. In H. Yang (Ed.) (Vol. 7078, pp. 188–203). Presented
at the APLAS: Asian Symposium on Programming Languages and Systems, Kenting, Taiwan:
Springer. https://doi.org/10.1007/978-3-642-25318-8_16'
chicago: Gupta, Ashutosh, Corneliu Popeea, and Andrey Rybalchenko. “Solving Recursion-Free
Horn Clauses over LI+UIF.” edited by Hongseok Yang, 7078:188–203. Springer, 2011.
https://doi.org/10.1007/978-3-642-25318-8_16.
ieee: 'A. Gupta, C. Popeea, and A. Rybalchenko, “Solving recursion-free Horn clauses
over LI+UIF,” presented at the APLAS: Asian Symposium on Programming Languages
and Systems, Kenting, Taiwan, 2011, vol. 7078, pp. 188–203.'
ista: 'Gupta A, Popeea C, Rybalchenko A. 2011. Solving recursion-free Horn clauses
over LI+UIF. APLAS: Asian Symposium on Programming Languages and Systems, LNCS,
vol. 7078, 188–203.'
mla: Gupta, Ashutosh, et al. Solving Recursion-Free Horn Clauses over LI+UIF.
Edited by Hongseok Yang, vol. 7078, Springer, 2011, pp. 188–203, doi:10.1007/978-3-642-25318-8_16.
short: A. Gupta, C. Popeea, A. Rybalchenko, in:, H. Yang (Ed.), Springer, 2011,
pp. 188–203.
conference:
end_date: 2011-12-07
location: Kenting, Taiwan
name: 'APLAS: Asian Symposium on Programming Languages and Systems'
start_date: 2011-12-05
date_created: 2018-12-11T12:02:20Z
date_published: 2011-12-05T00:00:00Z
date_updated: 2024-10-21T06:03:01Z
day: '05'
department:
- _id: ToHe
doi: 10.1007/978-3-642-25318-8_16
ec_funded: 1
editor:
- first_name: Hongseok
full_name: Yang, Hongseok
last_name: Yang
intvolume: ' 7078'
language:
- iso: eng
month: '12'
oa_version: None
page: 188 - 203
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication_status: published
publisher: Springer
publist_id: '3383'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Solving recursion-free Horn clauses over LI+UIF
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 7078
year: '2011'
...