---
_id: '10048'
abstract:
- lang: eng
text: "The security of cryptographic primitives and protocols against adversaries
that are allowed to make adaptive choices (e.g., which parties to corrupt or which
queries to make) is notoriously difficult to establish. A broad theoretical\r\nframework
was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper
we initiate the study of lower bounds on loss in adaptive security for certain
cryptographic protocols considered in the framework. We prove lower\r\nbounds
that almost match the upper bounds (proven using the framework) for proxy re-encryption,
prefix-constrained PRFs and generalized selective decryption, a security game
that captures the security of certain group messaging and\r\nbroadcast encryption
schemes. Those primitives have in common that their security game involves an
underlying graph that can be adaptively built by the adversary. Some of our lower
bounds only apply to a restricted class of black-box reductions which we term
“oblivious” (the existing upper bounds are of this restricted type), some apply
to the broader but still restricted class of non-rewinding reductions, while our
lower bound for proxy re-encryption applies to all black-box reductions. The fact
that some of our lower bounds seem to crucially rely on obliviousness or at least
a non-rewinding reduction hints to the exciting possibility that the existing
upper bounds can be improved by using more sophisticated reductions. Our main
conceptual contribution is a two-player multi-stage game called the Builder-Pebbler
Game. We can translate bounds on the winning probabilities for various instantiations
of this game into cryptographic lower bounds for the above-mentioned primitives
using oracle separation techniques.\r\n"
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
orcid: 0009-0006-6812-7317
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- 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
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in
security games on graphs. In: 19th Theory of Cryptography Conference 2021.
International Association for Cryptologic Research; 2021.'
apa: 'Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (2021). The
cost of adaptivity in security games on graphs. In 19th Theory of Cryptography
Conference 2021. Raleigh, NC, United States: International Association for
Cryptologic Research.'
chicago: Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael
Walter. “The Cost of Adaptivity in Security Games on Graphs.” In 19th Theory
of Cryptography Conference 2021. International Association for Cryptologic
Research, 2021.
ieee: C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity
in security games on graphs,” in 19th Theory of Cryptography Conference 2021,
Raleigh, NC, United States, 2021.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity
in security games on graphs. 19th Theory of Cryptography Conference 2021. TCC:
Theory of Cryptography Conference.'
mla: Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on
Graphs.” 19th Theory of Cryptography Conference 2021, International Association
for Cryptologic Research, 2021.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th Theory of
Cryptography Conference 2021, International Association for Cryptologic Research,
2021.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography Conference'
start_date: 2021-11-08
cryptoeprintid: 1
das_tickbox: '1'
date_created: 2021-09-27T12:52:05Z
date_published: 2021-07-08T00:00:00Z
date_updated: 2026-07-06T13:16:17Z
day: '08'
department:
- _id: KrPi
external_id:
cryptoeprintid:
- 2021/059
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://ia.cr/2021/059
month: '07'
oa: 1
oa_version: Preprint
publication: 19th Theory of Cryptography Conference 2021
publication_status: published
publisher: International Association for Cryptologic Research
quality_controlled: '1'
related_material:
record:
- id: '10410'
relation: later_version
status: public
- id: '10035'
relation: dissertation_contains
status: public
status: public
title: The cost of adaptivity in security games on graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '10044'
abstract:
- lang: eng
text: We show that Yao’s garbling scheme is adaptively indistinguishable for the
class of Boolean circuits of size S and treewidth w with only a S^O(w) loss in
security. For instance, circuits with constant treewidth are as a result adaptively
indistinguishable with only a polynomial loss. This (partially) complements a
negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way
functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main
technical contributions, we introduce a new pebble game that abstracts out our
security reduction and then present a pebbling strategy for this game where the
number of pebbles used is roughly O(d w log(S)), d being the fan-out of the circuit.
The design of the strategy relies on separators, a graph-theoretic notion with
connections to circuit complexity.
acknowledgement: 'We would like to thank Daniel Wichs for helpful discussions on the
landscape of adaptive security of Yao’s garbling. '
article_number: 2021/926
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
orcid: 0009-0006-6812-7317
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s
garbling. In: 19th Theory of Cryptography Conference 2021. International
Association for Cryptologic Research; 2021.'
apa: 'Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2021). On treewidth,
separators and Yao’s garbling. In 19th Theory of Cryptography Conference 2021.
Raleigh, NC, United States: International Association for Cryptologic Research.'
chicago: Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth,
Separators and Yao’s Garbling.” In 19th Theory of Cryptography Conference 2021.
International Association for Cryptologic Research, 2021.
ieee: C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators
and Yao’s garbling,” in 19th Theory of Cryptography Conference 2021, Raleigh,
NC, United States, 2021.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ. 2021. On treewidth, separators and
Yao’s garbling. 19th Theory of Cryptography Conference 2021. TCC: Theory of Cryptography
Conference, 2021/926.'
mla: Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.”
19th Theory of Cryptography Conference 2021, 2021/926, International Association
for Cryptologic Research, 2021.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th Theory of Cryptography
Conference 2021, International Association for Cryptologic Research, 2021.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography Conference'
start_date: 2021-11-08
cryptoeprintid: 1
das_tickbox: '1'
date_created: 2021-09-24T12:01:34Z
date_published: 2021-07-08T00:00:00Z
date_updated: 2026-07-06T13:15:57Z
day: '08'
department:
- _id: KrPi
ec_funded: 1
external_id:
cryptoeprintid:
- 2021/926
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/926
month: '07'
oa: 1
oa_version: Preprint
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 19th Theory of Cryptography Conference 2021
publication_status: published
publisher: International Association for Cryptologic Research
quality_controlled: '1'
related_material:
record:
- id: '10409'
relation: later_version
status: public
- id: '10035'
relation: dissertation_contains
status: public
status: public
title: On treewidth, separators and Yao's garbling
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '10674'
abstract:
- lang: eng
text: 'In two-player games on graphs, the players move a token through a graph to
produce an infinite path, which determines the winner of the game. Such games
are central in formal methods since they model the interaction between a non-terminating
system and its environment. In bidding games the players bid for the right to
move the token: in each round, the players simultaneously submit bids, and the
higher bidder moves the token and pays the other player. Bidding games are known
to have a clean and elegant mathematical structure that relies on the ability
of the players to submit arbitrarily small bids. Many applications, however, require
a fixed granularity for the bids, which can represent, for example, the monetary
value expressed in cents. We study, for the first time, the combination of discrete-bidding
and infinite-duration games. Our most important result proves that these games
form a large determined subclass of concurrent games, where determinacy is the
strong property that there always exists exactly one player who can guarantee
winning the game. In particular, we show that, in contrast to non-discrete bidding
games, the mechanism with which tied bids are resolved plays an important role
in discrete-bidding games. We study several natural tie-breaking mechanisms and
show that, while some do not admit determinacy, most natural mechanisms imply
determinacy for every pair of initial budgets.'
acknowledgement: "This research was supported in part by the Austrian Science Fund
(FWF) under grants S11402-N23 (RiSE/SHiNE), Z211-N23 (Wittgenstein Award), and M
2369-N33 (Meitner fellowship).\r\n"
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Milad
full_name: Aghajohari, Milad
last_name: Aghajohari
- first_name: Guy
full_name: Avni, Guy
id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
last_name: Avni
orcid: 0000-0001-5588-8287
- 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: Aghajohari M, Avni G, Henzinger TA. Determinacy in discrete-bidding infinite-duration
games. Logical Methods in Computer Science. 2021;17(1):10:1-10:23. doi:10.23638/LMCS-17(1:10)2021
apa: Aghajohari, M., Avni, G., & Henzinger, T. A. (2021). Determinacy in discrete-bidding
infinite-duration games. Logical Methods in Computer Science. EPI Sciences.
https://doi.org/10.23638/LMCS-17(1:10)2021
chicago: Aghajohari, Milad, Guy Avni, and Thomas A Henzinger. “Determinacy in Discrete-Bidding
Infinite-Duration Games.” Logical Methods in Computer Science. EPI Sciences,
2021. https://doi.org/10.23638/LMCS-17(1:10)2021.
ieee: M. Aghajohari, G. Avni, and T. A. Henzinger, “Determinacy in discrete-bidding
infinite-duration games,” Logical Methods in Computer Science, vol. 17,
no. 1. EPI Sciences, p. 10:1-10:23, 2021.
ista: Aghajohari M, Avni G, Henzinger TA. 2021. Determinacy in discrete-bidding
infinite-duration games. Logical Methods in Computer Science. 17(1), 10:1-10:23.
mla: Aghajohari, Milad, et al. “Determinacy in Discrete-Bidding Infinite-Duration
Games.” Logical Methods in Computer Science, vol. 17, no. 1, EPI Sciences,
2021, p. 10:1-10:23, doi:10.23638/LMCS-17(1:10)2021.
short: M. Aghajohari, G. Avni, T.A. Henzinger, Logical Methods in Computer Science
17 (2021) 10:1-10:23.
corr_author: '1'
das_tickbox: '1'
date_created: 2022-01-25T16:32:13Z
date_published: 2021-02-03T00:00:00Z
date_updated: 2026-07-06T13:21:45Z
day: '03'
ddc:
- '510'
department:
- _id: ToHe
doi: 10.23638/LMCS-17(1:10)2021
external_id:
arxiv:
- '1905.03588'
isi:
- '000658724600010'
file:
- access_level: open_access
checksum: b35586a50ed1ca8f44767de116d18d81
content_type: application/pdf
creator: alisjak
date_created: 2022-01-26T08:04:50Z
date_updated: 2022-01-26T08:04:50Z
file_id: '10690'
file_name: 2021_LMCS_AGHAJOHAR.pdf
file_size: 819878
relation: main_file
success: 1
file_date_updated: 2022-01-26T08:04:50Z
has_accepted_license: '1'
intvolume: ' 17'
isi: 1
issue: '1'
keyword:
- computer science
- computer science and game theory
- logic in computer science
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: 10:1-10:23
project:
- _id: 264B3912-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02369
name: Formal Methods meets Algorithmic Game Theory
- _id: 25F2ACDE-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-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: Logical Methods in Computer Science
publication_identifier:
eissn:
- 1860-5974
publication_status: published
publisher: EPI Sciences
quality_controlled: '1'
scopus_import: '1'
status: public
title: Determinacy in discrete-bidding infinite-duration games
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 17
year: '2021'
...
---
_id: '10023'
abstract:
- lang: eng
text: We study the temporal dissipation of variance and relative entropy for ergodic
Markov Chains in continuous time, and compute explicitly the corresponding dissipation
rates. These are identified, as is well known, in the case of the variance in
terms of an appropriate Hilbertian norm; and in the case of the relative entropy,
in terms of a Dirichlet form which morphs into a version of the familiar Fisher
information under conditions of detailed balance. Here we obtain trajectorial
versions of these results, valid along almost every path of the random motion
and most transparent in the backwards direction of time. Martingale arguments
and time reversal play crucial roles, as in the recent work of Karatzas, Schachermayer
and Tschiderer for conservative diffusions. Extensions are developed to general
“convex divergences” and to countable state-spaces. The steepest descent and gradient
flow properties for the variance, the relative entropy, and appropriate generalizations,
are studied along with their respective geometries under conditions of detailed
balance, leading to a very direct proof for the HWI inequality of Otto and Villani
in the present context.
acknowledgement: I.K. acknowledges support from the U.S. National Science Foundation
under Grant NSF-DMS-20-04997. J.M. acknowledges support from the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No 716117) and from the Austrian Science Fund (FWF) through project
F65. W.S. acknowledges support from the Austrian Science Fund (FWF) under grant
P28861 and by the Vienna Science and Technology Fund (WWTF) through projects MA14-008
and MA16-021.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Ioannis
full_name: Karatzas, Ioannis
last_name: Karatzas
- first_name: Jan
full_name: Maas, Jan
id: 4C5696CE-F248-11E8-B48F-1D18A9856A87
last_name: Maas
orcid: 0000-0002-0845-1338
- first_name: Walter
full_name: Schachermayer, Walter
last_name: Schachermayer
citation:
ama: Karatzas I, Maas J, Schachermayer W. Trajectorial dissipation and gradient
flow for the relative entropy in Markov chains. Communications in Information
and Systems. 2021;21(4):481-536. doi:10.4310/CIS.2021.v21.n4.a1
apa: Karatzas, I., Maas, J., & Schachermayer, W. (2021). Trajectorial dissipation
and gradient flow for the relative entropy in Markov chains. Communications
in Information and Systems. International Press of Boston. https://doi.org/10.4310/CIS.2021.v21.n4.a1
chicago: Karatzas, Ioannis, Jan Maas, and Walter Schachermayer. “Trajectorial Dissipation
and Gradient Flow for the Relative Entropy in Markov Chains.” Communications
in Information and Systems. International Press of Boston, 2021. https://doi.org/10.4310/CIS.2021.v21.n4.a1.
ieee: I. Karatzas, J. Maas, and W. Schachermayer, “Trajectorial dissipation and
gradient flow for the relative entropy in Markov chains,” Communications in
Information and Systems, vol. 21, no. 4. International Press of Boston, pp.
481–536, 2021.
ista: Karatzas I, Maas J, Schachermayer W. 2021. Trajectorial dissipation and gradient
flow for the relative entropy in Markov chains. Communications in Information
and Systems. 21(4), 481–536.
mla: Karatzas, Ioannis, et al. “Trajectorial Dissipation and Gradient Flow for the
Relative Entropy in Markov Chains.” Communications in Information and Systems,
vol. 21, no. 4, International Press of Boston, 2021, pp. 481–536, doi:10.4310/CIS.2021.v21.n4.a1.
short: I. Karatzas, J. Maas, W. Schachermayer, Communications in Information and
Systems 21 (2021) 481–536.
das_tickbox: '1'
date_created: 2021-09-19T08:53:19Z
date_published: 2021-06-04T00:00:00Z
date_updated: 2026-07-06T13:38:10Z
day: '04'
department:
- _id: JaMa
doi: 10.4310/CIS.2021.v21.n4.a1
ec_funded: 1
external_id:
arxiv:
- '2005.14177'
intvolume: ' 21'
issue: '4'
keyword:
- Markov Chain
- relative entropy
- time reversal
- steepest descent
- gradient flow
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2005.14177
month: '06'
oa: 1
oa_version: Preprint
page: 481-536
project:
- _id: 256E75B8-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '716117'
name: Optimal Transport and Stochastic Dynamics
- _id: fc31cba2-9c52-11eb-aca3-ff467d239cd2
grant_number: F6504
name: Taming Complexity in Partial Differential Systems
publication: Communications in Information and Systems
publication_identifier:
issn:
- 1526-7555
publication_status: published
publisher: International Press of Boston
quality_controlled: '1'
status: public
title: Trajectorial dissipation and gradient flow for the relative entropy in Markov
chains
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 21
year: '2021'
...
---
_id: '10204'
abstract:
- lang: eng
text: Two common representations of close packings of identical spheres consisting
of hexagonal layers, called Barlow stackings, appear abundantly in minerals and
metals. These motifs, however, occupy an identical portion of space and bear identical
first-order topological signatures as measured by persistent homology. Here we
present a novel method based on k-fold covers that unambiguously distinguishes
between these patterns. Moreover, our approach provides topological evidence that
the FCC motif is the more stable of the two in the context of evolving experimental
sphere packings during the transition from disordered to an ordered state. We
conclude that our approach can be generalised to distinguish between various Barlow
stackings manifested in minerals and metals.
acknowledgement: MS acknowledges the support by Australian Research Council funding
through the ARC Training Centre for M3D Innovation (IC180100008). MS thanks M. Hanifpour
and N. Francois for their input and valuable discussions. This project has received
funding from the European Research Council (ERC) under the European Union's Horizon
2020 research and innovation programme, grant no. 788183 and from the Wittgenstein
Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.
article_processing_charge: No
article_type: original
author:
- first_name: Georg F
full_name: Osang, Georg F
id: 464B40D6-F248-11E8-B48F-1D18A9856A87
last_name: Osang
orcid: 0000-0002-8882-5116
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Mohammad
full_name: Saadatfar, Mohammad
last_name: Saadatfar
citation:
ama: Osang GF, Edelsbrunner H, Saadatfar M. Topological signatures and stability
of hexagonal close packing and Barlow stackings. Soft Matter. 2021;17(40):9107-9115.
doi:10.1039/d1sm00774b
apa: Osang, G. F., Edelsbrunner, H., & Saadatfar, M. (2021). Topological signatures
and stability of hexagonal close packing and Barlow stackings. Soft Matter.
Royal Society of Chemistry. https://doi.org/10.1039/d1sm00774b
chicago: Osang, Georg F, Herbert Edelsbrunner, and Mohammad Saadatfar. “Topological
Signatures and Stability of Hexagonal Close Packing and Barlow Stackings.” Soft
Matter. Royal Society of Chemistry, 2021. https://doi.org/10.1039/d1sm00774b.
ieee: G. F. Osang, H. Edelsbrunner, and M. Saadatfar, “Topological signatures and
stability of hexagonal close packing and Barlow stackings,” Soft Matter,
vol. 17, no. 40. Royal Society of Chemistry, pp. 9107–9115, 2021.
ista: Osang GF, Edelsbrunner H, Saadatfar M. 2021. Topological signatures and stability
of hexagonal close packing and Barlow stackings. Soft Matter. 17(40), 9107–9115.
mla: Osang, Georg F., et al. “Topological Signatures and Stability of Hexagonal
Close Packing and Barlow Stackings.” Soft Matter, vol. 17, no. 40, Royal
Society of Chemistry, 2021, pp. 9107–15, doi:10.1039/d1sm00774b.
short: G.F. Osang, H. Edelsbrunner, M. Saadatfar, Soft Matter 17 (2021) 9107–9115.
das_tickbox: '1'
date_created: 2021-10-31T23:01:30Z
date_published: 2021-10-20T00:00:00Z
date_updated: 2026-07-06T13:55:05Z
day: '20'
ddc:
- '540'
department:
- _id: HeEd
doi: 10.1039/d1sm00774b
ec_funded: 1
external_id:
isi:
- '000700090000001'
pmid:
- '34569592'
file:
- access_level: open_access
checksum: b4da0c420530295e61b153960f6cb350
content_type: application/pdf
creator: dernst
date_created: 2023-10-03T09:21:42Z
date_updated: 2023-10-03T09:21:42Z
file_id: '14385'
file_name: 2021_SoftMatter_acceptedversion_Osang.pdf
file_size: 4678788
relation: main_file
success: 1
file_date_updated: 2023-10-03T09:21:42Z
has_accepted_license: '1'
intvolume: ' 17'
isi: 1
issue: '40'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 9107-9115
pmid: 1
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
publication: Soft Matter
publication_identifier:
eissn:
- 1744-6848
issn:
- 1744-683X
publication_status: published
publisher: Royal Society of Chemistry
quality_controlled: '1'
scopus_import: '1'
status: public
title: Topological signatures and stability of hexagonal close packing and Barlow
stackings
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 17
year: '2021'
...
---
OA_place: publisher
_id: '9733'
abstract:
- lang: eng
text: This thesis is the result of the research carried out by the author during
his PhD at IST Austria between 2017 and 2021. It mainly focuses on the Fröhlich
polaron model, specifically to its regime of strong coupling. This model, which
is rigorously introduced and discussed in the introduction, has been of great
interest in condensed matter physics and field theory for more than eighty years.
It is used to describe an electron interacting with the atoms of a solid material
(the strength of this interaction is modeled by the presence of a coupling constant
α in the Hamiltonian of the system). The particular regime examined here, which
is mathematically described by considering the limit α →∞, displays many interesting
features related to the emergence of classical behavior, which allows for a simplified
effective description of the system under analysis. The properties, the range
of validity and a quantitative analysis of the precision of such classical approximations
are the main object of the present work. We specify our investigation to the study
of the ground state energy of the system, its dynamics and its effective mass.
For each of these problems, we provide in the introduction an overview of the
previously known results and a detailed account of the original contributions
by the author.
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Dario
full_name: Feliciangeli, Dario
id: 41A639AA-F248-11E8-B48F-1D18A9856A87
last_name: Feliciangeli
orcid: 0000-0003-0754-8530
citation:
ama: Feliciangeli D. The polaron at strong coupling. 2021. doi:10.15479/at:ista:9733
apa: Feliciangeli, D. (2021). The polaron at strong coupling. Institute of
Science and Technology Austria. https://doi.org/10.15479/at:ista:9733
chicago: Feliciangeli, Dario. “The Polaron at Strong Coupling.” Institute of Science
and Technology Austria, 2021. https://doi.org/10.15479/at:ista:9733.
ieee: D. Feliciangeli, “The polaron at strong coupling,” Institute of Science and
Technology Austria, 2021.
ista: Feliciangeli D. 2021. The polaron at strong coupling. Institute of Science
and Technology Austria.
mla: Feliciangeli, Dario. The Polaron at Strong Coupling. Institute of Science
and Technology Austria, 2021, doi:10.15479/at:ista:9733.
short: D. Feliciangeli, The Polaron at Strong Coupling, Institute of Science and
Technology Austria, 2021.
corr_author: '1'
date_created: 2021-07-27T15:48:30Z
date_published: 2021-08-20T00:00:00Z
date_updated: 2026-07-06T14:02:25Z
day: '20'
ddc:
- '515'
- '519'
- '539'
degree_awarded: PhD
department:
- _id: GradSch
- _id: RoSe
- _id: JaMa
doi: 10.15479/at:ista:9733
ec_funded: 1
file:
- access_level: open_access
checksum: e88bb8ca43948abe060eb2d2fa719881
content_type: application/pdf
creator: dfelicia
date_created: 2021-08-19T14:03:48Z
date_updated: 2021-09-06T09:28:56Z
file_id: '9944'
file_name: Thesis_FeliciangeliA.pdf
file_size: 1958710
relation: main_file
- access_level: closed
checksum: 72810843abee83705853505b3f8348aa
content_type: application/octet-stream
creator: dfelicia
date_created: 2021-08-19T14:06:35Z
date_updated: 2022-03-10T12:13:57Z
file_id: '9945'
file_name: thesis.7z
file_size: 3771669
relation: source_file
file_date_updated: 2022-03-10T12:13:57Z
has_accepted_license: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '08'
oa: 1
oa_version: Published Version
page: '180'
project:
- _id: 256E75B8-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '716117'
name: Optimal Transport and Stochastic Dynamics
- _id: 25C6DC12-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '694227'
name: Analysis of quantum many-body systems
- _id: fc31cba2-9c52-11eb-aca3-ff467d239cd2
grant_number: F6504
name: Taming Complexity in Partial Differential Systems
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '9787'
relation: part_of_dissertation
status: public
- id: '9792'
relation: part_of_dissertation
status: public
- id: '9791'
relation: part_of_dissertation
status: public
- id: '9225'
relation: part_of_dissertation
status: public
- id: '9781'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Robert
full_name: Seiringer, Robert
id: 4AFD0470-F248-11E8-B48F-1D18A9856A87
last_name: Seiringer
orcid: 0000-0002-6781-0521
- first_name: Jan
full_name: Maas, Jan
id: 4C5696CE-F248-11E8-B48F-1D18A9856A87
last_name: Maas
orcid: 0000-0002-0845-1338
title: The polaron at strong coupling
tmp:
image: /image/cc_by_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
short: CC BY-ND (4.0)
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2021'
...
---
_id: '10222'
abstract:
- lang: eng
text: Consider a random set of points on the unit sphere in ℝd, which can be either
uniformly sampled or a Poisson point process. Its convex hull is a random inscribed
polytope, whose boundary approximates the sphere. We focus on the case d = 3,
for which there are elementary proofs and fascinating formulas for metric properties.
In particular, we study the fraction of acute facets, the expected intrinsic volumes,
the total edge length, and the distance to a fixed point. Finally we generalize
the results to the ellipsoid with homeoid density.
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme,
grant no. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), grant
no. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization
in Geometry and Dynamics’, Austrian Science Fund (FWF), grant no. I 02979-N35.\r\nWe
are grateful to Dmitry Zaporozhets and Christoph Thäle for valuable comments and
for directing us to relevant references. We also thank to Anton Mellit for a useful
discussion on Bessel functions."
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Arseniy
full_name: Akopyan, Arseniy
id: 430D2C90-F248-11E8-B48F-1D18A9856A87
last_name: Akopyan
orcid: 0000-0002-2548-617X
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Anton
full_name: Nikitenko, Anton
id: 3E4FF1BA-F248-11E8-B48F-1D18A9856A87
last_name: Nikitenko
orcid: 0000-0002-0659-3201
citation:
ama: Akopyan A, Edelsbrunner H, Nikitenko A. The beauty of random polytopes inscribed
in the 2-sphere. Experimental Mathematics. 2021:1-15. doi:10.1080/10586458.2021.1980459
apa: Akopyan, A., Edelsbrunner, H., & Nikitenko, A. (2021). The beauty of random
polytopes inscribed in the 2-sphere. Experimental Mathematics. Taylor &
Francis. https://doi.org/10.1080/10586458.2021.1980459
chicago: Akopyan, Arseniy, Herbert Edelsbrunner, and Anton Nikitenko. “The Beauty
of Random Polytopes Inscribed in the 2-Sphere.” Experimental Mathematics.
Taylor & Francis, 2021. https://doi.org/10.1080/10586458.2021.1980459.
ieee: A. Akopyan, H. Edelsbrunner, and A. Nikitenko, “The beauty of random polytopes
inscribed in the 2-sphere,” Experimental Mathematics. Taylor & Francis,
pp. 1–15, 2021.
ista: Akopyan A, Edelsbrunner H, Nikitenko A. 2021. The beauty of random polytopes
inscribed in the 2-sphere. Experimental Mathematics., 1–15.
mla: Akopyan, Arseniy, et al. “The Beauty of Random Polytopes Inscribed in the 2-Sphere.”
Experimental Mathematics, Taylor & Francis, 2021, pp. 1–15, doi:10.1080/10586458.2021.1980459.
short: A. Akopyan, H. Edelsbrunner, A. Nikitenko, Experimental Mathematics (2021)
1–15.
corr_author: '1'
das_tickbox: '1'
date_created: 2021-11-07T23:01:25Z
date_published: 2021-10-25T00:00:00Z
date_updated: 2026-07-07T05:33:35Z
day: '25'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1080/10586458.2021.1980459
ec_funded: 1
external_id:
arxiv:
- '2007.07783'
isi:
- '000710893500001'
file:
- access_level: open_access
checksum: 3514382e3a1eb87fa6c61ad622874415
content_type: application/pdf
creator: dernst
date_created: 2023-08-14T11:55:10Z
date_updated: 2023-08-14T11:55:10Z
file_id: '14053'
file_name: 2023_ExperimentalMath_Akopyan.pdf
file_size: 1966019
relation: main_file
success: 1
file_date_updated: 2023-08-14T11:55:10Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: 1-15
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
- _id: 0aa4bc98-070f-11eb-9043-e6fff9c6a316
grant_number: I4887
name: Persistent Homology, Algorithms and Stochastic Geometry
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Experimental Mathematics
publication_identifier:
eissn:
- 1944-950X
issn:
- 1058-6458
publication_status: published
publisher: Taylor & Francis
quality_controlled: '1'
scopus_import: '1'
status: public
title: The beauty of random polytopes inscribed in the 2-sphere
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '9241'
abstract:
- lang: eng
text: 'Volumetric light transport is a pervasive physical phenomenon, and therefore
its accurate simulation is important for a broad array of disciplines. While suitable
mathematical models for computing the transport are now available, obtaining the
necessary material parameters needed to drive such simulations is a challenging
task: direct measurements of these parameters from material samples are seldom
possible. Building on the inverse scattering paradigm, we present a novel measurement
approach which indirectly infers the transport parameters from extrinsic observations
of multiple-scattered radiance. The novelty of the proposed approach lies in replacing
structured illumination with a structured reflector bonded to the sample, and
a robust fitting procedure that largely compensates for potential systematic errors
in the calibration of the setup. We show the feasibility of our approach by validating
simulations of complex 3D compositions of the measured materials against physical
prints, using photo-polymer resins. As presented in this paper, our technique
yields colorspace data suitable for accurate appearance reproduction in the area
of 3D printing. Beyond that, and without fundamental changes to the basic measurement
methodology, it could equally well be used to obtain spectral measurements that
are useful for other application areas.'
acknowledgement: "H2020 Marie Skłodowska-Curie Actions (642841); European Research
Council (715767); Grantová Agentura České Republiky (16-08111S, 16-18964S); Univerzita
Karlova v Praze (SVV-2017-260452); Engineering and Physical Sciences Research Council
(EP/K023578/1).\r\nWe are grateful to Stratasys Ltd. for access to the voxel-level
print interface of the J750\r\nmachine."
article_processing_charge: No
article_type: original
author:
- first_name: Oskar
full_name: Elek, Oskar
last_name: Elek
- first_name: Ran
full_name: Zhang, Ran
id: 4DDBCEB0-F248-11E8-B48F-1D18A9856A87
last_name: Zhang
orcid: 0000-0002-3808-281X
- first_name: Denis
full_name: Sumin, Denis
last_name: Sumin
- first_name: Karol
full_name: Myszkowski, Karol
last_name: Myszkowski
- first_name: Bernd
full_name: Bickel, Bernd
id: 49876194-F248-11E8-B48F-1D18A9856A87
last_name: Bickel
orcid: 0000-0001-6511-9385
- first_name: Alexander
full_name: Wilkie, Alexander
last_name: Wilkie
- first_name: Jaroslav
full_name: Křivánek, Jaroslav
last_name: Křivánek
- first_name: Tim
full_name: Weyrich, Tim
last_name: Weyrich
citation:
ama: Elek O, Zhang R, Sumin D, et al. Robust and practical measurement of volume
transport parameters in solid photo-polymer materials for 3D printing. Optics
Express. 2021;29(5):7568-7588. doi:10.1364/OE.406095
apa: Elek, O., Zhang, R., Sumin, D., Myszkowski, K., Bickel, B., Wilkie, A., … Weyrich,
T. (2021). Robust and practical measurement of volume transport parameters in
solid photo-polymer materials for 3D printing. Optics Express. Optica Publishing
Group. https://doi.org/10.1364/OE.406095
chicago: Elek, Oskar, Ran Zhang, Denis Sumin, Karol Myszkowski, Bernd Bickel, Alexander
Wilkie, Jaroslav Křivánek, and Tim Weyrich. “Robust and Practical Measurement
of Volume Transport Parameters in Solid Photo-Polymer Materials for 3D Printing.”
Optics Express. Optica Publishing Group, 2021. https://doi.org/10.1364/OE.406095.
ieee: O. Elek et al., “Robust and practical measurement of volume transport
parameters in solid photo-polymer materials for 3D printing,” Optics Express,
vol. 29, no. 5. Optica Publishing Group, pp. 7568–7588, 2021.
ista: Elek O, Zhang R, Sumin D, Myszkowski K, Bickel B, Wilkie A, Křivánek J, Weyrich
T. 2021. Robust and practical measurement of volume transport parameters in solid
photo-polymer materials for 3D printing. Optics Express. 29(5), 7568–7588.
mla: Elek, Oskar, et al. “Robust and Practical Measurement of Volume Transport Parameters
in Solid Photo-Polymer Materials for 3D Printing.” Optics Express, vol.
29, no. 5, Optica Publishing Group, 2021, pp. 7568–88, doi:10.1364/OE.406095.
short: O. Elek, R. Zhang, D. Sumin, K. Myszkowski, B. Bickel, A. Wilkie, J. Křivánek,
T. Weyrich, Optics Express 29 (2021) 7568–7588.
date_created: 2021-03-14T23:01:33Z
date_published: 2021-03-01T00:00:00Z
date_updated: 2026-07-07T05:54:53Z
day: '01'
ddc:
- '000'
department:
- _id: BeBi
doi: 10.1364/OE.406095
ec_funded: 1
external_id:
isi:
- '000624968100103'
file:
- access_level: open_access
checksum: a9697ad83136c19ad87e46aa2db63cfd
content_type: application/pdf
creator: dernst
date_created: 2021-03-22T08:15:28Z
date_updated: 2021-03-22T08:15:28Z
file_id: '9269'
file_name: 2021_OpticsExpress_Elek.pdf
file_size: 10873700
relation: main_file
success: 1
file_date_updated: 2021-03-22T08:15:28Z
has_accepted_license: '1'
intvolume: ' 29'
isi: 1
issue: '5'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: 7568-7588
project:
- _id: 2508E324-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '642841'
name: Distributed 3D Object Design
- _id: 24F9549A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '715767'
name: 'MATERIALIZABLE: Intelligent fabrication-oriented Computational Design and
Modeling'
publication: Optics Express
publication_identifier:
eissn:
- 1094-4087
publication_status: published
publisher: Optica Publishing Group
quality_controlled: '1'
scopus_import: '1'
status: public
title: Robust and practical measurement of volume transport parameters in solid photo-polymer
materials for 3D printing
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 29
year: '2021'
...
---
OA_place: repository
OA_type: green
_id: '10666'
abstract:
- lang: eng
text: Adversarial training is an effective method to train deep learning models
that are resilient to norm-bounded perturbations, with the cost of nominal performance
drop. While adversarial training appears to enhance the robustness and safety
of a deep model deployed in open-world decision-critical applications, counterintuitively,
it induces undesired behaviors in robot learning settings. In this paper, we show
theoretically and experimentally that neural controllers obtained via adversarial
training are subjected to three types of defects, namely transient, systematic,
and conditional errors. We first generalize adversarial training to a safety-domain
optimization scheme allowing for more generic specifications. We then prove that
such a learning process tends to cause certain error profiles. We support our
theoretical results by a thorough experimental safety analysis in a robot-learning
task. Our results suggest that adversarial training is not yet ready for robot
learning.
acknowledgement: M.L. and T.A.H. are supported in part by the Austrian Science Fund
(FWF) under grant Z211-N23 (Wittgenstein Award). R.H. and D.R. are supported by
Boeing and R.G. by Horizon-2020 ECSEL Project grant no. 783163 (iDev40).
article_processing_charge: No
arxiv: 1
author:
- first_name: Mathias
full_name: Lechner, Mathias
id: 3DC22916-F248-11E8-B48F-1D18A9856A87
last_name: Lechner
- first_name: Ramin
full_name: Hasani, Ramin
last_name: Hasani
- first_name: Radu
full_name: Grosu, Radu
last_name: Grosu
- first_name: Daniela
full_name: Rus, Daniela
last_name: Rus
- 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: 'Lechner M, Hasani R, Grosu R, Rus D, Henzinger TA. Adversarial training is
not ready for robot learning. In: 2021 IEEE International Conference on Robotics
and Automation. IEEE; 2021:4140-4147. doi:10.1109/ICRA48506.2021.9561036'
apa: 'Lechner, M., Hasani, R., Grosu, R., Rus, D., & Henzinger, T. A. (2021).
Adversarial training is not ready for robot learning. In 2021 IEEE International
Conference on Robotics and Automation (pp. 4140–4147). Xi’an, China: IEEE.
https://doi.org/10.1109/ICRA48506.2021.9561036'
chicago: Lechner, Mathias, Ramin Hasani, Radu Grosu, Daniela Rus, and Thomas A Henzinger.
“Adversarial Training Is Not Ready for Robot Learning.” In 2021 IEEE International
Conference on Robotics and Automation, 4140–47. IEEE, 2021. https://doi.org/10.1109/ICRA48506.2021.9561036.
ieee: M. Lechner, R. Hasani, R. Grosu, D. Rus, and T. A. Henzinger, “Adversarial
training is not ready for robot learning,” in 2021 IEEE International Conference
on Robotics and Automation, Xi’an, China, 2021, pp. 4140–4147.
ista: 'Lechner M, Hasani R, Grosu R, Rus D, Henzinger TA. 2021. Adversarial training
is not ready for robot learning. 2021 IEEE International Conference on Robotics
and Automation. ICRA: International Conference on Robotics and Automation, 4140–4147.'
mla: Lechner, Mathias, et al. “Adversarial Training Is Not Ready for Robot Learning.”
2021 IEEE International Conference on Robotics and Automation, IEEE, 2021,
pp. 4140–47, doi:10.1109/ICRA48506.2021.9561036.
short: M. Lechner, R. Hasani, R. Grosu, D. Rus, T.A. Henzinger, in:, 2021 IEEE International
Conference on Robotics and Automation, IEEE, 2021, pp. 4140–4147.
conference:
end_date: 2021-06-05
location: Xi'an, China
name: 'ICRA: International Conference on Robotics and Automation'
start_date: 2021-05-30
das_tickbox: '1'
date_created: 2022-01-25T15:44:54Z
date_published: 2021-06-01T00:00:00Z
date_updated: 2026-07-07T06:20:35Z
day: '01'
ddc:
- '000'
department:
- _id: GradSch
- _id: ToHe
doi: 10.1109/ICRA48506.2021.9561036
external_id:
arxiv:
- '2103.08187'
isi:
- '000765738803040'
has_accepted_license: '1'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-nd/3.0/
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2103.08187
month: '06'
oa: 1
oa_version: Preprint
page: 4140-4147
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: 2021 IEEE International Conference on Robotics and Automation
publication_identifier:
eisbn:
- 978-1-7281-9077-8
eissn:
- 2577-087X
isbn:
- 978-1-7281-9078-5
issn:
- 1050-4729
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '11362'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Adversarial training is not ready for robot learning
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported (CC BY-NC-ND
3.0)
short: CC BY-NC-ND (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '9678'
abstract:
- lang: eng
text: We introduce a new graph problem, the token dropping game, and we show how
to solve it efficiently in a distributed setting. We use the token dropping game
as a tool to design an efficient distributed algorithm for stable orientations
and more generally for locally optimal semi-matchings. The prior work by Czygrinow
et al. (DISC 2012) finds a stable orientation in O(Δ^5) rounds in graphs of maximum
degree Δ, while we improve it to O(Δ^4) and also prove a lower bound of Ω(Δ).
For the more general problem of locally optimal semi-matchings, the prior upper
bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement
for C = o(S); here C and S are the maximum degrees of customers and servers, respectively.
acknowledgement: We thank Orr Fischer, Juho Hirvonen, and Tuomo Lempiäinen for valuable
discussions. This project has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
No. 840605.
article_processing_charge: No
arxiv: 1
author:
- first_name: Sebastian
full_name: Brandt, Sebastian
last_name: Brandt
- first_name: Barbara
full_name: Keller, Barbara
last_name: Keller
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Jukka
full_name: Suomela, Jukka
last_name: Suomela
- first_name: Jara
full_name: Uitto, Jara
last_name: Uitto
citation:
ama: 'Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. Efficient load-balancing
through distributed token dropping. In: Annual ACM Symposium on Parallelism
in Algorithms and Architectures. Association for Computing Machinery; 2021:129-139.
doi:10.1145/3409964.3461785'
apa: 'Brandt, S., Keller, B., Rybicki, J., Suomela, J., & Uitto, J. (2021).
Efficient load-balancing through distributed token dropping. In Annual ACM
Symposium on Parallelism in Algorithms and Architectures (pp. 129–139). Virtual
Event, United States: Association for Computing Machinery. https://doi.org/10.1145/3409964.3461785'
chicago: Brandt, Sebastian, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara
Uitto. “Efficient Load-Balancing through Distributed Token Dropping.” In Annual
ACM Symposium on Parallelism in Algorithms and Architectures, 129–39. Association
for Computing Machinery, 2021. https://doi.org/10.1145/3409964.3461785.
ieee: S. Brandt, B. Keller, J. Rybicki, J. Suomela, and J. Uitto, “Efficient load-balancing
through distributed token dropping,” in Annual ACM Symposium on Parallelism
in Algorithms and Architectures, Virtual Event, United States, 2021, pp.
129–139.
ista: 'Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. 2021. Efficient load-balancing
through distributed token dropping. Annual ACM Symposium on Parallelism in Algorithms
and Architectures. SPAA: Symposium on Parallelism in Algorithms and Architectures
, 129–139.'
mla: Brandt, Sebastian, et al. “Efficient Load-Balancing through Distributed Token
Dropping.” Annual ACM Symposium on Parallelism in Algorithms and Architectures,
Association for Computing Machinery, 2021, pp. 129–39, doi:10.1145/3409964.3461785.
short: S. Brandt, B. Keller, J. Rybicki, J. Suomela, J. Uitto, in:, Annual ACM Symposium
on Parallelism in Algorithms and Architectures, Association for Computing Machinery,
2021, pp. 129–139.
conference:
end_date: 2021-07-08
location: ' Virtual Event, United States'
name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures '
start_date: 2021-07-06
das_tickbox: '1'
date_created: 2021-07-18T22:01:22Z
date_published: 2021-07-06T00:00:00Z
date_updated: 2026-07-07T06:21:32Z
day: '06'
department:
- _id: DaAl
doi: 10.1145/3409964.3461785
ec_funded: 1
external_id:
arxiv:
- '2005.07761'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2005.07761
month: '07'
oa: 1
oa_version: Preprint
page: 129-139
project:
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: Annual ACM Symposium on Parallelism in Algorithms and Architectures
publication_identifier:
isbn:
- '9781450380706'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '15074'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Efficient load-balancing through distributed token dropping
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '10667'
abstract:
- lang: eng
text: Bayesian neural networks (BNNs) place distributions over the weights of a
neural network to model uncertainty in the data and the network's prediction.
We consider the problem of verifying safety when running a Bayesian neural network
policy in a feedback loop with infinite time horizon systems. Compared to the
existing sampling-based approaches, which are inapplicable to the infinite time
horizon setting, we train a separate deterministic neural network that serves
as an infinite time horizon safety certificate. In particular, we show that the
certificate network guarantees the safety of the system over a subset of the BNN
weight posterior's support. Our method first computes a safe weight set and then
alters the BNN's weight posterior to reject samples outside this set. Moreover,
we show how to extend our approach to a safe-exploration reinforcement learning
setting, in order to avoid unsafe trajectories during the training of the policy.
We evaluate our approach on a series of reinforcement learning benchmarks, including
non-Lyapunovian safety specifications.
acknowledgement: This research was supported in part by the Austrian Science Fund
(FWF) under grant Z211-N23 (Wittgenstein Award), ERC CoG 863818 (FoRM-SMArt), and
the European Union’s Horizon 2020 research and innovation programme under the Marie
Skłodowska-Curie Grant Agreement No. 665385.
alternative_title:
- ' Advances in Neural Information Processing Systems'
article_processing_charge: No
arxiv: 1
author:
- first_name: Mathias
full_name: Lechner, Mathias
id: 3DC22916-F248-11E8-B48F-1D18A9856A87
last_name: Lechner
- first_name: Ðorđe
full_name: Žikelić, Ðorđe
last_name: Žikelić
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- 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: 'Lechner M, Žikelić Ð, Chatterjee K, Henzinger TA. Infinite time horizon safety
of Bayesian neural networks. In: 35th Conference on Neural Information Processing
Systems. Neural Information Processing Systems Foundation; 2021. doi:10.48550/arXiv.2111.03165'
apa: 'Lechner, M., Žikelić, Ð., Chatterjee, K., & Henzinger, T. A. (2021). Infinite
time horizon safety of Bayesian neural networks. In 35th Conference on Neural
Information Processing Systems. Virtual: Neural Information Processing Systems
Foundation. https://doi.org/10.48550/arXiv.2111.03165'
chicago: Lechner, Mathias, Ðorđe Žikelić, Krishnendu Chatterjee, and Thomas A Henzinger.
“Infinite Time Horizon Safety of Bayesian Neural Networks.” In 35th Conference
on Neural Information Processing Systems. Neural Information Processing Systems
Foundation, 2021. https://doi.org/10.48550/arXiv.2111.03165.
ieee: M. Lechner, Ð. Žikelić, K. Chatterjee, and T. A. Henzinger, “Infinite time
horizon safety of Bayesian neural networks,” in 35th Conference on Neural Information
Processing Systems, Virtual, 2021.
ista: 'Lechner M, Žikelić Ð, Chatterjee K, Henzinger TA. 2021. Infinite time horizon
safety of Bayesian neural networks. 35th Conference on Neural Information Processing
Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information
Processing Systems, .'
mla: Lechner, Mathias, et al. “Infinite Time Horizon Safety of Bayesian Neural Networks.”
35th Conference on Neural Information Processing Systems, Neural Information
Processing Systems Foundation, 2021, doi:10.48550/arXiv.2111.03165.
short: M. Lechner, Ð. Žikelić, K. Chatterjee, T.A. Henzinger, in:, 35th Conference
on Neural Information Processing Systems, Neural Information Processing Systems
Foundation, 2021.
conference:
end_date: 2021-12-10
location: Virtual
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2021-12-06
corr_author: '1'
das_tickbox: '1'
date_created: 2022-01-25T15:45:58Z
date_published: 2021-12-01T00:00:00Z
date_updated: 2026-07-07T06:49:10Z
day: '01'
ddc:
- '000'
department:
- _id: GradSch
- _id: ToHe
- _id: KrCh
doi: 10.48550/arXiv.2111.03165
ec_funded: 1
external_id:
arxiv:
- '2111.03165'
file:
- access_level: open_access
checksum: 0fc0f852525c10dda9cc9ffea07fb4e4
content_type: application/pdf
creator: mlechner
date_created: 2022-01-26T07:39:59Z
date_updated: 2022-01-26T07:39:59Z
file_id: '10682'
file_name: infinite_time_horizon_safety_o.pdf
file_size: 452492
relation: main_file
success: 1
file_date_updated: 2022-01-26T07:39:59Z
has_accepted_license: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://proceedings.neurips.cc/paper/2021/hash/544defa9fddff50c53b71c43e0da72be-Abstract.html
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
publication: 35th Conference on Neural Information Processing Systems
publication_identifier:
issn:
- 1049-5258
publication_status: published
publisher: Neural Information Processing Systems Foundation
quality_controlled: '1'
related_material:
record:
- id: '11362'
relation: dissertation_contains
status: public
status: public
title: Infinite time horizon safety of Bayesian neural networks
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported (CC BY-NC-ND
3.0)
short: CC BY-NC-ND (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '10670'
abstract:
- lang: eng
text: "Imitation learning enables high-fidelity, vision-based learning of policies
within rich, photorealistic environments. However, such techniques often rely
on traditional discrete-time neural models and face difficulties in generalizing
to domain shifts by failing to account for the causal relationships between the
agent and the environment. In this paper, we propose a theoretical and experimental
framework for learning causal representations using continuous-time neural networks,
specifically over their discrete-time counterparts. We evaluate our method in
the context of visual-control learning of drones over a series of complex tasks,
ranging from short- and long-term navigation, to chasing static and dynamic objects
through photorealistic environments. Our results demonstrate that causal continuous-time\r\ndeep
models can perform robust navigation tasks, where advanced recurrent models fail.
These models learn complex causal control representations directly from raw visual
inputs and scale to solve a variety of tasks using imitation learning."
acknowledgement: "C.V., R.H. A.A. and D.R. are partially supported by Boeing and MIT.
A.A. is supported by the National Science Foundation (NSF) Graduate Research Fellowship
Program. M.L. is supported in part by the Austrian Science Fund (FWF) under grant
Z211-N23 (Wittgenstein Award). Research was sponsored by the United States Air Force
Research Laboratory and the United States Air Force Artificial Intelligence Accelerator
and was accomplished under Cooperative Agreement Number FA8750-19-2-1000. The views
and conclusions contained in this document are those of the authors\r\nand should
not be interpreted as representing the official policies, either expressed or implied,
of the United States Air Force or the U.S. Government. The U.S. Government is authorized
to reproduce and distribute reprints for Government purposes notwithstanding any
copyright notation herein.\r\n"
alternative_title:
- ' Advances in Neural Information Processing Systems'
article_processing_charge: No
arxiv: 1
author:
- first_name: Charles J
full_name: Vorbach, Charles J
last_name: Vorbach
- first_name: Ramin
full_name: Hasani, Ramin
last_name: Hasani
- first_name: Alexander
full_name: Amini, Alexander
last_name: Amini
- first_name: Mathias
full_name: Lechner, Mathias
id: 3DC22916-F248-11E8-B48F-1D18A9856A87
last_name: Lechner
- first_name: Daniela
full_name: Rus, Daniela
last_name: Rus
citation:
ama: 'Vorbach CJ, Hasani R, Amini A, Lechner M, Rus D. Causal navigation by continuous-time
neural networks. In: 35th Conference on Neural Information Processing Systems.
Neural Information Processing Systems Foundation; 2021.'
apa: 'Vorbach, C. J., Hasani, R., Amini, A., Lechner, M., & Rus, D. (2021).
Causal navigation by continuous-time neural networks. In 35th Conference on
Neural Information Processing Systems. Virtual: Neural Information Processing
Systems Foundation.'
chicago: Vorbach, Charles J, Ramin Hasani, Alexander Amini, Mathias Lechner, and
Daniela Rus. “Causal Navigation by Continuous-Time Neural Networks.” In 35th
Conference on Neural Information Processing Systems. Neural Information Processing
Systems Foundation, 2021.
ieee: C. J. Vorbach, R. Hasani, A. Amini, M. Lechner, and D. Rus, “Causal navigation
by continuous-time neural networks,” in 35th Conference on Neural Information
Processing Systems, Virtual, 2021.
ista: 'Vorbach CJ, Hasani R, Amini A, Lechner M, Rus D. 2021. Causal navigation
by continuous-time neural networks. 35th Conference on Neural Information Processing
Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information
Processing Systems, .'
mla: Vorbach, Charles J., et al. “Causal Navigation by Continuous-Time Neural Networks.”
35th Conference on Neural Information Processing Systems, Neural Information
Processing Systems Foundation, 2021.
short: C.J. Vorbach, R. Hasani, A. Amini, M. Lechner, D. Rus, in:, 35th Conference
on Neural Information Processing Systems, Neural Information Processing Systems
Foundation, 2021.
conference:
end_date: 2021-12-10
location: Virtual
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2021-12-06
das_tickbox: '1'
date_created: 2022-01-25T15:47:50Z
date_published: 2021-12-01T00:00:00Z
date_updated: 2026-07-07T06:49:46Z
day: '01'
ddc:
- '000'
department:
- _id: GradSch
- _id: ToHe
external_id:
arxiv:
- '2106.08314'
file:
- access_level: open_access
checksum: be81f0ade174a8c9b2d4fe09590b2021
content_type: application/pdf
creator: mlechner
date_created: 2022-01-26T07:37:24Z
date_updated: 2022-01-26T07:37:24Z
file_id: '10679'
file_name: NeurIPS-2021-causal-navigation-by-continuous-time-neural-networks-Paper.pdf
file_size: 6841228
relation: main_file
success: 1
file_date_updated: 2022-01-26T07:37:24Z
has_accepted_license: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://proceedings.neurips.cc/paper/2021/hash/67ba02d73c54f0b83c05507b7fb7267f-Abstract.html
month: '12'
oa: 1
oa_version: Published Version
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: 35th Conference on Neural Information Processing Systems
publication_identifier:
issn:
- 1049-5258
publication_status: published
publisher: Neural Information Processing Systems Foundation
quality_controlled: '1'
status: public
title: Causal navigation by continuous-time neural networks
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported (CC BY-NC-ND
3.0)
short: CC BY-NC-ND (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '9293'
abstract:
- lang: eng
text: 'We consider planning problems for graphs, Markov Decision Processes (MDPs),
and games on graphs in an explicit state space. While graphs represent the most
basic planning model, MDPs represent interaction with nature and games on graphs
represent interaction with an adversarial environment. We consider two planning
problems with k different target sets: (a) the coverage problem asks whether there
is a plan for each individual target set; and (b) the sequential target reachability
problem asks whether the targets can be reached in a given sequence. For the coverage
problem, we present a linear-time algorithm for graphs, and quadratic conditional
lower bound for MDPs and games on graphs. For the sequential target problem, we
present a linear-time algorithm for graphs, a sub-quadratic algorithm for MDPs,
and a quadratic conditional lower bound for games on graphs. Our results with
conditional lower bounds, based on the boolean matrix multiplication (BMM) conjecture
and strong exponential time hypothesis (SETH), establish (i) model-separation
results showing that for the coverage problem MDPs and games on graphs are harder
than graphs, and for the sequential reachability problem games on graphs are harder
than MDPs and graphs; and (ii) problem-separation results showing that for MDPs
the coverage problem is harder than the sequential target problem.'
article_number: '103499'
article_processing_charge: No
article_type: original
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: Wolfgang
full_name: Dvořák, Wolfgang
last_name: Dvořák
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Alexander
full_name: Svozil, Alexander
last_name: Svozil
citation:
ama: Chatterjee K, Dvořák W, Henzinger M, Svozil A. Algorithms and conditional lower
bounds for planning problems. Artificial Intelligence. 2021;297(8). doi:10.1016/j.artint.2021.103499
apa: Chatterjee, K., Dvořák, W., Henzinger, M., & Svozil, A. (2021). Algorithms
and conditional lower bounds for planning problems. Artificial Intelligence.
Elsevier. https://doi.org/10.1016/j.artint.2021.103499
chicago: Chatterjee, Krishnendu, Wolfgang Dvořák, Monika Henzinger, and Alexander
Svozil. “Algorithms and Conditional Lower Bounds for Planning Problems.” Artificial
Intelligence. Elsevier, 2021. https://doi.org/10.1016/j.artint.2021.103499.
ieee: K. Chatterjee, W. Dvořák, M. Henzinger, and A. Svozil, “Algorithms and conditional
lower bounds for planning problems,” Artificial Intelligence, vol. 297,
no. 8. Elsevier, 2021.
ista: Chatterjee K, Dvořák W, Henzinger M, Svozil A. 2021. Algorithms and conditional
lower bounds for planning problems. Artificial Intelligence. 297(8), 103499.
mla: Chatterjee, Krishnendu, et al. “Algorithms and Conditional Lower Bounds for
Planning Problems.” Artificial Intelligence, vol. 297, no. 8, 103499, Elsevier,
2021, doi:10.1016/j.artint.2021.103499.
short: K. Chatterjee, W. Dvořák, M. Henzinger, A. Svozil, Artificial Intelligence
297 (2021).
corr_author: '1'
date_created: 2021-03-28T22:01:40Z
date_published: 2021-03-16T00:00:00Z
date_updated: 2026-07-07T13:36:04Z
day: '16'
department:
- _id: KrCh
doi: 10.1016/j.artint.2021.103499
external_id:
arxiv:
- '1804.07031'
isi:
- '000657537500003'
intvolume: ' 297'
isi: 1
issue: '8'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1804.07031
month: '03'
oa: 1
oa_version: Preprint
publication: Artificial Intelligence
publication_identifier:
issn:
- 0004-3702
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '35'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Algorithms and conditional lower bounds for planning problems
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 297
year: '2021'
...
---
_id: '9441'
abstract:
- lang: eng
text: "Isomanifolds are the generalization of isosurfaces to arbitrary dimension
and codimension, i.e. submanifolds of ℝ^d defined as the zero set of some multivariate
multivalued smooth function f: ℝ^d → ℝ^{d-n}, where n is the intrinsic dimension
of the manifold. A natural way to approximate a smooth isomanifold M is to consider
its Piecewise-Linear (PL) approximation M̂ based on a triangulation \U0001D4AF
of the ambient space ℝ^d. In this paper, we describe a simple algorithm to trace
isomanifolds from a given starting point. The algorithm works for arbitrary dimensions
n and d, and any precision D. Our main result is that, when f (or M) has bounded
complexity, the complexity of the algorithm is polynomial in d and δ = 1/D (and
unavoidably exponential in n). Since it is known that for δ = Ω (d^{2.5}), M̂
is O(D²)-close and isotopic to M, our algorithm produces a faithful PL-approximation
of isomanifolds of bounded complexity in time polynomial in d. Combining this
algorithm with dimensionality reduction techniques, the dependency on d in the
size of M̂ can be completely removed with high probability. We also show that
the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds.
The algorithm for isomanifolds with boundary has been implemented and experimental
results are reported, showing that it is practical and can handle cases that are
far ahead of the state-of-the-art. "
acknowledgement: We thank Dominique Attali, Guilherme de Fonseca, Arijit Ghosh, Vincent
Pilaud and Aurélien Alvarez for their comments and suggestions. We also acknowledge
the reviewers.
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Jean-Daniel
full_name: Boissonnat, Jean-Daniel
last_name: Boissonnat
- first_name: Siargey
full_name: Kachanovich, Siargey
last_name: Kachanovich
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Boissonnat J-D, Kachanovich S, Wintraecken M. Tracing isomanifolds in Rd in
time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. In: 37th
International Symposium on Computational Geometry. Vol 189. Leibniz International
Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2021:17:1-17:16. doi:10.4230/LIPIcs.SoCG.2021.17'
apa: 'Boissonnat, J.-D., Kachanovich, S., & Wintraecken, M. (2021). Tracing
isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations.
In 37th International Symposium on Computational Geometry (Vol. 189, p.
17:1-17:16). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.SoCG.2021.17'
chicago: 'Boissonnat, Jean-Daniel, Siargey Kachanovich, and Mathijs Wintraecken.
“Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn
Triangulations.” In 37th International Symposium on Computational Geometry,
189:17:1-17:16. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl,
Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.SoCG.2021.17.'
ieee: J.-D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Tracing isomanifolds
in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations,”
in 37th International Symposium on Computational Geometry, Virtual, 2021,
vol. 189, p. 17:1-17:16.
ista: 'Boissonnat J-D, Kachanovich S, Wintraecken M. 2021. Tracing isomanifolds
in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. 37th
International Symposium on Computational Geometry. SoCG: Symposium on Computational
GeometryLeibniz International Proceedings in Informatics (LIPIcs), LIPIcs, vol.
189, 17:1-17:16.'
mla: Boissonnat, Jean-Daniel, et al. “Tracing Isomanifolds in Rd in Time Polynomial
in d Using Coxeter-Freudenthal-Kuhn Triangulations.” 37th International Symposium
on Computational Geometry, vol. 189, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2021, p. 17:1-17:16, doi:10.4230/LIPIcs.SoCG.2021.17.
short: J.-D. Boissonnat, S. Kachanovich, M. Wintraecken, in:, 37th International
Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
Dagstuhl, Germany, 2021, p. 17:1-17:16.
conference:
end_date: 2021-06-11
location: Virtual
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2021-06-07
das_tickbox: '1'
date_created: 2021-06-02T10:10:55Z
date_published: 2021-06-02T00:00:00Z
date_updated: 2026-07-07T13:43:40Z
day: '02'
ddc:
- '005'
- '516'
- '514'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2021.17
ec_funded: 1
file:
- access_level: open_access
checksum: c322aa48d5d35a35877896cc565705b6
content_type: application/pdf
creator: mwintrae
date_created: 2021-06-02T10:22:33Z
date_updated: 2021-06-02T10:22:33Z
file_id: '9442'
file_name: LIPIcs-SoCG-2021-17.pdf
file_size: 1972902
relation: main_file
success: 1
file_date_updated: 2021-06-02T10:22:33Z
has_accepted_license: '1'
intvolume: ' 189'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 17:1-17:16
place: Dagstuhl, Germany
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 37th International Symposium on Computational Geometry
publication_identifier:
isbn:
- 978-3-95977-184-9
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '12960'
relation: later_version
status: public
scopus_import: '1'
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn
triangulations
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 189
year: '2021'
...
---
_id: '9345'
abstract:
- lang: eng
text: Modeling a crystal as a periodic point set, we present a fingerprint consisting
of density functionsthat facilitates the efficient search for new materials and
material properties. We prove invarianceunder isometries, continuity, and completeness
in the generic case, which are necessary featuresfor the reliable comparison of
crystals. The proof of continuity integrates methods from discretegeometry and
lattice theory, while the proof of generic completeness combines techniques fromgeometry
with analysis. The fingerprint has a fast algorithm based on Brillouin zones and
relatedinclusion-exclusion formulae. We have implemented the algorithm and describe
its application tocrystal structure prediction.
acknowledgement: The authors thank Janos Pach for insightful discussions on the topic
of thispaper, Morteza Saghafian for finding the one-dimensional counterexample mentioned
in Section 5,and Larry Andrews for generously sharing his crystallographic perspective.
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Teresa
full_name: Heiss, Teresa
id: 4879BB4E-F248-11E8-B48F-1D18A9856A87
last_name: Heiss
orcid: 0000-0002-1780-2689
- first_name: Vitaliy
full_name: ' Kurlin , Vitaliy'
last_name: ' Kurlin '
- first_name: Philip
full_name: Smith, Philip
last_name: Smith
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Edelsbrunner H, Heiss T, Kurlin V, Smith P, Wintraecken M. The density fingerprint
of a periodic point set. In: 37th International Symposium on Computational
Geometry. Vol 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021:32:1-32:16.
doi:10.4230/LIPIcs.SoCG.2021.32'
apa: 'Edelsbrunner, H., Heiss, T., Kurlin , V., Smith, P., & Wintraecken, M.
(2021). The density fingerprint of a periodic point set. In 37th International
Symposium on Computational Geometry (Vol. 189, p. 32:1-32:16). Virtual: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2021.32'
chicago: Edelsbrunner, Herbert, Teresa Heiss, Vitaliy Kurlin , Philip Smith, and
Mathijs Wintraecken. “The Density Fingerprint of a Periodic Point Set.” In 37th
International Symposium on Computational Geometry, 189:32:1-32:16. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.SoCG.2021.32.
ieee: H. Edelsbrunner, T. Heiss, V. Kurlin , P. Smith, and M. Wintraecken, “The
density fingerprint of a periodic point set,” in 37th International Symposium
on Computational Geometry, Virtual, 2021, vol. 189, p. 32:1-32:16.
ista: 'Edelsbrunner H, Heiss T, Kurlin V, Smith P, Wintraecken M. 2021. The density
fingerprint of a periodic point set. 37th International Symposium on Computational
Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 189, 32:1-32:16.'
mla: Edelsbrunner, Herbert, et al. “The Density Fingerprint of a Periodic Point
Set.” 37th International Symposium on Computational Geometry, vol. 189,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 32:1-32:16, doi:10.4230/LIPIcs.SoCG.2021.32.
short: H. Edelsbrunner, T. Heiss, V. Kurlin , P. Smith, M. Wintraecken, in:, 37th
International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2021, p. 32:1-32:16.
conference:
end_date: 2021-06-11
location: Virtual
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2021-06-07
das_tickbox: '1'
date_created: 2021-04-22T08:09:58Z
date_published: 2021-06-02T00:00:00Z
date_updated: 2026-07-07T13:43:27Z
day: '02'
ddc:
- '004'
- '516'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2021.32
ec_funded: 1
file:
- access_level: open_access
checksum: 1787baef1523d6d93753b90d0c109a6d
content_type: application/pdf
creator: mwintrae
date_created: 2021-04-22T08:08:14Z
date_updated: 2021-04-22T08:08:14Z
file_id: '9346'
file_name: df_socg_final_version.pdf
file_size: 3117435
relation: main_file
success: 1
file_date_updated: 2021-04-22T08:08:14Z
has_accepted_license: '1'
intvolume: ' 189'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 32:1-32:16
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 0aa4bc98-070f-11eb-9043-e6fff9c6a316
grant_number: I4887
name: Persistent Homology, Algorithms and Stochastic Geometry
- _id: 25C5A090-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00312
name: Synaptic communication in neuronal microcircuits
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 37th International Symposium on Computational Geometry
publication_identifier:
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '18667'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: The density fingerprint of a periodic point set
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 189
year: '2021'
...
---
_id: '10041'
abstract:
- lang: eng
text: Yao’s garbling scheme is one of the most fundamental cryptographic constructions.
Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security
in the selective setting where the adversary chooses the challenge inputs before
seeing the garbled circuit assuming secure symmetric-key encryption (and hence
one-way functions). This was followed by results, both positive and negative,
concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto
2013) showed that it cannot satisfy adaptive security as is, due to a simple incompressibility
argument. Jafargholi and Wichs (TCC 2017) considered a natural adaptation of Yao’s
scheme (where the output mapping is sent in the online phase, together with the
garbled input) that circumvents this negative result, and proved that it is adaptively
secure, at least for shallow circuits. In particular, they showed that for the
class of circuits of depth δ , the loss in security is at most exponential in δ
. The above results all concern the simulation-based notion of security. In this
work, we show that the upper bound of Jafargholi and Wichs is basically optimal
in a strong sense. As our main result, we show that there exists a family of Boolean
circuits, one for each depth δ∈N , such that any black-box reduction proving
the adaptive indistinguishability of the natural adaptation of Yao’s scheme from
any symmetric-key encryption has to lose a factor that is exponential in δ√
. Since indistinguishability is a weaker notion than simulation, our bound also
applies to adaptive simulation. To establish our results, we build on the recent
approach of Kamath et al. (Eprint 2021), which uses pebbling lower bounds in conjunction
with oracle separations to prove fine-grained lower bounds on loss in cryptographic
security.
acknowledgement: We would like to thank the anonymous reviewers of Crypto’21 whose
detailed comments helped us considerably improve the presentation of the paper.
alternative_title:
- LCNS
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
orcid: 0009-0006-6812-7317
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- 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: Daniel
full_name: Wichs, Daniel
last_name: Wichs
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. Limits on the Adaptive Security
of Yao’s Garbling. In: 41st Annual International Cryptology Conference.
Vol 12826. Cham: Springer Nature; 2021:486-515. doi:10.1007/978-3-030-84245-1_17'
apa: 'Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Wichs, D. (2021). Limits
on the Adaptive Security of Yao’s Garbling. In 41st Annual International Cryptology
Conference (Vol. 12826, pp. 486–515). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-84245-1_17'
chicago: 'Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Daniel
Wichs. “Limits on the Adaptive Security of Yao’s Garbling.” In 41st Annual
International Cryptology Conference, 12826:486–515. Cham: Springer Nature,
2021. https://doi.org/10.1007/978-3-030-84245-1_17.'
ieee: C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and D. Wichs, “Limits on the
Adaptive Security of Yao’s Garbling,” in 41st Annual International Cryptology
Conference, Virtual, 2021, vol. 12826, pp. 486–515.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. 2021. Limits on the Adaptive
Security of Yao’s Garbling. 41st Annual International Cryptology Conference. CRYPTO:
Annual International Cryptology Conference, LCNS, vol. 12826, 486–515.'
mla: Kamath Hosdurg, Chethan, et al. “Limits on the Adaptive Security of Yao’s Garbling.”
41st Annual International Cryptology Conference, vol. 12826, Springer Nature,
2021, pp. 486–515, doi:10.1007/978-3-030-84245-1_17.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, D. Wichs, in:, 41st Annual International
Cryptology Conference, Springer Nature, Cham, 2021, pp. 486–515.
conference:
end_date: 2021-08-20
location: Virtual
name: 'CRYPTO: Annual International Cryptology Conference'
start_date: 2021-08-16
cryptoeprintid: 1
date_created: 2021-09-23T14:06:15Z
date_published: 2021-08-11T00:00:00Z
date_updated: 2026-07-07T13:57:01Z
day: '11'
department:
- _id: KrPi
doi: 10.1007/978-3-030-84245-1_17
ec_funded: 1
external_id:
cryptoeprintid:
- 2021/945
isi:
- '000696697800017'
intvolume: ' 12826'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/945
month: '08'
oa: 1
oa_version: Preprint
page: 486-515
place: Cham
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 41st Annual International Cryptology Conference
publication_identifier:
eisbn:
- 978-3-030-84245-1
eissn:
- 1611-3349
isbn:
- 978-3-030-84244-4
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '10035'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Limits on the Adaptive Security of Yao’s Garbling
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12826
year: '2021'
...
---
OA_place: publisher
_id: '10035'
abstract:
- lang: eng
text: 'Many security definitions come in two flavors: a stronger “adaptive” flavor,
where the adversary can arbitrarily make various choices during the course of
the attack, and a weaker “selective” flavor where the adversary must commit to
some or all of their choices a-priori. For example, in the context of identity-based
encryption, selective security requires the adversary to decide on the identity
of the attacked party at the very beginning of the game whereas adaptive security
allows the attacker to first see the master public key and some secret keys before
making this choice. Often, it appears to be much easier to achieve selective security
than it is to achieve adaptive security. A series of several recent works shows
how to cleverly achieve adaptive security in several such scenarios including
generalized selective decryption [Pan07][FJP15], constrained PRFs [FKPR14], and
Yao’s garbled circuits [JW16]. Although the above works expressed vague intuition
that they share a common technique, the connection was never made precise. In
this work we present a new framework (published at Crypto ’17 [JKK+17a]) that
connects all of these works and allows us to present them in a unified and simplified
fashion. Having the framework in place, we show how to achieve adaptive security
for proxy re-encryption schemes (published at PKC ’19 [FKKP19]) and provide the
first adaptive security proofs for continuous group key agreement protocols (published
at S&P ’21 [KPW+21]). Questioning optimality of our framework, we then show that
currently used proof techniques cannot lead to significantly better security guarantees
for "graph-building" games (published at TCC ’21 [KKPW21a]). These games cover
generalized selective decryption, as well as the security of prominent constructions
for constrained PRFs, continuous group key agreement, and proxy re-encryption.
Finally, we revisit the adaptive security of Yao’s garbled circuits and extend
the analysis of Jafargholi and Wichs in two directions: While they prove adaptive
security only for a modified construction with increased online complexity, we
provide the first positive results for the original construction by Yao (published
at TCC ’21 [KKP21a]). On the negative side, we prove that the results of Jafargholi
and Wichs are essentially optimal by showing that no black-box reduction can provide
a significantly better security bound (published at Crypto ’21 [KKPW21c]).'
acknowledgement: "I want to acknowledge the funding by the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(682815 - TOCNeT).\r\n"
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
citation:
ama: Klein K. On the adaptive security of graph-based games. 2021. doi:10.15479/at:ista:10035
apa: Klein, K. (2021). On the adaptive security of graph-based games. Institute
of Science and Technology Austria. https://doi.org/10.15479/at:ista:10035
chicago: Klein, Karen. “On the Adaptive Security of Graph-Based Games.” Institute
of Science and Technology Austria, 2021. https://doi.org/10.15479/at:ista:10035.
ieee: K. Klein, “On the adaptive security of graph-based games,” Institute of Science
and Technology Austria, 2021.
ista: Klein K. 2021. On the adaptive security of graph-based games. Institute of
Science and Technology Austria.
mla: Klein, Karen. On the Adaptive Security of Graph-Based Games. Institute
of Science and Technology Austria, 2021, doi:10.15479/at:ista:10035.
short: K. Klein, On the Adaptive Security of Graph-Based Games, Institute of Science
and Technology Austria, 2021.
corr_author: '1'
date_created: 2021-09-23T07:31:44Z
date_published: 2021-09-23T00:00:00Z
date_updated: 2026-07-07T13:57:00Z
day: '23'
ddc:
- '519'
degree_awarded: PhD
department:
- _id: GradSch
- _id: KrPi
doi: 10.15479/at:ista:10035
ec_funded: 1
file:
- access_level: open_access
checksum: 73a44345c683e81f3e765efbf86fdcc5
content_type: application/pdf
creator: cchlebak
date_created: 2021-10-04T12:22:33Z
date_updated: 2021-10-04T12:22:33Z
file_id: '10082'
file_name: thesis_pdfa.pdf
file_size: 2104726
relation: main_file
success: 1
- access_level: closed
checksum: 7b80df30a0e686c3ef6a56d4e1c59e29
content_type: application/x-zip-compressed
creator: cchlebak
date_created: 2021-10-05T07:04:37Z
date_updated: 2022-03-10T12:15:18Z
file_id: '10085'
file_name: thesis_final (1).zip
file_size: 9538359
relation: source_file
file_date_updated: 2022-03-10T12:15:18Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: '276'
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '10049'
relation: part_of_dissertation
status: public
- id: '637'
relation: part_of_dissertation
status: public
- id: '6430'
relation: part_of_dissertation
status: public
- id: '10044'
relation: part_of_dissertation
status: public
- id: '10048'
relation: part_of_dissertation
status: public
- id: '10041'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
title: On the adaptive security of graph-based games
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: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2021'
...
---
_id: '11453'
abstract:
- lang: eng
text: "Neuronal computations depend on synaptic connectivity and intrinsic electrophysiological
properties. Synaptic connectivity determines which inputs from presynaptic neurons
are integrated, while cellular properties determine how inputs are filtered over
time. Unlike their biological counterparts, most computational approaches to learning
in simulated neural networks are limited to changes in synaptic connectivity.
However, if intrinsic parameters change, neural computations are altered drastically.
Here, we include the parameters that determine the intrinsic properties,\r\ne.g.,
time constants and reset potential, into the learning paradigm. Using sparse feedback
signals that indicate target spike times, and gradient-based parameter updates,
we show that the intrinsic parameters can be learned along with the synaptic weights
to produce specific input-output functions. Specifically, we use a teacher-student
paradigm in which a randomly initialised leaky integrate-and-fire or resonate-and-fire
neuron must recover the parameters of a teacher neuron. We show that complex temporal
functions can be learned online and without backpropagation through time, relying
on event-based updates only. Our results are a step towards online learning of
neural computations from ungraded and unsigned sparse feedback signals with a
biologically inspired learning mechanism."
acknowledgement: We would like to thank Professor Dr. Henning Sprekeler for his valuable
suggestions and Dr. Andrew Saxe, Milan Klöwer and Anna Wallis for their constructive
feedback on the manuscript. Lukas Braun was supported by the Network of European
Neuroscience Schools through their NENS Exchange Grant program, by the European
Union through their European Community Action Scheme for the Mobility of University
Students, the Woodward Scholarship awarded by Wadham College, Oxford and the Medical
Research Council [MR/N013468/1]. Tim P. Vogels was supported by a Wellcome Trust
Senior Research Fellowship [214316/Z/18/Z].
alternative_title:
- Advances in Neural Information Processing Systems
article_processing_charge: No
author:
- first_name: Lukas
full_name: Braun, Lukas
last_name: Braun
- first_name: Tim P
full_name: Vogels, Tim P
id: CB6FF8D2-008F-11EA-8E08-2637E6697425
last_name: Vogels
orcid: 0000-0003-3295-6181
citation:
ama: 'Braun L, Vogels TP. Online learning of neural computations from sparse temporal
feedback. In: 35th Conference on Neural Information Processing Systems.
Vol 20. Neural Information Processing Systems Foundation; 2021:16437-16450.'
apa: 'Braun, L., & Vogels, T. P. (2021). Online learning of neural computations
from sparse temporal feedback. In 35th Conference on Neural Information Processing
Systems (Vol. 20, pp. 16437–16450). Virtual, Online: Neural Information Processing
Systems Foundation.'
chicago: Braun, Lukas, and Tim P Vogels. “Online Learning of Neural Computations
from Sparse Temporal Feedback.” In 35th Conference on Neural Information Processing
Systems, 20:16437–50. Neural Information Processing Systems Foundation, 2021.
ieee: L. Braun and T. P. Vogels, “Online learning of neural computations from sparse
temporal feedback,” in 35th Conference on Neural Information Processing Systems,
Virtual, Online, 2021, vol. 20, pp. 16437–16450.
ista: 'Braun L, Vogels TP. 2021. Online learning of neural computations from sparse
temporal feedback. 35th Conference on Neural Information Processing Systems. NeurIPS:
Neural Information Processing Systems, Advances in Neural Information Processing
Systems, vol. 20, 16437–16450.'
mla: Braun, Lukas, and Tim P. Vogels. “Online Learning of Neural Computations from
Sparse Temporal Feedback.” 35th Conference on Neural Information Processing
Systems, vol. 20, Neural Information Processing Systems Foundation, 2021,
pp. 16437–50.
short: L. Braun, T.P. Vogels, in:, 35th Conference on Neural Information Processing
Systems, Neural Information Processing Systems Foundation, 2021, pp. 16437–16450.
conference:
end_date: 2021-12-14
location: Virtual, Online
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2021-12-06
corr_author: '1'
das_tickbox: '1'
date_created: 2022-06-19T22:01:59Z
date_published: 2021-12-01T00:00:00Z
date_updated: 2026-07-08T05:45:00Z
day: '01'
ddc:
- '000'
- '570'
department:
- _id: TiVo
intvolume: ' 20'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://proceedings.neurips.cc/paper/2021/file/88e1ce84f9feef5a08d0df0334c53468-Paper.pdf
month: '12'
oa: 1
oa_version: Published Version
page: 16437-16450
project:
- _id: c084a126-5a5b-11eb-8a69-d75314a70a87
grant_number: 214316/Z/18/Z
name: "Whatâ\x80\x99s in a memory? Spatiotemporal dynamics in strongly coupled recurrent
neuronal networks."
publication: 35th Conference on Neural Information Processing Systems
publication_identifier:
isbn:
- '9781713845393'
issn:
- 1049-5258
publication_status: published
publisher: Neural Information Processing Systems Foundation
quality_controlled: '1'
scopus_import: '1'
status: public
title: Online learning of neural computations from sparse temporal feedback
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 20
year: '2021'
...
---
_id: '11452'
abstract:
- lang: eng
text: We study efficient distributed algorithms for the fundamental problem of principal
component analysis and leading eigenvector computation on the sphere, when the
data are randomly distributed among a set of computational nodes. We propose a
new quantized variant of Riemannian gradient descent to solve this problem, and
prove that the algorithm converges with high probability under a set of necessary
spherical-convexity properties. We give bounds on the number of bits transmitted
by the algorithm under common initialization schemes, and investigate the dependency
on the problem dimension in each case.
acknowledgement: We would like to thank the anonymous reviewers for helpful comments
and suggestions. We also thank Aurelien Lucchi and Antonio Orvieto for fruitful
discussions at an early stage of this work. FA is partially supported by the SNSF
under research project No. 192363 and conducted part of this work while at IST Austria
under the European Union’s Horizon 2020 research and innovation programme (grant
agreement No. 805223 ScaleML). PD partly conducted this work while at IST Austria
and was supported by the European Union’s Horizon 2020 programme under the Marie
Skłodowska-Curie grant agreement No. 754411.
alternative_title:
- Advances in Neural Information Processing Systems
article_processing_charge: No
arxiv: 1
author:
- first_name: Foivos
full_name: Alimisis, Foivos
last_name: Alimisis
- first_name: Peter
full_name: Davies, Peter
id: 11396234-BB50-11E9-B24C-90FCE5697425
last_name: Davies
orcid: 0000-0002-5646-9524
- first_name: Bart
full_name: Vandereycken, Bart
last_name: Vandereycken
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Alimisis F, Davies P, Vandereycken B, Alistarh D-A. Distributed principal
component analysis with limited communication. In: 35th Conference on Neural
Information Processing Systems. Vol 4. Neural Information Processing Systems
Foundation; 2021:2823-2834.'
apa: 'Alimisis, F., Davies, P., Vandereycken, B., & Alistarh, D.-A. (2021).
Distributed principal component analysis with limited communication. In 35th
Conference on Neural Information Processing Systems (Vol. 4, pp. 2823–2834).
Virtual, Online: Neural Information Processing Systems Foundation.'
chicago: Alimisis, Foivos, Peter Davies, Bart Vandereycken, and Dan-Adrian Alistarh.
“Distributed Principal Component Analysis with Limited Communication.” In 35th
Conference on Neural Information Processing Systems, 4:2823–34. Neural Information
Processing Systems Foundation, 2021.
ieee: F. Alimisis, P. Davies, B. Vandereycken, and D.-A. Alistarh, “Distributed
principal component analysis with limited communication,” in 35th Conference
on Neural Information Processing Systems, Virtual, Online, 2021, vol. 4, pp.
2823–2834.
ista: 'Alimisis F, Davies P, Vandereycken B, Alistarh D-A. 2021. Distributed principal
component analysis with limited communication. 35th Conference on Neural Information
Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in
Neural Information Processing Systems, vol. 4, 2823–2834.'
mla: Alimisis, Foivos, et al. “Distributed Principal Component Analysis with Limited
Communication.” 35th Conference on Neural Information Processing Systems,
vol. 4, Neural Information Processing Systems Foundation, 2021, pp. 2823–34.
short: F. Alimisis, P. Davies, B. Vandereycken, D.-A. Alistarh, in:, 35th Conference
on Neural Information Processing Systems, Neural Information Processing Systems
Foundation, 2021, pp. 2823–2834.
conference:
end_date: 2021-12-14
location: Virtual, Online
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2021-12-06
corr_author: '1'
das_tickbox: '1'
date_created: 2022-06-19T22:01:58Z
date_published: 2021-12-01T00:00:00Z
date_updated: 2026-07-08T05:44:33Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
ec_funded: 1
external_id:
arxiv:
- '2110.14391'
intvolume: ' 4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://proceedings.neurips.cc/paper/2021/file/1680e9fa7b4dd5d62ece800239bb53bd-Paper.pdf
month: '12'
oa: 1
oa_version: Published Version
page: 2823-2834
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 35th Conference on Neural Information Processing Systems
publication_identifier:
isbn:
- '9781713845393'
issn:
- 1049-5258
publication_status: published
publisher: Neural Information Processing Systems Foundation
quality_controlled: '1'
scopus_import: '1'
status: public
title: Distributed principal component analysis with limited communication
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2021'
...
---
OA_place: repository
OA_type: green
_id: '22156'
abstract:
- lang: eng
text: Extending a recent breakthrough of Shitov, we prove that the chromatic number
of the tensor product of two graphs can be a constant factor smaller than the
minimum chromatic number of the two graphs. More precisely, we prove that there
exists an absolute constant δ>0 such that for all c sufficiently large, there
exist graphs G and H with chromatic number at least (1+δ)c for which χ(G×H)≤c.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Xiaoyu
full_name: He, Xiaoyu
last_name: He
- first_name: Yuval
full_name: Wigderson, Yuval
id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
last_name: Wigderson
citation:
ama: He X, Wigderson Y. Hedetniemi’s conjecture is asymptotically false. Journal
of Combinatorial Theory, Series B. 2021;146:485-494. doi:10.1016/j.jctb.2020.03.003
apa: He, X., & Wigderson, Y. (2021). Hedetniemi’s conjecture is asymptotically
false. Journal of Combinatorial Theory, Series B. Elsevier. https://doi.org/10.1016/j.jctb.2020.03.003
chicago: He, Xiaoyu, and Yuval Wigderson. “Hedetniemi’s Conjecture Is Asymptotically
False.” Journal of Combinatorial Theory, Series B. Elsevier, 2021. https://doi.org/10.1016/j.jctb.2020.03.003.
ieee: X. He and Y. Wigderson, “Hedetniemi’s conjecture is asymptotically false,”
Journal of Combinatorial Theory, Series B, vol. 146. Elsevier, pp. 485–494,
2021.
ista: He X, Wigderson Y. 2021. Hedetniemi’s conjecture is asymptotically false.
Journal of Combinatorial Theory, Series B. 146, 485–494.
mla: He, Xiaoyu, and Yuval Wigderson. “Hedetniemi’s Conjecture Is Asymptotically
False.” Journal of Combinatorial Theory, Series B, vol. 146, Elsevier,
2021, pp. 485–94, doi:10.1016/j.jctb.2020.03.003.
short: X. He, Y. Wigderson, Journal of Combinatorial Theory, Series B 146 (2021)
485–494.
date_created: 2026-06-29T10:50:09Z
date_published: 2021-01-01T00:00:00Z
date_updated: 2026-07-08T07:43:57Z
day: '01'
doi: 10.1016/j.jctb.2020.03.003
extern: '1'
external_id:
arxiv:
- '1906.06783'
intvolume: ' 146'
keyword:
- Graph coloring
- Hedetniemi's conjecture
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1906.06783
month: '01'
oa: 1
oa_version: Preprint
page: 485-494
publication: Journal of Combinatorial Theory, Series B
publication_identifier:
issn:
- 0095-8956
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Hedetniemi's conjecture is asymptotically false
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 146
year: '2021'
...