4 Search Results for "Kahn, Charles M."

Document
DOI: 10.4230/LIPIcs.MFCS.2025.76
Deciding Termination of Simple Randomized Loops

Authors: Éléanore Meyer and Jürgen Giesl

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We show that universal positive almost sure termination (UPAST) is decidable for a class of simple randomized programs, i.e., it is decidable whether the expected runtime of such a program is finite for all inputs. Our class contains all programs that consist of a single loop, with a linear loop guard and a loop body composed of two linear commuting and diagonalizable updates. In each iteration of the loop, the update to be carried out is picked at random, according to a fixed probability. We show the decidability of UPAST for this class of programs, where the program’s variables and inputs may range over various sub-semirings of the real numbers. In this way, we extend a line of research initiated by Tiwari in 2004 into the realm of randomized programs.
Cite as

Éléanore Meyer and Jürgen Giesl. Deciding Termination of Simple Randomized Loops. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 76:1-76:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{meyer_et_al:LIPIcs.MFCS.2025.76,
  author =	{Meyer, \'{E}l\'{e}anore and Giesl, J\"{u}rgen},
  title =	{{Deciding Termination of Simple Randomized Loops}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{76:1--76:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.76},
  URN =		{urn:nbn:de:0030-drops-241833},
  doi =		{10.4230/LIPIcs.MFCS.2025.76},
  annote =	{Keywords: decision procedures, randomized programs, linear loops, positive almost sure termination}
}
Document
DOI: 10.4230/LIPIcs.WABI.2025.10
DiVerG: Scalable Distance Index for Validation of Paired-End Alignments in Sequence Graphs

Authors: Ali Ghaffaari, Alexander Schönhuth, and Tobias Marschall

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract
Determining the distance between two loci within a genomic region is a recurrent operation in various tasks in computational genomics. A notable example of this task arises in paired-end read mapping as a form of validation of distances between multiple alignments. While straightforward for a single genome, graph-based reference structures render the operation considerably more involved. Given the sheer number of such queries in a typical read mapping experiment, an efficient algorithm for answering distance queries is crucial. In this paper, we introduce DiVerG, a compact data structure as well as a fast and scalable algorithm, for constructing distance indexes for general sequence graphs on multi-core CPU and many-core GPU architectures. DiVerG is based on PairG [Jain et al., 2019], but overcomes the limitations of PairG by exploiting the extensive potential for improvements in terms of scalability and space efficiency. As a consequence, DiVerG can process substantially larger datasets, such as whole human genomes, which are unmanageable by PairG. DiVerG offers faster index construction time and consistently faster query time with gains proportional to the size of the underlying compact data structure. We demonstrate that our method performs favorably on multiple real datasets at various scales. DiVerG achieves superior performance over PairG; e.g. resulting to 2.5-4x speed-up in query time, 44-340x smaller index size, and 3-50x faster construction time for the genome graph of the MHC region, as a particularly variable region of the human genome. The implementation is available at: https://github.com/cartoonist/diverg
Cite as

Ali Ghaffaari, Alexander Schönhuth, and Tobias Marschall. DiVerG: Scalable Distance Index for Validation of Paired-End Alignments in Sequence Graphs. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 10:1-10:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ghaffaari_et_al:LIPIcs.WABI.2025.10,
  author =	{Ghaffaari, Ali and Sch\"{o}nhuth, Alexander and Marschall, Tobias},
  title =	{{DiVerG: Scalable Distance Index for Validation of Paired-End Alignments in Sequence Graphs}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{10:1--10:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.10},
  URN =		{urn:nbn:de:0030-drops-239369},
  doi =		{10.4230/LIPIcs.WABI.2025.10},
  annote =	{Keywords: Sequence graph, distance index, read mapping, sparse matrix}
}
Document
Extended Abstract
DOI: 10.4230/OASIcs.Tokenomics.2022.8
The Demand for Programmable Payments: Extended Abstract (Extended Abstract)

Authors: Charles M. Kahn and Maarten R.C. van Oordt

Published in: OASIcs, Volume 110, 4th International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2022)

Abstract
In [Kahn and Van Oordt, 2022], we examine the desirability of programmable payments, arrangements in which transfers are automatically executed conditional upon preset objective criteria. We study optimal payment arrangements in a continuous-time framework where a buyer and a seller of a service interact. We stack the cards in favor of programmable payments by considering an environment where neither agent has any legal recourse if the other fails to deliver upon their promises. We identify scenarios where programmable payments could improve economic outcomes and scenarios where they cannot. Direct payments increase the surplus by avoiding the liquidity cost of locking-up funds in a programmable payment arrangement until the moment where the conditions are satisfied to release those funds to the payee. Programmable payments will be desirable, and may in fact be the only viable payment arrangement, in situations where economic relationships are of a short duration. Nonetheless, there is a limit to the length of the arrangement a single programmable payment can support, because eventually the additional liquidity cost of locking up more funds for a longer period starts to exceed the additional surplus generated from extending the length of the arrangement. For longer periods multiple payments are necessary. Sufficiently long optimal chain-of-payments arrangements always start with direct payments because of the lower liquidity costs. Only towards the end of a relationship do the parties switch to the use of programmable payments. Moreover, the optimum for infinitely long payment arrangements consists of direct payments only. These results suggest that programmable payments are unlikely to become the new "standard" for all payment arrangements. Many have argued that technological developments in the payments space will lead to an explosion of so-called micro-payments. Our results suggest a more complex relationship between transactions cost and the number of payments. Lower transaction costs increase the number of payments for the extensive margin in the sense of increasing the set of potential buyer-seller pairs where transaction costs are no longer prohibitively expensive. For the intensive margin, that is, within buyer-seller pairs, we find the opposite effect: lower transaction costs are associated with fewer payments, as trust becomes easier to achieve.
Cite as

Charles M. Kahn and Maarten R.C. van Oordt. The Demand for Programmable Payments: Extended Abstract (Extended Abstract). In 4th International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2022). Open Access Series in Informatics (OASIcs), Volume 110, p. 8:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kahn_et_al:OASIcs.Tokenomics.2022.8,
  author =	{Kahn, Charles M. and Oordt, Maarten R.C. van},
  title =	{{The Demand for Programmable Payments: Extended Abstract}},
  booktitle =	{4th International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2022)},
  pages =	{8:1--8:1},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-274-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{110},
  editor =	{Amoussou-Guenou, Yackolley and Kiayias, Aggelos and Verdier, Marianne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2022.8},
  URN =		{urn:nbn:de:0030-drops-184255},
  doi =		{10.4230/OASIcs.Tokenomics.2022.8},
  annote =	{Keywords: Electronic payment, smart contracts, programmable payment}
}
Document
Extended Abstract
DOI: 10.4230/OASIcs.Tokenomics.2021.7
Best Before? Expiring Central Bank Digital Currency and Loss Recovery (Extended Abstract)

