---
_id: '1659'
abstract:
- lang: eng
text: 'The target discounted-sum problem is the following: Given a rational discount
factor 0 < λ < 1 and three rational values a, b, and t, does there exist
a finite or an infinite sequence w ε(a, b)∗ or w ε(a, b)w, such that Σ|w| i=0
w(i)λi equals t? The problem turns out to relate to many fields of mathematics
and computer science, and its decidability question is surprisingly hard to solve.
We solve the finite version of the problem, and show the hardness of the infinite
version, linking it to various areas and open problems in mathematics and computer
science: β-expansions, discounted-sum automata, piecewise affine maps, and generalizations
of the Cantor set. We provide some partial results to the infinite version, among
which are solutions to its restriction to eventually-periodic sequences and to
the cases that λ λ 1/2 or λ = 1/n, for every n ε N. We use our results for solving
some open problems on discounted-sum automata, among which are the exact-value
problem for nondeterministic automata over finite words and the universality and
inclusion problems for functional automata.'
acknowledgement: 'A technical report of the article is available at: https://research-explorer.app.ist.ac.at/record/5439'
article_processing_charge: No
author:
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- 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: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
citation:
ama: 'Boker U, Henzinger TA, Otop J. The target discounted-sum problem. In: LICS.
Logic in Computer Science. IEEE; 2015:750-761. doi:10.1109/LICS.2015.74'
apa: 'Boker, U., Henzinger, T. A., & Otop, J. (2015). The target discounted-sum
problem. In LICS (pp. 750–761). Kyoto, Japan: IEEE. https://doi.org/10.1109/LICS.2015.74'
chicago: Boker, Udi, Thomas A Henzinger, and Jan Otop. “The Target Discounted-Sum
Problem.” In LICS, 750–61. Logic in Computer Science. IEEE, 2015. https://doi.org/10.1109/LICS.2015.74.
ieee: U. Boker, T. A. Henzinger, and J. Otop, “The target discounted-sum problem,”
in LICS, Kyoto, Japan, 2015, pp. 750–761.
ista: 'Boker U, Henzinger TA, Otop J. 2015. The target discounted-sum problem. LICS.
LICS: Logic in Computer ScienceLogic in Computer Science, 750–761.'
mla: Boker, Udi, et al. “The Target Discounted-Sum Problem.” LICS, IEEE,
2015, pp. 750–61, doi:10.1109/LICS.2015.74.
short: U. Boker, T.A. Henzinger, J. Otop, in:, LICS, IEEE, 2015, pp. 750–761.
conference:
end_date: 2015-07-10
location: Kyoto, Japan
name: 'LICS: Logic in Computer Science'
start_date: 2015-007-06
date_created: 2018-12-11T11:53:19Z
date_published: 2015-07-01T00:00:00Z
date_updated: 2023-02-23T12:26:27Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1109/LICS.2015.74
ec_funded: 1
file:
- access_level: open_access
checksum: 6abebca9c1a620e9e103a8f9222befac
content_type: application/pdf
creator: dernst
date_created: 2020-05-15T08:53:29Z
date_updated: 2020-07-14T12:45:10Z
file_id: '7852'
file_name: 2015_LICS_Boker.pdf
file_size: 340215
relation: main_file
file_date_updated: 2020-07-14T12:45:10Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 750 - 761
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
publication: LICS
publication_identifier:
eisbn:
- '978-1-4799-8875-4 '
issn:
- '1043-6871 '
publication_status: published
publisher: IEEE
publist_id: '5491'
quality_controlled: '1'
related_material:
record:
- id: '5439'
relation: earlier_version
status: public
scopus_import: 1
series_title: Logic in Computer Science
status: public
title: The target discounted-sum problem
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '1660'
abstract:
- lang: eng
text: We study the pattern frequency vector for runs in probabilistic Vector Addition
Systems with States (pVASS). Intuitively, each configuration of a given pVASS
is assigned one of finitely many patterns, and every run can thus be seen as an
infinite sequence of these patterns. The pattern frequency vector assigns to each
run the limit of pattern frequencies computed for longer and longer prefixes of
the run. If the limit does not exist, then the vector is undefined. We show that
for one-counter pVASS, the pattern frequency vector is defined and takes one of
finitely many values for almost all runs. Further, these values and their associated
probabilities can be approximated up to an arbitrarily small relative error in
polynomial time. For stable two-counter pVASS, we show the same result, but we
do not provide any upper complexity bound. As a byproduct of our study, we discover
counterexamples falsifying some classical results about stochastic Petri nets
published in the 80s.
alternative_title:
- LICS
author:
- first_name: Tomáš
full_name: Brázdil, Tomáš
last_name: Brázdil
- first_name: Stefan
full_name: Kiefer, Stefan
last_name: Kiefer
- first_name: Antonín
full_name: Kučera, Antonín
last_name: Kučera
- first_name: Petr
full_name: Novotny, Petr
id: 3CC3B868-F248-11E8-B48F-1D18A9856A87
last_name: Novotny
citation:
ama: 'Brázdil T, Kiefer S, Kučera A, Novotný P. Long-run average behaviour of probabilistic
vector addition systems. In: IEEE; 2015:44-55. doi:10.1109/LICS.2015.15'
apa: 'Brázdil, T., Kiefer, S., Kučera, A., & Novotný, P. (2015). Long-run average
behaviour of probabilistic vector addition systems (pp. 44–55). Presented at the
LICS: Logic in Computer Science, Kyoto, Japan: IEEE. https://doi.org/10.1109/LICS.2015.15'
chicago: Brázdil, Tomáš, Stefan Kiefer, Antonín Kučera, and Petr Novotný. “Long-Run
Average Behaviour of Probabilistic Vector Addition Systems,” 44–55. IEEE, 2015.
https://doi.org/10.1109/LICS.2015.15.
ieee: 'T. Brázdil, S. Kiefer, A. Kučera, and P. Novotný, “Long-run average behaviour
of probabilistic vector addition systems,” presented at the LICS: Logic in Computer
Science, Kyoto, Japan, 2015, pp. 44–55.'
ista: 'Brázdil T, Kiefer S, Kučera A, Novotný P. 2015. Long-run average behaviour
of probabilistic vector addition systems. LICS: Logic in Computer Science, LICS,
, 44–55.'
mla: Brázdil, Tomáš, et al. Long-Run Average Behaviour of Probabilistic Vector
Addition Systems. IEEE, 2015, pp. 44–55, doi:10.1109/LICS.2015.15.
short: T. Brázdil, S. Kiefer, A. Kučera, P. Novotný, in:, IEEE, 2015, pp. 44–55.
conference:
end_date: 2015-07-10
location: Kyoto, Japan
name: 'LICS: Logic in Computer Science'
start_date: 2015-07-06
date_created: 2018-12-11T11:53:19Z
date_published: 2015-07-01T00:00:00Z
date_updated: 2021-01-12T06:52:20Z
day: '01'
department:
- _id: KrCh
doi: 10.1109/LICS.2015.15
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1505.02655
month: '07'
oa: 1
oa_version: Preprint
page: 44 - 55
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: IEEE
publist_id: '5490'
quality_controlled: '1'
scopus_import: 1
status: public
title: Long-run average behaviour of probabilistic vector addition systems
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '1661'
abstract:
- lang: eng
text: The computation of the winning set for one-pair Streett objectives and for
k-pair Streett objectives in (standard) graphs as well as in game graphs are central
problems in computer-aided verification, with application to the verification
of closed systems with strong fairness conditions, the verification of open systems,
checking interface compatibility, well-formed ness of specifications, and the
synthesis of reactive systems. We give faster algorithms for the computation of
the winning set for (1) one-pair Streett objectives (aka parity-3 problem) in
game graphs and (2) for k-pair Streett objectives in graphs. For both problems
this represents the first improvement in asymptotic running time in 15 years.
acknowledgement: 'K. C. is supported by the Austrian Science Fund (FWF): P23499-N23
and S11407-N23 (RiSE), an ERC Start Grant (279307: Graph Games), and a Microsoft
Faculty Fellows Award. M. H. is supported by the Austrian Science Fund (FWF): P23499-N23
and the Vienna Science and Technology Fund (WWTF) grant ICT10-002. V. L. is supported
by the Vienna Science and Technology Fund (WWTF) grant ICT10-002. The research leading
to these results has received funding from the European Research Council under the
European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement
no. 340506.'
article_number: '7174888'
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
- first_name: Veronika
full_name: Loitzenbauer, Veronika
last_name: Loitzenbauer
citation:
ama: 'Chatterjee K, Henzinger MH, Loitzenbauer V. Improved algorithms for one-pair
and k-pair Streett objectives. In: Proceedings - Symposium on Logic in Computer
Science. Vol 2015-July. IEEE; 2015. doi:10.1109/LICS.2015.34'
apa: 'Chatterjee, K., Henzinger, M. H., & Loitzenbauer, V. (2015). Improved
algorithms for one-pair and k-pair Streett objectives. In Proceedings - Symposium
on Logic in Computer Science (Vol. 2015–July). Kyoto, Japan: IEEE. https://doi.org/10.1109/LICS.2015.34'
chicago: Chatterjee, Krishnendu, Monika H Henzinger, and Veronika Loitzenbauer.
“Improved Algorithms for One-Pair and k-Pair Streett Objectives.” In Proceedings
- Symposium on Logic in Computer Science, Vol. 2015–July. IEEE, 2015. https://doi.org/10.1109/LICS.2015.34.
ieee: K. Chatterjee, M. H. Henzinger, and V. Loitzenbauer, “Improved algorithms
for one-pair and k-pair Streett objectives,” in Proceedings - Symposium on
Logic in Computer Science, Kyoto, Japan, 2015, vol. 2015–July.
ista: 'Chatterjee K, Henzinger MH, Loitzenbauer V. 2015. Improved algorithms for
one-pair and k-pair Streett objectives. Proceedings - Symposium on Logic in Computer
Science. LICS: Logic in Computer Science vol. 2015–July, 7174888.'
mla: Chatterjee, Krishnendu, et al. “Improved Algorithms for One-Pair and k-Pair
Streett Objectives.” Proceedings - Symposium on Logic in Computer Science,
vol. 2015–July, 7174888, IEEE, 2015, doi:10.1109/LICS.2015.34.
short: K. Chatterjee, M.H. Henzinger, V. Loitzenbauer, in:, Proceedings - Symposium
on Logic in Computer Science, IEEE, 2015.
conference:
end_date: 2015-07-10
location: Kyoto, Japan
name: 'LICS: Logic in Computer Science'
start_date: 2015-07-06
date_created: 2018-12-11T11:53:19Z
date_published: 2015-07-01T00:00:00Z
date_updated: 2025-06-02T08:53:41Z
day: '01'
department:
- _id: KrCh
doi: 10.1109/LICS.2015.34
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprints.cs.univie.ac.at/4368/
month: '07'
oa: 1
oa_version: Submitted Version
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'
publication: Proceedings - Symposium on Logic in Computer Science
publication_status: published
publisher: IEEE
publist_id: '5489'
quality_controlled: '1'
related_material:
record:
- id: '464'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Improved algorithms for one-pair and k-pair Streett objectives
type: conference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 2015-July
year: '2015'
...
---
_id: '1663'
abstract:
- lang: eng
text: CREB-binding protein (CBP) and p300 are transcriptional coactivators involved
in numerous biological processes that affect cell growth, transformation, differentiation,
and development. In this study, we provide evidence of the involvement of homeodomain-interacting
protein kinase 2 (HIPK2) in the regulation of CBP activity. We show that HIPK2
interacts with and phosphorylates several regions of CBP. We demonstrate that
serines 2361, 2363, 2371, 2376, and 2381 are responsible for the HIPK2-induced
mobility shift of CBP C-terminal activation domain. Moreover, we show that HIPK2
strongly potentiates the transcriptional activity of CBP. However, our data suggest
that HIPK2 activates CBP mainly by counteracting the repressive action of cell
cycle regulatory domain 1 (CRD1), located between amino acids 977 and 1076, independently
of CBP phosphorylation. Our findings thus highlight a complex regulation of CBP
activity by HIPK2, which might be relevant for the control of specific sets of
target genes involved in cellular proliferation, differentiation and apoptosis.
author:
- first_name: Krisztián
full_name: Kovács, Krisztián
id: 2AB5821E-F248-11E8-B48F-1D18A9856A87
last_name: Kovács
- first_name: Myriam
full_name: Steinmann, Myriam
last_name: Steinmann
- first_name: Olivier
full_name: Halfon, Olivier
last_name: Halfon
- first_name: Pierre
full_name: Magistretti, Pierre
last_name: Magistretti
- first_name: Jean
full_name: Cardinaux, Jean
last_name: Cardinaux
citation:
ama: Kovács K, Steinmann M, Halfon O, Magistretti P, Cardinaux J. Complex regulation
of CREB-binding protein by homeodomain-interacting protein kinase 2. Cellular
Signalling. 2015;27(11):2252-2260. doi:10.1016/j.cellsig.2015.08.001
apa: Kovács, K., Steinmann, M., Halfon, O., Magistretti, P., & Cardinaux, J.
(2015). Complex regulation of CREB-binding protein by homeodomain-interacting
protein kinase 2. Cellular Signalling. Elsevier. https://doi.org/10.1016/j.cellsig.2015.08.001
chicago: Kovács, Krisztián, Myriam Steinmann, Olivier Halfon, Pierre Magistretti,
and Jean Cardinaux. “Complex Regulation of CREB-Binding Protein by Homeodomain-Interacting
Protein Kinase 2.” Cellular Signalling. Elsevier, 2015. https://doi.org/10.1016/j.cellsig.2015.08.001.
ieee: K. Kovács, M. Steinmann, O. Halfon, P. Magistretti, and J. Cardinaux, “Complex
regulation of CREB-binding protein by homeodomain-interacting protein kinase 2,”
Cellular Signalling, vol. 27, no. 11. Elsevier, pp. 2252–2260, 2015.
ista: Kovács K, Steinmann M, Halfon O, Magistretti P, Cardinaux J. 2015. Complex
regulation of CREB-binding protein by homeodomain-interacting protein kinase 2.
Cellular Signalling. 27(11), 2252–2260.
mla: Kovács, Krisztián, et al. “Complex Regulation of CREB-Binding Protein by Homeodomain-Interacting
Protein Kinase 2.” Cellular Signalling, vol. 27, no. 11, Elsevier, 2015,
pp. 2252–60, doi:10.1016/j.cellsig.2015.08.001.
short: K. Kovács, M. Steinmann, O. Halfon, P. Magistretti, J. Cardinaux, Cellular
Signalling 27 (2015) 2252–2260.
date_created: 2018-12-11T11:53:20Z
date_published: 2015-11-01T00:00:00Z
date_updated: 2021-01-12T06:52:22Z
day: '01'
ddc:
- '570'
department:
- _id: JoCs
doi: 10.1016/j.cellsig.2015.08.001
ec_funded: 1
file:
- access_level: local
checksum: 4ee690b6444b7a43523237f0941457d1
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:18:03Z
date_updated: 2020-07-14T12:45:10Z
file_id: '5321'
file_name: IST-2016-578-v1+1_CLS-D-15-00072R1_.pdf
file_size: 1735337
relation: main_file
file_date_updated: 2020-07-14T12:45:10Z
has_accepted_license: '1'
intvolume: ' 27'
issue: '11'
language:
- iso: eng
month: '11'
oa_version: Published Version
page: 2252 - 2260
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Cellular Signalling
publication_status: published
publisher: Elsevier
publist_id: '5487'
pubrep_id: '578'
quality_controlled: '1'
scopus_import: 1
status: public
title: Complex regulation of CREB-binding protein by homeodomain-interacting protein
kinase 2
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 27
year: '2015'
...
---
_id: '1664'
abstract:
- lang: eng
text: Over a century of research into the origin of turbulence in wall-bounded shear
flows has resulted in a puzzling picture in which turbulence appears in a variety
of different states competing with laminar background flow. At moderate flow speeds,
turbulence is confined to localized patches; it is only at higher speeds that
the entire flow becomes turbulent. The origin of the different states encountered
during this transition, the front dynamics of the turbulent regions and the transformation
to full turbulence have yet to be explained. By combining experiments, theory
and computer simulations, here we uncover a bifurcation scenario that explains
the transformation to fully turbulent pipe flow and describe the front dynamics
of the different states encountered in the process. Key to resolving this problem
is the interpretation of the flow as a bistable system with nonlinear propagation
(advection) of turbulent fronts. These findings bridge the gap between our understanding
of the onset of turbulence and fully turbulent flows.
acknowledgement: We acknowledge the Deutsche Forschungsgemeinschaft (Project No. FOR
1182), and the European Research Council under the European Union’s Seventh Framework
Programme (FP/2007-2013)/ERC Grant Agreement 306589 for financial support. B.S.
acknowledges financial support from the Chinese State Scholarship Fund under grant
number 2010629145. B.S. acknowledges support from the International Max Planck Research
School for the Physics of Biological and Complex Systems and the Göttingen Graduate
School for Neurosciences and Molecular Biosciences. We acknowledge computing resources
from GWDG (Gesellschaft für wissenschaftliche Datenverarbeitung Göttingen) and the
Jülich Supercomputing Centre (grant HGU16) where the simulations were performed.
author:
- first_name: Dwight
full_name: Barkley, Dwight
last_name: Barkley
- first_name: Baofang
full_name: Song, Baofang
last_name: Song
- first_name: Mukund
full_name: Vasudevan, Mukund
id: 3C5A959A-F248-11E8-B48F-1D18A9856A87
last_name: Vasudevan
- first_name: Grégoire M
full_name: Lemoult, Grégoire M
id: 4787FE80-F248-11E8-B48F-1D18A9856A87
last_name: Lemoult
- first_name: Marc
full_name: Avila, Marc
last_name: Avila
- first_name: Björn
full_name: Hof, Björn
id: 3A374330-F248-11E8-B48F-1D18A9856A87
last_name: Hof
orcid: 0000-0003-2057-2754
citation:
ama: Barkley D, Song B, Vasudevan M, Lemoult GM, Avila M, Hof B. The rise of fully
turbulent flow. Nature. 2015;526(7574):550-553. doi:10.1038/nature15701
apa: Barkley, D., Song, B., Vasudevan, M., Lemoult, G. M., Avila, M., & Hof,
B. (2015). The rise of fully turbulent flow. Nature. Nature Publishing
Group. https://doi.org/10.1038/nature15701
chicago: Barkley, Dwight, Baofang Song, Mukund Vasudevan, Grégoire M Lemoult, Marc
Avila, and Björn Hof. “The Rise of Fully Turbulent Flow.” Nature. Nature
Publishing Group, 2015. https://doi.org/10.1038/nature15701.
ieee: D. Barkley, B. Song, M. Vasudevan, G. M. Lemoult, M. Avila, and B. Hof, “The
rise of fully turbulent flow,” Nature, vol. 526, no. 7574. Nature Publishing
Group, pp. 550–553, 2015.
ista: Barkley D, Song B, Vasudevan M, Lemoult GM, Avila M, Hof B. 2015. The rise
of fully turbulent flow. Nature. 526(7574), 550–553.
mla: Barkley, Dwight, et al. “The Rise of Fully Turbulent Flow.” Nature,
vol. 526, no. 7574, Nature Publishing Group, 2015, pp. 550–53, doi:10.1038/nature15701.
short: D. Barkley, B. Song, M. Vasudevan, G.M. Lemoult, M. Avila, B. Hof, Nature
526 (2015) 550–553.
date_created: 2018-12-11T11:53:20Z
date_published: 2015-10-21T00:00:00Z
date_updated: 2021-01-12T06:52:22Z
day: '21'
department:
- _id: BjHo
doi: 10.1038/nature15701
ec_funded: 1
intvolume: ' 526'
issue: '7574'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1510.09143
month: '10'
oa: 1
oa_version: Preprint
page: 550 - 553
project:
- _id: 25152F3A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '306589'
name: Decoding the complexity of turbulence at its origin
publication: Nature
publication_status: published
publisher: Nature Publishing Group
publist_id: '5485'
quality_controlled: '1'
scopus_import: 1
status: public
title: The rise of fully turbulent flow
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 526
year: '2015'
...
---
_id: '1665'
abstract:
- lang: eng
text: Which genetic alterations drive tumorigenesis and how they evolve over the
course of disease and therapy are central questions in cancer biology. Here we
identify 44 recurrently mutated genes and 11 recurrent somatic copy number variations
through whole-exome sequencing of 538 chronic lymphocytic leukaemia (CLL) and
matched germline DNA samples, 278 of which were collected in a prospective clinical
trial. These include previously unrecognized putative cancer drivers (RPS15, IKZF3),
and collectively identify RNA processing and export, MYC activity, and MAPK signalling
as central pathways involved in CLL. Clonality analysis of this large data set
further enabled reconstruction of temporal relationships between driver events.
Direct comparison between matched pre-treatment and relapse samples from 59 patients
demonstrated highly frequent clonal evolution. Thus, large sequencing data sets
of clinically informative samples enable the discovery of novel genes associated
with cancer, the network of relationships between the driver events, and their
impact on disease relapse and clinical outcome.
article_processing_charge: No
article_type: original
author:
- first_name: Dan
full_name: Landau, Dan
last_name: Landau
- first_name: Eugen
full_name: Tausch, Eugen
last_name: Tausch
- first_name: Amaro
full_name: Taylor Weiner, Amaro
last_name: Taylor Weiner
- first_name: Chip
full_name: Stewart, Chip
last_name: Stewart
- first_name: Johannes
full_name: Reiter, Johannes
id: 4A918E98-F248-11E8-B48F-1D18A9856A87
last_name: Reiter
orcid: 0000-0002-0170-7353
- first_name: Jasmin
full_name: Bahlo, Jasmin
last_name: Bahlo
- first_name: Sandra
full_name: Kluth, Sandra
last_name: Kluth
- first_name: Ivana
full_name: Božić, Ivana
last_name: Božić
- first_name: Michael
full_name: Lawrence, Michael
last_name: Lawrence
- first_name: Sebastian
full_name: Böttcher, Sebastian
last_name: Böttcher
- first_name: Scott
full_name: Carter, Scott
last_name: Carter
- first_name: Kristian
full_name: Cibulskis, Kristian
last_name: Cibulskis
- first_name: Daniel
full_name: Mertens, Daniel
last_name: Mertens
- first_name: Carrie
full_name: Sougnez, Carrie
last_name: Sougnez
- first_name: Mara
full_name: Rosenberg, Mara
last_name: Rosenberg
- first_name: Julian
full_name: Hess, Julian
last_name: Hess
- first_name: Jennifer
full_name: Edelmann, Jennifer
last_name: Edelmann
- first_name: Sabrina
full_name: Kless, Sabrina
last_name: Kless
- first_name: Michael
full_name: Kneba, Michael
last_name: Kneba
- first_name: Matthias
full_name: Ritgen, Matthias
last_name: Ritgen
- first_name: Anna
full_name: Fink, Anna
last_name: Fink
- first_name: Kirsten
full_name: Fischer, Kirsten
last_name: Fischer
- first_name: Stacey
full_name: Gabriel, Stacey
last_name: Gabriel
- first_name: Eric
full_name: Lander, Eric
last_name: Lander
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
- first_name: Hartmut
full_name: Döhner, Hartmut
last_name: Döhner
- first_name: Michael
full_name: Hallek, Michael
last_name: Hallek
- first_name: Donna
full_name: Neuberg, Donna
last_name: Neuberg
- first_name: Gad
full_name: Getz, Gad
last_name: Getz
- first_name: Stephan
full_name: Stilgenbauer, Stephan
last_name: Stilgenbauer
- first_name: Catherine
full_name: Wu, Catherine
last_name: Wu
citation:
ama: Landau D, Tausch E, Taylor Weiner A, et al. Mutations driving CLL and their
evolution in progression and relapse. Nature. 2015;526(7574):525-530. doi:10.1038/nature15395
apa: Landau, D., Tausch, E., Taylor Weiner, A., Stewart, C., Reiter, J., Bahlo,
J., … Wu, C. (2015). Mutations driving CLL and their evolution in progression
and relapse. Nature. Nature Publishing Group. https://doi.org/10.1038/nature15395
chicago: Landau, Dan, Eugen Tausch, Amaro Taylor Weiner, Chip Stewart, Johannes
Reiter, Jasmin Bahlo, Sandra Kluth, et al. “Mutations Driving CLL and Their Evolution
in Progression and Relapse.” Nature. Nature Publishing Group, 2015. https://doi.org/10.1038/nature15395.
ieee: D. Landau et al., “Mutations driving CLL and their evolution in progression
and relapse,” Nature, vol. 526, no. 7574. Nature Publishing Group, pp.
525–530, 2015.
ista: Landau D, Tausch E, Taylor Weiner A, Stewart C, Reiter J, Bahlo J, Kluth S,
Božić I, Lawrence M, Böttcher S, Carter S, Cibulskis K, Mertens D, Sougnez C,
Rosenberg M, Hess J, Edelmann J, Kless S, Kneba M, Ritgen M, Fink A, Fischer K,
Gabriel S, Lander E, Nowak M, Döhner H, Hallek M, Neuberg D, Getz G, Stilgenbauer
S, Wu C. 2015. Mutations driving CLL and their evolution in progression and relapse.
Nature. 526(7574), 525–530.
mla: Landau, Dan, et al. “Mutations Driving CLL and Their Evolution in Progression
and Relapse.” Nature, vol. 526, no. 7574, Nature Publishing Group, 2015,
pp. 525–30, doi:10.1038/nature15395.
short: D. Landau, E. Tausch, A. Taylor Weiner, C. Stewart, J. Reiter, J. Bahlo,
S. Kluth, I. Božić, M. Lawrence, S. Böttcher, S. Carter, K. Cibulskis, D. Mertens,
C. Sougnez, M. Rosenberg, J. Hess, J. Edelmann, S. Kless, M. Kneba, M. Ritgen,
A. Fink, K. Fischer, S. Gabriel, E. Lander, M. Nowak, H. Döhner, M. Hallek, D.
Neuberg, G. Getz, S. Stilgenbauer, C. Wu, Nature 526 (2015) 525–530.
date_created: 2018-12-11T11:53:21Z
date_published: 2015-10-22T00:00:00Z
date_updated: 2021-01-12T06:52:23Z
day: '22'
department:
- _id: KrCh
doi: 10.1038/nature15395
ec_funded: 1
external_id:
pmid:
- '26466571'
intvolume: ' 526'
issue: '7574'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4815041/
month: '10'
oa: 1
oa_version: Submitted Version
page: 525 - 530
pmid: 1
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _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
publication: Nature
publication_status: published
publisher: Nature Publishing Group
publist_id: '5484'
quality_controlled: '1'
scopus_import: 1
status: public
title: Mutations driving CLL and their evolution in progression and relapse
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 526
year: '2015'
...
---
_id: '1666'
abstract:
- lang: eng
text: Evolution of gene regulation is crucial for our understanding of the phenotypic
differences between species, populations and individuals. Sequence-specific binding
of transcription factors to the regulatory regions on the DNA is a key regulatory
mechanism that determines gene expression and hence heritable phenotypic variation.
We use a biophysical model for directional selection on gene expression to estimate
the rates of gain and loss of transcription factor binding sites (TFBS) in finite
populations under both point and insertion/deletion mutations. Our results show
that these rates are typically slow for a single TFBS in an isolated DNA region,
unless the selection is extremely strong. These rates decrease drastically with
increasing TFBS length or increasingly specific protein-DNA interactions, making
the evolution of sites longer than ∼ 10 bp unlikely on typical eukaryotic speciation
timescales. Similarly, evolution converges to the stationary distribution of binding
sequences very slowly, making the equilibrium assumption questionable. The availability
of longer regulatory sequences in which multiple binding sites can evolve simultaneously,
the presence of “pre-sites” or partially decayed old sites in the initial sequence,
and biophysical cooperativity between transcription factors, can all facilitate
gain of TFBS and reconcile theoretical calculations with timescales inferred from
comparative genomics.
author:
- first_name: Murat
full_name: Tugrul, Murat
id: 37C323C6-F248-11E8-B48F-1D18A9856A87
last_name: Tugrul
orcid: 0000-0002-8523-0758
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: Gasper
full_name: Tkacik, Gasper
id: 3D494DCA-F248-11E8-B48F-1D18A9856A87
last_name: Tkacik
orcid: 0000-0002-6699-1455
citation:
ama: Tugrul M, Paixao T, Barton NH, Tkačik G. Dynamics of transcription factor binding
site evolution. PLoS Genetics. 2015;11(11). doi:10.1371/journal.pgen.1005639
apa: Tugrul, M., Paixao, T., Barton, N. H., & Tkačik, G. (2015). Dynamics of
transcription factor binding site evolution. PLoS Genetics. Public Library
of Science. https://doi.org/10.1371/journal.pgen.1005639
chicago: Tugrul, Murat, Tiago Paixao, Nicholas H Barton, and Gašper Tkačik. “Dynamics
of Transcription Factor Binding Site Evolution.” PLoS Genetics. Public
Library of Science, 2015. https://doi.org/10.1371/journal.pgen.1005639.
ieee: M. Tugrul, T. Paixao, N. H. Barton, and G. Tkačik, “Dynamics of transcription
factor binding site evolution,” PLoS Genetics, vol. 11, no. 11. Public
Library of Science, 2015.
ista: Tugrul M, Paixao T, Barton NH, Tkačik G. 2015. Dynamics of transcription factor
binding site evolution. PLoS Genetics. 11(11).
mla: Tugrul, Murat, et al. “Dynamics of Transcription Factor Binding Site Evolution.”
PLoS Genetics, vol. 11, no. 11, Public Library of Science, 2015, doi:10.1371/journal.pgen.1005639.
short: M. Tugrul, T. Paixao, N.H. Barton, G. Tkačik, PLoS Genetics 11 (2015).
date_created: 2018-12-11T11:53:21Z
date_published: 2015-11-06T00:00:00Z
date_updated: 2023-09-07T11:53:49Z
day: '06'
ddc:
- '576'
department:
- _id: NiBa
- _id: CaGu
- _id: GaTk
doi: 10.1371/journal.pgen.1005639
ec_funded: 1
file:
- access_level: open_access
checksum: a4e72fca5ccf40ddacf4d08c8e46b554
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:07:58Z
date_updated: 2020-07-14T12:45:10Z
file_id: '4657'
file_name: IST-2016-463-v1+1_journal.pgen.1005639.pdf
file_size: 2580778
relation: main_file
file_date_updated: 2020-07-14T12:45:10Z
has_accepted_license: '1'
intvolume: ' 11'
issue: '11'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
project:
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
publication: PLoS Genetics
publication_status: published
publisher: Public Library of Science
publist_id: '5483'
pubrep_id: '463'
quality_controlled: '1'
related_material:
record:
- id: '9712'
relation: research_data
status: public
- id: '1131'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Dynamics of transcription factor binding site evolution
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 11
year: '2015'
...
---
_id: '1667'
abstract:
- lang: eng
text: We consider parametric version of fixed-delay continuoustime Markov chains
(or equivalently deterministic and stochastic Petri nets, DSPN) where fixed-delay
transitions are specified by parameters, rather than concrete values. Our goal
is to synthesize values of these parameters that, for a given cost function, minimise
expected total cost incurred before reaching a given set of target states. We
show that under mild assumptions, optimal values of parameters can be effectively
approximated using translation to a Markov decision process (MDP) whose actions
correspond to discretized values of these parameters. To this end we identify
and overcome several interesting phenomena arising in systems with fixed delays.
acknowledgement: The research leading to these results has received funding from the
People Programme (Marie Curie Actions) of the European Union’s Seventh Framework
Programme (FP7/2007-2013) under REA grant agreement n∘ [291734]. This work is partly
supported by the German Research Council (DFG) as part of the Transregional Collaborative
Research Center AVACS (SFB/TR 14), by the EU 7th Framework Programme under grant
agreement no. 295261 (MEALS) and 318490 (SENSATION), by the Czech Science Foundation,
grant No. 15-17564S, and by the CAS/SAFEA International Partnership Program for
Creative Research Teams.
alternative_title:
- LNCS
author:
- first_name: Tomáš
full_name: Brázdil, Tomáš
last_name: Brázdil
- first_name: L'Uboš
full_name: Korenčiak, L'Uboš
last_name: Korenčiak
- first_name: Jan
full_name: Krčál, Jan
last_name: Krčál
- first_name: Petr
full_name: Novotny, Petr
id: 3CC3B868-F248-11E8-B48F-1D18A9856A87
last_name: Novotny
- first_name: Vojtěch
full_name: Řehák, Vojtěch
last_name: Řehák
citation:
ama: Brázdil T, Korenčiak L, Krčál J, Novotný P, Řehák V. Optimizing performance
of continuous-time stochastic systems using timeout synthesis. 2015;9259:141-159.
doi:10.1007/978-3-319-22264-6_10
apa: 'Brázdil, T., Korenčiak, L., Krčál, J., Novotný, P., & Řehák, V. (2015).
Optimizing performance of continuous-time stochastic systems using timeout synthesis.
Presented at the QEST: Quantitative Evaluation of Systems, Madrid, Spain: Springer.
https://doi.org/10.1007/978-3-319-22264-6_10'
chicago: Brázdil, Tomáš, L’Uboš Korenčiak, Jan Krčál, Petr Novotný, and Vojtěch
Řehák. “Optimizing Performance of Continuous-Time Stochastic Systems Using Timeout
Synthesis.” Lecture Notes in Computer Science. Springer, 2015. https://doi.org/10.1007/978-3-319-22264-6_10.
ieee: T. Brázdil, L. Korenčiak, J. Krčál, P. Novotný, and V. Řehák, “Optimizing
performance of continuous-time stochastic systems using timeout synthesis,” vol.
9259. Springer, pp. 141–159, 2015.
ista: Brázdil T, Korenčiak L, Krčál J, Novotný P, Řehák V. 2015. Optimizing performance
of continuous-time stochastic systems using timeout synthesis. 9259, 141–159.
mla: Brázdil, Tomáš, et al. Optimizing Performance of Continuous-Time Stochastic
Systems Using Timeout Synthesis. Vol. 9259, Springer, 2015, pp. 141–59, doi:10.1007/978-3-319-22264-6_10.
short: T. Brázdil, L. Korenčiak, J. Krčál, P. Novotný, V. Řehák, 9259 (2015) 141–159.
conference:
end_date: 2015-09-03
location: Madrid, Spain
name: 'QEST: Quantitative Evaluation of Systems'
start_date: 2015-09-01
date_created: 2018-12-11T11:53:22Z
date_published: 2015-08-22T00:00:00Z
date_updated: 2021-01-12T06:52:24Z
day: '22'
department:
- _id: KrCh
doi: 10.1007/978-3-319-22264-6_10
ec_funded: 1
intvolume: ' 9259'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1407.4777
month: '08'
oa: 1
oa_version: Preprint
page: 141 - 159
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: Springer
publist_id: '5482'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Optimizing performance of continuous-time stochastic systems using timeout
synthesis
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9259
year: '2015'
...
---
_id: '1668'
abstract:
- lang: eng
text: "We revisit the security (as a pseudorandom permutation) of cascading-based
constructions for block-cipher key-length extension. Previous works typically
considered the extreme case where the adversary is given the entire codebook of
the construction, the only complexity measure being the number qe of queries to
the underlying ideal block cipher, representing adversary’s secret-key-independent
computation. Here, we initiate a systematic study of the more natural case of
an adversary restricted to adaptively learning a number qc of plaintext/ciphertext
pairs that is less than the entire codebook. For any such qc, we aim to determine
the highest number of block-cipher queries qe the adversary can issue without
being able to successfully distinguish the construction (under a secret key) from
a random permutation.\r\nMore concretely, we show the following results for key-length
extension schemes using a block cipher with n-bit blocks and κ-bit keys:\r\nPlain
cascades of length ℓ=2r+1 are secure whenever qcqre≪2r(κ+n), qc≪2κ and qe≪22κ.
The bound for r=1 also applies to two-key triple encryption (as used within Triple
DES).\r\nThe r-round XOR-cascade is secure as long as qcqre≪2r(κ+n), matching
an attack by Gaži (CRYPTO 2013).\r\nWe fully characterize the security of Gaži
and Tessaro’s two-call "
alternative_title:
- LNCS
author:
- first_name: Peter
full_name: Gazi, Peter
id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
last_name: Gazi
- first_name: Jooyoung
full_name: Lee, Jooyoung
last_name: Lee
- first_name: Yannick
full_name: Seurin, Yannick
last_name: Seurin
- first_name: John
full_name: Steinberger, John
last_name: Steinberger
- first_name: Stefano
full_name: Tessaro, Stefano
last_name: Tessaro
citation:
ama: 'Gazi P, Lee J, Seurin Y, Steinberger J, Tessaro S. Relaxing full-codebook
security: A refined analysis of key-length extension schemes. 2015;9054:319-341.
doi:10.1007/978-3-662-48116-5_16'
apa: 'Gazi, P., Lee, J., Seurin, Y., Steinberger, J., & Tessaro, S. (2015).
Relaxing full-codebook security: A refined analysis of key-length extension schemes.
Presented at the FSE: Fast Software Encryption, Istanbul, Turkey: Springer. https://doi.org/10.1007/978-3-662-48116-5_16'
chicago: 'Gazi, Peter, Jooyoung Lee, Yannick Seurin, John Steinberger, and Stefano
Tessaro. “Relaxing Full-Codebook Security: A Refined Analysis of Key-Length Extension
Schemes.” Lecture Notes in Computer Science. Springer, 2015. https://doi.org/10.1007/978-3-662-48116-5_16.'
ieee: 'P. Gazi, J. Lee, Y. Seurin, J. Steinberger, and S. Tessaro, “Relaxing full-codebook
security: A refined analysis of key-length extension schemes,” vol. 9054. Springer,
pp. 319–341, 2015.'
ista: 'Gazi P, Lee J, Seurin Y, Steinberger J, Tessaro S. 2015. Relaxing full-codebook
security: A refined analysis of key-length extension schemes. 9054, 319–341.'
mla: 'Gazi, Peter, et al. Relaxing Full-Codebook Security: A Refined Analysis
of Key-Length Extension Schemes. Vol. 9054, Springer, 2015, pp. 319–41, doi:10.1007/978-3-662-48116-5_16.'
short: P. Gazi, J. Lee, Y. Seurin, J. Steinberger, S. Tessaro, 9054 (2015) 319–341.
conference:
end_date: 2015-03-11
location: Istanbul, Turkey
name: 'FSE: Fast Software Encryption'
start_date: 2015-03-08
date_created: 2018-12-11T11:53:22Z
date_published: 2015-08-12T00:00:00Z
date_updated: 2020-08-11T10:09:26Z
day: '12'
department:
- _id: KrPi
doi: 10.1007/978-3-662-48116-5_16
ec_funded: 1
intvolume: ' 9054'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://eprint.iacr.org/2015/397
month: '08'
oa: 1
oa_version: Submitted Version
page: 319 - 341
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '5481'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: 'Relaxing full-codebook security: A refined analysis of key-length extension
schemes'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9054
year: '2015'
...
---
_id: '1669'
abstract:
- lang: eng
text: Computational notions of entropy (a.k.a. pseudoentropy) have found many applications,
including leakage-resilient cryptography, deterministic encryption or memory delegation.
The most important tools to argue about pseudoentropy are chain rules, which quantify
by how much (in terms of quantity and quality) the pseudoentropy of a given random
variable X decreases when conditioned on some other variable Z (think for example
of X as a secret key and Z as information leaked by a side-channel). In this paper
we give a very simple and modular proof of the chain rule for HILL pseudoentropy,
improving best known parameters. Our version allows for increasing the acceptable
length of leakage in applications up to a constant factor compared to the best
previous bounds. As a contribution of independent interest, we provide a comprehensive
study of all known versions of the chain rule, comparing their worst-case strength
and limitations.
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
- first_name: Maciej
full_name: Skórski, Maciej
last_name: Skórski
citation:
ama: Pietrzak KZ, Skórski M. The chain rule for HILL pseudoentropy, revisited. 2015;9230:81-98.
doi:10.1007/978-3-319-22174-8_5
apa: 'Pietrzak, K. Z., & Skórski, M. (2015). The chain rule for HILL pseudoentropy,
revisited. Presented at the LATINCRYPT: Cryptology and Information Security in
Latin America, Guadalajara, Mexico: Springer. https://doi.org/10.1007/978-3-319-22174-8_5'
chicago: Pietrzak, Krzysztof Z, and Maciej Skórski. “The Chain Rule for HILL Pseudoentropy,
Revisited.” Lecture Notes in Computer Science. Springer, 2015. https://doi.org/10.1007/978-3-319-22174-8_5.
ieee: K. Z. Pietrzak and M. Skórski, “The chain rule for HILL pseudoentropy, revisited,”
vol. 9230. Springer, pp. 81–98, 2015.
ista: Pietrzak KZ, Skórski M. 2015. The chain rule for HILL pseudoentropy, revisited.
9230, 81–98.
mla: Pietrzak, Krzysztof Z., and Maciej Skórski. The Chain Rule for HILL Pseudoentropy,
Revisited. Vol. 9230, Springer, 2015, pp. 81–98, doi:10.1007/978-3-319-22174-8_5.
short: K.Z. Pietrzak, M. Skórski, 9230 (2015) 81–98.
conference:
end_date: 2015-08-26
location: Guadalajara, Mexico
name: 'LATINCRYPT: Cryptology and Information Security in Latin America'
start_date: 2015-08-23
date_created: 2018-12-11T11:53:22Z
date_published: 2015-08-15T00:00:00Z
date_updated: 2021-01-12T06:52:24Z
day: '15'
ddc:
- '005'
department:
- _id: KrPi
doi: 10.1007/978-3-319-22174-8_5
ec_funded: 1
file:
- access_level: open_access
checksum: 8cd4215b83efba720e8cf27c23ff4781
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:18:29Z
date_updated: 2020-07-14T12:45:11Z
file_id: '5351'
file_name: IST-2016-669-v1+1_599.pdf
file_size: 443340
relation: main_file
file_date_updated: 2020-07-14T12:45:11Z
has_accepted_license: '1'
intvolume: ' 9230'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 81 - 98
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '5480'
pubrep_id: '669'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: The chain rule for HILL pseudoentropy, revisited
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9230
year: '2015'
...
---
_id: '1670'
abstract:
- lang: eng
text: Planning in hybrid domains poses a special challenge due to the involved mixed
discrete-continuous dynamics. A recent solving approach for such domains is based
on applying model checking techniques on a translation of PDDL+ planning problems
to hybrid automata. However, the proposed translation is limited because must
behavior is only overapproximated, and hence, processes and events are not reflected
exactly. In this paper, we present the theoretical foundation of an exact PDDL+
translation. We propose a schema to convert a hybrid automaton with must transitions
into an equivalent hybrid automaton featuring only may transitions.
acknowledgement: This work was partly supported by the German Research Foundation
(DFG) as part of the Transregional Collaborative Research Center “Automatic Verification
and Analysis of Complex Systems” (SFB/TR 14 AVACS, http://www.avacs.org/), by the
European Research Council (ERC) under grant 267989 (QUAREM), by the Austrian Science
Fund (FWF) under grants S11402-N23 (RiSE) and Z211-N23 (Wittgenstein Award), and
by the Swiss National Science Foundation (SNSF) as part of the project “Automated
Reformulation and Pruning in Factored State Spaces (ARAP)”.
author:
- first_name: Sergiy
full_name: Bogomolov, Sergiy
id: 369D9A44-F248-11E8-B48F-1D18A9856A87
last_name: Bogomolov
orcid: 0000-0002-0686-0365
- first_name: Daniele
full_name: Magazzeni, Daniele
last_name: Magazzeni
- first_name: Stefano
full_name: Minopoli, Stefano
last_name: Minopoli
- first_name: Martin
full_name: Wehrle, Martin
last_name: Wehrle
citation:
ama: 'Bogomolov S, Magazzeni D, Minopoli S, Wehrle M. PDDL+ planning with hybrid
automata: Foundations of translating must behavior. In: AAAI Press; 2015:42-46.'
apa: 'Bogomolov, S., Magazzeni, D., Minopoli, S., & Wehrle, M. (2015). PDDL+
planning with hybrid automata: Foundations of translating must behavior (pp. 42–46).
Presented at the ICAPS: International Conference on Automated Planning and Scheduling,
Jerusalem, Israel: AAAI Press.'
chicago: 'Bogomolov, Sergiy, Daniele Magazzeni, Stefano Minopoli, and Martin Wehrle.
“PDDL+ Planning with Hybrid Automata: Foundations of Translating Must Behavior,”
42–46. AAAI Press, 2015.'
ieee: 'S. Bogomolov, D. Magazzeni, S. Minopoli, and M. Wehrle, “PDDL+ planning with
hybrid automata: Foundations of translating must behavior,” presented at the ICAPS:
International Conference on Automated Planning and Scheduling, Jerusalem, Israel,
2015, pp. 42–46.'
ista: 'Bogomolov S, Magazzeni D, Minopoli S, Wehrle M. 2015. PDDL+ planning with
hybrid automata: Foundations of translating must behavior. ICAPS: International
Conference on Automated Planning and Scheduling, 42–46.'
mla: 'Bogomolov, Sergiy, et al. PDDL+ Planning with Hybrid Automata: Foundations
of Translating Must Behavior. AAAI Press, 2015, pp. 42–46.'
short: S. Bogomolov, D. Magazzeni, S. Minopoli, M. Wehrle, in:, AAAI Press, 2015,
pp. 42–46.
conference:
end_date: 2015-06-11
location: Jerusalem, Israel
name: 'ICAPS: International Conference on Automated Planning and Scheduling'
start_date: 2015-06-07
date_created: 2018-12-11T11:53:23Z
date_published: 2015-06-01T00:00:00Z
date_updated: 2021-01-12T06:52:25Z
day: '01'
department:
- _id: ToHe
ec_funded: 1
language:
- iso: eng
main_file_link:
- url: https://www.aaai.org/ocs/index.php/ICAPS/ICAPS15/paper/view/10606/10394
month: '06'
oa_version: None
page: 42 - 46
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication_status: published
publisher: AAAI Press
publist_id: '5479'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'PDDL+ planning with hybrid automata: Foundations of translating must behavior'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '1671'
abstract:
- lang: eng
text: This paper studies the concrete security of PRFs and MACs obtained by keying
hash functions based on the sponge paradigm. One such hash function is KECCAK,
selected as NIST’s new SHA-3 standard. In contrast to other approaches like HMAC,
the exact security of keyed sponges is not well understood. Indeed, recent security
analyses delivered concrete security bounds which are far from existing attacks.
This paper aims to close this gap. We prove (nearly) exact bounds on the concrete
PRF security of keyed sponges using a random permutation. These bounds are tight
for the most relevant ranges of parameters, i.e., for messages of length (roughly)
l ≤ min{2n/4, 2r} blocks, where n is the state size and r is the desired output
length; and for l ≤ q queries (to the construction or the underlying permutation).
Moreover, we also improve standard-model bounds. As an intermediate step of independent
interest, we prove tight bounds on the PRF security of the truncated CBC-MAC construction,
which operates as plain CBC-MAC, but only returns a prefix of the output.
alternative_title:
- LNCS
author:
- first_name: Peter
full_name: Gazi, Peter
id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
last_name: Gazi
- 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: Stefano
full_name: Tessaro, Stefano
last_name: Tessaro
citation:
ama: 'Gazi P, Pietrzak KZ, Tessaro S. The exact PRF security of truncation: Tight
bounds for keyed sponges and truncated CBC. In: Vol 9215. Springer; 2015:368-387.
doi:10.1007/978-3-662-47989-6_18'
apa: 'Gazi, P., Pietrzak, K. Z., & Tessaro, S. (2015). The exact PRF security
of truncation: Tight bounds for keyed sponges and truncated CBC (Vol. 9215, pp.
368–387). Presented at the CRYPTO: International Cryptology Conference, Santa
Barbara, CA, United States: Springer. https://doi.org/10.1007/978-3-662-47989-6_18'
chicago: 'Gazi, Peter, Krzysztof Z Pietrzak, and Stefano Tessaro. “The Exact PRF
Security of Truncation: Tight Bounds for Keyed Sponges and Truncated CBC,” 9215:368–87.
Springer, 2015. https://doi.org/10.1007/978-3-662-47989-6_18.'
ieee: 'P. Gazi, K. Z. Pietrzak, and S. Tessaro, “The exact PRF security of truncation:
Tight bounds for keyed sponges and truncated CBC,” presented at the CRYPTO: International
Cryptology Conference, Santa Barbara, CA, United States, 2015, vol. 9215, pp.
368–387.'
ista: 'Gazi P, Pietrzak KZ, Tessaro S. 2015. The exact PRF security of truncation:
Tight bounds for keyed sponges and truncated CBC. CRYPTO: International Cryptology
Conference, LNCS, vol. 9215, 368–387.'
mla: 'Gazi, Peter, et al. The Exact PRF Security of Truncation: Tight Bounds
for Keyed Sponges and Truncated CBC. Vol. 9215, Springer, 2015, pp. 368–87,
doi:10.1007/978-3-662-47989-6_18.'
short: P. Gazi, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2015, pp. 368–387.
conference:
end_date: 2015-08-20
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2015-08-16
date_created: 2018-12-11T11:53:23Z
date_published: 2015-08-01T00:00:00Z
date_updated: 2021-01-12T06:52:25Z
day: '01'
ddc:
- '004'
- '005'
department:
- _id: KrPi
doi: 10.1007/978-3-662-47989-6_18
ec_funded: 1
file:
- access_level: open_access
checksum: 17d854227b3b753fd34f5d29e5b5a32e
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:38Z
date_updated: 2020-07-14T12:45:11Z
file_id: '4827'
file_name: IST-2016-673-v1+1_053.pdf
file_size: 592296
relation: main_file
file_date_updated: 2020-07-14T12:45:11Z
has_accepted_license: '1'
intvolume: ' 9215'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 368 - 387
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '5478'
pubrep_id: '673'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'The exact PRF security of truncation: Tight bounds for keyed sponges and truncated
CBC'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9215
year: '2015'
...
---
_id: '1672'
abstract:
- lang: eng
text: Composable notions of incoercibility aim to forbid a coercer from using anything
beyond the coerced parties’ inputs and outputs to catch them when they try to
deceive him. Existing definitions are restricted to weak coercion types, and/or
are not universally composable. Furthermore, they often make too strong assumptions
on the knowledge of coerced parties—e.g., they assume they known the identities
and/or the strategies of other coerced parties, or those of corrupted parties—
which makes them unsuitable for applications of incoercibility such as e-voting,
where colluding adversarial parties may attempt to coerce honest voters, e.g.,
by offering them money for a promised vote, and use their own view to check that
the voter keeps his end of the bargain. In this work we put forward the first
universally composable notion of incoercible multi-party computation, which satisfies
the above intuition and does not assume collusions among coerced parties or knowledge
of the corrupted set. We define natural notions of UC incoercibility corresponding
to standard coercion-types, i.e., receipt-freeness and resistance to full-active
coercion. Importantly, our suggested notion has the unique property that it builds
on top of the well studied UC framework by Canetti instead of modifying it. This
guarantees backwards compatibility, and allows us to inherit results from the
rich UC literature. We then present MPC protocols which realize our notions of
UC incoercibility given access to an arguably minimal setup—namely honestly generate
tamper-proof hardware performing a very simple cryptographic operation—e.g., a
smart card. This is, to our knowledge, the first proposed construction of an MPC
protocol (for more than two parties) that is incoercibly secure and universally
composable, and therefore the first construction of a universally composable receipt-free
e-voting protocol.
acknowledgement: Joël Alwen was supported by the ERC starting grant (259668-PSPC).
Rafail Ostrovsky was supported in part by NSF grants 09165174, 1065276, 1118126
and 1136174, US-Israel BSF grant 2008411, OKAWA Foundation Research Award, IBM Faculty
Research Award, Xerox Faculty Research Award, B. John Garrick Foundation Award,
Teradata Research Award, Lockheed-Martin Corporation Research Award, and the Defense
Advanced Research Projects Agency through the U.S. Office of Naval Research under
Contract N00014 -11 -1-0392. The views expressed are those of the author and do
not reflect the official policy or position of the Department of Defense or the
U.S. Government. Vassilis Zikas was supported in part by the Swiss National Science
Foundation (SNF) via the Ambizione grant PZ00P-2142549.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Rafail
full_name: Ostrovsky, Rafail
last_name: Ostrovsky
- first_name: Hongsheng
full_name: Zhou, Hongsheng
last_name: Zhou
- first_name: Vassilis
full_name: Zikas, Vassilis
last_name: Zikas
citation:
ama: 'Alwen JF, Ostrovsky R, Zhou H, Zikas V. Incoercible multi-party computation
and universally composable receipt-free voting. In: Advances in Cryptology
- CRYPTO 2015. Vol 9216. Lecture Notes in Computer Science. Springer; 2015:763-780.
doi:10.1007/978-3-662-48000-7_37'
apa: 'Alwen, J. F., Ostrovsky, R., Zhou, H., & Zikas, V. (2015). Incoercible
multi-party computation and universally composable receipt-free voting. In Advances
in Cryptology - CRYPTO 2015 (Vol. 9216, pp. 763–780). Santa Barbara, CA, United
States: Springer. https://doi.org/10.1007/978-3-662-48000-7_37'
chicago: Alwen, Joel F, Rafail Ostrovsky, Hongsheng Zhou, and Vassilis Zikas. “Incoercible
Multi-Party Computation and Universally Composable Receipt-Free Voting.” In Advances
in Cryptology - CRYPTO 2015, 9216:763–80. Lecture Notes in Computer Science.
Springer, 2015. https://doi.org/10.1007/978-3-662-48000-7_37.
ieee: J. F. Alwen, R. Ostrovsky, H. Zhou, and V. Zikas, “Incoercible multi-party
computation and universally composable receipt-free voting,” in Advances in
Cryptology - CRYPTO 2015, Santa Barbara, CA, United States, 2015, vol. 9216,
pp. 763–780.
ista: 'Alwen JF, Ostrovsky R, Zhou H, Zikas V. 2015. Incoercible multi-party computation
and universally composable receipt-free voting. Advances in Cryptology - CRYPTO
2015. CRYPTO: International Cryptology ConferenceLecture Notes in Computer Science,
LNCS, vol. 9216, 763–780.'
mla: Alwen, Joel F., et al. “Incoercible Multi-Party Computation and Universally
Composable Receipt-Free Voting.” Advances in Cryptology - CRYPTO 2015,
vol. 9216, Springer, 2015, pp. 763–80, doi:10.1007/978-3-662-48000-7_37.
short: J.F. Alwen, R. Ostrovsky, H. Zhou, V. Zikas, in:, Advances in Cryptology
- CRYPTO 2015, Springer, 2015, pp. 763–780.
conference:
end_date: 2015-08-20
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2015-08-16
date_created: 2018-12-11T11:53:23Z
date_published: 2015-08-01T00:00:00Z
date_updated: 2022-06-07T09:51:55Z
day: '01'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.1007/978-3-662-48000-7_37
ec_funded: 1
file:
- access_level: open_access
checksum: 5b6649e80d1f781a8910f7cce6427f78
content_type: application/pdf
creator: dernst
date_created: 2020-05-15T08:55:29Z
date_updated: 2020-07-14T12:45:11Z
file_id: '7853'
file_name: 2015_CRYPTO_Alwen.pdf
file_size: 397363
relation: main_file
file_date_updated: 2020-07-14T12:45:11Z
has_accepted_license: '1'
intvolume: ' 9216'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 763 - 780
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: Advances in Cryptology - CRYPTO 2015
publication_identifier:
eisbn:
- 978-3-662-48000-7
isbn:
- 978-3-662-47999-5
publication_status: published
publisher: Springer
publist_id: '5476'
quality_controlled: '1'
scopus_import: '1'
series_title: Lecture Notes in Computer Science
status: public
title: Incoercible multi-party computation and universally composable receipt-free
voting
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9216
year: '2015'
...
---
_id: '1673'
abstract:
- lang: eng
text: 'When a new mutant arises in a population, there is a probability it outcompetes
the residents and fixes. The structure of the population can affect this fixation
probability. Suppressing population structures reduce the difference between two
competing variants, while amplifying population structures enhance the difference.
Suppressors are ubiquitous and easy to construct, but amplifiers for the large
population limit are more elusive and only a few examples have been discovered.
Whether or not a population structure is an amplifier of selection depends on
the probability distribution for the placement of the invading mutant. First,
we prove that there exist only bounded amplifiers for adversarial placement-that
is, for arbitrary initial conditions. Next, we show that the Star population structure,
which is known to amplify for mutants placed uniformly at random, does not amplify
for mutants that arise through reproduction and are therefore placed proportional
to the temperatures of the vertices. Finally, we construct population structures
that amplify for all mutational events that arise through reproduction, uniformly
at random, or through some combination of the two. '
acknowledgement: 'K.C. gratefully acknowledges support from ERC Start grant no. (279307:
Graph Games), Austrian Science Fund (FWF) grant no. P23499-N23, and FWF NFN grant
no. S11407-N23 (RiSE). '
article_number: '20150114'
author:
- first_name: Ben
full_name: Adlam, Ben
last_name: Adlam
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: 'Adlam B, Chatterjee K, Nowak M. Amplifiers of selection. Proceedings of
the Royal Society A: Mathematical, Physical and Engineering Sciences. 2015;471(2181).
doi:10.1098/rspa.2015.0114'
apa: 'Adlam, B., Chatterjee, K., & Nowak, M. (2015). Amplifiers of selection.
Proceedings of the Royal Society A: Mathematical, Physical and Engineering
Sciences. Royal Society of London. https://doi.org/10.1098/rspa.2015.0114'
chicago: 'Adlam, Ben, Krishnendu Chatterjee, and Martin Nowak. “Amplifiers of Selection.”
Proceedings of the Royal Society A: Mathematical, Physical and Engineering
Sciences. Royal Society of London, 2015. https://doi.org/10.1098/rspa.2015.0114.'
ieee: 'B. Adlam, K. Chatterjee, and M. Nowak, “Amplifiers of selection,” Proceedings
of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol.
471, no. 2181. Royal Society of London, 2015.'
ista: 'Adlam B, Chatterjee K, Nowak M. 2015. Amplifiers of selection. Proceedings
of the Royal Society A: Mathematical, Physical and Engineering Sciences. 471(2181),
20150114.'
mla: 'Adlam, Ben, et al. “Amplifiers of Selection.” Proceedings of the Royal
Society A: Mathematical, Physical and Engineering Sciences, vol. 471, no.
2181, 20150114, Royal Society of London, 2015, doi:10.1098/rspa.2015.0114.'
short: 'B. Adlam, K. Chatterjee, M. Nowak, Proceedings of the Royal Society A: Mathematical,
Physical and Engineering Sciences 471 (2015).'
date_created: 2018-12-11T11:53:24Z
date_published: 2015-09-08T00:00:00Z
date_updated: 2021-01-12T06:52:26Z
day: '08'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1098/rspa.2015.0114
ec_funded: 1
file:
- access_level: open_access
checksum: e613d94d283c776322403a28aad11bdd
content_type: application/pdf
creator: kschuh
date_created: 2019-04-18T12:39:56Z
date_updated: 2020-07-14T12:45:11Z
file_id: '6342'
file_name: 2015_rspa_Adlam.pdf
file_size: 391466
relation: main_file
file_date_updated: 2020-07-14T12:45:11Z
has_accepted_license: '1'
intvolume: ' 471'
issue: '2181'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _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
publication: 'Proceedings of the Royal Society A: Mathematical, Physical and Engineering
Sciences'
publication_status: published
publisher: Royal Society of London
publist_id: '5477'
quality_controlled: '1'
scopus_import: 1
status: public
title: Amplifiers of selection
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 471
year: '2015'
...
---
_id: '1674'
abstract:
- lang: eng
text: We consider N × N random matrices of the form H = W + V where W is a real
symmetric Wigner matrix and V a random or deterministic, real, diagonal matrix
whose entries are independent of W. We assume subexponential decay for the matrix
entries of W and we choose V so that the eigenvalues of W and V are typically
of the same order. For a large class of diagonal matrices V, we show that the
rescaled distribution of the extremal eigenvalues is given by the Tracy-Widom
distribution F1 in the limit of large N. Our proofs also apply to the complex
Hermitian setting, i.e. when W is a complex Hermitian Wigner matrix.
article_number: '1550018'
author:
- first_name: Jioon
full_name: Lee, Jioon
last_name: Lee
- first_name: Kevin
full_name: Schnelli, Kevin
id: 434AD0AE-F248-11E8-B48F-1D18A9856A87
last_name: Schnelli
orcid: 0000-0003-0954-3231
citation:
ama: Lee J, Schnelli K. Edge universality for deformed Wigner matrices. Reviews
in Mathematical Physics. 2015;27(8). doi:10.1142/S0129055X1550018X
apa: Lee, J., & Schnelli, K. (2015). Edge universality for deformed Wigner matrices.
Reviews in Mathematical Physics. World Scientific Publishing. https://doi.org/10.1142/S0129055X1550018X
chicago: Lee, Jioon, and Kevin Schnelli. “Edge Universality for Deformed Wigner
Matrices.” Reviews in Mathematical Physics. World Scientific Publishing,
2015. https://doi.org/10.1142/S0129055X1550018X.
ieee: J. Lee and K. Schnelli, “Edge universality for deformed Wigner matrices,”
Reviews in Mathematical Physics, vol. 27, no. 8. World Scientific Publishing,
2015.
ista: Lee J, Schnelli K. 2015. Edge universality for deformed Wigner matrices. Reviews
in Mathematical Physics. 27(8), 1550018.
mla: Lee, Jioon, and Kevin Schnelli. “Edge Universality for Deformed Wigner Matrices.”
Reviews in Mathematical Physics, vol. 27, no. 8, 1550018, World Scientific
Publishing, 2015, doi:10.1142/S0129055X1550018X.
short: J. Lee, K. Schnelli, Reviews in Mathematical Physics 27 (2015).
date_created: 2018-12-11T11:53:24Z
date_published: 2015-09-01T00:00:00Z
date_updated: 2021-01-12T06:52:26Z
day: '01'
department:
- _id: LaEr
doi: 10.1142/S0129055X1550018X
intvolume: ' 27'
issue: '8'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1407.8015
month: '09'
oa: 1
oa_version: Preprint
publication: Reviews in Mathematical Physics
publication_status: published
publisher: World Scientific Publishing
publist_id: '5475'
quality_controlled: '1'
scopus_import: 1
status: public
title: Edge universality for deformed Wigner matrices
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 27
year: '2015'
...
---
_id: '1675'
abstract:
- lang: eng
text: Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto’92) as
protection to a shared resource. The basic idea is to ask the service requestor
to dedicate some non-trivial amount of computational work to every request. The
original applications included prevention of spam and protection against denial
of service attacks. More recently, PoWs have been used to prevent double spending
in the Bitcoin digital currency system. In this work, we put forward an alternative
concept for PoWs - so-called proofs of space (PoS), where a service requestor
must dedicate a significant amount of disk space as opposed to computation. We
construct secure PoS schemes in the random oracle model (with one additional mild
assumption required for the proof to go through), using graphs with high “pebbling
complexity” and Merkle hash-trees. We discuss some applications, including follow-up
work where a decentralized digital currency scheme called Spacecoin is constructed
that uses PoS (instead of wasteful PoW like in Bitcoin) to prevent double spending.
The main technical contribution of this work is the construction of (directed,
loop-free) graphs on N vertices with in-degree O(log logN) such that even if one
places Θ(N) pebbles on the nodes of the graph, there’s a constant fraction of
nodes that needs Θ(N) steps to be pebbled (where in every step one can put a pebble
on a node if all its parents have a pebble).
alternative_title:
- LNCS
author:
- first_name: Stefan
full_name: Dziembowski, Stefan
last_name: Dziembowski
- first_name: Sebastian
full_name: Faust, Sebastian
last_name: Faust
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- 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: Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. Proofs of space. 2015;9216:585-605.
doi:10.1007/978-3-662-48000-7_29
apa: 'Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. Z. (2015).
Proofs of space. Presented at the CRYPTO: International Cryptology Conference,
Santa Barbara, CA, United States: Springer. https://doi.org/10.1007/978-3-662-48000-7_29'
chicago: Dziembowski, Stefan, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof
Z Pietrzak. “Proofs of Space.” Lecture Notes in Computer Science. Springer, 2015.
https://doi.org/10.1007/978-3-662-48000-7_29.
ieee: S. Dziembowski, S. Faust, V. Kolmogorov, and K. Z. Pietrzak, “Proofs of space,”
vol. 9216. Springer, pp. 585–605, 2015.
ista: Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2015. Proofs of space.
9216, 585–605.
mla: Dziembowski, Stefan, et al. Proofs of Space. Vol. 9216, Springer, 2015,
pp. 585–605, doi:10.1007/978-3-662-48000-7_29.
short: S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, 9216 (2015) 585–605.
conference:
end_date: 2015-08-20
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2015-08-16
date_created: 2018-12-11T11:53:24Z
date_published: 2015-08-01T00:00:00Z
date_updated: 2023-02-23T10:35:50Z
day: '01'
department:
- _id: VlKo
- _id: KrPi
doi: 10.1007/978-3-662-48000-7_29
ec_funded: 1
intvolume: ' 9216'
language:
- iso: eng
month: '08'
oa_version: None
page: 585 - 605
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '5474'
pubrep_id: '671'
quality_controlled: '1'
related_material:
record:
- id: '2274'
relation: earlier_version
status: public
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Proofs of space
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9216
year: '2015'
...
---
_id: '1676'
author:
- first_name: Michael K
full_name: Sixt, Michael K
id: 41E9FBEA-F248-11E8-B48F-1D18A9856A87
last_name: Sixt
orcid: 0000-0002-6620-9179
- first_name: Erez
full_name: Raz, Erez
last_name: Raz
citation:
ama: 'Sixt MK, Raz E. Editorial overview: Cell adhesion and migration. Current
Opinion in Cell Biology. 2015;36(10):4-6. doi:10.1016/j.ceb.2015.09.004'
apa: 'Sixt, M. K., & Raz, E. (2015). Editorial overview: Cell adhesion and migration.
Current Opinion in Cell Biology. Elsevier. https://doi.org/10.1016/j.ceb.2015.09.004'
chicago: 'Sixt, Michael K, and Erez Raz. “Editorial Overview: Cell Adhesion and
Migration.” Current Opinion in Cell Biology. Elsevier, 2015. https://doi.org/10.1016/j.ceb.2015.09.004.'
ieee: 'M. K. Sixt and E. Raz, “Editorial overview: Cell adhesion and migration,”
Current Opinion in Cell Biology, vol. 36, no. 10. Elsevier, pp. 4–6, 2015.'
ista: 'Sixt MK, Raz E. 2015. Editorial overview: Cell adhesion and migration. Current
Opinion in Cell Biology. 36(10), 4–6.'
mla: 'Sixt, Michael K., and Erez Raz. “Editorial Overview: Cell Adhesion and Migration.”
Current Opinion in Cell Biology, vol. 36, no. 10, Elsevier, 2015, pp. 4–6,
doi:10.1016/j.ceb.2015.09.004.'
short: M.K. Sixt, E. Raz, Current Opinion in Cell Biology 36 (2015) 4–6.
date_created: 2018-12-11T11:53:25Z
date_published: 2015-10-01T00:00:00Z
date_updated: 2021-01-12T06:52:27Z
day: '01'
department:
- _id: MiSi
doi: 10.1016/j.ceb.2015.09.004
intvolume: ' 36'
issue: '10'
language:
- iso: eng
month: '10'
oa_version: None
page: 4 - 6
publication: Current Opinion in Cell Biology
publication_status: published
publisher: Elsevier
publist_id: '5473'
scopus_import: 1
status: public
title: 'Editorial overview: Cell adhesion and migration'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2015'
...
---
_id: '1677'
abstract:
- lang: eng
text: We consider real symmetric and complex Hermitian random matrices with the
additional symmetry hxy = hN-y,N-x. The matrix elements are independent (up to
the fourfold symmetry) and not necessarily identically distributed. This ensemble
naturally arises as the Fourier transform of a Gaussian orthogonal ensemble. Italso
occurs as the flip matrix model - an approximation of the two-dimensional Anderson
model at small disorder. We show that the density of states converges to the Wigner
semicircle law despite the new symmetry type. We also prove the local version
of the semicircle law on the optimal scale.
article_number: '103301'
author:
- first_name: Johannes
full_name: Alt, Johannes
id: 36D3D8B6-F248-11E8-B48F-1D18A9856A87
last_name: Alt
citation:
ama: Alt J. The local semicircle law for random matrices with a fourfold symmetry.
Journal of Mathematical Physics. 2015;56(10). doi:10.1063/1.4932606
apa: Alt, J. (2015). The local semicircle law for random matrices with a fourfold
symmetry. Journal of Mathematical Physics. American Institute of Physics.
https://doi.org/10.1063/1.4932606
chicago: Alt, Johannes. “The Local Semicircle Law for Random Matrices with a Fourfold
Symmetry.” Journal of Mathematical Physics. American Institute of Physics,
2015. https://doi.org/10.1063/1.4932606.
ieee: J. Alt, “The local semicircle law for random matrices with a fourfold symmetry,”
Journal of Mathematical Physics, vol. 56, no. 10. American Institute of
Physics, 2015.
ista: Alt J. 2015. The local semicircle law for random matrices with a fourfold
symmetry. Journal of Mathematical Physics. 56(10), 103301.
mla: Alt, Johannes. “The Local Semicircle Law for Random Matrices with a Fourfold
Symmetry.” Journal of Mathematical Physics, vol. 56, no. 10, 103301, American
Institute of Physics, 2015, doi:10.1063/1.4932606.
short: J. Alt, Journal of Mathematical Physics 56 (2015).
date_created: 2018-12-11T11:53:25Z
date_published: 2015-10-09T00:00:00Z
date_updated: 2023-09-07T12:38:08Z
day: '09'
department:
- _id: LaEr
doi: 10.1063/1.4932606
ec_funded: 1
intvolume: ' 56'
issue: '10'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1506.04683
month: '10'
oa: 1
oa_version: Preprint
project:
- _id: 258DCDE6-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '338804'
name: Random matrices, universality and disordered quantum systems
publication: Journal of Mathematical Physics
publication_status: published
publisher: American Institute of Physics
publist_id: '5472'
quality_controlled: '1'
related_material:
record:
- id: '149'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: The local semicircle law for random matrices with a fourfold symmetry
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 56
year: '2015'
...
---
_id: '1678'
abstract:
- lang: eng
text: High-throughput live-cell screens are intricate elements of systems biology
studies and drug discovery pipelines. Here, we demonstrate an optogenetics-assisted
method that avoids the need for chemical activators and reporters, reduces the
number of operational steps and increases information content in a cell-based
small-molecule screen against human protein kinases, including an orphan receptor
tyrosine kinase. This blueprint for all-optical screening can be adapted to many
drug targets and cellular processes.
acknowledgement: 'This work was supported by grants from the European Union Seventh
Framework Programme (CIG-303564 to H.J. and ERC-StG-311166 to S.M.B.N.), the Human
Frontier Science Program (RGY0084_2012 to H.J.) and the Herzfelder Foundation (to
M.G.). A.I.-P. was supported by a Ramon Areces fellowship, and E.R. by the graduate
program MolecularDrugTargets (Austrian Science Fund (FWF): W 1232) and a FemTech
fellowship (3580812 Austrian Research Promotion Agency).'
author:
- first_name: Álvaro
full_name: Inglés Prieto, Álvaro
id: 2A9DB292-F248-11E8-B48F-1D18A9856A87
last_name: Inglés Prieto
orcid: 0000-0002-5409-8571
- first_name: Eva
full_name: Gschaider-Reichhart, Eva
id: 3FEE232A-F248-11E8-B48F-1D18A9856A87
last_name: Gschaider-Reichhart
orcid: 0000-0002-7218-7738
- first_name: Markus
full_name: Muellner, Markus
last_name: Muellner
- first_name: Matthias
full_name: Nowak, Matthias
id: 30845DAA-F248-11E8-B48F-1D18A9856A87
last_name: Nowak
- first_name: Sebastian
full_name: Nijman, Sebastian
last_name: Nijman
- first_name: Michael
full_name: Grusch, Michael
last_name: Grusch
- first_name: Harald L
full_name: Janovjak, Harald L
id: 33BA6C30-F248-11E8-B48F-1D18A9856A87
last_name: Janovjak
orcid: 0000-0002-8023-9315
citation:
ama: Inglés Prieto Á, Gschaider-Reichhart E, Muellner M, et al. Light-assisted small-molecule
screening against protein kinases. Nature Chemical Biology. 2015;11(12):952-954.
doi:10.1038/nchembio.1933
apa: Inglés Prieto, Á., Gschaider-Reichhart, E., Muellner, M., Nowak, M., Nijman,
S., Grusch, M., & Janovjak, H. L. (2015). Light-assisted small-molecule screening
against protein kinases. Nature Chemical Biology. Nature Publishing Group.
https://doi.org/10.1038/nchembio.1933
chicago: Inglés Prieto, Álvaro, Eva Gschaider-Reichhart, Markus Muellner, Matthias
Nowak, Sebastian Nijman, Michael Grusch, and Harald L Janovjak. “Light-Assisted
Small-Molecule Screening against Protein Kinases.” Nature Chemical Biology.
Nature Publishing Group, 2015. https://doi.org/10.1038/nchembio.1933.
ieee: Á. Inglés Prieto et al., “Light-assisted small-molecule screening against
protein kinases,” Nature Chemical Biology, vol. 11, no. 12. Nature Publishing
Group, pp. 952–954, 2015.
ista: Inglés Prieto Á, Gschaider-Reichhart E, Muellner M, Nowak M, Nijman S, Grusch
M, Janovjak HL. 2015. Light-assisted small-molecule screening against protein
kinases. Nature Chemical Biology. 11(12), 952–954.
mla: Inglés Prieto, Álvaro, et al. “Light-Assisted Small-Molecule Screening against
Protein Kinases.” Nature Chemical Biology, vol. 11, no. 12, Nature Publishing
Group, 2015, pp. 952–54, doi:10.1038/nchembio.1933.
short: Á. Inglés Prieto, E. Gschaider-Reichhart, M. Muellner, M. Nowak, S. Nijman,
M. Grusch, H.L. Janovjak, Nature Chemical Biology 11 (2015) 952–954.
date_created: 2018-12-11T11:53:25Z
date_published: 2015-10-12T00:00:00Z
date_updated: 2023-09-07T12:49:09Z
day: '12'
ddc:
- '571'
department:
- _id: HaJa
- _id: LifeSc
doi: 10.1038/nchembio.1933
ec_funded: 1
file:
- access_level: open_access
checksum: e9fb251dfcb7cd209b83f17867e61321
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:51Z
date_updated: 2020-07-14T12:45:12Z
file_id: '4842'
file_name: IST-2017-837-v1+1_ingles-prieto.pdf
file_size: 1308364
relation: main_file
file_date_updated: 2020-07-14T12:45:12Z
has_accepted_license: '1'
intvolume: ' 11'
issue: '12'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 952 - 954
project:
- _id: 25548C20-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '303564'
name: Microbial Ion Channels for Synthetic Neurobiology
- _id: 255BFFFA-B435-11E9-9278-68D0E5697425
grant_number: RGY0084/2012
name: In situ real-time imaging of neurotransmitter signaling using designer optical
sensors (HFSP Young Investigator)
- _id: 255A6082-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: W1232-B24
name: Molecular Drug Targets
publication: Nature Chemical Biology
publication_status: published
publisher: Nature Publishing Group
publist_id: '5471'
pubrep_id: '837'
quality_controlled: '1'
related_material:
record:
- id: '418'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Light-assisted small-molecule screening against protein kinases
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 11
year: '2015'
...
---
_id: '1679'
article_number: '091102'
author:
- first_name: Grégoire M
full_name: Lemoult, Grégoire M
id: 4787FE80-F248-11E8-B48F-1D18A9856A87
last_name: Lemoult
- first_name: Philipp
full_name: Maier, Philipp
id: 384F7C04-F248-11E8-B48F-1D18A9856A87
last_name: Maier
- first_name: Björn
full_name: Hof, Björn
id: 3A374330-F248-11E8-B48F-1D18A9856A87
last_name: Hof
orcid: 0000-0003-2057-2754
citation:
ama: Lemoult GM, Maier P, Hof B. Taylor’s Forest. Physics of Fluids. 2015;27(9).
doi:10.1063/1.4930850
apa: Lemoult, G. M., Maier, P., & Hof, B. (2015). Taylor’s Forest. Physics
of Fluids. American Institute of Physics. https://doi.org/10.1063/1.4930850
chicago: Lemoult, Grégoire M, Philipp Maier, and Björn Hof. “Taylor’s Forest.” Physics
of Fluids. American Institute of Physics, 2015. https://doi.org/10.1063/1.4930850.
ieee: G. M. Lemoult, P. Maier, and B. Hof, “Taylor’s Forest,” Physics of Fluids,
vol. 27, no. 9. American Institute of Physics, 2015.
ista: Lemoult GM, Maier P, Hof B. 2015. Taylor’s Forest. Physics of Fluids. 27(9),
091102.
mla: Lemoult, Grégoire M., et al. “Taylor’s Forest.” Physics of Fluids, vol.
27, no. 9, 091102, American Institute of Physics, 2015, doi:10.1063/1.4930850.
short: G.M. Lemoult, P. Maier, B. Hof, Physics of Fluids 27 (2015).
date_created: 2018-12-11T11:53:26Z
date_published: 2015-09-24T00:00:00Z
date_updated: 2021-01-12T06:52:28Z
day: '24'
ddc:
- '532'
department:
- _id: BjHo
doi: 10.1063/1.4930850
file:
- access_level: open_access
checksum: 604bba3c2496aadb3efcff77de01ce6c
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:35Z
date_updated: 2020-07-14T12:45:12Z
file_id: '5019'
file_name: IST-2017-748-v1+1_1.4930850.pdf
file_size: 872366
relation: main_file
file_date_updated: 2020-07-14T12:45:12Z
has_accepted_license: '1'
intvolume: ' 27'
issue: '9'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
publication: Physics of Fluids
publication_status: published
publisher: American Institute of Physics
publist_id: '5469'
pubrep_id: '748'
quality_controlled: '1'
scopus_import: 1
status: public
title: Taylor's Forest
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 27
year: '2015'
...