---
_id: '12432'
abstract:
- lang: eng
text: "We present CertifyHAM, a deterministic algorithm that takes a graph G as
input and either finds a Hamilton cycle of G or outputs that such a cycle does
not exist. If G ∼ G(n, p) and p ≥\r\n100 log n/n then the expected running time
of CertifyHAM is O(n/p) which is best possible. This improves upon previous results
due to Gurevich and Shelah, Thomason and Alon, and\r\nKrivelevich, who proved
analogous results for p being constant, p ≥ 12n −1/3 and p ≥ 70n\r\n−1/2 respectively."
acknowledgement: "This project has received funding from the European Union’s Horizon
2020\r\nresearch and innovation programme under the Marie Skłodowska-Curie grant\r\nagreement
No 101034413"
article_processing_charge: No
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
citation:
ama: 'Anastos M. Solving the Hamilton cycle problem fast on average. In: 63rd
Annual IEEE Symposium on Foundations of Computer Science. Vol 2022-October.
Institute of Electrical and Electronics Engineers; 2022:919-930. doi:10.1109/FOCS54457.2022.00091'
apa: 'Anastos, M. (2022). Solving the Hamilton cycle problem fast on average. In
63rd Annual IEEE Symposium on Foundations of Computer Science (Vol. 2022–October,
pp. 919–930). Denver, CO, United States: Institute of Electrical and Electronics
Engineers. https://doi.org/10.1109/FOCS54457.2022.00091'
chicago: Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.”
In 63rd Annual IEEE Symposium on Foundations of Computer Science, 2022–October:919–30.
Institute of Electrical and Electronics Engineers, 2022. https://doi.org/10.1109/FOCS54457.2022.00091.
ieee: M. Anastos, “Solving the Hamilton cycle problem fast on average,” in 63rd
Annual IEEE Symposium on Foundations of Computer Science, Denver, CO, United
States, 2022, vol. 2022–October, pp. 919–930.
ista: 'Anastos M. 2022. Solving the Hamilton cycle problem fast on average. 63rd
Annual IEEE Symposium on Foundations of Computer Science. FOCS: Foundations of
Computer Science vol. 2022–October, 919–930.'
mla: Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.” 63rd
Annual IEEE Symposium on Foundations of Computer Science, vol. 2022–October,
Institute of Electrical and Electronics Engineers, 2022, pp. 919–30, doi:10.1109/FOCS54457.2022.00091.
short: M. Anastos, in:, 63rd Annual IEEE Symposium on Foundations of Computer Science,
Institute of Electrical and Electronics Engineers, 2022, pp. 919–930.
conference:
end_date: 2022-11-03
location: Denver, CO, United States
name: 'FOCS: Foundations of Computer Science'
start_date: 2022-10-31
corr_author: '1'
date_created: 2023-01-29T23:00:59Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2025-07-10T11:50:26Z
day: '01'
department:
- _id: MaKw
doi: 10.1109/FOCS54457.2022.00091
ec_funded: 1
external_id:
isi:
- '000909382900084'
isi: 1
language:
- iso: eng
month: '12'
oa_version: None
page: 919-930
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: 63rd Annual IEEE Symposium on Foundations of Computer Science
publication_identifier:
isbn:
- '9781665455190'
issn:
- 0272-5428
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Solving the Hamilton cycle problem fast on average
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2022-October
year: '2022'
...
---
_id: '12452'
abstract:
- lang: eng
text: Portrait viewpoint and illumination editing is an important problem with several
applications in VR/AR, movies, and photography. Comprehensive knowledge of geometry
and illumination is critical for obtaining photorealistic results. Current methods
are unable to explicitly model in 3D while handing both viewpoint and illumination
editing from a single image. In this paper, we propose VoRF, a novel approach
that can take even a single portrait image as input and relight human heads under
novel illuminations that can be viewed from arbitrary viewpoints. VoRF represents
a human head as a continuous volumetric field and learns a prior model of human
heads using a coordinate-based MLP with separate latent spaces for identity and
illumination. The prior model is learnt in an auto-decoder manner over a diverse
class of head shapes and appearances, allowing VoRF to generalize to novel test
identities from a single input image. Additionally, VoRF has a reflectance MLP
that uses the intermediate features of the prior model for rendering One-Light-at-A-Time
(OLAT) images under novel views. We synthesize novel illuminations by combining
these OLAT images with target environment maps. Qualitative and quantitative evaluations
demonstrate the effectiveness of VoRF for relighting and novel view synthesis
even when applied to unseen subjects under uncontrolled illuminations.
acknowledgement: This work was supported by the ERC Consolidator Grant 4DReply (770784).
article_number: '708'
article_processing_charge: No
author:
- first_name: Pramod
full_name: Rao, Pramod
last_name: Rao
- first_name: Mallikarjun
full_name: B R, Mallikarjun
last_name: B R
- first_name: Gereon
full_name: Fox, Gereon
last_name: Fox
- first_name: Tim
full_name: Weyrich, Tim
last_name: Weyrich
- first_name: Bernd
full_name: Bickel, Bernd
id: 49876194-F248-11E8-B48F-1D18A9856A87
last_name: Bickel
orcid: 0000-0001-6511-9385
- first_name: Hans-Peter
full_name: Seidel, Hans-Peter
last_name: Seidel
- first_name: Hanspeter
full_name: Pfister, Hanspeter
last_name: Pfister
- first_name: Wojciech
full_name: Matusik, Wojciech
last_name: Matusik
- first_name: Ayush
full_name: Tewari, Ayush
last_name: Tewari
- first_name: Christian
full_name: Theobalt, Christian
last_name: Theobalt
- first_name: Mohamed
full_name: Elgharib, Mohamed
last_name: Elgharib
citation:
ama: 'Rao P, B R M, Fox G, et al. VoRF: Volumetric Relightable Faces. In: 33rd
British Machine Vision Conference. British Machine Vision Association and
Society for Pattern Recognition; 2022.'
apa: 'Rao, P., B R, M., Fox, G., Weyrich, T., Bickel, B., Seidel, H.-P., … Elgharib,
M. (2022). VoRF: Volumetric Relightable Faces. In 33rd British Machine Vision
Conference. London, United Kingdom: British Machine Vision Association and
Society for Pattern Recognition.'
chicago: 'Rao, Pramod, Mallikarjun B R, Gereon Fox, Tim Weyrich, Bernd Bickel, Hans-Peter
Seidel, Hanspeter Pfister, et al. “VoRF: Volumetric Relightable Faces.” In 33rd
British Machine Vision Conference. British Machine Vision Association and
Society for Pattern Recognition, 2022.'
ieee: 'P. Rao et al., “VoRF: Volumetric Relightable Faces,” in 33rd British
Machine Vision Conference, London, United Kingdom, 2022.'
ista: 'Rao P, B R M, Fox G, Weyrich T, Bickel B, Seidel H-P, Pfister H, Matusik
W, Tewari A, Theobalt C, Elgharib M. 2022. VoRF: Volumetric Relightable Faces.
33rd British Machine Vision Conference. BMVC: British Machine Vision Conference,
708.'
mla: 'Rao, Pramod, et al. “VoRF: Volumetric Relightable Faces.” 33rd British
Machine Vision Conference, 708, British Machine Vision Association and Society
for Pattern Recognition, 2022.'
short: P. Rao, M. B R, G. Fox, T. Weyrich, B. Bickel, H.-P. Seidel, H. Pfister,
W. Matusik, A. Tewari, C. Theobalt, M. Elgharib, in:, 33rd British Machine Vision
Conference, British Machine Vision Association and Society for Pattern Recognition,
2022.
conference:
end_date: 2022-11-24
location: London, United Kingdom
name: 'BMVC: British Machine Vision Conference'
start_date: 2022-11-21
date_created: 2023-01-30T10:47:06Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2023-10-31T08:40:55Z
day: '01'
ddc:
- '000'
department:
- _id: BeBi
file:
- access_level: open_access
checksum: b60b70bb48700aee709c85a69231821d
content_type: application/pdf
creator: bbickel
date_created: 2023-01-30T10:48:18Z
date_updated: 2023-01-30T10:48:18Z
file_id: '12453'
file_name: vorf_main.pdf
file_size: 5202710
relation: main_file
title: 'VoRF: Volumetric Relightable Faces'
- access_level: open_access
checksum: ce5f4ce66eaaa1590ee5df989fca6f61
content_type: application/pdf
creator: bbickel
date_created: 2023-01-30T10:48:29Z
date_updated: 2023-01-30T10:48:29Z
file_id: '12454'
file_name: vorf_supp.pdf
file_size: 37953188
relation: supplementary_material
title: 'VoRF: Volumetric Relightable Faces – SUPPLEMENTAL MATERIAL –'
- access_level: open_access
checksum: 08aecca434b08fee75ee1efe87943718
content_type: video/mp4
creator: bbickel
date_created: 2023-01-30T10:48:37Z
date_updated: 2023-01-30T10:48:37Z
file_id: '12455'
file_name: video.mp4
file_size: 57855492
relation: supplementary_material
file_date_updated: 2023-01-30T10:48:37Z
has_accepted_license: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://bmvc2022.mpi-inf.mpg.de/708/
month: '12'
oa: 1
oa_version: Published Version
publication: 33rd British Machine Vision Conference
publication_status: published
publisher: British Machine Vision Association and Society for Pattern Recognition
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'VoRF: Volumetric Relightable Faces'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...
---
_id: '12480'
abstract:
- lang: eng
text: 'We consider the problem of estimating a signal from measurements obtained
via a generalized linear model. We focus on estimators based on approximate message
passing (AMP), a family of iterative algorithms with many appealing features:
the performance of AMP in the high-dimensional limit can be succinctly characterized
under suitable model assumptions; AMP can also be tailored to the empirical distribution
of the signal entries, and for a wide class of estimation problems, AMP is conjectured
to be optimal among all polynomial-time algorithms. However, a major issue of
AMP is that in many models (such as phase retrieval), it requires an initialization
correlated with the ground-truth signal and independent from the measurement matrix.
Assuming that such an initialization is available is typically not realistic.
In this paper, we solve this problem by proposing an AMP algorithm initialized
with a spectral estimator. With such an initialization, the standard AMP analysis
fails since the spectral estimator depends in a complicated way on the design
matrix. Our main contribution is a rigorous characterization of the performance
of AMP with spectral initialization in the high-dimensional limit. The key technical
idea is to define and analyze a two-phase artificial AMP algorithm that first
produces the spectral estimator, and then closely approximates the iterates of
the true AMP. We also provide numerical results that demonstrate the validity
of the proposed approach.'
acknowledgement: "The authors would like to thank Andrea Montanari for helpful discussions.\r\nM
Mondelli was partially supported by the 2019 Lopez-Loreta Prize. R Venkataramanan
was partially supported by the Alan Turing Institute under the EPSRC Grant\r\nEP/N510129/1."
article_number: '114003'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Ramji
full_name: Venkataramanan, Ramji
last_name: Venkataramanan
citation:
ama: 'Mondelli M, Venkataramanan R. Approximate message passing with spectral initialization
for generalized linear models. Journal of Statistical Mechanics: Theory and
Experiment. 2022;2022(11). doi:10.1088/1742-5468/ac9828'
apa: 'Mondelli, M., & Venkataramanan, R. (2022). Approximate message passing
with spectral initialization for generalized linear models. Journal of Statistical
Mechanics: Theory and Experiment. IOP Publishing. https://doi.org/10.1088/1742-5468/ac9828'
chicago: 'Mondelli, Marco, and Ramji Venkataramanan. “Approximate Message Passing
with Spectral Initialization for Generalized Linear Models.” Journal of Statistical
Mechanics: Theory and Experiment. IOP Publishing, 2022. https://doi.org/10.1088/1742-5468/ac9828.'
ieee: 'M. Mondelli and R. Venkataramanan, “Approximate message passing with spectral
initialization for generalized linear models,” Journal of Statistical Mechanics:
Theory and Experiment, vol. 2022, no. 11. IOP Publishing, 2022.'
ista: 'Mondelli M, Venkataramanan R. 2022. Approximate message passing with spectral
initialization for generalized linear models. Journal of Statistical Mechanics:
Theory and Experiment. 2022(11), 114003.'
mla: 'Mondelli, Marco, and Ramji Venkataramanan. “Approximate Message Passing with
Spectral Initialization for Generalized Linear Models.” Journal of Statistical
Mechanics: Theory and Experiment, vol. 2022, no. 11, 114003, IOP Publishing,
2022, doi:10.1088/1742-5468/ac9828.'
short: 'M. Mondelli, R. Venkataramanan, Journal of Statistical Mechanics: Theory
and Experiment 2022 (2022).'
corr_author: '1'
date_created: 2023-02-02T08:31:57Z
date_published: 2022-11-24T00:00:00Z
date_updated: 2025-04-15T07:50:16Z
day: '24'
ddc:
- '510'
- '530'
department:
- _id: MaMo
doi: 10.1088/1742-5468/ac9828
external_id:
isi:
- '000889589900001'
file:
- access_level: open_access
checksum: 01411ffa76d3e380a0446baeb89b1ef7
content_type: application/pdf
creator: dernst
date_created: 2023-02-02T08:35:52Z
date_updated: 2023-02-02T08:35:52Z
file_id: '12481'
file_name: 2022_JourStatisticalMechanics_Mondelli.pdf
file_size: 1729997
relation: main_file
success: 1
file_date_updated: 2023-02-02T08:35:52Z
has_accepted_license: '1'
intvolume: ' 2022'
isi: 1
issue: '11'
keyword:
- Statistics
- Probability and Uncertainty
- Statistics and Probability
- Statistical and Nonlinear Physics
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: 'Journal of Statistical Mechanics: Theory and Experiment'
publication_identifier:
issn:
- 1742-5468
publication_status: published
publisher: IOP Publishing
quality_controlled: '1'
related_material:
record:
- id: '10598'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Approximate message passing with spectral initialization for generalized linear
models
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: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 2022
year: '2022'
...
---
_id: '12495'
abstract:
- lang: eng
text: "Fairness-aware learning aims at constructing classifiers that not only make
accurate predictions, but also do not discriminate against specific groups. It
is a fast-growing area of\r\nmachine learning with far-reaching societal impact.
However, existing fair learning methods\r\nare vulnerable to accidental or malicious
artifacts in the training data, which can cause\r\nthem to unknowingly produce
unfair classifiers. In this work we address the problem of\r\nfair learning from
unreliable training data in the robust multisource setting, where the\r\navailable
training data comes from multiple sources, a fraction of which might not be representative
of the true data distribution. We introduce FLEA, a filtering-based algorithm\r\nthat
identifies and suppresses those data sources that would have a negative impact
on\r\nfairness or accuracy if they were used for training. As such, FLEA is not
a replacement of\r\nprior fairness-aware learning methods but rather an augmentation
that makes any of them\r\nrobust against unreliable training data. We show the
effectiveness of our approach by a\r\ndiverse range of experiments on multiple
datasets. Additionally, we prove formally that\r\n–given enough data– FLEA protects
the learner against corruptions as long as the fraction of\r\naffected data sources
is less than half. Our source code and documentation are available at\r\nhttps://github.com/ISTAustria-CVML/FLEA."
acknowledged_ssus:
- _id: ScienComp
acknowledgement: 'The authors would like to thank Bernd Prach, Elias Frantar, Alexandra
Peste, Mahdi Nikdan, and Peter Súkeník for their helpful feedback. This research
was supported by the Scientific Service Units (SSU) of IST Austria through resources
provided by Scientific Computing (SciComp). This publication was made possible by
an ETH AI Center postdoctoral fellowship granted to Nikola Konstantinov. Eugenia
Iofinova was supported in part by the FWF DK VGSCO, grant agreement number W1260-N35. '
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Eugenia B
full_name: Iofinova, Eugenia B
id: f9a17499-f6e0-11ea-865d-fdf9a3f77117
last_name: Iofinova
orcid: 0000-0002-7778-3221
- first_name: Nikola H
full_name: Konstantinov, Nikola H
id: 4B9D76E4-F248-11E8-B48F-1D18A9856A87
last_name: Konstantinov
orcid: 0009-0009-5204-7621
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Iofinova EB, Konstantinov NH, Lampert C. FLEA: Provably robust fair multisource
learning from unreliable training data. Transactions on Machine Learning Research.
2022.'
apa: 'Iofinova, E. B., Konstantinov, N. H., & Lampert, C. (2022). FLEA: Provably
robust fair multisource learning from unreliable training data. Transactions
on Machine Learning Research. ML Research Press.'
chicago: 'Iofinova, Eugenia B, Nikola H Konstantinov, and Christoph Lampert. “FLEA:
Provably Robust Fair Multisource Learning from Unreliable Training Data.” Transactions
on Machine Learning Research. ML Research Press, 2022.'
ieee: 'E. B. Iofinova, N. H. Konstantinov, and C. Lampert, “FLEA: Provably robust
fair multisource learning from unreliable training data,” Transactions on Machine
Learning Research. ML Research Press, 2022.'
ista: 'Iofinova EB, Konstantinov NH, Lampert C. 2022. FLEA: Provably robust fair
multisource learning from unreliable training data. Transactions on Machine Learning
Research.'
mla: 'Iofinova, Eugenia B., et al. “FLEA: Provably Robust Fair Multisource Learning
from Unreliable Training Data.” Transactions on Machine Learning Research,
ML Research Press, 2022.'
short: E.B. Iofinova, N.H. Konstantinov, C. Lampert, Transactions on Machine Learning
Research (2022).
corr_author: '1'
date_created: 2023-02-02T20:29:57Z
date_published: 2022-12-22T00:00:00Z
date_updated: 2025-12-30T11:04:31Z
day: '22'
ddc:
- '000'
department:
- _id: ChLa
external_id:
arxiv:
- '2106.11732'
file:
- access_level: open_access
checksum: 97c8a8470759cab597abb973ca137a3b
content_type: application/pdf
creator: dernst
date_created: 2023-02-23T10:30:04Z
date_updated: 2023-02-23T10:30:04Z
file_id: '12673'
file_name: 2022_TMLR_Iofinova.pdf
file_size: 1948063
relation: main_file
success: 1
file_date_updated: 2023-02-23T10:30:04Z
has_accepted_license: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://openreview.net/forum?id=XsPopigZXV
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 9B9290DE-BA93-11EA-9121-9846C619BF3A
grant_number: W1260-N35
name: Vienna Graduate School on Computational Optimization
publication: Transactions on Machine Learning Research
publication_identifier:
issn:
- 2835-8856
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
link:
- description: source code
relation: software
url: https://github.com/ISTAustria-CVML/FLEA
status: public
title: 'FLEA: Provably robust fair multisource learning from unreliable training data'
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: '2022'
...
---
_id: '12508'
abstract:
- lang: eng
text: "We explore the notion of history-determinism in the context of timed automata
(TA). History-deterministic automata are those in which nondeterminism can be
resolved on the fly, based on the run constructed thus far. History-determinism
is a robust property that admits different game-based characterisations, and history-deterministic
specifications allow for game-based verification without an expensive determinization
step.\r\nWe show yet another characterisation of history-determinism in terms
of fair simulation, at the general level of labelled transition systems: a system
is history-deterministic precisely if and only if it fairly simulates all language
smaller systems.\r\nFor timed automata over infinite timed words it is known that
universality is undecidable for Büchi TA. We show that for history-deterministic
TA with arbitrary parity acceptance, timed universality, inclusion, and synthesis
all remain decidable and are ExpTime-complete.\r\nFor the subclass of TA with
safety or reachability acceptance, we show that checking whether such an automaton
is history-deterministic is decidable (in ExpTime), and history-deterministic
TA with safety acceptance are effectively determinizable without introducing new
automata states."
acknowledgement: "Thomas A. Henzinger: This work was supported in part by the ERC-2020-AdG
101020093.\r\nPatrick Totzke: acknowledges support from the EPSRC, project no. EP/V025848/1.\r\n"
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Karoliina
full_name: Lehtinen, Karoliina
last_name: Lehtinen
- first_name: Patrick
full_name: Totzke, Patrick
last_name: Totzke
citation:
ama: 'Henzinger TA, Lehtinen K, Totzke P. History-deterministic timed automata.
In: 33rd International Conference on Concurrency Theory. Vol 243. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2022:14:1-14:21. doi:10.4230/LIPIcs.CONCUR.2022.14'
apa: 'Henzinger, T. A., Lehtinen, K., & Totzke, P. (2022). History-deterministic
timed automata. In 33rd International Conference on Concurrency Theory
(Vol. 243, p. 14:1-14:21). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2022.14'
chicago: Henzinger, Thomas A, Karoliina Lehtinen, and Patrick Totzke. “History-Deterministic
Timed Automata.” In 33rd International Conference on Concurrency Theory,
243:14:1-14:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.CONCUR.2022.14.
ieee: T. A. Henzinger, K. Lehtinen, and P. Totzke, “History-deterministic timed
automata,” in 33rd International Conference on Concurrency Theory, Warsaw,
Poland, 2022, vol. 243, p. 14:1-14:21.
ista: 'Henzinger TA, Lehtinen K, Totzke P. 2022. History-deterministic timed automata.
33rd International Conference on Concurrency Theory. CONCUR: Conference on Concurrency
Theory, LIPIcs, vol. 243, 14:1-14:21.'
mla: Henzinger, Thomas A., et al. “History-Deterministic Timed Automata.” 33rd
International Conference on Concurrency Theory, vol. 243, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2022, p. 14:1-14:21, doi:10.4230/LIPIcs.CONCUR.2022.14.
short: T.A. Henzinger, K. Lehtinen, P. Totzke, in:, 33rd International Conference
on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022,
p. 14:1-14:21.
conference:
end_date: 2022-09-16
location: Warsaw, Poland
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2022-09-13
corr_author: '1'
date_created: 2023-02-05T17:24:23Z
date_published: 2022-09-06T00:00:00Z
date_updated: 2025-09-08T14:35:16Z
day: '06'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2022.14
ec_funded: 1
file:
- access_level: open_access
checksum: 9e97e15628f66b2ad77f535bb0327dee
content_type: application/pdf
creator: dernst
date_created: 2023-02-06T09:21:09Z
date_updated: 2023-02-06T09:21:09Z
file_id: '12520'
file_name: 2022_LIPICs_Henzinger2.pdf
file_size: 717940
relation: main_file
success: 1
file_date_updated: 2023-02-06T09:21:09Z
has_accepted_license: '1'
intvolume: ' 243'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 14:1-14:21
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 33rd International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783959772464'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '18530'
relation: later_version
status: public
scopus_import: '1'
status: public
title: History-deterministic timed automata
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: 243
year: '2022'
...
---
_id: '12509'
abstract:
- lang: eng
text: A graph game is a two-player zero-sum game in which the players move a token
throughout a graph to produce an infinite path, which determines the winner or
payoff of the game. In bidding games, both players have budgets, and in each turn,
we hold an "auction" (bidding) to determine which player moves the token. In this
survey, we consider several bidding mechanisms and their effect on the properties
of the game. Specifically, bidding games, and in particular bidding games of infinite
duration, have an intriguing equivalence with random-turn games in which in each
turn, the player who moves is chosen randomly. We summarize how minor changes
in the bidding mechanism lead to unexpected differences in the equivalence with
random-turn games.
acknowledgement: "Guy Avni: Work partially supported by the Israel Science Foundation,
ISF grant agreement\r\nno 1679/21.\r\nThomas A. Henzinger: This work was supported
in part by the ERC-2020-AdG 101020093.\r\nWe would like to thank all our collaborators
Milad Aghajohari, Ventsislav Chonev, Rasmus Ibsen-Jensen, Ismäel Jecker, Petr Novotný,
Josef Tkadlec, and Ðorđe Žikelić; we hope the collaboration was as fun and meaningful
for you as it was for us."
article_processing_charge: No
author:
- 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: 'Avni G, Henzinger TA. An updated survey of bidding games on graphs. In: 47th
International Symposium on Mathematical Foundations of Computer Science. Vol
241. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022:3:1-3:6. doi:10.4230/LIPIcs.MFCS.2022.3'
apa: 'Avni, G., & Henzinger, T. A. (2022). An updated survey of bidding games
on graphs. In 47th International Symposium on Mathematical Foundations of Computer
Science (Vol. 241, p. 3:1-3:6). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2022.3'
chicago: 'Avni, Guy, and Thomas A Henzinger. “An Updated Survey of Bidding Games
on Graphs.” In 47th International Symposium on Mathematical Foundations of
Computer Science, 241:3:1-3:6. Leibniz International Proceedings in Informatics
(LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022. https://doi.org/10.4230/LIPIcs.MFCS.2022.3.'
ieee: G. Avni and T. A. Henzinger, “An updated survey of bidding games on graphs,”
in 47th International Symposium on Mathematical Foundations of Computer Science,
Vienna, Austria, 2022, vol. 241, p. 3:1-3:6.
ista: 'Avni G, Henzinger TA. 2022. An updated survey of bidding games on graphs.
47th International Symposium on Mathematical Foundations of Computer Science.
MFCS: Mathematical Foundations of Computer ScienceLeibniz International Proceedings
in Informatics (LIPIcs) vol. 241, 3:1-3:6.'
mla: Avni, Guy, and Thomas A. Henzinger. “An Updated Survey of Bidding Games on
Graphs.” 47th International Symposium on Mathematical Foundations of Computer
Science, vol. 241, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022,
p. 3:1-3:6, doi:10.4230/LIPIcs.MFCS.2022.3.
short: G. Avni, T.A. Henzinger, in:, 47th International Symposium on Mathematical
Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
Dagstuhl, Germany, 2022, p. 3:1-3:6.
conference:
end_date: 2022-08-26
location: Vienna, Austria
name: 'MFCS: Mathematical Foundations of Computer Science'
start_date: 2022-08-22
corr_author: '1'
date_created: 2023-02-05T17:26:01Z
date_published: 2022-08-22T00:00:00Z
date_updated: 2025-07-10T11:50:27Z
day: '22'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.MFCS.2022.3
ec_funded: 1
file:
- access_level: open_access
checksum: 1888ec9421622f9526fbec2de035f132
content_type: application/pdf
creator: dernst
date_created: 2023-02-06T09:13:04Z
date_updated: 2023-02-06T09:13:04Z
file_id: '12519'
file_name: 2022_LIPICs_Avni.pdf
file_size: 624586
relation: main_file
success: 1
file_date_updated: 2023-02-06T09:13:04Z
has_accepted_license: '1'
intvolume: ' 241'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: 3:1-3:6
place: Dagstuhl, Germany
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 47th International Symposium on Mathematical Foundations of Computer
Science
publication_identifier:
isbn:
- '9783959772563'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: An updated survey of bidding games on graphs
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: 241
year: '2022'
...
---
_id: '12510'
abstract:
- lang: eng
text: "We introduce a new statistical verification algorithm that formally quantifies
the behavioral robustness of any time-continuous process formulated as a continuous-depth
model. Our algorithm solves a set of global optimization (Go) problems over a
given time horizon to construct a tight enclosure (Tube) of the set of all process
executions starting from a ball of initial states. We call our algorithm GoTube.
Through its construction, GoTube ensures that the bounding tube is conservative
up to a desired probability and up to a desired tightness.\r\n GoTube is implemented
in JAX and optimized to scale to complex continuous-depth neural network models.
Compared to advanced reachability analysis tools for time-continuous neural networks,
GoTube does not accumulate overapproximation errors between time steps and avoids
the infamous wrapping effect inherent in symbolic techniques. We show that GoTube
substantially outperforms state-of-the-art verification tools in terms of the
size of the initial ball, speed, time-horizon, task completion, and scalability
on a large set of experiments.\r\n GoTube is stable and sets the state-of-the-art
in terms of its ability to scale to time horizons well beyond what has been previously
possible."
acknowledgement: SG is funded by the Austrian Science Fund (FWF) project number W1255-N23.
ML and TH are supported in part by FWF under grant Z211-N23 (Wittgenstein Award)
and the ERC-2020-AdG 101020093. SS is supported by NSF awards DCL-2040599, CCF-1918225,
and CPS-1446832. RH and DR are partially supported by Boeing. RG is partially supported
by Horizon-2020 ECSEL Project grant No. 783163 (iDev40).
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Sophie A.
full_name: Gruenbacher, Sophie A.
last_name: Gruenbacher
- 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: 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
- first_name: Scott A.
full_name: Smolka, Scott A.
last_name: Smolka
- first_name: Radu
full_name: Grosu, Radu
last_name: Grosu
citation:
ama: 'Gruenbacher SA, Lechner M, Hasani R, et al. GoTube: Scalable statistical verification
of continuous-depth models. Proceedings of the AAAI Conference on Artificial
Intelligence. 2022;36(6):6755-6764. doi:10.1609/aaai.v36i6.20631'
apa: 'Gruenbacher, S. A., Lechner, M., Hasani, R., Rus, D., Henzinger, T. A., Smolka,
S. A., & Grosu, R. (2022). GoTube: Scalable statistical verification of continuous-depth
models. Proceedings of the AAAI Conference on Artificial Intelligence.
Association for the Advancement of Artificial Intelligence. https://doi.org/10.1609/aaai.v36i6.20631'
chicago: 'Gruenbacher, Sophie A., Mathias Lechner, Ramin Hasani, Daniela Rus, Thomas
A Henzinger, Scott A. Smolka, and Radu Grosu. “GoTube: Scalable Statistical Verification
of Continuous-Depth Models.” Proceedings of the AAAI Conference on Artificial
Intelligence. Association for the Advancement of Artificial Intelligence,
2022. https://doi.org/10.1609/aaai.v36i6.20631.'
ieee: 'S. A. Gruenbacher et al., “GoTube: Scalable statistical verification
of continuous-depth models,” Proceedings of the AAAI Conference on Artificial
Intelligence, vol. 36, no. 6. Association for the Advancement of Artificial
Intelligence, pp. 6755–6764, 2022.'
ista: 'Gruenbacher SA, Lechner M, Hasani R, Rus D, Henzinger TA, Smolka SA, Grosu
R. 2022. GoTube: Scalable statistical verification of continuous-depth models.
Proceedings of the AAAI Conference on Artificial Intelligence. 36(6), 6755–6764.'
mla: 'Gruenbacher, Sophie A., et al. “GoTube: Scalable Statistical Verification
of Continuous-Depth Models.” Proceedings of the AAAI Conference on Artificial
Intelligence, vol. 36, no. 6, Association for the Advancement of Artificial
Intelligence, 2022, pp. 6755–64, doi:10.1609/aaai.v36i6.20631.'
short: S.A. Gruenbacher, M. Lechner, R. Hasani, D. Rus, T.A. Henzinger, S.A. Smolka,
R. Grosu, Proceedings of the AAAI Conference on Artificial Intelligence 36 (2022)
6755–6764.
date_created: 2023-02-05T17:27:42Z
date_published: 2022-06-28T00:00:00Z
date_updated: 2025-04-15T06:26:14Z
day: '28'
department:
- _id: ToHe
doi: 10.1609/aaai.v36i6.20631
ec_funded: 1
external_id:
arxiv:
- '2107.08467'
intvolume: ' 36'
issue: '6'
keyword:
- General Medicine
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2107.08467
month: '06'
oa: 1
oa_version: Preprint
page: 6755-6764
project:
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: Proceedings of the AAAI Conference on Artificial Intelligence
publication_identifier:
eissn:
- 2374-3468
isbn:
- '978577358350'
issn:
- 2159-5399
publication_status: published
publisher: Association for the Advancement of Artificial Intelligence
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'GoTube: Scalable statistical verification of continuous-depth models'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2022'
...
---
_id: '12516'
abstract:
- lang: eng
text: "The homogeneous continuous LWE (hCLWE) problem is to distinguish samples
of a specific high-dimensional Gaussian mixture from standard normal samples.
It was shown to be at least as hard as Learning with Errors, but no reduction
in the other direction is currently known.\r\nWe present four new public-key encryption
schemes based on the hardness of hCLWE, with varying tradeoffs between decryption
and security errors, and different discretization techniques. Our schemes yield
a polynomial-time algorithm for solving hCLWE using a Statistical Zero-Knowledge
oracle."
acknowledgement: "We are grateful to Devika Sharma and Luca Trevisan for their insight
and advice and to an anonymous reviewer for helpful comments.\r\n\r\nThis work was
supported by the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation programme (Grant agreement No. 101019547). The first
author was additionally supported by RGC GRF CUHK14209920 and the fourth author
was additionally supported by ISF grant No. 1399/17, project PROMETHEUS (Grant 780701),
and Cariplo CRYPTONOMEX grant."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Andrej
full_name: Bogdanov, Andrej
last_name: Bogdanov
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
- first_name: Alon
full_name: Rosen, Alon
last_name: Rosen
citation:
ama: 'Bogdanov A, Cueto Noval M, Hoffmann C, Rosen A. Public-Key Encryption from Homogeneous
CLWE. In: Theory of Cryptography. Vol 13748. Springer Nature; 2022:565-592.
doi:10.1007/978-3-031-22365-5_20'
apa: 'Bogdanov, A., Cueto Noval, M., Hoffmann, C., & Rosen, A. (2022). Public-Key
Encryption from Homogeneous CLWE. In Theory of Cryptography (Vol. 13748,
pp. 565–592). Chicago, IL, United States: Springer Nature. https://doi.org/10.1007/978-3-031-22365-5_20'
chicago: Bogdanov, Andrej, Miguel Cueto Noval, Charlotte Hoffmann, and Alon Rosen.
“Public-Key Encryption from Homogeneous CLWE.” In Theory of Cryptography,
13748:565–92. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-22365-5_20.
ieee: A. Bogdanov, M. Cueto Noval, C. Hoffmann, and A. Rosen, “Public-Key Encryption
from Homogeneous CLWE,” in Theory of Cryptography, Chicago, IL, United
States, 2022, vol. 13748, pp. 565–592.
ista: 'Bogdanov A, Cueto Noval M, Hoffmann C, Rosen A. 2022. Public-Key Encryption
from Homogeneous CLWE. Theory of Cryptography. TCC: Theory of Cryptography, LNCS,
vol. 13748, 565–592.'
mla: Bogdanov, Andrej, et al. “Public-Key Encryption from Homogeneous CLWE.” Theory
of Cryptography, vol. 13748, Springer Nature, 2022, pp. 565–92, doi:10.1007/978-3-031-22365-5_20.
short: A. Bogdanov, M. Cueto Noval, C. Hoffmann, A. Rosen, in:, Theory of Cryptography,
Springer Nature, 2022, pp. 565–592.
conference:
end_date: 2022-11-10
location: Chicago, IL, United States
name: 'TCC: Theory of Cryptography'
start_date: 2022-11-07
corr_author: '1'
date_created: 2023-02-05T23:01:00Z
date_published: 2022-12-21T00:00:00Z
date_updated: 2024-10-09T21:04:05Z
day: '21'
department:
- _id: KrPi
doi: 10.1007/978-3-031-22365-5_20
external_id:
isi:
- '000921318200020'
intvolume: ' 13748'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2022/093
month: '12'
oa: 1
oa_version: Preprint
page: 565-592
publication: Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031223648'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Public-Key Encryption from Homogeneous CLWE
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13748
year: '2022'
...
---
_id: '12536'
abstract:
- lang: eng
text: 'We consider the problem of estimating a rank-1 signal corrupted by structured
rotationally invariant noise, and address the following question: how well do
inference algorithms perform when the noise statistics is unknown and hence Gaussian
noise is assumed? While the matched Bayes-optimal setting with unstructured noise
is well understood, the analysis of this mismatched problem is only at its premises.
In this paper, we make a step towards understanding the effect of the strong source
of mismatch which is the noise statistics. Our main technical contribution is
the rigorous analysis of a Bayes estimator and of an approximate message passing
(AMP) algorithm, both of which incorrectly assume a Gaussian setup. The first
result exploits the theory of spherical integrals and of low-rank matrix perturbations;
the idea behind the second one is to design and analyze an artificial AMP which,
by taking advantage of the flexibility in the denoisers, is able to "correct"
the mismatch. Armed with these sharp asymptotic characterizations, we unveil a
rich and often unexpected phenomenology. For example, despite AMP is in principle
designed to efficiently compute the Bayes estimator, the former is outperformed
by the latter in terms of mean-square error. We show that this performance gap
is due to an incorrect estimation of the signal norm. In fact, when the SNR is
large enough, the overlaps of the AMP and the Bayes estimator coincide, and they
even match those of optimal estimators taking into account the structure of the
noise.'
acknowledgement: "M. Mondelli was partially supported by the 2019 Lopez-Loreta Prize.
The authors acknowledge\r\ndiscussions with A. Krajenbrink, M. Robinson, A. Depope,
N. Macris and F. Pourkamali.\r\n"
alternative_title:
- NeurIPS
article_processing_charge: No
arxiv: 1
author:
- first_name: Jean
full_name: Barbier, Jean
last_name: Barbier
- first_name: TianQi
full_name: Hou, TianQi
last_name: Hou
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Manuel
full_name: Saenz, Manuel
last_name: Saenz
citation:
ama: 'Barbier J, Hou T, Mondelli M, Saenz M. The price of ignorance: How much does
it cost to forget noise structure in low-rank matrix estimation? In: 36th Annual
Conference on Neural Information Processing Systems. Vol 35. ; 2022.'
apa: 'Barbier, J., Hou, T., Mondelli, M., & Saenz, M. (2022). The price of ignorance:
How much does it cost to forget noise structure in low-rank matrix estimation?
In 36th Annual Conference on Neural Information Processing Systems (Vol.
35). New Orleans, LA, United States.'
chicago: 'Barbier, Jean, TianQi Hou, Marco Mondelli, and Manuel Saenz. “The Price
of Ignorance: How Much Does It Cost to Forget Noise Structure in Low-Rank Matrix
Estimation?” In 36th Annual Conference on Neural Information Processing Systems,
Vol. 35, 2022.'
ieee: 'J. Barbier, T. Hou, M. Mondelli, and M. Saenz, “The price of ignorance: How
much does it cost to forget noise structure in low-rank matrix estimation?,” in
36th Annual Conference on Neural Information Processing Systems, New Orleans,
LA, United States, 2022, vol. 35.'
ista: 'Barbier J, Hou T, Mondelli M, Saenz M. 2022. The price of ignorance: How
much does it cost to forget noise structure in low-rank matrix estimation? 36th
Annual Conference on Neural Information Processing Systems. NeurIPS: Neural Information
Processing Systems, NeurIPS, vol. 35.'
mla: 'Barbier, Jean, et al. “The Price of Ignorance: How Much Does It Cost to Forget
Noise Structure in Low-Rank Matrix Estimation?” 36th Annual Conference on Neural
Information Processing Systems, vol. 35, 2022.'
short: J. Barbier, T. Hou, M. Mondelli, M. Saenz, in:, 36th Annual Conference on
Neural Information Processing Systems, 2022.
conference:
end_date: 2022-12-09
location: New Orleans, LA, United States
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2022-11-28
corr_author: '1'
date_created: 2023-02-10T13:45:41Z
date_published: 2022-11-20T00:00:00Z
date_updated: 2024-10-09T21:04:25Z
day: '20'
department:
- _id: MaMo
external_id:
arxiv:
- '2205.10009'
intvolume: ' 35'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2205.10009
month: '11'
oa: 1
oa_version: Preprint
publication: 36th Annual Conference on Neural Information Processing Systems
publication_identifier:
isbn:
- '9781713871088'
publication_status: published
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The price of ignorance: How much does it cost to forget noise structure in
low-rank matrix estimation?'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 35
year: '2022'
...
---
OA_place: repository
OA_type: green
_id: '12537'
abstract:
- lang: eng
text: 'The Neural Tangent Kernel (NTK) has emerged as a powerful tool to provide
memorization, optimization and generalization guarantees in deep neural networks.
A line of work has studied the NTK spectrum for two-layer and deep networks with
at least a layer with Ω(N) neurons, N being the number of training samples. Furthermore,
there is increasing evidence suggesting that deep networks with sub-linear layer
widths are powerful memorizers and optimizers, as long as the number of parameters
exceeds the number of samples. Thus, a natural open question is whether the NTK
is well conditioned in such a challenging sub-linear setup. In this paper, we
answer this question in the affirmative. Our key technical contribution is a lower
bound on the smallest NTK eigenvalue for deep networks with the minimum possible
over-parameterization: the number of parameters is roughly Ω(N) and, hence, the
number of neurons is as little as Ω(N−−√). To showcase the applicability of our
NTK bounds, we provide two results concerning memorization capacity and optimization
guarantees for gradient descent training.'
acknowledgement: "The authors were partially supported by the 2019 Lopez-Loreta prize,
and they would like to thank\r\nQuynh Nguyen, Mahdi Soltanolkotabi and Adel Javanmard
for helpful discussions.\r\n"
alternative_title:
- Advances in Neural Information Processing Systems
article_processing_charge: No
arxiv: 1
author:
- first_name: Simone
full_name: Bombari, Simone
id: ca726dda-de17-11ea-bc14-f9da834f63aa
last_name: Bombari
- first_name: Mohammad Hossein
full_name: Amani, Mohammad Hossein
last_name: Amani
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Bombari S, Amani MH, Mondelli M. Memorization and optimization in deep neural
networks with minimum over-parameterization. In: 36th Conference on Neural
Information Processing Systems. Vol 35. Neural Information Processing Systems
Foundation; 2022:7628-7640.'
apa: 'Bombari, S., Amani, M. H., & Mondelli, M. (2022). Memorization and optimization
in deep neural networks with minimum over-parameterization. In 36th Conference
on Neural Information Processing Systems (Vol. 35, pp. 7628–7640). New Orleans,
LA, United States: Neural Information Processing Systems Foundation.'
chicago: Bombari, Simone, Mohammad Hossein Amani, and Marco Mondelli. “Memorization
and Optimization in Deep Neural Networks with Minimum Over-Parameterization.”
In 36th Conference on Neural Information Processing Systems, 35:7628–40.
Neural Information Processing Systems Foundation, 2022.
ieee: S. Bombari, M. H. Amani, and M. Mondelli, “Memorization and optimization in
deep neural networks with minimum over-parameterization,” in 36th Conference
on Neural Information Processing Systems, New Orleans, LA, United States,
2022, vol. 35, pp. 7628–7640.
ista: 'Bombari S, Amani MH, Mondelli M. 2022. Memorization and optimization in deep
neural networks with minimum over-parameterization. 36th Conference on Neural
Information Processing Systems. NeurIPS: Neural Information Processing Systems,
Advances in Neural Information Processing Systems, vol. 35, 7628–7640.'
mla: Bombari, Simone, et al. “Memorization and Optimization in Deep Neural Networks
with Minimum Over-Parameterization.” 36th Conference on Neural Information
Processing Systems, vol. 35, Neural Information Processing Systems Foundation,
2022, pp. 7628–40.
short: S. Bombari, M.H. Amani, M. Mondelli, in:, 36th Conference on Neural Information
Processing Systems, Neural Information Processing Systems Foundation, 2022, pp.
7628–7640.
conference:
end_date: 2022-12-09
location: New Orleans, LA, United States
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2022-11-28
corr_author: '1'
date_created: 2023-02-10T13:46:37Z
date_published: 2022-07-24T00:00:00Z
date_updated: 2025-05-14T11:28:22Z
day: '24'
department:
- _id: MaMo
external_id:
arxiv:
- '2205.10217'
intvolume: ' 35'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2205.10217'
month: '07'
oa: 1
oa_version: Preprint
page: 7628-7640
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: 36th Conference on Neural Information Processing Systems
publication_identifier:
eissn:
- 1049-5258
isbn:
- '9781713871088'
publication_status: published
publisher: Neural Information Processing Systems Foundation
quality_controlled: '1'
status: public
title: Memorization and optimization in deep neural networks with minimum over-parameterization
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 35
year: '2022'
...
---
_id: '12538'
abstract:
- lang: eng
text: In this paper, we study the compression of a target two-layer neural network
with N nodes into a compressed network with MIEEE Information Theory Workshop.
2022:588-593. doi:10.1109/ITW54588.2022.9965870
apa: 'Amani, M. H., Bombari, S., Mondelli, M., Pukdee, R., & Rini, S. (2022).
Sharp asymptotics on the compression of two-layer neural networks. IEEE Information
Theory Workshop. Mumbai, India: IEEE. https://doi.org/10.1109/ITW54588.2022.9965870'
chicago: Amani, Mohammad Hossein, Simone Bombari, Marco Mondelli, Rattana Pukdee,
and Stefano Rini. “Sharp Asymptotics on the Compression of Two-Layer Neural Networks.”
IEEE Information Theory Workshop. IEEE, 2022. https://doi.org/10.1109/ITW54588.2022.9965870.
ieee: M. H. Amani, S. Bombari, M. Mondelli, R. Pukdee, and S. Rini, “Sharp asymptotics
on the compression of two-layer neural networks,” IEEE Information Theory Workshop.
IEEE, pp. 588–593, 2022.
ista: Amani MH, Bombari S, Mondelli M, Pukdee R, Rini S. 2022. Sharp asymptotics
on the compression of two-layer neural networks. IEEE Information Theory Workshop.,
588–593.
mla: Amani, Mohammad Hossein, et al. “Sharp Asymptotics on the Compression of Two-Layer
Neural Networks.” IEEE Information Theory Workshop, IEEE, 2022, pp. 588–93,
doi:10.1109/ITW54588.2022.9965870.
short: M.H. Amani, S. Bombari, M. Mondelli, R. Pukdee, S. Rini, IEEE Information
Theory Workshop (2022) 588–593.
conference:
end_date: 2022-11-09
location: Mumbai, India
name: 'ITW: Information Theory Workshop'
start_date: 2022-11-01
date_created: 2023-02-10T13:47:56Z
date_published: 2022-11-16T00:00:00Z
date_updated: 2025-09-10T09:53:31Z
day: '16'
department:
- _id: MaMo
doi: 10.1109/ITW54588.2022.9965870
external_id:
arxiv:
- '2205.08199'
isi:
- '000904341100099'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2205.08199'
month: '11'
oa: 1
oa_version: Preprint
page: 588-593
publication: IEEE Information Theory Workshop
publication_identifier:
isbn:
- '9781665483414'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Sharp asymptotics on the compression of two-layer neural networks
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2022'
...
---
_id: '12540'
abstract:
- lang: eng
text: We consider the problem of signal estimation in generalized linear models
defined via rotationally invariant design matrices. Since these matrices can have
an arbitrary spectral distribution, this model is well suited for capturing complex
correlation structures which often arise in applications. We propose a novel family
of approximate message passing (AMP) algorithms for signal estimation, and rigorously
characterize their performance in the high-dimensional limit via a state evolution
recursion. Our rotationally invariant AMP has complexity of the same order as
the existing AMP derived under the restrictive assumption of a Gaussian design;
our algorithm also recovers this existing AMP as a special case. Numerical results
showcase a performance close to Vector AMP (which is conjectured to be Bayes-optimal
in some settings), but obtained with a much lower complexity, as the proposed
algorithm does not require a computationally expensive singular value decomposition.
acknowledgement: The authors would like to thank the anonymous reviewers for their
helpful comments. KK and MM were partially supported by the 2019 Lopez-Loreta Prize.
article_number: '22'
article_processing_charge: No
author:
- first_name: Ramji
full_name: Venkataramanan, Ramji
last_name: Venkataramanan
- first_name: Kevin
full_name: Kögler, Kevin
id: 94ec913c-dc85-11ea-9058-e5051ab2428b
last_name: Kögler
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Venkataramanan R, Kögler K, Mondelli M. Estimation in rotationally invariant
generalized linear models via approximate message passing. In: Proceedings
of the 39th International Conference on Machine Learning. Vol 162. ML Research
Press; 2022.'
apa: 'Venkataramanan, R., Kögler, K., & Mondelli, M. (2022). Estimation in rotationally
invariant generalized linear models via approximate message passing. In Proceedings
of the 39th International Conference on Machine Learning (Vol. 162). Baltimore,
MD, United States: ML Research Press.'
chicago: Venkataramanan, Ramji, Kevin Kögler, and Marco Mondelli. “Estimation in
Rotationally Invariant Generalized Linear Models via Approximate Message Passing.”
In Proceedings of the 39th International Conference on Machine Learning,
Vol. 162. ML Research Press, 2022.
ieee: R. Venkataramanan, K. Kögler, and M. Mondelli, “Estimation in rotationally
invariant generalized linear models via approximate message passing,” in Proceedings
of the 39th International Conference on Machine Learning, Baltimore, MD, United
States, 2022, vol. 162.
ista: 'Venkataramanan R, Kögler K, Mondelli M. 2022. Estimation in rotationally
invariant generalized linear models via approximate message passing. Proceedings
of the 39th International Conference on Machine Learning. ICML: International
Conference on Machine Learning vol. 162, 22.'
mla: Venkataramanan, Ramji, et al. “Estimation in Rotationally Invariant Generalized
Linear Models via Approximate Message Passing.” Proceedings of the 39th International
Conference on Machine Learning, vol. 162, 22, ML Research Press, 2022.
short: R. Venkataramanan, K. Kögler, M. Mondelli, in:, Proceedings of the 39th International
Conference on Machine Learning, ML Research Press, 2022.
conference:
end_date: 2022-07-23
location: Baltimore, MD, United States
name: 'ICML: International Conference on Machine Learning'
start_date: 2022-07-17
corr_author: '1'
date_created: 2023-02-10T13:49:04Z
date_published: 2022-01-01T00:00:00Z
date_updated: 2025-04-15T07:50:16Z
ddc:
- '000'
department:
- _id: MaMo
file:
- access_level: open_access
checksum: 67436eb0a660789514cdf9db79e84683
content_type: application/pdf
creator: dernst
date_created: 2023-02-13T10:53:11Z
date_updated: 2023-02-13T10:53:11Z
file_id: '12547'
file_name: 2022_PMLR_Venkataramanan.pdf
file_size: 2341343
relation: main_file
success: 1
file_date_updated: 2023-02-13T10:53:11Z
has_accepted_license: '1'
intvolume: ' 162'
language:
- iso: eng
oa: 1
oa_version: Published Version
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Proceedings of the 39th International Conference on Machine Learning
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
status: public
title: Estimation in rotationally invariant generalized linear models via approximate
message passing
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 162
year: '2022'
...
---
_id: '12568'
abstract:
- lang: eng
text: We treat the problem of risk-aware control for stochastic shortest path (SSP)
on Markov decision processes (MDP). Typically, expectation is considered for SSP,
which however is oblivious to the incurred risk. We present an alternative view,
instead optimizing conditional value-at-risk (CVaR), an established risk measure.
We treat both Markov chains as well as MDP and introduce, through novel insights,
two algorithms, based on linear programming and value iteration, respectively.
Both algorithms offer precise and provably correct solutions. Evaluation of our
prototype implementation shows that risk-aware control is feasible on several
moderately sized models.
article_processing_charge: No
arxiv: 1
author:
- first_name: Tobias
full_name: Meggendorfer, Tobias
id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
last_name: Meggendorfer
orcid: 0000-0002-1712-2165
citation:
ama: 'Meggendorfer T. Risk-aware stochastic shortest path. In: Proceedings of
the 36th AAAI Conference on Artificial Intelligence, AAAI 2022. Vol 36. Association
for the Advancement of Artificial Intelligence; 2022:9858-9867. doi:10.1609/aaai.v36i9.21222'
apa: 'Meggendorfer, T. (2022). Risk-aware stochastic shortest path. In Proceedings
of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022 (Vol. 36,
pp. 9858–9867). Virtual: Association for the Advancement of Artificial Intelligence.
https://doi.org/10.1609/aaai.v36i9.21222'
chicago: Meggendorfer, Tobias. “Risk-Aware Stochastic Shortest Path.” In Proceedings
of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022, 36:9858–67.
Association for the Advancement of Artificial Intelligence, 2022. https://doi.org/10.1609/aaai.v36i9.21222.
ieee: T. Meggendorfer, “Risk-aware stochastic shortest path,” in Proceedings
of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022, Virtual,
2022, vol. 36, no. 9, pp. 9858–9867.
ista: Meggendorfer T. 2022. Risk-aware stochastic shortest path. Proceedings of
the 36th AAAI Conference on Artificial Intelligence, AAAI 2022. Conference on
Artificial Intelligence vol. 36, 9858–9867.
mla: Meggendorfer, Tobias. “Risk-Aware Stochastic Shortest Path.” Proceedings
of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022, vol. 36,
no. 9, Association for the Advancement of Artificial Intelligence, 2022, pp. 9858–67,
doi:10.1609/aaai.v36i9.21222.
short: T. Meggendorfer, in:, Proceedings of the 36th AAAI Conference on Artificial
Intelligence, AAAI 2022, Association for the Advancement of Artificial Intelligence,
2022, pp. 9858–9867.
conference:
end_date: 2022-03-01
location: Virtual
name: Conference on Artificial Intelligence
start_date: 2022-02-22
corr_author: '1'
date_created: 2023-02-19T23:00:56Z
date_published: 2022-06-28T00:00:00Z
date_updated: 2024-10-09T21:04:32Z
day: '28'
department:
- _id: KrCh
doi: 10.1609/aaai.v36i9.21222
external_id:
arxiv:
- '2203.01640'
intvolume: ' 36'
issue: '9'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2203.01640'
month: '06'
oa: 1
oa_version: Preprint
page: 9858-9867
publication: Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI
2022
publication_identifier:
eissn:
- 2374-3468
isbn:
- '1577358767'
publication_status: published
publisher: Association for the Advancement of Artificial Intelligence
quality_controlled: '1'
scopus_import: '1'
status: public
title: Risk-aware stochastic shortest path
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2022'
...
---
_id: '12670'
abstract:
- lang: eng
text: DNA methylation plays essential homeostatic functions in eukaryotic genomes.
In animals, DNA methylation is also developmentally regulated and, in turn, regulates
development. In the past two decades, huge research effort has endorsed the understanding
that DNA methylation plays a similar role in plant development, especially during
sexual reproduction. The power of whole-genome sequencing and cell isolation techniques,
as well as bioinformatics tools, have enabled recent studies to reveal dynamic
changes in DNA methylation during germline development. Furthermore, the combination
of these technological advances with genetics, developmental biology and cell
biology tools has revealed functional methylation reprogramming events that control
gene and transposon activities in flowering plant germlines. In this review, we
discuss the major advances in our knowledge of DNA methylation dynamics during
male and female germline development in flowering plants.
article_processing_charge: No
article_type: review
author:
- first_name: Shengbo
full_name: He, Shengbo
last_name: He
- first_name: Xiaoqi
full_name: Feng, Xiaoqi
id: e0164712-22ee-11ed-b12a-d80fcdf35958
last_name: Feng
orcid: 0000-0002-4008-1234
citation:
ama: He S, Feng X. DNA methylation dynamics during germline development. Journal
of Integrative Plant Biology. 2022;64(12):2240-2251. doi:10.1111/jipb.13422
apa: He, S., & Feng, X. (2022). DNA methylation dynamics during germline development.
Journal of Integrative Plant Biology. Wiley. https://doi.org/10.1111/jipb.13422
chicago: He, Shengbo, and Xiaoqi Feng. “DNA Methylation Dynamics during Germline
Development.” Journal of Integrative Plant Biology. Wiley, 2022. https://doi.org/10.1111/jipb.13422.
ieee: S. He and X. Feng, “DNA methylation dynamics during germline development,”
Journal of Integrative Plant Biology, vol. 64, no. 12. Wiley, pp. 2240–2251,
2022.
ista: He S, Feng X. 2022. DNA methylation dynamics during germline development.
Journal of Integrative Plant Biology. 64(12), 2240–2251.
mla: He, Shengbo, and Xiaoqi Feng. “DNA Methylation Dynamics during Germline Development.”
Journal of Integrative Plant Biology, vol. 64, no. 12, Wiley, 2022, pp.
2240–51, doi:10.1111/jipb.13422.
short: S. He, X. Feng, Journal of Integrative Plant Biology 64 (2022) 2240–2251.
date_created: 2023-02-23T09:15:57Z
date_published: 2022-12-07T00:00:00Z
date_updated: 2024-10-14T12:03:14Z
day: '07'
department:
- _id: XiFe
doi: 10.1111/jipb.13422
extern: '1'
external_id:
pmid:
- '36478632'
intvolume: ' 64'
issue: '12'
keyword:
- Plant Science
- General Biochemistry
- Genetics and Molecular Biology
- Biochemistry
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1111/jipb.13422
month: '12'
oa: 1
oa_version: Published Version
page: 2240-2251
pmid: 1
publication: Journal of Integrative Plant Biology
publication_identifier:
eissn:
- 1744-7909
issn:
- 1672-9072
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: DNA methylation dynamics during germline development
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 64
year: '2022'
...
---
_id: '12671'
abstract:
- lang: eng
text: Sperm chromatin is typically transformed by protamines into a compact and
transcriptionally inactive state1,2. Sperm cells of flowering plants lack protamines,
yet they have small, transcriptionally active nuclei with chromatin condensed
through an unknown mechanism3,4. Here we show that a histone variant, H2B.8, mediates
sperm chromatin and nuclear condensation in Arabidopsis thaliana. Loss of H2B.8
causes enlarged sperm nuclei with dispersed chromatin, whereas ectopic expression
in somatic cells produces smaller nuclei with aggregated chromatin. This result
demonstrates that H2B.8 is sufficient for chromatin condensation. H2B.8 aggregates
transcriptionally inactive AT-rich chromatin into phase-separated condensates,
which facilitates nuclear compaction without reducing transcription. Reciprocal
crosses show that mutation of h2b.8 reduces male transmission, which suggests
that H2B.8-mediated sperm compaction is important for fertility. Altogether, our
results reveal a new mechanism of nuclear compaction through global aggregation
of unexpressed chromatin. We propose that H2B.8 is an evolutionary innovation
of flowering plants that achieves nuclear condensation compatible with active
transcription.
article_processing_charge: No
article_type: original
author:
- first_name: Toby
full_name: Buttress, Toby
last_name: Buttress
- first_name: Shengbo
full_name: He, Shengbo
last_name: He
- first_name: Liang
full_name: Wang, Liang
last_name: Wang
- first_name: Shaoli
full_name: Zhou, Shaoli
last_name: Zhou
- first_name: Gerhard
full_name: Saalbach, Gerhard
last_name: Saalbach
- first_name: Martin
full_name: Vickers, Martin
last_name: Vickers
- first_name: Guohong
full_name: Li, Guohong
last_name: Li
- first_name: Pilong
full_name: Li, Pilong
last_name: Li
- first_name: Xiaoqi
full_name: Feng, Xiaoqi
id: e0164712-22ee-11ed-b12a-d80fcdf35958
last_name: Feng
orcid: 0000-0002-4008-1234
citation:
ama: Buttress T, He S, Wang L, et al. Histone H2B.8 compacts flowering plant sperm
through chromatin phase separation. Nature. 2022;611(7936):614-622. doi:10.1038/s41586-022-05386-6
apa: Buttress, T., He, S., Wang, L., Zhou, S., Saalbach, G., Vickers, M., … Feng,
X. (2022). Histone H2B.8 compacts flowering plant sperm through chromatin phase
separation. Nature. Springer Nature. https://doi.org/10.1038/s41586-022-05386-6
chicago: Buttress, Toby, Shengbo He, Liang Wang, Shaoli Zhou, Gerhard Saalbach,
Martin Vickers, Guohong Li, Pilong Li, and Xiaoqi Feng. “Histone H2B.8 Compacts
Flowering Plant Sperm through Chromatin Phase Separation.” Nature. Springer
Nature, 2022. https://doi.org/10.1038/s41586-022-05386-6.
ieee: T. Buttress et al., “Histone H2B.8 compacts flowering plant sperm through
chromatin phase separation,” Nature, vol. 611, no. 7936. Springer Nature,
pp. 614–622, 2022.
ista: Buttress T, He S, Wang L, Zhou S, Saalbach G, Vickers M, Li G, Li P, Feng
X. 2022. Histone H2B.8 compacts flowering plant sperm through chromatin phase
separation. Nature. 611(7936), 614–622.
mla: Buttress, Toby, et al. “Histone H2B.8 Compacts Flowering Plant Sperm through
Chromatin Phase Separation.” Nature, vol. 611, no. 7936, Springer Nature,
2022, pp. 614–22, doi:10.1038/s41586-022-05386-6.
short: T. Buttress, S. He, L. Wang, S. Zhou, G. Saalbach, M. Vickers, G. Li, P.
Li, X. Feng, Nature 611 (2022) 614–622.
date_created: 2023-02-23T09:17:05Z
date_published: 2022-11-17T00:00:00Z
date_updated: 2024-10-14T12:03:36Z
day: '17'
department:
- _id: XiFe
doi: 10.1038/s41586-022-05386-6
extern: '1'
external_id:
pmid:
- '36323776'
intvolume: ' 611'
issue: '7936'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1038/s41586-022-05386-6
month: '11'
oa: 1
oa_version: Published Version
page: 614-622
pmid: 1
publication: Nature
publication_identifier:
eissn:
- 1476-4687
issn:
- 0028-0836
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Histone H2B.8 compacts flowering plant sperm through chromatin phase separation
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 611
year: '2022'
...
---
_id: '12677'
abstract:
- lang: eng
text: "In modern sample-driven Prophet Inequality, an adversary chooses a sequence
of n items with values v1,v2,…,vn to be presented to a decision maker (DM). The
process follows in two phases. In the first phase (sampling phase), some items,
possibly selected at random, are revealed to the DM, but she can never accept
them. In the second phase, the DM is presented with the other items in a random
order and online fashion. For each item, she must make an irrevocable decision
to either accept the item and stop the process or reject the item forever and
proceed to the next item. The goal of the DM is to maximize the expected value
as compared to a Prophet (or offline algorithm) that has access to all information.
In this setting, the sampling phase has no cost and is not part of the optimization
process. However, in many scenarios, the samples are obtained as part of the decision-making
process.\r\nWe model this aspect as a two-phase Prophet Inequality where an adversary
chooses a sequence of 2n items with values v1,v2,…,v2n and the items are randomly
ordered. Finally, there are two phases of the Prophet Inequality problem with
the first n-items and the rest of the items, respectively. We show that some basic
algorithms achieve a ratio of at most 0.450. We present an algorithm that achieves
a ratio of at least 0.495. Finally, we show that for every algorithm the ratio
it can achieve is at most 0.502. Hence our algorithm is near-optimal."
acknowledgement: This research was partially supported by the ERC CoG 863818 (ForM-SMArt)
grant.
article_number: '2209.14368'
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Mona
full_name: Mohammadi, Mona
id: 4363614d-b686-11ed-a7d5-ac9e4a24bc2e
last_name: Mohammadi
- first_name: Raimundo J
full_name: Saona Urmeneta, Raimundo J
id: BD1DF4C4-D767-11E9-B658-BC13E6697425
last_name: Saona Urmeneta
orcid: 0000-0001-5103-038X
citation:
ama: Chatterjee K, Mohammadi M, Saona Urmeneta RJ. Repeated prophet inequality with
near-optimal bounds. arXiv. doi:10.48550/ARXIV.2209.14368
apa: Chatterjee, K., Mohammadi, M., & Saona Urmeneta, R. J. (n.d.). Repeated
prophet inequality with near-optimal bounds. arXiv. https://doi.org/10.48550/ARXIV.2209.14368
chicago: Chatterjee, Krishnendu, Mona Mohammadi, and Raimundo J Saona Urmeneta.
“Repeated Prophet Inequality with Near-Optimal Bounds.” ArXiv, n.d. https://doi.org/10.48550/ARXIV.2209.14368.
ieee: K. Chatterjee, M. Mohammadi, and R. J. Saona Urmeneta, “Repeated prophet inequality
with near-optimal bounds,” arXiv. .
ista: Chatterjee K, Mohammadi M, Saona Urmeneta RJ. Repeated prophet inequality
with near-optimal bounds. arXiv, 2209.14368.
mla: Chatterjee, Krishnendu, et al. “Repeated Prophet Inequality with Near-Optimal
Bounds.” ArXiv, 2209.14368, doi:10.48550/ARXIV.2209.14368.
short: K. Chatterjee, M. Mohammadi, R.J. Saona Urmeneta, ArXiv (n.d.).
corr_author: '1'
date_created: 2023-02-24T12:21:40Z
date_published: 2022-09-28T00:00:00Z
date_updated: 2025-04-14T07:52:48Z
day: '28'
department:
- _id: GradSch
- _id: KrCh
doi: 10.48550/ARXIV.2209.14368
ec_funded: 1
external_id:
arxiv:
- '2209.14368'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2209.14368'
month: '09'
oa: 1
oa_version: Preprint
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: arXiv
publication_status: submitted
status: public
title: Repeated prophet inequality with near-optimal bounds
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...
---
_id: '12684'
abstract:
- lang: eng
text: Given a place ω of a global function field K over a finite field, with
associated affine function ring Rω and completion Kω , the aim of this paper
is to give an effective joint equidistribution result for renormalized primitive
lattice points (a,b)∈Rω2 in the plane Kω2 , and for renormalized solutions
to the gcd equation ax+by=1 . The main tools are techniques of Goronik and Nevo
for counting lattice points in well-rounded families of subsets. This gives a
sharper analog in positive characteristic of a result of Nevo and the first author
for the equidistribution of the primitive lattice points in \ZZ2 .
acknowledgement: "The authors warmly thank Amos Nevo for having presented the authors
to each other during\r\na beautiful conference in Goa in February 2016, where the
idea of this paper was born. The\r\nfirst author thanks the IHES for two post-doctoral
years when most of this paper was discussed,\r\nand the Topology team in Orsay for
financial support at the final stage. The first author was\r\nsupported by the EPRSC
EP/P026710/1 grant. Finally, we warmly thank the referee for many\r\nvery helpful
comments that have improved the readability of this paper."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Tal
full_name: Horesh, Tal
id: C8B7BF48-8D81-11E9-BCA9-F536E6697425
last_name: Horesh
- first_name: Frédéric
full_name: Paulin, Frédéric
last_name: Paulin
citation:
ama: Horesh T, Paulin F. Effective equidistribution of lattice points in positive
characteristic. Journal de Theorie des Nombres de Bordeaux. 2022;34(3):679-703.
doi:10.5802/JTNB.1222
apa: Horesh, T., & Paulin, F. (2022). Effective equidistribution of lattice
points in positive characteristic. Journal de Theorie Des Nombres de Bordeaux.
Université de Bordeaux. https://doi.org/10.5802/JTNB.1222
chicago: Horesh, Tal, and Frédéric Paulin. “Effective Equidistribution of Lattice
Points in Positive Characteristic.” Journal de Theorie Des Nombres de Bordeaux.
Université de Bordeaux, 2022. https://doi.org/10.5802/JTNB.1222.
ieee: T. Horesh and F. Paulin, “Effective equidistribution of lattice points in
positive characteristic,” Journal de Theorie des Nombres de Bordeaux, vol.
34, no. 3. Université de Bordeaux, pp. 679–703, 2022.
ista: Horesh T, Paulin F. 2022. Effective equidistribution of lattice points in
positive characteristic. Journal de Theorie des Nombres de Bordeaux. 34(3), 679–703.
mla: Horesh, Tal, and Frédéric Paulin. “Effective Equidistribution of Lattice Points
in Positive Characteristic.” Journal de Theorie Des Nombres de Bordeaux,
vol. 34, no. 3, Université de Bordeaux, 2022, pp. 679–703, doi:10.5802/JTNB.1222.
short: T. Horesh, F. Paulin, Journal de Theorie Des Nombres de Bordeaux 34 (2022)
679–703.
corr_author: '1'
date_created: 2023-02-26T23:01:02Z
date_published: 2022-01-27T00:00:00Z
date_updated: 2025-05-14T11:23:08Z
day: '27'
ddc:
- '510'
department:
- _id: TiBr
doi: 10.5802/JTNB.1222
external_id:
arxiv:
- '2001.01534'
isi:
- '000926504300003'
file:
- access_level: open_access
checksum: 08f28fded270251f568f610cf5166d69
content_type: application/pdf
creator: dernst
date_created: 2023-02-27T09:10:13Z
date_updated: 2023-02-27T09:10:13Z
file_id: '12689'
file_name: 2023_JourTheorieNombreBordeaux_Horesh.pdf
file_size: 870468
relation: main_file
success: 1
file_date_updated: 2023-02-27T09:10:13Z
has_accepted_license: '1'
intvolume: ' 34'
isi: 1
issue: '3'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '01'
oa: 1
oa_version: Published Version
page: 679-703
publication: Journal de Theorie des Nombres de Bordeaux
publication_identifier:
eissn:
- 2118-8572
issn:
- 1246-7405
publication_status: published
publisher: Université de Bordeaux
quality_controlled: '1'
scopus_import: '1'
status: public
title: Effective equidistribution of lattice points in positive characteristic
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: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2022'
...
---
_id: '12775'
abstract:
- lang: eng
text: "We consider the problem of approximating the reachability probabilities in
Markov decision processes (MDP) with uncountable (continuous) state and action
spaces. While there are algorithms that, for special classes of such MDP, provide
a sequence of approximations converging to the true value in the limit, our aim
is to obtain an algorithm with guarantees on the precision of the approximation.\r\nAs
this problem is undecidable in general, assumptions on the MDP are necessary.
Our main contribution is to identify sufficient assumptions that are as weak as
possible, thus approaching the \"boundary\" of which systems can be correctly
and reliably analyzed. To this end, we also argue why each of our assumptions
is necessary for algorithms based on processing finitely many observations.\r\nWe
present two solution variants. The first one provides converging lower bounds
under weaker assumptions than typical ones from previous works concerned with
guarantees. The second one then utilizes stronger assumptions to additionally
provide converging upper bounds. Altogether, we obtain an anytime algorithm, i.e.
yielding a sequence of approximants with known and iteratively improving precision,
converging to the true value in the limit. Besides, due to the generality of our
assumptions, our algorithms are very general templates, readily allowing for various
heuristics from literature in contrast to, e.g., a specific discretization algorithm.
Our theoretical contribution thus paves the way for future practical improvements
without sacrificing correctness guarantees."
acknowledgement: "Kush Grover: The author has been supported by the DFG research training
group GRK\r\n2428 ConVeY.\r\nMaximilian Weininger: The author has been partially
supported by DFG projects 383882557\r\nStatistical Unbounded Verification (SUV)
and 427755713 Group-By Objectives in Probabilistic\r\nVerification (GOPro)"
alternative_title:
- LIPIcs
article_number: '11'
article_processing_charge: No
arxiv: 1
author:
- first_name: Kush
full_name: Grover, Kush
last_name: Grover
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
- first_name: Tobias
full_name: Meggendorfer, Tobias
id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
last_name: Meggendorfer
orcid: 0000-0002-1712-2165
- first_name: Maimilian
full_name: Weininger, Maimilian
last_name: Weininger
citation:
ama: 'Grover K, Kretinsky J, Meggendorfer T, Weininger M. Anytime guarantees for
reachability in uncountable Markov decision processes. In: 33rd International
Conference on Concurrency Theory . Vol 243. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2022. doi:10.4230/LIPIcs.CONCUR.2022.11'
apa: 'Grover, K., Kretinsky, J., Meggendorfer, T., & Weininger, M. (2022). Anytime
guarantees for reachability in uncountable Markov decision processes. In 33rd
International Conference on Concurrency Theory (Vol. 243). Warsaw, Poland:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2022.11'
chicago: Grover, Kush, Jan Kretinsky, Tobias Meggendorfer, and Maimilian Weininger.
“Anytime Guarantees for Reachability in Uncountable Markov Decision Processes.”
In 33rd International Conference on Concurrency Theory , Vol. 243. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.CONCUR.2022.11.
ieee: K. Grover, J. Kretinsky, T. Meggendorfer, and M. Weininger, “Anytime guarantees
for reachability in uncountable Markov decision processes,” in 33rd International
Conference on Concurrency Theory , Warsaw, Poland, 2022, vol. 243.
ista: 'Grover K, Kretinsky J, Meggendorfer T, Weininger M. 2022. Anytime guarantees
for reachability in uncountable Markov decision processes. 33rd International
Conference on Concurrency Theory . CONCUR: Conference on Concurrency Theory, LIPIcs,
vol. 243, 11.'
mla: Grover, Kush, et al. “Anytime Guarantees for Reachability in Uncountable Markov
Decision Processes.” 33rd International Conference on Concurrency Theory ,
vol. 243, 11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:10.4230/LIPIcs.CONCUR.2022.11.
short: K. Grover, J. Kretinsky, T. Meggendorfer, M. Weininger, in:, 33rd International
Conference on Concurrency Theory , Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022.
conference:
end_date: 2022-09-16
location: Warsaw, Poland
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2022-09-13
corr_author: '1'
date_created: 2023-03-28T08:09:32Z
date_published: 2022-09-15T00:00:00Z
date_updated: 2024-10-09T21:04:52Z
day: '15'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.CONCUR.2022.11
external_id:
arxiv:
- '2008.04824'
file:
- access_level: open_access
checksum: e282e43d3ae0ba6e067b72f4583e13c0
content_type: application/pdf
creator: dernst
date_created: 2023-09-26T10:43:15Z
date_updated: 2023-09-26T10:43:15Z
file_id: '14372'
file_name: 2022_LIPIcS_Grover.pdf
file_size: 960036
relation: main_file
success: 1
file_date_updated: 2023-09-26T10:43:15Z
has_accepted_license: '1'
intvolume: ' 243'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
publication: '33rd International Conference on Concurrency Theory '
publication_identifier:
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Anytime guarantees for reachability in uncountable Markov decision processes
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: 243
year: '2022'
...
---
_id: '12776'
abstract:
- lang: eng
text: An improved asymptotic formula is established for the number of rational points
of bounded height on the split smooth del Pezzo surface of degree 5. The proof
uses the five conic bundle structures on the surface.
acknowledgement: This work was begun while the author was participating in the programme
on "Diophantine equations" at the Hausdorff Research Institute for Mathematics in
Bonn in 2009. The hospitality and financial support of the institute is gratefully
acknowledged. The idea of using conic bundles to study the split del Pezzo surface
of degree 5 was explained to the author by Professor Salberger. The author is very
grateful to him for his input into this project and also to Shuntaro Yamagishi for
many useful comments on an earlier version of this manuscript. While working on
this paper the author was supported by FWF grant P32428-N35.
article_processing_charge: No
article_type: original
author:
- first_name: Timothy D
full_name: Browning, Timothy D
id: 35827D50-F248-11E8-B48F-1D18A9856A87
last_name: Browning
orcid: 0000-0002-8314-0177
citation:
ama: Browning TD. Revisiting the Manin–Peyre conjecture for the split del Pezzo
surface of degree 5. New York Journal of Mathematics. 2022;28:1193-1229.
apa: Browning, T. D. (2022). Revisiting the Manin–Peyre conjecture for the split
del Pezzo surface of degree 5. New York Journal of Mathematics. State University
of New York.
chicago: Browning, Timothy D. “Revisiting the Manin–Peyre Conjecture for the Split
Del Pezzo Surface of Degree 5.” New York Journal of Mathematics. State
University of New York, 2022.
ieee: T. D. Browning, “Revisiting the Manin–Peyre conjecture for the split del Pezzo
surface of degree 5,” New York Journal of Mathematics, vol. 28. State University
of New York, pp. 1193–1229, 2022.
ista: Browning TD. 2022. Revisiting the Manin–Peyre conjecture for the split del
Pezzo surface of degree 5. New York Journal of Mathematics. 28, 1193–1229.
mla: Browning, Timothy D. “Revisiting the Manin–Peyre Conjecture for the Split Del
Pezzo Surface of Degree 5.” New York Journal of Mathematics, vol. 28, State
University of New York, 2022, pp. 1193–229.
short: T.D. Browning, New York Journal of Mathematics 28 (2022) 1193–1229.
corr_author: '1'
date_created: 2023-03-28T09:21:09Z
date_published: 2022-08-24T00:00:00Z
date_updated: 2025-04-15T07:39:01Z
day: '24'
ddc:
- '510'
department:
- _id: TiBr
file:
- access_level: open_access
checksum: c01e8291794a1bdb7416aa103cb68ef8
content_type: application/pdf
creator: dernst
date_created: 2023-03-30T07:09:35Z
date_updated: 2023-03-30T07:09:35Z
file_id: '12778'
file_name: 2022_NYJM_Browning.pdf
file_size: 897267
relation: main_file
success: 1
file_date_updated: 2023-03-30T07:09:35Z
has_accepted_license: '1'
intvolume: ' 28'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: 1193 - 1229
project:
- _id: 26AEDAB2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P32428
name: New frontiers of the Manin conjecture
publication: New York Journal of Mathematics
publication_identifier:
issn:
- 1076-9803
publication_status: published
publisher: State University of New York
quality_controlled: '1'
status: public
title: Revisiting the Manin–Peyre conjecture for the split del Pezzo surface of degree
5
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: 28
year: '2022'
...
---
_id: '12793'
abstract:
- lang: eng
text: "Let F be a global function field with constant field Fq. Let G be a reductive
group over Fq. We establish a variant of Arthur's truncated kernel for G and for
its Lie algebra which generalizes Arthur's original construction. We establish
a coarse geometric expansion for our variant truncation.\r\nAs applications, we
consider some existence and uniqueness problems of some cuspidal automorphic representations
for the functions field of the projective line P1Fq with two points of ramifications."
acknowledgement: 'I’d like to thank Prof. Chaudouard for introducing me to this area.
I’d like to thank Prof. Harris for asking me the question that makes Section 10
possible. I’m grateful for the support of Prof. Hausel and IST Austria. The author
was funded by an ISTplus fellowship: 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. 754411.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Hongjie
full_name: Yu, Hongjie
id: 3D7DD9BE-F248-11E8-B48F-1D18A9856A87
last_name: Yu
orcid: 0000-0001-5128-7126
citation:
ama: Yu H. A coarse geometric expansion of a variant of Arthur’s truncated traces
and some applications. Pacific Journal of Mathematics. 2022;321(1):193-237.
doi:10.2140/pjm.2022.321.193
apa: Yu, H. (2022). A coarse geometric expansion of a variant of Arthur’s truncated
traces and some applications. Pacific Journal of Mathematics. Mathematical
Sciences Publishers. https://doi.org/10.2140/pjm.2022.321.193
chicago: Yu, Hongjie. “ A Coarse Geometric Expansion of a Variant of Arthur’s Truncated
Traces and Some Applications.” Pacific Journal of Mathematics. Mathematical
Sciences Publishers, 2022. https://doi.org/10.2140/pjm.2022.321.193.
ieee: H. Yu, “ A coarse geometric expansion of a variant of Arthur’s truncated traces
and some applications,” Pacific Journal of Mathematics, vol. 321, no. 1.
Mathematical Sciences Publishers, pp. 193–237, 2022.
ista: Yu H. 2022. A coarse geometric expansion of a variant of Arthur’s truncated
traces and some applications. Pacific Journal of Mathematics. 321(1), 193–237.
mla: Yu, Hongjie. “ A Coarse Geometric Expansion of a Variant of Arthur’s Truncated
Traces and Some Applications.” Pacific Journal of Mathematics, vol. 321,
no. 1, Mathematical Sciences Publishers, 2022, pp. 193–237, doi:10.2140/pjm.2022.321.193.
short: H. Yu, Pacific Journal of Mathematics 321 (2022) 193–237.
corr_author: '1'
date_created: 2023-04-02T22:01:11Z
date_published: 2022-08-29T00:00:00Z
date_updated: 2025-04-14T07:44:01Z
day: '29'
department:
- _id: TaHa
doi: 10.2140/pjm.2022.321.193
ec_funded: 1
external_id:
arxiv:
- '2109.10245'
isi:
- '000954466300006'
intvolume: ' 321'
isi: 1
issue: '1'
keyword:
- Arthur–Selberg trace formula
- cuspidal automorphic representations
- global function fields
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2109.10245
month: '08'
oa: 1
oa_version: Preprint
page: 193-237
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Pacific Journal of Mathematics
publication_identifier:
eissn:
- 1945-5844
issn:
- 0030-8730
publication_status: published
publisher: Mathematical Sciences Publishers
quality_controlled: '1'
scopus_import: '1'
status: public
title: ' A coarse geometric expansion of a variant of Arthur''s truncated traces and
some applications'
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 321
year: '2022'
...