---
_id: '9227'
abstract:
- lang: eng
text: In the multiway cut problem we are given a weighted undirected graph G=(V,E) and
a set T⊆V of k terminals. The goal is to find a minimum weight set of edges E′⊆E with
the property that by removing E′ from G all the terminals become disconnected.
In this paper we present a simple local search approximation algorithm for the
multiway cut problem with approximation ratio 2−2k . We present an experimental
evaluation of the performance of our local search algorithm and show that it greatly
outperforms the isolation heuristic of Dalhaus et al. and it has similar performance
as the much more complex algorithms of Calinescu et al., Sharma and Vondrak, and
Buchbinder et al. which have the currently best known approximation ratios for
this problem.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Andrew
full_name: Bloch-Hansen, Andrew
last_name: Bloch-Hansen
- first_name: Nasim
full_name: Samei, Nasim
id: C1531CAE-36E9-11EA-845F-33AA3DDC885E
last_name: Samei
- first_name: Roberto
full_name: Solis-Oba, Roberto
last_name: Solis-Oba
citation:
ama: 'Bloch-Hansen A, Samei N, Solis-Oba R. Experimental evaluation of a local search
approximation algorithm for the multiway cut problem. In: Conference on Algorithms
and Discrete Applied Mathematics. Vol 12601. Springer Nature; 2021:346-358.
doi:10.1007/978-3-030-67899-9_28'
apa: 'Bloch-Hansen, A., Samei, N., & Solis-Oba, R. (2021). Experimental evaluation
of a local search approximation algorithm for the multiway cut problem. In Conference
on Algorithms and Discrete Applied Mathematics (Vol. 12601, pp. 346–358).
Rupnagar, India: Springer Nature. https://doi.org/10.1007/978-3-030-67899-9_28'
chicago: Bloch-Hansen, Andrew, Nasim Samei, and Roberto Solis-Oba. “Experimental
Evaluation of a Local Search Approximation Algorithm for the Multiway Cut Problem.”
In Conference on Algorithms and Discrete Applied Mathematics, 12601:346–58.
Springer Nature, 2021. https://doi.org/10.1007/978-3-030-67899-9_28.
ieee: A. Bloch-Hansen, N. Samei, and R. Solis-Oba, “Experimental evaluation of a
local search approximation algorithm for the multiway cut problem,” in Conference
on Algorithms and Discrete Applied Mathematics, Rupnagar, India, 2021, vol.
12601, pp. 346–358.
ista: 'Bloch-Hansen A, Samei N, Solis-Oba R. 2021. Experimental evaluation of a
local search approximation algorithm for the multiway cut problem. Conference
on Algorithms and Discrete Applied Mathematics. CALDAM: Conference on Algorithms
and Discrete Applied Mathematics, LNCS, vol. 12601, 346–358.'
mla: Bloch-Hansen, Andrew, et al. “Experimental Evaluation of a Local Search Approximation
Algorithm for the Multiway Cut Problem.” Conference on Algorithms and Discrete
Applied Mathematics, vol. 12601, Springer Nature, 2021, pp. 346–58, doi:10.1007/978-3-030-67899-9_28.
short: A. Bloch-Hansen, N. Samei, R. Solis-Oba, in:, Conference on Algorithms and
Discrete Applied Mathematics, Springer Nature, 2021, pp. 346–358.
conference:
end_date: 2021-02-13
location: Rupnagar, India
name: 'CALDAM: Conference on Algorithms and Discrete Applied Mathematics'
start_date: 2021-02-11
date_created: 2021-03-07T23:01:25Z
date_published: 2021-01-28T00:00:00Z
date_updated: 2025-09-10T10:01:54Z
day: '28'
department:
- _id: VlKo
doi: 10.1007/978-3-030-67899-9_28
external_id:
isi:
- '001433483100028'
intvolume: ' 12601'
isi: 1
language:
- iso: eng
month: '01'
oa_version: None
page: 346-358
publication: Conference on Algorithms and Discrete Applied Mathematics
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030678982'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Experimental evaluation of a local search approximation algorithm for the multiway
cut problem
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 12601
year: '2021'
...
---
_id: '9296'
abstract:
- lang: eng
text: ' matching is compatible to two or more labeled point sets of size n with
labels {1,…,n} if its straight-line drawing on each of these point sets is
crossing-free. We study the maximum number of edges in a matching compatible to
two or more labeled point sets in general position in the plane. We show that
for any two labeled convex sets of n points there exists a compatible matching
with ⌊2n−−√⌋ edges. More generally, for any ℓ labeled point sets we construct
compatible matchings of size Ω(n1/ℓ) . As a corresponding upper bound, we use
probabilistic arguments to show that for any ℓ given sets of n points there
exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges.
Finally, we show that Θ(logn) copies of any set of n points are necessary and
sufficient for the existence of a labeling such that any compatible matching consists
only of a single edge.'
acknowledgement: 'A.A. funded by the Marie Skłodowska-Curie grant agreement No. 754411.
Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant
no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative
DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported
by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by
ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23
(RiSE).'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Oswin
full_name: Aichholzer, Oswin
last_name: Aichholzer
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
- first_name: Irene
full_name: Parada, Irene
last_name: Parada
- first_name: Daniel
full_name: Perz, Daniel
last_name: Perz
- first_name: Alexander
full_name: Pilz, Alexander
last_name: Pilz
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Birgit
full_name: Vogtenhuber, Birgit
last_name: Vogtenhuber
citation:
ama: 'Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings.
In: 15th International Conference on Algorithms and Computation. Vol 12635.
Springer Nature; 2021:221-233. doi:10.1007/978-3-030-68211-8_18'
apa: 'Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D.,
Pilz, A., … Vogtenhuber, B. (2021). On compatible matchings. In 15th International
Conference on Algorithms and Computation (Vol. 12635, pp. 221–233). Yangon,
Myanmar: Springer Nature. https://doi.org/10.1007/978-3-030-68211-8_18'
chicago: Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada,
Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible
Matchings.” In 15th International Conference on Algorithms and Computation,
12635:221–33. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-68211-8_18.
ieee: O. Aichholzer et al., “On compatible matchings,” in 15th International
Conference on Algorithms and Computation, Yangon, Myanmar, 2021, vol. 12635,
pp. 221–233.
ista: 'Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec
J, Vogtenhuber B. 2021. On compatible matchings. 15th International Conference
on Algorithms and Computation. WALCOM: Algorithms and Computation, LNCS, vol.
12635, 221–233.'
mla: Aichholzer, Oswin, et al. “On Compatible Matchings.” 15th International
Conference on Algorithms and Computation, vol. 12635, Springer Nature, 2021,
pp. 221–33, doi:10.1007/978-3-030-68211-8_18.
short: O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz,
J. Tkadlec, B. Vogtenhuber, in:, 15th International Conference on Algorithms and
Computation, Springer Nature, 2021, pp. 221–233.
conference:
end_date: 2021-03-02
location: Yangon, Myanmar
name: 'WALCOM: Algorithms and Computation'
start_date: 2021-02-28
date_created: 2021-03-28T22:01:41Z
date_published: 2021-02-16T00:00:00Z
date_updated: 2026-04-16T09:18:21Z
day: '16'
department:
- _id: UlWa
- _id: HeEd
- _id: KrCh
doi: 10.1007/978-3-030-68211-8_18
ec_funded: 1
external_id:
arxiv:
- '2101.03928'
isi:
- '001435069600018'
intvolume: ' 12635'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2101.03928
month: '02'
oa: 1
oa_version: Preprint
page: 221-233
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _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
publication: 15th International Conference on Algorithms and Computation
publication_identifier:
eisbn:
- '9783030682118'
eissn:
- 1611-3349
isbn:
- '9783030682101'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11938'
relation: later_version
status: public
scopus_import: '1'
status: public
title: On compatible matchings
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12635
year: '2021'
...
---
_id: '9466'
abstract:
- lang: eng
text: In this work, we apply the dynamical systems analysis of Hanrot et al. (CRYPTO’11)
to a class of lattice block reduction algorithms that includes (natural variants
of) slide reduction and block-Rankin reduction. This implies sharper bounds on
the polynomial running times (in the query model) for these algorithms and opens
the door to faster practical variants of slide reduction. We give heuristic arguments
showing that such variants can indeed speed up slide reduction significantly in
practice. This is confirmed by experimental evidence, which also shows that our
variants are competitive with state-of-the-art reduction algorithms.
acknowledgement: 'This work was initiated in discussions with Léo Ducas, when the
author was visiting the Simons Institute for the Theory of Computation during the
program “Lattices: Algorithms, Complexity, and Cryptography”. We thank Thomas Espitau
for pointing out a bug in a proof in an earlier version of this manuscript.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Walter M. The convergence of slide-type reductions. In: Public-Key Cryptography
– PKC 2021. Vol 12710. Springer Nature; 2021:45-67. doi:10.1007/978-3-030-75245-3_3'
apa: 'Walter, M. (2021). The convergence of slide-type reductions. In Public-Key
Cryptography – PKC 2021 (Vol. 12710, pp. 45–67). Virtual: Springer Nature.
https://doi.org/10.1007/978-3-030-75245-3_3'
chicago: Walter, Michael. “The Convergence of Slide-Type Reductions.” In Public-Key
Cryptography – PKC 2021, 12710:45–67. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-75245-3_3.
ieee: M. Walter, “The convergence of slide-type reductions,” in Public-Key Cryptography
– PKC 2021, Virtual, 2021, vol. 12710, pp. 45–67.
ista: 'Walter M. 2021. The convergence of slide-type reductions. Public-Key Cryptography
– PKC 2021. PKC: IACR International Conference on Practice and Theory of Public
Key Cryptography, LNCS, vol. 12710, 45–67.'
mla: Walter, Michael. “The Convergence of Slide-Type Reductions.” Public-Key
Cryptography – PKC 2021, vol. 12710, Springer Nature, 2021, pp. 45–67, doi:10.1007/978-3-030-75245-3_3.
short: M. Walter, in:, Public-Key Cryptography – PKC 2021, Springer Nature, 2021,
pp. 45–67.
conference:
end_date: 2021-05-13
location: Virtual
name: 'PKC: IACR International Conference on Practice and Theory of Public Key Cryptography'
start_date: 2021-05-10
corr_author: '1'
date_created: 2021-06-06T22:01:29Z
date_published: 2021-05-01T00:00:00Z
date_updated: 2026-04-16T09:25:35Z
day: '01'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.1007/978-3-030-75245-3_3
ec_funded: 1
external_id:
isi:
- '001294728500003'
file:
- access_level: open_access
checksum: 413e564d645ed93d7318672361d9d470
content_type: application/pdf
creator: dernst
date_created: 2022-05-27T09:48:31Z
date_updated: 2022-05-27T09:48:31Z
file_id: '11416'
file_name: 2021_PKC_Walter.pdf
file_size: 489017
relation: main_file
success: 1
file_date_updated: 2022-05-27T09:48:31Z
has_accepted_license: '1'
intvolume: ' 12710'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '05'
oa: 1
oa_version: Published Version
page: 45-67
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Public-Key Cryptography – PKC 2021
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030752446'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: The convergence of slide-type reductions
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: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12710
year: '2021'
...
---
_id: '9620'
abstract:
- lang: eng
text: "In this note, we introduce a distributed twist on the classic coupon collector
problem: a set of m collectors wish to each obtain a set of n coupons; for this,
they can each sample coupons uniformly at random, but can also meet in pairwise
interactions, during which they can exchange coupons. By doing so, they hope to
reduce the number of coupons that must be sampled by each collector in order to
obtain a full set. This extension is natural when considering real-world manifestations
of the coupon collector phenomenon, and has been remarked upon and studied empirically
(Hayes and Hannigan 2006, Ahmad et al. 2014, Delmarcelle 2019).\r\n\r\nWe provide
the first theoretical analysis for such a scenario. We find that “coupon collecting
with friends” can indeed significantly reduce the number of coupons each collector
must sample, and raises interesting connections to the more traditional variants
of the problem. While our analysis is in most cases asymptotically tight, there
are several open questions raised, regarding finer-grained analysis of both “coupon
collecting with friends,” and of a long-studied variant of the original problem
in which a collector requires multiple full sets of coupons."
acknowledgement: Peter Davies is supported by the European Union’s Horizon2020 research
and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Peter
full_name: Davies, Peter
id: 11396234-BB50-11E9-B24C-90FCE5697425
last_name: Davies
orcid: 0000-0002-5646-9524
citation:
ama: 'Alistarh D-A, Davies P. Collecting coupons is faster with friends. In: Structural
Information and Communication Complexity. Vol 12810. Springer Nature; 2021:3-12.
doi:10.1007/978-3-030-79527-6_1'
apa: 'Alistarh, D.-A., & Davies, P. (2021). Collecting coupons is faster with
friends. In Structural Information and Communication Complexity (Vol. 12810,
pp. 3–12). Wrocław, Poland: Springer Nature. https://doi.org/10.1007/978-3-030-79527-6_1'
chicago: Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with
Friends.” In Structural Information and Communication Complexity, 12810:3–12.
Springer Nature, 2021. https://doi.org/10.1007/978-3-030-79527-6_1.
ieee: D.-A. Alistarh and P. Davies, “Collecting coupons is faster with friends,”
in Structural Information and Communication Complexity, Wrocław, Poland,
2021, vol. 12810, pp. 3–12.
ista: 'Alistarh D-A, Davies P. 2021. Collecting coupons is faster with friends.
Structural Information and Communication Complexity. SIROCCO: International Colloquium
on Structural Information and Communication Complexity, LNCS, vol. 12810, 3–12.'
mla: Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with
Friends.” Structural Information and Communication Complexity, vol. 12810,
Springer Nature, 2021, pp. 3–12, doi:10.1007/978-3-030-79527-6_1.
short: D.-A. Alistarh, P. Davies, in:, Structural Information and Communication
Complexity, Springer Nature, 2021, pp. 3–12.
conference:
end_date: 2021-07-01
location: Wrocław, Poland
name: 'SIROCCO: International Colloquium on Structural Information and Communication
Complexity'
start_date: 2021-06-28
date_created: 2021-07-01T11:04:43Z
date_published: 2021-06-20T00:00:00Z
date_updated: 2025-09-10T10:04:46Z
day: '20'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1007/978-3-030-79527-6_1
ec_funded: 1
external_id:
isi:
- '001292788400001'
file:
- access_level: open_access
checksum: fe37fb9af3f5016c1084af9d6e7109bd
content_type: application/pdf
creator: pdavies
date_created: 2021-07-01T11:21:40Z
date_updated: 2021-07-01T11:21:40Z
file_id: '9621'
file_name: Population_Coupon_Collector.pdf
file_size: 319728
relation: main_file
file_date_updated: 2021-07-01T11:21:40Z
has_accepted_license: '1'
intvolume: ' 12810'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Preprint
page: 3-12
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Structural Information and Communication Complexity
publication_identifier:
eisbn:
- '9783030795276'
eissn:
- 1611-3349
isbn:
- '9783030795269'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Collecting coupons is faster with friends
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 12810
year: '2021'
...
---
_id: '9823'
abstract:
- lang: eng
text: "Approximate agreement is one of the few variants of consensus that can be
solved in a wait-free manner in asynchronous systems where processes communicate
by reading and writing to shared memory. In this work, we consider a natural generalisation
of approximate agreement on arbitrary undirected connected graphs. Each process
is given a vertex of the graph as input and, if non-faulty, must output a vertex
such that\r\nall the outputs are within distance 1 of one another, and\r\n\r\neach
output value lies on a shortest path between two input values.\r\n\r\nFrom prior
work, it is known that there is no wait-free algorithm among \U0001D45B≥3 processes
for this problem on any cycle of length \U0001D450≥4 , by reduction from 2-set
agreement (Castañeda et al. 2018).\r\n\r\nIn this work, we investigate the solvability
and complexity of this task on general graphs. We give a new, direct proof of
the impossibility of approximate agreement on cycles of length \U0001D450≥4
, via a generalisation of Sperner’s Lemma to convex polygons. We also extend the
reduction from 2-set agreement to a larger class of graphs, showing that approximate
agreement on these graphs is unsolvable. On the positive side, we present a wait-free
algorithm for a class of graphs that properly contains the class of chordal graphs."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Faith
full_name: Ellen, Faith
last_name: Ellen
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: 'Alistarh D-A, Ellen F, Rybicki J. Wait-free approximate agreement on graphs.
In: Structural Information and Communication Complexity. Vol 12810. Springer
Nature; 2021:87-105. doi:10.1007/978-3-030-79527-6_6'
apa: 'Alistarh, D.-A., Ellen, F., & Rybicki, J. (2021). Wait-free approximate
agreement on graphs. In Structural Information and Communication Complexity
(Vol. 12810, pp. 87–105). Wrocław, Poland: Springer Nature. https://doi.org/10.1007/978-3-030-79527-6_6'
chicago: Alistarh, Dan-Adrian, Faith Ellen, and Joel Rybicki. “Wait-Free Approximate
Agreement on Graphs.” In Structural Information and Communication Complexity,
12810:87–105. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-79527-6_6.
ieee: D.-A. Alistarh, F. Ellen, and J. Rybicki, “Wait-free approximate agreement
on graphs,” in Structural Information and Communication Complexity, Wrocław,
Poland, 2021, vol. 12810, pp. 87–105.
ista: 'Alistarh D-A, Ellen F, Rybicki J. 2021. Wait-free approximate agreement on graphs.
Structural Information and Communication Complexity. SIROCCO: Structural Information
and Communication Complexity, LNCS, vol. 12810, 87–105.'
mla: Alistarh, Dan-Adrian, et al. “Wait-Free Approximate Agreement on Graphs.” Structural
Information and Communication Complexity, vol. 12810, Springer Nature, 2021,
pp. 87–105, doi:10.1007/978-3-030-79527-6_6.
short: D.-A. Alistarh, F. Ellen, J. Rybicki, in:, Structural Information and Communication
Complexity, Springer Nature, 2021, pp. 87–105.
conference:
end_date: 2021-07-01
location: Wrocław, Poland
name: 'SIROCCO: Structural Information and Communication Complexity'
start_date: 2021-06-28
date_created: 2021-08-08T22:01:29Z
date_published: 2021-06-20T00:00:00Z
date_updated: 2026-04-16T09:26:11Z
day: '20'
department:
- _id: DaAl
doi: 10.1007/978-3-030-79527-6_6
external_id:
arxiv:
- '2103.08949'
isi:
- '001292788400006'
intvolume: ' 12810'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2103.08949
month: '06'
oa: 1
oa_version: Preprint
page: 87-105
publication: Structural Information and Communication Complexity
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030795269'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Wait-free approximate agreement on graphs
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12810
year: '2021'
...
---
_id: '9824'
abstract:
- lang: eng
text: We define a new compact coordinate system in which each integer triplet addresses
a voxel in the BCC grid, and we investigate some of its properties. We propose
a characterization of 3D discrete analytical planes with their topological features
(in the Cartesian and in the new coordinate system) such as the interrelation
between the thickness of the plane and the separability constraint we aim to obtain.
acknowledgement: 'This work has been partially supported by the Ministry of Education,
Science and Technological Development of the Republic of Serbia through the project
no. 451-03-68/2020-14/200156: “Innovative scientific and artistic research from
the FTS (activity) domain” (LČ), the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme, grant no. 788183 (RB), and
the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’,
Austrian Science Fund (FWF), grant no. I 02979-N35 (RB).'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Lidija
full_name: Čomić, Lidija
last_name: Čomić
- first_name: Rita
full_name: Zrour, Rita
last_name: Zrour
- first_name: Gaëlle
full_name: Largeteau-Skapin, Gaëlle
last_name: Largeteau-Skapin
- first_name: Ranita
full_name: Biswas, Ranita
id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
last_name: Biswas
orcid: 0000-0002-5372-7890
- first_name: Eric
full_name: Andres, Eric
last_name: Andres
citation:
ama: 'Čomić L, Zrour R, Largeteau-Skapin G, Biswas R, Andres E. Body centered cubic
grid - coordinate system and discrete analytical plane definition. In: Discrete
Geometry and Mathematical Morphology. Vol 12708. Springer Nature; 2021:152-163.
doi:10.1007/978-3-030-76657-3_10'
apa: 'Čomić, L., Zrour, R., Largeteau-Skapin, G., Biswas, R., & Andres, E. (2021).
Body centered cubic grid - coordinate system and discrete analytical plane definition.
In Discrete Geometry and Mathematical Morphology (Vol. 12708, pp. 152–163).
Uppsala, Sweden: Springer Nature. https://doi.org/10.1007/978-3-030-76657-3_10'
chicago: Čomić, Lidija, Rita Zrour, Gaëlle Largeteau-Skapin, Ranita Biswas, and
Eric Andres. “Body Centered Cubic Grid - Coordinate System and Discrete Analytical
Plane Definition.” In Discrete Geometry and Mathematical Morphology, 12708:152–63.
Springer Nature, 2021. https://doi.org/10.1007/978-3-030-76657-3_10.
ieee: L. Čomić, R. Zrour, G. Largeteau-Skapin, R. Biswas, and E. Andres, “Body centered
cubic grid - coordinate system and discrete analytical plane definition,” in Discrete
Geometry and Mathematical Morphology, Uppsala, Sweden, 2021, vol. 12708, pp.
152–163.
ista: 'Čomić L, Zrour R, Largeteau-Skapin G, Biswas R, Andres E. 2021. Body centered
cubic grid - coordinate system and discrete analytical plane definition. Discrete
Geometry and Mathematical Morphology. DGMM: International Conference on Discrete
Geometry and Mathematical Morphology, LNCS, vol. 12708, 152–163.'
mla: Čomić, Lidija, et al. “Body Centered Cubic Grid - Coordinate System and Discrete
Analytical Plane Definition.” Discrete Geometry and Mathematical Morphology,
vol. 12708, Springer Nature, 2021, pp. 152–63, doi:10.1007/978-3-030-76657-3_10.
short: L. Čomić, R. Zrour, G. Largeteau-Skapin, R. Biswas, E. Andres, in:, Discrete
Geometry and Mathematical Morphology, Springer Nature, 2021, pp. 152–163.
conference:
end_date: 2021-05-27
location: Uppsala, Sweden
name: 'DGMM: International Conference on Discrete Geometry and Mathematical Morphology'
start_date: 2021-05-24
date_created: 2021-08-08T22:01:29Z
date_published: 2021-05-16T00:00:00Z
date_updated: 2026-04-16T09:26:30Z
day: '16'
department:
- _id: HeEd
doi: 10.1007/978-3-030-76657-3_10
ec_funded: 1
external_id:
isi:
- '001286400400010'
intvolume: ' 12708'
isi: 1
language:
- iso: eng
month: '05'
oa_version: None
page: 152-163
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Discrete Geometry and Mathematical Morphology
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030766566'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Body centered cubic grid - coordinate system and discrete analytical plane
definition
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12708
year: '2021'
...
---
_id: '9825'
abstract:
- lang: eng
text: "The dual attack has long been considered a relevant attack on lattice-based
cryptographic schemes relying on the hardness of learning with errors (LWE) and
its structured variants. As solving LWE corresponds to finding a nearest point
on a lattice, one may naturally wonder how efficient this dual approach is for
solving more general closest vector problems, such as the classical closest vector
problem (CVP), the variants bounded distance decoding (BDD) and approximate CVP,
and preprocessing versions of these problems. While primal, sieving-based solutions
to these problems (with preprocessing) were recently studied in a series of works
on approximate Voronoi cells [Laa16b, DLdW19, Laa20, DLvW20], for the dual attack
no such overview exists, especially for problems with preprocessing. With one
of the take-away messages of the approximate Voronoi cell line of work being that
primal attacks work well for approximate CVP(P) but scale poorly for BDD(P), one
may further wonder if the dual attack suffers the same drawbacks, or if it is
perhaps a better solution when trying to solve BDD(P).\r\n\r\nIn this work we
provide an overview of cost estimates for dual algorithms for solving these “classical”
closest lattice vector problems. Heuristically we expect to solve the search version
of average-case CVPP in time and space 20.293\U0001D451+\U0001D45C(\U0001D451)
\ in the single-target model. The distinguishing version of average-case CVPP,
where we wish to distinguish between random targets and targets planted at distance
(say) 0.99⋅\U0001D454\U0001D451 from the lattice, has the same complexity in
the single-target model, but can be solved in time and space 20.195\U0001D451+\U0001D45C(\U0001D451)
\ in the multi-target setting, when given a large number of targets from either
target distribution. This suggests an inequivalence between distinguishing and
searching, as we do not expect a similar improvement in the multi-target setting
to hold for search-CVPP. We analyze three slightly different decoders, both for
distinguishing and searching, and experimentally obtain concrete cost estimates
for the dual attack in dimensions 50 to 80, which confirm our heuristic assumptions,
and show that the hidden order terms in the asymptotic estimates are quite small.\r\n\r\nOur
main take-away message is that the dual attack appears to mirror the approximate
Voronoi cell line of work – whereas using approximate Voronoi cells works well
for approximate CVP(P) but scales poorly for BDD(P), the dual approach scales
well for BDD(P) instances but performs poorly on approximate CVP(P)."
acknowledgement: The authors thank Sauvik Bhattacharya, L´eo Ducas, Rachel Player,
and Christine van Vredendaal for early discussions on this topic and on preliminary
results. The authors further thank the reviewers of CT-RSA 2021 for their valuable
feedback.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Thijs
full_name: Laarhoven, Thijs
last_name: Laarhoven
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Laarhoven T, Walter M. Dual lattice attacks for closest vector problems (with
preprocessing). In: Topics in Cryptology – CT-RSA 2021. Vol 12704. Springer
Nature; 2021:478-502. doi:10.1007/978-3-030-75539-3_20'
apa: 'Laarhoven, T., & Walter, M. (2021). Dual lattice attacks for closest vector
problems (with preprocessing). In Topics in Cryptology – CT-RSA 2021 (Vol.
12704, pp. 478–502). Virtual Event: Springer Nature. https://doi.org/10.1007/978-3-030-75539-3_20'
chicago: Laarhoven, Thijs, and Michael Walter. “Dual Lattice Attacks for Closest
Vector Problems (with Preprocessing).” In Topics in Cryptology – CT-RSA 2021,
12704:478–502. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-75539-3_20.
ieee: T. Laarhoven and M. Walter, “Dual lattice attacks for closest vector problems
(with preprocessing),” in Topics in Cryptology – CT-RSA 2021, Virtual Event,
2021, vol. 12704, pp. 478–502.
ista: 'Laarhoven T, Walter M. 2021. Dual lattice attacks for closest vector problems
(with preprocessing). Topics in Cryptology – CT-RSA 2021. CT-RSA: Cryptographers’
Track at the RSA Conference, LNCS, vol. 12704, 478–502.'
mla: Laarhoven, Thijs, and Michael Walter. “Dual Lattice Attacks for Closest Vector
Problems (with Preprocessing).” Topics in Cryptology – CT-RSA 2021, vol.
12704, Springer Nature, 2021, pp. 478–502, doi:10.1007/978-3-030-75539-3_20.
short: T. Laarhoven, M. Walter, in:, Topics in Cryptology – CT-RSA 2021, Springer
Nature, 2021, pp. 478–502.
conference:
end_date: 2021-05-20
location: Virtual Event
name: 'CT-RSA: Cryptographers’ Track at the RSA Conference'
start_date: 2021-05-17
date_created: 2021-08-08T22:01:30Z
date_published: 2021-05-11T00:00:00Z
date_updated: 2026-04-16T09:28:30Z
day: '11'
department:
- _id: KrPi
doi: 10.1007/978-3-030-75539-3_20
intvolume: ' 12704'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/557
month: '05'
oa: 1
oa_version: Preprint
page: 478-502
publication: Topics in Cryptology – CT-RSA 2021
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030755386'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dual lattice attacks for closest vector problems (with preprocessing)
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12704
year: '2021'
...
---
_id: '9826'
abstract:
- lang: eng
text: "Automated contract tracing aims at supporting manual contact tracing during
pandemics by alerting users of encounters with infected people. There are currently
many proposals for protocols (like the “decentralized” DP-3T and PACT or the “centralized”
ROBERT and DESIRE) to be run on mobile phones, where the basic idea is to regularly
broadcast (using low energy Bluetooth) some values, and at the same time store
(a function of) incoming messages broadcasted by users in their proximity. In
the existing proposals one can trigger false positives on a massive scale by an
“inverse-Sybil” attack, where a large number of devices (malicious users or hacked
phones) pretend to be the same user, such that later, just a single person needs
to be diagnosed (and allowed to upload) to trigger an alert for all users who
were in proximity to any of this large group of devices.\r\n\r\nWe propose the
first protocols that do not succumb to such attacks assuming the devices involved
in the attack do not constantly communicate, which we observe is a necessary assumption.
The high level idea of the protocols is to derive the values to be broadcasted
by a hash chain, so that two (or more) devices who want to launch an inverse-Sybil
attack will not be able to connect their respective chains and thus only one of
them will be able to upload. Our protocols also achieve security against replay,
belated replay, and one of them even against relay attacks."
acknowledgement: Guillermo Pascual-Perez and Michelle Yeo were funded by the European
Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska–Curie
Grant Agreement No. 665385; the remaining contributors to this project have received
funding from the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation programme (682815 - TOCNeT).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Suvradip
full_name: Chakraborty, Suvradip
id: B9CD0494-D033-11E9-B219-A439E6697425
last_name: Chakraborty
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- 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: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Auerbach B, Chakraborty S, Klein K, et al. Inverse-Sybil attacks in automated
contact tracing. In: Topics in Cryptology – CT-RSA 2021. Vol 12704. Springer
Nature; 2021:399-421. doi:10.1007/978-3-030-75539-3_17'
apa: 'Auerbach, B., Chakraborty, S., Klein, K., Pascual Perez, G., Pietrzak, K.
Z., Walter, M., & Yeo, M. X. (2021). Inverse-Sybil attacks in automated contact
tracing. In Topics in Cryptology – CT-RSA 2021 (Vol. 12704, pp. 399–421).
Virtual Event: Springer Nature. https://doi.org/10.1007/978-3-030-75539-3_17'
chicago: Auerbach, Benedikt, Suvradip Chakraborty, Karen Klein, Guillermo Pascual
Perez, Krzysztof Z Pietrzak, Michael Walter, and Michelle X Yeo. “Inverse-Sybil
Attacks in Automated Contact Tracing.” In Topics in Cryptology – CT-RSA 2021,
12704:399–421. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-75539-3_17.
ieee: B. Auerbach et al., “Inverse-Sybil attacks in automated contact tracing,”
in Topics in Cryptology – CT-RSA 2021, Virtual Event, 2021, vol. 12704,
pp. 399–421.
ista: 'Auerbach B, Chakraborty S, Klein K, Pascual Perez G, Pietrzak KZ, Walter
M, Yeo MX. 2021. Inverse-Sybil attacks in automated contact tracing. Topics in
Cryptology – CT-RSA 2021. CT-RSA: Cryptographers’ Track at the RSA Conference,
LNCS, vol. 12704, 399–421.'
mla: Auerbach, Benedikt, et al. “Inverse-Sybil Attacks in Automated Contact Tracing.”
Topics in Cryptology – CT-RSA 2021, vol. 12704, Springer Nature, 2021,
pp. 399–421, doi:10.1007/978-3-030-75539-3_17.
short: B. Auerbach, S. Chakraborty, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M.
Walter, M.X. Yeo, in:, Topics in Cryptology – CT-RSA 2021, Springer Nature, 2021,
pp. 399–421.
conference:
end_date: 2021-05-20
location: Virtual Event
name: 'CT-RSA: Cryptographers’ Track at the RSA Conference'
start_date: 2021-05-17
corr_author: '1'
date_created: 2021-08-08T22:01:30Z
date_published: 2021-05-11T00:00:00Z
date_updated: 2026-04-16T09:28:46Z
day: '11'
department:
- _id: KrPi
- _id: GradSch
doi: 10.1007/978-3-030-75539-3_17
ec_funded: 1
intvolume: ' 12704'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2020/670
month: '05'
oa: 1
oa_version: Submitted Version
page: 399-421
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Topics in Cryptology – CT-RSA 2021
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030755386'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Inverse-Sybil attacks in automated contact tracing
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12704
year: '2021'
...
---
_id: '9987'
abstract:
- lang: eng
text: 'Stateless model checking (SMC) is one of the standard approaches to the verification
of concurrent programs. As scheduling non-determinism creates exponentially large
spaces of thread interleavings, SMC attempts to partition this space into equivalence
classes and explore only a few representatives from each class. The efficiency
of this approach depends on two factors: (a) the coarseness of the partitioning,
and (b) the time to generate representatives in each class. For this reason, the
search for coarse partitionings that are efficiently explorable is an active research
challenge. In this work we present RVF-SMC , a new SMC algorithm that uses a
novel reads-value-from (RVF) partitioning. Intuitively, two interleavings are
deemed equivalent if they agree on the value obtained in each read event, and
read events induce consistent causal orderings between them. The RVF partitioning
is provably coarser than recent approaches based on Mazurkiewicz and “reads-from”
partitionings. Our experimental evaluation reveals that RVF is quite often a very
effective equivalence, as the underlying partitioning is exponentially coarser
than other approaches. Moreover, RVF-SMC generates representatives very efficiently,
as the reduction in the partitioning is often met with significant speed-ups in
the model checking task.'
acknowledgement: The research was partially funded by the ERC CoG 863818 (ForM-SMArt)
and the Vienna Science and Technology Fund (WWTF) through project ICT15-003.
alternative_title:
- LNCS
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Pratyush
full_name: Agarwal, Pratyush
last_name: Agarwal
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Shreya
full_name: Pathak, Shreya
last_name: Pathak
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
- first_name: Viktor
full_name: Toman, Viktor
id: 3AF3DA7C-F248-11E8-B48F-1D18A9856A87
last_name: Toman
orcid: 0000-0001-9036-063X
citation:
ama: 'Agarwal P, Chatterjee K, Pathak S, Pavlogiannis A, Toman V. Stateless model
checking under a reads-value-from equivalence. In: 33rd International Conference
on Computer-Aided Verification . Vol 12759. Springer Nature; 2021:341-366.
doi:10.1007/978-3-030-81685-8_16'
apa: 'Agarwal, P., Chatterjee, K., Pathak, S., Pavlogiannis, A., & Toman, V.
(2021). Stateless model checking under a reads-value-from equivalence. In 33rd
International Conference on Computer-Aided Verification (Vol. 12759, pp.
341–366). Virtual: Springer Nature. https://doi.org/10.1007/978-3-030-81685-8_16'
chicago: Agarwal, Pratyush, Krishnendu Chatterjee, Shreya Pathak, Andreas Pavlogiannis,
and Viktor Toman. “Stateless Model Checking under a Reads-Value-from Equivalence.”
In 33rd International Conference on Computer-Aided Verification , 12759:341–66.
Springer Nature, 2021. https://doi.org/10.1007/978-3-030-81685-8_16.
ieee: P. Agarwal, K. Chatterjee, S. Pathak, A. Pavlogiannis, and V. Toman, “Stateless
model checking under a reads-value-from equivalence,” in 33rd International
Conference on Computer-Aided Verification , Virtual, 2021, vol. 12759, pp.
341–366.
ista: 'Agarwal P, Chatterjee K, Pathak S, Pavlogiannis A, Toman V. 2021. Stateless
model checking under a reads-value-from equivalence. 33rd International Conference
on Computer-Aided Verification . CAV: Computer Aided Verification , LNCS, vol.
12759, 341–366.'
mla: Agarwal, Pratyush, et al. “Stateless Model Checking under a Reads-Value-from
Equivalence.” 33rd International Conference on Computer-Aided Verification
, vol. 12759, Springer Nature, 2021, pp. 341–66, doi:10.1007/978-3-030-81685-8_16.
short: P. Agarwal, K. Chatterjee, S. Pathak, A. Pavlogiannis, V. Toman, in:, 33rd
International Conference on Computer-Aided Verification , Springer Nature, 2021,
pp. 341–366.
conference:
end_date: 2021-07-23
location: Virtual
name: 'CAV: Computer Aided Verification '
start_date: 2021-07-20
corr_author: '1'
date_created: 2021-09-05T22:01:24Z
date_published: 2021-07-15T00:00:00Z
date_updated: 2026-04-08T07:00:30Z
day: '15'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1007/978-3-030-81685-8_16
ec_funded: 1
external_id:
arxiv:
- '2105.06424'
isi:
- '000698732400016'
file:
- access_level: open_access
checksum: 4b346e5fbaa8b9bdf107819c7b2aadee
content_type: application/pdf
creator: dernst
date_created: 2022-05-13T07:00:20Z
date_updated: 2022-05-13T07:00:20Z
file_id: '11368'
file_name: 2021_LNCS_Agarwal.pdf
file_size: 1516756
relation: main_file
success: 1
file_date_updated: 2022-05-13T07:00:20Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 341-366
project:
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: '33rd International Conference on Computer-Aided Verification '
publication_identifier:
eisbn:
- 978-3-030-81685-8
eissn:
- 1611-3349
isbn:
- 978-3-030-81684-1
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '10199'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Stateless model checking under a reads-value-from equivalence
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: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: '12759 '
year: '2021'
...
---
_id: '10865'
abstract:
- lang: eng
text: "We introduce the notion of Witness Maps as a cryptographic notion of a proof
system. A Unique Witness Map (UWM) deterministically maps all witnesses for an
\ NP statement to a single representative witness, resulting in a computationally
sound, deterministic-prover, non-interactive witness independent proof system.
A relaxation of UWM, called Compact Witness Map (CWM), maps all the witnesses
to a small number of witnesses, resulting in a “lossy” deterministic-prover, non-interactive
proof-system. We also define a Dual Mode Witness Map (DMWM) which adds an “extractable”
mode to a CWM.\r\nOur main construction is a DMWM for all NP relations, assuming
sub-exponentially secure indistinguishability obfuscation ( iO ), along with
standard cryptographic assumptions. The DMWM construction relies on a CWM and
a new primitive called Cumulative All-Lossy-But-One Trapdoor Functions (C-ALBO-TDF),
both of which are in turn instantiated based on iO and other primitives. Our
instantiation of a CWM is in fact a UWM; in turn, we show that a UWM implies Witness
Encryption. Along the way to constructing UWM and C-ALBO-TDF, we also construct,
from standard assumptions, Puncturable Digital Signatures and a new primitive
called Cumulative Lossy Trapdoor Functions (C-LTDF). The former improves up on
a construction of Bellare et al. (Eurocrypt 2016), who relied on sub-exponentially
secure iO and sub-exponentially secure OWF.\r\nAs an application of our constructions,
we show how to use a DMWM to construct the first leakage and tamper-resilient
signatures with a deterministic signer, thereby solving a decade old open problem
posed by Katz and Vaikunthanathan (Asiacrypt 2009), by Boyle, Segev and Wichs
(Eurocrypt 2011), as well as by Faonio and Venturi (Asiacrypt 2016). Our construction
achieves the optimal leakage rate of 1−o(1) ."
acknowledgement: We would like to thank the anonymous reviewers of PKC 2019 for their
useful comments and suggestions. We thank Omer Paneth for pointing out to us the
connection between Unique Witness Maps (UWM) and Witness encryption (WE). The first
author would like to acknowledge Pandu Rangan for his involvement during the initial
discussion phase of the project.
article_processing_charge: No
author:
- first_name: Suvradip
full_name: Chakraborty, Suvradip
id: B9CD0494-D033-11E9-B219-A439E6697425
last_name: Chakraborty
- first_name: Manoj
full_name: Prabhakaran, Manoj
last_name: Prabhakaran
- first_name: Daniel
full_name: Wichs, Daniel
last_name: Wichs
citation:
ama: 'Chakraborty S, Prabhakaran M, Wichs D. Witness maps and applications. In:
Kiayias A, ed. Public-Key Cryptography. Vol 12110. LNCS. Cham: Springer
Nature; 2020:220-246. doi:10.1007/978-3-030-45374-9_8'
apa: 'Chakraborty, S., Prabhakaran, M., & Wichs, D. (2020). Witness maps and
applications. In A. Kiayias (Ed.), Public-Key Cryptography (Vol. 12110,
pp. 220–246). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-45374-9_8'
chicago: 'Chakraborty, Suvradip, Manoj Prabhakaran, and Daniel Wichs. “Witness Maps
and Applications.” In Public-Key Cryptography, edited by A Kiayias, 12110:220–46.
LNCS. Cham: Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45374-9_8.'
ieee: 'S. Chakraborty, M. Prabhakaran, and D. Wichs, “Witness maps and applications,”
in Public-Key Cryptography, vol. 12110, A. Kiayias, Ed. Cham: Springer
Nature, 2020, pp. 220–246.'
ista: 'Chakraborty S, Prabhakaran M, Wichs D. 2020.Witness maps and applications.
In: Public-Key Cryptography. vol. 12110, 220–246.'
mla: Chakraborty, Suvradip, et al. “Witness Maps and Applications.” Public-Key
Cryptography, edited by A Kiayias, vol. 12110, Springer Nature, 2020, pp.
220–46, doi:10.1007/978-3-030-45374-9_8.
short: S. Chakraborty, M. Prabhakaran, D. Wichs, in:, A. Kiayias (Ed.), Public-Key
Cryptography, Springer Nature, Cham, 2020, pp. 220–246.
corr_author: '1'
date_created: 2022-03-18T11:35:51Z
date_published: 2020-04-29T00:00:00Z
date_updated: 2026-04-16T10:21:31Z
day: '29'
doi: 10.1007/978-3-030-45374-9_8
editor:
- first_name: A
full_name: Kiayias, A
last_name: Kiayias
external_id:
isi:
- '001299210200008'
intvolume: ' 12110'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2020/090
month: '04'
oa: 1
oa_version: Preprint
page: 220-246
place: Cham
publication: Public-Key Cryptography
publication_identifier:
eisbn:
- '9783030453749'
eissn:
- 1611-3349
isbn:
- '9783030453732'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Witness maps and applications
type: book_chapter
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12110
year: '2020'
...
---
_id: '18251'
abstract:
- lang: eng
text: Magnetic Resonance Imaging (MRI) has long been considered to be among the
gold standards of today’s diagnostic imaging. The most significant drawback of
MRI is long acquisition times, prohibiting its use in standard practice for some
applications. Compressed sensing (CS) proposes to subsample the k-space (the Fourier
domain dual to the physical space of spatial coordinates) leading to significantly
accelerated acquisition. However, the benefit of compressed sensing has not been
fully exploited; most of the sampling densities obtained through CS do not produce
a trajectory that obeys the stringent constraints of the MRI machine imposed in
practice. Inspired by recent success of deep learning-based approaches for image
reconstruction and ideas from computational imaging on learning-based design of
imaging systems, we introduce 3D FLAT, a novel protocol for data-driven design
of 3D non-Cartesian accelerated trajectories in MRI. Our proposal leverages the
entire 3D k-space to simultaneously learn a physically feasible acquisition trajectory
with a reconstruction method. Experimental results, performed as a proof-of-concept,
suggest that 3D FLAT achieves higher image quality for a given readout time compared
to standard trajectories such as radial, stack-of-stars, or 2D learned trajectories
(trajectories that evolve only in the 2D plane while fully sampling along the
third dimension). Furthermore, we demonstrate evidence supporting the significant
benefit of performing MRI acquisitions using non-Cartesian 3D trajectories over
2D non-Cartesian trajectories acquired slice-wise.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Jonathan
full_name: Alush-Aben, Jonathan
last_name: Alush-Aben
- first_name: Linor
full_name: Ackerman-Schraier, Linor
last_name: Ackerman-Schraier
- first_name: Tomer
full_name: Weiss, Tomer
last_name: Weiss
- first_name: Sanketh
full_name: Vedula, Sanketh
last_name: Vedula
- first_name: Ortal
full_name: Senouf, Ortal
last_name: Senouf
- first_name: Alexander
full_name: Bronstein, Alexander
id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
last_name: Bronstein
orcid: 0000-0001-9699-8730
citation:
ama: 'Alush-Aben J, Ackerman-Schraier L, Weiss T, Vedula S, Senouf O, Bronstein
AM. 3D FLAT: Feasible learned acquisition trajectories for accelerated MRI. In:
International Workshop on Machine Learning for Medical Image Reconstruction.
Vol 12450. Springer Nature; 2020:3-16. doi:10.1007/978-3-030-61598-7_1'
apa: 'Alush-Aben, J., Ackerman-Schraier, L., Weiss, T., Vedula, S., Senouf, O.,
& Bronstein, A. M. (2020). 3D FLAT: Feasible learned acquisition trajectories
for accelerated MRI. In International Workshop on Machine Learning for Medical
Image Reconstruction (Vol. 12450, pp. 3–16). Lima, Peru: Springer Nature.
https://doi.org/10.1007/978-3-030-61598-7_1'
chicago: 'Alush-Aben, Jonathan, Linor Ackerman-Schraier, Tomer Weiss, Sanketh Vedula,
Ortal Senouf, and Alex M. Bronstein. “3D FLAT: Feasible Learned Acquisition Trajectories
for Accelerated MRI.” In International Workshop on Machine Learning for Medical
Image Reconstruction, 12450:3–16. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-61598-7_1.'
ieee: 'J. Alush-Aben, L. Ackerman-Schraier, T. Weiss, S. Vedula, O. Senouf, and
A. M. Bronstein, “3D FLAT: Feasible learned acquisition trajectories for accelerated
MRI,” in International Workshop on Machine Learning for Medical Image Reconstruction,
Lima, Peru, 2020, vol. 12450, pp. 3–16.'
ista: 'Alush-Aben J, Ackerman-Schraier L, Weiss T, Vedula S, Senouf O, Bronstein
AM. 2020. 3D FLAT: Feasible learned acquisition trajectories for accelerated MRI.
International Workshop on Machine Learning for Medical Image Reconstruction. MLMIR:
Workshop on Machine Learning for Medical Image Reconstruction, LNCS, vol. 12450,
3–16.'
mla: 'Alush-Aben, Jonathan, et al. “3D FLAT: Feasible Learned Acquisition Trajectories
for Accelerated MRI.” International Workshop on Machine Learning for Medical
Image Reconstruction, vol. 12450, Springer Nature, 2020, pp. 3–16, doi:10.1007/978-3-030-61598-7_1.'
short: J. Alush-Aben, L. Ackerman-Schraier, T. Weiss, S. Vedula, O. Senouf, A.M.
Bronstein, in:, International Workshop on Machine Learning for Medical Image Reconstruction,
Springer Nature, 2020, pp. 3–16.
conference:
end_date: 2020-10-08
location: Lima, Peru
name: 'MLMIR: Workshop on Machine Learning for Medical Image Reconstruction'
start_date: 2020-10-08
date_created: 2024-10-08T13:06:03Z
date_published: 2020-10-20T00:00:00Z
date_updated: 2025-01-23T15:13:44Z
day: '20'
doi: 10.1007/978-3-030-61598-7_1
extern: '1'
intvolume: ' 12450'
language:
- iso: eng
month: '10'
oa_version: None
page: 3 - 16
publication: International Workshop on Machine Learning for Medical Image Reconstruction
publication_identifier:
eisbn:
- '9783030615987'
eissn:
- 1611-3349
isbn:
- '9783030615970'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: '3D FLAT: Feasible learned acquisition trajectories for accelerated MRI'
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 12450
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
corr_author: '1'
date_created: 2020-05-10T22:00:49Z
date_published: 2020-04-17T00:00:00Z
date_updated: 2026-04-16T09:46:07Z
day: '17'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-030-45237-7_5
external_id:
isi:
- '001288734300005'
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'
isi: 1
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: Formal methods for the design and analysis of complex systems
publication: International Conference on Tools and Algorithms for the Construction
and Analysis of Systems
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030452360'
issn:
- 0302-9743
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: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12079
year: '2020'
...
---
_id: '7966'
abstract:
- lang: eng
text: "For 1≤m≤n, we consider a natural m-out-of-n multi-instance scenario for a
public-key encryption (PKE) scheme. An adversary, given n independent instances
of PKE, wins if he breaks at least m out of the n instances. In this work, we
are interested in the scaling factor of PKE schemes, SF, which measures how well
the difficulty of breaking m out of the n instances scales in m. That is, a scaling
factor SF=ℓ indicates that breaking m out of n instances is at least ℓ times more
difficult than breaking one single instance. A PKE scheme with small scaling factor
hence provides an ideal target for mass surveillance. In fact, the Logjam attack
(CCS 2015) implicitly exploited, among other things, an almost constant scaling
factor of ElGamal over finite fields (with shared group parameters).\r\n\r\nFor
Hashed ElGamal over elliptic curves, we use the generic group model to argue that
the scaling factor depends on the scheme's granularity. In low granularity, meaning
each public key contains its independent group parameter, the scheme has optimal
scaling factor SF=m; In medium and high granularity, meaning all public keys share
the same group parameter, the scheme still has a reasonable scaling factor SF=√m.
Our findings underline that instantiating ElGamal over elliptic curves should
be preferred to finite fields in a multi-instance scenario.\r\n\r\nAs our main
technical contribution, we derive new generic-group lower bounds of Ω(√(mp)) on
the difficulty of solving both the m-out-of-n Gap Discrete Logarithm and the m-out-of-n
Gap Computational Diffie-Hellman problem over groups of prime order p, extending
a recent result by Yun (EUROCRYPT 2015). We establish the lower bound by studying
the hardness of a related computational problem which we call the search-by-hypersurface
problem."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Federico
full_name: Giacon, Federico
last_name: Giacon
- first_name: Eike
full_name: Kiltz, Eike
last_name: Kiltz
citation:
ama: 'Auerbach B, Giacon F, Kiltz E. Everybody’s a target: Scalability in public-key
encryption. In: Advances in Cryptology – EUROCRYPT 2020. Vol 12107. Springer
Nature; 2020:475-506. doi:10.1007/978-3-030-45727-3_16'
apa: 'Auerbach, B., Giacon, F., & Kiltz, E. (2020). Everybody’s a target: Scalability
in public-key encryption. In Advances in Cryptology – EUROCRYPT 2020 (Vol.
12107, pp. 475–506). Springer Nature. https://doi.org/10.1007/978-3-030-45727-3_16'
chicago: 'Auerbach, Benedikt, Federico Giacon, and Eike Kiltz. “Everybody’s a Target:
Scalability in Public-Key Encryption.” In Advances in Cryptology – EUROCRYPT
2020, 12107:475–506. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45727-3_16.'
ieee: 'B. Auerbach, F. Giacon, and E. Kiltz, “Everybody’s a target: Scalability
in public-key encryption,” in Advances in Cryptology – EUROCRYPT 2020,
2020, vol. 12107, pp. 475–506.'
ista: 'Auerbach B, Giacon F, Kiltz E. 2020. Everybody’s a target: Scalability in
public-key encryption. Advances in Cryptology – EUROCRYPT 2020. EUROCRYPT: Theory
and Applications of Cryptographic Techniques, LNCS, vol. 12107, 475–506.'
mla: 'Auerbach, Benedikt, et al. “Everybody’s a Target: Scalability in Public-Key
Encryption.” Advances in Cryptology – EUROCRYPT 2020, vol. 12107, Springer
Nature, 2020, pp. 475–506, doi:10.1007/978-3-030-45727-3_16.'
short: B. Auerbach, F. Giacon, E. Kiltz, in:, Advances in Cryptology – EUROCRYPT
2020, Springer Nature, 2020, pp. 475–506.
conference:
end_date: 2020-05-15
name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
start_date: 2020-05-11
date_created: 2020-06-15T07:13:37Z
date_published: 2020-05-01T00:00:00Z
date_updated: 2026-04-16T10:21:02Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-030-45727-3_16
ec_funded: 1
external_id:
isi:
- '000828688000016'
intvolume: ' 12107'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/364
month: '05'
oa: 1
oa_version: Submitted Version
page: 475-506
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Advances in Cryptology – EUROCRYPT 2020
publication_identifier:
eisbn:
- '9783030457273'
eissn:
- 1611-3349
isbn:
- '9783030457266'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Everybody’s a target: Scalability in public-key encryption'
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12107
year: '2020'
...
---
_id: '8194'
abstract:
- lang: eng
text: 'Fixed-point arithmetic is a popular alternative to floating-point arithmetic
on embedded systems. Existing work on the verification of fixed-point programs
relies on custom formalizations of fixed-point arithmetic, which makes it hard
to compare the described techniques or reuse the implementations. In this paper,
we address this issue by proposing and formalizing an SMT theory of fixed-point
arithmetic. We present an intuitive yet comprehensive syntax of the fixed-point
theory, and provide formal semantics for it based on rational arithmetic. We also
describe two decision procedures for this theory: one based on the theory of bit-vectors
and the other on the theory of reals. We implement the two decision procedures,
and evaluate our implementations using existing mature SMT solvers on a benchmark
suite we created. Finally, we perform a case study of using the theory we propose
to verify properties of quantized neural networks.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Marek
full_name: Baranowski, Marek
last_name: Baranowski
- first_name: Shaobo
full_name: He, Shaobo
last_name: He
- first_name: Mathias
full_name: Lechner, Mathias
id: 3DC22916-F248-11E8-B48F-1D18A9856A87
last_name: Lechner
- first_name: Thanh Son
full_name: Nguyen, Thanh Son
last_name: Nguyen
- first_name: Zvonimir
full_name: Rakamarić, Zvonimir
last_name: Rakamarić
citation:
ama: 'Baranowski M, He S, Lechner M, Nguyen TS, Rakamarić Z. An SMT theory of fixed-point
arithmetic. In: Automated Reasoning. Vol 12166. Springer Nature; 2020:13-31.
doi:10.1007/978-3-030-51074-9_2'
apa: 'Baranowski, M., He, S., Lechner, M., Nguyen, T. S., & Rakamarić, Z. (2020).
An SMT theory of fixed-point arithmetic. In Automated Reasoning (Vol. 12166,
pp. 13–31). Paris, France: Springer Nature. https://doi.org/10.1007/978-3-030-51074-9_2'
chicago: Baranowski, Marek, Shaobo He, Mathias Lechner, Thanh Son Nguyen, and Zvonimir
Rakamarić. “An SMT Theory of Fixed-Point Arithmetic.” In Automated Reasoning,
12166:13–31. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-51074-9_2.
ieee: M. Baranowski, S. He, M. Lechner, T. S. Nguyen, and Z. Rakamarić, “An SMT
theory of fixed-point arithmetic,” in Automated Reasoning, Paris, France,
2020, vol. 12166, pp. 13–31.
ista: 'Baranowski M, He S, Lechner M, Nguyen TS, Rakamarić Z. 2020. An SMT theory
of fixed-point arithmetic. Automated Reasoning. IJCAR: International Joint Conference
on Automated Reasoning, LNCS, vol. 12166, 13–31.'
mla: Baranowski, Marek, et al. “An SMT Theory of Fixed-Point Arithmetic.” Automated
Reasoning, vol. 12166, Springer Nature, 2020, pp. 13–31, doi:10.1007/978-3-030-51074-9_2.
short: M. Baranowski, S. He, M. Lechner, T.S. Nguyen, Z. Rakamarić, in:, Automated
Reasoning, Springer Nature, 2020, pp. 13–31.
conference:
end_date: 2020-07-04
location: Paris, France
name: 'IJCAR: International Joint Conference on Automated Reasoning'
start_date: 2020-07-01
date_created: 2020-08-02T22:00:59Z
date_published: 2020-06-24T00:00:00Z
date_updated: 2026-06-18T19:31:14Z
day: '24'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-030-51074-9_2
external_id:
isi:
- '000884318000002'
intvolume: ' 12166'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/978-3-030-51074-9_2
month: '06'
oa: 1
oa_version: Published Version
page: 13-31
project:
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
publication: Automated Reasoning
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030510732'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: An SMT theory of fixed-point arithmetic
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12166
year: '2020'
...
---
_id: '8195'
abstract:
- lang: eng
text: This paper presents a foundation for refining concurrent programs with structured
control flow. The verification problem is decomposed into subproblems that aid
interactive program development, proof reuse, and automation. The formalization
in this paper is the basis of a new design and implementation of the Civl verifier.
acknowledgement: "Bernhard Kragl and Thomas A. Henzinger were supported by\r\nthe
Austrian Science Fund (FWF) under grant Z211-N23 (Wittgenstein Award)."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Bernhard
full_name: Kragl, Bernhard
id: 320FC952-F248-11E8-B48F-1D18A9856A87
last_name: Kragl
orcid: 0000-0001-7745-9117
- first_name: Shaz
full_name: Qadeer, Shaz
last_name: Qadeer
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
citation:
ama: 'Kragl B, Qadeer S, Henzinger TA. Refinement for structured concurrent programs.
In: Computer Aided Verification. Vol 12224. Springer Nature; 2020:275-298.
doi:10.1007/978-3-030-53288-8_14'
apa: Kragl, B., Qadeer, S., & Henzinger, T. A. (2020). Refinement for structured
concurrent programs. In Computer Aided Verification (Vol. 12224, pp. 275–298).
Springer Nature. https://doi.org/10.1007/978-3-030-53288-8_14
chicago: Kragl, Bernhard, Shaz Qadeer, and Thomas A Henzinger. “Refinement for Structured
Concurrent Programs.” In Computer Aided Verification, 12224:275–98. Springer
Nature, 2020. https://doi.org/10.1007/978-3-030-53288-8_14.
ieee: B. Kragl, S. Qadeer, and T. A. Henzinger, “Refinement for structured concurrent
programs,” in Computer Aided Verification, 2020, vol. 12224, pp. 275–298.
ista: Kragl B, Qadeer S, Henzinger TA. 2020. Refinement for structured concurrent
programs. Computer Aided Verification. , LNCS, vol. 12224, 275–298.
mla: Kragl, Bernhard, et al. “Refinement for Structured Concurrent Programs.” Computer
Aided Verification, vol. 12224, Springer Nature, 2020, pp. 275–98, doi:10.1007/978-3-030-53288-8_14.
short: B. Kragl, S. Qadeer, T.A. Henzinger, in:, Computer Aided Verification, Springer
Nature, 2020, pp. 275–298.
corr_author: '1'
date_created: 2020-08-03T11:45:35Z
date_published: 2020-07-14T00:00:00Z
date_updated: 2026-04-08T07:23:52Z
day: '14'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-030-53288-8_14
external_id:
isi:
- '000695276000014'
file:
- access_level: open_access
content_type: application/pdf
creator: dernst
date_created: 2020-08-06T08:14:54Z
date_updated: 2020-08-06T08:14:54Z
file_id: '8201'
file_name: 2020_LNCS_Kragl.pdf
file_size: 804237
relation: main_file
success: 1
file_date_updated: 2020-08-06T08:14:54Z
has_accepted_license: '1'
intvolume: ' 12224'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 275-298
project:
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
publication: Computer Aided Verification
publication_identifier:
eisbn:
- '9783030532888'
eissn:
- 1611-3349
isbn:
- '9783030532871'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '8332'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Refinement for structured concurrent programs
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 12224
year: '2020'
...
---
_id: '8272'
abstract:
- lang: eng
text: We study turn-based stochastic zero-sum games with lexicographic preferences
over reachability and safety objectives. Stochastic games are standard models
in control, verification, and synthesis of stochastic reactive systems that exhibit
both randomness as well as angelic and demonic non-determinism. Lexicographic
order allows to consider multiple objectives with a strict preference order over
the satisfaction of the objectives. To the best of our knowledge, stochastic games
with lexicographic objectives have not been studied before. We establish determinacy
of such games and present strategy and computational complexity results. For strategy
complexity, we show that lexicographically optimal strategies exist that are deterministic
and memory is only required to remember the already satisfied and violated objectives.
For a constant number of objectives, we show that the relevant decision problem
is in NP∩coNP , matching the current known bound for single objectives; and
in general the decision problem is PSPACE -hard and can be solved in NEXPTIME∩coNEXPTIME
. We present an algorithm that computes the lexicographically optimal strategies
via a reduction to computation of optimal strategies in a sequence of single-objectives
games. We have implemented our algorithm and report experimental results on various
case studies.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Joost P
full_name: Katoen, Joost P
id: 4524F760-F248-11E8-B48F-1D18A9856A87
last_name: Katoen
orcid: 0000-0002-6143-1926
- first_name: Maximilian
full_name: Weininger, Maximilian
last_name: Weininger
- first_name: Tobias
full_name: Winkler, Tobias
last_name: Winkler
citation:
ama: 'Chatterjee K, Katoen JP, Weininger M, Winkler T. Stochastic games with lexicographic
reachability-safety objectives. In: International Conference on Computer Aided
Verification. Vol 12225. Springer Nature; 2020:398-420. doi:10.1007/978-3-030-53291-8_21'
apa: Chatterjee, K., Katoen, J. P., Weininger, M., & Winkler, T. (2020). Stochastic
games with lexicographic reachability-safety objectives. In International Conference
on Computer Aided Verification (Vol. 12225, pp. 398–420). Springer Nature.
https://doi.org/10.1007/978-3-030-53291-8_21
chicago: Chatterjee, Krishnendu, Joost P Katoen, Maximilian Weininger, and Tobias
Winkler. “Stochastic Games with Lexicographic Reachability-Safety Objectives.”
In International Conference on Computer Aided Verification, 12225:398–420.
Springer Nature, 2020. https://doi.org/10.1007/978-3-030-53291-8_21.
ieee: K. Chatterjee, J. P. Katoen, M. Weininger, and T. Winkler, “Stochastic games
with lexicographic reachability-safety objectives,” in International Conference
on Computer Aided Verification, 2020, vol. 12225, pp. 398–420.
ista: 'Chatterjee K, Katoen JP, Weininger M, Winkler T. 2020. Stochastic games with
lexicographic reachability-safety objectives. International Conference on Computer
Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 12225, 398–420.'
mla: Chatterjee, Krishnendu, et al. “Stochastic Games with Lexicographic Reachability-Safety
Objectives.” International Conference on Computer Aided Verification, vol.
12225, Springer Nature, 2020, pp. 398–420, doi:10.1007/978-3-030-53291-8_21.
short: K. Chatterjee, J.P. Katoen, M. Weininger, T. Winkler, in:, International
Conference on Computer Aided Verification, Springer Nature, 2020, pp. 398–420.
conference:
name: 'CAV: Computer Aided Verification'
date_created: 2020-08-16T22:00:58Z
date_published: 2020-07-14T00:00:00Z
date_updated: 2026-04-16T09:31:14Z
day: '14'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1007/978-3-030-53291-8_21
ec_funded: 1
external_id:
arxiv:
- '2005.04018'
isi:
- '000695272500021'
file:
- access_level: open_access
checksum: 093d4788d7d5b2ce0ffe64fbe7820043
content_type: application/pdf
creator: dernst
date_created: 2020-08-17T11:32:44Z
date_updated: 2020-08-17T11:32:44Z
file_id: '8276'
file_name: 2020_LNCS_CAV_Chatterjee.pdf
file_size: 625056
relation: main_file
success: 1
file_date_updated: 2020-08-17T11:32:44Z
has_accepted_license: '1'
intvolume: ' 12225'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 398-420
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
publication: International Conference on Computer Aided Verification
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030532901'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '12738'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Stochastic games with lexicographic reachability-safety objectives
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: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12225
year: '2020'
...
---
_id: '8322'
abstract:
- lang: eng
text: "Reverse firewalls were introduced at Eurocrypt 2015 by Miro-nov and Stephens-Davidowitz,
as a method for protecting cryptographic protocols against attacks on the devices
of the honest parties. In a nutshell: a reverse firewall is placed outside of
a device and its goal is to “sanitize” the messages sent by it, in such a way
that a malicious device cannot leak its secrets to the outside world. It is typically
assumed that the cryptographic devices are attacked in a “functionality-preserving
way” (i.e. informally speaking, the functionality of the protocol remains unchanged
under this attacks). In their paper, Mironov and Stephens-Davidowitz construct
a protocol for passively-secure two-party computations with firewalls, leaving
extension of this result to stronger models as an open question.\r\nIn this paper,
we address this problem by constructing a protocol for secure computation with
firewalls that has two main advantages over the original protocol from Eurocrypt
2015. Firstly, it is a multiparty computation protocol (i.e. it works for an arbitrary
number n of the parties, and not just for 2). Secondly, it is secure in much stronger
corruption settings, namely in the active corruption model. More precisely: we
consider an adversary that can fully corrupt up to \U0001D45B−1 parties, while
the remaining parties are corrupt in a functionality-preserving way.\r\nOur core
techniques are: malleable commitments and malleable non-interactive zero-knowledge,
which in particular allow us to create a novel protocol for multiparty augmented
coin-tossing into the well with reverse firewalls (that is based on a protocol
of Lindell from Crypto 2001)."
acknowledgement: We would like to thank the anonymous reviewers for their helpful
comments and suggestions. The work was initiated while the first author was in IIT
Madras, India. Part of this work was done while the author was visiting the University
of Warsaw. This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(682815 - TOCNeT) and from the Foundation for Polish Science under grant TEAM/2016-1/4
founded within the UE 2014–2020 Smart Growth Operational Program. The last author
was supported by the Independent Research Fund Denmark project BETHE and the Concordium
Blockchain Research Center, Aarhus University, Denmark.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Suvradip
full_name: Chakraborty, Suvradip
id: B9CD0494-D033-11E9-B219-A439E6697425
last_name: Chakraborty
- first_name: Stefan
full_name: Dziembowski, Stefan
last_name: Dziembowski
- first_name: Jesper Buus
full_name: Nielsen, Jesper Buus
last_name: Nielsen
citation:
ama: 'Chakraborty S, Dziembowski S, Nielsen JB. Reverse firewalls for actively secure MPCs.
In: Advances in Cryptology – CRYPTO 2020. Vol 12171. Springer Nature; 2020:732-762.
doi:10.1007/978-3-030-56880-1_26'
apa: 'Chakraborty, S., Dziembowski, S., & Nielsen, J. B. (2020). Reverse firewalls for actively secure MPCs.
In Advances in Cryptology – CRYPTO 2020 (Vol. 12171, pp. 732–762). Santa
Barbara, CA, United States: Springer Nature. https://doi.org/10.1007/978-3-030-56880-1_26'
chicago: Chakraborty, Suvradip, Stefan Dziembowski, and Jesper Buus Nielsen. “Reverse Firewalls for Actively Secure MPCs.”
In Advances in Cryptology – CRYPTO 2020, 12171:732–62. Springer Nature,
2020. https://doi.org/10.1007/978-3-030-56880-1_26.
ieee: S. Chakraborty, S. Dziembowski, and J. B. Nielsen, “Reverse firewalls for actively secure MPCs,”
in Advances in Cryptology – CRYPTO 2020, Santa Barbara, CA, United States,
2020, vol. 12171, pp. 732–762.
ista: 'Chakraborty S, Dziembowski S, Nielsen JB. 2020. Reverse firewalls for actively secure MPCs.
Advances in Cryptology – CRYPTO 2020. CRYPTO: Annual International Cryptology
Conference, LNCS, vol. 12171, 732–762.'
mla: Chakraborty, Suvradip, et al. “Reverse Firewalls for Actively Secure MPCs.”
Advances in Cryptology – CRYPTO 2020, vol. 12171, Springer Nature, 2020,
pp. 732–62, doi:10.1007/978-3-030-56880-1_26.
short: S. Chakraborty, S. Dziembowski, J.B. Nielsen, in:, Advances in Cryptology
– CRYPTO 2020, Springer Nature, 2020, pp. 732–762.
conference:
end_date: 2020-08-21
location: Santa Barbara, CA, United States
name: 'CRYPTO: Annual International Cryptology Conference'
start_date: 2020-08-17
date_created: 2020-08-30T22:01:12Z
date_published: 2020-08-10T00:00:00Z
date_updated: 2026-04-16T09:31:34Z
day: '10'
department:
- _id: KrPi
doi: 10.1007/978-3-030-56880-1_26
ec_funded: 1
external_id:
isi:
- '001415325700026'
intvolume: ' 12171'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/1317
month: '08'
oa: 1
oa_version: Preprint
page: 732-762
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Advances in Cryptology – CRYPTO 2020
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030568795'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Reverse firewalls for actively secure MPCs
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12171
year: '2020'
...
---
_id: '8339'
abstract:
- lang: eng
text: "Discrete Gaussian distributions over lattices are central to lattice-based
cryptography, and to the computational and mathematical aspects of lattices more
broadly. The literature contains a wealth of useful theorems about the behavior
of discrete Gaussians under convolutions and related operations. Yet despite their
structural similarities, most of these theorems are formally incomparable, and
their proofs tend to be monolithic and written nearly “from scratch,” making them
unnecessarily hard to verify, understand, and extend.\r\nIn this work we present
a modular framework for analyzing linear operations on discrete Gaussian distributions.
The framework abstracts away the particulars of Gaussians, and usually reduces
proofs to the choice of appropriate linear transformations and elementary linear
algebra. To showcase the approach, we establish several general properties of
discrete Gaussians, and show how to obtain all prior convolution theorems (along
with some new ones) as straightforward corollaries. As another application, we
describe a self-reduction for Learning With Errors (LWE) that uses a fixed number
of samples to generate an unlimited number of additional ones (having somewhat
larger error). The distinguishing features of our reduction are its simple analysis
in our framework, and its exclusive use of discrete Gaussians without any loss
in parameters relative to a prior mixed discrete-and-continuous approach.\r\nAs
a contribution of independent interest, for subgaussian random matrices we prove
a singular value concentration bound with explicitly stated constants, and we
give tighter heuristics for specific distributions that are commonly used for
generating lattice trapdoors. These bounds yield improvements in the concrete
bit-security estimates for trapdoor lattice cryptosystems."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Nicholas
full_name: Genise, Nicholas
last_name: Genise
- first_name: Daniele
full_name: Micciancio, Daniele
last_name: Micciancio
- first_name: Chris
full_name: Peikert, Chris
last_name: Peikert
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Genise N, Micciancio D, Peikert C, Walter M. Improved discrete Gaussian and
subgaussian analysis for lattice cryptography. In: 23rd IACR International
Conference on the Practice and Theory of Public-Key Cryptography. Vol 12110.
Springer Nature; 2020:623-651. doi:10.1007/978-3-030-45374-9_21'
apa: 'Genise, N., Micciancio, D., Peikert, C., & Walter, M. (2020). Improved
discrete Gaussian and subgaussian analysis for lattice cryptography. In 23rd
IACR International Conference on the Practice and Theory of Public-Key Cryptography
(Vol. 12110, pp. 623–651). Edinburgh, United Kingdom: Springer Nature. https://doi.org/10.1007/978-3-030-45374-9_21'
chicago: Genise, Nicholas, Daniele Micciancio, Chris Peikert, and Michael Walter.
“Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography.”
In 23rd IACR International Conference on the Practice and Theory of Public-Key
Cryptography, 12110:623–51. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45374-9_21.
ieee: N. Genise, D. Micciancio, C. Peikert, and M. Walter, “Improved discrete Gaussian
and subgaussian analysis for lattice cryptography,” in 23rd IACR International
Conference on the Practice and Theory of Public-Key Cryptography, Edinburgh,
United Kingdom, 2020, vol. 12110, pp. 623–651.
ista: 'Genise N, Micciancio D, Peikert C, Walter M. 2020. Improved discrete Gaussian
and subgaussian analysis for lattice cryptography. 23rd IACR International Conference
on the Practice and Theory of Public-Key Cryptography. PKC: Public-Key Cryptography,
LNCS, vol. 12110, 623–651.'
mla: Genise, Nicholas, et al. “Improved Discrete Gaussian and Subgaussian Analysis
for Lattice Cryptography.” 23rd IACR International Conference on the Practice
and Theory of Public-Key Cryptography, vol. 12110, Springer Nature, 2020,
pp. 623–51, doi:10.1007/978-3-030-45374-9_21.
short: N. Genise, D. Micciancio, C. Peikert, M. Walter, in:, 23rd IACR International
Conference on the Practice and Theory of Public-Key Cryptography, Springer Nature,
2020, pp. 623–651.
conference:
end_date: 2020-05-07
location: Edinburgh, United Kingdom
name: 'PKC: Public-Key Cryptography'
start_date: 2020-05-04
date_created: 2020-09-06T22:01:13Z
date_published: 2020-05-15T00:00:00Z
date_updated: 2026-04-16T09:32:27Z
day: '15'
department:
- _id: KrPi
doi: 10.1007/978-3-030-45374-9_21
ec_funded: 1
external_id:
isi:
- '001299210200021'
intvolume: ' 12110'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2020/337
month: '05'
oa: 1
oa_version: Preprint
page: 623-651
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 23rd IACR International Conference on the Practice and Theory of Public-Key
Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030453732'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Improved discrete Gaussian and subgaussian analysis for lattice cryptography
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12110
year: '2020'
...
---
_id: '8623'
abstract:
- lang: eng
text: We introduce the monitoring of trace properties under assumptions. An assumption
limits the space of possible traces that the monitor may encounter. An assumption
may result from knowledge about the system that is being monitored, about the
environment, or about another, connected monitor. We define monitorability under
assumptions and study its theoretical properties. In particular, we show that
for every assumption A, the boolean combinations of properties that are safe or
co-safe relative to A are monitorable under A. We give several examples and constructions
on how an assumption can make a non-monitorable property monitorable, and how
an assumption can make a monitorable property monitorable with fewer resources,
such as integer registers.
acknowledgement: This research was supported in part by the Austrian Science Fund
(FWF) under grant Z211-N23 (Wittgenstein Award).
alternative_title:
- LNCS
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: Naci E
full_name: Sarac, Naci E
id: 8C6B42F8-C8E6-11E9-A03A-F2DCE5697425
last_name: Sarac
citation:
ama: 'Henzinger TA, Sarac NE. Monitorability under assumptions. In: Runtime Verification.
Vol 12399. Springer Nature; 2020:3-18. doi:10.1007/978-3-030-60508-7_1'
apa: 'Henzinger, T. A., & Sarac, N. E. (2020). Monitorability under assumptions.
In Runtime Verification (Vol. 12399, pp. 3–18). Los Angeles, CA, United
States: Springer Nature. https://doi.org/10.1007/978-3-030-60508-7_1'
chicago: Henzinger, Thomas A, and Naci E Sarac. “Monitorability under Assumptions.”
In Runtime Verification, 12399:3–18. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-60508-7_1.
ieee: T. A. Henzinger and N. E. Sarac, “Monitorability under assumptions,” in Runtime
Verification, Los Angeles, CA, United States, 2020, vol. 12399, pp. 3–18.
ista: 'Henzinger TA, Sarac NE. 2020. Monitorability under assumptions. Runtime Verification.
RV: Runtime Verification, LNCS, vol. 12399, 3–18.'
mla: Henzinger, Thomas A., and Naci E. Sarac. “Monitorability under Assumptions.”
Runtime Verification, vol. 12399, Springer Nature, 2020, pp. 3–18, doi:10.1007/978-3-030-60508-7_1.
short: T.A. Henzinger, N.E. Sarac, in:, Runtime Verification, Springer Nature, 2020,
pp. 3–18.
conference:
end_date: 2020-10-09
location: Los Angeles, CA, United States
name: 'RV: Runtime Verification'
start_date: 2020-10-06
date_created: 2020-10-07T15:05:37Z
date_published: 2020-10-02T00:00:00Z
date_updated: 2026-04-16T10:22:01Z
day: '02'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-030-60508-7_1
external_id:
isi:
- '000728160600001'
file:
- access_level: open_access
checksum: 00661f9b7034f52e18bf24fa552b8194
content_type: application/pdf
creator: esarac
date_created: 2020-10-15T14:28:06Z
date_updated: 2020-10-15T14:28:06Z
file_id: '8665'
file_name: monitorability.pdf
file_size: 478148
relation: main_file
success: 1
file_date_updated: 2020-10-15T14:28:06Z
has_accepted_license: '1'
intvolume: ' 12399'
isi: 1
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 3-18
project:
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
publication: Runtime Verification
publication_identifier:
eisbn:
- '9783030605087'
eissn:
- 1611-3349
isbn:
- '9783030605070'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Monitorability under assumptions
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12399
year: '2020'
...
---
_id: '8732'
abstract:
- lang: eng
text: 'A simple drawing D(G) of a graph G is one where each pair of edges share
at most one point: either a common endpoint or a proper crossing. An edge e in
the complement of G can be inserted into D(G) if there exists a simple drawing
of G+e extending D(G). As a result of Levi’s Enlargement Lemma, if a drawing
is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement
of lines (pseudolines), then any edge in the complement of G can be inserted.
In contrast, we show that it is NP -complete to decide whether one edge can
be inserted into a simple drawing. This remains true even if we assume that the
drawing is pseudocircular, that is, the edges can be extended to an arrangement
of pseudocircles. On the positive side, we show that, given an arrangement of
pseudocircles A and a pseudosegment σ , it can be decided in polynomial time
whether there exists a pseudocircle Φσ extending σ for which A∪{Φσ} is
again an arrangement of pseudocircles.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- first_name: Fabian
full_name: Klute, Fabian
last_name: Klute
- first_name: Irene
full_name: Parada, Irene
last_name: Parada
- first_name: Raimund
full_name: Seidel, Raimund
last_name: Seidel
- first_name: Birgit
full_name: Vogtenhuber, Birgit
last_name: Vogtenhuber
- first_name: Tilo
full_name: Wiedera, Tilo
last_name: Wiedera
citation:
ama: 'Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T.
Inserting one edge into a simple drawing is hard. In: Graph-Theoretic Concepts
in Computer Science. Vol 12301. Springer Nature; 2020:325-338. doi:10.1007/978-3-030-60440-0_26'
apa: 'Arroyo Guevara, A. M., Klute, F., Parada, I., Seidel, R., Vogtenhuber, B.,
& Wiedera, T. (2020). Inserting one edge into a simple drawing is hard. In
Graph-Theoretic Concepts in Computer Science (Vol. 12301, pp. 325–338).
Leeds, United Kingdom: Springer Nature. https://doi.org/10.1007/978-3-030-60440-0_26'
chicago: Arroyo Guevara, Alan M, Fabian Klute, Irene Parada, Raimund Seidel, Birgit
Vogtenhuber, and Tilo Wiedera. “Inserting One Edge into a Simple Drawing Is Hard.”
In Graph-Theoretic Concepts in Computer Science, 12301:325–38. Springer
Nature, 2020. https://doi.org/10.1007/978-3-030-60440-0_26.
ieee: A. M. Arroyo Guevara, F. Klute, I. Parada, R. Seidel, B. Vogtenhuber, and
T. Wiedera, “Inserting one edge into a simple drawing is hard,” in Graph-Theoretic
Concepts in Computer Science, Leeds, United Kingdom, 2020, vol. 12301, pp.
325–338.
ista: 'Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T.
2020. Inserting one edge into a simple drawing is hard. Graph-Theoretic Concepts
in Computer Science. WG: Workshop on Graph-Theoretic Concepts in Computer Science,
LNCS, vol. 12301, 325–338.'
mla: Arroyo Guevara, Alan M., et al. “Inserting One Edge into a Simple Drawing Is
Hard.” Graph-Theoretic Concepts in Computer Science, vol. 12301, Springer
Nature, 2020, pp. 325–38, doi:10.1007/978-3-030-60440-0_26.
short: A.M. Arroyo Guevara, F. Klute, I. Parada, R. Seidel, B. Vogtenhuber, T. Wiedera,
in:, Graph-Theoretic Concepts in Computer Science, Springer Nature, 2020, pp.
325–338.
conference:
end_date: 2020-06-26
location: Leeds, United Kingdom
name: 'WG: Workshop on Graph-Theoretic Concepts in Computer Science'
start_date: 2020-06-24
date_created: 2020-11-06T08:45:03Z
date_published: 2020-10-09T00:00:00Z
date_updated: 2026-04-16T10:22:35Z
day: '09'
department:
- _id: UlWa
doi: 10.1007/978-3-030-60440-0_26
ec_funded: 1
external_id:
isi:
- '001299688100026'
intvolume: ' 12301'
isi: 1
language:
- iso: eng
month: '10'
oa_version: None
page: 325-338
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Graph-Theoretic Concepts in Computer Science
publication_identifier:
eisbn:
- '9783030604400'
eissn:
- 1611-3349
isbn:
- '9783030604394'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Inserting one edge into a simple drawing is hard
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12301
year: '2020'
...