Authors: Charles M. Kahn, Maarten R.C. van Oordt, and Yu Zhu

Published in: OASIcs, Volume 97, 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)

Abstract
An important feature of physical cash payments is resilience, due to their independence of power outages or network coverage. Many central banks are exploring issuing digital cash substitutes with similar offline payment functionality. Such substitutes could incorporate novel features making them more desirable than physical cash. This paper considers introducing an expiry date for offline digital currency balances to automate personal loss recovery. We show this functionality could increase consumer demand for digital cash, with the time to expiration playing a key role. The optimal time to expiration should have short wait time to get lost money reimbursed but leave enough time for agents to deposit received offline balances. Setting the time to expiration a bit too long has minor impact on welfare but setting it too short dramatically reduce welfare. If the offline device provides information about past transactions to the central bank, the accuracy of loss recovery can be improved but welfare can decrease.
Cite as

Charles M. Kahn, Maarten R.C. van Oordt, and Yu Zhu. Best Before? Expiring Central Bank Digital Currency and Loss Recovery (Extended Abstract). In 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021). Open Access Series in Informatics (OASIcs), Volume 97, p. 7:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kahn_et_al:OASIcs.Tokenomics.2021.7,
  author =	{Kahn, Charles M. and van Oordt, Maarten R.C. and Zhu, Yu},
  title =	{{Best Before? Expiring Central Bank Digital Currency and Loss Recovery}},
  booktitle =	{3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)},
  pages =	{7:1--7:1},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-220-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{97},
  editor =	{Gramoli, Vincent and Halaburda, Hanna and Pass, Rafael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2021.7},
  URN =		{urn:nbn:de:0030-drops-159040},
  doi =		{10.4230/OASIcs.Tokenomics.2021.7},
  annote =	{Keywords: Central Bank Digital Currency, Design, Offline Payments, Operational Resilience, Financial Inclusion}
}
  • Refine by Type
  • 4 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2023
  • 1 2022

  • Refine by Author
  • 2 Kahn, Charles M.
  • 1 Ghaffaari, Ali
  • 1 Giesl, Jürgen
  • 1 Marschall, Tobias
  • 1 Meyer, Éléanore
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs
  • 2 OASIcs

  • Refine by Classification
  • 1 Applied computing → Computational genomics
  • 1 Applied computing → Digital cash
  • 1 Applied computing → E-commerce infrastructure
  • 1 Applied computing → Electronic funds transfer
  • 1 Applied computing → Online banking
  • Show More...

  • Refine by Keyword
  • 1 Central Bank Digital Currency
  • 1 Design
  • 1 Electronic payment
  • 1 Financial Inclusion
  • 1 Offline Payments
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact