---
_id: '1063'
abstract:
- lang: eng
text: Severe environmental change can drive a population extinct unless the population
adapts in time to the new conditions (“evolutionary rescue”). How does biparental
sexual reproduction influence the chances of population persistence compared to
clonal reproduction or selfing? In this article, we set up a one‐locus two‐allele
model for adaptation in diploid species, where rescue is contingent on the establishment
of the mutant homozygote. Reproduction can occur by random mating, selfing, or
clonally. Random mating generates and destroys the rescue mutant; selfing is efficient
at generating it but at the same time depletes the heterozygote, which can lead
to a low mutant frequency in the standing genetic variation. Due to these (and
other) antagonistic effects, we find a nontrivial dependence of population survival
on the rate of sex/selfing, which is strongly influenced by the dominance coefficient
of the mutation before and after the environmental change. Importantly, since
mating with the wild‐type breaks the mutant homozygote up, a slow decay of the
wild‐type population size can impede rescue in randomly mating populations.
article_processing_charge: No
author:
- first_name: Hildegard
full_name: Uecker, Hildegard
id: 2DB8F68A-F248-11E8-B48F-1D18A9856A87
last_name: Uecker
orcid: 0000-0001-9435-2813
citation:
ama: Uecker H. Evolutionary rescue in randomly mating, selfing, and clonal populations.
Evolution. 2017;71(4):845-858. doi:10.1111/evo.13191
apa: Uecker, H. (2017). Evolutionary rescue in randomly mating, selfing, and clonal
populations. Evolution. Wiley-Blackwell. https://doi.org/10.1111/evo.13191
chicago: Uecker, Hildegard. “Evolutionary Rescue in Randomly Mating, Selfing, and
Clonal Populations.” Evolution. Wiley-Blackwell, 2017. https://doi.org/10.1111/evo.13191.
ieee: H. Uecker, “Evolutionary rescue in randomly mating, selfing, and clonal populations,”
Evolution, vol. 71, no. 4. Wiley-Blackwell, pp. 845–858, 2017.
ista: Uecker H. 2017. Evolutionary rescue in randomly mating, selfing, and clonal
populations. Evolution. 71(4), 845–858.
mla: Uecker, Hildegard. “Evolutionary Rescue in Randomly Mating, Selfing, and Clonal
Populations.” Evolution, vol. 71, no. 4, Wiley-Blackwell, 2017, pp. 845–58,
doi:10.1111/evo.13191.
short: H. Uecker, Evolution 71 (2017) 845–858.
date_created: 2018-12-11T11:49:57Z
date_published: 2017-04-01T00:00:00Z
date_updated: 2025-05-28T11:42:51Z
day: '01'
department:
- _id: NiBa
doi: 10.1111/evo.13191
ec_funded: 1
external_id:
isi:
- '000398545200003'
intvolume: ' 71'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://biorxiv.org/content/early/2016/10/14/081042
month: '04'
oa: 1
oa_version: Submitted Version
page: 845 - 858
project:
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
publication: Evolution
publication_identifier:
issn:
- '00143820'
publication_status: published
publisher: Wiley-Blackwell
publist_id: '6327'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Evolutionary rescue in randomly mating, selfing, and clonal populations
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 71
year: '2017'
...
---
_id: '1065'
abstract:
- lang: eng
text: 'We consider the problem of reachability in pushdown graphs. We study the
problem for pushdown graphs with constant treewidth. Even for pushdown graphs
with treewidth 1, for the reachability problem we establish the following: (i)
the problem is PTIME-complete, and (ii) any subcubic algorithm for the problem
would contradict the k-clique conjecture and imply faster combinatorial algorithms
for cliques in graphs.'
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Georg F
full_name: Osang, Georg F
id: 464B40D6-F248-11E8-B48F-1D18A9856A87
last_name: Osang
orcid: 0000-0002-8882-5116
citation:
ama: Chatterjee K, Osang GF. Pushdown reachability with constant treewidth. Information
Processing Letters. 2017;122:25-29. doi:10.1016/j.ipl.2017.02.003
apa: Chatterjee, K., & Osang, G. F. (2017). Pushdown reachability with constant
treewidth. Information Processing Letters. Elsevier. https://doi.org/10.1016/j.ipl.2017.02.003
chicago: Chatterjee, Krishnendu, and Georg F Osang. “Pushdown Reachability with
Constant Treewidth.” Information Processing Letters. Elsevier, 2017. https://doi.org/10.1016/j.ipl.2017.02.003.
ieee: K. Chatterjee and G. F. Osang, “Pushdown reachability with constant treewidth,”
Information Processing Letters, vol. 122. Elsevier, pp. 25–29, 2017.
ista: Chatterjee K, Osang GF. 2017. Pushdown reachability with constant treewidth.
Information Processing Letters. 122, 25–29.
mla: Chatterjee, Krishnendu, and Georg F. Osang. “Pushdown Reachability with Constant
Treewidth.” Information Processing Letters, vol. 122, Elsevier, 2017, pp.
25–29, doi:10.1016/j.ipl.2017.02.003.
short: K. Chatterjee, G.F. Osang, Information Processing Letters 122 (2017) 25–29.
date_created: 2018-12-11T11:49:57Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2023-09-20T12:08:18Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
- _id: HeEd
doi: 10.1016/j.ipl.2017.02.003
ec_funded: 1
external_id:
isi:
- '000399506600005'
file:
- access_level: open_access
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:17Z
date_updated: 2019-10-15T07:44:51Z
file_id: '4998'
file_name: IST-2018-991-v1+2_2018_Chatterjee_Pushdown_PREPRINT.pdf
file_size: 247657
relation: main_file
file_date_updated: 2019-10-15T07:44:51Z
has_accepted_license: '1'
intvolume: ' 122'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 25 - 29
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication: Information Processing Letters
publication_identifier:
issn:
- '00200190'
publication_status: published
publisher: Elsevier
publist_id: '6323'
pubrep_id: '991'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Pushdown reachability with constant treewidth
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 122
year: '2017'
...
---
_id: '1180'
abstract:
- lang: eng
text: In this article we define an algebraic vertex of a generalized polyhedron
and show that the set of algebraic vertices is the smallest set of points needed
to define the polyhedron. We prove that the indicator function of a generalized
polytope P is a linear combination of indicator functions of simplices whose vertices
are algebraic vertices of P. We also show that the indicator function of any generalized
polyhedron is a linear combination, with integer coefficients, of indicator functions
of cones with apices at algebraic vertices and line-cones. The concept of an algebraic
vertex is closely related to the Fourier–Laplace transform. We show that a point
v is an algebraic vertex of a generalized polyhedron P if and only if the tangent
cone of P, at v, has non-zero Fourier–Laplace transform.
article_processing_charge: No
author:
- first_name: Arseniy
full_name: Akopyan, Arseniy
id: 430D2C90-F248-11E8-B48F-1D18A9856A87
last_name: Akopyan
orcid: 0000-0002-2548-617X
- first_name: Imre
full_name: Bárány, Imre
last_name: Bárány
- first_name: Sinai
full_name: Robins, Sinai
last_name: Robins
citation:
ama: Akopyan A, Bárány I, Robins S. Algebraic vertices of non-convex polyhedra.
Advances in Mathematics. 2017;308:627-644. doi:10.1016/j.aim.2016.12.026
apa: Akopyan, A., Bárány, I., & Robins, S. (2017). Algebraic vertices of non-convex
polyhedra. Advances in Mathematics. Academic Press. https://doi.org/10.1016/j.aim.2016.12.026
chicago: Akopyan, Arseniy, Imre Bárány, and Sinai Robins. “Algebraic Vertices of
Non-Convex Polyhedra.” Advances in Mathematics. Academic Press, 2017. https://doi.org/10.1016/j.aim.2016.12.026.
ieee: A. Akopyan, I. Bárány, and S. Robins, “Algebraic vertices of non-convex polyhedra,”
Advances in Mathematics, vol. 308. Academic Press, pp. 627–644, 2017.
ista: Akopyan A, Bárány I, Robins S. 2017. Algebraic vertices of non-convex polyhedra.
Advances in Mathematics. 308, 627–644.
mla: Akopyan, Arseniy, et al. “Algebraic Vertices of Non-Convex Polyhedra.” Advances
in Mathematics, vol. 308, Academic Press, 2017, pp. 627–44, doi:10.1016/j.aim.2016.12.026.
short: A. Akopyan, I. Bárány, S. Robins, Advances in Mathematics 308 (2017) 627–644.
date_created: 2018-12-11T11:50:34Z
date_published: 2017-02-21T00:00:00Z
date_updated: 2023-09-20T11:21:27Z
day: '21'
department:
- _id: HeEd
doi: 10.1016/j.aim.2016.12.026
ec_funded: 1
external_id:
isi:
- '000409292900015'
intvolume: ' 308'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1508.07594
month: '02'
oa: 1
oa_version: Submitted Version
page: 627 - 644
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Advances in Mathematics
publication_identifier:
issn:
- '00018708'
publication_status: published
publisher: Academic Press
publist_id: '6173'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Algebraic vertices of non-convex polyhedra
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 308
year: '2017'
...
---
_id: '11829'
abstract:
- lang: eng
text: "In recent years it has become popular to study dynamic problems in a sensitivity
setting: Instead of allowing for an arbitrary sequence of updates, the sensitivity
model only allows to apply batch updates of small size to the original input data.
The sensitivity model is particularly appealing since recent strong conditional
lower bounds ruled out fast algorithms for many dynamic problems, such as shortest
paths, reachability, or subgraph connectivity.\r\n\r\nIn this paper we prove conditional
lower bounds for these and additional problems in a sensitivity setting. For example,
we show that under the Boolean Matrix Multiplication (BMM) conjecture combinatorial
algorithms cannot compute the (4/3-\\varepsilon)-approximate diameter of an undirected
unweighted dense graph with truly subcubic preprocessing time and truly subquadratic
update/query time. This result is surprising since in the static setting it is
not clear whether a reduction from BMM to diameter is possible. We further show
under the BMM conjecture that many problems, such as reachability or approximate
shortest paths, cannot be solved faster than by recomputation from scratch even
after only one or two edge insertions. We extend our reduction from BMM to Diameter
to give a reduction from All Pairs Shortest Paths to Diameter under one deletion
in weighted graphs. This is intriguing, as in the static setting it is a big open
problem whether Diameter is as hard as APSP. We further get a nearly tight lower
bound for shortest paths after two edge deletions based on the APSP conjecture.
We give more lower bounds under the Strong Exponential Time Hypothesis. Many of
our lower bounds also hold for static oracle data structures where no sensitivity
is required.\r\n\r\nFinally, we give the first algorithm for the (1+\\varepsilon)-approximate
radius, diameter, and eccentricity problems in directed or undirected unweighted
graphs in case of single edges failures. The algorithm has a truly subcubic running
time for graphs with a truly subquadratic number of edges; it is tight w.r.t.
the conditional lower bounds we obtain."
alternative_title:
- LIPIcs
article_number: '26'
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: Andrea
full_name: Lincoln, Andrea
last_name: Lincoln
- first_name: Stefan
full_name: Neumann, Stefan
last_name: Neumann
- first_name: Virginia
full_name: Vassilevska Williams, Virginia
last_name: Vassilevska Williams
citation:
ama: 'Henzinger MH, Lincoln A, Neumann S, Vassilevska Williams V. Conditional hardness
for sensitivity problems. In: 8th Innovations in Theoretical Computer Science
Conference. Vol 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017.
doi:10.4230/LIPICS.ITCS.2017.26'
apa: 'Henzinger, M. H., Lincoln, A., Neumann, S., & Vassilevska Williams, V.
(2017). Conditional hardness for sensitivity problems. In 8th Innovations in
Theoretical Computer Science Conference (Vol. 67). Berkley, CA, United States:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2017.26'
chicago: Henzinger, Monika H, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska
Williams. “Conditional Hardness for Sensitivity Problems.” In 8th Innovations
in Theoretical Computer Science Conference, Vol. 67. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2017. https://doi.org/10.4230/LIPICS.ITCS.2017.26.
ieee: M. H. Henzinger, A. Lincoln, S. Neumann, and V. Vassilevska Williams, “Conditional
hardness for sensitivity problems,” in 8th Innovations in Theoretical Computer
Science Conference, Berkley, CA, United States, 2017, vol. 67.
ista: 'Henzinger MH, Lincoln A, Neumann S, Vassilevska Williams V. 2017. Conditional
hardness for sensitivity problems. 8th Innovations in Theoretical Computer Science
Conference. ITCS: Innovations in Theoretical Computer Science Conference, LIPIcs,
vol. 67, 26.'
mla: Henzinger, Monika H., et al. “Conditional Hardness for Sensitivity Problems.”
8th Innovations in Theoretical Computer Science Conference, vol. 67, 26,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ITCS.2017.26.
short: M.H. Henzinger, A. Lincoln, S. Neumann, V. Vassilevska Williams, in:, 8th
Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2017.
conference:
end_date: 2017-01-11
location: Berkley, CA, United States
name: 'ITCS: Innovations in Theoretical Computer Science Conference'
start_date: 2017-01-09
date_created: 2022-08-12T08:55:33Z
date_published: 2017-11-28T00:00:00Z
date_updated: 2023-02-16T11:49:15Z
day: '28'
doi: 10.4230/LIPICS.ITCS.2017.26
extern: '1'
external_id:
arxiv:
- '1703.01638'
intvolume: ' 67'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPICS.ITCS.2017.26
month: '11'
oa: 1
oa_version: Published Version
publication: 8th Innovations in Theoretical Computer Science Conference
publication_identifier:
isbn:
- '9783959770293'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Conditional hardness for sensitivity problems
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 67
year: '2017'
...
---
_id: '11831'
abstract:
- lang: eng
text: "Graph Sparsification aims at compressing large graphs into smaller ones while
(approximately) preserving important characteristics of the input graph. In this
work we study Vertex Sparsifiers, i.e., sparsifiers whose goal is to reduce the
number of vertices. Given a weighted graph G=(V,E), and a terminal set K with
|K|=k, a quality-q vertex cut sparsifier of G is a graph H with K contained in
V_H that preserves the value of minimum cuts separating any bipartition of K,
up to a factor of q. We show that planar graphs with all the k terminals lying
on the same face admit quality-1 vertex cut sparsifier of size O(k^2) that are
also planar. Our result extends to vertex flow and distance sparsifiers. It improves
the previous best known bound of O(k^2 2^(2k)) for cut and flow sparsifiers by
an exponential factor, and matches an Omega(k^2) lower-bound for this class of
graphs.\r\n\r\nWe also study vertex reachability sparsifiers for directed graphs.
Given a digraph G=(V,E) and a terminal set K, a vertex reachability sparsifier
of G is a digraph H=(V_H,E_H), K contained in V_H that preserves all reachability
information among terminal pairs. We introduce the notion of reachability-preserving
minors, i.e., we require H to be a minor of G. Among others, for general planar
digraphs, we construct reachability-preserving minors of size O(k^2 log^2 k).
We complement our upper-bound by showing that there exists an infinite family
of acyclic planar digraphs such that any reachability-preserving minor must have
Omega(k^2) vertices."
alternative_title:
- LIPIcs
article_number: '44'
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: Pan
full_name: Peng, Pan
last_name: Peng
citation:
ama: 'Goranci G, Henzinger MH, Peng P. Improved guarantees for vertex sparsification
in planar graphs. In: 25th Annual European Symposium on Algorithms. Vol
87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.44'
apa: 'Goranci, G., Henzinger, M. H., & Peng, P. (2017). Improved guarantees
for vertex sparsification in planar graphs. In 25th Annual European Symposium
on Algorithms (Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPICS.ESA.2017.44'
chicago: Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Improved Guarantees
for Vertex Sparsification in Planar Graphs.” In 25th Annual European Symposium
on Algorithms, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2017. https://doi.org/10.4230/LIPICS.ESA.2017.44.
ieee: G. Goranci, M. H. Henzinger, and P. Peng, “Improved guarantees for vertex
sparsification in planar graphs,” in 25th Annual European Symposium on Algorithms,
Vienna, Austria, 2017, vol. 87.
ista: 'Goranci G, Henzinger MH, Peng P. 2017. Improved guarantees for vertex sparsification
in planar graphs. 25th Annual European Symposium on Algorithms. ESA: Annual European
Symposium on Algorithms, LIPIcs, vol. 87, 44.'
mla: Goranci, Gramoz, et al. “Improved Guarantees for Vertex Sparsification in Planar
Graphs.” 25th Annual European Symposium on Algorithms, vol. 87, 44, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ESA.2017.44.
short: G. Goranci, M.H. Henzinger, P. Peng, in:, 25th Annual European Symposium
on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
conference:
end_date: 2017-09-06
location: Vienna, Austria
name: 'ESA: Annual European Symposium on Algorithms'
start_date: 2017-09-04
date_created: 2022-08-12T09:27:11Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2023-02-21T16:32:16Z
day: '01'
doi: 10.4230/LIPICS.ESA.2017.44
extern: '1'
external_id:
arxiv:
- '1702.01136'
intvolume: ' 87'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPIcs.ESA.2017.44
month: '09'
oa: 1
oa_version: Published Version
publication: 25th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- 978-3-95977-049-1
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '11894'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Improved guarantees for vertex sparsification in planar graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 87
year: '2017'
...
---
_id: '11832'
abstract:
- lang: eng
text: "In this paper, we study the problem of opening centers to cluster a set of
clients in a metric space so as to minimize the sum of the costs of the centers
and of the cluster radii, in a dynamic environment where clients arrive and depart,
and the solution must be updated efficiently while remaining competitive with
respect to the current optimal solution. We call this dynamic sum-of-radii clustering
problem.\r\n\r\nWe present a data structure that maintains a solution whose cost
is within a constant factor of the cost of an optimal solution in metric spaces
with bounded doubling dimension and whose worst-case update time is logarithmic
in the parameters of the problem."
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: Dariusz
full_name: Leniowski, Dariusz
last_name: Leniowski
- first_name: Claire
full_name: Mathieu, Claire
last_name: Mathieu
citation:
ama: 'Henzinger MH, Leniowski D, Mathieu C. Dynamic clustering to minimize the sum
of radii. In: 25th Annual European Symposium on Algorithms. Vol 87. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.48'
apa: 'Henzinger, M. H., Leniowski, D., & Mathieu, C. (2017). Dynamic clustering
to minimize the sum of radii. In 25th Annual European Symposium on Algorithms
(Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPICS.ESA.2017.48'
chicago: Henzinger, Monika H, Dariusz Leniowski, and Claire Mathieu. “Dynamic Clustering
to Minimize the Sum of Radii.” In 25th Annual European Symposium on Algorithms,
Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ESA.2017.48.
ieee: M. H. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize
the sum of radii,” in 25th Annual European Symposium on Algorithms, Vienna,
Austria, 2017, vol. 87.
ista: 'Henzinger MH, Leniowski D, Mathieu C. 2017. Dynamic clustering to minimize
the sum of radii. 25th Annual European Symposium on Algorithms. ESA: Annual European
Symposium on Algorithms, LIPIcs, vol. 87, 48.'
mla: Henzinger, Monika H., et al. “Dynamic Clustering to Minimize the Sum of Radii.”
25th Annual European Symposium on Algorithms, vol. 87, 48, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ESA.2017.48.
short: M.H. Henzinger, D. Leniowski, C. Mathieu, in:, 25th Annual European Symposium
on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
conference:
end_date: 2017-09-06
location: Vienna, Austria
name: 'ESA: Annual European Symposium on Algorithms'
start_date: 2017-09-04
date_created: 2022-08-12T09:58:46Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2023-02-16T11:54:12Z
day: '01'
doi: 10.4230/LIPICS.ESA.2017.48
extern: '1'
external_id:
arxiv:
- '1707.02577'
intvolume: ' 87'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPICS.ESA.2017.48
month: '09'
oa: 1
oa_version: Published Version
publication: 25th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- 978-3-95977-049-1
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic clustering to minimize the sum of radii
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 87
year: '2017'
...
---
_id: '11833'
abstract:
- lang: eng
text: "We introduce a new algorithmic framework for designing dynamic graph algorithms
in minor-free graphs, by exploiting the structure of such graphs and a tool called
vertex sparsification, which is a way to compress large graphs into small ones
that well preserve relevant properties among a subset of vertices and has previously
mainly been used in the design of approximation algorithms.\r\n\r\nUsing this
framework, we obtain a Monte Carlo randomized fully dynamic algorithm for (1 +
epsilon)-approximating the energy of electrical flows in n-vertex planar graphs
with tilde{O}(r epsilon^{-2}) worst-case update time and tilde{O}((r + n / sqrt{r})
epsilon^{-2}) worst-case query time, for any r larger than some constant. For
r=n^{2/3}, this gives tilde{O}(n^{2/3} epsilon^{-2}) update time and tilde{O}(n^{2/3}
epsilon^{-2}) query time. We also extend this algorithm to work for minor-free
graphs with similar approximation and running time guarantees. Furthermore, we
illustrate our framework on the all-pairs max flow and shortest path problems
by giving corresponding dynamic algorithms in minor-free graphs with both sublinear
update and query times. To the best of our knowledge, our results are the first
to systematically establish such a connection between dynamic graph algorithms
and vertex sparsification.\r\n\r\nWe also present both upper bound and lower bound
for maintaining the energy of electrical flows in the incremental subgraph model,
where updates consist of only vertex activations, which might be of independent
interest."
alternative_title:
- LIPIcs
article_number: '45'
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: Pan
full_name: Peng, Pan
last_name: Peng
citation:
ama: 'Goranci G, Henzinger MH, Peng P. The power of vertex sparsifiers in dynamic
graph algorithms. In: 25th Annual European Symposium on Algorithms. Vol
87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.45'
apa: 'Goranci, G., Henzinger, M. H., & Peng, P. (2017). The power of vertex
sparsifiers in dynamic graph algorithms. In 25th Annual European Symposium
on Algorithms (Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPICS.ESA.2017.45'
chicago: Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “The Power of Vertex
Sparsifiers in Dynamic Graph Algorithms.” In 25th Annual European Symposium
on Algorithms, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2017. https://doi.org/10.4230/LIPICS.ESA.2017.45.
ieee: G. Goranci, M. H. Henzinger, and P. Peng, “The power of vertex sparsifiers
in dynamic graph algorithms,” in 25th Annual European Symposium on Algorithms,
Vienna, Austria, 2017, vol. 87.
ista: 'Goranci G, Henzinger MH, Peng P. 2017. The power of vertex sparsifiers in
dynamic graph algorithms. 25th Annual European Symposium on Algorithms. ESA: Annual
European Symposium on Algorithms, LIPIcs, vol. 87, 45.'
mla: Goranci, Gramoz, et al. “The Power of Vertex Sparsifiers in Dynamic Graph Algorithms.”
25th Annual European Symposium on Algorithms, vol. 87, 45, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ESA.2017.45.
short: G. Goranci, M.H. Henzinger, P. Peng, in:, 25th Annual European Symposium
on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
conference:
end_date: 2017-09-06
location: Vienna, Austria
name: 'ESA: Annual European Symposium on Algorithms'
start_date: 2017-09-04
date_created: 2022-08-12T10:46:26Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2023-02-16T11:56:37Z
day: '01'
doi: 10.4230/LIPICS.ESA.2017.45
extern: '1'
external_id:
arxiv:
- '1712.06473'
intvolume: ' 87'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPIcs.ESA.2017.45
month: '09'
oa: 1
oa_version: Published Version
publication: 25th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- 978-3-95977-049-1
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: The power of vertex sparsifiers in dynamic graph algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 87
year: '2017'
...
---
_id: '1187'
abstract:
- lang: eng
text: We construct efficient authentication protocols and message authentication
codes (MACs) whose security can be reduced to the learning parity with noise (LPN)
problem. Despite a large body of work—starting with the (Formula presented.) protocol
of Hopper and Blum in 2001—until now it was not even known how to construct an
efficient authentication protocol from LPN which is secure against man-in-the-middle
attacks. A MAC implies such a (two-round) protocol.
article_processing_charge: No
article_type: original
author:
- first_name: Eike
full_name: Kiltz, Eike
last_name: Kiltz
- 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: Daniele
full_name: Venturi, Daniele
last_name: Venturi
- first_name: David
full_name: Cash, David
last_name: Cash
- first_name: Abhishek
full_name: Jain, Abhishek
last_name: Jain
citation:
ama: Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. Efficient authentication from
hard learning problems. Journal of Cryptology. 2017;30(4):1238-1275. doi:10.1007/s00145-016-9247-3
apa: Kiltz, E., Pietrzak, K. Z., Venturi, D., Cash, D., & Jain, A. (2017). Efficient
authentication from hard learning problems. Journal of Cryptology. Springer.
https://doi.org/10.1007/s00145-016-9247-3
chicago: Kiltz, Eike, Krzysztof Z Pietrzak, Daniele Venturi, David Cash, and Abhishek
Jain. “Efficient Authentication from Hard Learning Problems.” Journal of Cryptology.
Springer, 2017. https://doi.org/10.1007/s00145-016-9247-3.
ieee: E. Kiltz, K. Z. Pietrzak, D. Venturi, D. Cash, and A. Jain, “Efficient authentication
from hard learning problems,” Journal of Cryptology, vol. 30, no. 4. Springer,
pp. 1238–1275, 2017.
ista: Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. 2017. Efficient authentication
from hard learning problems. Journal of Cryptology. 30(4), 1238–1275.
mla: Kiltz, Eike, et al. “Efficient Authentication from Hard Learning Problems.”
Journal of Cryptology, vol. 30, no. 4, Springer, 2017, pp. 1238–75, doi:10.1007/s00145-016-9247-3.
short: E. Kiltz, K.Z. Pietrzak, D. Venturi, D. Cash, A. Jain, Journal of Cryptology
30 (2017) 1238–1275.
date_created: 2018-12-11T11:50:37Z
date_published: 2017-10-01T00:00:00Z
date_updated: 2023-09-20T11:20:58Z
day: '01'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.1007/s00145-016-9247-3
ec_funded: 1
external_id:
isi:
- '000410788600007'
file:
- access_level: open_access
checksum: c647520d115b772a1682fc06fa273eb1
content_type: application/pdf
creator: dernst
date_created: 2020-05-14T16:30:17Z
date_updated: 2020-07-14T12:44:37Z
file_id: '7843'
file_name: 2017_JournalCrypto_Kiltz.pdf
file_size: 516959
relation: main_file
file_date_updated: 2020-07-14T12:44:37Z
has_accepted_license: '1'
intvolume: ' 30'
isi: 1
issue: '4'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 1238 - 1275
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: Journal of Cryptology
publication_status: published
publisher: Springer
publist_id: '6166'
quality_controlled: '1'
related_material:
record:
- id: '3238'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Efficient authentication from hard learning problems
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 30
year: '2017'
...
---
_id: '11873'
abstract:
- lang: eng
text: "We study the problem of computing a minimum cut in a simple, undirected graph
and give a deterministic O(m log2 n log log2 n) time algorithm. This improves
both on the best previously known deterministic running time of O(m log12 n) (Kawarabayashi
and Thorup [12]) and the best previously known randomized running time of O(mlog3n)
(Karger [11]) for this problem, though Karger's algorithm can be further applied
to weighted graphs.\r\n\r\nOur approach is using the Kawarabayashi and Tho- rup
graph compression technique, which repeatedly finds low-conductance cuts. To find
these cuts they use a diffusion-based local algorithm. We use instead a flow-
based local algorithm and suitably adjust their framework to work with our flow-based
subroutine. Both flow and diffusion based methods have a long history of being
applied to finding low conductance cuts. Diffusion algorithms have several variants
that are naturally local while it is more complicated to make flow methods local.
Some prior work has proven nice properties for local flow based algorithms with
respect to improving or cleaning up low conductance cuts. Our flow subroutine,
however, is the first that is both local and produces low conductance cuts. Thus,
it may be of independent interest."
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: Satish
full_name: Rao, Satish
last_name: Rao
- first_name: Di
full_name: Wang, Di
last_name: Wang
citation:
ama: 'Henzinger MH, Rao S, Wang D. Local flow partitioning for faster edge connectivity.
In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for
Industrial and Applied Mathematics; 2017:1919-1938. doi:10.1137/1.9781611974782.125'
apa: 'Henzinger, M. H., Rao, S., & Wang, D. (2017). Local flow partitioning
for faster edge connectivity. In 28th Annual ACM-SIAM Symposium on Discrete
Algorithms (pp. 1919–1938). Barcelona, Spain: Society for Industrial and Applied
Mathematics. https://doi.org/10.1137/1.9781611974782.125'
chicago: Henzinger, Monika H, Satish Rao, and Di Wang. “Local Flow Partitioning
for Faster Edge Connectivity.” In 28th Annual ACM-SIAM Symposium on Discrete
Algorithms, 1919–38. Society for Industrial and Applied Mathematics, 2017.
https://doi.org/10.1137/1.9781611974782.125.
ieee: M. H. Henzinger, S. Rao, and D. Wang, “Local flow partitioning for faster
edge connectivity,” in 28th Annual ACM-SIAM Symposium on Discrete Algorithms,
Barcelona, Spain, 2017, pp. 1919–1938.
ista: 'Henzinger MH, Rao S, Wang D. 2017. Local flow partitioning for faster edge
connectivity. 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium
on Discrete Algorithms, 1919–1938.'
mla: Henzinger, Monika H., et al. “Local Flow Partitioning for Faster Edge Connectivity.”
28th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial
and Applied Mathematics, 2017, pp. 1919–38, doi:10.1137/1.9781611974782.125.
short: M.H. Henzinger, S. Rao, D. Wang, in:, 28th Annual ACM-SIAM Symposium on Discrete
Algorithms, Society for Industrial and Applied Mathematics, 2017, pp. 1919–1938.
conference:
end_date: 2017-01-19
location: Barcelona, Spain
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2017-01-16
date_created: 2022-08-16T12:20:59Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-02-21T16:32:01Z
day: '01'
doi: 10.1137/1.9781611974782.125
extern: '1'
external_id:
arxiv:
- '1704.01254'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1704.01254
month: '01'
oa: 1
oa_version: Preprint
page: 1919-1938
publication: 28th Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
eisbn:
- 978-161197478-2
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
record:
- id: '11889'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Local flow partitioning for faster edge connectivity
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '11874'
abstract:
- lang: eng
text: "We consider the problem of maintaining an approximately maximum (fractional)
matching and an approximately minimum vertex cover in a dynamic graph. Starting
with the seminal paper by Onak and Rubinfeld [STOC 2010], this problem has received
significant attention in recent years. There remains, however, a polynomial gap
between the best known worst case update time and the best known amortised update
time for this problem, even after allowing for randomisation. Specifically, Bernstein
and Stein [ICALP 2015, SODA 2016] have the best known worst case update time.
They present a deterministic data structure with approximation ratio (3/2 + ∊)
and worst case update time O(m1/4/ ∊2), where m is the number of edges in the
graph. In recent past, Gupta and Peng [FOCS 2013] gave a deterministic data structure
with approximation ratio (1+ ∊) and worst case update time No known randomised
data structure beats the worst case update times of these two results. In contrast,
the paper by Onak and Rubinfeld [STOC 2010] gave a randomised data structure with
approximation ratio O(1) and amortised update time O(log2 n), where n is the number
of nodes in the graph. This was later improved by Baswana, Gupta and Sen [FOCS
2011] and Solomon [FOCS 2016], leading to a randomised date structure with approximation
ratio 2 and amortised update time O(1).\r\n\r\nWe bridge the polynomial gap between
the worst case and amortised update times for this problem, without using any
randomisation. We present a deterministic data structure with approximation ratio
(2 + ∊) and worst case update time O(log3 n), for all sufficiently small constants
∊."
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. Fully dynamic approximate maximum
matching and minimum vertex cover in o(log3 n) worst case update time. In: 28th
Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 0. Society for Industrial
and Applied Mathematics; 2017:470-489. doi:10.1137/1.9781611974782.30'
apa: 'Bhattacharya, S., Henzinger, M. H., & Nanongkai, D. (2017). Fully dynamic
approximate maximum matching and minimum vertex cover in o(log3 n) worst case
update time. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms (Vol.
0, pp. 470–489). Barcelona, Spain: Society for Industrial and Applied Mathematics.
https://doi.org/10.1137/1.9781611974782.30'
chicago: Bhattacharya, Sayan, Monika H Henzinger, and Danupon Nanongkai. “Fully
Dynamic Approximate Maximum Matching and Minimum Vertex Cover in o(Log3 n) Worst
Case Update Time.” In 28th Annual ACM-SIAM Symposium on Discrete Algorithms,
0:470–89. Society for Industrial and Applied Mathematics, 2017. https://doi.org/10.1137/1.9781611974782.30.
ieee: S. Bhattacharya, M. H. Henzinger, and D. Nanongkai, “Fully dynamic approximate
maximum matching and minimum vertex cover in o(log3 n) worst case update time,”
in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain,
2017, vol. 0, pp. 470–489.
ista: 'Bhattacharya S, Henzinger MH, Nanongkai D. 2017. Fully dynamic approximate
maximum matching and minimum vertex cover in o(log3 n) worst case update time.
28th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete
Algorithms vol. 0, 470–489.'
mla: Bhattacharya, Sayan, et al. “Fully Dynamic Approximate Maximum Matching and
Minimum Vertex Cover in o(Log3 n) Worst Case Update Time.” 28th Annual ACM-SIAM
Symposium on Discrete Algorithms, vol. 0, Society for Industrial and Applied
Mathematics, 2017, pp. 470–89, doi:10.1137/1.9781611974782.30.
short: S. Bhattacharya, M.H. Henzinger, D. Nanongkai, in:, 28th Annual ACM-SIAM
Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics,
2017, pp. 470–489.
conference:
end_date: 2017-01-19
location: Barcelona, Spain
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2017-01-16
date_created: 2022-08-16T12:28:27Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-02-17T11:54:22Z
day: '01'
doi: 10.1137/1.9781611974782.30
extern: '1'
external_id:
arxiv:
- '1704.02844'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1704.02844
month: '01'
oa: 1
oa_version: Preprint
page: 470 - 489
publication: 28th Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
eisbn:
- 978-161197478-2
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully dynamic approximate maximum matching and minimum vertex cover in o(log3
n) worst case update time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: '0'
year: '2017'
...
---
_id: '11903'
abstract:
- lang: eng
text: "Online social networks allow the collection of large amounts of data about
the influence between users connected by a friendship-like relationship. When
distributing items among agents forming a social network, this information allows
us to exploit network externalities that each agent receives from his neighbors
that get the same item. In this paper we consider Friends-of-Friends (2-hop) network
externalities, i.e., externalities that not only depend on the neighbors that
get the same item but also on neighbors of neighbors. For these externalities
we study a setting where multiple different items are assigned to unit-demand
agents. Specifically, we study the problem of welfare maximization under different
types of externality functions. Let n be the number of agents and m be the number
of items. Our contributions are the following: (1) We show that welfare maximization
is APX-hard; we show that even for step functions with 2-hop (and also with 1-hop)
externalities it is NP-hard to approximate social welfare better than (1−1/e).
(2) On the positive side we present (i) an \U0001D442(\U0001D45B√)-approximation
algorithm for general concave externality functions, (ii) an O(log m)-approximation
algorithm for linear externality functions, and (iii) a 518(1−1/\U0001D452)-approximation
algorithm for 2-hop step function externalities. We also improve the result from
[7] for 1-hop step function externalities by giving a 12(1−1/\U0001D452)-approximation
algorithm."
article_processing_charge: No
article_type: original
author:
- first_name: Sayan
full_name: Bhattacharya, Sayan
last_name: Bhattacharya
- first_name: Wolfgang
full_name: Dvořák, Wolfgang
last_name: Dvořák
- 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: Martin
full_name: Starnberger, Martin
last_name: Starnberger
citation:
ama: Bhattacharya S, Dvořák W, Henzinger MH, Starnberger M. Welfare maximization
with friends-of-friends network externalities. Theory of Computing Systems.
2017;61(4):948-986. doi:10.1007/s00224-017-9759-8
apa: Bhattacharya, S., Dvořák, W., Henzinger, M. H., & Starnberger, M. (2017).
Welfare maximization with friends-of-friends network externalities. Theory
of Computing Systems. Springer Nature. https://doi.org/10.1007/s00224-017-9759-8
chicago: Bhattacharya, Sayan, Wolfgang Dvořák, Monika H Henzinger, and Martin Starnberger.
“Welfare Maximization with Friends-of-Friends Network Externalities.” Theory
of Computing Systems. Springer Nature, 2017. https://doi.org/10.1007/s00224-017-9759-8.
ieee: S. Bhattacharya, W. Dvořák, M. H. Henzinger, and M. Starnberger, “Welfare
maximization with friends-of-friends network externalities,” Theory of Computing
Systems, vol. 61, no. 4. Springer Nature, pp. 948–986, 2017.
ista: Bhattacharya S, Dvořák W, Henzinger MH, Starnberger M. 2017. Welfare maximization
with friends-of-friends network externalities. Theory of Computing Systems. 61(4),
948–986.
mla: Bhattacharya, Sayan, et al. “Welfare Maximization with Friends-of-Friends Network
Externalities.” Theory of Computing Systems, vol. 61, no. 4, Springer Nature,
2017, pp. 948–86, doi:10.1007/s00224-017-9759-8.
short: S. Bhattacharya, W. Dvořák, M.H. Henzinger, M. Starnberger, Theory of Computing
Systems 61 (2017) 948–986.
date_created: 2022-08-17T11:14:12Z
date_published: 2017-11-01T00:00:00Z
date_updated: 2023-02-21T16:29:58Z
day: '01'
doi: 10.1007/s00224-017-9759-8
extern: '1'
intvolume: ' 61'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/s00224-017-9759-8
month: '11'
oa: 1
oa_version: Published Version
page: 948-986
publication: Theory of Computing Systems
publication_identifier:
eissn:
- 1433-0490
issn:
- 1432-4350
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11837'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Welfare maximization with friends-of-friends network externalities
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 61
year: '2017'
...
---
_id: '1191'
abstract:
- lang: eng
text: Variation in genotypes may be responsible for differences in dispersal rates,
directional biases, and growth rates of individuals. These traits may favor certain
genotypes and enhance their spatiotemporal spreading into areas occupied by the
less advantageous genotypes. We study how these factors influence the speed of
spreading in the case of two competing genotypes under the assumption that spatial
variation of the total population is small compared to the spatial variation of
the frequencies of the genotypes in the population. In that case, the dynamics
of the frequency of one of the genotypes is approximately described by a generalized
Fisher–Kolmogorov–Petrovskii–Piskunov (F–KPP) equation. This generalized F–KPP
equation with (nonlinear) frequency-dependent diffusion and advection terms admits
traveling wave solutions that characterize the invasion of the dominant genotype.
Our existence results generalize the classical theory for traveling waves for
the F–KPP with constant coefficients. Moreover, in the particular case of the
quadratic (monostable) nonlinear growth–decay rate in the generalized F–KPP we
study in detail the influence of the variance in diffusion and mean displacement
rates of the two genotypes on the minimal wave propagation speed.
acknowledgement: "We thank Nick Barton, Katarína Bod’ová, and Sr\r\n-\r\ndan Sarikas
for constructive feed-\r\nback and support. Furthermore, we would like to express
our deep gratitude to the anonymous referees (one\r\nof whom, Jimmy Garnier, agreed
to reveal his identity) and the editor Max Souza, for very helpful and\r\ndetailed
comments and suggestions that significantly helped us to improve the manuscript.
This project has\r\nreceived funding from the European Union’s Seventh Framework
Programme for research, technological\r\ndevelopment and demonstration under Grant
Agreement 618091 Speed of Adaptation in Population Genet-\r\nics and Evolutionary
Computation (SAGE) and the European Research Council (ERC) Grant No. 250152\r\n(SN),
from the Scientific Grant Agency of the Slovak Republic under the Grant 1/0459/13
and by the Slovak\r\nResearch and Development Agency under the Contract No. APVV-14-0378
(RK). RK would also like to\r\nthank IST Austria for its hospitality during the
work on this project."
author:
- first_name: Richard
full_name: Kollár, Richard
last_name: Kollár
- first_name: Sebastian
full_name: Novak, Sebastian
id: 461468AE-F248-11E8-B48F-1D18A9856A87
last_name: Novak
orcid: 0000-0002-2519-824X
citation:
ama: Kollár R, Novak S. Existence of traveling waves for the generalized F–KPP equation.
Bulletin of Mathematical Biology. 2017;79(3):525-559. doi:10.1007/s11538-016-0244-3
apa: Kollár, R., & Novak, S. (2017). Existence of traveling waves for the generalized
F–KPP equation. Bulletin of Mathematical Biology. Springer. https://doi.org/10.1007/s11538-016-0244-3
chicago: Kollár, Richard, and Sebastian Novak. “Existence of Traveling Waves for
the Generalized F–KPP Equation.” Bulletin of Mathematical Biology. Springer,
2017. https://doi.org/10.1007/s11538-016-0244-3.
ieee: R. Kollár and S. Novak, “Existence of traveling waves for the generalized
F–KPP equation,” Bulletin of Mathematical Biology, vol. 79, no. 3. Springer,
pp. 525–559, 2017.
ista: Kollár R, Novak S. 2017. Existence of traveling waves for the generalized
F–KPP equation. Bulletin of Mathematical Biology. 79(3), 525–559.
mla: Kollár, Richard, and Sebastian Novak. “Existence of Traveling Waves for the
Generalized F–KPP Equation.” Bulletin of Mathematical Biology, vol. 79,
no. 3, Springer, 2017, pp. 525–59, doi:10.1007/s11538-016-0244-3.
short: R. Kollár, S. Novak, Bulletin of Mathematical Biology 79 (2017) 525–559.
date_created: 2018-12-11T11:50:38Z
date_published: 2017-03-01T00:00:00Z
date_updated: 2025-05-28T11:42:46Z
day: '01'
department:
- _id: NiBa
doi: 10.1007/s11538-016-0244-3
ec_funded: 1
intvolume: ' 79'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1607.00944
month: '03'
oa: 1
oa_version: Preprint
page: 525-559
project:
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '618091'
name: Speed of Adaptation in Population Genetics and Evolutionary Computation
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
publication: Bulletin of Mathematical Biology
publication_status: published
publisher: Springer
publist_id: '6160'
quality_controlled: '1'
scopus_import: 1
status: public
title: Existence of traveling waves for the generalized F–KPP equation
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 79
year: '2017'
...
---
_id: '1192'
abstract:
- lang: eng
text: The main result of this paper is a generalization of the classical blossom
algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean
CSPs where each variable appears in exactly two constraints (we call it edge CSP)
and all constraints are even Δ-matroid relations (represented by lists of tuples).
As a consequence of this, we settle the complexity classification of planar Boolean
CSPs started by Dvorak and Kupec. Knowing that edge CSP is tractable for even
Δ-matroid constraints allows us to extend the tractability result to a larger
class of Δ-matroids that includes many classes that were known to be tractable
before, namely co-independent, compact, local and binary.
article_processing_charge: No
author:
- first_name: Alexandr
full_name: Kazda, Alexandr
id: 3B32BAA8-F248-11E8-B48F-1D18A9856A87
last_name: Kazda
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
ama: 'Kazda A, Kolmogorov V, Rolinek M. Even delta-matroids and the complexity of
planar Boolean CSPs. In: SIAM; 2017:307-326. doi:10.1137/1.9781611974782.20'
apa: 'Kazda, A., Kolmogorov, V., & Rolinek, M. (2017). Even delta-matroids and
the complexity of planar Boolean CSPs (pp. 307–326). Presented at the SODA: Symposium
on Discrete Algorithms, Barcelona, Spain: SIAM. https://doi.org/10.1137/1.9781611974782.20'
chicago: Kazda, Alexandr, Vladimir Kolmogorov, and Michal Rolinek. “Even Delta-Matroids
and the Complexity of Planar Boolean CSPs,” 307–26. SIAM, 2017. https://doi.org/10.1137/1.9781611974782.20.
ieee: 'A. Kazda, V. Kolmogorov, and M. Rolinek, “Even delta-matroids and the complexity
of planar Boolean CSPs,” presented at the SODA: Symposium on Discrete Algorithms,
Barcelona, Spain, 2017, pp. 307–326.'
ista: 'Kazda A, Kolmogorov V, Rolinek M. 2017. Even delta-matroids and the complexity
of planar Boolean CSPs. SODA: Symposium on Discrete Algorithms, 307–326.'
mla: Kazda, Alexandr, et al. Even Delta-Matroids and the Complexity of Planar
Boolean CSPs. SIAM, 2017, pp. 307–26, doi:10.1137/1.9781611974782.20.
short: A. Kazda, V. Kolmogorov, M. Rolinek, in:, SIAM, 2017, pp. 307–326.
conference:
end_date: 2017-01019
location: Barcelona, Spain
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2017-01-16
date_created: 2018-12-11T11:50:38Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-09-20T11:20:26Z
day: '01'
department:
- _id: VlKo
doi: 10.1137/1.9781611974782.20
ec_funded: 1
external_id:
isi:
- '000426965800020'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1602.03124
month: '01'
oa: 1
oa_version: Submitted Version
page: 307 - 326
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
isbn:
- 978-161197478-2
publication_status: published
publisher: SIAM
publist_id: '6159'
quality_controlled: '1'
related_material:
record:
- id: '6032'
relation: later_version
status: public
status: public
title: Even delta-matroids and the complexity of planar Boolean CSPs
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...
---
_id: '1194'
abstract:
- lang: eng
text: 'Termination is one of the basic liveness properties, and we study the termination
problem for probabilistic programs with real-valued variables. Previous works
focused on the qualitative problem that asks whether an input program terminates
with probability~1 (almost-sure termination). A powerful approach for this qualitative
problem is the notion of ranking supermartingales with respect to a given set
of invariants. The quantitative problem (probabilistic termination) asks for bounds
on the termination probability. A fundamental and conceptual drawback of the existing
approaches to address probabilistic termination is that even though the supermartingales
consider the probabilistic behavior of the programs, the invariants are obtained
completely ignoring the probabilistic aspect. In this work we address the probabilistic
termination problem for linear-arithmetic probabilistic programs with nondeterminism.
We define the notion of {\em stochastic invariants}, which are constraints along
with a probability bound that the constraints hold. We introduce a concept of
{\em repulsing supermartingales}. First, we show that repulsing supermartingales
can be used to obtain bounds on the probability of the stochastic invariants.
Second, we show the effectiveness of repulsing supermartingales in the following
three ways: (1)~With a combination of ranking and repulsing supermartingales we
can compute lower bounds on the probability of termination; (2)~repulsing supermartingales
provide witnesses for refutation of almost-sure termination; and (3)~with a combination
of ranking and repulsing supermartingales we can establish persistence properties
of probabilistic programs. We also present results on related computational problems
and an experimental evaluation of our approach on academic examples. '
alternative_title:
- ACM SIGPLAN Notices
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Petr
full_name: Novotny, Petr
id: 3CC3B868-F248-11E8-B48F-1D18A9856A87
last_name: Novotny
- first_name: Djordje
full_name: Zikelic, Djordje
last_name: Zikelic
citation:
ama: 'Chatterjee K, Novotný P, Zikelic D. Stochastic invariants for probabilistic
termination. In: Vol 52. ACM; 2017:145-160. doi:10.1145/3009837.3009873'
apa: 'Chatterjee, K., Novotný, P., & Zikelic, D. (2017). Stochastic invariants
for probabilistic termination (Vol. 52, pp. 145–160). Presented at the POPL: Principles
of Programming Languages, Paris, France: ACM. https://doi.org/10.1145/3009837.3009873'
chicago: Chatterjee, Krishnendu, Petr Novotný, and Djordje Zikelic. “Stochastic
Invariants for Probabilistic Termination,” 52:145–60. ACM, 2017. https://doi.org/10.1145/3009837.3009873.
ieee: 'K. Chatterjee, P. Novotný, and D. Zikelic, “Stochastic invariants for probabilistic
termination,” presented at the POPL: Principles of Programming Languages, Paris,
France, 2017, vol. 52, no. 1, pp. 145–160.'
ista: 'Chatterjee K, Novotný P, Zikelic D. 2017. Stochastic invariants for probabilistic
termination. POPL: Principles of Programming Languages, ACM SIGPLAN Notices, vol.
52, 145–160.'
mla: Chatterjee, Krishnendu, et al. Stochastic Invariants for Probabilistic Termination.
Vol. 52, no. 1, ACM, 2017, pp. 145–60, doi:10.1145/3009837.3009873.
short: K. Chatterjee, P. Novotný, D. Zikelic, in:, ACM, 2017, pp. 145–160.
conference:
end_date: 2017-01-21
location: Paris, France
name: 'POPL: Principles of Programming Languages'
start_date: 2017-01-15
date_created: 2018-12-11T11:50:39Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2025-07-14T09:09:58Z
day: '01'
department:
- _id: KrCh
doi: 10.1145/3009837.3009873
ec_funded: 1
external_id:
isi:
- '000408311200013'
intvolume: ' 52'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1611.01063
month: '01'
oa: 1
oa_version: Submitted Version
page: 145 - 160
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_identifier:
issn:
- '07308566'
publication_status: published
publisher: ACM
publist_id: '6157'
quality_controlled: '1'
related_material:
record:
- id: '14539'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Stochastic invariants for probabilistic termination
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 52
year: '2017'
...
---
_id: '1196'
abstract:
- lang: eng
text: 'We define the . model-measuring problem: given a model . M and specification
. ϕ, what is the maximal distance . ρ such that all models . M'' within distance
. ρ from . M satisfy (or violate) . ϕ. The model-measuring problem presupposes
a distance function on models. We concentrate on . automatic distance functions,
which are defined by weighted automata. The model-measuring problem subsumes several
generalizations of the classical model-checking problem, in particular, quantitative
model-checking problems that measure the degree of satisfaction of a specification;
robustness problems that measure how much a model can be perturbed without violating
the specification; and parameter synthesis for hybrid systems. We show that for
automatic distance functions, and (a) . ω-regular linear-time, (b) . ω-regular
branching-time, and (c) hybrid specifications, the model-measuring problem can
be solved.We use automata-theoretic model-checking methods for model measuring,
replacing the emptiness question for word, tree, and hybrid automata by the .
optimal-value question for the weighted versions of these automata. For automata
over words and trees, we consider weighted automata that accumulate weights by
maximizing, summing, discounting, and limit averaging. For hybrid automata, we
consider monotonic (parametric) hybrid automata, a hybrid counterpart of (discrete)
weighted automata.We give several examples of using the model-measuring problem
to compute various notions of robustness and quantitative satisfaction for temporal
specifications. Further, we propose the modeling framework for model measuring
to ease the specification and reduce the likelihood of errors in modeling.Finally,
we present a variant of the model-measuring problem, called the . model-repair
problem. The model-repair problem applies to models that do not satisfy the specification;
it can be used to derive restrictions, under which the model satisfies the specification,
i.e., to repair the model.'
acknowledgement: "This research was supported in part by the European Research Council
(ERC) under grant 267989 (QUAREM), by the Austrian Science Fund1 (FWF) under grants
S11402-N23 (RiSE) and Z211-N23 (Wittgenstein Award), and by the National Science
Centre (NCN), Poland under grant 2014/15/D/ST6/04543.\r\nA Technical Report of this
article is available via: https://repository.ist.ac.at/171/"
article_processing_charge: No
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
citation:
ama: 'Henzinger TA, Otop J. Model measuring for discrete and hybrid systems. Nonlinear
Analysis: Hybrid Systems. 2017;23:166-190. doi:10.1016/j.nahs.2016.09.001'
apa: 'Henzinger, T. A., & Otop, J. (2017). Model measuring for discrete and
hybrid systems. Nonlinear Analysis: Hybrid Systems. Elsevier. https://doi.org/10.1016/j.nahs.2016.09.001'
chicago: 'Henzinger, Thomas A, and Jan Otop. “Model Measuring for Discrete and Hybrid
Systems.” Nonlinear Analysis: Hybrid Systems. Elsevier, 2017. https://doi.org/10.1016/j.nahs.2016.09.001.'
ieee: 'T. A. Henzinger and J. Otop, “Model measuring for discrete and hybrid systems,”
Nonlinear Analysis: Hybrid Systems, vol. 23. Elsevier, pp. 166–190, 2017.'
ista: 'Henzinger TA, Otop J. 2017. Model measuring for discrete and hybrid systems.
Nonlinear Analysis: Hybrid Systems. 23, 166–190.'
mla: 'Henzinger, Thomas A., and Jan Otop. “Model Measuring for Discrete and Hybrid
Systems.” Nonlinear Analysis: Hybrid Systems, vol. 23, Elsevier, 2017,
pp. 166–90, doi:10.1016/j.nahs.2016.09.001.'
short: 'T.A. Henzinger, J. Otop, Nonlinear Analysis: Hybrid Systems 23 (2017) 166–190.'
date_created: 2018-12-11T11:50:39Z
date_published: 2017-02-01T00:00:00Z
date_updated: 2023-09-20T11:18:50Z
day: '01'
department:
- _id: ToHe
doi: 10.1016/j.nahs.2016.09.001
ec_funded: 1
external_id:
isi:
- '000390637000011'
intvolume: ' 23'
isi: 1
language:
- iso: eng
month: '02'
oa_version: None
page: 166 - 190
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
publication: 'Nonlinear Analysis: Hybrid Systems'
publication_status: published
publisher: Elsevier
publist_id: '6154'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Model measuring for discrete and hybrid systems
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 23
year: '2017'
...
---
_id: '11961'
abstract:
- lang: eng
text: Flow chemistry involves the use of channels or tubing to conduct a reaction
in a continuous stream rather than in a flask. Flow equipment provides chemists
with unique control over reaction parameters enhancing reactivity or in some cases
enabling new reactions. This relatively young technology has received a remarkable
amount of attention in the past decade with many reports on what can be done in
flow. Until recently, however, the question, “Should we do this in flow?” has
merely been an afterthought. This review introduces readers to the basic principles
and fundamentals of flow chemistry and critically discusses recent flow chemistry
accounts.
article_processing_charge: No
article_type: original
author:
- first_name: Matthew B.
full_name: Plutschack, Matthew B.
last_name: Plutschack
- first_name: Bartholomäus
full_name: Pieber, Bartholomäus
id: 93e5e5b2-0da6-11ed-8a41-af589a024726
last_name: Pieber
orcid: 0000-0001-8689-388X
- first_name: Kerry
full_name: Gilmore, Kerry
last_name: Gilmore
- first_name: Peter H.
full_name: Seeberger, Peter H.
last_name: Seeberger
citation:
ama: Plutschack MB, Pieber B, Gilmore K, Seeberger PH. The Hitchhiker’s Guide to
flow chemistry. Chemical Reviews. 2017;117(18):11796-11893. doi:10.1021/acs.chemrev.7b00183
apa: Plutschack, M. B., Pieber, B., Gilmore, K., & Seeberger, P. H. (2017).
The Hitchhiker’s Guide to flow chemistry. Chemical Reviews. American Chemical
Society. https://doi.org/10.1021/acs.chemrev.7b00183
chicago: Plutschack, Matthew B., Bartholomäus Pieber, Kerry Gilmore, and Peter H.
Seeberger. “The Hitchhiker’s Guide to Flow Chemistry.” Chemical Reviews.
American Chemical Society, 2017. https://doi.org/10.1021/acs.chemrev.7b00183.
ieee: M. B. Plutschack, B. Pieber, K. Gilmore, and P. H. Seeberger, “The Hitchhiker’s
Guide to flow chemistry,” Chemical Reviews, vol. 117, no. 18. American
Chemical Society, pp. 11796–11893, 2017.
ista: Plutschack MB, Pieber B, Gilmore K, Seeberger PH. 2017. The Hitchhiker’s Guide
to flow chemistry. Chemical Reviews. 117(18), 11796–11893.
mla: Plutschack, Matthew B., et al. “The Hitchhiker’s Guide to Flow Chemistry.”
Chemical Reviews, vol. 117, no. 18, American Chemical Society, 2017, pp.
11796–893, doi:10.1021/acs.chemrev.7b00183.
short: M.B. Plutschack, B. Pieber, K. Gilmore, P.H. Seeberger, Chemical Reviews
117 (2017) 11796–11893.
date_created: 2022-08-24T11:07:46Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2023-02-21T10:09:28Z
day: '01'
doi: 10.1021/acs.chemrev.7b00183
extern: '1'
external_id:
pmid:
- '28570059'
intvolume: ' 117'
issue: '18'
language:
- iso: eng
month: '06'
oa_version: None
page: 11796-11893
pmid: 1
publication: Chemical Reviews
publication_identifier:
eissn:
- 1520-6890
issn:
- 0009-2665
publication_status: published
publisher: American Chemical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: The Hitchhiker’s Guide to flow chemistry
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 117
year: '2017'
...
---
_id: '11976'
abstract:
- lang: eng
text: The way organic multistep synthesis is performed is changing due to the adoption
of flow chemical techniques, which has enabled the development of improved methods
to make complex molecules. The modular nature of the technique provides not only
access to target molecules via linear flow approaches but also for the targeting
of structural cores with single systems. This perspective article summarizes the
state of the art of continuous multistep synthesis and discusses the main challenges
and opportunities in this area.
article_processing_charge: No
article_type: original
author:
- first_name: Bartholomäus
full_name: Pieber, Bartholomäus
id: 93e5e5b2-0da6-11ed-8a41-af589a024726
last_name: Pieber
orcid: 0000-0001-8689-388X
- first_name: Kerry
full_name: Gilmore, Kerry
last_name: Gilmore
- first_name: Peter H.
full_name: Seeberger, Peter H.
last_name: Seeberger
citation:
ama: Pieber B, Gilmore K, Seeberger PH. Integrated flow processing - challenges
in continuous multistep synthesis. Journal of Flow Chemistry. 2017;7(3-4):129-136.
doi:10.1556/1846.2017.00016
apa: Pieber, B., Gilmore, K., & Seeberger, P. H. (2017). Integrated flow processing
- challenges in continuous multistep synthesis. Journal of Flow Chemistry.
AKJournals. https://doi.org/10.1556/1846.2017.00016
chicago: Pieber, Bartholomäus, Kerry Gilmore, and Peter H. Seeberger. “Integrated
Flow Processing - Challenges in Continuous Multistep Synthesis.” Journal of
Flow Chemistry. AKJournals, 2017. https://doi.org/10.1556/1846.2017.00016.
ieee: B. Pieber, K. Gilmore, and P. H. Seeberger, “Integrated flow processing -
challenges in continuous multistep synthesis,” Journal of Flow Chemistry,
vol. 7, no. 3–4. AKJournals, pp. 129–136, 2017.
ista: Pieber B, Gilmore K, Seeberger PH. 2017. Integrated flow processing - challenges
in continuous multistep synthesis. Journal of Flow Chemistry. 7(3–4), 129–136.
mla: Pieber, Bartholomäus, et al. “Integrated Flow Processing - Challenges in Continuous
Multistep Synthesis.” Journal of Flow Chemistry, vol. 7, no. 3–4, AKJournals,
2017, pp. 129–36, doi:10.1556/1846.2017.00016.
short: B. Pieber, K. Gilmore, P.H. Seeberger, Journal of Flow Chemistry 7 (2017)
129–136.
date_created: 2022-08-25T10:47:51Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2023-02-21T10:10:02Z
day: '01'
doi: 10.1556/1846.2017.00016
extern: '1'
intvolume: ' 7'
issue: 3-4
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1556/1846.2017.00016
month: '09'
oa: 1
oa_version: Published Version
page: 129-136
publication: Journal of Flow Chemistry
publication_identifier:
eissn:
- 2063-0212
issn:
- 2062-249X
publication_status: published
publisher: AKJournals
quality_controlled: '1'
scopus_import: '1'
status: public
title: Integrated flow processing - challenges in continuous multistep synthesis
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7
year: '2017'
...
---
_id: '1198'
abstract:
- lang: eng
text: We consider a model of fermions interacting via point interactions, defined
via a certain weighted Dirichlet form. While for two particles the interaction
corresponds to infinite scattering length, the presence of further particles effectively
decreases the interaction strength. We show that the model becomes trivial in
the thermodynamic limit, in the sense that the free energy density at any given
particle density and temperature agrees with the corresponding expression for
non-interacting particles.
acknowledgement: 'Open access funding provided by Institute of Science and Technology
(IST Austria). '
article_processing_charge: Yes (via OA deal)
author:
- first_name: Thomas
full_name: Moser, Thomas
id: 2B5FC9A4-F248-11E8-B48F-1D18A9856A87
last_name: Moser
- first_name: Robert
full_name: Seiringer, Robert
id: 4AFD0470-F248-11E8-B48F-1D18A9856A87
last_name: Seiringer
orcid: 0000-0002-6781-0521
citation:
ama: Moser T, Seiringer R. Triviality of a model of particles with point interactions
in the thermodynamic limit. Letters in Mathematical Physics. 2017;107(3):533-552.
doi:10.1007/s11005-016-0915-x
apa: Moser, T., & Seiringer, R. (2017). Triviality of a model of particles with
point interactions in the thermodynamic limit. Letters in Mathematical Physics.
Springer. https://doi.org/10.1007/s11005-016-0915-x
chicago: Moser, Thomas, and Robert Seiringer. “Triviality of a Model of Particles
with Point Interactions in the Thermodynamic Limit.” Letters in Mathematical
Physics. Springer, 2017. https://doi.org/10.1007/s11005-016-0915-x.
ieee: T. Moser and R. Seiringer, “Triviality of a model of particles with point
interactions in the thermodynamic limit,” Letters in Mathematical Physics,
vol. 107, no. 3. Springer, pp. 533–552, 2017.
ista: Moser T, Seiringer R. 2017. Triviality of a model of particles with point
interactions in the thermodynamic limit. Letters in Mathematical Physics. 107(3),
533–552.
mla: Moser, Thomas, and Robert Seiringer. “Triviality of a Model of Particles with
Point Interactions in the Thermodynamic Limit.” Letters in Mathematical Physics,
vol. 107, no. 3, Springer, 2017, pp. 533–52, doi:10.1007/s11005-016-0915-x.
short: T. Moser, R. Seiringer, Letters in Mathematical Physics 107 (2017) 533–552.
date_created: 2018-12-11T11:50:40Z
date_published: 2017-03-01T00:00:00Z
date_updated: 2023-09-20T11:18:13Z
day: '01'
ddc:
- '510'
- '539'
department:
- _id: RoSe
doi: 10.1007/s11005-016-0915-x
external_id:
isi:
- '000394280200007'
file:
- access_level: open_access
checksum: c0c835def162c1bc52f978fad26e3c2f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:40Z
date_updated: 2020-07-14T12:44:38Z
file_id: '5296'
file_name: IST-2016-723-v1+1_s11005-016-0915-x.pdf
file_size: 587207
relation: main_file
file_date_updated: 2020-07-14T12:44:38Z
has_accepted_license: '1'
intvolume: ' 107'
isi: 1
issue: '3'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: ' 533 - 552'
project:
- _id: 25C878CE-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P27533_N27
name: Structure of the Excitation Spectrum for Many-Body Quantum Systems
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Letters in Mathematical Physics
publication_identifier:
issn:
- '03779017'
publication_status: published
publisher: Springer
publist_id: '6152'
pubrep_id: '723'
quality_controlled: '1'
related_material:
record:
- id: '52'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Triviality of a model of particles with point interactions in the thermodynamic
limit
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 107
year: '2017'
...
---
_id: '1199'
abstract:
- lang: eng
text: Much of quantitative genetics is based on the ‘infinitesimal model’, under
which selection has a negligible effect on the genetic variance. This is typically
justified by assuming a very large number of loci with additive effects. However,
it applies even when genes interact, provided that the number of loci is large
enough that selection on each of them is weak relative to random drift. In the
long term, directional selection will change allele frequencies, but even then,
the effects of epistasis on the ultimate change in trait mean due to selection
may be modest. Stabilising selection can maintain many traits close to their optima,
even when the underlying alleles are weakly selected. However, the number of traits
that can be optimised is apparently limited to ~4Ne by the ‘drift load’, and this
is hard to reconcile with the apparent complexity of many organisms. Just as for
the mutation load, this limit can be evaded by a particular form of negative epistasis.
A more robust limit is set by the variance in reproductive success. This suggests
that selection accumulates information most efficiently in the infinitesimal regime,
when selection on individual alleles is weak, and comparable with random drift.
A review of evidence on selection strength suggests that although most variance
in fitness may be because of alleles with large Nes, substantial amounts of adaptation
may be because of alleles in the infinitesimal regime, in which epistasis has
modest effects.
article_processing_charge: No
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
citation:
ama: Barton NH. How does epistasis influence the response to selection? Heredity.
2017;118:96-109. doi:10.1038/hdy.2016.109
apa: Barton, N. H. (2017). How does epistasis influence the response to selection?
Heredity. Nature Publishing Group. https://doi.org/10.1038/hdy.2016.109
chicago: Barton, Nicholas H. “How Does Epistasis Influence the Response to Selection?”
Heredity. Nature Publishing Group, 2017. https://doi.org/10.1038/hdy.2016.109.
ieee: N. H. Barton, “How does epistasis influence the response to selection?,” Heredity,
vol. 118. Nature Publishing Group, pp. 96–109, 2017.
ista: Barton NH. 2017. How does epistasis influence the response to selection? Heredity.
118, 96–109.
mla: Barton, Nicholas H. “How Does Epistasis Influence the Response to Selection?”
Heredity, vol. 118, Nature Publishing Group, 2017, pp. 96–109, doi:10.1038/hdy.2016.109.
short: N.H. Barton, Heredity 118 (2017) 96–109.
date_created: 2018-12-11T11:50:40Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2025-05-28T11:42:47Z
day: '01'
department:
- _id: NiBa
doi: 10.1038/hdy.2016.109
ec_funded: 1
external_id:
isi:
- '000392229100011'
intvolume: ' 118'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5176114/
month: '01'
oa: 1
oa_version: Submitted Version
page: 96 - 109
project:
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
publication: Heredity
publication_status: published
publisher: Nature Publishing Group
publist_id: '6151'
quality_controlled: '1'
related_material:
record:
- id: '9710'
relation: research_data
status: public
scopus_import: '1'
status: public
title: How does epistasis influence the response to selection?
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 118
year: '2017'
...
---
_id: '1207'
abstract:
- lang: eng
text: The eigenvalue distribution of the sum of two large Hermitian matrices, when
one of them is conjugated by a Haar distributed unitary matrix, is asymptotically
given by the free convolution of their spectral distributions. We prove that this
convergence also holds locally in the bulk of the spectrum, down to the optimal
scales larger than the eigenvalue spacing. The corresponding eigenvectors are
fully delocalized. Similar results hold for the sum of two real symmetric matrices,
when one is conjugated by Haar orthogonal matrix.
article_processing_charge: Yes (via OA deal)
author:
- first_name: Zhigang
full_name: Bao, Zhigang
id: 442E6A6C-F248-11E8-B48F-1D18A9856A87
last_name: Bao
orcid: 0000-0003-3036-1475
- first_name: László
full_name: Erdös, László
id: 4DBD5372-F248-11E8-B48F-1D18A9856A87
last_name: Erdös
orcid: 0000-0001-5366-9603
- first_name: Kevin
full_name: Schnelli, Kevin
id: 434AD0AE-F248-11E8-B48F-1D18A9856A87
last_name: Schnelli
orcid: 0000-0003-0954-3231
citation:
ama: Bao Z, Erdös L, Schnelli K. Local law of addition of random matrices on optimal
scale. Communications in Mathematical Physics. 2017;349(3):947-990. doi:10.1007/s00220-016-2805-6
apa: Bao, Z., Erdös, L., & Schnelli, K. (2017). Local law of addition of random
matrices on optimal scale. Communications in Mathematical Physics. Springer.
https://doi.org/10.1007/s00220-016-2805-6
chicago: Bao, Zhigang, László Erdös, and Kevin Schnelli. “Local Law of Addition
of Random Matrices on Optimal Scale.” Communications in Mathematical Physics.
Springer, 2017. https://doi.org/10.1007/s00220-016-2805-6.
ieee: Z. Bao, L. Erdös, and K. Schnelli, “Local law of addition of random matrices
on optimal scale,” Communications in Mathematical Physics, vol. 349, no.
3. Springer, pp. 947–990, 2017.
ista: Bao Z, Erdös L, Schnelli K. 2017. Local law of addition of random matrices
on optimal scale. Communications in Mathematical Physics. 349(3), 947–990.
mla: Bao, Zhigang, et al. “Local Law of Addition of Random Matrices on Optimal Scale.”
Communications in Mathematical Physics, vol. 349, no. 3, Springer, 2017,
pp. 947–90, doi:10.1007/s00220-016-2805-6.
short: Z. Bao, L. Erdös, K. Schnelli, Communications in Mathematical Physics 349
(2017) 947–990.
date_created: 2018-12-11T11:50:43Z
date_published: 2017-02-01T00:00:00Z
date_updated: 2023-09-20T11:16:57Z
day: '01'
ddc:
- '530'
department:
- _id: LaEr
doi: 10.1007/s00220-016-2805-6
ec_funded: 1
external_id:
isi:
- '000393696700005'
file:
- access_level: open_access
checksum: ddff79154c3daf27237de5383b1264a9
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:14:47Z
date_updated: 2020-07-14T12:44:39Z
file_id: '5102'
file_name: IST-2016-722-v1+1_s00220-016-2805-6.pdf
file_size: 1033743
relation: main_file
file_date_updated: 2020-07-14T12:44:39Z
has_accepted_license: '1'
intvolume: ' 349'
isi: 1
issue: '3'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: 947 - 990
project:
- _id: 258DCDE6-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '338804'
name: Random matrices, universality and disordered quantum systems
publication: Communications in Mathematical Physics
publication_identifier:
issn:
- '00103616'
publication_status: published
publisher: Springer
publist_id: '6141'
pubrep_id: '722'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Local law of addition of random matrices on optimal scale
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 349
year: '2017'
...