---
_id: '9580'
abstract:
- lang: eng
text: An r-cut of a k-uniform hypergraph H is a partition of the vertex set of H
into r parts and the size of the cut is the number of edges which have a vertex
in each part. A classical result of Edwards says that every m-edge graph has a
2-cut of size m/2+Ω)(m−−√) and this is best possible. That is, there exist cuts
which exceed the expected size of a random cut by some multiple of the standard
deviation. We study analogues of this and related results in hypergraphs. First,
we observe that similarly to graphs, every m-edge k-uniform hypergraph has an
r-cut whose size is Ω(m−−√) larger than the expected size of a random r-cut. Moreover,
in the case where k = 3 and r = 2 this bound is best possible and is attained
by Steiner triple systems. Surprisingly, for all other cases (that is, if k ≥
4 or r ≥ 3), we show that every m-edge k-uniform hypergraph has an r-cut whose
size is Ω(m5/9) larger than the expected size of a random r-cut. This is a significant
difference in behaviour, since the amount by which the size of the largest cut
exceeds the expected size of a random cut is now considerably larger than the
standard deviation.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: David
full_name: Conlon, David
last_name: Conlon
- first_name: Jacob
full_name: Fox, Jacob
last_name: Fox
- first_name: Matthew Alan
full_name: Kwan, Matthew Alan
id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
last_name: Kwan
orcid: 0000-0002-4003-7567
- first_name: Benny
full_name: Sudakov, Benny
last_name: Sudakov
citation:
ama: Conlon D, Fox J, Kwan MA, Sudakov B. Hypergraph cuts above the average. Israel
Journal of Mathematics. 2019;233(1):67-111. doi:10.1007/s11856-019-1897-z
apa: Conlon, D., Fox, J., Kwan, M. A., & Sudakov, B. (2019). Hypergraph cuts
above the average. Israel Journal of Mathematics. Springer. https://doi.org/10.1007/s11856-019-1897-z
chicago: Conlon, David, Jacob Fox, Matthew Alan Kwan, and Benny Sudakov. “Hypergraph
Cuts above the Average.” Israel Journal of Mathematics. Springer, 2019.
https://doi.org/10.1007/s11856-019-1897-z.
ieee: D. Conlon, J. Fox, M. A. Kwan, and B. Sudakov, “Hypergraph cuts above the
average,” Israel Journal of Mathematics, vol. 233, no. 1. Springer, pp.
67–111, 2019.
ista: Conlon D, Fox J, Kwan MA, Sudakov B. 2019. Hypergraph cuts above the average.
Israel Journal of Mathematics. 233(1), 67–111.
mla: Conlon, David, et al. “Hypergraph Cuts above the Average.” Israel Journal
of Mathematics, vol. 233, no. 1, Springer, 2019, pp. 67–111, doi:10.1007/s11856-019-1897-z.
short: D. Conlon, J. Fox, M.A. Kwan, B. Sudakov, Israel Journal of Mathematics 233
(2019) 67–111.
date_created: 2021-06-21T13:36:02Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2023-02-23T14:01:41Z
day: '01'
doi: 10.1007/s11856-019-1897-z
extern: '1'
external_id:
arxiv:
- '1803.08462'
intvolume: ' 233'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1803.08462
month: '08'
oa: 1
oa_version: Preprint
page: 67-111
publication: Israel Journal of Mathematics
publication_identifier:
eissn:
- 1565-8511
issn:
- 0021-2172
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Hypergraph cuts above the average
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 233
year: '2019'
...
---
_id: '9806'
abstract:
- lang: eng
text: 1. Hosts can alter their strategy towards pathogens during their lifetime,
i.e., they can show phenotypic plasticity in immunity or life history. Immune
priming is one such example, where a previous encounter with a pathogen confers
enhanced protection upon secondary challenge, resulting in reduced pathogen load
(i.e. resistance) and improved host survival. However, an initial encounter might
also enhance tolerance, particularly to less virulent opportunistic pathogens
that establish persistent infections. In this scenario, individuals are better
able to reduce the negative fitness consequences that result from a high pathogen
load. Finally, previous exposure may also lead to life history adjustments, such
as terminal investment into reproduction. 2. Using different Drosophila melanogaster
host genotypes and two bacterial pathogens, Lactococcus lactis and Pseudomonas
entomophila, we tested if previous exposure results in resistance or tolerance
and whether it modifies immune gene expression during an acute-phase infection
(one day post-challenge). We then asked if previous pathogen exposure affects
chronic-phase pathogen persistence and longer-term survival (28 days post-challenge).
3. We predicted that previous exposure would increase host resistance to an early
stage bacterial infection while it might come at a cost to host fecundity tolerance.
We reasoned that resistance would be due in part to stronger immune gene expression
after challenge. We expected that previous exposure would improve long-term survival,
that it would reduce infection persistence, and we expected to find genetic variation
in these responses. 4. We found that previous exposure to P. entomophila weakened
host resistance to a second infection independent of genotype and had no effect
on immune gene expression. Fecundity tolerance showed genotypic variation but
was not influenced by previous exposure. However, L. lactis persisted as a chronic
infection, whereas survivors cleared the more pathogenic P. entomophila infection.
5. To our knowledge, this is the first study that addresses host tolerance to
bacteria in relation to previous exposure, taking a multi-faceted approach to
address the topic. Our results suggest that previous exposure comes with transient
costs to resistance during the early stage of infection in this host-pathogen
system and that infection persistence may be bacterium-specific.
article_processing_charge: No
author:
- first_name: Megan
full_name: Kutzer, Megan
id: 29D0B332-F248-11E8-B48F-1D18A9856A87
last_name: Kutzer
orcid: 0000-0002-8696-6978
- first_name: Joachim
full_name: Kurtz, Joachim
last_name: Kurtz
- first_name: Sophie A.O.
full_name: Armitage, Sophie A.O.
last_name: Armitage
citation:
ama: 'Kutzer M, Kurtz J, Armitage SAO. Data from: A multi-faceted approach testing
the effects of previous bacterial exposure on resistance and tolerance. 2019.
doi:10.5061/dryad.9kj41f0'
apa: 'Kutzer, M., Kurtz, J., & Armitage, S. A. O. (2019). Data from: A multi-faceted
approach testing the effects of previous bacterial exposure on resistance and
tolerance. Dryad. https://doi.org/10.5061/dryad.9kj41f0'
chicago: 'Kutzer, Megan, Joachim Kurtz, and Sophie A.O. Armitage. “Data from: A
Multi-Faceted Approach Testing the Effects of Previous Bacterial Exposure on Resistance
and Tolerance.” Dryad, 2019. https://doi.org/10.5061/dryad.9kj41f0.'
ieee: 'M. Kutzer, J. Kurtz, and S. A. O. Armitage, “Data from: A multi-faceted approach
testing the effects of previous bacterial exposure on resistance and tolerance.”
Dryad, 2019.'
ista: 'Kutzer M, Kurtz J, Armitage SAO. 2019. Data from: A multi-faceted approach
testing the effects of previous bacterial exposure on resistance and tolerance,
Dryad, 10.5061/dryad.9kj41f0.'
mla: 'Kutzer, Megan, et al. Data from: A Multi-Faceted Approach Testing the Effects
of Previous Bacterial Exposure on Resistance and Tolerance. Dryad, 2019, doi:10.5061/dryad.9kj41f0.'
short: M. Kutzer, J. Kurtz, S.A.O. Armitage, (2019).
date_created: 2021-08-06T12:06:40Z
date_published: 2019-02-05T00:00:00Z
date_updated: 2025-07-10T11:53:11Z
day: '05'
department:
- _id: SyCr
doi: 10.5061/dryad.9kj41f0
main_file_link:
- open_access: '1'
url: https://doi.org/10.5061/dryad.9kj41f0
month: '02'
oa: 1
oa_version: Published Version
publisher: Dryad
related_material:
record:
- id: '6105'
relation: used_in_publication
status: public
status: public
title: 'Data from: A multi-faceted approach testing the effects of previous bacterial
exposure on resistance and tolerance'
type: research_data_reference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
year: '2019'
...
---
_id: '6428'
abstract:
- lang: eng
text: 'Safety and security are major concerns in the development of Cyber-Physical
Systems (CPS). Signal temporal logic (STL) was proposedas a language to specify
and monitor the correctness of CPS relativeto formalized requirements. Incorporating
STL into a developmentprocess enables designers to automatically monitor and diagnosetraces,
compute robustness estimates based on requirements, andperform requirement falsification,
leading to productivity gains inverification and validation activities; however,
in its current formSTL is agnostic to the input/output classification of signals,
andthis negatively impacts the relevance of the analysis results.In this paper
we propose to make the interface explicit in theSTL language by introducing input/output
signal declarations. Wethen define new measures of input vacuity and output robustnessthat
better reflect the nature of the system and the specification in-tent. The resulting
framework, which we call interface-aware signaltemporal logic (IA-STL), aids verification
and validation activities.We demonstrate the benefits of IA-STL on several CPS
analysisactivities: (1) robustness-driven sensitivity analysis, (2) falsificationand
(3) fault localization. We describe an implementation of our en-hancement to STL
and associated notions of robustness and vacuityin a prototype extension of Breach,
a MATLAB®/Simulink®toolboxfor CPS verification and validation. We explore these
methodologi-cal improvements and evaluate our results on two examples fromthe
automotive domain: a benchmark powertrain control systemand a hydrogen fuel cell
system.'
article_processing_charge: No
author:
- first_name: Thomas
full_name: Ferrere, Thomas
id: 40960E6E-F248-11E8-B48F-1D18A9856A87
last_name: Ferrere
orcid: 0000-0001-5199-3143
- first_name: Dejan
full_name: Nickovic, Dejan
id: 41BCEE5C-F248-11E8-B48F-1D18A9856A87
last_name: Nickovic
- first_name: Alexandre
full_name: Donzé, Alexandre
last_name: Donzé
- first_name: Hisahiro
full_name: Ito, Hisahiro
last_name: Ito
- first_name: James
full_name: Kapinski, James
last_name: Kapinski
citation:
ama: 'Ferrere T, Nickovic D, Donzé A, Ito H, Kapinski J. Interface-aware signal
temporal logic. In: Proceedings of the 2019 22nd ACM International Conference
on Hybrid Systems: Computation and Control. ACM; 2019:57-66. doi:10.1145/3302504.3311800'
apa: 'Ferrere, T., Nickovic, D., Donzé, A., Ito, H., & Kapinski, J. (2019).
Interface-aware signal temporal logic. In Proceedings of the 2019 22nd ACM
International Conference on Hybrid Systems: Computation and Control (pp. 57–66).
Montreal, Canada: ACM. https://doi.org/10.1145/3302504.3311800'
chicago: 'Ferrere, Thomas, Dejan Nickovic, Alexandre Donzé, Hisahiro Ito, and James
Kapinski. “Interface-Aware Signal Temporal Logic.” In Proceedings of the 2019
22nd ACM International Conference on Hybrid Systems: Computation and Control,
57–66. ACM, 2019. https://doi.org/10.1145/3302504.3311800.'
ieee: 'T. Ferrere, D. Nickovic, A. Donzé, H. Ito, and J. Kapinski, “Interface-aware
signal temporal logic,” in Proceedings of the 2019 22nd ACM International Conference
on Hybrid Systems: Computation and Control, Montreal, Canada, 2019, pp. 57–66.'
ista: 'Ferrere T, Nickovic D, Donzé A, Ito H, Kapinski J. 2019. Interface-aware
signal temporal logic. Proceedings of the 2019 22nd ACM International Conference
on Hybrid Systems: Computation and Control. HSCC: Hybrid Systems - Computation
and Control, 57–66.'
mla: 'Ferrere, Thomas, et al. “Interface-Aware Signal Temporal Logic.” Proceedings
of the 2019 22nd ACM International Conference on Hybrid Systems: Computation and
Control, ACM, 2019, pp. 57–66, doi:10.1145/3302504.3311800.'
short: 'T. Ferrere, D. Nickovic, A. Donzé, H. Ito, J. Kapinski, in:, Proceedings
of the 2019 22nd ACM International Conference on Hybrid Systems: Computation and
Control, ACM, 2019, pp. 57–66.'
conference:
end_date: 2019-04-18
location: Montreal, Canada
name: 'HSCC: Hybrid Systems - Computation and Control'
start_date: 2019-04-16
date_created: 2019-05-13T08:13:46Z
date_published: 2019-04-16T00:00:00Z
date_updated: 2025-07-10T11:53:22Z
day: '16'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1145/3302504.3311800
external_id:
isi:
- '000516713900007'
file:
- access_level: open_access
checksum: b8e967081e051d1c55ca5d18fb187890
content_type: application/pdf
creator: dernst
date_created: 2020-10-08T17:25:45Z
date_updated: 2020-10-08T17:25:45Z
file_id: '8633'
file_name: 2019_ACM_Ferrere.pdf
file_size: 1055421
relation: main_file
success: 1
file_date_updated: 2020-10-08T17:25:45Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '04'
oa: 1
oa_version: Submitted Version
page: 57-66
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
publication: 'Proceedings of the 2019 22nd ACM International Conference on Hybrid
Systems: Computation and Control'
publication_identifier:
isbn:
- '9781450362825'
publication_status: published
publisher: ACM
quality_controlled: '1'
scopus_import: '1'
status: public
title: Interface-aware signal temporal logic
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '6430'
abstract:
- lang: eng
text: "A proxy re-encryption (PRE) scheme is a public-key encryption scheme that
allows the holder of a key pk to derive a re-encryption key for any other key
\U0001D45D\U0001D458′. This re-encryption key lets anyone transform ciphertexts
under pk into ciphertexts under \U0001D45D\U0001D458′ without having to know the
underlying message, while transformations from \U0001D45D\U0001D458′ to pk should
not be possible (unidirectional). Security is defined in a multi-user setting
against an adversary that gets the users’ public keys and can ask for re-encryption
keys and can corrupt users by requesting their secret keys. Any ciphertext that
the adversary cannot trivially decrypt given the obtained secret and re-encryption
keys should be secure.\r\n\r\nAll existing security proofs for PRE only show selective
security, where the adversary must first declare the users it wants to corrupt.
This can be lifted to more meaningful adaptive security by guessing the set of
corrupted users among the n users, which loses a factor exponential in Open image
in new window , rendering the result meaningless already for moderate Open image
in new window .\r\n\r\nJafargholi et al. (CRYPTO’17) proposed a framework that
in some cases allows to give adaptive security proofs for schemes which were previously
only known to be selectively secure, while avoiding the exponential loss that
results from guessing the adaptive choices made by an adversary. We apply their
framework to PREs that satisfy some natural additional properties. Concretely,
we give a more fine-grained reduction for several unidirectional PREs, proving
adaptive security at a much smaller loss. The loss depends on the graph of users
whose edges represent the re-encryption keys queried by the adversary. For trees
and chains the loss is quasi-polynomial in the size and for general graphs it
is exponential in their depth and indegree (instead of their size as for previous
reductions). Fortunately, trees and low-depth graphs cover many, if not most,
interesting applications.\r\n\r\nOur results apply e.g. to the bilinear-map based
PRE schemes by Ateniese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme
(STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14)."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
- 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: 'Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. Adaptively secure proxy
re-encryption. In: Vol 11443. Springer Nature; 2019:317-346. doi:10.1007/978-3-030-17259-6_11'
apa: 'Fuchsbauer, G., Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2019).
Adaptively secure proxy re-encryption (Vol. 11443, pp. 317–346). Presented at
the PKC: Public-Key Cryptograhy, Beijing, China: Springer Nature. https://doi.org/10.1007/978-3-030-17259-6_11'
chicago: Fuchsbauer, Georg, Chethan Kamath Hosdurg, Karen Klein, and Krzysztof Z
Pietrzak. “Adaptively Secure Proxy Re-Encryption,” 11443:317–46. Springer Nature,
2019. https://doi.org/10.1007/978-3-030-17259-6_11.
ieee: 'G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “Adaptively
secure proxy re-encryption,” presented at the PKC: Public-Key Cryptograhy, Beijing,
China, 2019, vol. 11443, pp. 317–346.'
ista: 'Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. 2019. Adaptively secure
proxy re-encryption. PKC: Public-Key Cryptograhy, LNCS, vol. 11443, 317–346.'
mla: Fuchsbauer, Georg, et al. Adaptively Secure Proxy Re-Encryption. Vol.
11443, Springer Nature, 2019, pp. 317–46, doi:10.1007/978-3-030-17259-6_11.
short: G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, Springer
Nature, 2019, pp. 317–346.
conference:
end_date: 2019-04-17
location: Beijing, China
name: 'PKC: Public-Key Cryptograhy'
start_date: 2019-04-14
date_created: 2019-05-13T08:13:46Z
date_published: 2019-04-06T00:00:00Z
date_updated: 2026-04-16T09:52:04Z
day: '06'
department:
- _id: KrPi
doi: 10.1007/978-3-030-17259-6_11
ec_funded: 1
external_id:
isi:
- '001299215500011'
intvolume: ' 11443'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2018/426
month: '04'
oa: 1
oa_version: Preprint
page: 317-346
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030172589'
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: Adaptively secure proxy re-encryption
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 11443
year: '2019'
...
---
_id: '6462'
abstract:
- lang: eng
text: A controller is a device that interacts with a plant. At each time point,it
reads the plant’s state and issues commands with the goal that the plant oper-ates
optimally. Constructing optimal controllers is a fundamental and challengingproblem.
Machine learning techniques have recently been successfully applied totrain controllers,
yet they have limitations. Learned controllers are monolithic andhard to reason
about. In particular, it is difficult to add features without retraining,to guarantee
any level of performance, and to achieve acceptable performancewhen encountering
untrained scenarios. These limitations can be addressed bydeploying quantitative
run-timeshieldsthat serve as a proxy for the controller.At each time point, the
shield reads the command issued by the controller andmay choose to alter it before
passing it on to the plant. We show how optimalshields that interfere as little
as possible while guaranteeing a desired level ofcontroller performance, can be
generated systematically and automatically usingreactive synthesis. First, we abstract the plant by building a stochastic model.Second,
we consider the learned controller to be a black box. Third, we mea-surecontroller
performanceandshield interferenceby two quantitative run-timemeasures that are
formally defined using weighted automata. Then, the problemof constructing a shield
that guarantees maximal performance with minimal inter-ference is the problem
of finding an optimal strategy in a stochastic2-player game“controller versus
shield” played on the abstract state space of the plant with aquantitative objective
obtained from combining the performance and interferencemeasures. We illustrate
the effectiveness of our approach by automatically con-structing lightweight shields
for learned traffic-light controllers in various roadnetworks. The shields we
generate avoid liveness bugs, improve controller per-formance in untrained and
changing traffic situations, and add features to learnedcontrollers, such as giving
priority to emergency vehicles.
alternative_title:
- LNCS
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: Roderick
full_name: Bloem, Roderick
last_name: Bloem
- 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
- first_name: Bettina
full_name: Konighofer, Bettina
last_name: Konighofer
- first_name: Stefan
full_name: Pranger, Stefan
last_name: Pranger
citation:
ama: 'Avni G, Bloem R, Chatterjee K, Henzinger TA, Konighofer B, Pranger S. Run-time
optimization for learned controllers through quantitative games. In: 31st International
Conference on Computer-Aided Verification. Vol 11561. Springer; 2019:630-649.
doi:10.1007/978-3-030-25540-4_36'
apa: 'Avni, G., Bloem, R., Chatterjee, K., Henzinger, T. A., Konighofer, B., &
Pranger, S. (2019). Run-time optimization for learned controllers through quantitative
games. In 31st International Conference on Computer-Aided Verification
(Vol. 11561, pp. 630–649). New York, NY, United States: Springer. https://doi.org/10.1007/978-3-030-25540-4_36'
chicago: Avni, Guy, Roderick Bloem, Krishnendu Chatterjee, Thomas A Henzinger, Bettina
Konighofer, and Stefan Pranger. “Run-Time Optimization for Learned Controllers
through Quantitative Games.” In 31st International Conference on Computer-Aided
Verification, 11561:630–49. Springer, 2019. https://doi.org/10.1007/978-3-030-25540-4_36.
ieee: G. Avni, R. Bloem, K. Chatterjee, T. A. Henzinger, B. Konighofer, and S. Pranger,
“Run-time optimization for learned controllers through quantitative games,” in
31st International Conference on Computer-Aided Verification, New York,
NY, United States, 2019, vol. 11561, pp. 630–649.
ista: 'Avni G, Bloem R, Chatterjee K, Henzinger TA, Konighofer B, Pranger S. 2019.
Run-time optimization for learned controllers through quantitative games. 31st
International Conference on Computer-Aided Verification. CAV: Computer Aided Verification,
LNCS, vol. 11561, 630–649.'
mla: Avni, Guy, et al. “Run-Time Optimization for Learned Controllers through Quantitative
Games.” 31st International Conference on Computer-Aided Verification, vol.
11561, Springer, 2019, pp. 630–49, doi:10.1007/978-3-030-25540-4_36.
short: G. Avni, R. Bloem, K. Chatterjee, T.A. Henzinger, B. Konighofer, S. Pranger,
in:, 31st International Conference on Computer-Aided Verification, Springer, 2019,
pp. 630–649.
conference:
end_date: 2019-07-18
location: New York, NY, United States
name: 'CAV: Computer Aided Verification'
start_date: 2019-07-13
corr_author: '1'
date_created: 2019-05-16T11:22:30Z
date_published: 2019-07-12T00:00:00Z
date_updated: 2025-04-15T06:26:05Z
day: '12'
ddc:
- '000'
department:
- _id: ToHe
- _id: KrCh
doi: 10.1007/978-3-030-25540-4_36
external_id:
isi:
- '000491468000036'
file:
- access_level: open_access
checksum: c231579f2485c6fd4df17c9443a4d80b
content_type: application/pdf
creator: dernst
date_created: 2019-08-14T09:35:24Z
date_updated: 2020-07-14T12:47:31Z
file_id: '6816'
file_name: 2019_CAV_Avni.pdf
file_size: 659766
relation: main_file
file_date_updated: 2020-07-14T12:47:31Z
has_accepted_license: '1'
intvolume: ' 11561'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 630-649
project:
- _id: 264B3912-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02369
name: Formal Methods meets Algorithmic Game Theory
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication: 31st International Conference on Computer-Aided Verification
publication_identifier:
isbn:
- '9783030255398'
issn:
- 0302-9743
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Run-time optimization for learned controllers through quantitative 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: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 11561
year: '2019'
...
---
OA_place: publisher
_id: '6473'
abstract:
- lang: eng
text: "Single cells are constantly interacting with their environment and each other,
more importantly, the accurate perception of environmental cues is crucial for
growth, survival, and reproduction. This communication between cells and their
environment can be formalized in mathematical terms and be quantified as the information
flow between them, as prescribed by information theory. \r\nThe recent availability
of real–time dynamical patterns of signaling molecules in single cells has allowed
us to identify encoding about the identity of the environment in the time–series.
However, efficient estimation of the information transmitted by these signals
has been a data–analysis challenge due to the high dimensionality of the trajectories
and the limited number of samples. In the first part of this thesis, we develop
and evaluate decoding–based estimation methods to lower bound the mutual information
and derive model–based precise information estimates for biological reaction networks
governed by the chemical master equation. This is followed by applying the decoding-based
methods to study the intracellular representation of extracellular changes in
budding yeast, by observing the transient dynamics of nuclear translocation of
10 transcription factors in response to 3 stress conditions. Additionally, we
apply these estimators to previously published data on ERK and Ca2+ signaling
and yeast stress response. We argue that this single cell decoding-based measure
of information provides an unbiased, quantitative and interpretable measure for
the fidelity of biological signaling processes. \r\nFinally, in the last section,
we deal with gene regulation which is primarily controlled by transcription factors
(TFs) that bind to the DNA to activate gene expression. The possibility that non-cognate
TFs activate transcription diminishes the accuracy of regulation with potentially
disastrous effects for the cell. This ’crosstalk’ acts as a previously unexplored
source of noise in biochemical networks and puts a strong constraint on their
performance. To mitigate erroneous initiation we propose an out of equilibrium
scheme that implements kinetic proofreading. We show that such architectures are
favored over their equilibrium counterparts for complex organisms despite introducing
noise in gene expression. "
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Sarah A
full_name: Cepeda Humerez, Sarah A
id: 3DEE19A4-F248-11E8-B48F-1D18A9856A87
last_name: Cepeda Humerez
citation:
ama: Cepeda Humerez SA. Estimating information flow in single cells. 2019. doi:10.15479/AT:ISTA:6473
apa: Cepeda Humerez, S. A. (2019). Estimating information flow in single cells.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:6473
chicago: Cepeda Humerez, Sarah A. “Estimating Information Flow in Single Cells.”
Institute of Science and Technology Austria, 2019. https://doi.org/10.15479/AT:ISTA:6473.
ieee: S. A. Cepeda Humerez, “Estimating information flow in single cells,” Institute
of Science and Technology Austria, 2019.
ista: Cepeda Humerez SA. 2019. Estimating information flow in single cells. Institute
of Science and Technology Austria.
mla: Cepeda Humerez, Sarah A. Estimating Information Flow in Single Cells.
Institute of Science and Technology Austria, 2019, doi:10.15479/AT:ISTA:6473.
short: S.A. Cepeda Humerez, Estimating Information Flow in Single Cells, Institute
of Science and Technology Austria, 2019.
corr_author: '1'
date_created: 2019-05-21T00:11:23Z
date_published: 2019-05-23T00:00:00Z
date_updated: 2026-04-16T08:37:38Z
day: '23'
ddc:
- '004'
degree_awarded: PhD
department:
- _id: GaTk
doi: 10.15479/AT:ISTA:6473
file:
- access_level: closed
checksum: 75f9184c1346e10a5de5f9cc7338309a
content_type: application/zip
creator: scepeda
date_created: 2019-05-23T11:18:16Z
date_updated: 2020-07-14T12:47:31Z
file_id: '6480'
file_name: Thesis_Cepeda.zip
file_size: 23937464
relation: source_file
- access_level: open_access
checksum: afdc0633ddbd71d5b13550d7fb4f4454
content_type: application/pdf
creator: scepeda
date_created: 2019-05-23T11:18:13Z
date_updated: 2020-07-14T12:47:31Z
file_id: '6481'
file_name: CepedaThesis.pdf
file_size: 16646985
relation: main_file
file_date_updated: 2020-07-14T12:47:31Z
has_accepted_license: '1'
keyword:
- Information estimation
- Time-series
- data analysis
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: '135'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '2016'
relation: dissertation_contains
status: public
- id: '281'
relation: dissertation_contains
status: public
- id: '1576'
relation: dissertation_contains
status: public
- id: '6900'
relation: dissertation_contains
status: public
status: public
supervisor:
- first_name: Gašper
full_name: Tkačik, Gašper
id: 3D494DCA-F248-11E8-B48F-1D18A9856A87
last_name: Tkačik
orcid: 0000-0002-6699-1455
title: Estimating information flow in single cells
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: '2019'
...
---
_id: '6482'
abstract:
- lang: eng
text: 'Computer vision systems for automatic image categorization have become accurate
and reliable enough that they can run continuously for days or even years as components
of real-world commercial applications. A major open problem in this context, however,
is quality control. Good classification performance can only be expected if systems
run under the specific conditions, in particular data distributions, that they
were trained for. Surprisingly, none of the currently used deep network architectures
have a built-in functionality that could detect if a network operates on data
from a distribution it was not trained for, such that potentially a warning to
the human users could be triggered. In this work, we describe KS(conf), a procedure
for detecting such outside of specifications (out-of-specs) operation, based on
statistical testing of the network outputs. We show by extensive experiments using
the ImageNet, AwA2 and DAVIS datasets on a variety of ConvNets architectures that
KS(conf) reliably detects out-of-specs situations. It furthermore has a number
of properties that make it a promising candidate for practical deployment: it
is easy to implement, adds almost no overhead to the system, works with all networks,
including pretrained ones, and requires no a priori knowledge of how the data
distribution could change. '
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Rémy
full_name: Sun, Rémy
last_name: Sun
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Sun R, Lampert C. KS(conf): A light-weight test if a ConvNet operates outside
of Its specifications. In: Vol 11269. Springer Nature; 2019:244-259. doi:10.1007/978-3-030-12939-2_18'
apa: 'Sun, R., & Lampert, C. (2019). KS(conf): A light-weight test if a ConvNet
operates outside of Its specifications (Vol. 11269, pp. 244–259). Presented at
the GCPR: Conference on Pattern Recognition, Stuttgart, Germany: Springer Nature.
https://doi.org/10.1007/978-3-030-12939-2_18'
chicago: 'Sun, Rémy, and Christoph Lampert. “KS(Conf): A Light-Weight Test If a
ConvNet Operates Outside of Its Specifications,” 11269:244–59. Springer Nature,
2019. https://doi.org/10.1007/978-3-030-12939-2_18.'
ieee: 'R. Sun and C. Lampert, “KS(conf): A light-weight test if a ConvNet operates
outside of Its specifications,” presented at the GCPR: Conference on Pattern Recognition,
Stuttgart, Germany, 2019, vol. 11269, pp. 244–259.'
ista: 'Sun R, Lampert C. 2019. KS(conf): A light-weight test if a ConvNet operates
outside of Its specifications. GCPR: Conference on Pattern Recognition, LNCS,
vol. 11269, 244–259.'
mla: 'Sun, Rémy, and Christoph Lampert. KS(Conf): A Light-Weight Test If a ConvNet
Operates Outside of Its Specifications. Vol. 11269, Springer Nature, 2019,
pp. 244–59, doi:10.1007/978-3-030-12939-2_18.'
short: R. Sun, C. Lampert, in:, Springer Nature, 2019, pp. 244–259.
conference:
end_date: 2018-10-12
location: Stuttgart, Germany
name: 'GCPR: Conference on Pattern Recognition'
start_date: 2018-10-09
date_created: 2019-05-24T09:48:36Z
date_published: 2019-02-14T00:00:00Z
date_updated: 2025-04-15T07:10:25Z
day: '14'
department:
- _id: ChLa
doi: 10.1007/978-3-030-12939-2_18
ec_funded: 1
external_id:
arxiv:
- '1804.04171'
intvolume: ' 11269'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1804.04171
month: '02'
oa: 1
oa_version: Preprint
page: 244-259
project:
- _id: 2532554C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '308036'
name: Lifelong Learning of Visual Scene Understanding
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030129385'
- '9783030129392'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '6944'
relation: later_version
status: public
scopus_import: '1'
status: public
title: 'KS(conf): A light-weight test if a ConvNet operates outside of Its specifications'
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 11269
year: '2019'
...
---
_id: '6485'
abstract:
- lang: eng
text: Traditional concurrent programming involves manipulating shared mutable state.
Alternatives to this programming style are communicating sequential processes
(CSP) [1] and actor [2] models, which share data via explicit communication. Rendezvous
channelis the common abstraction for communication between several processes,
where senders and receivers perform a rendezvous handshake as a part of their
protocol (senders wait for receivers and vice versa). Additionally to this, channels
support the select expression. In this work, we present the first efficient lock-free
channel algorithm, and compare it against Go [3] and Kotlin [4] baseline implementations.
article_processing_charge: No
author:
- first_name: Nikita
full_name: Koval, Nikita
id: 2F4DB10C-F248-11E8-B48F-1D18A9856A87
last_name: Koval
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Roman
full_name: Elizarov, Roman
last_name: Elizarov
citation:
ama: Koval N, Alistarh D-A, Elizarov R. Lock-Free Channels for Programming via
Communicating Sequential Processes. ACM; 2019:417-418. doi:10.1145/3293883.3297000
apa: 'Koval, N., Alistarh, D.-A., & Elizarov, R. (2019). Lock-free channels
for programming via communicating sequential processes. Proceedings of
the 24th Symposium on Principles and Practice of Parallel Programming (pp.
417–418). Washington, NY, United States: ACM. https://doi.org/10.1145/3293883.3297000'
chicago: Koval, Nikita, Dan-Adrian Alistarh, and Roman Elizarov. Lock-Free Channels
for Programming via Communicating Sequential Processes. Proceedings of
the 24th Symposium on Principles and Practice of Parallel Programming. ACM,
2019. https://doi.org/10.1145/3293883.3297000.
ieee: N. Koval, D.-A. Alistarh, and R. Elizarov, Lock-free channels for programming
via communicating sequential processes. ACM, 2019, pp. 417–418.
ista: Koval N, Alistarh D-A, Elizarov R. 2019. Lock-free channels for programming
via communicating sequential processes, ACM,p.
mla: Koval, Nikita, et al. “Lock-Free Channels for Programming via Communicating
Sequential Processes.” Proceedings of the 24th Symposium on Principles and
Practice of Parallel Programming, ACM, 2019, pp. 417–18, doi:10.1145/3293883.3297000.
short: N. Koval, D.-A. Alistarh, R. Elizarov, Lock-Free Channels for Programming
via Communicating Sequential Processes, ACM, 2019.
conference:
end_date: 2019-02-20
location: Washington, NY, United States
name: 'PPoPP: Principles and Practice of Parallel Programming'
start_date: 2019-02-16
date_created: 2019-05-24T10:09:12Z
date_published: 2019-02-01T00:00:00Z
date_updated: 2024-12-11T11:42:22Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3293883.3297000
external_id:
isi:
- '000587604600044'
isi: 1
language:
- iso: eng
month: '02'
oa_version: None
page: 417-418
publication: Proceedings of the 24th Symposium on Principles and Practice of Parallel
Programming
publication_identifier:
isbn:
- '9781450362252'
publication_status: published
publisher: ACM
quality_controlled: '1'
status: public
title: Lock-free channels for programming via communicating sequential processes
type: conference_poster
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '6493'
abstract:
- lang: eng
text: We present two algorithmic approaches for synthesizing linear hybrid automata
from experimental data. Unlike previous approaches, our algorithms work without
a template and generate an automaton with nondeterministic guards and invariants,
and with an arbitrary number and topology of modes. They thus construct a succinct
model from the data and provide formal guarantees. In particular, (1) the generated
automaton can reproduce the data up to a specified tolerance and (2) the automaton
is tight, given the first guarantee. Our first approach encodes the synthesis
problem as a logical formula in the theory of linear arithmetic, which can then
be solved by an SMT solver. This approach minimizes the number of modes in the
resulting model but is only feasible for limited data sets. To address scalability,
we propose a second approach that does not enforce to find a minimal model. The
algorithm constructs an initial automaton and then iteratively extends the automaton
based on processing new data. Therefore the algorithm is well-suited for online
and synthesis-in-the-loop applications. The core of the algorithm is a membership
query that checks whether, within the specified tolerance, a given data set can
result from the execution of a given automaton. We solve this membership problem
for linear hybrid automata by repeated reachability computations. We demonstrate
the effectiveness of the algorithm on synthetic data sets and on cardiac-cell
measurements.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Miriam
full_name: Garcia Soto, Miriam
id: 4B3207F6-F248-11E8-B48F-1D18A9856A87
last_name: Garcia Soto
orcid: 0000−0003−2936−5719
- 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: Christian
full_name: Schilling, Christian
id: 3A2F4DCE-F248-11E8-B48F-1D18A9856A87
last_name: Schilling
orcid: 0000-0003-3658-1065
- first_name: Luka
full_name: Zeleznik, Luka
id: 3ADCA2E4-F248-11E8-B48F-1D18A9856A87
last_name: Zeleznik
citation:
ama: 'Garcia Soto M, Henzinger TA, Schilling C, Zeleznik L. Membership-based synthesis
of linear hybrid automata. In: 31st International Conference on Computer-Aided
Verification. Vol 11561. Springer; 2019:297-314. doi:10.1007/978-3-030-25540-4_16'
apa: 'Garcia Soto, M., Henzinger, T. A., Schilling, C., & Zeleznik, L. (2019).
Membership-based synthesis of linear hybrid automata. In 31st International
Conference on Computer-Aided Verification (Vol. 11561, pp. 297–314). New York
City, NY, USA: Springer. https://doi.org/10.1007/978-3-030-25540-4_16'
chicago: Garcia Soto, Miriam, Thomas A Henzinger, Christian Schilling, and Luka
Zeleznik. “Membership-Based Synthesis of Linear Hybrid Automata.” In 31st International
Conference on Computer-Aided Verification, 11561:297–314. Springer, 2019.
https://doi.org/10.1007/978-3-030-25540-4_16.
ieee: M. Garcia Soto, T. A. Henzinger, C. Schilling, and L. Zeleznik, “Membership-based
synthesis of linear hybrid automata,” in 31st International Conference on Computer-Aided
Verification, New York City, NY, USA, 2019, vol. 11561, pp. 297–314.
ista: 'Garcia Soto M, Henzinger TA, Schilling C, Zeleznik L. 2019. Membership-based
synthesis of linear hybrid automata. 31st International Conference on Computer-Aided
Verification. CAV: Computer-Aided Verification, LNCS, vol. 11561, 297–314.'
mla: Garcia Soto, Miriam, et al. “Membership-Based Synthesis of Linear Hybrid Automata.”
31st International Conference on Computer-Aided Verification, vol. 11561,
Springer, 2019, pp. 297–314, doi:10.1007/978-3-030-25540-4_16.
short: M. Garcia Soto, T.A. Henzinger, C. Schilling, L. Zeleznik, in:, 31st International
Conference on Computer-Aided Verification, Springer, 2019, pp. 297–314.
conference:
end_date: 2019-07-18
location: New York City, NY, USA
name: 'CAV: Computer-Aided Verification'
start_date: 2019-07-15
corr_author: '1'
date_created: 2019-05-27T07:09:53Z
date_published: 2019-07-12T00:00:00Z
date_updated: 2025-04-15T06:26:13Z
day: '12'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-030-25540-4_16
ec_funded: 1
external_id:
isi:
- '000491468000016'
file:
- access_level: open_access
checksum: 1f1d61b83a151031745ef70a501da3d6
content_type: application/pdf
creator: dernst
date_created: 2019-08-14T11:05:30Z
date_updated: 2020-07-14T12:47:32Z
file_id: '6817'
file_name: 2019_CAV_GarciaSoto.pdf
file_size: 674795
relation: main_file
file_date_updated: 2020-07-14T12:47:32Z
has_accepted_license: '1'
intvolume: ' 11561'
isi: 1
keyword:
- Synthesis
- Linear hybrid automaton
- Membership
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 297-314
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
publication: 31st International Conference on Computer-Aided Verification
publication_identifier:
isbn:
- '9783030255398'
issn:
- 0302-9743
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Membership-based synthesis of linear hybrid 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: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 11561
year: '2019'
...
---
_id: '6528'
abstract:
- lang: eng
text: We construct a verifiable delay function (VDF) by showing how the Rivest-Shamir-Wagner
time-lock puzzle can be made publicly verifiable. Concretely, we give a statistically
sound public-coin protocol to prove that a tuple (N,x,T,y) satisfies y=x2T (mod
N) where the prover doesn’t know the factorization of N and its running time is
dominated by solving the puzzle, that is, compute x2T, which is conjectured to
require T sequential squarings. To get a VDF we make this protocol non-interactive
using the Fiat-Shamir heuristic.The motivation for this work comes from the Chia
blockchain design, which uses a VDF as akey ingredient. For typical parameters
(T≤2 40, N= 2048), our proofs are of size around 10K B, verification cost around
three RSA exponentiations and computing the proof is 8000 times faster than solving
the puzzle even without any parallelism.
alternative_title:
- LIPIcs
article_number: '60'
article_processing_charge: No
author:
- 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: 'Pietrzak KZ. Simple verifiable delay functions. In: 10th Innovations in
Theoretical Computer Science Conference. Vol 124. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2019. doi:10.4230/LIPICS.ITCS.2019.60'
apa: 'Pietrzak, K. Z. (2019). Simple verifiable delay functions. In 10th Innovations
in Theoretical Computer Science Conference (Vol. 124). San Diego, CA, United
States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2019.60'
chicago: Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” In 10th
Innovations in Theoretical Computer Science Conference, Vol. 124. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ITCS.2019.60.
ieee: K. Z. Pietrzak, “Simple verifiable delay functions,” in 10th Innovations
in Theoretical Computer Science Conference, San Diego, CA, United States,
2019, vol. 124.
ista: 'Pietrzak KZ. 2019. Simple verifiable delay functions. 10th Innovations in
Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer
Science, LIPIcs, vol. 124, 60.'
mla: Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” 10th Innovations
in Theoretical Computer Science Conference, vol. 124, 60, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.ITCS.2019.60.
short: K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science Conference,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
conference:
end_date: 2019-01-12
location: San Diego, CA, United States
name: 'ITCS: Innovations in Theoretical Computer Science'
start_date: 2019-01-10
date_created: 2019-06-06T14:12:36Z
date_published: 2019-01-10T00:00:00Z
date_updated: 2025-07-10T11:53:29Z
day: '10'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.4230/LIPICS.ITCS.2019.60
ec_funded: 1
file:
- access_level: open_access
checksum: f0ae1bb161431d9db3dea5ace082bfb5
content_type: application/pdf
creator: dernst
date_created: 2019-06-06T14:22:04Z
date_updated: 2020-07-14T12:47:33Z
file_id: '6529'
file_name: 2019_LIPIcs_Pietrzak.pdf
file_size: 558770
relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: ' 124'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2018/627
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 10th Innovations in Theoretical Computer Science Conference
publication_identifier:
isbn:
- 978-3-95977-095-8
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Simple verifiable delay functions
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: 124
year: '2019'
...
---
_id: '6556'
abstract:
- lang: eng
text: 'Motivated by fixed-parameter tractable (FPT) problems in computational topology,
we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined
to be the minimum treewidth of the face pairing graph of any triangulation T of
M. In this setting the relationship between the topology of a 3-manifold and its
treewidth is of particular interest. First, as a corollary of work of Jaco and
Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth
tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination
with our earlier work with Wagner, this yields that for non-Haken manifolds the
Heegaard genus and the treewidth are within a constant factor. Second, we characterize
all 3-manifolds of treewidth one: These are precisely the lens spaces and a single
other Seifert fibered space. Furthermore, we show that all remaining orientable
Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth
two. In particular, for every spherical 3-manifold we exhibit a triangulation
of treewidth at most two. Our results further validate the parameter of treewidth
(and other related parameters such as cutwidth or congestion) to be useful for
topological computing, and also shed more light on the scope of existing FPT-algorithms
in the field.'
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Kristóf
full_name: Huszár, Kristóf
id: 33C26278-F248-11E8-B48F-1D18A9856A87
last_name: Huszár
orcid: 0000-0002-5445-5057
- first_name: Jonathan
full_name: Spreer, Jonathan
last_name: Spreer
citation:
ama: 'Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: 35th
International Symposium on Computational Geometry. Vol 129. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2019:44:1-44:20. doi:10.4230/LIPIcs.SoCG.2019.44'
apa: 'Huszár, K., & Spreer, J. (2019). 3-manifold triangulations with small
treewidth. In 35th International Symposium on Computational Geometry (Vol.
129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2019.44'
chicago: Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small
Treewidth.” In 35th International Symposium on Computational Geometry,
129:44:1-44:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPIcs.SoCG.2019.44.
ieee: K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,”
in 35th International Symposium on Computational Geometry, Portland, Oregon,
United States, 2019, vol. 129, p. 44:1-44:20.
ista: 'Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth.
35th International Symposium on Computational Geometry. SoCG: Symposium on Computational
Geometry, LIPIcs, vol. 129, 44:1-44:20.'
mla: Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small
Treewidth.” 35th International Symposium on Computational Geometry, vol.
129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20, doi:10.4230/LIPIcs.SoCG.2019.44.
short: K. Huszár, J. Spreer, in:, 35th International Symposium on Computational
Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20.
conference:
end_date: 2019-06-21
location: Portland, Oregon, United States
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2019-06-18
corr_author: '1'
date_created: 2019-06-11T20:09:57Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2026-04-08T07:21:27Z
day: '01'
ddc:
- '516'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2019.44
external_id:
arxiv:
- '1812.05528'
file:
- access_level: open_access
checksum: 29d18c435368468aa85823dabb157e43
content_type: application/pdf
creator: kschuh
date_created: 2019-06-12T06:45:33Z
date_updated: 2020-07-14T12:47:33Z
file_id: '6557'
file_name: 2019_LIPIcs-Huszar.pdf
file_size: 905885
relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: ' 129'
keyword:
- computational 3-manifold topology
- fixed-parameter tractability
- layered triangulations
- structural graph theory
- treewidth
- cutwidth
- Heegaard genus
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 44:1-44:20
publication: 35th International Symposium on Computational Geometry
publication_identifier:
isbn:
- 978-3-95977-104-7
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '8032'
relation: part_of_dissertation
status: public
scopus_import: '1'
status: public
title: 3-manifold triangulations with small treewidth
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: 129
year: '2019'
...
---
_id: '6647'
abstract:
- lang: eng
text: The Tverberg theorem is one of the cornerstones of discrete geometry. It states
that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition
X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r,
all share a common point. In this paper, we prove a strengthening of this theorem
that guarantees a partition which, in addition to the above, has the property
that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections.
Possible generalizations and algorithmic aspects are also discussed. As a concrete
application, we show that any n points in the plane in general position span floor[n/3]
vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries
have pairwise nonempty intersections; this number is clearly best possible. A
previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing
triangles. Our result generalizes to a result about simplices in R^d,d >=2.
alternative_title:
- LIPIcs
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Bernd
full_name: Gärtner, Bernd
last_name: Gärtner
- first_name: Andrey
full_name: Kupavskii, Andrey
last_name: Kupavskii
- first_name: Pavel
full_name: Valtr, Pavel
last_name: Valtr
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg
theorem. In: 35th International Symposium on Computational Geometry. Vol
129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:38:1-38:13. doi:10.4230/LIPICS.SOCG.2019.38'
apa: 'Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2019).
The crossing Tverberg theorem. In 35th International Symposium on Computational
Geometry (Vol. 129, p. 38:1-38:13). Portland, OR, United States: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.38'
chicago: Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli
Wagner. “The Crossing Tverberg Theorem.” In 35th International Symposium on
Computational Geometry, 129:38:1-38:13. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2019. https://doi.org/10.4230/LIPICS.SOCG.2019.38.
ieee: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing
Tverberg theorem,” in 35th International Symposium on Computational Geometry,
Portland, OR, United States, 2019, vol. 129, p. 38:1-38:13.
ista: 'Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2019. The crossing Tverberg
theorem. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium
on Computational Geometry, LIPIcs, vol. 129, 38:1-38:13.'
mla: Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” 35th International
Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2019, p. 38:1-38:13, doi:10.4230/LIPICS.SOCG.2019.38.
short: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, in:, 35th International
Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2019, p. 38:1-38:13.
conference:
end_date: 2019-06-21
location: Portland, OR, United States
name: 'SoCG 2019: Symposium on Computational Geometry'
start_date: 2019-06-18
corr_author: '1'
date_created: 2019-07-17T10:35:04Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2025-04-14T13:52:36Z
day: '01'
ddc:
- '000'
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPICS.SOCG.2019.38
external_id:
arxiv:
- '1812.04911'
file:
- access_level: open_access
checksum: d6d017f8b41291b94d102294fa96ae9c
content_type: application/pdf
creator: dernst
date_created: 2019-07-24T06:54:52Z
date_updated: 2020-07-14T12:47:35Z
file_id: '6667'
file_name: 2019_LIPICS_Fulek.pdf
file_size: 559837
relation: main_file
file_date_updated: 2020-07-14T12:47:35Z
has_accepted_license: '1'
intvolume: ' 129'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 38:1-38:13
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: 35th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959771047'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '13974'
relation: later_version
status: public
scopus_import: 1
status: public
title: The crossing Tverberg theorem
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: 129
year: '2019'
...
---
_id: '6663'
abstract:
- lang: eng
text: Consider the problem of constructing a polar code of block length N for a
given transmission channel W. Previous approaches require one to compute the reliability
of the N synthetic channels and then use only those that are sufficiently reliable.
However, we know from two independent works by Schürch and by Bardet et al. that
the synthetic channels are partially ordered with respect to degradation. Hence,
it is natural to ask whether the partial order can be exploited to reduce the
computational burden of the construction problem. We show that, if we take advantage
of the partial order, we can construct a polar code by computing the reliability
of roughly a fraction 1/ log 3/2 N of the synthetic channels. In particular, we
prove that N/ log 3/2 N is a lower bound on the number of synthetic channels to
be considered and such a bound is tight up to a multiplicative factor log log
N. This set of roughly N/ log 3/2 N synthetic channels is universal, in the sense
that it allows one to construct polar codes for any W, and it can be identified
by solving a maximum matching problem on a bipartite graph. Our proof technique
consists of reducing the construction problem to the problem of computing the
maximum cardinality of an antichain for a suitable partially ordered set. As such,
this method is general, and it can be used to further improve the complexity of
the construction problem, in case a refined partial order on the synthetic channels
of polar codes is discovered.
arxiv: 1
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Rudiger
full_name: Urbanke, Rudiger
last_name: Urbanke
citation:
ama: Mondelli M, Hassani H, Urbanke R. Construction of polar codes with sublinear
complexity. IEEE. 2019;65(5):2782-2791. doi:10.1109/tit.2018.2889667
apa: Mondelli, M., Hassani, H., & Urbanke, R. (2019). Construction of polar
codes with sublinear complexity. IEEE. IEEE. https://doi.org/10.1109/tit.2018.2889667
chicago: Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “Construction of Polar
Codes with Sublinear Complexity.” IEEE. IEEE, 2019. https://doi.org/10.1109/tit.2018.2889667.
ieee: M. Mondelli, H. Hassani, and R. Urbanke, “Construction of polar codes with
sublinear complexity,” IEEE, vol. 65, no. 5. IEEE, pp. 2782–2791, 2019.
ista: Mondelli M, Hassani H, Urbanke R. 2019. Construction of polar codes with sublinear
complexity. IEEE. 65(5), 2782–2791.
mla: Mondelli, Marco, et al. “Construction of Polar Codes with Sublinear Complexity.”
IEEE, vol. 65, no. 5, IEEE, 2019, pp. 2782–91, doi:10.1109/tit.2018.2889667.
short: M. Mondelli, H. Hassani, R. Urbanke, IEEE 65 (2019) 2782–2791.
date_created: 2019-07-23T07:32:57Z
date_published: 2019-05-01T00:00:00Z
date_updated: 2023-02-23T12:50:20Z
day: '01'
doi: 10.1109/tit.2018.2889667
extern: '1'
external_id:
arxiv:
- '1612.05295'
intvolume: ' 65'
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1612.05295
month: '05'
oa: 1
oa_version: Preprint
page: 2782-2791
publication: IEEE
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '6729'
relation: earlier_version
status: public
status: public
title: Construction of polar codes with sublinear complexity
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 65
year: '2019'
...
---
_id: '6672'
abstract:
- lang: eng
text: The construction of anisotropic triangulations is desirable for various applications,
such as the numerical solving of partial differential equations and the representation
of surfaces in graphics. To solve this notoriously difficult problem in a practical
way, we introduce the discrete Riemannian Voronoi diagram, a discrete structure
that approximates the Riemannian Voronoi diagram. This structure has been implemented
and was shown to lead to good triangulations in $\mathbb{R}^2$ and on surfaces
embedded in $\mathbb{R}^3$ as detailed in our experimental companion paper. In
this paper, we study theoretical aspects of our structure. Given a finite set
of points $\mathcal{P}$ in a domain $\Omega$ equipped with a Riemannian metric,
we compare the discrete Riemannian Voronoi diagram of $\mathcal{P}$ to its Riemannian
Voronoi diagram. Both diagrams have dual structures called the discrete Riemannian
Delaunay and the Riemannian Delaunay complex. We provide conditions that guarantee
that these dual structures are identical. It then follows from previous results
that the discrete Riemannian Delaunay complex can be embedded in $\Omega$ under
sufficient conditions, leading to an anisotropic triangulation with curved simplices.
Furthermore, we show that, under similar conditions, the simplices of this triangulation
can be straightened.
arxiv: 1
author:
- first_name: Jean-Daniel
full_name: Boissonnat, Jean-Daniel
last_name: Boissonnat
- first_name: Mael
full_name: Rouxel-Labbé, Mael
last_name: Rouxel-Labbé
- 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, Rouxel-Labbé M, Wintraecken M. Anisotropic triangulations via
discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. 2019;48(3):1046-1097.
doi:10.1137/17m1152292
apa: Boissonnat, J.-D., Rouxel-Labbé, M., & Wintraecken, M. (2019). Anisotropic
triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing.
Society for Industrial & Applied Mathematics (SIAM). https://doi.org/10.1137/17m1152292
chicago: Boissonnat, Jean-Daniel, Mael Rouxel-Labbé, and Mathijs Wintraecken. “Anisotropic
Triangulations via Discrete Riemannian Voronoi Diagrams.” SIAM Journal on Computing.
Society for Industrial & Applied Mathematics (SIAM), 2019. https://doi.org/10.1137/17m1152292.
ieee: J.-D. Boissonnat, M. Rouxel-Labbé, and M. Wintraecken, “Anisotropic triangulations
via discrete Riemannian Voronoi diagrams,” SIAM Journal on Computing, vol.
48, no. 3. Society for Industrial & Applied Mathematics (SIAM), pp. 1046–1097,
2019.
ista: Boissonnat J-D, Rouxel-Labbé M, Wintraecken M. 2019. Anisotropic triangulations
via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. 48(3), 1046–1097.
mla: Boissonnat, Jean-Daniel, et al. “Anisotropic Triangulations via Discrete Riemannian
Voronoi Diagrams.” SIAM Journal on Computing, vol. 48, no. 3, Society for
Industrial & Applied Mathematics (SIAM), 2019, pp. 1046–97, doi:10.1137/17m1152292.
short: J.-D. Boissonnat, M. Rouxel-Labbé, M. Wintraecken, SIAM Journal on Computing
48 (2019) 1046–1097.
date_created: 2019-07-24T08:42:12Z
date_published: 2019-05-21T00:00:00Z
date_updated: 2021-01-12T08:08:30Z
day: '21'
doi: 10.1137/17m1152292
extern: '1'
external_id:
arxiv:
- '1703.06487'
intvolume: ' 48'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1703.06487
month: '05'
oa: 1
oa_version: Preprint
page: 1046-1097
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: Society for Industrial & Applied Mathematics (SIAM)
quality_controlled: '1'
status: public
title: Anisotropic triangulations via discrete Riemannian Voronoi diagrams
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 48
year: '2019'
...
---
OA_place: publisher
_id: '6681'
abstract:
- lang: eng
text: "The first part of the thesis considers the computational aspects of the homotopy
groups πd(X) of a topological space X. It is well known that there is no algorithm
to decide whether the fundamental group π1(X) of a given finite simplicial complex
X is trivial. On the other hand, there are several algorithms that, given a finite
simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute
the higher homotopy group πd(X) for any given d ≥ 2.\r\nHowever, these algorithms
come with a caveat: They compute the isomorphism type of πd(X), d ≥ 2 as an abstract
finitely generated abelian group given by generators and relations, but they work
with very implicit representations of the elements of πd(X). We present an algorithm
that, given a simply connected space X, computes πd(X) and represents its elements
as simplicial maps from suitable triangulations of the d-sphere Sd to X. For fixed
d, the algorithm runs in time exponential in size(X), the number of simplices
of X. Moreover, we prove that this is optimal: For every fixed d ≥ 2,\r\nwe construct
a family of simply connected spaces X such that for any simplicial map representing
a generator of πd(X), the size of the triangulation of S d on which the map is
defined, is exponential in size(X).\r\nIn the second part of the thesis, we prove
that the following question is algorithmically undecidable for d < ⌊3(k+1)/2⌋,
k ≥ 5 and (k, d) ̸= (5, 7), which covers essentially everything outside the meta-stable
range: Given a finite simplicial complex K of dimension k, decide whether there
exists a piecewise-linear (i.e., linear on an arbitrarily fine subdivision of
K) embedding f : K ↪→ Rd of K into a d-dimensional Euclidean space."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Stephan Y
full_name: Zhechev, Stephan Y
id: 3AA52972-F248-11E8-B48F-1D18A9856A87
last_name: Zhechev
citation:
ama: Zhechev SY. Algorithmic aspects of homotopy theory and embeddability. 2019.
doi:10.15479/AT:ISTA:6681
apa: Zhechev, S. Y. (2019). Algorithmic aspects of homotopy theory and embeddability.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:6681
chicago: Zhechev, Stephan Y. “Algorithmic Aspects of Homotopy Theory and Embeddability.”
Institute of Science and Technology Austria, 2019. https://doi.org/10.15479/AT:ISTA:6681.
ieee: S. Y. Zhechev, “Algorithmic aspects of homotopy theory and embeddability,”
Institute of Science and Technology Austria, 2019.
ista: Zhechev SY. 2019. Algorithmic aspects of homotopy theory and embeddability.
Institute of Science and Technology Austria.
mla: Zhechev, Stephan Y. Algorithmic Aspects of Homotopy Theory and Embeddability.
Institute of Science and Technology Austria, 2019, doi:10.15479/AT:ISTA:6681.
short: S.Y. Zhechev, Algorithmic Aspects of Homotopy Theory and Embeddability, Institute
of Science and Technology Austria, 2019.
corr_author: '1'
date_created: 2019-07-26T11:14:34Z
date_published: 2019-08-08T00:00:00Z
date_updated: 2026-04-16T12:20:40Z
day: '08'
ddc:
- '514'
degree_awarded: PhD
department:
- _id: UlWa
doi: 10.15479/AT:ISTA:6681
file:
- access_level: open_access
checksum: 3231e7cbfca3b5687366f84f0a57a0c0
content_type: application/pdf
creator: szhechev
date_created: 2019-08-07T13:02:50Z
date_updated: 2020-07-14T12:47:37Z
file_id: '6771'
file_name: Stephan_Zhechev_thesis.pdf
file_size: 1464227
relation: main_file
- access_level: closed
checksum: 85d65eb27b4377a9e332ee37a70f08b6
content_type: application/octet-stream
creator: szhechev
date_created: 2019-08-07T13:03:22Z
date_updated: 2020-07-14T12:47:37Z
file_id: '6772'
file_name: Stephan_Zhechev_thesis.tex
file_size: 303988
relation: source_file
- access_level: closed
checksum: 86b374d264ca2dd53e712728e253ee75
content_type: application/zip
creator: szhechev
date_created: 2019-08-07T13:03:34Z
date_updated: 2020-07-14T12:47:37Z
file_id: '6773'
file_name: supplementary_material.zip
file_size: 1087004
relation: supplementary_material
file_date_updated: 2020-07-14T12:47:37Z
has_accepted_license: '1'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: '104'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '6774'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
title: Algorithmic aspects of homotopy theory and embeddability
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: '2019'
...
---
_id: '6725'
abstract:
- lang: eng
text: "A Valued Constraint Satisfaction Problem (VCSP) provides a common framework
that can express a wide range of discrete optimization problems. A VCSP instance
is given by a finite set of variables, a finite domain of labels, and an objective
function to be minimized. This function is represented as a sum of terms where
each term depends on a subset of the variables. To obtain different classes of
optimization problems, one can restrict all terms to come from a fixed set Γ of
cost functions, called a language. \r\nRecent breakthrough results have established
a complete complexity classification of such classes with respect to language
Γ: if all cost functions in Γ satisfy a certain algebraic condition then all Γ-instances
can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately,
testing this condition for a given language Γ is known to be NP-hard. We thus
study exponential algorithms for this meta-problem. We show that the tractability
condition of a finite-valued language Γ can be tested in O(3‾√3|D|⋅poly(size(Γ)))
time, where D is the domain of Γ and poly(⋅) is some fixed polynomial. We also
obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH).
More precisely, we prove that for any constant δ<1 there is no O(3‾√3δ|D|) algorithm,
assuming that SETH holds."
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Kolmogorov V. Testing the complexity of a valued CSP language. In: 46th
International Colloquium on Automata, Languages and Programming. Vol 132.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:77:1-77:12. doi:10.4230/LIPICS.ICALP.2019.77'
apa: 'Kolmogorov, V. (2019). Testing the complexity of a valued CSP language. In
46th International Colloquium on Automata, Languages and Programming (Vol.
132, p. 77:1-77:12). Patras, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPICS.ICALP.2019.77'
chicago: Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.”
In 46th International Colloquium on Automata, Languages and Programming,
132:77:1-77:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ICALP.2019.77.
ieee: V. Kolmogorov, “Testing the complexity of a valued CSP language,” in 46th
International Colloquium on Automata, Languages and Programming, Patras, Greece,
2019, vol. 132, p. 77:1-77:12.
ista: 'Kolmogorov V. 2019. Testing the complexity of a valued CSP language. 46th
International Colloquium on Automata, Languages and Programming. ICALP: Automata,
Languages and Programming, LIPIcs, vol. 132, 77:1-77:12.'
mla: Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” 46th
International Colloquium on Automata, Languages and Programming, vol. 132,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12, doi:10.4230/LIPICS.ICALP.2019.77.
short: V. Kolmogorov, in:, 46th International Colloquium on Automata, Languages
and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12.
conference:
end_date: 2019-07-12
location: Patras, Greece
name: 'ICALP: Automata, Languages and Programming'
start_date: 2019-07-08
date_created: 2019-07-29T12:23:29Z
date_published: 2019-07-01T00:00:00Z
date_updated: 2025-07-10T11:53:47Z
day: '01'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.4230/LIPICS.ICALP.2019.77
ec_funded: 1
external_id:
arxiv:
- '1803.02289'
file:
- access_level: open_access
checksum: f5ebee8eec6ae09e30365578ee63a492
content_type: application/pdf
creator: dernst
date_created: 2019-07-31T07:01:45Z
date_updated: 2020-07-14T12:47:38Z
file_id: '6738'
file_name: 2019_LIPICS_Kolmogorov.pdf
file_size: 575475
relation: main_file
file_date_updated: 2020-07-14T12:47:38Z
has_accepted_license: '1'
intvolume: ' 132'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 77:1-77:12
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: 46th International Colloquium on Automata, Languages and Programming
publication_identifier:
isbn:
- 978-3-95977-109-2
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Testing the complexity of a valued CSP language
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: 132
year: '2019'
...
---
_id: '6726'
abstract:
- lang: eng
text: Randomness is an essential part of any secure cryptosystem, but many constructions
rely on distributions that are not uniform. This is particularly true for lattice
based cryptosystems, which more often than not make use of discrete Gaussian distributions
over the integers. For practical purposes it is crucial to evaluate the impact
that approximation errors have on the security of a scheme to provide the best
possible trade-off between security and performance. Recent years have seen surprising
results allowing to use relatively low precision while maintaining high levels
of security. A key insight in these results is that sampling a distribution with
low relative error can provide very strong security guarantees. Since floating
point numbers provide guarantees on the relative approximation error, they seem
a suitable tool in this setting, but it is not obvious which sampling algorithms
can actually profit from them. While previous works have shown that inversion
sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES
2014; Prest, ASIACRYPT 2017), other works have called into question if this is
possible for other sampling techniques (Zheng et al., Eprint report 2018/309).
In this work, we consider all sampling algorithms that are popular in the cryptographic
setting and analyze the relationship of floating point precision and the resulting
relative error. We show that all of the algorithms either natively achieve a low
relative error or can be adapted to do so.
article_processing_charge: No
author:
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Walter M. Sampling the integers with low relative error. In: Buchmann J, Nitaj
A, Rachidi T, eds. Progress in Cryptology – AFRICACRYPT 2019. Vol 11627.
LNCS. Cham: Springer Nature; 2019:157-180. doi:10.1007/978-3-030-23696-0_9'
apa: 'Walter, M. (2019). Sampling the integers with low relative error. In J. Buchmann,
A. Nitaj, & T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019
(Vol. 11627, pp. 157–180). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-23696-0_9'
chicago: 'Walter, Michael. “Sampling the Integers with Low Relative Error.” In Progress
in Cryptology – AFRICACRYPT 2019, edited by J Buchmann, A Nitaj, and T Rachidi,
11627:157–80. LNCS. Cham: Springer Nature, 2019. https://doi.org/10.1007/978-3-030-23696-0_9.'
ieee: 'M. Walter, “Sampling the integers with low relative error,” in Progress
in Cryptology – AFRICACRYPT 2019, vol. 11627, J. Buchmann, A. Nitaj, and T.
Rachidi, Eds. Cham: Springer Nature, 2019, pp. 157–180.'
ista: 'Walter M. 2019.Sampling the integers with low relative error. In: Progress
in Cryptology – AFRICACRYPT 2019. vol. 11627, 157–180.'
mla: Walter, Michael. “Sampling the Integers with Low Relative Error.” Progress
in Cryptology – AFRICACRYPT 2019, edited by J Buchmann et al., vol. 11627,
Springer Nature, 2019, pp. 157–80, doi:10.1007/978-3-030-23696-0_9.
short: M. Walter, in:, J. Buchmann, A. Nitaj, T. Rachidi (Eds.), Progress in Cryptology
– AFRICACRYPT 2019, Springer Nature, Cham, 2019, pp. 157–180.
conference:
end_date: 2019-07-11
location: Rabat, Morocco
name: 'AFRICACRYPT: International Conference on Cryptology in Africa'
start_date: 2019-07-09
date_created: 2019-07-29T12:25:31Z
date_published: 2019-06-29T00:00:00Z
date_updated: 2025-09-10T10:38:28Z
day: '29'
department:
- _id: KrPi
doi: 10.1007/978-3-030-23696-0_9
ec_funded: 1
editor:
- first_name: J
full_name: Buchmann, J
last_name: Buchmann
- first_name: A
full_name: Nitaj, A
last_name: Nitaj
- first_name: T
full_name: Rachidi, T
last_name: Rachidi
external_id:
isi:
- '001299240700009'
intvolume: ' 11627'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/068
month: '06'
oa: 1
oa_version: Preprint
page: 157-180
place: Cham
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Progress in Cryptology – AFRICACRYPT 2019
publication_identifier:
eisbn:
- 978-3-0302-3696-0
eissn:
- 1611-3349
isbn:
- 978-3-0302-3695-3
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Sampling the integers with low relative error
type: book_chapter
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 11627
year: '2019'
...
---
OA_place: publisher
OA_type: hybrid
_id: '6756'
abstract:
- lang: eng
text: "We study the topology generated by the temperature fluctuations of the cosmic
microwave background (CMB) radiation, as quantified by the number of components
and holes, formally given by the Betti numbers, in the growing excursion sets.
We compare CMB maps observed by the Planck satellite with a thousand simulated
maps generated according to the ΛCDM paradigm with Gaussian distributed fluctuations.
The comparison is multi-scale, being performed on a sequence of degraded maps
with mean pixel separation ranging from 0.05 to 7.33°. The survey of the CMB over
\U0001D54A2 is incomplete due to obfuscation effects by bright point sources and
other extended foreground objects like our own galaxy. To deal with such situations,
where analysis in the presence of “masks” is of importance, we introduce the concept
of relative homology. The parametric χ2-test shows differences between observations
and simulations, yielding p-values at percent to less than permil levels roughly
between 2 and 7°, with the difference in the number of components and holes peaking
at more than 3σ sporadically at these scales. The highest observed deviation between
the observations and simulations for b0 and b1 is approximately between 3σ and
4σ at scales of 3–7°. There are reports of mildly unusual behaviour of the Euler
characteristic at 3.66° in the literature, computed from independent measurements
of the CMB temperature fluctuations by Planck’s predecessor, the Wilkinson Microwave
Anisotropy Probe (WMAP) satellite. The mildly anomalous behaviour of the Euler
characteristic is phenomenologically related to the strongly anomalous behaviour
of components and holes, or the zeroth and first Betti numbers, respectively.
Further, since these topological descriptors show consistent anomalous behaviour
over independent measurements of Planck and WMAP, instrumental and systematic
errors may be an unlikely source. These are also the scales at which the observed
maps exhibit low variance compared to the simulations, and approximately the range
of scales at which the power spectrum exhibits a dip with respect to the theoretical
model. Non-parametric tests show even stronger differences at almost all scales.
Crucially, Gaussian simulations based on power-spectrum matching the characteristics
of the observed dipped power spectrum are not able to resolve the anomaly. Understanding
the origin of the anomalies in the CMB, whether cosmological in nature or arising
due to late-time effects, is an extremely challenging task. Regardless, beyond
the trivial possibility that this may still be a manifestation of an extreme Gaussian
case, these observations, along with the super-horizon scales involved, may motivate
the study of primordial non-Gaussianity. Alternative scenarios worth exploring
may be models with non-trivial topology, including topological defect models."
acknowledgement: 'PP is grateful to Julian Borill from the Planck consortium for providing
the data, and for the illuminating discussions and inputs. PP also thanks Hans Kristen
Eriksen, Anne Ducout, and Francois R. Bouchet for significantly helpful discussions
at various stages. The authors collectively thank the anonymous referee for the
invaluable comments and suggestions that have added significant value to the contents
of the manuscript. PP and RA acknowledge the support of ERC advanced grant Understanding
Random Systems through Algebraic Topology (URSAT) (no: 320422, PI: RA). This work
is also part of a project that has received funding for PP and TB from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme (grant agreement ERC advanced grant 740021– Advances in Research on THeories
of the dark UniverSe (ARTHUS), PI: TB). HE and HW acknowledge the support by the
Office of Naval Research, through grant N62909-18-1-2038, and by the DFG Collaborative
Research Center TRR 109, “Discretization in Geometry and Dynamics”, through grant
I02979-N35 of the Austrian Science Fund (FWF). PP acknowledges the support and use
of resources at the NERSC computing center.'
article_number: A163
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Pratyush
full_name: Pranav, Pratyush
last_name: Pranav
- first_name: Robert J.
full_name: Adler, Robert J.
last_name: Adler
- first_name: Thomas
full_name: Buchert, Thomas
last_name: Buchert
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Bernard J.T.
full_name: Jones, Bernard J.T.
last_name: Jones
- first_name: Armin
full_name: Schwartzman, Armin
last_name: Schwartzman
- first_name: Hubert
full_name: Wagner, Hubert
id: 379CA8B8-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
- first_name: Rien
full_name: Van De Weygaert, Rien
last_name: Van De Weygaert
citation:
ama: Pranav P, Adler RJ, Buchert T, et al. Unexpected topology of the temperature
fluctuations in the cosmic microwave background. Astronomy and Astrophysics.
2019;627. doi:10.1051/0004-6361/201834916
apa: Pranav, P., Adler, R. J., Buchert, T., Edelsbrunner, H., Jones, B. J. T., Schwartzman,
A., … Van De Weygaert, R. (2019). Unexpected topology of the temperature fluctuations
in the cosmic microwave background. Astronomy and Astrophysics. EDP Sciences.
https://doi.org/10.1051/0004-6361/201834916
chicago: Pranav, Pratyush, Robert J. Adler, Thomas Buchert, Herbert Edelsbrunner,
Bernard J.T. Jones, Armin Schwartzman, Hubert Wagner, and Rien Van De Weygaert.
“Unexpected Topology of the Temperature Fluctuations in the Cosmic Microwave Background.”
Astronomy and Astrophysics. EDP Sciences, 2019. https://doi.org/10.1051/0004-6361/201834916.
ieee: P. Pranav et al., “Unexpected topology of the temperature fluctuations
in the cosmic microwave background,” Astronomy and Astrophysics, vol. 627.
EDP Sciences, 2019.
ista: Pranav P, Adler RJ, Buchert T, Edelsbrunner H, Jones BJT, Schwartzman A, Wagner
H, Van De Weygaert R. 2019. Unexpected topology of the temperature fluctuations
in the cosmic microwave background. Astronomy and Astrophysics. 627, A163.
mla: Pranav, Pratyush, et al. “Unexpected Topology of the Temperature Fluctuations
in the Cosmic Microwave Background.” Astronomy and Astrophysics, vol. 627,
A163, EDP Sciences, 2019, doi:10.1051/0004-6361/201834916.
short: P. Pranav, R.J. Adler, T. Buchert, H. Edelsbrunner, B.J.T. Jones, A. Schwartzman,
H. Wagner, R. Van De Weygaert, Astronomy and Astrophysics 627 (2019).
date_created: 2019-08-04T21:59:18Z
date_published: 2019-07-17T00:00:00Z
date_updated: 2025-05-20T08:01:55Z
day: '17'
ddc:
- '520'
- '530'
department:
- _id: HeEd
doi: 10.1051/0004-6361/201834916
external_id:
arxiv:
- '1812.07678'
isi:
- '000475839300003'
file:
- access_level: open_access
checksum: 83b9209ed9eefbdcefd89019c5a97805
content_type: application/pdf
creator: dernst
date_created: 2019-08-05T08:08:59Z
date_updated: 2020-07-14T12:47:39Z
file_id: '6766'
file_name: 2019_AstronomyAstrophysics_Pranav.pdf
file_size: 14420451
relation: main_file
file_date_updated: 2020-07-14T12:47:39Z
has_accepted_license: '1'
intvolume: ' 627'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 265683E4-B435-11E9-9278-68D0E5697425
grant_number: M62909-18-1-2038
name: Toward Computational Information Topology
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Astronomy and Astrophysics
publication_identifier:
eissn:
- 1432-0746
issn:
- 0004-6361
publication_status: published
publisher: EDP Sciences
quality_controlled: '1'
scopus_import: '1'
status: public
title: Unexpected topology of the temperature fluctuations in the cosmic microwave
background
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: 627
year: '2019'
...
---
_id: '6819'
abstract:
- lang: eng
text: Glyphosate (N-phosphonomethyl glycine) and its commercial herbicide formulations
have been shown to exert toxicity via various mechanisms. It has been asserted
that glyphosate substitutes for glycine in polypeptide chains leading to protein
misfolding and toxicity. However, as no direct evidence exists for glycine to
glyphosate substitution in proteins, including in mammalian organisms, we tested
this claim by conducting a proteomics analysis of MDA-MB-231 human breast cancer
cells grown in the presence of 100 mg/L glyphosate for 6 days. Protein extracts
from three treated and three untreated cell cultures were analysed as one TMT-6plex
labelled sample, to highlight a specific pattern (+/+/+/−/−/−) of reporter intensities
for peptides bearing true glyphosate treatment induced-post translational modifications
as well as allowing an investigation of the total proteome.
article_number: '494'
article_processing_charge: No
author:
- first_name: Michael N.
full_name: Antoniou, Michael N.
last_name: Antoniou
- first_name: Armel
full_name: Nicolas, Armel
id: 2A103192-F248-11E8-B48F-1D18A9856A87
last_name: Nicolas
- first_name: Robin
full_name: Mesnage, Robin
last_name: Mesnage
- first_name: Martina
full_name: Biserni, Martina
last_name: Biserni
- first_name: Francesco V.
full_name: Rao, Francesco V.
last_name: Rao
- first_name: Cristina Vazquez
full_name: Martin, Cristina Vazquez
last_name: Martin
citation:
ama: Antoniou MN, Nicolas A, Mesnage R, Biserni M, Rao FV, Martin CV. Glyphosate
does not substitute for glycine in proteins of actively dividing mammalian cells.
BMC Research Notes. 2019;12. doi:10.1186/s13104-019-4534-3
apa: Antoniou, M. N., Nicolas, A., Mesnage, R., Biserni, M., Rao, F. V., & Martin,
C. V. (2019). Glyphosate does not substitute for glycine in proteins of actively
dividing mammalian cells. BMC Research Notes. BioMed Central. https://doi.org/10.1186/s13104-019-4534-3
chicago: Antoniou, Michael N., Armel Nicolas, Robin Mesnage, Martina Biserni, Francesco
V. Rao, and Cristina Vazquez Martin. “Glyphosate Does Not Substitute for Glycine
in Proteins of Actively Dividing Mammalian Cells.” BMC Research Notes.
BioMed Central, 2019. https://doi.org/10.1186/s13104-019-4534-3.
ieee: M. N. Antoniou, A. Nicolas, R. Mesnage, M. Biserni, F. V. Rao, and C. V. Martin,
“Glyphosate does not substitute for glycine in proteins of actively dividing mammalian
cells,” BMC Research Notes, vol. 12. BioMed Central, 2019.
ista: Antoniou MN, Nicolas A, Mesnage R, Biserni M, Rao FV, Martin CV. 2019. Glyphosate
does not substitute for glycine in proteins of actively dividing mammalian cells.
BMC Research Notes. 12, 494.
mla: Antoniou, Michael N., et al. “Glyphosate Does Not Substitute for Glycine in
Proteins of Actively Dividing Mammalian Cells.” BMC Research Notes, vol.
12, 494, BioMed Central, 2019, doi:10.1186/s13104-019-4534-3.
short: M.N. Antoniou, A. Nicolas, R. Mesnage, M. Biserni, F.V. Rao, C.V. Martin,
BMC Research Notes 12 (2019).
date_created: 2019-08-18T22:00:39Z
date_published: 2019-08-08T00:00:00Z
date_updated: 2023-02-23T14:08:14Z
day: '08'
ddc:
- '570'
department:
- _id: LifeSc
doi: 10.1186/s13104-019-4534-3
external_id:
pmid:
- '31395095'
file:
- access_level: open_access
checksum: 4a2bb7994b7f2c432bf44f5127ea3102
content_type: application/pdf
creator: dernst
date_created: 2019-08-23T11:10:35Z
date_updated: 2020-07-14T12:47:40Z
file_id: '6829'
file_name: 2019_BMC_Antoniou.pdf
file_size: 1177482
relation: main_file
file_date_updated: 2020-07-14T12:47:40Z
has_accepted_license: '1'
intvolume: ' 12'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
pmid: 1
publication: BMC Research Notes
publication_identifier:
eissn:
- 1756-0500
publication_status: published
publisher: BioMed Central
quality_controlled: '1'
related_material:
record:
- id: '9784'
relation: research_data
status: public
scopus_import: 1
status: public
title: Glyphosate does not substitute for glycine in proteins of actively dividing
mammalian cells
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 12
year: '2019'
...
---
_id: '6822'
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 qualitative winner or quantitative
payoff of the game. In bidding games, in each turn, we hold an auction between
the two players to determine which player moves the token. Bidding games have
largely been studied with concrete bidding mechanisms that are variants of a first-price
auction: in each turn both players simultaneously submit bids, the higher\r\nbidder
moves the token, and pays his bid to the lower bidder in Richman bidding, to the
bank in poorman bidding, and in taxman bidding, the bid is split between the other
player and the bank according to a predefined constant factor. Bidding games are
deterministic games. They have an intriguing connection with a fragment of stochastic
games called \r\n randomturn games. We study, for the first time, a combination
of bidding games with probabilistic behavior; namely, we study bidding games that
are played on Markov decision processes, where the players bid for the right to
choose the next action, which determines the probability distribution according
to which the next vertex is chosen. We study parity and meanpayoff bidding games
on MDPs and extend results from the deterministic bidding setting to the probabilistic
one."
alternative_title:
- LNCS
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
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Petr
full_name: Novotny, Petr
last_name: Novotny
citation:
ama: 'Avni G, Henzinger TA, Ibsen-Jensen R, Novotny P. Bidding games on Markov decision
processes. In: Proceedings of the 13th International Conference of Reachability
Problems. Vol 11674. Springer; 2019:1-12. doi:10.1007/978-3-030-30806-3_1'
apa: 'Avni, G., Henzinger, T. A., Ibsen-Jensen, R., & Novotny, P. (2019). Bidding
games on Markov decision processes. In Proceedings of the 13th International
Conference of Reachability Problems (Vol. 11674, pp. 1–12). Brussels, Belgium:
Springer. https://doi.org/10.1007/978-3-030-30806-3_1'
chicago: Avni, Guy, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Petr Novotny. “Bidding
Games on Markov Decision Processes.” In Proceedings of the 13th International
Conference of Reachability Problems, 11674:1–12. Springer, 2019. https://doi.org/10.1007/978-3-030-30806-3_1.
ieee: G. Avni, T. A. Henzinger, R. Ibsen-Jensen, and P. Novotny, “Bidding games
on Markov decision processes,” in Proceedings of the 13th International Conference
of Reachability Problems, Brussels, Belgium, 2019, vol. 11674, pp. 1–12.
ista: 'Avni G, Henzinger TA, Ibsen-Jensen R, Novotny P. 2019. Bidding games on Markov
decision processes. Proceedings of the 13th International Conference of Reachability
Problems. RP: Reachability Problems, LNCS, vol. 11674, 1–12.'
mla: Avni, Guy, et al. “Bidding Games on Markov Decision Processes.” Proceedings
of the 13th International Conference of Reachability Problems, vol. 11674,
Springer, 2019, pp. 1–12, doi:10.1007/978-3-030-30806-3_1.
short: G. Avni, T.A. Henzinger, R. Ibsen-Jensen, P. Novotny, in:, Proceedings of
the 13th International Conference of Reachability Problems, Springer, 2019, pp.
1–12.
conference:
end_date: 2019-09-13
location: Brussels, Belgium
name: 'RP: Reachability Problems'
start_date: 2019-09-11
date_created: 2019-08-19T07:58:10Z
date_published: 2019-09-06T00:00:00Z
date_updated: 2025-09-10T10:39:56Z
day: '06'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-030-30806-3_1
external_id:
isi:
- '001333747500001'
file:
- access_level: open_access
checksum: 45ebbc709af2b247d28c7c293c01504b
content_type: application/pdf
creator: gavni
date_created: 2019-08-19T07:56:40Z
date_updated: 2020-07-14T12:47:41Z
file_id: '6823'
file_name: prob.pdf
file_size: 436635
relation: main_file
file_date_updated: 2020-07-14T12:47:41Z
has_accepted_license: '1'
intvolume: ' 11674'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Submitted Version
page: 1-12
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: ' Proceedings of the 13th International Conference of Reachability Problems'
publication_identifier:
isbn:
- 978-303030805-6
issn:
- 0302-9743
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Bidding games on Markov decision processes
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 11674
year: '2019'
...