---
_id: '8188'
abstract:
- lang: eng
text: "A natural approach to generative modeling of videos is to represent them
as a composition of moving objects. Recent works model a set of 2D sprites over
a slowly-varying background, but without considering the underlying 3D scene that\r\ngives
rise to them. We instead propose to model a video as the view seen while moving
through a scene with multiple 3D objects and a 3D background. Our model is trained
from monocular videos without any supervision, yet learns to\r\ngenerate coherent
3D scenes containing several moving objects. We conduct detailed experiments on
two datasets, going beyond the visual complexity supported by state-of-the-art
generative approaches. We evaluate our method on\r\ndepth-prediction and 3D object
detection---tasks which cannot be addressed by those earlier works---and show
it out-performs them even on 2D instance segmentation and tracking."
acknowledged_ssus:
- _id: ScienComp
acknowledgement: "This research was supported by the Scientific Service Units (SSU)
of IST Austria through resources\r\nprovided by Scientific Computing (SciComp).
PH is employed part-time by Blackford Analysis, but\r\nthey did not support this
project in any way."
article_processing_charge: No
author:
- first_name: Paul M
full_name: Henderson, Paul M
id: 13C09E74-18D9-11E9-8878-32CFE5697425
last_name: Henderson
orcid: 0000-0002-5198-7445
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Henderson PM, Lampert C. Unsupervised object-centric video generation and
decomposition in 3D. In: 34th Conference on Neural Information Processing Systems.
Vol 33. Curran Associates; 2020:3106–3117.'
apa: 'Henderson, P. M., & Lampert, C. (2020). Unsupervised object-centric video
generation and decomposition in 3D. In 34th Conference on Neural Information
Processing Systems (Vol. 33, pp. 3106–3117). Vancouver, Canada: Curran Associates.'
chicago: Henderson, Paul M, and Christoph Lampert. “Unsupervised Object-Centric
Video Generation and Decomposition in 3D.” In 34th Conference on Neural Information
Processing Systems, 33:3106–3117. Curran Associates, 2020.
ieee: P. M. Henderson and C. Lampert, “Unsupervised object-centric video generation
and decomposition in 3D,” in 34th Conference on Neural Information Processing
Systems, Vancouver, Canada, 2020, vol. 33, pp. 3106–3117.
ista: 'Henderson PM, Lampert C. 2020. Unsupervised object-centric video generation
and decomposition in 3D. 34th Conference on Neural Information Processing Systems.
NeurIPS: Neural Information Processing Systems vol. 33, 3106–3117.'
mla: Henderson, Paul M., and Christoph Lampert. “Unsupervised Object-Centric Video
Generation and Decomposition in 3D.” 34th Conference on Neural Information
Processing Systems, vol. 33, Curran Associates, 2020, pp. 3106–3117.
short: P.M. Henderson, C. Lampert, in:, 34th Conference on Neural Information Processing
Systems, Curran Associates, 2020, pp. 3106–3117.
conference:
end_date: 2020-12-12
location: Vancouver, Canada
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2020-12-06
date_created: 2020-07-31T16:59:19Z
date_published: 2020-07-07T00:00:00Z
date_updated: 2023-04-25T09:49:58Z
day: '07'
department:
- _id: ChLa
external_id:
arxiv:
- '2007.06705'
intvolume: ' 33'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2007.06705
month: '07'
oa: 1
oa_version: Preprint
page: 3106–3117
publication: 34th Conference on Neural Information Processing Systems
publication_identifier:
isbn:
- '9781713829546'
publication_status: published
publisher: Curran Associates
quality_controlled: '1'
status: public
title: Unsupervised object-centric video generation and decomposition in 3D
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 33
year: '2020'
...
---
_id: '7474'
abstract:
- lang: eng
text: This booklet is a collection of abstracts presented at the AHPC conference.
article_processing_charge: No
citation:
ama: 'Schlögl A, Kiss J, Elefante S, eds. Austrian High-Performance-Computing
Meeting (AHPC2020). Klosterneuburg, Austria: IST Austria; 2020. doi:10.15479/AT:ISTA:7474'
apa: 'Schlögl, A., Kiss, J., & Elefante, S. (Eds.). (2020). Austrian High-Performance-Computing
meeting (AHPC2020). Presented at the AHPC: Austrian High-Performance-Computing
Meeting, Klosterneuburg, Austria: IST Austria. https://doi.org/10.15479/AT:ISTA:7474'
chicago: 'Schlögl, Alois, Janos Kiss, and Stefano Elefante, eds. Austrian High-Performance-Computing
Meeting (AHPC2020). Klosterneuburg, Austria: IST Austria, 2020. https://doi.org/10.15479/AT:ISTA:7474.'
ieee: 'A. Schlögl, J. Kiss, and S. Elefante, Eds., Austrian High-Performance-Computing
meeting (AHPC2020). Klosterneuburg, Austria: IST Austria, 2020.'
ista: 'Schlögl A, Kiss J, Elefante S eds. 2020. Austrian High-Performance-Computing
meeting (AHPC2020), Klosterneuburg, Austria: IST Austria, 72p.'
mla: Schlögl, Alois, et al., editors. Austrian High-Performance-Computing Meeting
(AHPC2020). IST Austria, 2020, doi:10.15479/AT:ISTA:7474.
short: A. Schlögl, J. Kiss, S. Elefante, eds., Austrian High-Performance-Computing
Meeting (AHPC2020), IST Austria, Klosterneuburg, Austria, 2020.
conference:
end_date: 2020-02-21
location: Klosterneuburg, Austria
name: 'AHPC: Austrian High-Performance-Computing Meeting'
start_date: 2020-02-19
date_created: 2020-02-11T07:59:04Z
date_published: 2020-02-19T00:00:00Z
date_updated: 2023-05-16T07:48:28Z
day: '19'
ddc:
- '000'
department:
- _id: ScienComp
doi: 10.15479/AT:ISTA:7474
editor:
- first_name: Alois
full_name: Schlögl, Alois
id: 45BF87EE-F248-11E8-B48F-1D18A9856A87
last_name: Schlögl
orcid: 0000-0002-5621-8100
- first_name: Janos
full_name: Kiss, Janos
id: 3D3A06F8-F248-11E8-B48F-1D18A9856A87
last_name: Kiss
- first_name: Stefano
full_name: Elefante, Stefano
id: 490F40CE-F248-11E8-B48F-1D18A9856A87
last_name: Elefante
file:
- access_level: open_access
checksum: 49798edb9e57bbd6be18362d1d7b18a9
content_type: application/pdf
creator: schloegl
date_created: 2020-02-19T06:53:38Z
date_updated: 2020-07-14T12:47:59Z
file_id: '7504'
file_name: BOOKLET_AHPC2020.final.pdf
file_size: 90899507
relation: main_file
file_date_updated: 2020-07-14T12:47:59Z
has_accepted_license: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '02'
oa: 1
oa_version: Published Version
page: '72'
place: Klosterneuburg, Austria
publication_identifier:
isbn:
- 978-3-99078-004-6
publication_status: published
publisher: IST Austria
quality_controlled: '1'
status: public
title: Austrian High-Performance-Computing meeting (AHPC2020)
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: book_editor
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2020'
...
---
_id: '7808'
abstract:
- lang: eng
text: Quantization converts neural networks into low-bit fixed-point computations
which can be carried out by efficient integer-only hardware, and is standard practice
for the deployment of neural networks on real-time embedded devices. However,
like their real-numbered counterpart, quantized networks are not immune to malicious
misclassification caused by adversarial attacks. We investigate how quantization
affects a network’s robustness to adversarial attacks, which is a formal verification
question. We show that neither robustness nor non-robustness are monotonic with
changing the number of bits for the representation and, also, neither are preserved
by quantization from a real-numbered network. For this reason, we introduce a
verification method for quantized neural networks which, using SMT solving over
bit-vectors, accounts for their exact, bit-precise semantics. We built a tool
and analyzed the effect of quantization on a classifier for the MNIST dataset.
We demonstrate that, compared to our method, existing methods for the analysis
of real-numbered networks often derive false conclusions about their quantizations,
both when determining robustness and when detecting attacks, and that existing
methods for quantized networks often miss attacks. Furthermore, we applied our
method beyond robustness, showing how the number of bits in quantization enlarges
the gender bias of a predictor for students’ grades.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Mirco
full_name: Giacobbe, Mirco
id: 3444EA5E-F248-11E8-B48F-1D18A9856A87
last_name: Giacobbe
orcid: 0000-0001-8180-0904
- 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: Mathias
full_name: Lechner, Mathias
id: 3DC22916-F248-11E8-B48F-1D18A9856A87
last_name: Lechner
citation:
ama: 'Giacobbe M, Henzinger TA, Lechner M. How many bits does it take to quantize
your neural network? In: International Conference on Tools and Algorithms for
the Construction and Analysis of Systems. Vol 12079. Springer Nature; 2020:79-97.
doi:10.1007/978-3-030-45237-7_5'
apa: 'Giacobbe, M., Henzinger, T. A., & Lechner, M. (2020). How many bits does
it take to quantize your neural network? In International Conference on Tools
and Algorithms for the Construction and Analysis of Systems (Vol. 12079, pp.
79–97). Dublin, Ireland: Springer Nature. https://doi.org/10.1007/978-3-030-45237-7_5'
chicago: Giacobbe, Mirco, Thomas A Henzinger, and Mathias Lechner. “How Many Bits
Does It Take to Quantize Your Neural Network?” In International Conference
on Tools and Algorithms for the Construction and Analysis of Systems, 12079:79–97.
Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45237-7_5.
ieee: M. Giacobbe, T. A. Henzinger, and M. Lechner, “How many bits does it take
to quantize your neural network?,” in International Conference on Tools and
Algorithms for the Construction and Analysis of Systems, Dublin, Ireland,
2020, vol. 12079, pp. 79–97.
ista: 'Giacobbe M, Henzinger TA, Lechner M. 2020. How many bits does it take to
quantize your neural network? International Conference on Tools and Algorithms
for the Construction and Analysis of Systems. TACAS: Tools and Algorithms for
the Construction and Analysis of Systems, LNCS, vol. 12079, 79–97.'
mla: Giacobbe, Mirco, et al. “How Many Bits Does It Take to Quantize Your Neural
Network?” International Conference on Tools and Algorithms for the Construction
and Analysis of Systems, vol. 12079, Springer Nature, 2020, pp. 79–97, doi:10.1007/978-3-030-45237-7_5.
short: M. Giacobbe, T.A. Henzinger, M. Lechner, in:, International Conference on
Tools and Algorithms for the Construction and Analysis of Systems, Springer Nature,
2020, pp. 79–97.
conference:
end_date: 2020-04-30
location: Dublin, Ireland
name: 'TACAS: Tools and Algorithms for the Construction and Analysis of Systems'
start_date: 2020-04-25
date_created: 2020-05-10T22:00:49Z
date_published: 2020-04-17T00:00:00Z
date_updated: 2023-06-23T07:01:11Z
day: '17'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-030-45237-7_5
file:
- access_level: open_access
checksum: f19905a42891fe5ce93d69143fa3f6fb
content_type: application/pdf
creator: dernst
date_created: 2020-05-26T12:48:15Z
date_updated: 2020-07-14T12:48:03Z
file_id: '7893'
file_name: 2020_TACAS_Giacobbe.pdf
file_size: 2744030
relation: main_file
file_date_updated: 2020-07-14T12:48:03Z
has_accepted_license: '1'
intvolume: ' 12079'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 79-97
project:
- _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: International Conference on Tools and Algorithms for the Construction
and Analysis of Systems
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783030452360'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11362'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: How many bits does it take to quantize your neural network?
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12079
year: '2020'
...
---
_id: '7952'
abstract:
- lang: eng
text: "Isomanifolds are the generalization of isosurfaces to arbitrary dimension
and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued
smooth function f: ℝ^d → ℝ^(d-n). A natural (and efficient) way to approximate
an isomanifold is to consider its Piecewise-Linear (PL) approximation based on
a triangulation \U0001D4AF of the ambient space ℝ^d. In this paper, we give conditions
under which the PL-approximation of an isomanifold is topologically equivalent
to the isomanifold. The conditions are easy to satisfy in the sense that they
can always be met by taking a sufficiently fine triangulation \U0001D4AF. This
contrasts with previous results on the triangulation of manifolds where, in arbitrary
dimensions, delicate perturbations are needed to guarantee topological correctness,
which leads to strong limitations in practice. We further give a bound on the
Fréchet distance between the original isomanifold and its PL-approximation. Finally
we show analogous results for the PL-approximation of an isomanifold with boundary. "
alternative_title:
- LIPIcs
article_number: 20:1-20:18
article_processing_charge: No
author:
- first_name: Jean-Daniel
full_name: Boissonnat, Jean-Daniel
last_name: Boissonnat
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Boissonnat J-D, Wintraecken M. The topological correctness of PL-approximations
of isomanifolds. In: 36th International Symposium on Computational Geometry.
Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.20'
apa: 'Boissonnat, J.-D., & Wintraecken, M. (2020). The topological correctness
of PL-approximations of isomanifolds. In 36th International Symposium on Computational
Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.20'
chicago: Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness
of PL-Approximations of Isomanifolds.” In 36th International Symposium on Computational
Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
https://doi.org/10.4230/LIPIcs.SoCG.2020.20.
ieee: J.-D. Boissonnat and M. Wintraecken, “The topological correctness of PL-approximations
of isomanifolds,” in 36th International Symposium on Computational Geometry,
Zürich, Switzerland, 2020, vol. 164.
ista: 'Boissonnat J-D, Wintraecken M. 2020. The topological correctness of PL-approximations
of isomanifolds. 36th International Symposium on Computational Geometry. SoCG:
Symposium on Computational Geometry, LIPIcs, vol. 164, 20:1-20:18.'
mla: Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness
of PL-Approximations of Isomanifolds.” 36th International Symposium on Computational
Geometry, vol. 164, 20:1-20:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2020, doi:10.4230/LIPIcs.SoCG.2020.20.
short: J.-D. Boissonnat, M. Wintraecken, in:, 36th International Symposium on Computational
Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
end_date: 2020-06-26
location: Zürich, Switzerland
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2020-06-22
date_created: 2020-06-09T07:24:11Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2023-08-02T06:49:16Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2020.20
ec_funded: 1
file:
- access_level: open_access
checksum: 38cbfa4f5d484d267a35d44d210df044
content_type: application/pdf
creator: dernst
date_created: 2020-06-17T10:13:34Z
date_updated: 2020-07-14T12:48:06Z
file_id: '7969'
file_name: 2020_LIPIcsSoCG_Boissonnat.pdf
file_size: 1009739
relation: main_file
file_date_updated: 2020-07-14T12:48:06Z
has_accepted_license: '1'
intvolume: ' 164'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 36th International Symposium on Computational Geometry
publication_identifier:
isbn:
- 978-3-95977-143-6
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '9649'
relation: later_version
status: public
scopus_import: '1'
status: public
title: The topological correctness of PL-approximations of isomanifolds
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 164
year: '2020'
...
---
_id: '7990'
abstract:
- lang: eng
text: 'Given a finite point set P in general position in the plane, a full triangulation
is a maximal straight-line embedded plane graph on P. A partial triangulation
on P is a full triangulation of some subset P'' of P containing all extreme points
in P. A bistellar flip on a partial triangulation either flips an edge, removes
a non-extreme point of degree 3, or adds a point in P ⧵ P'' as vertex of degree
3. The bistellar flip graph has all partial triangulations as vertices, and a
pair of partial triangulations is adjacent if they can be obtained from one another
by a bistellar flip. The goal of this paper is to investigate the structure of
this graph, with emphasis on its connectivity. For sets P of n points in general
position, we show that the bistellar flip graph is (n-3)-connected, thereby answering,
for sets in general position, an open questions raised in a book (by De Loera,
Rambau, and Santos) and a survey (by Lee and Santos) on triangulations. This matches
the situation for the subfamily of regular triangulations (i.e., partial triangulations
obtained by lifting the points and projecting the lower convex hull), where (n-3)-connectivity
has been known since the late 1980s through the secondary polytope (Gelfand, Kapranov,
Zelevinsky) and Balinski’s Theorem. Our methods also yield the following results
(see the full version [Wagner and Welzl, 2020]): (i) The bistellar flip graph
can be covered by graphs of polytopes of dimension n-3 (products of secondary
polytopes). (ii) A partial triangulation is regular, if it has distance n-3 in
the Hasse diagram of the partial order of partial subdivisions from the trivial
subdivision. (iii) All partial triangulations are regular iff the trivial subdivision
has height n-3 in the partial order of partial subdivisions. (iv) There are arbitrarily
large sets P with non-regular partial triangulations, while every proper subset
has only regular triangulations, i.e., there are no small certificates for the
existence of non-regular partial triangulations (answering a question by F. Santos
in the unexpected direction).'
alternative_title:
- LIPIcs
article_number: 67:1 - 67:16
article_processing_charge: No
author:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: 'Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane
(Part II: Bistellar flips). In: 36th International Symposium on Computational
Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020.
doi:10.4230/LIPIcs.SoCG.2020.67'
apa: 'Wagner, U., & Welzl, E. (2020). Connectivity of triangulation flip graphs
in the plane (Part II: Bistellar flips). In 36th International Symposium on
Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl -
Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.67'
chicago: 'Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs
in the Plane (Part II: Bistellar Flips).” In 36th International Symposium on
Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.67.'
ieee: 'U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the
plane (Part II: Bistellar flips),” in 36th International Symposium on Computational
Geometry, Zürich, Switzerland, 2020, vol. 164.'
ista: 'Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the
plane (Part II: Bistellar flips). 36th International Symposium on Computational
Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 67:1-67:16.'
mla: 'Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in
the Plane (Part II: Bistellar Flips).” 36th International Symposium on Computational
Geometry, vol. 164, 67:1-67:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2020, doi:10.4230/LIPIcs.SoCG.2020.67.'
short: U. Wagner, E. Welzl, in:, 36th International Symposium on Computational Geometry,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
end_date: 2020-06-26
location: Zürich, Switzerland
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2020-06-22
date_created: 2020-06-22T09:14:19Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2023-08-04T08:51:07Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2020.67
external_id:
arxiv:
- '2003.13557'
file:
- access_level: open_access
checksum: 3f6925be5f3dcdb3b14cab92f410edf7
content_type: application/pdf
creator: dernst
date_created: 2020-06-23T06:37:27Z
date_updated: 2020-07-14T12:48:06Z
file_id: '8003'
file_name: 2020_LIPIcsSoCG_Wagner.pdf
file_size: 793187
relation: main_file
file_date_updated: 2020-07-14T12:48:06Z
has_accepted_license: '1'
intvolume: ' 164'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: 36th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959771436'
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '12129'
relation: later_version
status: public
scopus_import: 1
status: public
title: 'Connectivity of triangulation flip graphs in the plane (Part II: Bistellar
flips)'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 164
year: '2020'
...
---
_id: '7807'
abstract:
- lang: eng
text: "In a straight-line embedded triangulation of a point set P in the plane,
removing an inner edge and—provided the resulting quadrilateral is convex—adding
the other diagonal is called an edge flip. The (edge) flip graph has all triangulations
as vertices, and a pair of triangulations is adjacent if they can be obtained
from each other by an edge flip. The goal of this paper is to contribute to a
better understanding of the flip graph, with an emphasis on its connectivity.\r\nFor
sets in general position, it is known that every triangulation allows at least
edge flips (a tight bound) which gives the minimum degree of any flip graph for
n points. We show that for every point set P in general position, the flip graph
is at least -vertex connected. Somewhat more strongly, we show that the vertex
connectivity equals the minimum degree occurring in the flip graph, i.e. the minimum
number of flippable edges in any triangulation of P, provided P is large enough.
Finally, we exhibit some of the geometry of the flip graph by showing that the
flip graph can be covered by 1-skeletons of polytopes of dimension (products of
associahedra).\r\nA corresponding result ((n – 3)-vertex connectedness) can be
shown for the bistellar flip graph of partial triangulations, i.e. the set of
all triangulations of subsets of P which contain all extreme points of P. This
will be treated separately in a second part."
article_processing_charge: No
author:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: 'Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane
(Part I: Edge flips). In: Proceedings of the Annual ACM-SIAM Symposium on Discrete
Algorithms. Vol 2020-January. SIAM; 2020:2823-2841. doi:10.1137/1.9781611975994.172'
apa: 'Wagner, U., & Welzl, E. (2020). Connectivity of triangulation flip graphs
in the plane (Part I: Edge flips). In Proceedings of the Annual ACM-SIAM Symposium
on Discrete Algorithms (Vol. 2020–January, pp. 2823–2841). Salt Lake City,
UT, United States: SIAM. https://doi.org/10.1137/1.9781611975994.172'
chicago: 'Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs
in the Plane (Part I: Edge Flips).” In Proceedings of the Annual ACM-SIAM Symposium
on Discrete Algorithms, 2020–January:2823–41. SIAM, 2020. https://doi.org/10.1137/1.9781611975994.172.'
ieee: 'U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the
plane (Part I: Edge flips),” in Proceedings of the Annual ACM-SIAM Symposium
on Discrete Algorithms, Salt Lake City, UT, United States, 2020, vol. 2020–January,
pp. 2823–2841.'
ista: 'Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the
plane (Part I: Edge flips). Proceedings of the Annual ACM-SIAM Symposium on Discrete
Algorithms. SODA: Symposium on Discrete Algorithms vol. 2020–January, 2823–2841.'
mla: 'Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in
the Plane (Part I: Edge Flips).” Proceedings of the Annual ACM-SIAM Symposium
on Discrete Algorithms, vol. 2020–January, SIAM, 2020, pp. 2823–41, doi:10.1137/1.9781611975994.172.'
short: U. Wagner, E. Welzl, in:, Proceedings of the Annual ACM-SIAM Symposium on
Discrete Algorithms, SIAM, 2020, pp. 2823–2841.
conference:
end_date: 2020-01-08
location: Salt Lake City, UT, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2020-01-05
date_created: 2020-05-10T22:00:48Z
date_published: 2020-01-01T00:00:00Z
date_updated: 2023-08-04T08:51:07Z
day: '01'
department:
- _id: UlWa
doi: 10.1137/1.9781611975994.172
external_id:
arxiv:
- '2003.13557'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1137/1.9781611975994.172
month: '01'
oa: 1
oa_version: Submitted Version
page: 2823-2841
publication: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
isbn:
- '9781611975994'
publication_status: published
publisher: SIAM
quality_controlled: '1'
related_material:
record:
- id: '12129'
relation: later_version
status: public
scopus_import: 1
status: public
title: 'Connectivity of triangulation flip graphs in the plane (Part I: Edge flips)'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2020-January
year: '2020'
...
---
_id: '13073'
abstract:
- lang: eng
text: The Mytilus complex of marine mussel species forms a mosaic of hybrid zones,
found across temperate regions of the globe. This allows us to study "replicated"
instances of secondary contact between closely-related species. Previous work
on this complex has shown that local introgression is both widespread and highly
heterogeneous, and has identified SNPs that are outliers of differentiation between
lineages. Here, we developed an ancestry-informative panel of such SNPs. We then
compared their frequencies in newly-sampled populations, including samples from
within the hybrid zones, and parental populations at different distances from
the contact. Results show that close to the hybrid zones, some outlier loci are
near to fixation for the heterospecific allele, suggesting enhanced local introgression,
or the local sweep of a shared ancestral allele. Conversely, genomic cline analyses,
treating local parental populations as the reference, reveal a globally high concordance
among loci, albeit with a few signals of asymmetric introgression. Enhanced local
introgression at specific loci is consistent with the early transfer of adaptive
variants after contact, possibly including asymmetric bi-stable variants (Dobzhansky-Muller
incompatibilities), or haplotypes loaded with fewer deleterious mutations. Having
escaped one barrier, however, these variants can be trapped or delayed at the
next barrier, confining the introgression locally. These results shed light on
the decay of species barriers during phases of contact.
article_processing_charge: No
author:
- first_name: Alexis
full_name: Simon, Alexis
last_name: Simon
- first_name: Christelle
full_name: Fraisse, Christelle
id: 32DF5794-F248-11E8-B48F-1D18A9856A87
last_name: Fraisse
orcid: 0000-0001-8441-5075
- first_name: Tahani
full_name: El Ayari, Tahani
last_name: El Ayari
- first_name: Cathy
full_name: Liautard-Haag, Cathy
last_name: Liautard-Haag
- first_name: Petr
full_name: Strelkov, Petr
last_name: Strelkov
- first_name: John
full_name: Welch, John
last_name: Welch
- first_name: Nicolas
full_name: Bierne, Nicolas
last_name: Bierne
citation:
ama: Simon A, Fraisse C, El Ayari T, et al. How do species barriers decay? concordance
and local introgression in mosaic hybrid zones of mussels. 2020. doi:10.5061/DRYAD.R4XGXD29N
apa: Simon, A., Fraisse, C., El Ayari, T., Liautard-Haag, C., Strelkov, P., Welch,
J., & Bierne, N. (2020). How do species barriers decay? concordance and local
introgression in mosaic hybrid zones of mussels. Dryad. https://doi.org/10.5061/DRYAD.R4XGXD29N
chicago: Simon, Alexis, Christelle Fraisse, Tahani El Ayari, Cathy Liautard-Haag,
Petr Strelkov, John Welch, and Nicolas Bierne. “How Do Species Barriers Decay?
Concordance and Local Introgression in Mosaic Hybrid Zones of Mussels.” Dryad,
2020. https://doi.org/10.5061/DRYAD.R4XGXD29N.
ieee: A. Simon et al., “How do species barriers decay? concordance and local
introgression in mosaic hybrid zones of mussels.” Dryad, 2020.
ista: Simon A, Fraisse C, El Ayari T, Liautard-Haag C, Strelkov P, Welch J, Bierne
N. 2020. How do species barriers decay? concordance and local introgression in
mosaic hybrid zones of mussels, Dryad, 10.5061/DRYAD.R4XGXD29N.
mla: Simon, Alexis, et al. How Do Species Barriers Decay? Concordance and Local
Introgression in Mosaic Hybrid Zones of Mussels. Dryad, 2020, doi:10.5061/DRYAD.R4XGXD29N.
short: A. Simon, C. Fraisse, T. El Ayari, C. Liautard-Haag, P. Strelkov, J. Welch,
N. Bierne, (2020).
date_created: 2023-05-23T16:48:27Z
date_published: 2020-09-22T00:00:00Z
date_updated: 2023-08-04T11:04:11Z
day: '22'
ddc:
- '570'
department:
- _id: NiBa
doi: 10.5061/DRYAD.R4XGXD29N
license: https://creativecommons.org/publicdomain/zero/1.0/
main_file_link:
- open_access: '1'
url: https://doi.org/10.5061/dryad.r4xgxd29n
month: '09'
oa: 1
oa_version: Published Version
publisher: Dryad
related_material:
record:
- id: '8708'
relation: used_in_publication
status: public
status: public
title: How do species barriers decay? concordance and local introgression in mosaic
hybrid zones of mussels
tmp:
image: /images/cc_0.png
legal_code_url: https://creativecommons.org/publicdomain/zero/1.0/legalcode
name: Creative Commons Public Domain Dedication (CC0 1.0)
short: CC0 (1.0)
type: research_data_reference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2020'
...
---
_id: '13065'
abstract:
- lang: eng
text: Domestication is a human-induced selection process that imprints the genomes
of domesticated populations over a short evolutionary time scale, and that occurs
in a given demographic context. Reconstructing historical gene flow, effective
population size changes and their timing is therefore of fundamental interest
to understand how plant demography and human selection jointly shape genomic divergence
during domestication. Yet, the comparison under a single statistical framework
of independent domestication histories across different crop species has been
little evaluated so far. Thus, it is unclear whether domestication leads to convergent
demographic changes that similarly affect crop genomes. To address this question,
we used existing and new transcriptome data on three crop species of Solanaceae
(eggplant, pepper and tomato), together with their close wild relatives. We fitted
twelve demographic models of increasing complexity on the unfolded joint allele
frequency spectrum for each wild/crop pair, and we found evidence for both shared
and species-specific demographic processes between species. A convergent history
of domestication with gene-flow was inferred for all three species, along with
evidence of strong reduction in the effective population size during the cultivation
stage of tomato and pepper. The absence of any reduction in size of the crop in
eggplant stands out from the classical view of the domestication process; as does
the existence of a “protracted period” of management before cultivation. Our results
also suggest divergent management strategies of modern cultivars among species
as their current demography substantially differs. Finally, the timing of domestication
is species-specific and supported by the few historical records available.
article_processing_charge: No
author:
- first_name: Stephanie
full_name: Arnoux, Stephanie
last_name: Arnoux
- first_name: Christelle
full_name: Fraisse, Christelle
id: 32DF5794-F248-11E8-B48F-1D18A9856A87
last_name: Fraisse
orcid: 0000-0001-8441-5075
- first_name: Christopher
full_name: Sauvage, Christopher
last_name: Sauvage
citation:
ama: 'Arnoux S, Fraisse C, Sauvage C. VCF files of synonymous SNPs related to: Genomic
inference of complex domestication histories in three Solanaceae species. 2020.
doi:10.5061/DRYAD.Q2BVQ83HD'
apa: 'Arnoux, S., Fraisse, C., & Sauvage, C. (2020). VCF files of synonymous
SNPs related to: Genomic inference of complex domestication histories in three
Solanaceae species. Dryad. https://doi.org/10.5061/DRYAD.Q2BVQ83HD'
chicago: 'Arnoux, Stephanie, Christelle Fraisse, and Christopher Sauvage. “VCF Files
of Synonymous SNPs Related to: Genomic Inference of Complex Domestication Histories
in Three Solanaceae Species.” Dryad, 2020. https://doi.org/10.5061/DRYAD.Q2BVQ83HD.'
ieee: 'S. Arnoux, C. Fraisse, and C. Sauvage, “VCF files of synonymous SNPs related
to: Genomic inference of complex domestication histories in three Solanaceae species.”
Dryad, 2020.'
ista: 'Arnoux S, Fraisse C, Sauvage C. 2020. VCF files of synonymous SNPs related
to: Genomic inference of complex domestication histories in three Solanaceae species,
Dryad, 10.5061/DRYAD.Q2BVQ83HD.'
mla: 'Arnoux, Stephanie, et al. VCF Files of Synonymous SNPs Related to: Genomic
Inference of Complex Domestication Histories in Three Solanaceae Species.
Dryad, 2020, doi:10.5061/DRYAD.Q2BVQ83HD.'
short: S. Arnoux, C. Fraisse, C. Sauvage, (2020).
date_created: 2023-05-23T16:30:20Z
date_published: 2020-10-19T00:00:00Z
date_updated: 2023-08-04T11:19:26Z
day: '19'
ddc:
- '570'
department:
- _id: NiBa
doi: 10.5061/DRYAD.Q2BVQ83HD
main_file_link:
- open_access: '1'
url: https://doi.org/10.5061/dryad.q2bvq83hd
month: '10'
oa: 1
oa_version: Published Version
publisher: Dryad
related_material:
link:
- relation: software
url: https://github.com/starnoux/arnoux_et_al_2019
record:
- id: '8928'
relation: used_in_publication
status: public
status: public
title: 'VCF files of synonymous SNPs related to: Genomic inference of complex domestication
histories in three Solanaceae species'
tmp:
image: /images/cc_0.png
legal_code_url: https://creativecommons.org/publicdomain/zero/1.0/legalcode
name: Creative Commons Public Domain Dedication (CC0 1.0)
short: CC0 (1.0)
type: research_data_reference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2020'
...
---
_id: '8536'
abstract:
- lang: eng
text: This work analyzes the latency of the simplified successive cancellation (SSC)
decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It
is shown that, unlike conventional successive cancellation decoding, where latency
is linear in the block length, the latency of SSC decoding is sublinear. More
specifically, the latency of SSC decoding is O(N 1−1/µ ), where N is the block
length and µ is the scaling exponent of the channel, which captures the speed
of convergence of the rate to capacity. Numerical results demonstrate the tightness
of the bound and show that most of the latency reduction arises from the parallel
decoding of subcodes of rate 0 and 1.
acknowledgement: M. Mondelli was partially supported by grants NSF DMS-1613091, CCF-1714305,
IIS-1741162 and ONR N00014-18-1-2729. S. A. Hashemi is supported by a Postdoctoral
Fellowship from the Natural Sciences and Engineering Research Council of Canada
(NSERC) and by Huawei.
article_number: 401-406
article_processing_charge: No
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Seyyed Ali
full_name: Hashemi, Seyyed Ali
last_name: Hashemi
- first_name: John
full_name: Cioffi, John
last_name: Cioffi
- first_name: Andrea
full_name: Goldsmith, Andrea
last_name: Goldsmith
citation:
ama: 'Mondelli M, Hashemi SA, Cioffi J, Goldsmith A. Simplified successive cancellation
decoding of polar codes has sublinear latency. In: IEEE International Symposium
on Information Theory - Proceedings. Vol 2020-June. IEEE; 2020. doi:10.1109/ISIT44484.2020.9174141'
apa: 'Mondelli, M., Hashemi, S. A., Cioffi, J., & Goldsmith, A. (2020). Simplified
successive cancellation decoding of polar codes has sublinear latency. In IEEE
International Symposium on Information Theory - Proceedings (Vol. 2020–June).
Los Angeles, CA, United States: IEEE. https://doi.org/10.1109/ISIT44484.2020.9174141'
chicago: Mondelli, Marco, Seyyed Ali Hashemi, John Cioffi, and Andrea Goldsmith.
“Simplified Successive Cancellation Decoding of Polar Codes Has Sublinear Latency.”
In IEEE International Symposium on Information Theory - Proceedings, Vol.
2020–June. IEEE, 2020. https://doi.org/10.1109/ISIT44484.2020.9174141.
ieee: M. Mondelli, S. A. Hashemi, J. Cioffi, and A. Goldsmith, “Simplified successive
cancellation decoding of polar codes has sublinear latency,” in IEEE International
Symposium on Information Theory - Proceedings, Los Angeles, CA, United States,
2020, vol. 2020–June.
ista: 'Mondelli M, Hashemi SA, Cioffi J, Goldsmith A. 2020. Simplified successive
cancellation decoding of polar codes has sublinear latency. IEEE International
Symposium on Information Theory - Proceedings. ISIT: Internation Symposium on
Information Theory vol. 2020–June, 401–406.'
mla: Mondelli, Marco, et al. “Simplified Successive Cancellation Decoding of Polar
Codes Has Sublinear Latency.” IEEE International Symposium on Information Theory
- Proceedings, vol. 2020–June, 401–406, IEEE, 2020, doi:10.1109/ISIT44484.2020.9174141.
short: M. Mondelli, S.A. Hashemi, J. Cioffi, A. Goldsmith, in:, IEEE International
Symposium on Information Theory - Proceedings, IEEE, 2020.
conference:
end_date: 2020-06-26
location: Los Angeles, CA, United States
name: 'ISIT: Internation Symposium on Information Theory'
start_date: 2020-06-21
date_created: 2020-09-20T22:01:37Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2023-08-07T13:36:24Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/ISIT44484.2020.9174141
external_id:
arxiv:
- '1909.04892'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1909.04892
month: '06'
oa: 1
oa_version: Preprint
publication: IEEE International Symposium on Information Theory - Proceedings
publication_identifier:
isbn:
- '9781728164328'
issn:
- '21578095'
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '9047'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Simplified successive cancellation decoding of polar codes has sublinear latency
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2020-June
year: '2020'
...
---
_id: '9308'
acknowledgement: This research was carried out with the support of the Russian Foundation
for Basic Research(grant no. 19-01-00169)
article_processing_charge: No
article_type: original
author:
- first_name: Sergey
full_name: Avvakumov, Sergey
id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
last_name: Avvakumov
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Isaac
full_name: Mabillard, Isaac
id: 32BF9DAA-F248-11E8-B48F-1D18A9856A87
last_name: Mabillard
- first_name: A. B.
full_name: Skopenkov, A. B.
last_name: Skopenkov
citation:
ama: Avvakumov S, Wagner U, Mabillard I, Skopenkov AB. Eliminating higher-multiplicity
intersections, III. Codimension 2. Russian Mathematical Surveys. 2020;75(6):1156-1158.
doi:10.1070/RM9943
apa: Avvakumov, S., Wagner, U., Mabillard, I., & Skopenkov, A. B. (2020). Eliminating
higher-multiplicity intersections, III. Codimension 2. Russian Mathematical
Surveys. IOP Publishing. https://doi.org/10.1070/RM9943
chicago: Avvakumov, Sergey, Uli Wagner, Isaac Mabillard, and A. B. Skopenkov. “Eliminating
Higher-Multiplicity Intersections, III. Codimension 2.” Russian Mathematical
Surveys. IOP Publishing, 2020. https://doi.org/10.1070/RM9943.
ieee: S. Avvakumov, U. Wagner, I. Mabillard, and A. B. Skopenkov, “Eliminating higher-multiplicity
intersections, III. Codimension 2,” Russian Mathematical Surveys, vol.
75, no. 6. IOP Publishing, pp. 1156–1158, 2020.
ista: Avvakumov S, Wagner U, Mabillard I, Skopenkov AB. 2020. Eliminating higher-multiplicity
intersections, III. Codimension 2. Russian Mathematical Surveys. 75(6), 1156–1158.
mla: Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections, III.
Codimension 2.” Russian Mathematical Surveys, vol. 75, no. 6, IOP Publishing,
2020, pp. 1156–58, doi:10.1070/RM9943.
short: S. Avvakumov, U. Wagner, I. Mabillard, A.B. Skopenkov, Russian Mathematical
Surveys 75 (2020) 1156–1158.
date_created: 2021-04-04T22:01:22Z
date_published: 2020-12-01T00:00:00Z
date_updated: 2023-08-14T11:43:54Z
day: '01'
department:
- _id: UlWa
doi: 10.1070/RM9943
external_id:
arxiv:
- '1511.03501'
isi:
- '000625983100001'
intvolume: ' 75'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1511.03501
month: '12'
oa: 1
oa_version: Preprint
page: 1156-1158
publication: Russian Mathematical Surveys
publication_identifier:
issn:
- 0036-0279
publication_status: published
publisher: IOP Publishing
quality_controlled: '1'
related_material:
record:
- id: '8183'
relation: earlier_version
status: public
- id: '10220'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Eliminating higher-multiplicity intersections, III. Codimension 2
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 75
year: '2020'
...