---
_id: '1681'
abstract:
- lang: eng
text: In many social situations, individuals endeavor to find the single best possible
partner, but are constrained to evaluate the candidates in sequence. Examples
include the search for mates, economic partnerships, or any other long-term ties
where the choice to interact involves two parties. Surprisingly, however, previous
theoretical work on mutual choice problems focuses on finding equilibrium solutions,
while ignoring the evolutionary dynamics of decisions. Empirically, this may be
of high importance, as some equilibrium solutions can never be reached unless
the population undergoes radical changes and a sufficient number of individuals
change their decisions simultaneously. To address this question, we apply a mutual
choice sequential search problem in an evolutionary game-theoretical model that
allows one to find solutions that are favored by evolution. As an example, we
study the influence of sequential search on the evolutionary dynamics of cooperation.
For this, we focus on the classic snowdrift game and the prisoner’s dilemma game.
article_processing_charge: No
article_type: original
author:
- first_name: Tadeas
full_name: Priklopil, Tadeas
id: 3C869AA0-F248-11E8-B48F-1D18A9856A87
last_name: Priklopil
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: Priklopil T, Chatterjee K. Evolution of decisions in population games with
sequentially searching individuals. Games. 2015;6(4):413-437. doi:10.3390/g6040413
apa: Priklopil, T., & Chatterjee, K. (2015). Evolution of decisions in population
games with sequentially searching individuals. Games. MDPI. https://doi.org/10.3390/g6040413
chicago: Priklopil, Tadeas, and Krishnendu Chatterjee. “Evolution of Decisions in
Population Games with Sequentially Searching Individuals.” Games. MDPI,
2015. https://doi.org/10.3390/g6040413.
ieee: T. Priklopil and K. Chatterjee, “Evolution of decisions in population games
with sequentially searching individuals,” Games, vol. 6, no. 4. MDPI, pp.
413–437, 2015.
ista: Priklopil T, Chatterjee K. 2015. Evolution of decisions in population games
with sequentially searching individuals. Games. 6(4), 413–437.
mla: Priklopil, Tadeas, and Krishnendu Chatterjee. “Evolution of Decisions in Population
Games with Sequentially Searching Individuals.” Games, vol. 6, no. 4, MDPI,
2015, pp. 413–37, doi:10.3390/g6040413.
short: T. Priklopil, K. Chatterjee, Games 6 (2015) 413–437.
date_created: 2018-12-11T11:53:26Z
date_published: 2015-09-29T00:00:00Z
date_updated: 2023-10-17T11:42:52Z
day: '29'
ddc:
- '000'
department:
- _id: NiBa
- _id: KrCh
doi: 10.3390/g6040413
ec_funded: 1
file:
- access_level: open_access
checksum: 912e1acbaf201100f447a43e4d5958bd
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:41Z
date_updated: 2020-07-14T12:45:12Z
file_id: '4959'
file_name: IST-2016-448-v1+1_games-06-00413.pdf
file_size: 518832
relation: main_file
file_date_updated: 2020-07-14T12:45:12Z
has_accepted_license: '1'
intvolume: ' 6'
issue: '4'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '09'
oa: 1
oa_version: Published Version
page: 413 - 437
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _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: Games
publication_identifier:
eissn:
- 2073-4336
publication_status: published
publisher: MDPI
publist_id: '5467'
pubrep_id: '448'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Evolution of decisions in population games with sequentially searching individuals
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: 6
year: '2015'
...
---
_id: '1655'
abstract:
- lang: eng
text: Quantifying behaviors of robots which were generated autonomously from task-independent
objective functions is an important prerequisite for objective comparisons of
algorithms and movements of animals. The temporal sequence of such a behavior
can be considered as a time series and hence complexity measures developed for
time series are natural candidates for its quantification. The predictive information
and the excess entropy are such complexity measures. They measure the amount of
information the past contains about the future and thus quantify the nonrandom
structure in the temporal sequence. However, when using these measures for systems
with continuous states one has to deal with the fact that their values will depend
on the resolution with which the systems states are observed. For deterministic
systems both measures will diverge with increasing resolution. We therefore propose
a new decomposition of the excess entropy in resolution dependent and resolution
independent parts and discuss how they depend on the dimensionality of the dynamics,
correlations and the noise level. For the practical estimation we propose to use
estimates based on the correlation integral instead of the direct estimation of
the mutual information based on next neighbor statistics because the latter allows
less control of the scale dependencies. Using our algorithm we are able to show
how autonomous learning generates behavior of increasing complexity with increasing
learning duration.
acknowledgement: This work was supported by the DFG priority program 1527 (Autonomous
Learning) and by the European Community’s Seventh Framework Programme (FP7/2007-2013)
under grant agreement no. 318723 (MatheMACS) and from the People Programme (Marie
Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013)
under REA grant agreement no. 291734.
article_processing_charge: No
author:
- first_name: Georg S
full_name: Martius, Georg S
id: 3A276B68-F248-11E8-B48F-1D18A9856A87
last_name: Martius
- first_name: Eckehard
full_name: Olbrich, Eckehard
last_name: Olbrich
citation:
ama: Martius GS, Olbrich E. Quantifying emergent behavior of autonomous robots.
Entropy. 2015;17(10):7266-7297. doi:10.3390/e17107266
apa: Martius, G. S., & Olbrich, E. (2015). Quantifying emergent behavior of
autonomous robots. Entropy. MDPI. https://doi.org/10.3390/e17107266
chicago: Martius, Georg S, and Eckehard Olbrich. “Quantifying Emergent Behavior
of Autonomous Robots.” Entropy. MDPI, 2015. https://doi.org/10.3390/e17107266.
ieee: G. S. Martius and E. Olbrich, “Quantifying emergent behavior of autonomous
robots,” Entropy, vol. 17, no. 10. MDPI, pp. 7266–7297, 2015.
ista: Martius GS, Olbrich E. 2015. Quantifying emergent behavior of autonomous robots.
Entropy. 17(10), 7266–7297.
mla: Martius, Georg S., and Eckehard Olbrich. “Quantifying Emergent Behavior of
Autonomous Robots.” Entropy, vol. 17, no. 10, MDPI, 2015, pp. 7266–97,
doi:10.3390/e17107266.
short: G.S. Martius, E. Olbrich, Entropy 17 (2015) 7266–7297.
date_created: 2018-12-11T11:53:17Z
date_published: 2015-10-23T00:00:00Z
date_updated: 2023-10-17T11:42:00Z
day: '23'
ddc:
- '000'
department:
- _id: ChLa
- _id: GaTk
doi: 10.3390/e17107266
ec_funded: 1
file:
- access_level: open_access
checksum: 945d99631a96e0315acb26dc8541dcf9
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:25Z
date_updated: 2020-07-14T12:45:08Z
file_id: '4943'
file_name: IST-2016-464-v1+1_entropy-17-07266.pdf
file_size: 6455007
relation: main_file
file_date_updated: 2020-07-14T12:45:08Z
has_accepted_license: '1'
intvolume: ' 17'
issue: '10'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: 7266 - 7297
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Entropy
publication_status: published
publisher: MDPI
publist_id: '5495'
pubrep_id: '464'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Quantifying emergent behavior of autonomous robots
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: 17
year: '2015'
...
---
_id: '1834'
abstract:
- lang: eng
text: Huge body of evidences demonstrated that volatile anesthetics affect the hippocampal
neurogenesis and neurocognitive functions, and most of them showed impairment
at anesthetic dose. Here, we investigated the effect of low dose (1.8%) sevoflurane
on hippocampal neurogenesis and dentate gyrus-dependent learning. Neonatal rats
at postnatal day 4 to 6 (P4-6) were treated with 1.8% sevoflurane for 6 hours.
Neurogenesis was quantified by bromodeoxyuridine labeling and electrophysiology
recording. Four and seven weeks after treatment, the Morris water maze and contextual-fear
discrimination learning tests were performed to determine the influence on spatial
learning and pattern separation. A 6-hour treatment with 1.8% sevoflurane promoted
hippocampal neurogenesis and increased the survival of newborn cells and the proportion
of immature granular cells in the dentate gyrus of neonatal rats. Sevoflurane-treated
rats performed better during the training days of the Morris water maze test and
in contextual-fear discrimination learning test. These results suggest that a
subanesthetic dose of sevoflurane promotes hippocampal neurogenesis in neonatal
rats and facilitates their performance in dentate gyrus-dependent learning tasks.
article_processing_charge: No
article_type: original
author:
- first_name: Chong
full_name: Chen, Chong
id: 3DFD581A-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Chao
full_name: Wang, Chao
last_name: Wang
- first_name: Xuan
full_name: Zhao, Xuan
last_name: Zhao
- first_name: Tao
full_name: Zhou, Tao
last_name: Zhou
- first_name: Dao
full_name: Xu, Dao
last_name: Xu
- first_name: Zhi
full_name: Wang, Zhi
last_name: Wang
- first_name: Ying
full_name: Wang, Ying
last_name: Wang
citation:
ama: Chen C, Wang C, Zhao X, et al. Low-dose sevoflurane promoteshippocampal neurogenesis
and facilitates the development of dentate gyrus-dependent learning in neonatal
rats. ASN Neuro. 2015;7(2). doi:10.1177/1759091415575845
apa: Chen, C., Wang, C., Zhao, X., Zhou, T., Xu, D., Wang, Z., & Wang, Y. (2015).
Low-dose sevoflurane promoteshippocampal neurogenesis and facilitates the development
of dentate gyrus-dependent learning in neonatal rats. ASN Neuro. SAGE Publications.
https://doi.org/10.1177/1759091415575845
chicago: Chen, Chong, Chao Wang, Xuan Zhao, Tao Zhou, Dao Xu, Zhi Wang, and Ying
Wang. “Low-Dose Sevoflurane Promoteshippocampal Neurogenesis and Facilitates the
Development of Dentate Gyrus-Dependent Learning in Neonatal Rats.” ASN Neuro.
SAGE Publications, 2015. https://doi.org/10.1177/1759091415575845.
ieee: C. Chen et al., “Low-dose sevoflurane promoteshippocampal neurogenesis
and facilitates the development of dentate gyrus-dependent learning in neonatal
rats,” ASN Neuro, vol. 7, no. 2. SAGE Publications, 2015.
ista: Chen C, Wang C, Zhao X, Zhou T, Xu D, Wang Z, Wang Y. 2015. Low-dose sevoflurane
promoteshippocampal neurogenesis and facilitates the development of dentate gyrus-dependent
learning in neonatal rats. ASN Neuro. 7(2).
mla: Chen, Chong, et al. “Low-Dose Sevoflurane Promoteshippocampal Neurogenesis
and Facilitates the Development of Dentate Gyrus-Dependent Learning in Neonatal
Rats.” ASN Neuro, vol. 7, no. 2, SAGE Publications, 2015, doi:10.1177/1759091415575845.
short: C. Chen, C. Wang, X. Zhao, T. Zhou, D. Xu, Z. Wang, Y. Wang, ASN Neuro 7
(2015).
date_created: 2018-12-11T11:54:16Z
date_published: 2015-04-13T00:00:00Z
date_updated: 2023-10-18T06:47:30Z
day: '13'
ddc:
- '570'
department:
- _id: PeJo
doi: 10.1177/1759091415575845
file:
- access_level: open_access
checksum: 53e16bd3fc2ae2c0d7de9164626c37aa
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:14:08Z
date_updated: 2020-07-14T12:45:18Z
file_id: '5057'
file_name: IST-2016-456-v1+1_ASN_Neuro-2015-Chen-.pdf
file_size: 1146814
relation: main_file
file_date_updated: 2020-07-14T12:45:18Z
has_accepted_license: '1'
intvolume: ' 7'
issue: '2'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/3.0/
month: '04'
oa: 1
oa_version: Published Version
publication: ASN Neuro
publication_status: published
publisher: SAGE Publications
publist_id: '5269'
pubrep_id: '456'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Low-dose sevoflurane promoteshippocampal neurogenesis and facilitates the development
of dentate gyrus-dependent learning in neonatal rats
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
short: CC BY (3.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7
year: '2015'
...
---
_id: '1635'
abstract:
- lang: eng
text: We calculate a Ricci curvature lower bound for some classical examples of
random walks, namely, a chain on a slice of the n-dimensional discrete cube (the
so-called Bernoulli-Laplace model) and the random transposition shuffle of the
symmetric group of permutations on n letters.
article_processing_charge: No
article_type: original
author:
- first_name: Matthias
full_name: Erbar, Matthias
last_name: Erbar
- first_name: Jan
full_name: Maas, Jan
id: 4C5696CE-F248-11E8-B48F-1D18A9856A87
last_name: Maas
orcid: 0000-0002-0845-1338
- first_name: Prasad
full_name: Tetali, Prasad
last_name: Tetali
citation:
ama: Erbar M, Maas J, Tetali P. Discrete Ricci curvature bounds for Bernoulli-Laplace
and random transposition models. Annales de la faculté des sciences de Toulouse.
2015;24(4):781-800. doi:10.5802/afst.1464
apa: Erbar, M., Maas, J., & Tetali, P. (2015). Discrete Ricci curvature bounds
for Bernoulli-Laplace and random transposition models. Annales de La Faculté
Des Sciences de Toulouse. Faculté des sciences de Toulouse. https://doi.org/10.5802/afst.1464
chicago: Erbar, Matthias, Jan Maas, and Prasad Tetali. “Discrete Ricci Curvature
Bounds for Bernoulli-Laplace and Random Transposition Models.” Annales de La
Faculté Des Sciences de Toulouse. Faculté des sciences de Toulouse, 2015.
https://doi.org/10.5802/afst.1464.
ieee: M. Erbar, J. Maas, and P. Tetali, “Discrete Ricci curvature bounds for Bernoulli-Laplace
and random transposition models,” Annales de la faculté des sciences de Toulouse,
vol. 24, no. 4. Faculté des sciences de Toulouse, pp. 781–800, 2015.
ista: Erbar M, Maas J, Tetali P. 2015. Discrete Ricci curvature bounds for Bernoulli-Laplace
and random transposition models. Annales de la faculté des sciences de Toulouse.
24(4), 781–800.
mla: Erbar, Matthias, et al. “Discrete Ricci Curvature Bounds for Bernoulli-Laplace
and Random Transposition Models.” Annales de La Faculté Des Sciences de Toulouse,
vol. 24, no. 4, Faculté des sciences de Toulouse, 2015, pp. 781–800, doi:10.5802/afst.1464.
short: M. Erbar, J. Maas, P. Tetali, Annales de La Faculté Des Sciences de Toulouse
24 (2015) 781–800.
date_created: 2018-12-11T11:53:10Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2023-10-18T07:48:28Z
day: '01'
department:
- _id: JaMa
doi: 10.5802/afst.1464
external_id:
arxiv:
- '1409.8605'
intvolume: ' 24'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1409.8605
month: '01'
oa: 1
oa_version: Preprint
page: 781 - 800
publication: Annales de la faculté des sciences de Toulouse
publication_status: published
publisher: Faculté des sciences de Toulouse
publist_id: '5520'
quality_controlled: '1'
status: public
title: Discrete Ricci curvature bounds for Bernoulli-Laplace and random transposition
models
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '2015'
...
---
_id: '14303'
abstract:
- lang: eng
text: Scaffolded DNA origami enables the fabrication of a variety of complex nanostructures
that promise utility in diverse fields of application, ranging from biosensing
over advanced therapeutics to metamaterials. The broad applicability of DNA origami
as a material beyond the level of proof-of-concept studies critically depends,
among other factors, on the availability of large amounts of pure single-stranded
scaffold DNA. Here, we present a method for the efficient production of M13 bacteriophage-derived
genomic DNA using high-cell-density fermentation of Escherichia coli in stirred-tank
bioreactors. We achieve phage titers of up to 1.6 × 1014 plaque-forming units
per mL. Downstream processing yields up to 410 mg of high-quality single-stranded
DNA per one liter reaction volume, thus upgrading DNA origami-based nanotechnology
from the milligram to the gram scale.
article_processing_charge: No
article_type: letter_note
author:
- first_name: B
full_name: Kick, B
last_name: Kick
- first_name: Florian M
full_name: Praetorius, Florian M
id: dfec9381-4341-11ee-8fd8-faa02bba7d62
last_name: Praetorius
- first_name: H
full_name: Dietz, H
last_name: Dietz
- first_name: D
full_name: Weuster-Botz, D
last_name: Weuster-Botz
citation:
ama: Kick B, Praetorius FM, Dietz H, Weuster-Botz D. Efficient production of single-stranded
phage DNA as scaffolds for DNA origami. Nano Letters. 2015;15(7):4672-4676.
doi:10.1021/acs.nanolett.5b01461
apa: Kick, B., Praetorius, F. M., Dietz, H., & Weuster-Botz, D. (2015). Efficient
production of single-stranded phage DNA as scaffolds for DNA origami. Nano
Letters. ACS Publications. https://doi.org/10.1021/acs.nanolett.5b01461
chicago: Kick, B, Florian M Praetorius, H Dietz, and D Weuster-Botz. “Efficient
Production of Single-Stranded Phage DNA as Scaffolds for DNA Origami.” Nano
Letters. ACS Publications, 2015. https://doi.org/10.1021/acs.nanolett.5b01461.
ieee: B. Kick, F. M. Praetorius, H. Dietz, and D. Weuster-Botz, “Efficient production
of single-stranded phage DNA as scaffolds for DNA origami,” Nano Letters,
vol. 15, no. 7. ACS Publications, pp. 4672–4676, 2015.
ista: Kick B, Praetorius FM, Dietz H, Weuster-Botz D. 2015. Efficient production
of single-stranded phage DNA as scaffolds for DNA origami. Nano Letters. 15(7),
4672–4676.
mla: Kick, B., et al. “Efficient Production of Single-Stranded Phage DNA as Scaffolds
for DNA Origami.” Nano Letters, vol. 15, no. 7, ACS Publications, 2015,
pp. 4672–76, doi:10.1021/acs.nanolett.5b01461.
short: B. Kick, F.M. Praetorius, H. Dietz, D. Weuster-Botz, Nano Letters 15 (2015)
4672–4676.
date_created: 2023-09-06T12:52:47Z
date_published: 2015-06-01T00:00:00Z
date_updated: 2023-11-07T11:56:32Z
day: '01'
doi: 10.1021/acs.nanolett.5b01461
extern: '1'
external_id:
pmid:
- '26028443'
intvolume: ' 15'
issue: '7'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1021/acs.nanolett.5b01461
month: '06'
oa: 1
oa_version: Published Version
page: 4672-4676
pmid: 1
publication: Nano Letters
publication_identifier:
eissn:
- 1530-6992
issn:
- 1530-6984
publication_status: published
publisher: ACS Publications
quality_controlled: '1'
status: public
title: Efficient production of single-stranded phage DNA as scaffolds for DNA origami
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2015'
...
---
_id: '1603'
abstract:
- lang: eng
text: "For deterministic systems, a counterexample to a property can simply be an
error trace, whereas counterexamples in probabilistic systems are necessarily
more complex. For instance, a set of erroneous traces with a sufficient cumulative
probability mass can be used. Since these are too large objects to understand
and manipulate, compact representations such as subchains have been considered.
In the case of probabilistic systems with non-determinism, the situation is even
more complex. While a subchain for a given strategy (or scheduler, resolving non-determinism)
is a straightforward choice, we take a different approach. Instead, we focus on
the strategy itself, and extract the most important decisions it makes, and present
its succinct representation.\r\nThe key tools we employ to achieve this are (1)
introducing a concept of importance of a state w.r.t. the strategy, and (2) learning
using decision trees. There are three main consequent advantages of our approach.
Firstly, it exploits the quantitative information on states, stressing the more
important decisions. Secondly, it leads to a greater variability and degree of
freedom in representing the strategies. Thirdly, the representation uses a self-explanatory
data structure. In summary, our approach produces more succinct and more explainable
strategies, as opposed to e.g. binary decision diagrams. Finally, our experimental
results show that we can extract several rules describing the strategy even for
very large systems that do not fit in memory, and based on the rules explain the
erroneous behaviour."
acknowledgement: This research was funded in part by Austrian Science Fund (FWF) Grant
No P 23499-N23, FWF NFN Grant No S11407-N23 (RiSE) and Z211-N23 (Wittgenstein Award),
European Research Council (ERC) Grant No 279307 (Graph Games), ERC Grant No 267989
(QUAREM), the Czech Science Foundation Grant No P202/12/G061, and People Programme
(Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007–2013)
REA Grant No 291734.
alternative_title:
- LNCS
author:
- first_name: Tomáš
full_name: Brázdil, Tomáš
last_name: Brázdil
- 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: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Andreas
full_name: Fellner, Andreas
id: 42BABFB4-F248-11E8-B48F-1D18A9856A87
last_name: Fellner
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
citation:
ama: 'Brázdil T, Chatterjee K, Chmelik M, Fellner A, Kretinsky J. Counterexample
explanation by learning small strategies in Markov decision processes. In: Vol
9206. Springer; 2015:158-177. doi:10.1007/978-3-319-21690-4_10'
apa: 'Brázdil, T., Chatterjee, K., Chmelik, M., Fellner, A., & Kretinsky, J.
(2015). Counterexample explanation by learning small strategies in Markov decision
processes (Vol. 9206, pp. 158–177). Presented at the CAV: Computer Aided Verification,
San Francisco, CA, United States: Springer. https://doi.org/10.1007/978-3-319-21690-4_10'
chicago: Brázdil, Tomáš, Krishnendu Chatterjee, Martin Chmelik, Andreas Fellner,
and Jan Kretinsky. “Counterexample Explanation by Learning Small Strategies in
Markov Decision Processes,” 9206:158–77. Springer, 2015. https://doi.org/10.1007/978-3-319-21690-4_10.
ieee: 'T. Brázdil, K. Chatterjee, M. Chmelik, A. Fellner, and J. Kretinsky, “Counterexample
explanation by learning small strategies in Markov decision processes,” presented
at the CAV: Computer Aided Verification, San Francisco, CA, United States, 2015,
vol. 9206, pp. 158–177.'
ista: 'Brázdil T, Chatterjee K, Chmelik M, Fellner A, Kretinsky J. 2015. Counterexample
explanation by learning small strategies in Markov decision processes. CAV: Computer
Aided Verification, LNCS, vol. 9206, 158–177.'
mla: Brázdil, Tomáš, et al. Counterexample Explanation by Learning Small Strategies
in Markov Decision Processes. Vol. 9206, Springer, 2015, pp. 158–77, doi:10.1007/978-3-319-21690-4_10.
short: T. Brázdil, K. Chatterjee, M. Chmelik, A. Fellner, J. Kretinsky, in:, Springer,
2015, pp. 158–177.
conference:
end_date: 2015-07-24
location: San Francisco, CA, United States
name: 'CAV: Computer Aided Verification'
start_date: 2015-07-18
date_created: 2018-12-11T11:52:58Z
date_published: 2015-07-16T00:00:00Z
date_updated: 2024-02-21T13:52:07Z
day: '16'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-319-21690-4_10
ec_funded: 1
intvolume: ' 9206'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1502.02834
month: '07'
oa: 1
oa_version: Preprint
page: 158 - 177
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: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_identifier:
eisbn:
- 978-3-319-21690-4
publication_status: published
publisher: Springer
publist_id: '5564'
quality_controlled: '1'
related_material:
record:
- id: '5549'
relation: research_paper
status: public
scopus_import: 1
status: public
title: Counterexample explanation by learning small strategies in Markov decision
processes
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9206
year: '2015'
...
---
_id: '5549'
abstract:
- lang: eng
text: "This repository contains the experimental part of the CAV 2015 publication
Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.\r\nWe
extended the probabilistic model checker PRISM to represent strategies of Markov
Decision Processes as Decision Trees.\r\nThe archive contains a java executable
version of the extended tool (prism_dectree.jar) together with a few examples
of the PRISM benchmark library.\r\nTo execute the program, please have a look
at the README.txt, which provides instructions and further information on the
archive.\r\nThe archive contains scripts that (if run often enough) reproduces
the data presented in the publication."
article_processing_charge: No
author:
- first_name: Andreas
full_name: Fellner, Andreas
id: 42BABFB4-F248-11E8-B48F-1D18A9856A87
last_name: Fellner
citation:
ama: 'Fellner A. Experimental part of CAV 2015 publication: Counterexample Explanation
by Learning Small Strategies in Markov Decision Processes. 2015. doi:10.15479/AT:ISTA:28'
apa: 'Fellner, A. (2015). Experimental part of CAV 2015 publication: Counterexample
Explanation by Learning Small Strategies in Markov Decision Processes. Institute
of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:28'
chicago: 'Fellner, Andreas. “Experimental Part of CAV 2015 Publication: Counterexample
Explanation by Learning Small Strategies in Markov Decision Processes.” Institute
of Science and Technology Austria, 2015. https://doi.org/10.15479/AT:ISTA:28.'
ieee: 'A. Fellner, “Experimental part of CAV 2015 publication: Counterexample Explanation
by Learning Small Strategies in Markov Decision Processes.” Institute of Science
and Technology Austria, 2015.'
ista: 'Fellner A. 2015. Experimental part of CAV 2015 publication: Counterexample
Explanation by Learning Small Strategies in Markov Decision Processes, Institute
of Science and Technology Austria, 10.15479/AT:ISTA:28.'
mla: 'Fellner, Andreas. Experimental Part of CAV 2015 Publication: Counterexample
Explanation by Learning Small Strategies in Markov Decision Processes. Institute
of Science and Technology Austria, 2015, doi:10.15479/AT:ISTA:28.'
short: A. Fellner, (2015).
contributor:
- first_name: Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
datarep_id: '28'
date_created: 2018-12-12T12:31:29Z
date_published: 2015-08-13T00:00:00Z
date_updated: 2024-02-21T13:52:07Z
day: '13'
ddc:
- '004'
department:
- _id: KrCh
- _id: ToHe
doi: 10.15479/AT:ISTA:28
ec_funded: 1
file:
- access_level: open_access
checksum: b8bcb43c0893023cda66c1b69c16ac62
content_type: application/zip
creator: system
date_created: 2018-12-12T13:02:31Z
date_updated: 2020-07-14T12:47:00Z
file_id: '5597'
file_name: IST-2015-28-v1+2_Fellner_DataRep.zip
file_size: 49557109
relation: main_file
file_date_updated: 2020-07-14T12:47:00Z
has_accepted_license: '1'
keyword:
- Markov Decision Process
- Decision Tree
- Probabilistic Verification
- Counterexample Explanation
license: https://creativecommons.org/publicdomain/zero/1.0/
month: '08'
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: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publisher: Institute of Science and Technology Austria
publist_id: '5564'
related_material:
record:
- id: '1603'
relation: popular_science
status: public
status: public
title: 'Experimental part of CAV 2015 publication: Counterexample Explanation by Learning
Small Strategies in Markov Decision Processes'
tmp:
image: /images/cc_0.png
legal_code_url: https://creativecommons.org/publicdomain/zero/1.0/legalcode
name: Creative Commons Public Domain Dedication (CC0 1.0)
short: CC0 (1.0)
type: research_data
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '1512'
abstract:
- lang: eng
text: 'We show that very weak topological assumptions are enough to ensure the existence
of a Helly-type theorem. More precisely, we show that for any non-negative integers
b and d there exists an integer h(b,d) such that the following holds. If F is
a finite family of subsets of R^d such that the ith reduced Betti number (with
Z_2 coefficients in singular homology) of the intersection of any proper subfamily
G of F is at most b for every non-negative integer i less or equal to (d-1)/2,
then F has Helly number at most h(b,d). These topological conditions are sharp:
not controlling any of these first Betti numbers allow for families with unbounded
Helly number. Our proofs combine homological non-embeddability results with a
Ramsey-based approach to build, given an arbitrary simplicial complex K, some
well-behaved chain map from C_*(K) to C_*(R^d). Both techniques are of independent
interest.'
acknowledgement: "PP, ZP and MT were partially supported by the Charles University
Grant GAUK 421511. ZP was\r\npartially supported by the Charles University Grant
SVV-2014-260103. ZP and MT were partially\r\nsupported by the ERC Advanced Grant
No. 267165 and by the project CE-ITI (GACR P202/12/G061)\r\nof the Czech Science
Foundation. UW was partially supported by the Swiss National Science Foundation\r\n(grants
SNSF-200020-138230 and SNSF-PP00P2-138948). Part of this work was done when XG was
affiliated with INRIA Nancy Grand-Est and when MT was affiliated with Institutionen
för matematik, Kungliga Tekniska Högskolan, then IST Austria."
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Xavier
full_name: Goaoc, Xavier
last_name: Goaoc
- first_name: Pavel
full_name: Paták, Pavel
last_name: Paták
- first_name: Zuzana
full_name: Patakova, Zuzana
last_name: Patakova
orcid: 0000-0002-3975-1683
- first_name: Martin
full_name: Tancer, Martin
last_name: Tancer
orcid: 0000-0002-1191-6714
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Bounding Helly numbers via
Betti numbers. In: Vol 34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2015:507-521. doi:10.4230/LIPIcs.SOCG.2015.507'
apa: 'Goaoc, X., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2015). Bounding
Helly numbers via Betti numbers (Vol. 34, pp. 507–521). Presented at the SoCG:
Symposium on Computational Geometry, Eindhoven, Netherlands: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SOCG.2015.507'
chicago: Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner.
“Bounding Helly Numbers via Betti Numbers,” 34:507–21. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2015. https://doi.org/10.4230/LIPIcs.SOCG.2015.507.
ieee: 'X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Bounding Helly
numbers via Betti numbers,” presented at the SoCG: Symposium on Computational
Geometry, Eindhoven, Netherlands, 2015, vol. 34, pp. 507–521.'
ista: 'Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2015. Bounding Helly numbers
via Betti numbers. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 34,
507–521.'
mla: Goaoc, Xavier, et al. Bounding Helly Numbers via Betti Numbers. Vol.
34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 507–21, doi:10.4230/LIPIcs.SOCG.2015.507.
short: X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2015, pp. 507–521.
conference:
end_date: 2015-06-25
location: Eindhoven, Netherlands
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2015-06-22
date_created: 2018-12-11T11:52:27Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2024-02-28T12:59:37Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SOCG.2015.507
file:
- access_level: open_access
checksum: e6881df44d87fe0c2529c9f7b2724614
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:09Z
date_updated: 2020-07-14T12:45:00Z
file_id: '4794'
file_name: IST-2016-501-v1+1_46.pdf
file_size: 633712
relation: main_file
file_date_updated: 2020-07-14T12:45:00Z
has_accepted_license: '1'
intvolume: ' 34'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 507 - 521
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '5665'
pubrep_id: '501'
quality_controlled: '1'
related_material:
record:
- id: '424'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Bounding Helly numbers via Betti numbers
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2015'
...
---
_id: '271'
abstract:
- lang: eng
text: We show that a non-singular integral form of degree d is soluble non-trivially
over the integers if and only if it is soluble non-trivially over the reals and
the p-adic numbers, provided that the form has at least (d-\sqrt{d}/2)2^d variables.
This improves on a longstanding result of Birch.
acknowledgement: While working on this paper the authors were supported by the Leverhulme
Trust and ERC grant 306457.
article_processing_charge: No
article_type: original
author:
- first_name: Timothy D
full_name: Browning, Timothy D
id: 35827D50-F248-11E8-B48F-1D18A9856A87
last_name: Browning
orcid: 0000-0002-8314-0177
- first_name: Sean
full_name: Prendiville, Sean
last_name: Prendiville
citation:
ama: Browning TD, Prendiville S. Improvements in Birch’s theorem on forms in many
variables. Journal fur die Reine und Angewandte Mathematik. 2017(731):203-234.
doi:10.1515/crelle-2014-0122
apa: Browning, T. D., & Prendiville, S. (n.d.). Improvements in Birch’s theorem
on forms in many variables. Journal Fur Die Reine Und Angewandte Mathematik.
Walter de Gruyter. https://doi.org/10.1515/crelle-2014-0122
chicago: Browning, Timothy D, and Sean Prendiville. “Improvements in Birch’s Theorem
on Forms in Many Variables.” Journal Fur Die Reine Und Angewandte Mathematik.
Walter de Gruyter, n.d. https://doi.org/10.1515/crelle-2014-0122.
ieee: T. D. Browning and S. Prendiville, “Improvements in Birch’s theorem on forms
in many variables,” Journal fur die Reine und Angewandte Mathematik, vol.
2017, no. 731. Walter de Gruyter, pp. 203–234.
ista: Browning TD, Prendiville S. Improvements in Birch’s theorem on forms in many
variables. Journal fur die Reine und Angewandte Mathematik. 2017(731), 203–234.
mla: Browning, Timothy D., and Sean Prendiville. “Improvements in Birch’s Theorem
on Forms in Many Variables.” Journal Fur Die Reine Und Angewandte Mathematik,
vol. 2017, no. 731, Walter de Gruyter, pp. 203–34, doi:10.1515/crelle-2014-0122.
short: T.D. Browning, S. Prendiville, Journal Fur Die Reine Und Angewandte Mathematik
2017 (n.d.) 203–234.
date_created: 2018-12-11T11:45:32Z
date_published: 2015-02-20T00:00:00Z
date_updated: 2024-03-05T12:09:22Z
day: '20'
doi: 10.1515/crelle-2014-0122
extern: '1'
external_id:
arxiv:
- '1402.4489'
intvolume: ' 2017'
issue: '731'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1402.4489
month: '02'
oa: 1
oa_version: Preprint
page: 203 - 234
publication: Journal fur die Reine und Angewandte Mathematik
publication_identifier:
issn:
- 0075-4102
publication_status: submitted
publisher: Walter de Gruyter
publist_id: '7631'
quality_controlled: '1'
related_material:
record:
- id: '256'
relation: later_version
status: public
status: public
title: Improvements in Birch's theorem on forms in many variables
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2017
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
article_processing_charge: No
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. In: 35th
Annual Cryptology Conference. Vol 9216. Springer; 2015: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. In 35th Annual Cryptology Conference (Vol. 9216, pp. 585–605).
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.” In 35th Annual Cryptology Conference, 9216:585–605.
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,”
in 35th Annual Cryptology Conference, Santa Barbara, CA, United States,
2015, vol. 9216, pp. 585–605.
ista: 'Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2015. Proofs of space.
35th Annual Cryptology Conference. CRYPTO: International Cryptology Conference,
LNCS, vol. 9216, 585–605.'
mla: Dziembowski, Stefan, et al. “Proofs of Space.” 35th Annual Cryptology Conference,
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, in:, 35th Annual
Cryptology Conference, Springer, 2015, pp. 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: 2024-03-20T08:31:49Z
day: '01'
department:
- _id: VlKo
- _id: KrPi
doi: 10.1007/978-3-662-48000-7_29
ec_funded: 1
intvolume: ' 9216'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2013/796.pdf
month: '08'
oa: 1
oa_version: Preprint
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: 35th Annual Cryptology Conference
publication_identifier:
isbn:
- '9783662479995'
issn:
- 0302-9743
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'
status: public
title: Proofs of space
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9216
year: '2015'
...