---
_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
license: https://creativecommons.org/licenses/by/4.0/
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'
...
---
_id: '2157'
abstract:
- lang: eng
text: 'We show that the following algorithmic problem is decidable: given a 2-dimensional
simplicial complex, can it be embedded (topologically, or equivalently, piecewise
linearly) in ℝ3? By a known reduction, it suffices to decide the embeddability
of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which
allows us to simplify X and recurse, is in proving that if X can be embedded in
S3, then there is also an embedding in which X has a short meridian, i.e., an
essential curve in the boundary of X bounding a disk in S3 nX with length bounded
by a computable function of the number of tetrahedra of X.'
acknowledgement: ERC Advanced Grant No. 267165; Grant GRADR Eurogiga GIG/11/E023 (SNSF-PP00P2-138948);
Swiss National Science Foundation (SNSF-200020-138230).
author:
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Eric
full_name: Sedgwick, Eric
last_name: Sedgwick
- first_name: Martin
full_name: Tancer, Martin
id: 38AC689C-F248-11E8-B48F-1D18A9856A87
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: 'Matoušek J, Sedgwick E, Tancer M, Wagner U. Embeddability in the 3 sphere
is decidable. In: Proceedings of the Annual Symposium on Computational Geometry.
ACM; 2014:78-84. doi:10.1145/2582112.2582137'
apa: 'Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2014). Embeddability
in the 3 sphere is decidable. In Proceedings of the Annual Symposium on Computational
Geometry (pp. 78–84). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582137'
chicago: Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Embeddability
in the 3 Sphere Is Decidable.” In Proceedings of the Annual Symposium on Computational
Geometry, 78–84. ACM, 2014. https://doi.org/10.1145/2582112.2582137.
ieee: J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Embeddability in the
3 sphere is decidable,” in Proceedings of the Annual Symposium on Computational
Geometry, Kyoto, Japan, 2014, pp. 78–84.
ista: 'Matoušek J, Sedgwick E, Tancer M, Wagner U. 2014. Embeddability in the 3
sphere is decidable. Proceedings of the Annual Symposium on Computational Geometry.
SoCG: Symposium on Computational Geometry, 78–84.'
mla: Matoušek, Jiří, et al. “Embeddability in the 3 Sphere Is Decidable.” Proceedings
of the Annual Symposium on Computational Geometry, ACM, 2014, pp. 78–84, doi:10.1145/2582112.2582137.
short: J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, in:, Proceedings of the Annual
Symposium on Computational Geometry, ACM, 2014, pp. 78–84.
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: 2023-09-11T13:38:49Z
day: '01'
department:
- _id: UlWa
doi: 10.1145/2582112.2582137
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1402.0815
month: '06'
oa: 1
oa_version: Submitted Version
page: 78 - 84
publication: Proceedings of the Annual Symposium on Computational Geometry
publication_status: published
publisher: ACM
publist_id: '4849'
quality_controlled: '1'
related_material:
record:
- id: '425'
relation: later_version
status: public
scopus_import: 1
status: public
title: Embeddability in the 3 sphere is decidable
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2158'
abstract:
- lang: eng
text: Directional guidance of migrating cells is relatively well explored in the
reductionist setting of cell culture experiments. Here spatial gradients of chemical
cues as well as gradients of mechanical substrate characteristics prove sufficient
to attract single cells as well as their collectives. How such gradients present
and act in the context of an organism is far less clear. Here we review recent
advances in understanding how guidance cues emerge and operate in the physiological
context.
acknowledgement: This effort was supported by the Intramural Research Program of the
Center for Cancer Research, NCI, National Institutes of Health and the European
Research Council (ERC).
author:
- first_name: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
- first_name: Michael K
full_name: Sixt, Michael K
id: 41E9FBEA-F248-11E8-B48F-1D18A9856A87
last_name: Sixt
orcid: 0000-0002-6620-9179
- first_name: Carole
full_name: Parent, Carole
last_name: Parent
citation:
ama: Majumdar R, Sixt MK, Parent C. New paradigms in the establishment and maintenance
of gradients during directed cell migration. Current Opinion in Cell Biology.
2014;30(1):33-40. doi:10.1016/j.ceb.2014.05.010
apa: Majumdar, R., Sixt, M. K., & Parent, C. (2014). New paradigms in the establishment
and maintenance of gradients during directed cell migration. Current Opinion
in Cell Biology. Elsevier. https://doi.org/10.1016/j.ceb.2014.05.010
chicago: Majumdar, Ritankar, Michael K Sixt, and Carole Parent. “New Paradigms in
the Establishment and Maintenance of Gradients during Directed Cell Migration.”
Current Opinion in Cell Biology. Elsevier, 2014. https://doi.org/10.1016/j.ceb.2014.05.010.
ieee: R. Majumdar, M. K. Sixt, and C. Parent, “New paradigms in the establishment
and maintenance of gradients during directed cell migration,” Current Opinion
in Cell Biology, vol. 30, no. 1. Elsevier, pp. 33–40, 2014.
ista: Majumdar R, Sixt MK, Parent C. 2014. New paradigms in the establishment and
maintenance of gradients during directed cell migration. Current Opinion in Cell
Biology. 30(1), 33–40.
mla: Majumdar, Ritankar, et al. “New Paradigms in the Establishment and Maintenance
of Gradients during Directed Cell Migration.” Current Opinion in Cell Biology,
vol. 30, no. 1, Elsevier, 2014, pp. 33–40, doi:10.1016/j.ceb.2014.05.010.
short: R. Majumdar, M.K. Sixt, C. Parent, Current Opinion in Cell Biology 30 (2014)
33–40.
date_created: 2018-12-11T11:56:03Z
date_published: 2014-10-01T00:00:00Z
date_updated: 2021-01-12T06:55:40Z
day: '01'
department:
- _id: MiSi
doi: 10.1016/j.ceb.2014.05.010
external_id:
pmid:
- '24959970'
intvolume: ' 30'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4177954/
month: '10'
oa: 1
oa_version: Submitted Version
page: 33 - 40
pmid: 1
publication: Current Opinion in Cell Biology
publication_status: published
publisher: Elsevier
publist_id: '4848'
quality_controlled: '1'
scopus_import: 1
status: public
title: New paradigms in the establishment and maintenance of gradients during directed
cell migration
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 30
year: '2014'
...
---
_id: '2159'
abstract:
- lang: eng
text: 'Motivated by topological Tverberg-type problems, we consider multiple (double,
triple, and higher multiplicity) selfintersection points of maps from finite simplicial
complexes (compact polyhedra) into ℝd and study conditions under which such multiple
points can be eliminated. The most classical case is that of embeddings (i.e.,
maps without double points) of a κ-dimensional complex K into ℝ2κ. For this problem,
the work of van Kampen, Shapiro, and Wu provides an efficiently testable necessary
condition for embeddability (namely, vanishing of the van Kampen ob-struction).
For κ ≥ 3, the condition is also sufficient, and yields a polynomial-time algorithm
for deciding embeddability: One starts with an arbitrary map f : K→ℝ2κ, which
generically has finitely many double points; if k ≥ 3 and if the obstruction vanishes
then one can successively remove these double points by local modifications of
the map f. One of the main tools is the famous Whitney trick that permits eliminating
pairs of double points of opposite intersection sign. We are interested in generalizing
this approach to intersection points of higher multiplicity. We call a point y
2 ℝd an r-fold Tverberg point of a map f : Kκ →ℝd if y lies in the intersection
f(σ1)∩. ∩f(σr) of the images of r pairwise disjoint simplices of K. The analogue
of (non-)embeddability that we study is the problem Tverbergκ r→d: Given a κ-dimensional
complex K, does it satisfy a Tverberg-type theorem with parameters r and d, i.e.,
does every map f : K κ → ℝd have an r-fold Tverberg point? Here, we show that
for fixed r, κ and d of the form d = rm and k = (r-1)m, m ≥ 3, there is a polynomial-time
algorithm for deciding this (based on the vanishing of a cohomological obstruction,
as in the case of embeddings). Our main tool is an r-fold analogue of the Whitney
trick: Given r pairwise disjoint simplices of K such that the intersection of
their images contains two r-fold Tverberg points y+ and y- of opposite intersection
sign, we can eliminate y+ and y- by a local isotopy of f. In a subsequent paper,
we plan to develop this further and present a generalization of the classical
Haeiger-Weber Theorem (which yields a necessary and sufficient condition for embeddability
of κ-complexes into ℝd for a wider range of dimensions) to intersection points
of higher multiplicity.'
acknowledgement: Swiss National Science Foundation (Project SNSF-PP00P2-138948)
author:
- first_name: Isaac
full_name: Mabillard, Isaac
id: 32BF9DAA-F248-11E8-B48F-1D18A9856A87
last_name: Mabillard
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Mabillard I, Wagner U. Eliminating Tverberg points, I. An analogue of the
Whitney trick. In: Proceedings of the Annual Symposium on Computational Geometry.
ACM; 2014:171-180. doi:10.1145/2582112.2582134'
apa: 'Mabillard, I., & Wagner, U. (2014). Eliminating Tverberg points, I. An
analogue of the Whitney trick. In Proceedings of the Annual Symposium on Computational
Geometry (pp. 171–180). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582134'
chicago: Mabillard, Isaac, and Uli Wagner. “Eliminating Tverberg Points, I. An Analogue
of the Whitney Trick.” In Proceedings of the Annual Symposium on Computational
Geometry, 171–80. ACM, 2014. https://doi.org/10.1145/2582112.2582134.
ieee: I. Mabillard and U. Wagner, “Eliminating Tverberg points, I. An analogue of
the Whitney trick,” in Proceedings of the Annual Symposium on Computational
Geometry, Kyoto, Japan, 2014, pp. 171–180.
ista: 'Mabillard I, Wagner U. 2014. Eliminating Tverberg points, I. An analogue
of the Whitney trick. Proceedings of the Annual Symposium on Computational Geometry.
SoCG: Symposium on Computational Geometry, 171–180.'
mla: Mabillard, Isaac, and Uli Wagner. “Eliminating Tverberg Points, I. An Analogue
of the Whitney Trick.” Proceedings of the Annual Symposium on Computational
Geometry, ACM, 2014, pp. 171–80, doi:10.1145/2582112.2582134.
short: I. Mabillard, U. Wagner, in:, Proceedings of the Annual Symposium on Computational
Geometry, ACM, 2014, pp. 171–180.
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:03Z
date_published: 2014-06-08T00:00:00Z
date_updated: 2023-09-07T11:56:27Z
day: '08'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1145/2582112.2582134
file:
- access_level: open_access
checksum: 2aae223fee8ffeaf57bbabd8d92b6a2c
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:09:12Z
date_updated: 2020-07-14T12:45:30Z
file_id: '4735'
file_name: IST-2016-534-v1+1_Eliminating_Tverberg_points_I._An_analogue_of_the_Whitney_trick.pdf
file_size: 914396
relation: main_file
file_date_updated: 2020-07-14T12:45:30Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 171 - 180
publication: Proceedings of the Annual Symposium on Computational Geometry
publication_status: published
publisher: ACM
publist_id: '4847'
pubrep_id: '534'
quality_controlled: '1'
related_material:
record:
- id: '1123'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Eliminating Tverberg points, I. An analogue of the Whitney trick
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2160'
abstract:
- lang: eng
text: Transfer learning has received a lot of attention in the machine learning
community over the last years, and several effective algorithms have been developed.
However, relatively little is known about their theoretical properties, especially
in the setting of lifelong learning, where the goal is to transfer information
to tasks for which no data have been observed so far. In this work we study lifelong
learning from a theoretical perspective. Our main result is a PAC-Bayesian generalization
bound that offers a unified view on existing paradigms for transfer learning,
such as the transfer of parameters or the transfer of low-dimensional representations.
We also use the bound to derive two principled lifelong learning algorithms, and
we show that these yield results comparable with existing methods.
article_processing_charge: No
author:
- first_name: Anastasia
full_name: Pentina, Anastasia
id: 42E87FC6-F248-11E8-B48F-1D18A9856A87
last_name: Pentina
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Pentina A, Lampert C. A PAC-Bayesian bound for Lifelong Learning. In: Vol
32. ML Research Press; 2014:991-999.'
apa: 'Pentina, A., & Lampert, C. (2014). A PAC-Bayesian bound for Lifelong Learning
(Vol. 32, pp. 991–999). Presented at the ICML: International Conference on Machine
Learning, Beijing, China: ML Research Press.'
chicago: Pentina, Anastasia, and Christoph Lampert. “A PAC-Bayesian Bound for Lifelong
Learning,” 32:991–99. ML Research Press, 2014.
ieee: 'A. Pentina and C. Lampert, “A PAC-Bayesian bound for Lifelong Learning,”
presented at the ICML: International Conference on Machine Learning, Beijing,
China, 2014, vol. 32, pp. 991–999.'
ista: 'Pentina A, Lampert C. 2014. A PAC-Bayesian bound for Lifelong Learning. ICML:
International Conference on Machine Learning vol. 32, 991–999.'
mla: Pentina, Anastasia, and Christoph Lampert. A PAC-Bayesian Bound for Lifelong
Learning. Vol. 32, ML Research Press, 2014, pp. 991–99.
short: A. Pentina, C. Lampert, in:, ML Research Press, 2014, pp. 991–999.
conference:
end_date: 2014-06-26
location: Beijing, China
name: 'ICML: International Conference on Machine Learning'
start_date: 2014-06-21
date_created: 2018-12-11T11:56:03Z
date_published: 2014-05-10T00:00:00Z
date_updated: 2023-10-17T11:54:24Z
day: '10'
department:
- _id: ChLa
intvolume: ' 32'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://dl.acm.org/citation.cfm?id=3045003
month: '05'
oa: 1
oa_version: Submitted Version
page: 991 - 999
publication_status: published
publisher: ML Research Press
publist_id: '4844'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A PAC-Bayesian bound for Lifelong Learning
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 32
year: '2014'
...
---
_id: '2161'
abstract:
- lang: eng
text: 'Repeated pathogen exposure is a common threat in colonies of social insects,
posing selection pressures on colony members to respond with improved disease-defense
performance. We here tested whether experience gained by repeated tending of low-level
fungus-exposed (Metarhizium robertsii) larvae may alter the performance of sanitary
brood care in the clonal ant, Platythyrea punctata. We trained ants individually
over nine consecutive trials to either sham-treated or fungus-exposed larvae.
We then compared the larval grooming behavior of naive and trained ants and measured
how effectively they removed infectious fungal conidiospores from the fungus-exposed
larvae. We found that the ants changed the duration of larval grooming in response
to both, larval treatment and their level of experience: (1) sham-treated larvae
received longer grooming than the fungus-exposed larvae and (2) trained ants performed
less self-grooming but longer larval grooming than naive ants, which was true
for both, ants trained to fungus-exposed and also to sham-treated larvae. Ants
that groomed the fungus-exposed larvae for longer periods removed a higher number
of fungal conidiospores from the surface of the fungus-exposed larvae. As experienced
ants performed longer larval grooming, they were more effective in fungal removal,
thus making them better caretakers under pathogen attack of the colony. By studying
this clonal ant, we can thus conclude that even in the absence of genetic variation
between colony members, differences in experience levels of brood care may affect
performance of sanitary brood care in social insects.'
acknowledgement: "We thank Katrin Kellner for colony establishment and characterization,
Mike Bidochka for the fungal strain, Meghan Vyleta for fungal strain characterization,
Martina Klatt and Simon Tragust for help in the laboratory, Dimitri Missoh for developing
the software BioLogic, and Mark Brown and Raphaël Jeanson for discussion and help
with data analysis. The study was funded by the European Research Council (ERC Starting
Grant to SC; Marie Curie IEF to LVU) and the German Research Foundation DFG (to
SC and to JH), and CW received funding by the doctoral school Diversité du Vivant
(Cotutelle project to CD and SC).\r\n"
article_processing_charge: No
article_type: original
author:
- first_name: Claudia
full_name: Westhus, Claudia
id: ca9c6ca9-e8aa-11ec-a586-b9471ede0494
last_name: Westhus
- 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: Edouard
full_name: Tourdot, Edouard
last_name: Tourdot
- first_name: Jürgen
full_name: Heinze, Jürgen
last_name: Heinze
- first_name: Claudie
full_name: Doums, Claudie
last_name: Doums
- first_name: Sylvia
full_name: Cremer, Sylvia
id: 2F64EC8C-F248-11E8-B48F-1D18A9856A87
last_name: Cremer
orcid: 0000-0002-2193-3868
citation:
ama: Westhus C, Ugelvig LV, Tourdot E, Heinze J, Doums C, Cremer S. Increased grooming
after repeated brood care provides sanitary benefits in a clonal ant. Behavioral
Ecology and Sociobiology. 2014;68(10):1701-1710. doi:10.1007/s00265-014-1778-8
apa: Westhus, C., Ugelvig, L. V., Tourdot, E., Heinze, J., Doums, C., & Cremer,
S. (2014). Increased grooming after repeated brood care provides sanitary benefits
in a clonal ant. Behavioral Ecology and Sociobiology. Springer. https://doi.org/10.1007/s00265-014-1778-8
chicago: Westhus, Claudia, Line V Ugelvig, Edouard Tourdot, Jürgen Heinze, Claudie
Doums, and Sylvia Cremer. “Increased Grooming after Repeated Brood Care Provides
Sanitary Benefits in a Clonal Ant.” Behavioral Ecology and Sociobiology.
Springer, 2014. https://doi.org/10.1007/s00265-014-1778-8.
ieee: C. Westhus, L. V. Ugelvig, E. Tourdot, J. Heinze, C. Doums, and S. Cremer,
“Increased grooming after repeated brood care provides sanitary benefits in a
clonal ant,” Behavioral Ecology and Sociobiology, vol. 68, no. 10. Springer,
pp. 1701–1710, 2014.
ista: Westhus C, Ugelvig LV, Tourdot E, Heinze J, Doums C, Cremer S. 2014. Increased
grooming after repeated brood care provides sanitary benefits in a clonal ant.
Behavioral Ecology and Sociobiology. 68(10), 1701–1710.
mla: Westhus, Claudia, et al. “Increased Grooming after Repeated Brood Care Provides
Sanitary Benefits in a Clonal Ant.” Behavioral Ecology and Sociobiology,
vol. 68, no. 10, Springer, 2014, pp. 1701–10, doi:10.1007/s00265-014-1778-8.
short: C. Westhus, L.V. Ugelvig, E. Tourdot, J. Heinze, C. Doums, S. Cremer, Behavioral
Ecology and Sociobiology 68 (2014) 1701–1710.
date_created: 2018-12-11T11:56:03Z
date_published: 2014-07-23T00:00:00Z
date_updated: 2023-02-23T14:06:46Z
day: '23'
department:
- _id: SyCr
doi: 10.1007/s00265-014-1778-8
ec_funded: 1
intvolume: ' 68'
issue: '10'
language:
- iso: eng
month: '07'
oa_version: None
page: 1701 - 1710
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 25DC711C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '243071'
name: 'Social Vaccination in Ant Colonies: from Individual Mechanisms to Society
Effects'
- _id: 25DAF0B2-B435-11E9-9278-68D0E5697425
grant_number: CR-118/3-1
name: Host-Parasite Coevolution
publication: Behavioral Ecology and Sociobiology
publication_identifier:
issn:
- 0340-5443
publication_status: published
publisher: Springer
publist_id: '4823'
quality_controlled: '1'
related_material:
record:
- id: '9742'
relation: research_data
status: public
scopus_import: '1'
status: public
title: Increased grooming after repeated brood care provides sanitary benefits in
a clonal ant
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 68
year: '2014'
...
---
_id: '2162'
abstract:
- lang: eng
text: 'We study two-player (zero-sum) concurrent mean-payoff games played on a finite-state
graph. We focus on the important sub-class of ergodic games where all states are
visited infinitely often with probability 1. The algorithmic study of ergodic
games was initiated in a seminal work of Hoffman and Karp in 1966, but all basic
complexity questions have remained unresolved. Our main results for ergodic games
are as follows: We establish (1) an optimal exponential bound on the patience
of stationary strategies (where patience of a distribution is the inverse of the
smallest positive probability and represents a complexity measure of a stationary
strategy); (2) the approximation problem lies in FNP; (3) the approximation problem
is at least as hard as the decision problem for simple stochastic games (for which
NP ∩ coNP is the long-standing best known bound). We present a variant of the
strategy-iteration algorithm by Hoffman and Karp; show that both our algorithm
and the classical value-iteration algorithm can approximate the value in exponential
time; and identify a subclass where the value-iteration algorithm is a FPTAS.
We also show that the exact value can be expressed in the existential theory of
the reals, and establish square-root sum hardness for a related class of games.'
alternative_title:
- LNCS
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: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
citation:
ama: 'Chatterjee K, Ibsen-Jensen R. The complexity of ergodic mean payoff games.
In: Vol 8573. Springer; 2014:122-133. doi:10.1007/978-3-662-43951-7_11'
apa: 'Chatterjee, K., & Ibsen-Jensen, R. (2014). The complexity of ergodic mean
payoff games (Vol. 8573, pp. 122–133). Presented at the ICST: International Conference
on Software Testing, Verification and Validation, Copenhagen, Denmark: Springer.
https://doi.org/10.1007/978-3-662-43951-7_11'
chicago: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Complexity of Ergodic
Mean Payoff Games,” 8573:122–33. Springer, 2014. https://doi.org/10.1007/978-3-662-43951-7_11.
ieee: 'K. Chatterjee and R. Ibsen-Jensen, “The complexity of ergodic mean payoff
games,” presented at the ICST: International Conference on Software Testing, Verification
and Validation, Copenhagen, Denmark, 2014, vol. 8573, no. Part 2, pp. 122–133.'
ista: 'Chatterjee K, Ibsen-Jensen R. 2014. The complexity of ergodic mean payoff
games. ICST: International Conference on Software Testing, Verification and Validation,
LNCS, vol. 8573, 122–133.'
mla: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Complexity of Ergodic
Mean Payoff Games. Vol. 8573, no. Part 2, Springer, 2014, pp. 122–33, doi:10.1007/978-3-662-43951-7_11.
short: K. Chatterjee, R. Ibsen-Jensen, in:, Springer, 2014, pp. 122–133.
conference:
end_date: 2014-07-11
location: Copenhagen, Denmark
name: 'ICST: International Conference on Software Testing, Verification and Validation'
start_date: 2014-07-08
date_created: 2018-12-11T11:56:04Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2023-02-23T12:24:48Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-662-43951-7_11
ec_funded: 1
external_id:
arxiv:
- '1404.5734'
intvolume: ' 8573'
issue: Part 2
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1404.5734
month: '01'
oa: 1
oa_version: Preprint
page: 122 - 133
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_status: published
publisher: Springer
publist_id: '4822'
quality_controlled: '1'
related_material:
record:
- id: '5404'
relation: earlier_version
status: public
status: public
title: The complexity of ergodic mean payoff games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8573
year: '2014'
...
---
_id: '2163'
abstract:
- lang: eng
text: We consider multi-player graph games with partial-observation and parity objective.
While the decision problem for three-player games with a coalition of the first
and second players against the third player is undecidable in general, we present
a decidability result for partial-observation games where the first and third
player are in a coalition against the second player, thus where the second player
is adversarial but weaker due to partial-observation. We establish tight complexity
bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness
for parity objectives. The symmetric case of player 1 more informed than player
2 is much more complicated, and we show that already in the case where player
1 has perfect observation, memory of size non-elementary is necessary in general
for reachability objectives, and the problem is decidable for safety and reachability
objectives. From our results we derive new complexity results for partial-observation
stochastic games.
acknowledgement: "This research was partly supported by European project Cassting
(FP7-601148).\r\nTechnical Report under https://research-explorer.app.ist.ac.at/record/5418\r\n"
alternative_title:
- LNCS
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
citation:
ama: 'Chatterjee K, Doyen L. Games with a weak adversary. In: Lecture Notes in
Computer Science. Vol 8573. Springer; 2014:110-121. doi:10.1007/978-3-662-43951-7_10'
apa: 'Chatterjee, K., & Doyen, L. (2014). Games with a weak adversary. In Lecture
Notes in Computer Science (Vol. 8573, pp. 110–121). Copenhagen, Denmark: Springer.
https://doi.org/10.1007/978-3-662-43951-7_10'
chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Games with a Weak Adversary.”
In Lecture Notes in Computer Science, 8573:110–21. Springer, 2014. https://doi.org/10.1007/978-3-662-43951-7_10.
ieee: K. Chatterjee and L. Doyen, “Games with a weak adversary,” in Lecture Notes
in Computer Science, Copenhagen, Denmark, 2014, vol. 8573, no. Part 2, pp.
110–121.
ista: 'Chatterjee K, Doyen L. 2014. Games with a weak adversary. Lecture Notes in
Computer Science. ICALP: Automata, Languages and Programming, LNCS, vol. 8573,
110–121.'
mla: Chatterjee, Krishnendu, and Laurent Doyen. “Games with a Weak Adversary.” Lecture
Notes in Computer Science, vol. 8573, no. Part 2, Springer, 2014, pp. 110–21,
doi:10.1007/978-3-662-43951-7_10.
short: K. Chatterjee, L. Doyen, in:, Lecture Notes in Computer Science, Springer,
2014, pp. 110–121.
conference:
end_date: 2014-07-11
location: Copenhagen, Denmark
name: 'ICALP: Automata, Languages and Programming'
start_date: 2014-07-08
date_created: 2018-12-11T11:56:04Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2023-02-23T12:25:29Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-662-43951-7_10
ec_funded: 1
external_id:
arxiv:
- '1404.5453'
intvolume: ' 8573'
issue: Part 2
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1404.5453
month: '01'
oa: 1
oa_version: Preprint
page: 110 - 121
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: Lecture Notes in Computer Science
publication_status: published
publisher: Springer
publist_id: '4821'
quality_controlled: '1'
related_material:
record:
- id: '5418'
relation: earlier_version
status: public
status: public
title: Games with a weak adversary
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8573
year: '2014'
...
---
_id: '2164'
abstract:
- lang: eng
text: 'Neuronal ectopia, such as granule cell dispersion (GCD) in temporal lobe
epilepsy (TLE), has been assumed to result from a migration defect during development.
Indeed, recent studies reported that aberrant migration of neonatal-generated
dentate granule cells (GCs) increased the risk to develop epilepsy later in life.
On the contrary, in the present study, we show that fully differentiated GCs become
motile following the induction of epileptiform activity, resulting in GCD. Hippocampal
slice cultures from transgenic mice expressing green fluorescent protein in differentiated,
but not in newly generated GCs, were incubated with the glutamate receptor agonist
kainate (KA), which induced GC burst activity and GCD. Using real-time microscopy,
we observed that KA-exposed, differentiated GCs translocated their cell bodies
and changed their dendritic organization. As found in human TLE, KA application
was associated with decreased expression of the extracellular matrix protein Reelin,
particularly in hilar interneurons. Together these findings suggest that KA-induced
motility of differentiated GCs contributes to the development of GCD and establish
slice cultures as a model to study neuronal changes induced by epileptiform activity. '
author:
- first_name: Xuejun
full_name: Chai, Xuejun
last_name: Chai
- first_name: Gert
full_name: Münzner, Gert
last_name: Münzner
- first_name: Shanting
full_name: Zhao, Shanting
last_name: Zhao
- first_name: Stefanie
full_name: Tinnes, Stefanie
last_name: Tinnes
- first_name: Janina
full_name: Kowalski, Janina
id: 3F3CA136-F248-11E8-B48F-1D18A9856A87
last_name: Kowalski
- first_name: Ute
full_name: Häussler, Ute
last_name: Häussler
- first_name: Christina
full_name: Young, Christina
last_name: Young
- first_name: Carola
full_name: Haas, Carola
last_name: Haas
- first_name: Michael
full_name: Frotscher, Michael
last_name: Frotscher
citation:
ama: Chai X, Münzner G, Zhao S, et al. Epilepsy-induced motility of differentiated
neurons. Cerebral Cortex. 2014;24(8):2130-2140. doi:10.1093/cercor/bht067
apa: Chai, X., Münzner, G., Zhao, S., Tinnes, S., Kowalski, J., Häussler, U., …
Frotscher, M. (2014). Epilepsy-induced motility of differentiated neurons. Cerebral
Cortex. Oxford University Press. https://doi.org/10.1093/cercor/bht067
chicago: Chai, Xuejun, Gert Münzner, Shanting Zhao, Stefanie Tinnes, Janina Kowalski,
Ute Häussler, Christina Young, Carola Haas, and Michael Frotscher. “Epilepsy-Induced
Motility of Differentiated Neurons.” Cerebral Cortex. Oxford University
Press, 2014. https://doi.org/10.1093/cercor/bht067.
ieee: X. Chai et al., “Epilepsy-induced motility of differentiated neurons,”
Cerebral Cortex, vol. 24, no. 8. Oxford University Press, pp. 2130–2140,
2014.
ista: Chai X, Münzner G, Zhao S, Tinnes S, Kowalski J, Häussler U, Young C, Haas
C, Frotscher M. 2014. Epilepsy-induced motility of differentiated neurons. Cerebral
Cortex. 24(8), 2130–2140.
mla: Chai, Xuejun, et al. “Epilepsy-Induced Motility of Differentiated Neurons.”
Cerebral Cortex, vol. 24, no. 8, Oxford University Press, 2014, pp. 2130–40,
doi:10.1093/cercor/bht067.
short: X. Chai, G. Münzner, S. Zhao, S. Tinnes, J. Kowalski, U. Häussler, C. Young,
C. Haas, M. Frotscher, Cerebral Cortex 24 (2014) 2130–2140.
date_created: 2018-12-11T11:56:04Z
date_published: 2014-08-01T00:00:00Z
date_updated: 2021-01-12T06:55:43Z
day: '01'
department:
- _id: PeJo
doi: 10.1093/cercor/bht067
intvolume: ' 24'
issue: '8'
language:
- iso: eng
month: '08'
oa_version: None
page: 2130 - 2140
publication: Cerebral Cortex
publication_status: published
publisher: Oxford University Press
publist_id: '4820'
quality_controlled: '1'
scopus_import: 1
status: public
title: Epilepsy-induced motility of differentiated neurons
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '2014'
...
---
_id: '2167'
abstract:
- lang: eng
text: Model-based testing is a promising technology for black-box software and hardware
testing, in which test cases are generated automatically from high-level specifications.
Nowadays, systems typically consist of multiple interacting components and, due
to their complexity, testing presents a considerable portion of the effort and
cost in the design process. Exploiting the compositional structure of system specifications
can considerably reduce the effort in model-based testing. Moreover, inferring
properties about the system from testing its individual components allows the
designer to reduce the amount of integration testing. In this paper, we study
compositional properties of the ioco-testing theory. We propose a new approach
to composition and hiding operations, inspired by contract-based design and interface
theories. These operations preserve behaviors that are compatible under composition
and hiding, and prune away incompatible ones. The resulting specification characterizes
the input sequences for which the unit testing of components is sufficient to
infer the correctness of component integration without the need for further tests.
We provide a methodology that uses these results to minimize integration testing
effort, but also to detect potential weaknesses in specifications. While we focus
on asynchronous models and the ioco conformance relation, the resulting methodology
can be applied to a broader class of systems.
article_number: '6823899'
article_processing_charge: No
arxiv: 1
author:
- first_name: Przemyslaw
full_name: Daca, Przemyslaw
id: 49351290-F248-11E8-B48F-1D18A9856A87
last_name: Daca
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Willibald
full_name: Krenn, Willibald
last_name: Krenn
- first_name: Dejan
full_name: Nickovic, Dejan
last_name: Nickovic
citation:
ama: 'Daca P, Henzinger TA, Krenn W, Nickovic D. Compositional specifications for
IOCO testing. In: IEEE 7th International Conference on Software Testing, Verification
and Validation. IEEE; 2014. doi:10.1109/ICST.2014.50'
apa: 'Daca, P., Henzinger, T. A., Krenn, W., & Nickovic, D. (2014). Compositional
specifications for IOCO testing. In IEEE 7th International Conference on Software
Testing, Verification and Validation. Cleveland, USA: IEEE. https://doi.org/10.1109/ICST.2014.50'
chicago: Daca, Przemyslaw, Thomas A Henzinger, Willibald Krenn, and Dejan Nickovic.
“Compositional Specifications for IOCO Testing.” In IEEE 7th International
Conference on Software Testing, Verification and Validation. IEEE, 2014. https://doi.org/10.1109/ICST.2014.50.
ieee: P. Daca, T. A. Henzinger, W. Krenn, and D. Nickovic, “Compositional specifications
for IOCO testing,” in IEEE 7th International Conference on Software Testing,
Verification and Validation, Cleveland, USA, 2014.
ista: 'Daca P, Henzinger TA, Krenn W, Nickovic D. 2014. Compositional specifications
for IOCO testing. IEEE 7th International Conference on Software Testing, Verification
and Validation. ICST: International Conference on Software Testing, Verification
and Validation, 6823899.'
mla: Daca, Przemyslaw, et al. “Compositional Specifications for IOCO Testing.” IEEE
7th International Conference on Software Testing, Verification and Validation,
6823899, IEEE, 2014, doi:10.1109/ICST.2014.50.
short: P. Daca, T.A. Henzinger, W. Krenn, D. Nickovic, in:, IEEE 7th International
Conference on Software Testing, Verification and Validation, IEEE, 2014.
conference:
end_date: 2014-04-04
location: Cleveland, USA
name: 'ICST: International Conference on Software Testing, Verification and Validation'
start_date: 2014-03-31
date_created: 2018-12-11T11:56:06Z
date_published: 2014-03-01T00:00:00Z
date_updated: 2023-09-07T11:58:33Z
day: '01'
department:
- _id: ToHe
doi: 10.1109/ICST.2014.50
ec_funded: 1
external_id:
arxiv:
- '1904.07083'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1904.07083
month: '03'
oa: 1
oa_version: Preprint
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
publication: IEEE 7th International Conference on Software Testing, Verification and
Validation
publication_identifier:
isbn:
- 978-1-4799-2255-0
issn:
- 2159-4848
publication_status: published
publisher: IEEE
publist_id: '4817'
quality_controlled: '1'
related_material:
record:
- id: '5411'
relation: earlier_version
status: public
- id: '1155'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Compositional specifications for IOCO testing
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2168'
abstract:
- lang: eng
text: Many species have an essentially continuous distribution in space, in which
there are no natural divisions between randomly mating subpopulations. Yet, the
standard approach to modelling these populations is to impose an arbitrary grid
of demes, adjusting deme sizes and migration rates in an attempt to capture the
important features of the population. Such indirect methods are required because
of the failure of the classical models of isolation by distance, which have been
shown to have major technical flaws. A recently introduced model of extinction
and recolonisation in two dimensions solves these technical problems, and provides
a rigorous technical foundation for the study of populations evolving in a spatial
continuum. The coalescent process for this model is simply stated, but direct
simulation is very inefficient for large neighbourhood sizes. We present efficient
and exact algorithms to simulate this coalescent process for arbitrary sample
sizes and numbers of loci, and analyse these algorithms in detail.
author:
- first_name: Jerome
full_name: Kelleher, Jerome
last_name: Kelleher
- first_name: Alison
full_name: Etheridge, Alison
last_name: Etheridge
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
citation:
ama: 'Kelleher J, Etheridge A, Barton NH. Coalescent simulation in continuous space:
Algorithms for large neighbourhood size. Theoretical Population Biology.
2014;95:13-23. doi:10.1016/j.tpb.2014.05.001'
apa: 'Kelleher, J., Etheridge, A., & Barton, N. H. (2014). Coalescent simulation
in continuous space: Algorithms for large neighbourhood size. Theoretical Population
Biology. Academic Press. https://doi.org/10.1016/j.tpb.2014.05.001'
chicago: 'Kelleher, Jerome, Alison Etheridge, and Nicholas H Barton. “Coalescent
Simulation in Continuous Space: Algorithms for Large Neighbourhood Size.” Theoretical
Population Biology. Academic Press, 2014. https://doi.org/10.1016/j.tpb.2014.05.001.'
ieee: 'J. Kelleher, A. Etheridge, and N. H. Barton, “Coalescent simulation in continuous
space: Algorithms for large neighbourhood size,” Theoretical Population Biology,
vol. 95. Academic Press, pp. 13–23, 2014.'
ista: 'Kelleher J, Etheridge A, Barton NH. 2014. Coalescent simulation in continuous
space: Algorithms for large neighbourhood size. Theoretical Population Biology.
95, 13–23.'
mla: 'Kelleher, Jerome, et al. “Coalescent Simulation in Continuous Space: Algorithms
for Large Neighbourhood Size.” Theoretical Population Biology, vol. 95,
Academic Press, 2014, pp. 13–23, doi:10.1016/j.tpb.2014.05.001.'
short: J. Kelleher, A. Etheridge, N.H. Barton, Theoretical Population Biology 95
(2014) 13–23.
date_created: 2018-12-11T11:56:06Z
date_published: 2014-08-01T00:00:00Z
date_updated: 2021-01-12T06:55:44Z
day: '01'
ddc:
- '570'
department:
- _id: NiBa
doi: 10.1016/j.tpb.2014.05.001
ec_funded: 1
file:
- access_level: open_access
checksum: 979d7a8034e9df198f068f0d251f31bd
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:49Z
date_updated: 2020-07-14T12:45:31Z
file_id: '4839'
file_name: IST-2015-391-v1+1_1-s2.0-S0040580914000355-main.pdf
file_size: 569005
relation: main_file
file_date_updated: 2020-07-14T12:45:31Z
has_accepted_license: '1'
intvolume: ' 95'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: 13 - 23
project:
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
publication: Theoretical Population Biology
publication_status: published
publisher: Academic Press
publist_id: '4816'
pubrep_id: '391'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Coalescent simulation in continuous space: Algorithms for large neighbourhood
size'
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 95
year: '2014'
...
---
_id: '2169'
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: Sebastian
full_name: Novak, Sebastian
id: 461468AE-F248-11E8-B48F-1D18A9856A87
last_name: Novak
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
citation:
ama: Barton NH, Novak S, Paixao T. Diverse forms of selection in evolution and computer
science. PNAS. 2014;111(29):10398-10399. doi:10.1073/pnas.1410107111
apa: Barton, N. H., Novak, S., & Paixao, T. (2014). Diverse forms of selection
in evolution and computer science. PNAS. National Academy of Sciences.
https://doi.org/10.1073/pnas.1410107111
chicago: Barton, Nicholas H, Sebastian Novak, and Tiago Paixao. “Diverse Forms of
Selection in Evolution and Computer Science.” PNAS. National Academy of
Sciences, 2014. https://doi.org/10.1073/pnas.1410107111.
ieee: N. H. Barton, S. Novak, and T. Paixao, “Diverse forms of selection in evolution
and computer science,” PNAS, vol. 111, no. 29. National Academy of Sciences,
pp. 10398–10399, 2014.
ista: Barton NH, Novak S, Paixao T. 2014. Diverse forms of selection in evolution
and computer science. PNAS. 111(29), 10398–10399.
mla: Barton, Nicholas H., et al. “Diverse Forms of Selection in Evolution and Computer
Science.” PNAS, vol. 111, no. 29, National Academy of Sciences, 2014, pp.
10398–99, doi:10.1073/pnas.1410107111.
short: N.H. Barton, S. Novak, T. Paixao, PNAS 111 (2014) 10398–10399.
date_created: 2018-12-11T11:56:07Z
date_published: 2014-07-22T00:00:00Z
date_updated: 2021-01-12T06:55:45Z
day: '22'
department:
- _id: NiBa
doi: 10.1073/pnas.1410107111
intvolume: ' 111'
issue: '29'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4115508/
month: '07'
oa: 1
oa_version: Submitted Version
page: 10398 - 10399
publication: PNAS
publication_status: published
publisher: National Academy of Sciences
publist_id: '4815'
quality_controlled: '1'
scopus_import: 1
status: public
title: Diverse forms of selection in evolution and computer science
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 111
year: '2014'
...