---
_id: '11578'
abstract:
- lang: eng
text: We present the first results from our CAlibrating LYMan α with Hα (CALYMHA)
pilot survey at the Isaac Newton Telescope. We measure Lyα emission for 488 Hα
selected galaxies at z = 2.23 from High-z Emission Line Survey in the COSMOS and
UDS fields with a specially designed narrow-band filter (λc = 3918 Å, Δλ = 52
Å). We find 17 dual Hα-Lyα emitters [fLyα > 5 × 10−17 erg s−1 cm−2, of which five
are X-ray active galactic nuclei (AGN)]. For star-forming galaxies, we find a
range of Lyα escape fractions (fesc, measured with 3 arcsec apertures) from 2
to 30 per cent. These galaxies have masses from 3 × 108 M⊙ to 1011 M⊙ and dust
attenuations E(B − V) = 0–0.5. Using stacking, we measure a median escape fraction
of 1.6 ± 0.5 per cent (4.0 ± 1.0 per cent without correcting Hα for dust), but
show that this depends on galaxy properties. The stacked fesc tends to decrease
with increasing star formation rate and dust attenuation. However, at the highest
masses and dust attenuations, we detect individual galaxies with fesc much higher
than the typical values from stacking, indicating significant scatter in the values
of fesc. Relations between fesc and UV slope are bimodal, with high fesc for either
the bluest or reddest galaxies. We speculate that this bimodality and large scatter
in the values of fesc is due to additional physical mechanisms such as outflows
facilitating fesc for dusty/massive systems. Lyα is significantly more extended
than Hα and the UV. fesc continues to increase up to at least 20 kpc (3σ, 40 kpc
[2σ]) for typical star-forming galaxies and thus the aperture is the most important
predictor of fesc.
acknowledgement: "We thank the anonymous referee for constructive comments and suggestions
which have improved the quality of this work. JM acknowledges the support of a Huygens
PhD fellowship from Leiden University. DS and JM acknowledge financial support from
the Netherlands Organization for Scientific research (NWO) through a Veni fellowship,
and DS from FCT through a FCT Investigator Starting Grant and Start-up Grant (IF/01154/2012/CP0189/CT0010)
and from FCT grant PEst-OE/FIS/UI2751/2014. IO acknowledges support from the European
Research Council (ERC) in the form of Advanced Investigator Programme, COSMICISM,
321302. HR acknowledges support from the ERC Advanced Investigator programme NewClusters
321271. IRS acknowledges support from STFC (ST/L00075X/1), the ERC Advanced Investigator
programme DUSTYGAL 321334 and a Royal Society/Wolfson Merit Award. APA acknowledges
support from the Fundac¸ao para a Ciencia e para a Tecnologia (FCT) through the
Fellowship SFRH/BD/52706/2014.\r\nBased on observations made with the Isaac Newton
Telescope (proposals 2013AN002, 2013BN008, 2014AC88, 2014AN002, 2014BN006, 2014BC118)
operated on the island of La Palma by the Isaac Newton Group in the Spanish Observatorio
del Roque de los Muchachos of the Instituto de Astrof´ısica de Canarias. We acknowledge
the tremendous work that has been done by both COSMOS and UKIDSS UDS/SXDF teams
in assembling such large, state-ofthe-art multi-wavelength data sets over such wide
areas, as those have been crucial for the results presented in this paper. The sample
of HAEs is publicly available from Sobral et al. (2013).\r\nWe have benefited greatly
from the publically available programming language PYTHON, including the NUMPY,
MATPLOTLIB, PYFITS, SCIPY (Jones et al. 2001; Hunter 2007; Van Der Walt, Colbert
& Varoquaux 2011) and ASTROPY (Astropy Collaboration et al. 2013) packages, the
imaging tools SEXTRACTOR, SWARP and SCAMP (Bertin & Arnouts 1996; Bertin 2006, 2010)
and the TOPCAT analysis program (Taylor 2005)."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jorryt J
full_name: Matthee, Jorryt J
id: 7439a258-f3c0-11ec-9501-9df22fe06720
last_name: Matthee
orcid: 0000-0003-2871-127X
- first_name: David
full_name: Sobral, David
last_name: Sobral
- first_name: Iván
full_name: Oteo, Iván
last_name: Oteo
- first_name: Philip
full_name: Best, Philip
last_name: Best
- first_name: Ian
full_name: Smail, Ian
last_name: Smail
- first_name: Huub
full_name: Röttgering, Huub
last_name: Röttgering
- first_name: Ana
full_name: Paulino-Afonso, Ana
last_name: Paulino-Afonso
citation:
ama: 'Matthee JJ, Sobral D, Oteo I, et al. The CALYMHA survey: Lyα escape fraction
and its dependence on galaxy properties at z = 2.23. Monthly Notices of the
Royal Astronomical Society. 2016;458(1):449-467. doi:10.1093/mnras/stw322'
apa: 'Matthee, J. J., Sobral, D., Oteo, I., Best, P., Smail, I., Röttgering, H.,
& Paulino-Afonso, A. (2016). The CALYMHA survey: Lyα escape fraction and its
dependence on galaxy properties at z = 2.23. Monthly Notices of the Royal Astronomical
Society. Oxford University Press. https://doi.org/10.1093/mnras/stw322'
chicago: 'Matthee, Jorryt J, David Sobral, Iván Oteo, Philip Best, Ian Smail, Huub
Röttgering, and Ana Paulino-Afonso. “The CALYMHA Survey: Lyα Escape Fraction and
Its Dependence on Galaxy Properties at z = 2.23.” Monthly Notices of the Royal
Astronomical Society. Oxford University Press, 2016. https://doi.org/10.1093/mnras/stw322.'
ieee: 'J. J. Matthee et al., “The CALYMHA survey: Lyα escape fraction and
its dependence on galaxy properties at z = 2.23,” Monthly Notices of the Royal
Astronomical Society, vol. 458, no. 1. Oxford University Press, pp. 449–467,
2016.'
ista: 'Matthee JJ, Sobral D, Oteo I, Best P, Smail I, Röttgering H, Paulino-Afonso
A. 2016. The CALYMHA survey: Lyα escape fraction and its dependence on galaxy
properties at z = 2.23. Monthly Notices of the Royal Astronomical Society. 458(1),
449–467.'
mla: 'Matthee, Jorryt J., et al. “The CALYMHA Survey: Lyα Escape Fraction and Its
Dependence on Galaxy Properties at z = 2.23.” Monthly Notices of the Royal
Astronomical Society, vol. 458, no. 1, Oxford University Press, 2016, pp.
449–67, doi:10.1093/mnras/stw322.'
short: J.J. Matthee, D. Sobral, I. Oteo, P. Best, I. Smail, H. Röttgering, A. Paulino-Afonso,
Monthly Notices of the Royal Astronomical Society 458 (2016) 449–467.
date_created: 2022-07-14T08:51:37Z
date_published: 2016-05-01T00:00:00Z
date_updated: 2022-08-19T08:17:19Z
day: '01'
doi: 10.1093/mnras/stw322
extern: '1'
external_id:
arxiv:
- '1602.02756'
intvolume: ' 458'
issue: '1'
keyword:
- Space and Planetary Science
- Astronomy and Astrophysics
- 'galaxies: evolution'
- 'galaxies: high-redshift'
- 'galaxies: ISM'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1602.02756
month: '05'
oa: 1
oa_version: Preprint
page: 449-467
publication: Monthly Notices of the Royal Astronomical Society
publication_identifier:
eissn:
- 1365-2966
issn:
- 0035-8711
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The CALYMHA survey: Lyα escape fraction and its dependence on galaxy properties
at z = 2.23'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 458
year: '2016'
...
---
_id: '1158'
abstract:
- lang: eng
text: Speciation results from the progressive accumulation of mutations that decrease
the probability of mating between parental populations or reduce the fitness of
hybrids—the so-called species barriers. The speciation genomic literature, however,
is mainly a collection of case studies, each with its own approach and specificities,
such that a global view of the gradual process of evolution from one to two species
is currently lacking. Of primary importance is the prevalence of gene flow between
diverging entities, which is central in most species concepts and has been widely
discussed in recent years. Here, we explore the continuum of speciation thanks
to a comparative analysis of genomic data from 61 pairs of populations/species
of animals with variable levels of divergence. Gene flow between diverging gene
pools is assessed under an approximate Bayesian computation (ABC) framework. We
show that the intermediate "grey zone" of speciation, in which taxonomy
is often controversial, spans from 0.5% to 2% of net synonymous divergence, irrespective
of species life history traits or ecology. Thanks to appropriate modeling of among-locus
variation in genetic drift and introgression rate, we clarify the status of the
majority of ambiguous cases and uncover a number of cryptic species. Our analysis
also reveals the high incidence in animals of semi-isolated species (when some
but not all loci are affected by barriers to gene flow) and highlights the intrinsic
difficulty, both statistical and conceptual, of delineating species in the grey
zone of speciation.
acknowledgement: "European Research Council (ERC) https://erc.europa.eu/ (grant number
ERC grant 232971). PopPhyl project. The funder had no role in study design, data
collection and analysis, decision to publish, or preparation of the manuscript.
French National Research Agency (ANR) http://www.agence-nationale-recherche.fr/en/project-based-funding-to-advance-french-research/
(grant number ANR-12-BSV7- 0011). HYSEA project.\r\nWe thank Aude Darracq, Vincent
Castric, Pierre-Alexandre Gagnaire, Xavier Vekemans, and John Welch for insightful
discussions. The computations were performed at the Vital-IT (http://www.vital-it.ch)
Center for high-performance computing of the SIB Swiss Institute of Bioinformatics
and the ISEM computing cluster at the platform Montpellier Bioinformatique et Biodiversité."
article_number: e2000234
author:
- first_name: Camille
full_name: Roux, Camille
last_name: Roux
- first_name: Christelle
full_name: Fraisse, Christelle
id: 32DF5794-F248-11E8-B48F-1D18A9856A87
last_name: Fraisse
orcid: 0000-0001-8441-5075
- first_name: Jonathan
full_name: Romiguier, Jonathan
last_name: Romiguier
- first_name: Youann
full_name: Anciaux, Youann
last_name: Anciaux
- first_name: Nicolas
full_name: Galtier, Nicolas
last_name: Galtier
- first_name: Nicolas
full_name: Bierne, Nicolas
last_name: Bierne
citation:
ama: Roux C, Fraisse C, Romiguier J, Anciaux Y, Galtier N, Bierne N. Shedding light
on the grey zone of speciation along a continuum of genomic divergence. PLoS
Biology. 2016;14(12). doi:10.1371/journal.pbio.2000234
apa: Roux, C., Fraisse, C., Romiguier, J., Anciaux, Y., Galtier, N., & Bierne,
N. (2016). Shedding light on the grey zone of speciation along a continuum of
genomic divergence. PLoS Biology. Public Library of Science. https://doi.org/10.1371/journal.pbio.2000234
chicago: Roux, Camille, Christelle Fraisse, Jonathan Romiguier, Youann Anciaux,
Nicolas Galtier, and Nicolas Bierne. “Shedding Light on the Grey Zone of Speciation
along a Continuum of Genomic Divergence.” PLoS Biology. Public Library
of Science, 2016. https://doi.org/10.1371/journal.pbio.2000234.
ieee: C. Roux, C. Fraisse, J. Romiguier, Y. Anciaux, N. Galtier, and N. Bierne,
“Shedding light on the grey zone of speciation along a continuum of genomic divergence,”
PLoS Biology, vol. 14, no. 12. Public Library of Science, 2016.
ista: Roux C, Fraisse C, Romiguier J, Anciaux Y, Galtier N, Bierne N. 2016. Shedding
light on the grey zone of speciation along a continuum of genomic divergence.
PLoS Biology. 14(12), e2000234.
mla: Roux, Camille, et al. “Shedding Light on the Grey Zone of Speciation along
a Continuum of Genomic Divergence.” PLoS Biology, vol. 14, no. 12, e2000234,
Public Library of Science, 2016, doi:10.1371/journal.pbio.2000234.
short: C. Roux, C. Fraisse, J. Romiguier, Y. Anciaux, N. Galtier, N. Bierne, PLoS
Biology 14 (2016).
date_created: 2018-12-11T11:50:28Z
date_published: 2016-12-27T00:00:00Z
date_updated: 2023-02-23T14:11:16Z
day: '27'
ddc:
- '576'
department:
- _id: BeVi
- _id: NiBa
doi: 10.1371/journal.pbio.2000234
file:
- access_level: open_access
checksum: 2bab63b068a9840efd532b9ae583f9bb
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:42Z
date_updated: 2020-07-14T12:44:36Z
file_id: '5164'
file_name: IST-2017-742-v1+1_journal.pbio.2000234.pdf
file_size: 2494348
relation: main_file
file_date_updated: 2020-07-14T12:44:36Z
has_accepted_license: '1'
intvolume: ' 14'
issue: '12'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
publication: PLoS Biology
publication_status: published
publisher: Public Library of Science
publist_id: '6200'
pubrep_id: '742'
quality_controlled: '1'
related_material:
record:
- id: '9862'
relation: research_data
status: public
- id: '9863'
relation: research_data
status: public
scopus_import: 1
status: public
title: Shedding light on the grey zone of speciation along a continuum of genomic
divergence
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: 14
year: '2016'
...
---
_id: '1164'
abstract:
- lang: eng
text: 'A drawing of a graph G is radial if the vertices of G are placed on concentric
circles C1, … , Ck with common center c, and edges are drawn radially: every edge
intersects every circle centered at c at most once. G is radial planar if it has
a radial embedding, that is, a crossing-free radial drawing. If the vertices of
G are ordered or partitioned into ordered levels (as they are for leveled graphs),
we require that the assignment of vertices to circles corresponds to the given
ordering or leveling. A pair of edges e and f in a graph is independent if e and
f do not share a vertex. We show that a graph G is radial planar if G has a radial
drawing in which every two independent edges cross an even number of times; the
radial embedding has the same leveling as the radial drawing. In other words,
we establish the strong Hanani-Tutte theorem for radial planarity. This characterization
yields a very simple algorithm for radial planarity testing.'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Michael
full_name: Pelsmajer, Michael
last_name: Pelsmajer
- first_name: Marcus
full_name: Schaefer, Marcus
last_name: Schaefer
citation:
ama: 'Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity II. In:
Vol 9801. Springer; 2016:468-481. doi:10.1007/978-3-319-50106-2_36'
apa: 'Fulek, R., Pelsmajer, M., & Schaefer, M. (2016). Hanani-Tutte for radial
planarity II (Vol. 9801, pp. 468–481). Presented at the GD: Graph Drawing and
Network Visualization, Athens, Greece: Springer. https://doi.org/10.1007/978-3-319-50106-2_36'
chicago: Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte
for Radial Planarity II,” 9801:468–81. Springer, 2016. https://doi.org/10.1007/978-3-319-50106-2_36.
ieee: 'R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity
II,” presented at the GD: Graph Drawing and Network Visualization, Athens, Greece,
2016, vol. 9801, pp. 468–481.'
ista: 'Fulek R, Pelsmajer M, Schaefer M. 2016. Hanani-Tutte for radial planarity
II. GD: Graph Drawing and Network Visualization, LNCS, vol. 9801, 468–481.'
mla: Fulek, Radoslav, et al. Hanani-Tutte for Radial Planarity II. Vol. 9801,
Springer, 2016, pp. 468–81, doi:10.1007/978-3-319-50106-2_36.
short: R. Fulek, M. Pelsmajer, M. Schaefer, in:, Springer, 2016, pp. 468–481.
conference:
end_date: 2016-09-21
location: Athens, Greece
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2016-09-19
date_created: 2018-12-11T11:50:29Z
date_published: 2016-12-08T00:00:00Z
date_updated: 2023-02-23T10:05:57Z
day: '08'
department:
- _id: UlWa
doi: 10.1007/978-3-319-50106-2_36
ec_funded: 1
external_id:
arxiv:
- '1608.08662'
intvolume: ' 9801'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1608.08662
month: '12'
oa: 1
oa_version: Preprint
page: 468 - 481
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: Springer
publist_id: '6193'
quality_controlled: '1'
related_material:
record:
- id: '1113'
relation: later_version
status: public
- id: '1595'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Hanani-Tutte for radial planarity II
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9801
year: '2016'
...
---
_id: '1165'
abstract:
- lang: eng
text: We show that c-planarity is solvable in quadratic time for flat clustered
graphs with three clusters if the combinatorial embedding of the underlying graph
is fixed. In simpler graph-theoretical terms our result can be viewed as follows.
Given a graph G with the vertex set partitioned into three parts embedded on a
2-sphere, our algorithm decides if we can augment G by adding edges without creating
an edge-crossing so that in the resulting spherical graph the vertices of each
part induce a connected sub-graph. We proceed by a reduction to the problem of
testing the existence of a perfect matching in planar bipartite graphs. We formulate
our result in a slightly more general setting of cyclic clustered graphs, i.e.,
the simple graph obtained by contracting each cluster, where we disregard loops
and multi-edges, is a cycle.
acknowledgement: "R. Fulek—The research leading to these results has received funding
from the People Programme (Marie Curie Actions) of the European Union’s Seventh
Framework Programme (FP7/2007-2013) under REA grant agreement no [291734].\r\nI
would like to thank Jan Kynčl and Dömötör Pálvölgyi for many comments and suggestions
that helped to improve the presentation of the result."
alternative_title:
- LNCS
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
citation:
ama: 'Fulek R. C-planarity of embedded cyclic c-graphs. In: Vol 9801. Springer;
2016:94-106. doi:10.1007/978-3-319-50106-2_8'
apa: 'Fulek, R. (2016). C-planarity of embedded cyclic c-graphs (Vol. 9801, pp.
94–106). Presented at the GD: Graph Drawing and Network Visualization, Athens,
Greece: Springer. https://doi.org/10.1007/978-3-319-50106-2_8'
chicago: Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs,” 9801:94–106.
Springer, 2016. https://doi.org/10.1007/978-3-319-50106-2_8.
ieee: 'R. Fulek, “C-planarity of embedded cyclic c-graphs,” presented at the GD:
Graph Drawing and Network Visualization, Athens, Greece, 2016, vol. 9801, pp.
94–106.'
ista: 'Fulek R. 2016. C-planarity of embedded cyclic c-graphs. GD: Graph Drawing
and Network Visualization, LNCS, vol. 9801, 94–106.'
mla: Fulek, Radoslav. C-Planarity of Embedded Cyclic c-Graphs. Vol. 9801,
Springer, 2016, pp. 94–106, doi:10.1007/978-3-319-50106-2_8.
short: R. Fulek, in:, Springer, 2016, pp. 94–106.
conference:
end_date: 2016-09-21
location: Athens, Greece
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2016-09-19
date_created: 2018-12-11T11:50:30Z
date_published: 2016-12-08T00:00:00Z
date_updated: 2023-09-27T12:14:48Z
day: '08'
department:
- _id: UlWa
doi: 10.1007/978-3-319-50106-2_8
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1602.01346
month: '12'
oa: 1
oa_version: Preprint
page: 94 - 106
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: Springer
publist_id: '6192'
quality_controlled: '1'
related_material:
record:
- id: '794'
relation: later_version
status: public
scopus_import: 1
status: public
title: C-planarity of embedded cyclic c-graphs
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: '9801 '
year: '2016'
...
---
_id: '1167'
abstract:
- lang: eng
text: Evolutionary pathways describe trajectories of biological evolution in the
space of different variants of organisms (genotypes). The probability of existence
and the number of evolutionary pathways that lead from a given genotype to a better-adapted
genotype are important measures of accessibility of local fitness optima and the
reproducibility of evolution. Both quantities have been studied in simple mathematical
models where genotypes are represented as binary sequences of two types of basic
units, and the network of permitted mutations between the genotypes is a hypercube
graph. However, it is unclear how these results translate to the biologically
relevant case in which genotypes are represented by sequences of more than two
units, for example four nucleotides (DNA) or 20 amino acids (proteins), and the
mutational graph is not the hypercube. Here we investigate accessibility of the
best-adapted genotype in the general case of K > 2 units. Using computer generated
and experimental fitness landscapes we show that accessibility of the global fitness
maximum increases with K and can be much higher than for binary sequences. The
increase in accessibility comes from the increase in the number of indirect trajectories
exploited by evolution for higher K. As one of the consequences, the fraction
of genotypes that are accessible increases by three orders of magnitude when the
number of units K increases from 2 to 16 for landscapes of size N ∼ 106genotypes.
This suggests that evolution can follow many different trajectories on such landscapes
and the reconstruction of evolutionary pathways from experimental data might be
an extremely difficult task.
acknowledgement: MZ acknowledges the Polish National Science Centre grant no. DEC-2012/07/N/NZ2/00107.
BW was supported by the Scottish Government/Royal Society of Edinburgh Personal
Research Fellowship. We thank Marjon de Vos and Oliver Martin for critically reading
the manuscript.
article_number: e1005218
article_processing_charge: No
author:
- first_name: Marcin P
full_name: Zagórski, Marcin P
id: 343DA0DC-F248-11E8-B48F-1D18A9856A87
last_name: Zagórski
orcid: 0000-0001-7896-7762
- first_name: Zdzisław
full_name: Burda, Zdzisław
last_name: Burda
- first_name: Bartłomiej
full_name: Wacław, Bartłomiej
last_name: Wacław
citation:
ama: Zagórski MP, Burda Z, Wacław B. Beyond the hypercube evolutionary accessibility
of fitness landscapes with realistic mutational networks. PLoS Computational
Biology. 2016;12(12). doi:10.1371/journal.pcbi.1005218
apa: Zagórski, M. P., Burda, Z., & Wacław, B. (2016). Beyond the hypercube evolutionary
accessibility of fitness landscapes with realistic mutational networks. PLoS
Computational Biology. Public Library of Science. https://doi.org/10.1371/journal.pcbi.1005218
chicago: Zagórski, Marcin P, Zdzisław Burda, and Bartłomiej Wacław. “Beyond the
Hypercube Evolutionary Accessibility of Fitness Landscapes with Realistic Mutational
Networks.” PLoS Computational Biology. Public Library of Science, 2016.
https://doi.org/10.1371/journal.pcbi.1005218.
ieee: M. P. Zagórski, Z. Burda, and B. Wacław, “Beyond the hypercube evolutionary
accessibility of fitness landscapes with realistic mutational networks,” PLoS
Computational Biology, vol. 12, no. 12. Public Library of Science, 2016.
ista: Zagórski MP, Burda Z, Wacław B. 2016. Beyond the hypercube evolutionary accessibility
of fitness landscapes with realistic mutational networks. PLoS Computational Biology.
12(12), e1005218.
mla: Zagórski, Marcin P., et al. “Beyond the Hypercube Evolutionary Accessibility
of Fitness Landscapes with Realistic Mutational Networks.” PLoS Computational
Biology, vol. 12, no. 12, e1005218, Public Library of Science, 2016, doi:10.1371/journal.pcbi.1005218.
short: M.P. Zagórski, Z. Burda, B. Wacław, PLoS Computational Biology 12 (2016).
date_created: 2018-12-11T11:50:30Z
date_published: 2016-12-09T00:00:00Z
date_updated: 2023-02-23T14:11:22Z
day: '09'
ddc:
- '570'
department:
- _id: AnKi
doi: 10.1371/journal.pcbi.1005218
file:
- access_level: open_access
checksum: 84f44ae92866c52ff1ca8a574558dca7
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:08Z
date_updated: 2020-07-14T12:44:37Z
file_id: '4926'
file_name: IST-2017-740-v1+1_journal.pcbi.1005218.pdf
file_size: 3822299
relation: main_file
file_date_updated: 2020-07-14T12:44:37Z
has_accepted_license: '1'
intvolume: ' 12'
issue: '12'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
publication: PLoS Computational Biology
publication_status: published
publisher: Public Library of Science
publist_id: '6190'
pubrep_id: '740'
quality_controlled: '1'
related_material:
record:
- id: '9866'
relation: research_data
status: public
scopus_import: '1'
status: public
title: Beyond the hypercube evolutionary accessibility of fitness landscapes with
realistic mutational networks
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: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 12
year: '2016'
...
---
_id: '1172'
abstract:
- lang: eng
text: A central issue in cell biology is the physico-chemical basis of organelle
biogenesis in intracellular trafficking pathways, its most impressive manifestation
being the biogenesis of Golgi cisternae. At a basic level, such morphologically
and chemically distinct compartments should arise from an interplay between the
molecular transport and chemical maturation. Here, we formulate analytically tractable,
minimalist models, that incorporate this interplay between transport and chemical
progression in physical space, and explore the conditions for de novo biogenesis
of distinct cisternae. We propose new quantitative measures that can discriminate
between the various models of transport in a qualitative manner-this includes
measures of the dynamics in steady state and the dynamical response to perturbations
of the kind amenable to live-cell imaging.
acknowledgement: H.S. thanks NCBS for hospitality. We thank Vivek Malhotra and Mukund
Thattai for critical discussions and suggestions.
article_number: '38840'
author:
- first_name: Himani
full_name: Sachdeva, Himani
id: 42377A0A-F248-11E8-B48F-1D18A9856A87
last_name: Sachdeva
- first_name: Mustansir
full_name: Barma, Mustansir
last_name: Barma
- first_name: Madan
full_name: Rao, Madan
last_name: Rao
citation:
ama: Sachdeva H, Barma M, Rao M. Nonequilibrium description of de novo biogenesis
and transport through Golgi-like cisternae. Scientific Reports. 2016;6.
doi:10.1038/srep38840
apa: Sachdeva, H., Barma, M., & Rao, M. (2016). Nonequilibrium description of
de novo biogenesis and transport through Golgi-like cisternae. Scientific Reports.
Nature Publishing Group. https://doi.org/10.1038/srep38840
chicago: Sachdeva, Himani, Mustansir Barma, and Madan Rao. “Nonequilibrium Description
of de Novo Biogenesis and Transport through Golgi-like Cisternae.” Scientific
Reports. Nature Publishing Group, 2016. https://doi.org/10.1038/srep38840.
ieee: H. Sachdeva, M. Barma, and M. Rao, “Nonequilibrium description of de novo
biogenesis and transport through Golgi-like cisternae,” Scientific Reports,
vol. 6. Nature Publishing Group, 2016.
ista: Sachdeva H, Barma M, Rao M. 2016. Nonequilibrium description of de novo biogenesis
and transport through Golgi-like cisternae. Scientific Reports. 6, 38840.
mla: Sachdeva, Himani, et al. “Nonequilibrium Description of de Novo Biogenesis
and Transport through Golgi-like Cisternae.” Scientific Reports, vol. 6,
38840, Nature Publishing Group, 2016, doi:10.1038/srep38840.
short: H. Sachdeva, M. Barma, M. Rao, Scientific Reports 6 (2016).
date_created: 2018-12-11T11:50:32Z
date_published: 2016-12-19T00:00:00Z
date_updated: 2021-01-12T06:48:50Z
day: '19'
ddc:
- '576'
department:
- _id: NiBa
doi: 10.1038/srep38840
file:
- access_level: open_access
checksum: cb378732da885ea4959ec5b845fb6e52
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:56Z
date_updated: 2020-07-14T12:44:37Z
file_id: '4977'
file_name: IST-2017-737-v1+1_srep38840.pdf
file_size: 760967
relation: main_file
file_date_updated: 2020-07-14T12:44:37Z
has_accepted_license: '1'
intvolume: ' 6'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
publication: Scientific Reports
publication_status: published
publisher: Nature Publishing Group
publist_id: '6183'
pubrep_id: '737'
quality_controlled: '1'
scopus_import: 1
status: public
title: Nonequilibrium description of de novo biogenesis and transport through Golgi-like
cisternae
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: 6
year: '2016'
...
---
_id: '1177'
abstract:
- lang: eng
text: Boldyreva, Palacio and Warinschi introduced a multiple forking game as an
extension of general forking. The notion of (multiple) forking is a useful abstraction
from the actual simulation of cryptographic scheme to the adversary in a security
reduction, and is achieved through the intermediary of a so-called wrapper algorithm.
Multiple forking has turned out to be a useful tool in the security argument of
several cryptographic protocols. However, a reduction employing multiple forking
incurs a significant degradation of (Formula presented.) , where (Formula presented.)
denotes the upper bound on the underlying random oracle calls and (Formula presented.)
, the number of forkings. In this work we take a closer look at the reasons for
the degradation with a tighter security bound in mind. We nail down the exact
set of conditions for success in the multiple forking game. A careful analysis
of the cryptographic schemes and corresponding security reduction employing multiple
forking leads to the formulation of ‘dependence’ and ‘independence’ conditions
pertaining to the output of the wrapper in different rounds. Based on the (in)dependence
conditions we propose a general framework of multiple forking and a General Multiple
Forking Lemma. Leveraging (in)dependence to the full allows us to improve the
degradation factor in the multiple forking game by a factor of (Formula presented.).
By implication, the cost of a single forking involving two random oracles (augmented
forking) matches that involving a single random oracle (elementary forking). Finally,
we study the effect of these observations on the concrete security of existing
schemes employing multiple forking. We conclude that by careful design of the
protocol (and the wrapper in the security reduction) it is possible to harness
our observations to the full extent.
acknowledgement: "We are grateful to the anonymous reviewers for their insightful
comments. The\r\ndetailed reports helped us a lot to address the technical mistakes
as well as to improve the overall presentation of the paper."
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Sanjit
full_name: Chatterjee, Sanjit
last_name: Chatterjee
citation:
ama: 'Kamath Hosdurg C, Chatterjee S. A closer look at multiple-forking: Leveraging
(in)dependence for a tighter bound. Algorithmica. 2016;74(4):1321-1362.
doi:10.1007/s00453-015-9997-6'
apa: 'Kamath Hosdurg, C., & Chatterjee, S. (2016). A closer look at multiple-forking:
Leveraging (in)dependence for a tighter bound. Algorithmica. Springer.
https://doi.org/10.1007/s00453-015-9997-6'
chicago: 'Kamath Hosdurg, Chethan, and Sanjit Chatterjee. “A Closer Look at Multiple-Forking:
Leveraging (in)Dependence for a Tighter Bound.” Algorithmica. Springer,
2016. https://doi.org/10.1007/s00453-015-9997-6.'
ieee: 'C. Kamath Hosdurg and S. Chatterjee, “A closer look at multiple-forking:
Leveraging (in)dependence for a tighter bound,” Algorithmica, vol. 74,
no. 4. Springer, pp. 1321–1362, 2016.'
ista: 'Kamath Hosdurg C, Chatterjee S. 2016. A closer look at multiple-forking:
Leveraging (in)dependence for a tighter bound. Algorithmica. 74(4), 1321–1362.'
mla: 'Kamath Hosdurg, Chethan, and Sanjit Chatterjee. “A Closer Look at Multiple-Forking:
Leveraging (in)Dependence for a Tighter Bound.” Algorithmica, vol. 74,
no. 4, Springer, 2016, pp. 1321–62, doi:10.1007/s00453-015-9997-6.'
short: C. Kamath Hosdurg, S. Chatterjee, Algorithmica 74 (2016) 1321–1362.
date_created: 2018-12-11T11:50:33Z
date_published: 2016-04-01T00:00:00Z
date_updated: 2021-01-12T06:48:52Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/s00453-015-9997-6
intvolume: ' 74'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://eprint.iacr.org/2013/651
month: '04'
oa: 1
oa_version: Submitted Version
page: 1321 - 1362
publication: Algorithmica
publication_status: published
publisher: Springer
publist_id: '6177'
quality_controlled: '1'
status: public
title: 'A closer look at multiple-forking: Leveraging (in)dependence for a tighter
bound'
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 74
year: '2016'
...
---
_id: '1179'
abstract:
- lang: eng
text: "Computational notions of entropy have recently found many applications, including
leakage-resilient cryptography, deterministic encryption or memory delegation.
The two main types of results which make computational notions so useful are (1)
Chain rules, which quantify by how much the computational entropy of a variable
decreases if conditioned on some other variable (2) Transformations, which quantify
to which extend one type of entropy implies another.\r\n\r\nSuch chain rules and
transformations typically lose a significant amount in quality of the entropy,
and are the reason why applying these results one gets rather weak quantitative
security bounds. In this paper we for the first time prove lower bounds in this
context, showing that existing results for transformations are, unfortunately,
basically optimal for non-adaptive black-box reductions (and it’s hard to imagine
how non black-box reductions or adaptivity could be useful here.)\r\n\r\nA variable
X has k bits of HILL entropy of quality (ϵ,s)\r\nif there exists a variable Y
with k bits min-entropy which cannot be distinguished from X with advantage ϵ\r\n\r\nby
distinguishing circuits of size s. A weaker notion is Metric entropy, where we
switch quantifiers, and only require that for every distinguisher of size s, such
a Y exists.\r\n\r\nWe first describe our result concerning transformations. By
definition, HILL implies Metric without any loss in quality. Metric entropy often
comes up in applications, but must be transformed to HILL for meaningful security
guarantees. The best known result states that if a variable X has k bits of Metric
entropy of quality (ϵ,s)\r\n, then it has k bits of HILL with quality (2ϵ,s⋅ϵ2).
We show that this loss of a factor Ω(ϵ−2)\r\n\r\nin circuit size is necessary.
In fact, we show the stronger result that this loss is already necessary when
transforming so called deterministic real valued Metric entropy to randomised
boolean Metric (both these variants of Metric entropy are implied by HILL without
loss in quality).\r\n\r\nThe chain rule for HILL entropy states that if X has
k bits of HILL entropy of quality (ϵ,s)\r\n, then for any variable Z of length
m, X conditioned on Z has k−m bits of HILL entropy with quality (ϵ,s⋅ϵ2/2m). We
show that a loss of Ω(2m/ϵ) in circuit size necessary here. Note that this still
leaves a gap of ϵ between the known bound and our lower bound."
acknowledgement: "K. Pietrzak—Supported by the European Research Council consolidator
grant (682815-TOCNeT).\r\nM. Skórski—Supported by the National Science Center, Poland
(2015/17/N/ST6/03564)."
alternative_title:
- LNCS
author:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Skorski
full_name: Maciej, Skorski
last_name: Maciej
citation:
ama: 'Pietrzak KZ, Maciej S. Pseudoentropy: Lower-bounds for chain rules and transformations.
In: Vol 9985. Springer; 2016:183-203. doi:10.1007/978-3-662-53641-4_8'
apa: 'Pietrzak, K. Z., & Maciej, S. (2016). Pseudoentropy: Lower-bounds for
chain rules and transformations (Vol. 9985, pp. 183–203). Presented at the TCC:
Theory of Cryptography Conference, Beijing, China: Springer. https://doi.org/10.1007/978-3-662-53641-4_8'
chicago: 'Pietrzak, Krzysztof Z, and Skorski Maciej. “Pseudoentropy: Lower-Bounds
for Chain Rules and Transformations,” 9985:183–203. Springer, 2016. https://doi.org/10.1007/978-3-662-53641-4_8.'
ieee: 'K. Z. Pietrzak and S. Maciej, “Pseudoentropy: Lower-bounds for chain rules
and transformations,” presented at the TCC: Theory of Cryptography Conference,
Beijing, China, 2016, vol. 9985, pp. 183–203.'
ista: 'Pietrzak KZ, Maciej S. 2016. Pseudoentropy: Lower-bounds for chain rules
and transformations. TCC: Theory of Cryptography Conference, LNCS, vol. 9985,
183–203.'
mla: 'Pietrzak, Krzysztof Z., and Skorski Maciej. Pseudoentropy: Lower-Bounds
for Chain Rules and Transformations. Vol. 9985, Springer, 2016, pp. 183–203,
doi:10.1007/978-3-662-53641-4_8.'
short: K.Z. Pietrzak, S. Maciej, in:, Springer, 2016, pp. 183–203.
conference:
end_date: 2016-11-03
location: Beijing, China
name: 'TCC: Theory of Cryptography Conference'
start_date: 2016-10-31
date_created: 2018-12-11T11:50:34Z
date_published: 2016-10-22T00:00:00Z
date_updated: 2021-01-12T06:48:53Z
day: '22'
department:
- _id: KrPi
doi: 10.1007/978-3-662-53641-4_8
ec_funded: 1
intvolume: ' 9985'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/159
month: '10'
oa: 1
oa_version: Preprint
page: 183 - 203
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_status: published
publisher: Springer
publist_id: '6175'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Pseudoentropy: Lower-bounds for chain rules and transformations'
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 9985
year: '2016'
...
---
_id: '1182'
abstract:
- lang: eng
text: 'Balanced knockout tournaments are ubiquitous in sports competitions and are
also used in decisionmaking and elections. The traditional computational question,
that asks to compute a draw (optimal draw) that maximizes the winning probability
for a distinguished player, has received a lot of attention. Previous works consider
the problem where the pairwise winning probabilities are known precisely, while
we study how robust is the winning probability with respect to small errors in
the pairwise winning probabilities. First, we present several illuminating examples
to establish: (a) there exist deterministic tournaments (where the pairwise winning
probabilities are 0 or 1) where one optimal draw is much more robust than the
other; and (b) in general, there exist tournaments with slightly suboptimal draws
that are more robust than all the optimal draws. The above examples motivate the
study of the computational problem of robust draws that guarantee a specified
winning probability. Second, we present a polynomial-time algorithm for approximating
the robustness of a draw for sufficiently small errors in pairwise winning probabilities,
and obtain that the stated computational problem is NP-complete. We also show
that two natural cases of deterministic tournaments where the optimal draw could
be computed in polynomial time also admit polynomial-time algorithms to compute
robust optimal draws.'
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
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
citation:
ama: 'Chatterjee K, Ibsen-Jensen R, Tkadlec J. Robust draws in balanced knockout
tournaments. In: Vol 2016-January. AAAI Press; 2016:172-179.'
apa: 'Chatterjee, K., Ibsen-Jensen, R., & Tkadlec, J. (2016). Robust draws in
balanced knockout tournaments (Vol. 2016–January, pp. 172–179). Presented at the
IJCAI: International Joint Conference on Artificial Intelligence, New York, NY,
USA: AAAI Press.'
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Josef Tkadlec. “Robust
Draws in Balanced Knockout Tournaments,” 2016–January:172–79. AAAI Press, 2016.
ieee: 'K. Chatterjee, R. Ibsen-Jensen, and J. Tkadlec, “Robust draws in balanced
knockout tournaments,” presented at the IJCAI: International Joint Conference
on Artificial Intelligence, New York, NY, USA, 2016, vol. 2016–January, pp. 172–179.'
ista: 'Chatterjee K, Ibsen-Jensen R, Tkadlec J. 2016. Robust draws in balanced knockout
tournaments. IJCAI: International Joint Conference on Artificial Intelligence
vol. 2016–January, 172–179.'
mla: Chatterjee, Krishnendu, et al. Robust Draws in Balanced Knockout Tournaments.
Vol. 2016–January, AAAI Press, 2016, pp. 172–79.
short: K. Chatterjee, R. Ibsen-Jensen, J. Tkadlec, in:, AAAI Press, 2016, pp. 172–179.
conference:
end_date: 2016-07-15
location: New York, NY, USA
name: 'IJCAI: International Joint Conference on Artificial Intelligence'
start_date: 2016-07-09
date_created: 2018-12-11T11:50:35Z
date_published: 2016-01-01T00:00:00Z
date_updated: 2023-02-21T10:04:26Z
day: '01'
department:
- _id: KrCh
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1604.05090v1
month: '01'
oa: 1
oa_version: Preprint
page: 172 - 179
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication_status: published
publisher: AAAI Press
publist_id: '6171'
quality_controlled: '1'
related_material:
link:
- relation: table_of_contents
url: https://www.ijcai.org/proceedings/2016
scopus_import: 1
status: public
title: Robust draws in balanced knockout tournaments
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2016-January
year: '2016'
...
---
_id: '1183'
abstract:
- lang: eng
text: Autism spectrum disorders (ASD) are a group of genetic disorders often overlapping
with other neurological conditions. We previously described abnormalities in the
branched-chain amino acid (BCAA) catabolic pathway as a cause of ASD. Here, we
show that the solute carrier transporter 7a5 (SLC7A5), a large neutral amino acid
transporter localized at the blood brain barrier (BBB), has an essential role
in maintaining normal levels of brain BCAAs. In mice, deletion of Slc7a5 from
the endothelial cells of the BBB leads to atypical brain amino acid profile, abnormal
mRNA translation, and severe neurological abnormalities. Furthermore, we identified
several patients with autistic traits and motor delay carrying deleterious homozygous
mutations in the SLC7A5 gene. Finally, we demonstrate that BCAA intracerebroventricular
administration ameliorates abnormal behaviors in adult mutant mice. Our data elucidate
a neurological syndrome defined by SLC7A5 mutations and support an essential role
for the BCAA in human brain function.
acknowledgement: "This work was supported by NICHD (P01HD070494) and SFARI (grant
275275) to J.G.G., and FWF (SFB35_3523) to G.N.\r\nWe thank A.C. Manzano, Mike Liu,
and F. Marr for technical assistance, and R. Shigemoto and the IST Austria Electron
Microscopy (EM) Facility for assistance. We acknowledge support from CIDR for genome-wide
SNP analysis (X01HG008823) and Broad Institute Center for Mendelian Disorders (UM1HG008900
to D. MacArthur), the Yale Center for Mendelian Disorders (U54HG006504 to M.G.),
the Gregory M. Kiez and Mehmet Kutman Foundation (M.G.), Italian Ministry of Instruction
University and Research (PON01_00937 to C.I.), and NIH (R01-GM108911 to A.S.). This
work was supported by NICHD (P01HD070494) and SFARI (grant 275275) to J.G.G., and
FWF (SFB35_3523) to G.N.\r\n\r\n#EMFacility"
article_processing_charge: No
article_type: original
author:
- first_name: Dora-Clara
full_name: Tarlungeanu, Dora-Clara
id: 2ABCE612-F248-11E8-B48F-1D18A9856A87
last_name: Tarlungeanu
- first_name: Elena
full_name: Deliu, Elena
id: 37A40D7E-F248-11E8-B48F-1D18A9856A87
last_name: Deliu
orcid: 0000-0002-7370-5293
- first_name: Christoph
full_name: Dotter, Christoph
id: 4C66542E-F248-11E8-B48F-1D18A9856A87
last_name: Dotter
orcid: 0000-0002-9033-9096
- first_name: Majdi
full_name: Kara, Majdi
last_name: Kara
- first_name: Philipp
full_name: Janiesch, Philipp
last_name: Janiesch
- first_name: Mariafrancesca
full_name: Scalise, Mariafrancesca
last_name: Scalise
- first_name: Michele
full_name: Galluccio, Michele
last_name: Galluccio
- first_name: Mateja
full_name: Tesulov, Mateja
last_name: Tesulov
- first_name: Emanuela
full_name: Morelli, Emanuela
id: 3F4D1282-F248-11E8-B48F-1D18A9856A87
last_name: Morelli
- first_name: Fatma
full_name: Sönmez, Fatma
last_name: Sönmez
- first_name: Kaya
full_name: Bilgüvar, Kaya
last_name: Bilgüvar
- first_name: Ryuichi
full_name: Ohgaki, Ryuichi
last_name: Ohgaki
- first_name: Yoshikatsu
full_name: Kanai, Yoshikatsu
last_name: Kanai
- first_name: Anide
full_name: Johansen, Anide
last_name: Johansen
- first_name: Seham
full_name: Esharif, Seham
last_name: Esharif
- first_name: Tawfeg
full_name: Ben Omran, Tawfeg
last_name: Ben Omran
- first_name: Meral
full_name: Topcu, Meral
last_name: Topcu
- first_name: Avner
full_name: Schlessinger, Avner
last_name: Schlessinger
- first_name: Cesare
full_name: Indiveri, Cesare
last_name: Indiveri
- first_name: Kent
full_name: Duncan, Kent
last_name: Duncan
- first_name: Ahmet
full_name: Caglayan, Ahmet
last_name: Caglayan
- first_name: Murat
full_name: Günel, Murat
last_name: Günel
- first_name: Joseph
full_name: Gleeson, Joseph
last_name: Gleeson
- first_name: Gaia
full_name: Novarino, Gaia
id: 3E57A680-F248-11E8-B48F-1D18A9856A87
last_name: Novarino
orcid: 0000-0002-7673-7178
citation:
ama: Tarlungeanu D-C, Deliu E, Dotter C, et al. Impaired amino acid transport at
the blood brain barrier is a cause of autism spectrum disorder. Cell. 2016;167(6):1481-1494.
doi:10.1016/j.cell.2016.11.013
apa: Tarlungeanu, D.-C., Deliu, E., Dotter, C., Kara, M., Janiesch, P., Scalise,
M., … Novarino, G. (2016). Impaired amino acid transport at the blood brain barrier
is a cause of autism spectrum disorder. Cell. Cell Press. https://doi.org/10.1016/j.cell.2016.11.013
chicago: Tarlungeanu, Dora-Clara, Elena Deliu, Christoph Dotter, Majdi Kara, Philipp
Janiesch, Mariafrancesca Scalise, Michele Galluccio, et al. “Impaired Amino Acid
Transport at the Blood Brain Barrier Is a Cause of Autism Spectrum Disorder.”
Cell. Cell Press, 2016. https://doi.org/10.1016/j.cell.2016.11.013.
ieee: D.-C. Tarlungeanu et al., “Impaired amino acid transport at the blood
brain barrier is a cause of autism spectrum disorder,” Cell, vol. 167,
no. 6. Cell Press, pp. 1481–1494, 2016.
ista: Tarlungeanu D-C, Deliu E, Dotter C, Kara M, Janiesch P, Scalise M, Galluccio
M, Tesulov M, Morelli E, Sönmez F, Bilgüvar K, Ohgaki R, Kanai Y, Johansen A,
Esharif S, Ben Omran T, Topcu M, Schlessinger A, Indiveri C, Duncan K, Caglayan
A, Günel M, Gleeson J, Novarino G. 2016. Impaired amino acid transport at the
blood brain barrier is a cause of autism spectrum disorder. Cell. 167(6), 1481–1494.
mla: Tarlungeanu, Dora-Clara, et al. “Impaired Amino Acid Transport at the Blood
Brain Barrier Is a Cause of Autism Spectrum Disorder.” Cell, vol. 167,
no. 6, Cell Press, 2016, pp. 1481–94, doi:10.1016/j.cell.2016.11.013.
short: D.-C. Tarlungeanu, E. Deliu, C. Dotter, M. Kara, P. Janiesch, M. Scalise,
M. Galluccio, M. Tesulov, E. Morelli, F. Sönmez, K. Bilgüvar, R. Ohgaki, Y. Kanai,
A. Johansen, S. Esharif, T. Ben Omran, M. Topcu, A. Schlessinger, C. Indiveri,
K. Duncan, A. Caglayan, M. Günel, J. Gleeson, G. Novarino, Cell 167 (2016) 1481–1494.
date_created: 2018-12-11T11:50:35Z
date_published: 2016-12-01T00:00:00Z
date_updated: 2024-03-25T23:30:07Z
day: '01'
ddc:
- '576'
- '616'
department:
- _id: GaNo
doi: 10.1016/j.cell.2016.11.013
file:
- access_level: open_access
checksum: 7fe01ab12a6610d3db421e0136db2f77
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:44Z
date_updated: 2020-07-14T12:44:37Z
file_id: '5030'
file_name: IST-2017-771-v1+1_Tarlungeanu_et_al._Final_edited.pdf
file_size: 73907957
relation: main_file
file_date_updated: 2020-07-14T12:44:37Z
has_accepted_license: '1'
intvolume: ' 167'
issue: '6'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Submitted Version
page: 1481 - 1494
project:
- _id: 25473368-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: F03523
name: Transmembrane Transporters in Health and Disease
publication: Cell
publication_status: published
publisher: Cell Press
publist_id: '6170'
pubrep_id: '771'
quality_controlled: '1'
related_material:
record:
- id: '395'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Impaired amino acid transport at the blood brain barrier is a cause of autism
spectrum disorder
type: journal_article
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 167
year: '2016'
...
---
_id: '11834'
abstract:
- lang: eng
text: "We present a deterministic incremental algorithm for exactly maintaining
the size of a minimum cut with ~O(1) amortized time per edge insertion and O(1)
query time. This result partially answers an open question posed by Thorup [Combinatorica
2007]. It also stays in sharp contrast to a polynomial conditional lower-bound
for the fully-dynamic weighted minimum cut problem. Our algorithm is obtained
by combining a recent sparsification technique of Kawarabayashi and Thorup [STOC
2015] and an exact incremental algorithm of Henzinger [J. of Algorithm 1997].\r\n\r\nWe
also study space-efficient incremental algorithms for the minimum cut problem.
Concretely, we show that there exists an O(n log n/epsilon^2) space Monte-Carlo
algorithm that can process a stream of edge insertions starting from an empty
graph, and with high probability, the algorithm maintains a (1+epsilon)-approximation
to the minimum cut. The algorithm has ~O(1) amortized update-time and constant
query-time."
alternative_title:
- LIPIcs
article_number: '46'
article_processing_charge: No
arxiv: 1
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Mikkel
full_name: Thorup, Mikkel
last_name: Thorup
citation:
ama: 'Goranci G, Henzinger MH, Thorup M. Incremental exact min-cut in poly-logarithmic
amortized update time. In: 24th Annual European Symposium on Algorithms.
Vol 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPICS.ESA.2016.46'
apa: 'Goranci, G., Henzinger, M. H., & Thorup, M. (2016). Incremental exact
min-cut in poly-logarithmic amortized update time. In 24th Annual European
Symposium on Algorithms (Vol. 57). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPICS.ESA.2016.46'
chicago: Goranci, Gramoz, Monika H Henzinger, and Mikkel Thorup. “Incremental Exact
Min-Cut in Poly-Logarithmic Amortized Update Time.” In 24th Annual European
Symposium on Algorithms, Vol. 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2016. https://doi.org/10.4230/LIPICS.ESA.2016.46.
ieee: G. Goranci, M. H. Henzinger, and M. Thorup, “Incremental exact min-cut in
poly-logarithmic amortized update time,” in 24th Annual European Symposium
on Algorithms, Aarhus, Denmark, 2016, vol. 57.
ista: 'Goranci G, Henzinger MH, Thorup M. 2016. Incremental exact min-cut in poly-logarithmic
amortized update time. 24th Annual European Symposium on Algorithms. ESA: Annual
European Symposium on Algorithms, LIPIcs, vol. 57, 46.'
mla: Goranci, Gramoz, et al. “Incremental Exact Min-Cut in Poly-Logarithmic Amortized
Update Time.” 24th Annual European Symposium on Algorithms, vol. 57, 46,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:10.4230/LIPICS.ESA.2016.46.
short: G. Goranci, M.H. Henzinger, M. Thorup, in:, 24th Annual European Symposium
on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
conference:
end_date: 2016-08-24
location: Aarhus, Denmark
name: 'ESA: Annual European Symposium on Algorithms'
start_date: 2016-08-22
date_created: 2022-08-12T10:58:32Z
date_published: 2016-08-18T00:00:00Z
date_updated: 2023-02-16T12:05:59Z
day: '18'
doi: 10.4230/LIPICS.ESA.2016.46
extern: '1'
external_id:
arxiv:
- '1611.06500'
intvolume: ' 57'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPIcs.ESA.2016.46
month: '08'
oa: 1
oa_version: Published Version
publication: 24th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- 978-3-95977-015-6
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Incremental exact min-cut in poly-logarithmic amortized update time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 57
year: '2016'
...
---
_id: '11835'
abstract:
- lang: eng
text: "During the last 10 years it has become popular to study dynamic graph problems
in a emergency planning or sensitivity setting: Instead of considering the general
fully dynamic problem, we only have to process a single batch update of size d;
after the update we have to answer queries.\r\n\r\nIn this paper, we consider
the dynamic subgraph connectivity problem with sensitivity d: We are given a graph
of which some vertices are activated and some are deactivated. After that we get
a single update in which the states of up to $d$ vertices are changed. Then we
get a sequence of connectivity queries in the subgraph of activated vertices.\r\n\r\nWe
present the first fully dynamic algorithm for this problem which has an update
and query time only slightly worse than the best decremental algorithm. In addition,
we present the first incremental algorithm which is tight with respect to the
best known conditional lower bound; moreover, the algorithm is simple and we believe
it is implementable and efficient in practice."
alternative_title:
- LIPIcs
article_number: '48'
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Stefan
full_name: Neumann, Stefan
last_name: Neumann
citation:
ama: 'Henzinger MH, Neumann S. Incremental and fully dynamic subgraph connectivity
for emergency planning. In: 24th Annual European Symposium on Algorithms.
Vol 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPICS.ESA.2016.48'
apa: 'Henzinger, M. H., & Neumann, S. (2016). Incremental and fully dynamic
subgraph connectivity for emergency planning. In 24th Annual European Symposium
on Algorithms (Vol. 57). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPICS.ESA.2016.48'
chicago: Henzinger, Monika H, and Stefan Neumann. “Incremental and Fully Dynamic
Subgraph Connectivity for Emergency Planning.” In 24th Annual European Symposium
on Algorithms, Vol. 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2016. https://doi.org/10.4230/LIPICS.ESA.2016.48.
ieee: M. H. Henzinger and S. Neumann, “Incremental and fully dynamic subgraph connectivity
for emergency planning,” in 24th Annual European Symposium on Algorithms,
Aarhus, Denmark, 2016, vol. 57.
ista: 'Henzinger MH, Neumann S. 2016. Incremental and fully dynamic subgraph connectivity
for emergency planning. 24th Annual European Symposium on Algorithms. ESA: Annual
European Symposium on Algorithms, LIPIcs, vol. 57, 48.'
mla: Henzinger, Monika H., and Stefan Neumann. “Incremental and Fully Dynamic Subgraph
Connectivity for Emergency Planning.” 24th Annual European Symposium on Algorithms,
vol. 57, 48, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:10.4230/LIPICS.ESA.2016.48.
short: M.H. Henzinger, S. Neumann, in:, 24th Annual European Symposium on Algorithms,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
conference:
end_date: 2016-08-24
location: Aarhus, Denmark
name: 'ESA: Annual European Symposium on Algorithms'
start_date: 2016-08-22
date_created: 2022-08-12T11:05:41Z
date_published: 2016-08-18T00:00:00Z
date_updated: 2023-02-16T12:07:46Z
day: '18'
doi: 10.4230/LIPICS.ESA.2016.48
extern: '1'
external_id:
arxiv:
- '1611.05248'
intvolume: ' 57'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPIcs.ESA.2016.48
month: '08'
oa: 1
oa_version: Published Version
publication: 24th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- 978-3-95977-015-6
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Incremental and fully dynamic subgraph connectivity for emergency planning
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 57
year: '2016'
...
---
_id: '11836'
abstract:
- lang: eng
text: "Given a graph where vertices are partitioned into k terminals and non-terminals,
the goal is to compress the graph (i.e., reduce the number of non-terminals) using
minor operations while preserving terminal distances approximately. The distortion
of a compressed graph is the maximum multiplicative blow-up of distances between
all pairs of terminals. We study the trade-off between the number of non-terminals
and the distortion. This problem generalizes the Steiner Point Removal (SPR) problem,
in which all non-terminals must be removed.\r\n\r\nWe introduce a novel black-box
reduction to convert any lower bound on distortion for the SPR problem into a
super-linear lower bound on the number of non-terminals, with the same distortion,
for our problem. This allows us to show that there exist graphs such that every
minor with distortion less than 2 / 2.5 / 3 must have Omega(k^2) / Omega(k^{5/4})
/ Omega(k^{6/5}) non-terminals, plus more trade-offs in between. The black-box
reduction has an interesting consequence: if the tight lower bound on distortion
for the SPR problem is super-constant, then allowing any O(k) non-terminals will
not help improving the lower bound to a constant.\r\n\r\nWe also build on the
existing results on spanners, distance oracles and connected 0-extensions to show
a number of upper bounds for general graphs, planar graphs, graphs that exclude
a fixed minor and bounded treewidth graphs. Among others, we show that any graph
admits a minor with O(log k) distortion and O(k^2) non-terminals, and any planar
graph admits a minor with\r\n1 + epsilon distortion and ~O((k/epsilon)^2) non-terminals."
alternative_title:
- LIPIcs
article_number: '131'
article_processing_charge: No
arxiv: 1
author:
- first_name: Yun Kuen
full_name: Cheung, Yun Kuen
last_name: Cheung
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- 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: 'Cheung YK, Goranci G, Henzinger MH. Graph minors for preserving terminal distances
approximately - lower and upper bounds. In: 43rd International Colloquium on
Automata, Languages, and Programming. Vol 55. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2016. doi:10.4230/LIPICS.ICALP.2016.131'
apa: 'Cheung, Y. K., Goranci, G., & Henzinger, M. H. (2016). Graph minors for
preserving terminal distances approximately - lower and upper bounds. In 43rd
International Colloquium on Automata, Languages, and Programming (Vol. 55).
Rome, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2016.131'
chicago: Cheung, Yun Kuen, Gramoz Goranci, and Monika H Henzinger. “Graph Minors
for Preserving Terminal Distances Approximately - Lower and Upper Bounds.” In
43rd International Colloquium on Automata, Languages, and Programming,
Vol. 55. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. https://doi.org/10.4230/LIPICS.ICALP.2016.131.
ieee: Y. K. Cheung, G. Goranci, and M. H. Henzinger, “Graph minors for preserving
terminal distances approximately - lower and upper bounds,” in 43rd International
Colloquium on Automata, Languages, and Programming, Rome, Italy, 2016, vol.
55.
ista: 'Cheung YK, Goranci G, Henzinger MH. 2016. Graph minors for preserving terminal
distances approximately - lower and upper bounds. 43rd International Colloquium
on Automata, Languages, and Programming. ICALP: International Colloquium on Automata,
Languages, and Programming, LIPIcs, vol. 55, 131.'
mla: Cheung, Yun Kuen, et al. “Graph Minors for Preserving Terminal Distances Approximately
- Lower and Upper Bounds.” 43rd International Colloquium on Automata, Languages,
and Programming, vol. 55, 131, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2016, doi:10.4230/LIPICS.ICALP.2016.131.
short: Y.K. Cheung, G. Goranci, M.H. Henzinger, in:, 43rd International Colloquium
on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2016.
conference:
end_date: 2016-07-15
location: Rome, Italy
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2016-07-12
date_created: 2022-08-12T11:16:01Z
date_published: 2016-08-23T00:00:00Z
date_updated: 2023-02-16T12:09:54Z
day: '23'
doi: 10.4230/LIPICS.ICALP.2016.131
extern: '1'
external_id:
arxiv:
- '1604.08342'
intvolume: ' 55'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPICS.ICALP.2016.131
month: '08'
oa: 1
oa_version: Published Version
publication: 43rd International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- 978-3-95977-013-2
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Graph minors for preserving terminal distances approximately - lower and upper
bounds
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 55
year: '2016'
...
---
_id: '1184'
abstract:
- lang: eng
text: Across multicellular organisms, the costs of reproduction and self-maintenance
result in a life history trade-off between fecundity and longevity. Queens of
perennial social Hymenoptera are both highly fertile and long-lived, and thus,
this fundamental trade-off is lacking. Whether social insect males similarly evade
the fecundity/longevity trade-off remains largely unstudied. Wingless males of
the ant genus Cardiocondyla stay in their natal colonies throughout their relatively
long lives and mate with multiple female sexuals. Here, we show that Cardiocondyla
obscurior males that were allowed to mate with large numbers of female sexuals
had a shortened life span compared to males that mated at a low frequency or virgin
males. Although frequent mating negatively affects longevity, males clearly benefit
from a “live fast, die young strategy” by inseminating as many female sexuals
as possible at a cost to their own survival.
acknowledgement: 'German Science Foundation. Grant Number: SCHR 1135/2-1. We thank
M. Adam for handling part of the setups and J. Zoellner for behavioral observations.'
author:
- first_name: Sina
full_name: Metzler, Sina
id: 48204546-F248-11E8-B48F-1D18A9856A87
last_name: Metzler
- first_name: Jürgen
full_name: Heinze, Jürgen
last_name: Heinze
- first_name: Alexandra
full_name: Schrempf, Alexandra
last_name: Schrempf
citation:
ama: Metzler S, Heinze J, Schrempf A. Mating and longevity in ant males. Ecology
and Evolution. 2016;6(24):8903-8906. doi:10.1002/ece3.2474
apa: Metzler, S., Heinze, J., & Schrempf, A. (2016). Mating and longevity in
ant males. Ecology and Evolution. Wiley-Blackwell. https://doi.org/10.1002/ece3.2474
chicago: Metzler, Sina, Jürgen Heinze, and Alexandra Schrempf. “Mating and Longevity
in Ant Males.” Ecology and Evolution. Wiley-Blackwell, 2016. https://doi.org/10.1002/ece3.2474.
ieee: S. Metzler, J. Heinze, and A. Schrempf, “Mating and longevity in ant males,”
Ecology and Evolution, vol. 6, no. 24. Wiley-Blackwell, pp. 8903–8906,
2016.
ista: Metzler S, Heinze J, Schrempf A. 2016. Mating and longevity in ant males.
Ecology and Evolution. 6(24), 8903–8906.
mla: Metzler, Sina, et al. “Mating and Longevity in Ant Males.” Ecology and Evolution,
vol. 6, no. 24, Wiley-Blackwell, 2016, pp. 8903–06, doi:10.1002/ece3.2474.
short: S. Metzler, J. Heinze, A. Schrempf, Ecology and Evolution 6 (2016) 8903–8906.
date_created: 2018-12-11T11:50:36Z
date_published: 2016-12-01T00:00:00Z
date_updated: 2021-01-12T06:48:55Z
day: '01'
ddc:
- '576'
- '592'
department:
- _id: SyCr
doi: 10.1002/ece3.2474
file:
- access_level: open_access
checksum: 789026eb9e1be2a0da08376f29f569cf
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:14:12Z
date_updated: 2020-07-14T12:44:37Z
file_id: '5062'
file_name: IST-2017-736-v1+1_Metzler_et_al-2016-Ecology_and_Evolution.pdf
file_size: 328414
relation: main_file
file_date_updated: 2020-07-14T12:44:37Z
has_accepted_license: '1'
intvolume: ' 6'
issue: '24'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 8903 - 8906
publication: Ecology and Evolution
publication_status: published
publisher: Wiley-Blackwell
publist_id: '6169'
pubrep_id: '736'
quality_controlled: '1'
scopus_import: 1
status: public
title: Mating and longevity in ant males
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: 6
year: '2016'
...
---
_id: '1186'
abstract:
- lang: eng
text: The human pathogen Streptococcus pneumoniae is decorated with a special class
of surface-proteins known as choline-binding proteins (CBPs) attached to phosphorylcholine
(PCho) moieties from cell-wall teichoic acids. By a combination of X-ray crystallography,
NMR, molecular dynamics techniques and in vivo virulence and phagocytosis studies,
we provide structural information of choline-binding protein L (CbpL) and demonstrate
its impact on pneumococcal pathogenesis and immune evasion. CbpL is a very elongated
three-module protein composed of (i) an Excalibur Ca 2+ -binding domain -reported
in this work for the very first time-, (ii) an unprecedented anchorage module
showing alternate disposition of canonical and non-canonical choline-binding sites
that allows vine-like binding of fully-PCho-substituted teichoic acids (with two
choline moieties per unit), and (iii) a Ltp-Lipoprotein domain. Our structural
and infection assays indicate an important role of the whole multimodular protein
allowing both to locate CbpL at specific places on the cell wall and to interact
with host components in order to facilitate pneumococcal lung infection and transmigration
from nasopharynx to the lungs and blood. CbpL implication in both resistance against
killing by phagocytes and pneumococcal pathogenesis further postulate this surface-protein
as relevant among the pathogenic arsenal of the pneumococcus.
acknowledgement: We gratefully acknowledge Karsta Barnekow and Kristine Sievert-Giermann,
for technical assistance and Lothar Petruschka for in silico analysis (all Dept.
of Genetics, University of Greifswald). We are further grateful to the staff from
SLS synchrotron beamline for help in data collection. This work was supported by
grants from the Deutsche Forschungsgemeinschaft DFG GRK 1870 (to SH) and the Spanish
Ministry of Economy and Competitiveness (BFU2014-59389-P to JAH, CTQ2014-52633-P
to MB and SAF2012-39760-C02-02 to FG) and S2010/BMD-2457 (Community of Madrid to
JAH and FG).
article_number: '38094'
author:
- first_name: Javier
full_name: Gutierrez-Fernandez, Javier
id: 3D9511BA-F248-11E8-B48F-1D18A9856A87
last_name: Gutierrez-Fernandez
- first_name: Malek
full_name: Saleh, Malek
last_name: Saleh
- first_name: Martín
full_name: Alcorlo, Martín
last_name: Alcorlo
- first_name: Alejandro
full_name: Gómez Mejóa, Alejandro
last_name: Gómez Mejóa
- first_name: David
full_name: Pantoja Uceda, David
last_name: Pantoja Uceda
- first_name: Miguel
full_name: Treviño, Miguel
last_name: Treviño
- first_name: Franziska
full_name: Vob, Franziska
last_name: Vob
- first_name: Mohammed
full_name: Abdullah, Mohammed
last_name: Abdullah
- first_name: Sergio
full_name: Galán Bartual, Sergio
last_name: Galán Bartual
- first_name: Jolien
full_name: Seinen, Jolien
last_name: Seinen
- first_name: Pedro
full_name: Sánchez Murcia, Pedro
last_name: Sánchez Murcia
- first_name: Federico
full_name: Gago, Federico
last_name: Gago
- first_name: Marta
full_name: Bruix, Marta
last_name: Bruix
- first_name: Sven
full_name: Hammerschmidt, Sven
last_name: Hammerschmidt
- first_name: Juan
full_name: Hermoso, Juan
last_name: Hermoso
citation:
ama: Gutierrez-Fernandez J, Saleh M, Alcorlo M, et al. Modular architecture and
unique teichoic acid recognition features of choline-binding protein L CbpL contributing
to pneumococcal pathogenesis. Scientific Reports. 2016;6. doi:10.1038/srep38094
apa: Gutierrez-Fernandez, J., Saleh, M., Alcorlo, M., Gómez Mejóa, A., Pantoja Uceda,
D., Treviño, M., … Hermoso, J. (2016). Modular architecture and unique teichoic
acid recognition features of choline-binding protein L CbpL contributing to pneumococcal
pathogenesis. Scientific Reports. Nature Publishing Group. https://doi.org/10.1038/srep38094
chicago: Gutierrez-Fernandez, Javier, Malek Saleh, Martín Alcorlo, Alejandro Gómez
Mejóa, David Pantoja Uceda, Miguel Treviño, Franziska Vob, et al. “Modular Architecture
and Unique Teichoic Acid Recognition Features of Choline-Binding Protein L CbpL
Contributing to Pneumococcal Pathogenesis.” Scientific Reports. Nature
Publishing Group, 2016. https://doi.org/10.1038/srep38094.
ieee: J. Gutierrez-Fernandez et al., “Modular architecture and unique teichoic
acid recognition features of choline-binding protein L CbpL contributing to pneumococcal
pathogenesis,” Scientific Reports, vol. 6. Nature Publishing Group, 2016.
ista: Gutierrez-Fernandez J, Saleh M, Alcorlo M, Gómez Mejóa A, Pantoja Uceda D,
Treviño M, Vob F, Abdullah M, Galán Bartual S, Seinen J, Sánchez Murcia P, Gago
F, Bruix M, Hammerschmidt S, Hermoso J. 2016. Modular architecture and unique
teichoic acid recognition features of choline-binding protein L CbpL contributing
to pneumococcal pathogenesis. Scientific Reports. 6, 38094.
mla: Gutierrez-Fernandez, Javier, et al. “Modular Architecture and Unique Teichoic
Acid Recognition Features of Choline-Binding Protein L CbpL Contributing to Pneumococcal
Pathogenesis.” Scientific Reports, vol. 6, 38094, Nature Publishing Group,
2016, doi:10.1038/srep38094.
short: J. Gutierrez-Fernandez, M. Saleh, M. Alcorlo, A. Gómez Mejóa, D. Pantoja
Uceda, M. Treviño, F. Vob, M. Abdullah, S. Galán Bartual, J. Seinen, P. Sánchez
Murcia, F. Gago, M. Bruix, S. Hammerschmidt, J. Hermoso, Scientific Reports 6
(2016).
date_created: 2018-12-11T11:50:36Z
date_published: 2016-12-05T00:00:00Z
date_updated: 2021-01-12T06:48:56Z
day: '05'
ddc:
- '576'
- '610'
department:
- _id: LeSa
doi: 10.1038/srep38094
file:
- access_level: open_access
checksum: e007d78b483bc59bf5ab98e9d42a6ec1
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:18Z
date_updated: 2020-07-14T12:44:37Z
file_id: '4804'
file_name: IST-2017-735-v1+1_srep38094.pdf
file_size: 2716045
relation: main_file
file_date_updated: 2020-07-14T12:44:37Z
has_accepted_license: '1'
intvolume: ' 6'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
publication: Scientific Reports
publication_status: published
publisher: Nature Publishing Group
publist_id: '6167'
pubrep_id: '735'
quality_controlled: '1'
scopus_import: 1
status: public
title: Modular architecture and unique teichoic acid recognition features of choline-binding
protein L CbpL contributing to pneumococcal pathogenesis
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: 6
year: '2016'
...
---
_id: '11866'
abstract:
- lang: eng
text: "We present a deterministic (1+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time
algorithm for solving the single-source shortest paths problem on distributed
weighted networks (the CONGEST model); here n is the number of nodes in the network
and D is its (hop) diameter. This is the first non-trivial deterministic algorithm
for this problem. It also improves (i) the running time of the randomized (1+o(1))-approximation
Õ(n1/2D1/4+D)-time algorithm of Nanongkai [STOC 2014] by a factor of as large
as n1/8, and (ii) the O(є−1logє−1)-approximation factor of Lenzen and Patt-Shamir’s
Õ(n1/2+є+D)-time algorithm [STOC 2013] within the same running time. Our running
time matches the known time lower bound of Ω(n1/2/logn + D) [Das Sarma et al.
STOC 2011] modulo some lower-order terms, thus essentially settling the status
of this problem which was raised at least a decade ago [Elkin SIGACT News 2004].
It also implies a (2+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for
approximating a network’s weighted diameter which almost matches the lower bound
by Holzer et al. [PODC 2012].\r\n\r\nIn achieving this result, we develop two
techniques which might be of independent interest and useful in other settings:
(i) a deterministic process that replaces the “hitting set argument” commonly
used for shortest paths computation in various settings, and (ii) a simple, deterministic,
construction of an (no(1), o(1))-hop set of size O(n1+o(1)). We combine these
techniques with many distributed algorithmic techniques, some of which from problems
that are not directly related to shortest paths, e.g. ruling sets [Goldberg et
al. STOC 1987], source detection [Lenzen, Peleg PODC 2013], and partial distance
estimation [Lenzen, Patt-Shamir PODC 2015]. Our hop set construction also leads
to single-source shortest paths algorithms in two other settings: (i) a (1+o(1))-approximation
O(no(1))-time algorithm on congested cliques, and (ii) a (1+o(1))-approximation
O(no(1)logW)-pass O(n1+o(1)logW)-space streaming algorithm, when edge weights
are in {1, 2, …, W}. The first result answers an open problem in [Nanongkai, STOC
2014]. The second result partially answers an open problem raised by McGregor
in 2006 [sublinear.info
, Problem 14]."
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Sebastian
full_name: Krinninger, Sebastian
last_name: Krinninger
- first_name: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
citation:
ama: 'Henzinger MH, Krinninger S, Nanongkai D. A deterministic almost-tight distributed
algorithm for approximating single-source shortest paths. In: 48th Annual ACM
SIGACT Symposium on Theory of Computing. Association for Computing Machinery;
2016:489-498. doi:10.1145/2897518.2897638'
apa: 'Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2016). A deterministic
almost-tight distributed algorithm for approximating single-source shortest paths.
In 48th Annual ACM SIGACT Symposium on Theory of Computing (pp. 489–498).
Cambridge, MA, United States: Association for Computing Machinery. https://doi.org/10.1145/2897518.2897638'
chicago: Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic
Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.”
In 48th Annual ACM SIGACT Symposium on Theory of Computing, 489–98. Association
for Computing Machinery, 2016. https://doi.org/10.1145/2897518.2897638.
ieee: M. H. Henzinger, S. Krinninger, and D. Nanongkai, “A deterministic almost-tight
distributed algorithm for approximating single-source shortest paths,” in 48th
Annual ACM SIGACT Symposium on Theory of Computing, Cambridge, MA, United
States, 2016, pp. 489–498.
ista: 'Henzinger MH, Krinninger S, Nanongkai D. 2016. A deterministic almost-tight
distributed algorithm for approximating single-source shortest paths. 48th Annual
ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing,
489–498.'
mla: Henzinger, Monika H., et al. “A Deterministic Almost-Tight Distributed Algorithm
for Approximating Single-Source Shortest Paths.” 48th Annual ACM SIGACT Symposium
on Theory of Computing, Association for Computing Machinery, 2016, pp. 489–98,
doi:10.1145/2897518.2897638.
short: M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, 48th Annual ACM SIGACT
Symposium on Theory of Computing, Association for Computing Machinery, 2016, pp.
489–498.
conference:
end_date: 2016-06-21
location: Cambridge, MA, United States
name: 'STOC: Symposium on Theory of Computing'
start_date: 2016-06-19
date_created: 2022-08-16T09:19:31Z
date_published: 2016-06-01T00:00:00Z
date_updated: 2023-02-17T10:32:23Z
day: '01'
doi: 10.1145/2897518.2897638
extern: '1'
external_id:
arxiv:
- '1504.07056'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1504.07056
month: '06'
oa: 1
oa_version: Preprint
page: 489 - 498
publication: 48th Annual ACM SIGACT Symposium on Theory of Computing
publication_identifier:
isbn:
- 978-145034132-5
issn:
- 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: A deterministic almost-tight distributed algorithm for approximating single-source
shortest paths
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '11867'
abstract:
- lang: eng
text: We present two deterministic dynamic algorithms for the maximum matching problem.
(1) An algorithm that maintains a (2+є)-approximate maximum matching in general
graphs with O(poly(logn, 1/є)) update time. (2) An algorithm that maintains an
αK approximation of the value of the maximum matching with O(n2/K) update time
in bipartite graphs, for every sufficiently large constant positive integer K.
Here, 1≤ αK < 2 is a constant determined by the value of K. Result (1) is the
first deterministic algorithm that can maintain an o(logn)-approximate maximum
matching with polylogarithmic update time, improving the seminal result of Onak
et al. [STOC 2010]. Its approximation guarantee almost matches the guarantee of
the best randomized polylogarithmic update time algorithm [Baswana et al. FOCS
2011]. Result (2) achieves a better-than-two approximation with arbitrarily small
polynomial update time on bipartite graphs. Previously the best update time for
this problem was O(m1/4) [Bernstein et al. ICALP 2015], where m is the current
number of edges in the graph.
article_processing_charge: No
arxiv: 1
author:
- first_name: Sayan
full_name: Bhattacharya, Sayan
last_name: Bhattacharya
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
citation:
ama: 'Bhattacharya S, Henzinger MH, Nanongkai D. New deterministic approximation
algorithms for fully dynamic matching. In: 48th Annual ACM SIGACT Symposium
on Theory of Computing. Association for Computing Machinery; 2016:398-411.
doi:10.1145/2897518.2897568'
apa: 'Bhattacharya, S., Henzinger, M. H., & Nanongkai, D. (2016). New deterministic
approximation algorithms for fully dynamic matching. In 48th Annual ACM SIGACT
Symposium on Theory of Computing (pp. 398–411). Cambridge, MA, United States:
Association for Computing Machinery. https://doi.org/10.1145/2897518.2897568'
chicago: Bhattacharya, Sayan, Monika H Henzinger, and Danupon Nanongkai. “New Deterministic
Approximation Algorithms for Fully Dynamic Matching.” In 48th Annual ACM SIGACT
Symposium on Theory of Computing, 398–411. Association for Computing Machinery,
2016. https://doi.org/10.1145/2897518.2897568.
ieee: S. Bhattacharya, M. H. Henzinger, and D. Nanongkai, “New deterministic approximation
algorithms for fully dynamic matching,” in 48th Annual ACM SIGACT Symposium
on Theory of Computing, Cambridge, MA, United States, 2016, pp. 398–411.
ista: 'Bhattacharya S, Henzinger MH, Nanongkai D. 2016. New deterministic approximation
algorithms for fully dynamic matching. 48th Annual ACM SIGACT Symposium on Theory
of Computing. STOC: Symposium on Theory of Computing, 398–411.'
mla: Bhattacharya, Sayan, et al. “New Deterministic Approximation Algorithms for
Fully Dynamic Matching.” 48th Annual ACM SIGACT Symposium on Theory of Computing,
Association for Computing Machinery, 2016, pp. 398–411, doi:10.1145/2897518.2897568.
short: S. Bhattacharya, M.H. Henzinger, D. Nanongkai, in:, 48th Annual ACM SIGACT
Symposium on Theory of Computing, Association for Computing Machinery, 2016, pp.
398–411.
conference:
end_date: 2016-06-21
location: Cambridge, MA, United States
name: 'STOC: Symposium on Theory of Computing'
start_date: 2016-06-19
date_created: 2022-08-16T09:27:35Z
date_published: 2016-06-01T00:00:00Z
date_updated: 2023-02-17T11:08:19Z
day: '01'
doi: 10.1145/2897518.2897568
extern: '1'
external_id:
arxiv:
- '1604.05765'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1604.05765
month: '06'
oa: 1
oa_version: Preprint
page: 398 - 411
publication: 48th Annual ACM SIGACT Symposium on Theory of Computing
publication_identifier:
isbn:
- 978-145034132-5
issn:
- 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: New deterministic approximation algorithms for fully dynamic matching
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '1188'
abstract:
- lang: eng
text: "We consider a population dynamics model coupling cell growth to a diffusion
in the space of metabolic phenotypes as it can be obtained from realistic constraints-based
modelling. \r\nIn the asymptotic regime of slow\r\ndiffusion, that coincides with
the relevant experimental range, the resulting\r\nnon-linear Fokker–Planck equation
is solved for the steady state in the WKB\r\napproximation that maps it into the
ground state of a quantum particle in an\r\nAiry potential plus a centrifugal
term. We retrieve scaling laws for growth rate\r\nfluctuations and time response
with respect to the distance from the maximum\r\ngrowth rate suggesting that suboptimal
populations can have a faster response\r\nto perturbations."
acknowledgement: D De Martino is supported by the People Programme (Marie Curie Actions)
of the European Union's Seventh Framework Programme (FP7/2007–2013) under REA grant
agreement no. [291734]. D Masoero is supported by the FCT scholarship, number SFRH/BPD/75908/2011.
D De Martino thanks the Grupo de Física Matemática of the Universidade de Lisboa
for the kind hospitality. We also wish to thank Matteo Osella, Vincenzo Vitagliano
and Vera Luz Masoero for useful discussions, also late at night.
article_number: '123502'
author:
- first_name: Daniele
full_name: De Martino, Daniele
id: 3FF5848A-F248-11E8-B48F-1D18A9856A87
last_name: De Martino
orcid: 0000-0002-5214-4706
- first_name: Davide
full_name: Masoero, Davide
last_name: Masoero
citation:
ama: 'De Martino D, Masoero D. Asymptotic analysis of noisy fitness maximization,
applied to metabolism & growth. Journal of Statistical Mechanics:
Theory and Experiment. 2016;2016(12). doi:10.1088/1742-5468/aa4e8f'
apa: 'De Martino, D., & Masoero, D. (2016). Asymptotic analysis of noisy fitness
maximization, applied to metabolism & growth. Journal of Statistical
Mechanics: Theory and Experiment. IOPscience. https://doi.org/10.1088/1742-5468/aa4e8f'
chicago: 'De Martino, Daniele, and Davide Masoero. “Asymptotic Analysis of Noisy
Fitness Maximization, Applied to Metabolism & Growth.” Journal of
Statistical Mechanics: Theory and Experiment. IOPscience, 2016. https://doi.org/10.1088/1742-5468/aa4e8f.'
ieee: 'D. De Martino and D. Masoero, “Asymptotic analysis of noisy fitness maximization,
applied to metabolism & growth,” Journal of Statistical Mechanics:
Theory and Experiment, vol. 2016, no. 12. IOPscience, 2016.'
ista: 'De Martino D, Masoero D. 2016. Asymptotic analysis of noisy fitness maximization,
applied to metabolism & growth. Journal of Statistical Mechanics: Theory
and Experiment. 2016(12), 123502.'
mla: 'De Martino, Daniele, and Davide Masoero. “Asymptotic Analysis of Noisy Fitness
Maximization, Applied to Metabolism & Growth.” Journal of Statistical
Mechanics: Theory and Experiment, vol. 2016, no. 12, 123502, IOPscience, 2016,
doi:10.1088/1742-5468/aa4e8f.'
short: 'D. De Martino, D. Masoero, Journal of Statistical Mechanics: Theory and
Experiment 2016 (2016).'
date_created: 2018-12-11T11:50:37Z
date_published: 2016-12-30T00:00:00Z
date_updated: 2021-01-12T06:48:57Z
day: '30'
department:
- _id: GaTk
doi: 10.1088/1742-5468/aa4e8f
ec_funded: 1
intvolume: ' 2016'
issue: '12'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1606.09048
month: '12'
oa: 1
oa_version: Preprint
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: ' Journal of Statistical Mechanics: Theory and Experiment'
publication_status: published
publisher: IOPscience
publist_id: '6165'
quality_controlled: '1'
scopus_import: 1
status: public
title: Asymptotic analysis of noisy fitness maximization, applied to metabolism &
growth
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 2016
year: '2016'
...
---
_id: '1189'
abstract:
- lang: eng
text: "Within the scope of this thesis, we show that a driven-dissipative system
with\r\nfew ultracold atoms can exhibit dissipatively bound states, even if the
atom-atom\r\ninteraction is purely repulsive. This bond arises due to the dipole-dipole
inter-\r\naction, which is restricted to one of the lower electronic energy states,
resulting\r\nin the distance-dependent coherent population trapping. The quality
of this al-\r\nready established method of dissipative binding is improved and
the application\r\nis extended to higher dimensions and a larger number of atoms.
\ Here, we simu-\r\nlate two- and three-atom systems using an adapted approach
to the Monte Carlo\r\nwave-function method and analyse the results. Finally,
\ we examine the possi-\r\nbility of finding a setting allowing trimer
\ states but prohibiting dimer states.\r\nIn the context of open quantum systems,
such a three-body bound states corre-\r\nsponds to the driven-dissipative analogue
of a Borromean state. These states can\r\nbe detected in modern experiments with
dipolar and Rydberg-dressed ultracold\r\natomic gases.\r\n"
article_processing_charge: No
author:
- first_name: Clemens
full_name: Jochum, Clemens
last_name: Jochum
citation:
ama: Jochum C. Dissipative Few-Body Quantum Systems. 2016.
apa: Jochum, C. (2016). Dissipative Few-Body Quantum Systems. Technical University
Vienna.
chicago: Jochum, Clemens. “Dissipative Few-Body Quantum Systems.” Technical University
Vienna, 2016.
ieee: C. Jochum, “Dissipative Few-Body Quantum Systems,” Technical University Vienna,
2016.
ista: Jochum C. 2016. Dissipative Few-Body Quantum Systems. Technical University
Vienna.
mla: Jochum, Clemens. Dissipative Few-Body Quantum Systems. Technical University
Vienna, 2016.
short: C. Jochum, Dissipative Few-Body Quantum Systems, Technical University Vienna,
2016.
date_created: 2018-12-11T11:50:37Z
date_published: 2016-11-28T00:00:00Z
date_updated: 2021-01-12T06:48:57Z
day: '28'
extern: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://repositum.tuwien.ac.at/obvutwhs/content/titleinfo/1517088
month: '11'
oa: 1
oa_version: Published Version
page: '94'
publication_status: published
publisher: Technical University Vienna
publist_id: '6164'
status: public
supervisor:
- first_name: Mikhail
full_name: Lemeshko, Mikhail
id: 37CB05FA-F248-11E8-B48F-1D18A9856A87
last_name: Lemeshko
orcid: 0000-0002-6990-7802
- first_name: Peter
full_name: Rabl, Peter
last_name: Rabl
title: Dissipative Few-Body Quantum Systems
type: dissertation
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '11891'
abstract:
- lang: eng
text: "We study dynamic (1+\U0001D716)-approximation algorithms for the all-pairs
shortest paths problem in unweighted undirected \U0001D45B-node \U0001D45A-edge
graphs under edge deletions. The fastest algorithm for this problem is a randomized
algorithm with a total update time of \U0001D442̃ (\U0001D45A\U0001D45B/\U0001D716)
and constant query time by Roditty and Zwick [SIAM J. Comput., 41 (2012), pp.
670--683]. The fastest deterministic algorithm is from a 1981 paper by Even and
Shiloach [J. ACM, 28 (1981), pp. 1--4]; it has a total update time of \U0001D442(\U0001D45A\U0001D45B2)
and constant query time. We improve these results as follows: (1) We present an
algorithm with a total update time of \U0001D442̃ (\U0001D45B5/2/\U0001D716) and
constant query time that has an additive error of 2 in addition to the 1+\U0001D716
multiplicative error. This beats the previous \U0001D442̃ (\U0001D45A\U0001D45B/\U0001D716)
time when \U0001D45A=Ω(\U0001D45B3/2). Note that the additive error is unavoidable
since, even in the static case, an \U0001D442(\U0001D45B3−\U0001D6FF)-time (a
so-called truly subcubic) combinatorial algorithm with 1+\U0001D716 multiplicative
error cannot have an additive error less than 2−\U0001D716, unless we make a major
breakthrough for Boolean matrix multiplication [D. Dor, S. Halrepin, and U. Zwick,
SIAM J. Comput., 29 (2000), pp. 1740--1759] and many other long-standing problems
[V. Vassilevska Williams and R. Williams, Proceedings of the 2010 IEEE 51st Annual
Symposium on Foundations of Computer Science, 2010, pp. 645--654]. The algorithm
can also be turned into a (2+\U0001D716)-approximation algorithm (without an additive
error) with the same time guarantees, improving the recent (3+\U0001D716)-approximation
algorithm with \U0001D442̃ (\U0001D45B5/2+\U0001D442(log(1/\U0001D716)/log\U0001D45B√))
running time of Bernstein and Roditty [Proceedings of the Twenty-Second Annual
ACM-SIAM Symposium on Discrete Algorithms, 2011, pp. 1355--1365] in terms of both
approximation and time guarantees. (2) We present a deterministic algorithm with
a total update time of \U0001D442̃ (\U0001D45A\U0001D45B/\U0001D716) and a query
time of \U0001D442(loglog\U0001D45B). The algorithm has a multiplicative error
of 1+\U0001D716 and gives the first improved deterministic algorithm since 1981.
It also answers an open question raised by Bernstein in [Proceedings of the Forty-Fifth
Annual ACM Symposium on Theory of Computing, 2013, pp. 725--734]. The deterministic
algorithm can be turned into a deterministic fully dynamic (1+\U0001D716)-approximation
with an amortized update time of \U0001D442̃ (\U0001D45A\U0001D45B/(\U0001D716\U0001D461))
and a query time of \U0001D442̃ (\U0001D461) for every \U0001D461≤\U0001D45B√.
In order to achieve our results, we introduce two new techniques: (i) A monotone
Even--Shiloach tree algorithm which maintains a bounded-distance shortest-paths
tree on a certain type of emulator called a locally persevering emulator. (ii)
A derandomization technique based on moving Even--Shiloach trees as a way to derandomize
the standard random set argument. These techniques might be of independent interest."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Sebastian
full_name: Krinninger, Sebastian
last_name: Krinninger
- first_name: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
citation:
ama: 'Henzinger MH, Krinninger S, Nanongkai D. Dynamic approximate all-pairs shortest
paths: Breaking the O(mn) barrier and derandomization. SIAM Journal on Computing.
2016;45(3):947-1006. doi:10.1137/140957299'
apa: 'Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2016). Dynamic approximate
all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM
Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/140957299'
chicago: 'Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Dynamic
Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.”
SIAM Journal on Computing. Society for Industrial & Applied Mathematics,
2016. https://doi.org/10.1137/140957299.'
ieee: 'M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Dynamic approximate all-pairs
shortest paths: Breaking the O(mn) barrier and derandomization,” SIAM Journal
on Computing, vol. 45, no. 3. Society for Industrial & Applied Mathematics,
pp. 947–1006, 2016.'
ista: 'Henzinger MH, Krinninger S, Nanongkai D. 2016. Dynamic approximate all-pairs
shortest paths: Breaking the O(mn) barrier and derandomization. SIAM Journal on
Computing. 45(3), 947–1006.'
mla: 'Henzinger, Monika H., et al. “Dynamic Approximate All-Pairs Shortest Paths:
Breaking the O(Mn) Barrier and Derandomization.” SIAM Journal on Computing,
vol. 45, no. 3, Society for Industrial & Applied Mathematics, 2016, pp. 947–1006,
doi:10.1137/140957299.'
short: M.H. Henzinger, S. Krinninger, D. Nanongkai, SIAM Journal on Computing 45
(2016) 947–1006.
date_created: 2022-08-17T08:37:00Z
date_published: 2016-05-01T00:00:00Z
date_updated: 2023-02-17T14:21:40Z
day: '01'
doi: 10.1137/140957299
extern: '1'
external_id:
arxiv:
- '1308.0776'
intvolume: ' 45'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1308.0776
month: '05'
oa: 1
oa_version: Preprint
page: 947-1006
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: Society for Industrial & Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and
derandomization'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 45
year: '2016'
...