---
_id: '9753'
abstract:
- lang: eng
text: 'Background: The brood of ants and other social insects is highly susceptible
to pathogens, particularly those that penetrate the soft larval and pupal cuticle.
We here test whether the presence of a pupal cocoon, which occurs in some ant
species but not in others, affects the sanitary brood care and fungal infection
patterns after exposure to the entomopathogenic fungus Metarhizium brunneum. We
use a) a comparative approach analysing four species with either naked or cocooned
pupae and b) a within-species analysis of a single ant species, in which both
pupal types co-exist in the same colony. Results: We found that the presence of
a cocoon did not compromise fungal pathogen detection by the ants and that species
with cocooned pupae increased brood grooming after pathogen exposure. All tested
ant species further removed brood from their nests, which was predominantly expressed
towards larvae and naked pupae treated with the live fungal pathogen. In contrast,
cocooned pupae exposed to live fungus were not removed at higher rates than cocooned
pupae exposed to dead fungus or a sham control. Consistent with this, exposure
to the live fungus caused high numbers of infections and fungal outgrowth in larvae
and naked pupae, but not in cocooned pupae. Moreover, the ants consistently removed
the brood prior to fungal outgrowth, ensuring a clean brood chamber. Conclusion:
Our study suggests that the pupal cocoon has a protective effect against fungal
infection, causing an adaptive change in sanitary behaviours by the ants. It further
demonstrates that brood removal - originally described for honeybees as “hygienic
behaviour” – is a widespread sanitary behaviour in ants, which likely has important
implications on disease dynamics in social insect colonies.'
article_processing_charge: No
author:
- first_name: Simon
full_name: Tragust, Simon
id: 35A7A418-F248-11E8-B48F-1D18A9856A87
last_name: Tragust
- first_name: Line V
full_name: Ugelvig, Line V
id: 3DC97C8E-F248-11E8-B48F-1D18A9856A87
last_name: Ugelvig
orcid: 0000-0003-1832-8883
- first_name: Michel
full_name: Chapuisat, Michel
last_name: Chapuisat
- first_name: Jürgen
full_name: Heinze, Jürgen
last_name: Heinze
- first_name: Sylvia
full_name: Cremer, Sylvia
id: 2F64EC8C-F248-11E8-B48F-1D18A9856A87
last_name: Cremer
orcid: 0000-0002-2193-3868
citation:
ama: 'Tragust S, Ugelvig LV, Chapuisat M, Heinze J, Cremer S. Data from: Pupal cocoons
affect sanitary brood care and limit fungal infections in ant colonies. 2014.
doi:10.5061/dryad.nc0gc'
apa: 'Tragust, S., Ugelvig, L. V., Chapuisat, M., Heinze, J., & Cremer, S. (2014).
Data from: Pupal cocoons affect sanitary brood care and limit fungal infections
in ant colonies. Dryad. https://doi.org/10.5061/dryad.nc0gc'
chicago: 'Tragust, Simon, Line V Ugelvig, Michel Chapuisat, Jürgen Heinze, and Sylvia
Cremer. “Data from: Pupal Cocoons Affect Sanitary Brood Care and Limit Fungal
Infections in Ant Colonies.” Dryad, 2014. https://doi.org/10.5061/dryad.nc0gc.'
ieee: 'S. Tragust, L. V. Ugelvig, M. Chapuisat, J. Heinze, and S. Cremer, “Data
from: Pupal cocoons affect sanitary brood care and limit fungal infections in
ant colonies.” Dryad, 2014.'
ista: 'Tragust S, Ugelvig LV, Chapuisat M, Heinze J, Cremer S. 2014. Data from:
Pupal cocoons affect sanitary brood care and limit fungal infections in ant colonies,
Dryad, 10.5061/dryad.nc0gc.'
mla: 'Tragust, Simon, et al. Data from: Pupal Cocoons Affect Sanitary Brood Care
and Limit Fungal Infections in Ant Colonies. Dryad, 2014, doi:10.5061/dryad.nc0gc.'
short: S. Tragust, L.V. Ugelvig, M. Chapuisat, J. Heinze, S. Cremer, (2014).
date_created: 2021-07-30T08:24:11Z
date_published: 2014-10-08T00:00:00Z
date_updated: 2023-02-23T10:36:17Z
day: '08'
department:
- _id: SyCr
doi: 10.5061/dryad.nc0gc
main_file_link:
- open_access: '1'
url: https://doi.org/10.5061/dryad.nc0gc
month: '10'
oa: 1
oa_version: Published Version
publisher: Dryad
related_material:
record:
- id: '2284'
relation: used_in_publication
status: public
status: public
title: 'Data from: Pupal cocoons affect sanitary brood care and limit fungal infections
in ant colonies'
type: research_data_reference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
year: '2014'
...
---
_id: '9888'
abstract:
- lang: eng
text: Detailed description of the experimental prodedures, data analyses and additional
statistical analyses of the results.
article_processing_charge: No
author:
- first_name: Stephan
full_name: Wolf, Stephan
last_name: Wolf
- first_name: Dino
full_name: Mcmahon, Dino
last_name: Mcmahon
- first_name: Ka
full_name: Lim, Ka
last_name: Lim
- first_name: Christopher
full_name: Pull, Christopher
id: 3C7F4840-F248-11E8-B48F-1D18A9856A87
last_name: Pull
orcid: 0000-0003-1122-3982
- first_name: Suzanne
full_name: Clark, Suzanne
last_name: Clark
- first_name: Robert
full_name: Paxton, Robert
last_name: Paxton
- first_name: Juliet
full_name: Osborne, Juliet
last_name: Osborne
citation:
ama: Wolf S, Mcmahon D, Lim K, et al. Supporting information. 2014. doi:10.1371/journal.pone.0103989.s003
apa: Wolf, S., Mcmahon, D., Lim, K., Pull, C., Clark, S., Paxton, R., & Osborne,
J. (2014). Supporting information. Public Library of Science. https://doi.org/10.1371/journal.pone.0103989.s003
chicago: Wolf, Stephan, Dino Mcmahon, Ka Lim, Christopher Pull, Suzanne Clark, Robert
Paxton, and Juliet Osborne. “Supporting Information.” Public Library of Science,
2014. https://doi.org/10.1371/journal.pone.0103989.s003.
ieee: S. Wolf et al., “Supporting information.” Public Library of Science,
2014.
ista: Wolf S, Mcmahon D, Lim K, Pull C, Clark S, Paxton R, Osborne J. 2014. Supporting
information, Public Library of Science, 10.1371/journal.pone.0103989.s003.
mla: Wolf, Stephan, et al. Supporting Information. Public Library of Science,
2014, doi:10.1371/journal.pone.0103989.s003.
short: S. Wolf, D. Mcmahon, K. Lim, C. Pull, S. Clark, R. Paxton, J. Osborne, (2014).
date_created: 2021-08-11T14:17:53Z
date_updated: 2023-02-23T10:27:38Z
day: '06'
department:
- _id: SyCr
doi: 10.1371/journal.pone.0103989.s003
month: '08'
oa_version: Published Version
publisher: Public Library of Science
related_material:
record:
- id: '2086'
relation: used_in_publication
status: public
status: public
title: Supporting information
type: research_data_reference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
year: '2014'
...
---
_id: '9931'
abstract:
- lang: eng
text: Gene duplication is important in evolution, because it provides new raw material
for evolutionary adaptations. Several existing hypotheses about the causes of
duplicate retention and diversification differ in their emphasis on gene dosage,
subfunctionalization, and neofunctionalization. Little experimental data exist
on the relative importance of gene expression changes and changes in coding regions
for the evolution of duplicate genes. Furthermore, we do not know how strongly
the environment could affect this importance. To address these questions, we performed
evolution experiments with the TEM-1 beta lactamase gene in Escherichia coli to
study the initial stages of duplicate gene evolution in the laboratory. We mimicked
tandem duplication by inserting two copies of the TEM-1 gene on the same plasmid.
We then subjected these copies to repeated cycles of mutagenesis and selection
in various environments that contained antibiotics in different combinations and
concentrations. Our experiments showed that gene dosage is the most important
factor in the initial stages of duplicate gene evolution, and overshadows the
importance of point mutations in the coding region.
acknowledgement: We thank the Functional Genomics Center Zurich for its service in
generating sequencing data, M. Ackermann and E. Hayden for helpful discussions,
A. de Visser for comments on earlier versions of this manuscript, and M. Moser for
help with quantitative PCR. This work was supported by Swiss National Science Foundation
(grant 315230–129708), as well as through the YeastX project of SystemsX.ch, and
the University Priority Research Program in Systems Biology at the University of
Zurich. RD acknowledges support from the Forschungskredit program of the University
of Zurich. The authors declare no conflict of interest.
article_processing_charge: No
article_type: original
author:
- first_name: Riddhiman
full_name: Dhar, Riddhiman
last_name: Dhar
- first_name: Tobias
full_name: Bergmiller, Tobias
id: 2C471CFA-F248-11E8-B48F-1D18A9856A87
last_name: Bergmiller
orcid: 0000-0001-5396-4346
- first_name: Andreas
full_name: Wagner, Andreas
last_name: Wagner
citation:
ama: Dhar R, Bergmiller T, Wagner A. Increased gene dosage plays a predominant role
in the initial stages of evolution of duplicate TEM-1 beta lactamase genes. Evolution.
2014;68(6):1775-1791. doi:10.1111/evo.12373
apa: Dhar, R., Bergmiller, T., & Wagner, A. (2014). Increased gene dosage plays
a predominant role in the initial stages of evolution of duplicate TEM-1 beta
lactamase genes. Evolution. Wiley. https://doi.org/10.1111/evo.12373
chicago: Dhar, Riddhiman, Tobias Bergmiller, and Andreas Wagner. “Increased Gene
Dosage Plays a Predominant Role in the Initial Stages of Evolution of Duplicate
TEM-1 Beta Lactamase Genes.” Evolution. Wiley, 2014. https://doi.org/10.1111/evo.12373.
ieee: R. Dhar, T. Bergmiller, and A. Wagner, “Increased gene dosage plays a predominant
role in the initial stages of evolution of duplicate TEM-1 beta lactamase genes,”
Evolution, vol. 68, no. 6. Wiley, pp. 1775–1791, 2014.
ista: Dhar R, Bergmiller T, Wagner A. 2014. Increased gene dosage plays a predominant
role in the initial stages of evolution of duplicate TEM-1 beta lactamase genes.
Evolution. 68(6), 1775–1791.
mla: Dhar, Riddhiman, et al. “Increased Gene Dosage Plays a Predominant Role in
the Initial Stages of Evolution of Duplicate TEM-1 Beta Lactamase Genes.” Evolution,
vol. 68, no. 6, Wiley, 2014, pp. 1775–91, doi:10.1111/evo.12373.
short: R. Dhar, T. Bergmiller, A. Wagner, Evolution 68 (2014) 1775–1791.
date_created: 2021-08-17T09:03:09Z
date_published: 2014-06-03T00:00:00Z
date_updated: 2023-02-23T14:13:27Z
day: '03'
department:
- _id: CaGu
doi: 10.1111/evo.12373
external_id:
pmid:
- '24495000'
intvolume: ' 68'
issue: '6'
language:
- iso: eng
month: '06'
oa_version: None
page: 1775-1791
pmid: 1
publication: Evolution
publication_identifier:
eissn:
- 1558-5646
issn:
- 0014-3820
publication_status: published
publisher: Wiley
quality_controlled: '1'
related_material:
record:
- id: '9932'
relation: research_data
status: public
scopus_import: '1'
status: public
title: Increased gene dosage plays a predominant role in the initial stages of evolution
of duplicate TEM-1 beta lactamase genes
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 68
year: '2014'
...
---
_id: '9932'
abstract:
- lang: eng
text: Gene duplication is important in evolution, because it provides new raw material
for evolutionary adaptations. Several existing hypotheses about the causes of
duplicate retention and diversification differ in their emphasis on gene dosage,
sub-functionalization, and neo-functionalization. Little experimental data exists
on the relative importance of gene expression changes and changes in coding regions
for the evolution of duplicate genes. Furthermore, we do not know how strongly
the environment could affect this importance. To address these questions, we performed
evolution experiments with the TEM-1 beta lactamase gene in E. coli to study the
initial stages of duplicate gene evolution in the laboratory. We mimicked tandem
duplication by inserting two copies of the TEM-1 gene on the same plasmid. We
then subjected these copies to repeated cycles of mutagenesis and selection in
various environments that contained antibiotics in different combinations and
concentrations. Our experiments showed that gene dosage is the most important
factor in the initial stages of duplicate gene evolution, and overshadows the
importance of point mutations in the coding region.
article_processing_charge: No
author:
- first_name: Riddhiman
full_name: Dhar, Riddhiman
last_name: Dhar
- first_name: Tobias
full_name: Bergmiller, Tobias
id: 2C471CFA-F248-11E8-B48F-1D18A9856A87
last_name: Bergmiller
orcid: 0000-0001-5396-4346
- first_name: Andreas
full_name: Wagner, Andreas
last_name: Wagner
citation:
ama: 'Dhar R, Bergmiller T, Wagner A. Data from: Increased gene dosage plays a predominant
role in the initial stages of evolution of duplicate TEM-1 beta lactamase genes.
2014. doi:10.5061/dryad.jc402'
apa: 'Dhar, R., Bergmiller, T., & Wagner, A. (2014). Data from: Increased gene
dosage plays a predominant role in the initial stages of evolution of duplicate
TEM-1 beta lactamase genes. Dryad. https://doi.org/10.5061/dryad.jc402'
chicago: 'Dhar, Riddhiman, Tobias Bergmiller, and Andreas Wagner. “Data from: Increased
Gene Dosage Plays a Predominant Role in the Initial Stages of Evolution of Duplicate
TEM-1 Beta Lactamase Genes.” Dryad, 2014. https://doi.org/10.5061/dryad.jc402.'
ieee: 'R. Dhar, T. Bergmiller, and A. Wagner, “Data from: Increased gene dosage
plays a predominant role in the initial stages of evolution of duplicate TEM-1
beta lactamase genes.” Dryad, 2014.'
ista: 'Dhar R, Bergmiller T, Wagner A. 2014. Data from: Increased gene dosage plays
a predominant role in the initial stages of evolution of duplicate TEM-1 beta
lactamase genes, Dryad, 10.5061/dryad.jc402.'
mla: 'Dhar, Riddhiman, et al. Data from: Increased Gene Dosage Plays a Predominant
Role in the Initial Stages of Evolution of Duplicate TEM-1 Beta Lactamase Genes.
Dryad, 2014, doi:10.5061/dryad.jc402.'
short: R. Dhar, T. Bergmiller, A. Wagner, (2014).
date_created: 2021-08-17T09:11:40Z
date_published: 2014-01-27T00:00:00Z
date_updated: 2023-02-23T14:13:24Z
day: '27'
department:
- _id: CaGu
doi: 10.5061/dryad.jc402
main_file_link:
- open_access: '1'
url: https://doi.org/10.5061/dryad.jc402
month: '01'
oa: 1
oa_version: Published Version
publisher: Dryad
related_material:
record:
- id: '9931'
relation: used_in_publication
status: public
status: public
title: 'Data from: Increased gene dosage plays a predominant role in the initial stages
of evolution of duplicate TEM-1 beta lactamase genes'
type: research_data_reference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
year: '2014'
...
---
_id: '10817'
abstract:
- lang: eng
text: The Morse-Smale complex can be either explicitly or implicitly represented.
Depending on the type of representation, the simplification of the Morse-Smale
complex works differently. In the explicit representation, the Morse-Smale complex
is directly simplified by explicitly reconnecting the critical points during the
simplification. In the implicit representation, on the other hand, the Morse-Smale
complex is given by a combinatorial gradient field. In this setting, the simplification
changes the combinatorial flow, which yields an indirect simplification of the
Morse-Smale complex. The topological complexity of the Morse-Smale complex is
reduced in both representations. However, the simplifications generally yield
different results. In this chapter, we emphasize properties of the two representations
that cause these differences. We also provide a complexity analysis of the two
schemes with respect to running time and memory consumption.
acknowledgement: This research is supported and funded by the Digiteo unTopoVis project,
the TOPOSYS project FP7-ICT-318493-STREP, and MPC-VCC.
article_processing_charge: No
author:
- first_name: David
full_name: Günther, David
last_name: Günther
- first_name: Jan
full_name: Reininghaus, Jan
id: 4505473A-F248-11E8-B48F-1D18A9856A87
last_name: Reininghaus
- first_name: Hans-Peter
full_name: Seidel, Hans-Peter
last_name: Seidel
- first_name: Tino
full_name: Weinkauf, Tino
last_name: Weinkauf
citation:
ama: 'Günther D, Reininghaus J, Seidel H-P, Weinkauf T. Notes on the simplification
of the Morse-Smale complex. In: Bremer P-T, Hotz I, Pascucci V, Peikert R, eds.
Topological Methods in Data Analysis and Visualization III. Mathematics
and Visualization. Cham: Springer Nature; 2014:135-150. doi:10.1007/978-3-319-04099-8_9'
apa: 'Günther, D., Reininghaus, J., Seidel, H.-P., & Weinkauf, T. (2014). Notes
on the simplification of the Morse-Smale complex. In P.-T. Bremer, I. Hotz, V.
Pascucci, & R. Peikert (Eds.), Topological Methods in Data Analysis and
Visualization III. (pp. 135–150). Cham: Springer Nature. https://doi.org/10.1007/978-3-319-04099-8_9'
chicago: 'Günther, David, Jan Reininghaus, Hans-Peter Seidel, and Tino Weinkauf.
“Notes on the Simplification of the Morse-Smale Complex.” In Topological Methods
in Data Analysis and Visualization III., edited by Peer-Timo Bremer, Ingrid
Hotz, Valerio Pascucci, and Ronald Peikert, 135–50. Mathematics and Visualization.
Cham: Springer Nature, 2014. https://doi.org/10.1007/978-3-319-04099-8_9.'
ieee: 'D. Günther, J. Reininghaus, H.-P. Seidel, and T. Weinkauf, “Notes on the
simplification of the Morse-Smale complex,” in Topological Methods in Data
Analysis and Visualization III., P.-T. Bremer, I. Hotz, V. Pascucci, and R.
Peikert, Eds. Cham: Springer Nature, 2014, pp. 135–150.'
ista: 'Günther D, Reininghaus J, Seidel H-P, Weinkauf T. 2014.Notes on the simplification
of the Morse-Smale complex. In: Topological Methods in Data Analysis and Visualization
III. , 135–150.'
mla: Günther, David, et al. “Notes on the Simplification of the Morse-Smale Complex.”
Topological Methods in Data Analysis and Visualization III., edited by
Peer-Timo Bremer et al., Springer Nature, 2014, pp. 135–50, doi:10.1007/978-3-319-04099-8_9.
short: D. Günther, J. Reininghaus, H.-P. Seidel, T. Weinkauf, in:, P.-T. Bremer,
I. Hotz, V. Pascucci, R. Peikert (Eds.), Topological Methods in Data Analysis
and Visualization III., Springer Nature, Cham, 2014, pp. 135–150.
date_created: 2022-03-04T08:33:57Z
date_published: 2014-03-19T00:00:00Z
date_updated: 2023-09-05T15:33:45Z
day: '19'
department:
- _id: HeEd
doi: 10.1007/978-3-319-04099-8_9
ec_funded: 1
editor:
- first_name: Peer-Timo
full_name: Bremer, Peer-Timo
last_name: Bremer
- first_name: Ingrid
full_name: Hotz, Ingrid
last_name: Hotz
- first_name: Valerio
full_name: Pascucci, Valerio
last_name: Pascucci
- first_name: Ronald
full_name: Peikert, Ronald
last_name: Peikert
language:
- iso: eng
month: '03'
oa_version: None
page: 135-150
place: Cham
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
publication: Topological Methods in Data Analysis and Visualization III.
publication_identifier:
eisbn:
- '9783319040998'
eissn:
- 2197-666X
isbn:
- '9783319040981'
issn:
- 1612-3786
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: Mathematics and Visualization
status: public
title: Notes on the simplification of the Morse-Smale complex
type: book_chapter
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2014'
...
---
_id: '10884'
abstract:
- lang: eng
text: "We revisit the parameterized model checking problem for token-passing systems
and specifications in indexed CTL ∗ \\X. Emerson and Namjoshi (1995, 2003) have
shown that parameterized model checking of indexed CTL ∗ \\X in uni-directional
token rings can be reduced to checking rings up to some cutoff size. Clarke et
al. (2004) have shown a similar result for general topologies and indexed LTL
\\X, provided processes cannot choose the directions for sending or receiving
the token.\r\nWe unify and substantially extend these results by systematically
exploring fragments of indexed CTL ∗ \\X with respect to general topologies.
For each fragment we establish whether a cutoff exists, and for some concrete
topologies, such as rings, cliques and stars, we infer small cutoffs. Finally,
we show that the problem becomes undecidable, and thus no cutoffs exist, if processes
are allowed to choose the directions in which they send or from which they receive
the token."
acknowledgement: "This work was supported by the Austrian Science Fund through grant
P23499-N23\r\nand through the RiSE network (S11403, S11405, S11406, S11407-N23);
ERC Starting Grant (279307: Graph Games); Vienna Science and Technology Fund (WWTF)\r\ngrants
PROSEED, ICT12-059, and VRG11-005."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Benjamin
full_name: Aminof, Benjamin
id: 4A55BD00-F248-11E8-B48F-1D18A9856A87
last_name: Aminof
- first_name: Swen
full_name: Jacobs, Swen
last_name: Jacobs
- first_name: Ayrat
full_name: Khalimov, Ayrat
last_name: Khalimov
- first_name: Sasha
full_name: Rubin, Sasha
id: 2EC51194-F248-11E8-B48F-1D18A9856A87
last_name: Rubin
citation:
ama: 'Aminof B, Jacobs S, Khalimov A, Rubin S. Parameterized model checking of token-passing
systems. In: Verification, Model Checking, and Abstract Interpretation.
Vol 8318. Springer Nature; 2014:262-281. doi:10.1007/978-3-642-54013-4_15'
apa: 'Aminof, B., Jacobs, S., Khalimov, A., & Rubin, S. (2014). Parameterized
model checking of token-passing systems. In Verification, Model Checking, and
Abstract Interpretation (Vol. 8318, pp. 262–281). San Diego, CA, United States:
Springer Nature. https://doi.org/10.1007/978-3-642-54013-4_15'
chicago: Aminof, Benjamin, Swen Jacobs, Ayrat Khalimov, and Sasha Rubin. “Parameterized
Model Checking of Token-Passing Systems.” In Verification, Model Checking,
and Abstract Interpretation, 8318:262–81. Springer Nature, 2014. https://doi.org/10.1007/978-3-642-54013-4_15.
ieee: B. Aminof, S. Jacobs, A. Khalimov, and S. Rubin, “Parameterized model checking
of token-passing systems,” in Verification, Model Checking, and Abstract Interpretation,
San Diego, CA, United States, 2014, vol. 8318, pp. 262–281.
ista: 'Aminof B, Jacobs S, Khalimov A, Rubin S. 2014. Parameterized model checking
of token-passing systems. Verification, Model Checking, and Abstract Interpretation.
VMCAI: Verifcation, Model Checking, and Abstract Interpretation, LNCS, vol. 8318,
262–281.'
mla: Aminof, Benjamin, et al. “Parameterized Model Checking of Token-Passing Systems.”
Verification, Model Checking, and Abstract Interpretation, vol. 8318, Springer
Nature, 2014, pp. 262–81, doi:10.1007/978-3-642-54013-4_15.
short: B. Aminof, S. Jacobs, A. Khalimov, S. Rubin, in:, Verification, Model Checking,
and Abstract Interpretation, Springer Nature, 2014, pp. 262–281.
conference:
end_date: 2014-01-21
location: San Diego, CA, United States
name: 'VMCAI: Verifcation, Model Checking, and Abstract Interpretation'
start_date: 2014-01-19
date_created: 2022-03-18T13:01:22Z
date_published: 2014-01-30T00:00:00Z
date_updated: 2022-05-17T08:36:01Z
day: '30'
department:
- _id: KrCh
doi: 10.1007/978-3-642-54013-4_15
ec_funded: 1
external_id:
arxiv:
- '1311.4425'
intvolume: ' 8318'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.1311.4425'
month: '01'
oa: 1
oa_version: Preprint
page: 262-281
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication: Verification, Model Checking, and Abstract Interpretation
publication_identifier:
eisbn:
- '9783642540134'
eissn:
- 1611-3349
isbn:
- '9783642540127'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Parameterized model checking of token-passing systems
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8318
year: '2014'
...
---
_id: '10885'
abstract:
- lang: eng
text: "Two-player games on graphs provide the theoretical framework for many important
problems such as reactive synthesis. While the traditional study of two-player
zero-sum games has been extended to multi-player games with several notions of
equilibria, they are decidable only for perfect-information games, whereas several
applications require imperfect-information games.\r\nIn this paper we propose
a new notion of equilibria, called doomsday equilibria, which is a strategy profile
such that all players satisfy their own objective, and if any coalition of players
deviates and violates even one of the players objective, then the objective of
every player is violated.\r\nWe present algorithms and complexity results for
deciding the existence of doomsday equilibria for various classes of ω-regular
objectives, both for imperfect-information games, and for perfect-information
games.We provide optimal complexity bounds for imperfect-information games, and
in most cases for perfect-information games."
acknowledgement: " Supported by Austrian Science Fund (FWF) Grant No P23499-N23, FWF
NFN Grant No\r\nS11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft
faculty fellows award."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Emmanuel
full_name: Filiot, Emmanuel
last_name: Filiot
- first_name: Jean-François
full_name: Raskin, Jean-François
last_name: Raskin
citation:
ama: 'Chatterjee K, Doyen L, Filiot E, Raskin J-F. Doomsday equilibria for omega-regular
games. In: VMCAI 2014: Verification, Model Checking, and Abstract Interpretation.
Vol 8318. Springer Nature; 2014:78-97. doi:10.1007/978-3-642-54013-4_5'
apa: 'Chatterjee, K., Doyen, L., Filiot, E., & Raskin, J.-F. (2014). Doomsday
equilibria for omega-regular games. In VMCAI 2014: Verification, Model Checking,
and Abstract Interpretation (Vol. 8318, pp. 78–97). San Diego, CA, United
States: Springer Nature. https://doi.org/10.1007/978-3-642-54013-4_5'
chicago: 'Chatterjee, Krishnendu, Laurent Doyen, Emmanuel Filiot, and Jean-François
Raskin. “Doomsday Equilibria for Omega-Regular Games.” In VMCAI 2014: Verification,
Model Checking, and Abstract Interpretation, 8318:78–97. Springer Nature,
2014. https://doi.org/10.1007/978-3-642-54013-4_5.'
ieee: 'K. Chatterjee, L. Doyen, E. Filiot, and J.-F. Raskin, “Doomsday equilibria
for omega-regular games,” in VMCAI 2014: Verification, Model Checking, and
Abstract Interpretation, San Diego, CA, United States, 2014, vol. 8318, pp.
78–97.'
ista: 'Chatterjee K, Doyen L, Filiot E, Raskin J-F. 2014. Doomsday equilibria for
omega-regular games. VMCAI 2014: Verification, Model Checking, and Abstract Interpretation.
VMCAI: Verifcation, Model Checking, and Abstract Interpretation, LNCS, vol. 8318,
78–97.'
mla: 'Chatterjee, Krishnendu, et al. “Doomsday Equilibria for Omega-Regular Games.”
VMCAI 2014: Verification, Model Checking, and Abstract Interpretation,
vol. 8318, Springer Nature, 2014, pp. 78–97, doi:10.1007/978-3-642-54013-4_5.'
short: 'K. Chatterjee, L. Doyen, E. Filiot, J.-F. Raskin, in:, VMCAI 2014: Verification,
Model Checking, and Abstract Interpretation, Springer Nature, 2014, pp. 78–97.'
conference:
end_date: 2014-01-21
location: San Diego, CA, United States
name: 'VMCAI: Verifcation, Model Checking, and Abstract Interpretation'
start_date: 2014-01-19
date_created: 2022-03-18T13:03:15Z
date_published: 2014-01-30T00:00:00Z
date_updated: 2023-02-23T12:52:24Z
day: '30'
department:
- _id: KrCh
doi: 10.1007/978-3-642-54013-4_5
ec_funded: 1
external_id:
arxiv:
- '1311.3238'
intvolume: ' 8318'
language:
- iso: eng
month: '01'
oa_version: Preprint
page: 78-97
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: 'VMCAI 2014: Verification, Model Checking, and Abstract Interpretation'
publication_identifier:
eisbn:
- '9783642540134'
eissn:
- 1611-3349
isbn:
- '9783642540127'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '681'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Doomsday equilibria for omega-regular games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8318
year: '2014'
...
---
_id: '10886'
abstract:
- lang: eng
text: We propose a method for visualizing two-dimensional symmetric positive definite
tensor fields using the Heat Kernel Signature (HKS). The HKS is derived from the
heat kernel and was originally introduced as an isometry invariant shape signature.
Each positive definite tensor field defines a Riemannian manifold by considering
the tensor field as a Riemannian metric. On this Riemmanian manifold we can apply
the definition of the HKS. The resulting scalar quantity is used for the visualization
of tensor fields. The HKS is closely related to the Gaussian curvature of the
Riemannian manifold and the time parameter of the heat kernel allows a multiscale
analysis in a natural way. In this way, the HKS represents field related scale
space properties, enabling a level of detail analysis of tensor fields. This makes
the HKS an interesting new scalar quantity for tensor fields, which differs significantly
from usual tensor invariants like the trace or the determinant. A method for visualization
and a numerical realization of the HKS for tensor fields is proposed in this chapter.
To validate the approach we apply it to some illustrating simple examples as isolated
critical points and to a medical diffusion tensor data set.
acknowledgement: This research is partially supported by the TOPOSYS project FP7-ICT-318493-STREP.
alternative_title:
- Mathematics and Visualization
article_processing_charge: No
author:
- first_name: Valentin
full_name: Zobel, Valentin
last_name: Zobel
- first_name: Jan
full_name: Reininghaus, Jan
id: 4505473A-F248-11E8-B48F-1D18A9856A87
last_name: Reininghaus
- first_name: Ingrid
full_name: Hotz, Ingrid
last_name: Hotz
citation:
ama: 'Zobel V, Reininghaus J, Hotz I. Visualization of two-dimensional symmetric
positive definite tensor fields using the heat kernel signature. In: Topological
Methods in Data Analysis and Visualization III . Springer; 2014:249-262. doi:10.1007/978-3-319-04099-8_16'
apa: Zobel, V., Reininghaus, J., & Hotz, I. (2014). Visualization of two-dimensional
symmetric positive definite tensor fields using the heat kernel signature. In
Topological Methods in Data Analysis and Visualization III (pp. 249–262).
Springer. https://doi.org/10.1007/978-3-319-04099-8_16
chicago: Zobel, Valentin, Jan Reininghaus, and Ingrid Hotz. “Visualization of Two-Dimensional
Symmetric Positive Definite Tensor Fields Using the Heat Kernel Signature.” In
Topological Methods in Data Analysis and Visualization III , 249–62. Springer,
2014. https://doi.org/10.1007/978-3-319-04099-8_16.
ieee: V. Zobel, J. Reininghaus, and I. Hotz, “Visualization of two-dimensional symmetric
positive definite tensor fields using the heat kernel signature,” in Topological
Methods in Data Analysis and Visualization III , 2014, pp. 249–262.
ista: Zobel V, Reininghaus J, Hotz I. 2014. Visualization of two-dimensional symmetric
positive definite tensor fields using the heat kernel signature. Topological Methods
in Data Analysis and Visualization III . , Mathematics and Visualization, , 249–262.
mla: Zobel, Valentin, et al. “Visualization of Two-Dimensional Symmetric Positive
Definite Tensor Fields Using the Heat Kernel Signature.” Topological Methods
in Data Analysis and Visualization III , Springer, 2014, pp. 249–62, doi:10.1007/978-3-319-04099-8_16.
short: V. Zobel, J. Reininghaus, I. Hotz, in:, Topological Methods in Data Analysis
and Visualization III , Springer, 2014, pp. 249–262.
date_created: 2022-03-18T13:05:39Z
date_published: 2014-03-19T00:00:00Z
date_updated: 2023-09-05T14:13:16Z
day: '19'
department:
- _id: HeEd
doi: 10.1007/978-3-319-04099-8_16
language:
- iso: eng
month: '03'
oa_version: None
page: 249-262
publication: 'Topological Methods in Data Analysis and Visualization III '
publication_identifier:
eisbn:
- '9783319040998'
eissn:
- 2197-666X
isbn:
- '9783319040981'
issn:
- 1612-3786
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Visualization of two-dimensional symmetric positive definite tensor fields
using the heat kernel signature
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2014'
...
---
_id: '10892'
abstract:
- lang: eng
text: "In this paper, we introduce planar matchings on directed pseudo-line arrangements,
which yield a planar set of pseudo-line segments such that only matching-partners
are adjacent. By translating the planar matching problem into a corresponding
stable roommates problem we show that such matchings always exist.\r\nUsing our
new framework, we establish, for the first time, a complete, rigorous definition
of weighted straight skeletons, which are based on a so-called wavefront propagation
process. We present a generalized and unified approach to treat structural changes
in the wavefront that focuses on the restoration of weak planarity by finding
planar matchings."
acknowledgement: 'T. Biedl was supported by NSERC and the Ross and Muriel Cheriton
Fellowship. P. Palfrader was supported by Austrian Science Fund (FWF): P25816-N15.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Therese
full_name: Biedl, Therese
last_name: Biedl
- first_name: Stefan
full_name: Huber, Stefan
id: 4700A070-F248-11E8-B48F-1D18A9856A87
last_name: Huber
orcid: 0000-0002-8871-5814
- first_name: Peter
full_name: Palfrader, Peter
last_name: Palfrader
citation:
ama: 'Biedl T, Huber S, Palfrader P. Planar matchings for weighted straight skeletons.
In: 25th International Symposium, ISAAC 2014. Vol 8889. Springer Nature;
2014:117-127. doi:10.1007/978-3-319-13075-0_10'
apa: 'Biedl, T., Huber, S., & Palfrader, P. (2014). Planar matchings for weighted
straight skeletons. In 25th International Symposium, ISAAC 2014 (Vol. 8889,
pp. 117–127). Jeonju, Korea: Springer Nature. https://doi.org/10.1007/978-3-319-13075-0_10'
chicago: Biedl, Therese, Stefan Huber, and Peter Palfrader. “Planar Matchings for
Weighted Straight Skeletons.” In 25th International Symposium, ISAAC 2014,
8889:117–27. Springer Nature, 2014. https://doi.org/10.1007/978-3-319-13075-0_10.
ieee: T. Biedl, S. Huber, and P. Palfrader, “Planar matchings for weighted straight
skeletons,” in 25th International Symposium, ISAAC 2014, Jeonju, Korea,
2014, vol. 8889, pp. 117–127.
ista: 'Biedl T, Huber S, Palfrader P. 2014. Planar matchings for weighted straight
skeletons. 25th International Symposium, ISAAC 2014. ISAAC: International Symposium
on Algorithms and Computation, LNCS, vol. 8889, 117–127.'
mla: Biedl, Therese, et al. “Planar Matchings for Weighted Straight Skeletons.”
25th International Symposium, ISAAC 2014, vol. 8889, Springer Nature, 2014,
pp. 117–27, doi:10.1007/978-3-319-13075-0_10.
short: T. Biedl, S. Huber, P. Palfrader, in:, 25th International Symposium, ISAAC
2014, Springer Nature, 2014, pp. 117–127.
conference:
end_date: 2014-12-17
location: Jeonju, Korea
name: 'ISAAC: International Symposium on Algorithms and Computation'
start_date: 2014-12-15
date_created: 2022-03-21T07:09:03Z
date_published: 2014-11-08T00:00:00Z
date_updated: 2023-02-23T12:20:55Z
day: '08'
department:
- _id: HeEd
doi: 10.1007/978-3-319-13075-0_10
intvolume: ' 8889'
language:
- iso: eng
month: '11'
oa_version: None
page: 117-127
publication: 25th International Symposium, ISAAC 2014
publication_identifier:
eisbn:
- '9783319130750'
eissn:
- 1611-3349
isbn:
- '9783319130743'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '481'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Planar matchings for weighted straight skeletons
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8889
year: '2014'
...
---
_id: '10893'
abstract:
- lang: eng
text: Saddle periodic orbits are an essential and stable part of the topological
skeleton of a 3D vector field. Nevertheless, there is currently no efficient algorithm
to robustly extract these features. In this chapter, we present a novel technique
to extract saddle periodic orbits. Exploiting the analytic properties of such
an orbit, we propose a scalar measure based on the finite-time Lyapunov exponent
(FTLE) that indicates its presence. Using persistent homology, we can then extract
the robust cycles of this field. These cycles thereby represent the saddle periodic
orbits of the given vector field. We discuss the different existing FTLE approximation
schemes regarding their applicability to this specific problem and propose an
adapted version of FTLE called Normalized Velocity Separation. Finally, we evaluate
our method using simple analytic vector field data.
acknowledgement: First, we thank the reviewers of this paper for their ideas and critical
comments. In addition, we thank Ronny Peikert and Filip Sadlo for a fruitful discussions.
This research is supported by the European Commission under the TOPOSYS project
FP7-ICT-318493-STREP, the European Social Fund (ESF App. No. 100098251), and the
European Science Foundation under the ACAT Research Network Program.
article_processing_charge: No
author:
- first_name: Jens
full_name: Kasten, Jens
last_name: Kasten
- first_name: Jan
full_name: Reininghaus, Jan
id: 4505473A-F248-11E8-B48F-1D18A9856A87
last_name: Reininghaus
- first_name: Wieland
full_name: Reich, Wieland
last_name: Reich
- first_name: Gerik
full_name: Scheuermann, Gerik
last_name: Scheuermann
citation:
ama: 'Kasten J, Reininghaus J, Reich W, Scheuermann G. Toward the extraction of
saddle periodic orbits. In: Bremer P-T, Hotz I, Pascucci V, Peikert R, eds. Topological
Methods in Data Analysis and Visualization III . Vol 1. Mathematics and Visualization.
Cham: Springer; 2014:55-69. doi:10.1007/978-3-319-04099-8_4'
apa: 'Kasten, J., Reininghaus, J., Reich, W., & Scheuermann, G. (2014). Toward
the extraction of saddle periodic orbits. In P.-T. Bremer, I. Hotz, V. Pascucci,
& R. Peikert (Eds.), Topological Methods in Data Analysis and Visualization
III (Vol. 1, pp. 55–69). Cham: Springer. https://doi.org/10.1007/978-3-319-04099-8_4'
chicago: 'Kasten, Jens, Jan Reininghaus, Wieland Reich, and Gerik Scheuermann. “Toward
the Extraction of Saddle Periodic Orbits.” In Topological Methods in Data Analysis
and Visualization III , edited by Peer-Timo Bremer, Ingrid Hotz, Valerio Pascucci,
and Ronald Peikert, 1:55–69. Mathematics and Visualization. Cham: Springer, 2014.
https://doi.org/10.1007/978-3-319-04099-8_4.'
ieee: 'J. Kasten, J. Reininghaus, W. Reich, and G. Scheuermann, “Toward the extraction
of saddle periodic orbits,” in Topological Methods in Data Analysis and Visualization
III , vol. 1, P.-T. Bremer, I. Hotz, V. Pascucci, and R. Peikert, Eds. Cham:
Springer, 2014, pp. 55–69.'
ista: 'Kasten J, Reininghaus J, Reich W, Scheuermann G. 2014.Toward the extraction
of saddle periodic orbits. In: Topological Methods in Data Analysis and Visualization
III . vol. 1, 55–69.'
mla: Kasten, Jens, et al. “Toward the Extraction of Saddle Periodic Orbits.” Topological
Methods in Data Analysis and Visualization III , edited by Peer-Timo Bremer
et al., vol. 1, Springer, 2014, pp. 55–69, doi:10.1007/978-3-319-04099-8_4.
short: J. Kasten, J. Reininghaus, W. Reich, G. Scheuermann, in:, P.-T. Bremer, I.
Hotz, V. Pascucci, R. Peikert (Eds.), Topological Methods in Data Analysis and
Visualization III , Springer, Cham, 2014, pp. 55–69.
date_created: 2022-03-21T07:11:23Z
date_published: 2014-03-19T00:00:00Z
date_updated: 2022-06-21T12:01:47Z
day: '19'
department:
- _id: HeEd
doi: 10.1007/978-3-319-04099-8_4
ec_funded: 1
editor:
- first_name: Peer-Timo
full_name: Bremer, Peer-Timo
last_name: Bremer
- first_name: Ingrid
full_name: Hotz, Ingrid
last_name: Hotz
- first_name: Valerio
full_name: Pascucci, Valerio
last_name: Pascucci
- first_name: Ronald
full_name: Peikert, Ronald
last_name: Peikert
intvolume: ' 1'
language:
- iso: eng
month: '03'
oa_version: None
page: 55-69
place: Cham
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
publication: 'Topological Methods in Data Analysis and Visualization III '
publication_identifier:
eisbn:
- '9783319040998'
eissn:
- 2197-666X
isbn:
- '9783319040981'
issn:
- 1612-3786
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
series_title: Mathematics and Visualization
status: public
title: Toward the extraction of saddle periodic orbits
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 1
year: '2014'
...
---
_id: '10894'
abstract:
- lang: eng
text: PHAT is a C++ library for the computation of persistent homology by matrix
reduction. We aim for a simple generic design that decouples algorithms from data
structures without sacrificing efficiency or user-friendliness. This makes PHAT
a versatile platform for experimenting with algorithmic ideas and comparing them
to state of the art implementations.
article_processing_charge: No
author:
- first_name: Ulrich
full_name: Bauer, Ulrich
id: 2ADD483A-F248-11E8-B48F-1D18A9856A87
last_name: Bauer
orcid: 0000-0002-9683-0724
- first_name: Michael
full_name: Kerber, Michael
last_name: Kerber
- first_name: Jan
full_name: Reininghaus, Jan
id: 4505473A-F248-11E8-B48F-1D18A9856A87
last_name: Reininghaus
- first_name: Hubert
full_name: Wagner, Hubert
last_name: Wagner
citation:
ama: 'Bauer U, Kerber M, Reininghaus J, Wagner H. PHAT – Persistent Homology Algorithms
Toolbox. In: ICMS 2014: International Congress on Mathematical Software.
Vol 8592. LNCS. Berlin, Heidelberg: Springer Berlin Heidelberg; 2014:137-143.
doi:10.1007/978-3-662-44199-2_24'
apa: 'Bauer, U., Kerber, M., Reininghaus, J., & Wagner, H. (2014). PHAT – Persistent
Homology Algorithms Toolbox. In ICMS 2014: International Congress on Mathematical
Software (Vol. 8592, pp. 137–143). Berlin, Heidelberg: Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-662-44199-2_24'
chicago: 'Bauer, Ulrich, Michael Kerber, Jan Reininghaus, and Hubert Wagner. “PHAT
– Persistent Homology Algorithms Toolbox.” In ICMS 2014: International Congress
on Mathematical Software, 8592:137–43. LNCS. Berlin, Heidelberg: Springer
Berlin Heidelberg, 2014. https://doi.org/10.1007/978-3-662-44199-2_24.'
ieee: 'U. Bauer, M. Kerber, J. Reininghaus, and H. Wagner, “PHAT – Persistent Homology
Algorithms Toolbox,” in ICMS 2014: International Congress on Mathematical Software,
Seoul, South Korea, 2014, vol. 8592, pp. 137–143.'
ista: 'Bauer U, Kerber M, Reininghaus J, Wagner H. 2014. PHAT – Persistent Homology
Algorithms Toolbox. ICMS 2014: International Congress on Mathematical Software.
ICMS: International Congress on Mathematical SoftwareLNCS vol. 8592, 137–143.'
mla: 'Bauer, Ulrich, et al. “PHAT – Persistent Homology Algorithms Toolbox.” ICMS
2014: International Congress on Mathematical Software, vol. 8592, Springer
Berlin Heidelberg, 2014, pp. 137–43, doi:10.1007/978-3-662-44199-2_24.'
short: 'U. Bauer, M. Kerber, J. Reininghaus, H. Wagner, in:, ICMS 2014: International
Congress on Mathematical Software, Springer Berlin Heidelberg, Berlin, Heidelberg,
2014, pp. 137–143.'
conference:
end_date: 2014-08-09
location: Seoul, South Korea
name: 'ICMS: International Congress on Mathematical Software'
start_date: 2014-08-05
date_created: 2022-03-21T07:12:16Z
date_published: 2014-09-01T00:00:00Z
date_updated: 2023-09-20T09:42:40Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/978-3-662-44199-2_24
intvolume: ' 8592'
language:
- iso: eng
month: '09'
oa_version: None
page: 137-143
place: Berlin, Heidelberg
publication: 'ICMS 2014: International Congress on Mathematical Software'
publication_identifier:
eisbn:
- '9783662441992'
eissn:
- 1611-3349
isbn:
- '9783662441985'
issn:
- 0302-9743
publication_status: published
publisher: Springer Berlin Heidelberg
quality_controlled: '1'
related_material:
record:
- id: '1433'
relation: later_version
status: public
scopus_import: '1'
series_title: LNCS
status: public
title: PHAT – Persistent Homology Algorithms Toolbox
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 8592
year: '2014'
...
---
_id: '2082'
abstract:
- lang: eng
text: 'NMAC is a mode of operation which turns a fixed input-length keyed hash function
f into a variable input-length function. A practical single-key variant of NMAC
called HMAC is a very popular and widely deployed message authentication code
(MAC). Security proofs and attacks for NMAC can typically be lifted to HMAC. NMAC
was introduced by Bellare, Canetti and Krawczyk [Crypto''96], who proved it to
be a secure pseudorandom function (PRF), and thus also a MAC, assuming that (1)
f is a PRF and (2) the function we get when cascading f is weakly collision-resistant.
Unfortunately, HMAC is typically instantiated with cryptographic hash functions
like MD5 or SHA-1 for which (2) has been found to be wrong. To restore the provable
guarantees for NMAC, Bellare [Crypto''06] showed its security based solely on
the assumption that f is a PRF, albeit via a non-uniform reduction. - Our first
contribution is a simpler and uniform proof for this fact: If f is an ε-secure
PRF (against q queries) and a δ-non-adaptively secure PRF (against q queries),
then NMAC f is an (ε+ℓqδ)-secure PRF against q queries of length at most ℓ blocks
each. - We then show that this ε+ℓqδ bound is basically tight. For the most interesting
case where ℓqδ ≥ ε we prove this by constructing an f for which an attack with
advantage ℓqδ exists. This also violates the bound O(ℓε) on the PRF-security of
NMAC recently claimed by Koblitz and Menezes. - Finally, we analyze the PRF-security
of a modification of NMAC called NI [An and Bellare, Crypto''99] that differs
mainly by using a compression function with an additional keying input. This avoids
the constant rekeying on multi-block messages in NMAC and allows for a security
proof starting by the standard switch from a PRF to a random function, followed
by an information-theoretic analysis. We carry out such an analysis, obtaining
a tight ℓq2/2 c bound for this step, improving over the trivial bound of ℓ2q2/2c.
The proof borrows combinatorial techniques originally developed for proving the
security of CBC-MAC [Bellare et al., Crypto''05].'
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: Michal
full_name: Rybar, Michal
id: 2B3E3DE8-F248-11E8-B48F-1D18A9856A87
last_name: Rybar
citation:
ama: 'Gazi P, Pietrzak KZ, Rybar M. The exact PRF-security of NMAC and HMAC. In:
Garay J, Gennaro R, eds. Vol 8616. Springer; 2014:113-130. doi:10.1007/978-3-662-44371-2_7'
apa: 'Gazi, P., Pietrzak, K. Z., & Rybar, M. (2014). The exact PRF-security
of NMAC and HMAC. In J. Garay & R. Gennaro (Eds.) (Vol. 8616, pp. 113–130).
Presented at the CRYPTO: International Cryptology Conference, Santa Barbara, USA:
Springer. https://doi.org/10.1007/978-3-662-44371-2_7'
chicago: Gazi, Peter, Krzysztof Z Pietrzak, and Michal Rybar. “The Exact PRF-Security
of NMAC and HMAC.” edited by Juan Garay and Rosario Gennaro, 8616:113–30. Springer,
2014. https://doi.org/10.1007/978-3-662-44371-2_7.
ieee: 'P. Gazi, K. Z. Pietrzak, and M. Rybar, “The exact PRF-security of NMAC and
HMAC,” presented at the CRYPTO: International Cryptology Conference, Santa Barbara,
USA, 2014, vol. 8616, no. 1, pp. 113–130.'
ista: 'Gazi P, Pietrzak KZ, Rybar M. 2014. The exact PRF-security of NMAC and HMAC.
CRYPTO: International Cryptology Conference, LNCS, vol. 8616, 113–130.'
mla: Gazi, Peter, et al. The Exact PRF-Security of NMAC and HMAC. Edited
by Juan Garay and Rosario Gennaro, vol. 8616, no. 1, Springer, 2014, pp. 113–30,
doi:10.1007/978-3-662-44371-2_7.
short: P. Gazi, K.Z. Pietrzak, M. Rybar, in:, J. Garay, R. Gennaro (Eds.), Springer,
2014, pp. 113–130.
conference:
end_date: 2014-08-21
location: Santa Barbara, USA
name: 'CRYPTO: International Cryptology Conference'
start_date: 2014-08-17
date_created: 2018-12-11T11:55:36Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2023-09-07T12:02:27Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: KrPi
doi: 10.1007/978-3-662-44371-2_7
ec_funded: 1
editor:
- first_name: Juan
full_name: Garay, Juan
last_name: Garay
- first_name: Rosario
full_name: Gennaro, Rosario
last_name: Gennaro
file:
- access_level: open_access
checksum: dab6ab36a5f6af94f2b597e6404ed11d
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:17Z
date_updated: 2020-07-14T12:45:28Z
file_id: '4999'
file_name: IST-2016-682-v1+1_578.pdf
file_size: 492310
relation: main_file
file_date_updated: 2020-07-14T12:45:28Z
has_accepted_license: '1'
intvolume: ' 8616'
issue: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 113 - 130
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: '4955'
pubrep_id: '682'
quality_controlled: '1'
related_material:
record:
- id: '838'
relation: dissertation_contains
status: public
status: public
title: The exact PRF-security of NMAC and HMAC
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8616
year: '2014'
...
---
_id: '2083'
abstract:
- lang: eng
text: Understanding the effects of sex and migration on adaptation to novel environments
remains a key problem in evolutionary biology. Using a single-cell alga Chlamydomonas
reinhardtii, we investigated how sex and migration affected rates of evolutionary
rescue in a sink environment, and subsequent changes in fitness following evolutionary
rescue. We show that sex and migration affect both the rate of evolutionary rescue
and subsequent adaptation. However, their combined effects change as the populations
adapt to a sink habitat. Both sex and migration independently increased rates
of evolutionary rescue, but the effect of sex on subsequent fitness improvements,
following initial rescue, changed with migration, as sex was beneficial in the
absence of migration but constraining adaptation when combined with migration.
These results suggest that sex and migration are beneficial during the initial
stages of adaptation, but can become detrimental as the population adapts to its
environment.
acknowledgement: The authors are grateful to the Leverhulme Trust (F/00 215/AW) for
funding this work.
article_processing_charge: No
article_type: original
author:
- first_name: Mato
full_name: Lagator, Mato
id: 345D25EC-F248-11E8-B48F-1D18A9856A87
last_name: Lagator
- first_name: Andrew
full_name: Morgan, Andrew
last_name: Morgan
- first_name: Paul
full_name: Neve, Paul
last_name: Neve
- first_name: Nick
full_name: Colegrave, Nick
last_name: Colegrave
citation:
ama: Lagator M, Morgan A, Neve P, Colegrave N. Role of sex and migration in adaptation
to sink environments. Evolution. 2014;68(8):2296-2305. doi:10.1111/evo.12440
apa: Lagator, M., Morgan, A., Neve, P., & Colegrave, N. (2014). Role of sex
and migration in adaptation to sink environments. Evolution. Wiley. https://doi.org/10.1111/evo.12440
chicago: Lagator, Mato, Andrew Morgan, Paul Neve, and Nick Colegrave. “Role of Sex
and Migration in Adaptation to Sink Environments.” Evolution. Wiley, 2014.
https://doi.org/10.1111/evo.12440.
ieee: M. Lagator, A. Morgan, P. Neve, and N. Colegrave, “Role of sex and migration
in adaptation to sink environments,” Evolution, vol. 68, no. 8. Wiley,
pp. 2296–2305, 2014.
ista: Lagator M, Morgan A, Neve P, Colegrave N. 2014. Role of sex and migration
in adaptation to sink environments. Evolution. 68(8), 2296–2305.
mla: Lagator, Mato, et al. “Role of Sex and Migration in Adaptation to Sink Environments.”
Evolution, vol. 68, no. 8, Wiley, 2014, pp. 2296–305, doi:10.1111/evo.12440.
short: M. Lagator, A. Morgan, P. Neve, N. Colegrave, Evolution 68 (2014) 2296–2305.
date_created: 2018-12-11T11:55:36Z
date_published: 2014-04-25T00:00:00Z
date_updated: 2023-02-23T14:06:51Z
day: '25'
ddc:
- '570'
department:
- _id: CaGu
doi: 10.1111/evo.12440
file:
- access_level: open_access
checksum: 8d459b07e4a11bb5fde92d969184fe48
content_type: application/pdf
creator: dernst
date_created: 2020-05-14T16:40:31Z
date_updated: 2020-07-14T12:45:28Z
file_id: '7845'
file_name: 2014_Evolution_Lagator.pdf
file_size: 467254
relation: main_file
file_date_updated: 2020-07-14T12:45:28Z
has_accepted_license: '1'
intvolume: ' 68'
issue: '8'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 2296 - 2305
publication: Evolution
publication_status: published
publisher: Wiley
publist_id: '4954'
quality_controlled: '1'
related_material:
record:
- id: '9747'
relation: research_data
status: public
scopus_import: 1
status: public
title: Role of sex and migration in adaptation to sink environments
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 68
year: '2014'
...
---
_id: '2084'
abstract:
- lang: eng
text: Receptor tyrosine kinases (RTKs) are a large family of cell surface receptors
that sense growth factors and hormones and regulate a variety of cell behaviours
in health and disease. Contactless activation of RTKs with spatial and temporal
precision is currently not feasible. Here, we generated RTKs that are insensitive
to endogenous ligands but can be selectively activated by low-intensity blue light.
We screened light-oxygen-voltage (LOV)-sensing domains for their ability to activate
RTKs by light-activated dimerization. Incorporation of LOV domains found in aureochrome
photoreceptors of stramenopiles resulted in robust activation of the fibroblast
growth factor receptor 1 (FGFR1), epidermal growth factor receptor (EGFR) and
rearranged during transfection (RET). In human cancer and endothelial cells, light
induced cellular signalling with spatial and temporal precision. Furthermore,
light faithfully mimicked complex mitogenic and morphogenic cell behaviour induced
by growth factors. RTKs under optical control (Opto-RTKs) provide a powerful optogenetic
approach to actuate cellular signals and manipulate cell behaviour.
acknowledgement: European Union Seventh Framework Programme; Human Frontier Science
Program; Oesterreichische Nationalbank Anniversary Fund 14211; Austrian Research
Promotion Agency; FemTech
author:
- first_name: Michael
full_name: Grusch, Michael
last_name: Grusch
- first_name: Karin
full_name: Schelch, Karin
last_name: Schelch
- first_name: Robert
full_name: Riedler, Robert
last_name: Riedler
- 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: Christopher
full_name: Differ, Christopher
last_name: Differ
- first_name: Walter
full_name: Berger, Walter
last_name: Berger
- 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: Harald L
full_name: Janovjak, Harald L
id: 33BA6C30-F248-11E8-B48F-1D18A9856A87
last_name: Janovjak
orcid: 0000-0002-8023-9315
citation:
ama: Grusch M, Schelch K, Riedler R, et al. Spatio-temporally precise activation
of engineered receptor tyrosine kinases by light. EMBO Journal. 2014;33(15):1713-1726.
doi:10.15252/embj.201387695
apa: Grusch, M., Schelch, K., Riedler, R., Gschaider-Reichhart, E., Differ, C.,
Berger, W., … Janovjak, H. L. (2014). Spatio-temporally precise activation of
engineered receptor tyrosine kinases by light. EMBO Journal. Wiley-Blackwell.
https://doi.org/10.15252/embj.201387695
chicago: Grusch, Michael, Karin Schelch, Robert Riedler, Eva Gschaider-Reichhart,
Christopher Differ, Walter Berger, Álvaro Inglés Prieto, and Harald L Janovjak.
“Spatio-Temporally Precise Activation of Engineered Receptor Tyrosine Kinases
by Light.” EMBO Journal. Wiley-Blackwell, 2014. https://doi.org/10.15252/embj.201387695.
ieee: M. Grusch et al., “Spatio-temporally precise activation of engineered
receptor tyrosine kinases by light,” EMBO Journal, vol. 33, no. 15. Wiley-Blackwell,
pp. 1713–1726, 2014.
ista: Grusch M, Schelch K, Riedler R, Gschaider-Reichhart E, Differ C, Berger W,
Inglés Prieto Á, Janovjak HL. 2014. Spatio-temporally precise activation of engineered
receptor tyrosine kinases by light. EMBO Journal. 33(15), 1713–1726.
mla: Grusch, Michael, et al. “Spatio-Temporally Precise Activation of Engineered
Receptor Tyrosine Kinases by Light.” EMBO Journal, vol. 33, no. 15, Wiley-Blackwell,
2014, pp. 1713–26, doi:10.15252/embj.201387695.
short: M. Grusch, K. Schelch, R. Riedler, E. Gschaider-Reichhart, C. Differ, W.
Berger, Á. Inglés Prieto, H.L. Janovjak, EMBO Journal 33 (2014) 1713–1726.
date_created: 2018-12-11T11:55:37Z
date_published: 2014-07-01T00:00:00Z
date_updated: 2023-09-07T12:49:09Z
day: '01'
department:
- _id: HaJa
doi: 10.15252/embj.201387695
intvolume: ' 33'
issue: '15'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4194103/
month: '07'
oa: 1
oa_version: Submitted Version
page: 1713 - 1726
publication: EMBO Journal
publication_status: published
publisher: Wiley-Blackwell
publist_id: '4953'
quality_controlled: '1'
related_material:
record:
- id: '418'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Spatio-temporally precise activation of engineered receptor tyrosine kinases
by light
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 33
year: '2014'
...
---
_id: '2086'
abstract:
- lang: eng
text: Pathogens may gain a fitness advantage through manipulation of the behaviour
of their hosts. Likewise, host behavioural changes can be a defence mechanism,
counteracting the impact of pathogens on host fitness. We apply harmonic radar
technology to characterize the impact of an emerging pathogen - Nosema ceranae
(Microsporidia) - on honeybee (Apis mellifera) flight and orientation performance
in the field. Honeybees are the most important commercial pollinators. Emerging
diseases have been proposed to play a prominent role in colony decline, partly
through sub-lethal behavioural manipulation of their hosts. We found that homing
success was significantly reduced in diseased (65.8%) versus healthy foragers
(92.5%). Although lost bees had significantly reduced continuous flight times
and prolonged resting times, other flight characteristics and navigational abilities
showed no significant difference between infected and non-infected bees. Our results
suggest that infected bees express normal flight characteristics but are constrained
in their homing ability, potentially compromising the colony by reducing its resource
inputs, but also counteracting the intra-colony spread of infection. We provide
the first high-resolution analysis of sub-lethal effects of an emerging disease
on insect flight behaviour. The potential causes and the implications for both
host and parasite are discussed.
acknowledgement: This study was funded jointly by a grant from BBSRC, Defra, NERC,
the Scottish Government and the Wellcome Trust, under the Insect Pollinators Initiative
(grant numbers BB/I00097/1 and BB/I000100/1). Rothamsted Research is a national
institute of bioscience strategically funded by the UK Biotechnology and Biological
Sciences Research Council (BBSRC).
article_number: e103989
author:
- first_name: Stephan
full_name: Wolf, Stephan
last_name: Wolf
- first_name: Dino
full_name: Mcmahon, Dino
last_name: Mcmahon
- first_name: Ka
full_name: Lim, Ka
last_name: Lim
- first_name: Christopher
full_name: Pull, Christopher
id: 3C7F4840-F248-11E8-B48F-1D18A9856A87
last_name: Pull
orcid: 0000-0003-1122-3982
- first_name: Suzanne
full_name: Clark, Suzanne
last_name: Clark
- first_name: Robert
full_name: Paxton, Robert
last_name: Paxton
- first_name: Juliet
full_name: Osborne, Juliet
last_name: Osborne
citation:
ama: 'Wolf S, Mcmahon D, Lim K, et al. So near and yet so far: Harmonic radar reveals
reduced homing ability of Nosema infected honeybees. PLoS One. 2014;9(8).
doi:10.1371/journal.pone.0103989'
apa: 'Wolf, S., Mcmahon, D., Lim, K., Pull, C., Clark, S., Paxton, R., & Osborne,
J. (2014). So near and yet so far: Harmonic radar reveals reduced homing ability
of Nosema infected honeybees. PLoS One. Public Library of Science. https://doi.org/10.1371/journal.pone.0103989'
chicago: 'Wolf, Stephan, Dino Mcmahon, Ka Lim, Christopher Pull, Suzanne Clark,
Robert Paxton, and Juliet Osborne. “So near and yet so Far: Harmonic Radar Reveals
Reduced Homing Ability of Nosema Infected Honeybees.” PLoS One. Public
Library of Science, 2014. https://doi.org/10.1371/journal.pone.0103989.'
ieee: 'S. Wolf et al., “So near and yet so far: Harmonic radar reveals reduced
homing ability of Nosema infected honeybees,” PLoS One, vol. 9, no. 8.
Public Library of Science, 2014.'
ista: 'Wolf S, Mcmahon D, Lim K, Pull C, Clark S, Paxton R, Osborne J. 2014. So
near and yet so far: Harmonic radar reveals reduced homing ability of Nosema infected
honeybees. PLoS One. 9(8), e103989.'
mla: 'Wolf, Stephan, et al. “So near and yet so Far: Harmonic Radar Reveals Reduced
Homing Ability of Nosema Infected Honeybees.” PLoS One, vol. 9, no. 8,
e103989, Public Library of Science, 2014, doi:10.1371/journal.pone.0103989.'
short: S. Wolf, D. Mcmahon, K. Lim, C. Pull, S. Clark, R. Paxton, J. Osborne, PLoS
One 9 (2014).
date_created: 2018-12-11T11:55:37Z
date_published: 2014-08-06T00:00:00Z
date_updated: 2023-02-23T14:11:56Z
day: '06'
ddc:
- '570'
department:
- _id: SyCr
doi: 10.1371/journal.pone.0103989
file:
- access_level: open_access
checksum: 2fc62c6739eada4bddf026afbae669db
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:55Z
date_updated: 2020-07-14T12:45:28Z
file_id: '5042'
file_name: IST-2016-437-v1+1_journal.pone.0103989.pdf
file_size: 1013386
relation: main_file
file_date_updated: 2020-07-14T12:45:28Z
has_accepted_license: '1'
intvolume: ' 9'
issue: '8'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
publication: PLoS One
publication_status: published
publisher: Public Library of Science
publist_id: '4949'
pubrep_id: '437'
quality_controlled: '1'
related_material:
record:
- id: '9888'
relation: research_data
status: public
scopus_import: 1
status: public
title: 'So near and yet so far: Harmonic radar reveals reduced homing ability of Nosema
infected honeybees'
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: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 9
year: '2014'
...
---
_id: '2141'
abstract:
- lang: eng
text: The computation of the winning set for Büchi objectives in alternating games
on graphs is a central problem in computer-aided verification with a large number
of applications. The long-standing best known upper bound for solving the problem
is Õ(n ⋅ m), where n is the number of vertices and m is the number of edges in
the graph. We are the first to break the Õ(n ⋅ m) boundary by presenting a new
technique that reduces the running time to O(n2). This bound also leads to O(n2)-time
algorithms for computing the set of almost-sure winning vertices for Büchi objectives
(1) in alternating games with probabilistic transitions (improving an earlier
bound of Õ(n ⋅ m)), (2) in concurrent graph games with constant actions (improving
an earlier bound of O(n3)), and (3) in Markov decision processes (improving for
m>n4/3 an earlier bound of O(m ⋅ √m)). We then show how to maintain the winning
set for Büchi objectives in alternating games under a sequence of edge insertions
or a sequence of edge deletions in O(n) amortized time per operation. Our algorithms
are the first dynamic algorithms for this problem. We then consider another core
graph theoretic problem in verification of probabilistic systems, namely computing
the maximal end-component decomposition of a graph. We present two improved static
algorithms for the maximal end-component decomposition problem. Our first algorithm
is an O(m ⋅ √m)-time algorithm, and our second algorithm is an O(n2)-time algorithm
which is obtained using the same technique as for alternating Büchi games. Thus,
we obtain an O(min &lcu;m ⋅ √m,n2})-time algorithm improving the long-standing
O(n ⋅ m) time bound. Finally, we show how to maintain the maximal end-component
decomposition of a graph under a sequence of edge insertions or a sequence of
edge deletions in O(n) amortized time per edge deletion, and O(m) worst-case time
per edge insertion. Again, our algorithms are the first dynamic algorithms for
this problem.
article_number: a15
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: Chatterjee K, Henzinger MH. Efficient and dynamic algorithms for alternating
Büchi games and maximal end-component decomposition. Journal of the ACM.
2014;61(3). doi:10.1145/2597631
apa: Chatterjee, K., & Henzinger, M. H. (2014). Efficient and dynamic algorithms
for alternating Büchi games and maximal end-component decomposition. Journal
of the ACM. ACM. https://doi.org/10.1145/2597631
chicago: Chatterjee, Krishnendu, and Monika H Henzinger. “Efficient and Dynamic
Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition.”
Journal of the ACM. ACM, 2014. https://doi.org/10.1145/2597631.
ieee: K. Chatterjee and M. H. Henzinger, “Efficient and dynamic algorithms for alternating
Büchi games and maximal end-component decomposition,” Journal of the ACM,
vol. 61, no. 3. ACM, 2014.
ista: Chatterjee K, Henzinger MH. 2014. Efficient and dynamic algorithms for alternating
Büchi games and maximal end-component decomposition. Journal of the ACM. 61(3),
a15.
mla: Chatterjee, Krishnendu, and Monika H. Henzinger. “Efficient and Dynamic Algorithms
for Alternating Büchi Games and Maximal End-Component Decomposition.” Journal
of the ACM, vol. 61, no. 3, a15, ACM, 2014, doi:10.1145/2597631.
short: K. Chatterjee, M.H. Henzinger, Journal of the ACM 61 (2014).
date_created: 2018-12-11T11:55:57Z
date_published: 2014-05-01T00:00:00Z
date_updated: 2025-06-02T08:53:48Z
day: '01'
department:
- _id: KrCh
doi: 10.1145/2597631
ec_funded: 1
intvolume: ' 61'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprints.cs.univie.ac.at/3933/
month: '05'
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: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Journal of the ACM
publication_status: published
publisher: ACM
publist_id: '4883'
quality_controlled: '1'
related_material:
record:
- id: '3165'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Efficient and dynamic algorithms for alternating Büchi games and maximal end-component
decomposition
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 61
year: '2014'
...
---
_id: '2153'
abstract:
- lang: eng
text: 'We define a simple, explicit map sending a morphism f : M → N of pointwise
finite dimensional persistence modules to a matching between the barcodes of M
and N. Our main result is that, in a precise sense, the quality of this matching
is tightly controlled by the lengths of the longest intervals in the barcodes
of ker f and coker f . As an immediate corollary, we obtain a new proof of the
algebraic stability theorem for persistence barcodes [5, 9], a fundamental result
in the theory of persistent homology. In contrast to previous proofs, ours shows
explicitly how a δ-interleaving morphism between two persistence modules induces
a δ-matching between the barcodes of the two modules. Our main result also specializes
to a structure theorem for submodules and quotients of persistence modules. Copyright
is held by the owner/author(s).'
author:
- first_name: Ulrich
full_name: Bauer, Ulrich
id: 2ADD483A-F248-11E8-B48F-1D18A9856A87
last_name: Bauer
orcid: 0000-0002-9683-0724
- first_name: Michael
full_name: Lesnick, Michael
last_name: Lesnick
citation:
ama: 'Bauer U, Lesnick M. Induced matchings of barcodes and the algebraic stability
of persistence. In: Proceedings of the Annual Symposium on Computational Geometry.
ACM; 2014:355-364. doi:10.1145/2582112.2582168'
apa: 'Bauer, U., & Lesnick, M. (2014). Induced matchings of barcodes and the
algebraic stability of persistence. In Proceedings of the Annual Symposium
on Computational Geometry (pp. 355–364). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582168'
chicago: Bauer, Ulrich, and Michael Lesnick. “Induced Matchings of Barcodes and
the Algebraic Stability of Persistence.” In Proceedings of the Annual Symposium
on Computational Geometry, 355–64. ACM, 2014. https://doi.org/10.1145/2582112.2582168.
ieee: U. Bauer and M. Lesnick, “Induced matchings of barcodes and the algebraic
stability of persistence,” in Proceedings of the Annual Symposium on Computational
Geometry, Kyoto, Japan, 2014, pp. 355–364.
ista: 'Bauer U, Lesnick M. 2014. Induced matchings of barcodes and the algebraic
stability of persistence. Proceedings of the Annual Symposium on Computational
Geometry. SoCG: Symposium on Computational Geometry, 355–364.'
mla: Bauer, Ulrich, and Michael Lesnick. “Induced Matchings of Barcodes and the
Algebraic Stability of Persistence.” Proceedings of the Annual Symposium on
Computational Geometry, ACM, 2014, pp. 355–64, doi:10.1145/2582112.2582168.
short: U. Bauer, M. Lesnick, in:, Proceedings of the Annual Symposium on Computational
Geometry, ACM, 2014, pp. 355–364.
conference:
end_date: 2014-06-11
location: Kyoto, Japan
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2014-06-08
date_created: 2018-12-11T11:56:01Z
date_published: 2014-06-01T00:00:00Z
date_updated: 2021-01-12T06:55:38Z
day: '01'
department:
- _id: HeEd
doi: 10.1145/2582112.2582168
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1311.3681
month: '06'
oa: 1
oa_version: Submitted Version
page: 355 - 364
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
publication: Proceedings of the Annual Symposium on Computational Geometry
publication_status: published
publisher: ACM
publist_id: '4853'
quality_controlled: '1'
scopus_import: 1
status: public
title: Induced matchings of barcodes and the algebraic stability of persistence
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2154'
abstract:
- lang: eng
text: A result of Boros and Füredi (d = 2) and of Bárány (arbitrary d) asserts that
for every d there exists cd > 0 such that for every n-point set P ⊂ ℝd, some
point of ℝd is covered by at least (Formula presented.) of the d-simplices spanned
by the points of P. The largest possible value of cd has been the subject of ongoing
research. Recently Gromov improved the existing lower bounds considerably by introducing
a new, topological proof method. We provide an exposition of the combinatorial
component of Gromov's approach, in terms accessible to combinatorialists and discrete
geometers, and we investigate the limits of his method. In particular, we give
tighter bounds on the cofilling profiles for the (n - 1)-simplex. These bounds
yield a minor improvement over Gromov's lower bounds on cd for large d, but they
also show that the room for further improvement through the cofilling profiles
alone is quite small. We also prove a slightly better lower bound for c3 by an
approach using an additional structure besides the cofilling profiles. We formulate
a combinatorial extremal problem whose solution might perhaps lead to a tight
lower bound for cd.
acknowledgement: Swiss National Science Foundation (SNF 200021-125309, 200020-138230,
200020-12507)
author:
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Matoušek J, Wagner U. On Gromov’s method of selecting heavily covered points.
Discrete & Computational Geometry. 2014;52(1):1-33. doi:10.1007/s00454-014-9584-7
apa: Matoušek, J., & Wagner, U. (2014). On Gromov’s method of selecting heavily
covered points. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-014-9584-7
chicago: Matoušek, Jiří, and Uli Wagner. “On Gromov’s Method of Selecting Heavily
Covered Points.” Discrete & Computational Geometry. Springer, 2014.
https://doi.org/10.1007/s00454-014-9584-7.
ieee: J. Matoušek and U. Wagner, “On Gromov’s method of selecting heavily covered
points,” Discrete & Computational Geometry, vol. 52, no. 1. Springer,
pp. 1–33, 2014.
ista: Matoušek J, Wagner U. 2014. On Gromov’s method of selecting heavily covered
points. Discrete & Computational Geometry. 52(1), 1–33.
mla: Matoušek, Jiří, and Uli Wagner. “On Gromov’s Method of Selecting Heavily Covered
Points.” Discrete & Computational Geometry, vol. 52, no. 1, Springer,
2014, pp. 1–33, doi:10.1007/s00454-014-9584-7.
short: J. Matoušek, U. Wagner, Discrete & Computational Geometry 52 (2014) 1–33.
date_created: 2018-12-11T11:56:01Z
date_published: 2014-07-01T00:00:00Z
date_updated: 2021-01-12T06:55:38Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-014-9584-7
intvolume: ' 52'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1102.3515
month: '07'
oa: 1
oa_version: Submitted Version
page: 1 - 33
project:
- _id: 25FA3206-B435-11E9-9278-68D0E5697425
grant_number: PP00P2_138948
name: 'Embeddings in Higher Dimensions: Algorithms and Combinatorics'
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '4852'
quality_controlled: '1'
scopus_import: 1
status: public
title: On Gromov's method of selecting heavily covered points
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 52
year: '2014'
...
---
_id: '2155'
abstract:
- lang: eng
text: Given a finite set of points in Rn and a positive radius, we study the Čech,
Delaunay-Čech, alpha, and wrap complexes as instances of a generalized discrete
Morse theory. We prove that the latter three complexes are simple-homotopy equivalent.
Our results have applications in topological data analysis and in the reconstruction
of shapes from sampled data. Copyright is held by the owner/author(s).
acknowledgement: This research is partially supported by ESF under the ACAT Research
Network Programme, and by the Russian Government under mega project 11.G34.31.0053
author:
- first_name: Ulrich
full_name: Bauer, Ulrich
id: 2ADD483A-F248-11E8-B48F-1D18A9856A87
last_name: Bauer
orcid: 0000-0002-9683-0724
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: 'Bauer U, Edelsbrunner H. The morse theory of Čech and Delaunay filtrations.
In: Proceedings of the Annual Symposium on Computational Geometry. ACM;
2014:484-490. doi:10.1145/2582112.2582167'
apa: 'Bauer, U., & Edelsbrunner, H. (2014). The morse theory of Čech and Delaunay
filtrations. In Proceedings of the Annual Symposium on Computational Geometry
(pp. 484–490). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582167'
chicago: Bauer, Ulrich, and Herbert Edelsbrunner. “The Morse Theory of Čech and
Delaunay Filtrations.” In Proceedings of the Annual Symposium on Computational
Geometry, 484–90. ACM, 2014. https://doi.org/10.1145/2582112.2582167.
ieee: U. Bauer and H. Edelsbrunner, “The morse theory of Čech and Delaunay filtrations,”
in Proceedings of the Annual Symposium on Computational Geometry, Kyoto,
Japan, 2014, pp. 484–490.
ista: 'Bauer U, Edelsbrunner H. 2014. The morse theory of Čech and Delaunay filtrations.
Proceedings of the Annual Symposium on Computational Geometry. SoCG: Symposium
on Computational Geometry, 484–490.'
mla: Bauer, Ulrich, and Herbert Edelsbrunner. “The Morse Theory of Čech and Delaunay
Filtrations.” Proceedings of the Annual Symposium on Computational Geometry,
ACM, 2014, pp. 484–90, doi:10.1145/2582112.2582167.
short: U. Bauer, H. Edelsbrunner, in:, Proceedings of the Annual Symposium on Computational
Geometry, ACM, 2014, pp. 484–490.
conference:
end_date: 2014-06-11
location: Kyoto, Japan
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2014-06-08
date_created: 2018-12-11T11:56:01Z
date_published: 2014-06-01T00:00:00Z
date_updated: 2021-01-12T06:55:38Z
day: '01'
department:
- _id: HeEd
doi: 10.1145/2582112.2582167
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1312.1231
month: '06'
oa: 1
oa_version: Submitted Version
page: 484 - 490
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
publication: Proceedings of the Annual Symposium on Computational Geometry
publication_status: published
publisher: ACM
publist_id: '4851'
quality_controlled: '1'
scopus_import: 1
status: public
title: The morse theory of Čech and Delaunay filtrations
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2156'
abstract:
- lang: eng
text: We propose a metric for Reeb graphs, called the functional distortion distance.
Under this distance, the Reeb graph is stable against small changes of input functions.
At the same time, it remains discriminative at differentiating input functions.
In particular, the main result is that the functional distortion distance between
two Reeb graphs is bounded from below by the bottleneck distance between both
the ordinary and extended persistence diagrams for appropriate dimensions. As
an application of our results, we analyze a natural simplification scheme for
Reeb graphs, and show that persistent features in Reeb graph remains persistent
under simplification. Understanding the stability of important features of the
Reeb graph under simplification is an interesting problem on its own right, and
critical to the practical usage of Reeb graphs. Copyright is held by the owner/author(s).
acknowledgement: National Science Foundation under grants CCF-1319406, CCF-1116258.
author:
- first_name: Ulrich
full_name: Bauer, Ulrich
id: 2ADD483A-F248-11E8-B48F-1D18A9856A87
last_name: Bauer
orcid: 0000-0002-9683-0724
- first_name: Xiaoyin
full_name: Ge, Xiaoyin
last_name: Ge
- first_name: Yusu
full_name: Wang, Yusu
last_name: Wang
citation:
ama: 'Bauer U, Ge X, Wang Y. Measuring distance between Reeb graphs. In: Proceedings
of the Annual Symposium on Computational Geometry. ACM; 2014:464-473. doi:10.1145/2582112.2582169'
apa: 'Bauer, U., Ge, X., & Wang, Y. (2014). Measuring distance between Reeb
graphs. In Proceedings of the Annual Symposium on Computational Geometry
(pp. 464–473). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582169'
chicago: Bauer, Ulrich, Xiaoyin Ge, and Yusu Wang. “Measuring Distance between Reeb
Graphs.” In Proceedings of the Annual Symposium on Computational Geometry,
464–73. ACM, 2014. https://doi.org/10.1145/2582112.2582169.
ieee: U. Bauer, X. Ge, and Y. Wang, “Measuring distance between Reeb graphs,” in
Proceedings of the Annual Symposium on Computational Geometry, Kyoto, Japan,
2014, pp. 464–473.
ista: 'Bauer U, Ge X, Wang Y. 2014. Measuring distance between Reeb graphs. Proceedings
of the Annual Symposium on Computational Geometry. SoCG: Symposium on Computational
Geometry, 464–473.'
mla: Bauer, Ulrich, et al. “Measuring Distance between Reeb Graphs.” Proceedings
of the Annual Symposium on Computational Geometry, ACM, 2014, pp. 464–73,
doi:10.1145/2582112.2582169.
short: U. Bauer, X. Ge, Y. Wang, in:, Proceedings of the Annual Symposium on Computational
Geometry, ACM, 2014, pp. 464–473.
conference:
end_date: 2014-06-11
location: Kyoto, Japan
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2014-06-08
date_created: 2018-12-11T11:56:02Z
date_published: 2014-06-01T00:00:00Z
date_updated: 2021-01-12T06:55:39Z
day: '01'
department:
- _id: HeEd
doi: 10.1145/2582112.2582169
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1307.2839
month: '06'
oa: 1
oa_version: Submitted Version
page: 464 - 473
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
publication: Proceedings of the Annual Symposium on Computational Geometry
publication_status: published
publisher: ACM
publist_id: '4850'
quality_controlled: '1'
scopus_import: 1
status: public
title: Measuring distance between Reeb graphs
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2014'
...