Search Results

Documents authored by Křišťan, Jan Matyáš

Document
DOI: 10.4230/LIPIcs.DISC.2025.23
Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection

Authors: Krishnendu Chatterjee, Jan Matyáš Křišťan, Stefan Schmid, Jakub Svoboda, and Michelle Yeo

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Payment channel networks (PCNs) are a promising technology that alleviates blockchain scalability by shifting the transaction load from the blockchain to the PCN. Nevertheless, the network topology has to be carefully designed to maximise the transaction throughput in PCNs. Additionally, users in PCNs also have to make optimal decisions on which transactions to forward and which to reject to prolong the lifetime of their channels. In this work, we consider an input sequence of transactions over p parties. Each transaction consists of a transaction size, source, and target, and can be either accepted or rejected (entailing a cost). The goal is to design a PCN topology among the p cooperating parties, along with the channel capacities, and then output a decision for each transaction in the sequence to minimise the cost of creating and augmenting channels, as well as the cost of rejecting transactions. Our main contribution is an 𝒪(p) approximation algorithm for the problem with p parties. We further show that with some assumptions on the distribution of transactions, we can reduce the approximation ratio to 𝒪(√p). We complement our theoretical analysis with an empirical study of our assumptions and approach in the context of the Lightning Network.
Cite as

Krishnendu Chatterjee, Jan Matyáš Křišťan, Stefan Schmid, Jakub Svoboda, and Michelle Yeo. Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.DISC.2025.23,
  author =	{Chatterjee, Krishnendu and K\v{r}i\v{s}\v{t}an, Jan Maty\'{a}\v{s} and Schmid, Stefan and Svoboda, Jakub and Yeo, Michelle},
  title =	{{Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.23},
  URN =		{urn:nbn:de:0030-drops-248402},
  doi =		{10.4230/LIPIcs.DISC.2025.23},
  annote =	{Keywords: Blockchains, Cryptocurrencies, Payment Channel Networks, Throughput, Optimisation, Graph Algorithms, Approximation Algorithms}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2024.49
Brief Announcement: Decreasing Verification Radius in Local Certification

Authors: Jan Matyáš Křišťan and Josef Erik Sedláček

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
This paper deals with local certification, specifically locally checkable proofs: given a graph property, the task is to certify whether a graph satisfies the property. The verification of this certification needs to be done locally without the knowledge of the whole graph. We examine the trade-off between the visibility radius and the size of certificates. We describe a procedure that decreases the radius by encoding the neighbourhood of each vertex into its certificate. We also provide a corresponding lower bound on the required certificate size increase, showing that such an approach is close to optimal.
Cite as

Jan Matyáš Křišťan and Josef Erik Sedláček. Brief Announcement: Decreasing Verification Radius in Local Certification. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 49:1-49:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kristan_et_al:LIPIcs.DISC.2024.49,
  author =	{K\v{r}i\v{s}\v{t}an, Jan Maty\'{a}\v{s} and Sedl\'{a}\v{c}ek, Josef Erik},
  title =	{{Brief Announcement: Decreasing Verification Radius in Local Certification}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{49:1--49:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.49},
  URN =		{urn:nbn:de:0030-drops-212773},
  doi =		{10.4230/LIPIcs.DISC.2024.49},
  annote =	{Keywords: Local certification, locally checkable proofs, proof-labeling schemes, graphs, distributed computing}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.54
Romeo and Juliet Is EXPTIME-Complete

Authors: Harmender Gahlawat, Jan Matyáš Křišťan, and Tomáš Valla

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Romeo and Juliet is a two player Rendezvous game played on graphs where one player controls two agents, Romeo (ℛ) and Juliet (𝒥) who aim to meet at a vertex against k adversaries, called dividers, controlled by the other player. The optimization in this game lies at deciding the minimum number of dividers sufficient to restrict ℛ and 𝒥 from meeting in a graph, called the dynamic separation number. We establish that Romeo and Juliet is EXPTIME-complete, settling a conjecture of Fomin, Golovach, and Thilikos [Inf. and Comp., 2023] positively. We also consider the game for directed graphs and establish that although the game is EXPTIME-complete for general directed graphs, it is PSPACE-complete and co-W[2]-hard for directed acyclic graphs.
Cite as

Harmender Gahlawat, Jan Matyáš Křišťan, and Tomáš Valla. Romeo and Juliet Is EXPTIME-Complete. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gahlawat_et_al:LIPIcs.MFCS.2024.54,
  author =	{Gahlawat, Harmender and K\v{r}i\v{s}\v{t}an, Jan Maty\'{a}\v{s} and Valla, Tom\'{a}\v{s}},
  title =	{{Romeo and Juliet Is EXPTIME-Complete}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{54:1--54:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.54},
  URN =		{urn:nbn:de:0030-drops-206106},
  doi =		{10.4230/LIPIcs.MFCS.2024.54},
  annote =	{Keywords: Rendezvous Games on graphs, EXPTIME-completeness, Dynamic Separators}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact