6 Search Results for "Studený, Jan"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.10
Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms

Authors: Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, Joona Särkijärvi, and Jukka Suomela

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
In this work, we give a unifying view of locality in four settings: distributed algorithms, sequential greedy algorithms, dynamic algorithms, and online algorithms. We introduce a new model of computing, called the online-LOCAL model: the adversary presents the nodes of the input graph one by one, in the same way as in classical online algorithms, but for each node we get to see its radius-T neighborhood before choosing the output. Instead of looking ahead in time, we have the power of looking around in space. We compare the online-LOCAL model with three other models: the LOCAL model of distributed computing, where each node produces its output based on its radius-T neighborhood, the SLOCAL model, which is the sequential counterpart of LOCAL, and the dynamic-LOCAL model, where changes in the dynamic input graph only influence the radius-T neighborhood of the point of change. The SLOCAL and dynamic-LOCAL models are sandwiched between the LOCAL and online-LOCAL models. In general, all four models are distinct, but we study in particular locally checkable labeling problems (LCLs), which is a family of graph problems extensively studied in the context of distributed graph algorithms. We prove that for LCL problems in paths, cycles, and rooted trees, all four models are roughly equivalent: the locality of any LCL problem falls in the same broad class - O(log* n), Θ(log n), or n^Θ(1) - in all four models. In particular, this result enables one to generalize prior lower-bound results from the LOCAL model to all four models, and it also allows one to simulate e.g. dynamic-LOCAL algorithms efficiently in the LOCAL model. We also show that this equivalence does not hold in two-dimensional grids or general bipartite graphs. We provide an online-LOCAL algorithm with locality O(log n) for the 3-coloring problem in bipartite graphs - this is a problem with locality Ω(n^{1/2}) in the LOCAL model and Ω(n^{1/10}) in the SLOCAL model.
Cite as

Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, Joona Särkijärvi, and Jukka Suomela. Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{akbari_et_al:LIPIcs.ICALP.2023.10,
  author =	{Akbari, Amirreza and Eslami, Navid and Lievonen, Henrik and Melnyk, Darya and S\"{a}rkij\"{a}rvi, Joona and Suomela, Jukka},
  title =	{{Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.10},
  URN =		{urn:nbn:de:0030-drops-180627},
  doi =		{10.4230/LIPIcs.ICALP.2023.10},
  annote =	{Keywords: Online computation, spatial advice, distributed algorithms, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.8
Efficient Classification of Locally Checkable Problems in Regular Trees

Authors: Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, and Jukka Suomela

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
We give practical, efficient algorithms that automatically determine the asymptotic distributed round complexity of a given locally checkable graph problem in the [Θ(log n), Θ(n)] region, in two settings. We present one algorithm for unrooted regular trees and another algorithm for rooted regular trees. The algorithms take the description of a locally checkable labeling problem as input, and the running time is polynomial in the size of the problem description. The algorithms decide if the problem is solvable in O(log n) rounds. If not, it is known that the complexity has to be Θ(n^{1/k}) for some k = 1, 2, ..., and in this case the algorithms also output the right value of the exponent k. In rooted trees in the O(log n) case we can then further determine the exact complexity class by using algorithms from prior work; for unrooted trees the more fine-grained classification in the O(log n) region remains an open question.
Cite as

Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, and Jukka Suomela. Efficient Classification of Locally Checkable Problems in Regular Trees. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.DISC.2022.8,
  author =	{Balliu, Alkida and Brandt, Sebastian and Chang, Yi-Jun and Olivetti, Dennis and Studen\'{y}, Jan and Suomela, Jukka},
  title =	{{Efficient Classification of Locally Checkable Problems in Regular Trees}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.8},
  URN =		{urn:nbn:de:0030-drops-171993},
  doi =		{10.4230/LIPIcs.DISC.2022.8},
  annote =	{Keywords: locally checkable labeling, locality, distributed computational complexity}
}
Document
DOI: 10.4230/LIPIcs.WABI.2021.13
Compressing and Indexing Aligned Readsets

Authors: Travis Gagie, Garance Gourdel, and Giovanni Manzini

Published in: LIPIcs, Volume 201, 21st International Workshop on Algorithms in Bioinformatics (WABI 2021)

Abstract
Compressed full-text indexes are one of the main success stories of bioinformatics data structures but even they struggle to handle some DNA readsets. This may seem surprising since, at least when dealing with short reads from the same individual, the readset will be highly repetitive and, thus, highly compressible. If we are not careful, however, this advantage can be more than offset by two disadvantages: first, since most base pairs are included in at least tens reads each, the uncompressed readset is likely to be at least an order of magnitude larger than the individual’s uncompressed genome; second, these indexes usually pay some space overhead for each string they store, and the total overhead can be substantial when dealing with millions of reads. The most successful compressed full-text indexes for readsets so far are based on the Extended Burrows-Wheeler Transform (EBWT) and use a sorting heuristic to try to reduce the space overhead per read, but they still treat the reads as separate strings and thus may not take full advantage of the readset’s structure. For example, if we have already assembled an individual’s genome from the readset, then we can usually use it to compress the readset well: e.g., we store the gap-coded list of reads' starting positions; we store the list of their lengths, which is often highly compressible; and we store information about the sequencing errors, which are rare with short reads. There is nowhere, however, where we can plug an assembled genome into the EBWT. In this paper we show how to use one or more assembled or partially assembled genome as the basis for a compressed full-text index of its readset. Specifically, we build a labelled tree by taking the assembled genome as a trunk and grafting onto it the reads that align to it, at the starting positions of their alignments. Next, we compute the eXtended Burrows-Wheeler Transform (XBWT) of the resulting labelled tree and build a compressed full-text index on that. Although this index can occasionally return false positives, it is usually much more compact than the alternatives. Following the established practice for datasets with many repetitions, we compare different full-text indices by looking at the number of runs in the transformed strings. For a human Chr19 readset our preliminary experiments show that eliminating separators characters from the EBWT reduces the number of runs by 19%, from 220 million to 178 million, and using the XBWT reduces it by a further 15%, to 150 million.
Cite as

Travis Gagie, Garance Gourdel, and Giovanni Manzini. Compressing and Indexing Aligned Readsets. In 21st International Workshop on Algorithms in Bioinformatics (WABI 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 201, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gagie_et_al:LIPIcs.WABI.2021.13,
  author =	{Gagie, Travis and Gourdel, Garance and Manzini, Giovanni},
  title =	{{Compressing and Indexing Aligned Readsets}},
  booktitle =	{21st International Workshop on Algorithms in Bioinformatics (WABI 2021)},
  pages =	{13:1--13:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-200-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{201},
  editor =	{Carbone, Alessandra and El-Kebir, Mohammed},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2021.13},
  URN =		{urn:nbn:de:0030-drops-143660},
  doi =		{10.4230/LIPIcs.WABI.2021.13},
  annote =	{Keywords: data compression, compact data structures, FM-index, Burrows-Wheeler Transform, EBWT, XBWT, DNA reads}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.17
Classification of Distributed Binary Labeling Problems

Authors: Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, perfect matching, and the task of coloring edges red and blue such that all nodes are incident to at least one red and at least one blue edge. More generally, we can encode e.g. any cardinality constraints on indegrees and outdegrees. We study the deterministic time complexity of solving a given binary labeling problem in trees, in the usual LOCAL model of distributed computing. We show that the complexity of any such problem is in one of the following classes: O(1), Θ(log n), Θ(n), or unsolvable. In particular, a problem that can be represented in the binary labeling formalism cannot have time complexity Θ(log^* n), and hence we know that e.g. any encoding of maximal matchings has to use at least three labels (which is tight). Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it. Hence the distributed time complexity of binary labeling problems is decidable, not only in principle, but also in practice: there is a simple and efficient algorithm that takes the description of a binary labeling problem and outputs its distributed time complexity.
Cite as

Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Classification of Distributed Binary Labeling Problems. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.DISC.2020.17,
  author =	{Balliu, Alkida and Brandt, Sebastian and Efron, Yuval and Hirvonen, Juho and Maus, Yannic and Olivetti, Dennis and Suomela, Jukka},
  title =	{{Classification of Distributed Binary Labeling Problems}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.17},
  URN =		{urn:nbn:de:0030-drops-130957},
  doi =		{10.4230/LIPIcs.DISC.2020.17},
  annote =	{Keywords: LOCAL model, graph problems, locally checkable labeling problems, distributed computational complexity}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.41
Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens

Authors: Yi-Jun Chang, Jan Studený, and Jukka Suomela

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
We study the following algorithm synthesis question: given the description of a locally checkable graph problem Π for paths or cycles, determine in which instances Π is solvable, determine what is the locality of Π, and construct an asymptotically optimal distributed algorithm for solving Π (in the usual LOCAL model of distributed computing). To answer such questions, we represent Π as a nondeterministic finite automaton ℳ over a unary alphabet, and identify polynomial-time-computable properties of automaton ℳ that capture the locality and solvability of problem Π.
Cite as

Yi-Jun Chang, Jan Studený, and Jukka Suomela. Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 41:1-41:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.DISC.2020.41,
  author =	{Chang, Yi-Jun and Studen\'{y}, Jan and Suomela, Jukka},
  title =	{{Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{41:1--41:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.41},
  URN =		{urn:nbn:de:0030-drops-131197},
  doi =		{10.4230/LIPIcs.DISC.2020.41},
  annote =	{Keywords: Algorithm synthesis, locally checkable labeling problems, LOCAL model, locality, distributed computational complexity, nondeterministic finite automata}
}
Document
DOI: 10.4230/LIPIcs.CPM.2019.15
Approximating Approximate Pattern Matching

Authors: Jan Studený and Przemysław Uznański

Published in: LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)

Abstract
Given a text T of length n and a pattern P of length m, the approximate pattern matching problem asks for computation of a particular distance function between P and every m-substring of T. We consider a (1 +/- epsilon) multiplicative approximation variant of this problem, for l_p distance function. In this paper, we describe two (1+epsilon)-approximate algorithms with a runtime of O~(n/epsilon) for all (constant) non-negative values of p. For constant p >= 1 we show a deterministic (1+epsilon)-approximation algorithm. Previously, such run time was known only for the case of l_1 distance, by Gawrychowski and Uznański [ICALP 2018] and only with a randomized algorithm. For constant 0 <= p <= 1 we show a randomized algorithm for the l_p, thereby providing a smooth tradeoff between algorithms of Kopelowitz and Porat [FOCS 2015, SOSA 2018] for Hamming distance (case of p=0) and of Gawrychowski and Uznański for l_1 distance.
Cite as

Jan Studený and Przemysław Uznański. Approximating Approximate Pattern Matching. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{studeny_et_al:LIPIcs.CPM.2019.15,
  author =	{Studen\'{y}, Jan and Uzna\'{n}ski, Przemys{\l}aw},
  title =	{{Approximating Approximate Pattern Matching}},
  booktitle =	{30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
  pages =	{15:1--15:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-103-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{128},
  editor =	{Pisanti, Nadia and P. Pissis, Solon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.15},
  URN =		{urn:nbn:de:0030-drops-104865},
  doi =		{10.4230/LIPIcs.CPM.2019.15},
  annote =	{Keywords: Approximate Pattern Matching, l\underlinep Distance, l\underline1 Distance, Hamming Distance, Approximation Algorithms}
}
  • Refine by Author
  • 4 Suomela, Jukka
  • 3 Studený, Jan
  • 2 Balliu, Alkida
  • 2 Brandt, Sebastian
  • 2 Chang, Yi-Jun
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Distributed algorithms
  • 1 Computing methodologies → Distributed algorithms
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Data compression
  • 1 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 3 distributed computational complexity
  • 2 LOCAL model
  • 2 locality
  • 2 locally checkable labeling problems
  • 1 Algorithm synthesis
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2020
  • 1 2019
  • 1 2021
  • 1 2022
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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