4 Search Results for "Rozhoň, Václav"


Document
Noisy k-Means++ Revisited

Authors: Christoph Grunau, Ahmet Alper Özüdoğru, and Václav Rozhoň

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)


Abstract
The k-means++ algorithm by Arthur and Vassilvitskii [SODA 2007] is a classical and time-tested algorithm for the k-means problem. While being very practical, the algorithm also has good theoretical guarantees: its solution is O(log k)-approximate, in expectation. In a recent work, Bhattacharya, Eube, Roglin, and Schmidt [ESA 2020] considered the following question: does the algorithm retain its guarantees if we allow for a slight adversarial noise in the sampling probability distributions used by the algorithm? This is motivated e.g. by the fact that computations with real numbers in k-means++ implementations are inexact. Surprisingly, the analysis under this scenario gets substantially more difficult and the authors were able to prove only a weaker approximation guarantee of O(log² k). In this paper, we close the gap by providing a tight, O(log k)-approximate guarantee for the k-means++ algorithm with noise.

Cite as

Christoph Grunau, Ahmet Alper Özüdoğru, and Václav Rozhoň. Noisy k-Means++ Revisited. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 55:1-55:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{grunau_et_al:LIPIcs.ESA.2023.55,
  author =	{Grunau, Christoph and \"{O}z\"{u}do\u{g}ru, Ahmet Alper and Rozho\v{n}, V\'{a}clav},
  title =	{{Noisy k-Means++ Revisited}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{55:1--55:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.55},
  URN =		{urn:nbn:de:0030-drops-187080},
  doi =		{10.4230/LIPIcs.ESA.2023.55},
  annote =	{Keywords: clustering, k-means, k-means++, adversarial noise}
}
Document
Track A: Algorithms, Complexity and Games
Approximate Triangle Counting via Sampling and Fast Matrix Multiplication

Authors: Jakub Tětek

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
There is a simple O(n³/{ε²T}) time algorithm for 1±ε-approximate triangle counting where T is the number of triangles in the graph and n the number of vertices. At the same time, one may count triangles exactly using fast matrix multiplication in time Õ(n^ω). Is it possible to get a negative dependency on the number of triangles T while retaining the state-of-the-art n^ω dependency on n? We answer this question positively by providing an algorithm which runs in time O({n^ω}/T^{ω-2})⋅poly(n^o(1)/ε). This is optimal in the sense that as long as the exponent of T is independent of n, T, it cannot be improved while retaining the dependency on n. Our algorithm improves upon the state of the art when T ≫ 1 and T ≪ n. We also consider the problem of approximate triangle counting in sparse graphs, parameterized by the number of edges m. The best known algorithm runs in time Õ_ε(m^{3/2}/T) [Eden et al., SIAM Journal on Computing, 2017]. An algorithm by Alon et al. [JACM, 1995] for exact triangle counting that runs in time Õ(m^{2ω/(ω + 1)}). We again get an algorithm whose complexity has a state-of-the-art dependency on m while having negative dependency on T. Specifically, our algorithm runs in time O({m^{2ω/(ω+1)}}/{T^{2(ω-1)/(ω+1)}}) ⋅ poly(n^o(1)/ε). This is again optimal in the sense that no better constant exponent of T is possible without worsening the dependency on m. This algorithm improves upon the state of the art when T ≫ 1 and T ≪ √m. In both cases, algorithms with time complexity matching query complexity lower bounds were known on some range of parameters. While those algorithms have optimal query complexity for the whole range of T, the time complexity departs from the query complexity and is no longer optimal (as we show) for T ≪ n and T ≪ √m, respectively. We focus on the time complexity in this range of T. To the best of our knowledge, this is the first paper considering the discrepancy between query and time complexity in graph parameter estimation.

Cite as

Jakub Tětek. Approximate Triangle Counting via Sampling and Fast Matrix Multiplication. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 107:1-107:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{tetek:LIPIcs.ICALP.2022.107,
  author =	{T\v{e}tek, Jakub},
  title =	{{Approximate Triangle Counting via Sampling and Fast Matrix Multiplication}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{107:1--107:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.107},
  URN =		{urn:nbn:de:0030-drops-164485},
  doi =		{10.4230/LIPIcs.ICALP.2022.107},
  annote =	{Keywords: Approximate triangle counting, Fast matrix multiplication, Sampling}
}
Document
Distributed Recoloring of Interval and Chordal Graphs

Authors: Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich, and Mikaël Rabie

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)


Abstract
One of the fundamental and most-studied algorithmic problems in distributed computing on networks is graph coloring, both in bounded-degree and in general graphs. Recently, the study of this problem has been extended in two directions. First, the problem of recoloring, that is computing an efficient transformation between two given colorings (instead of computing a new coloring), has been considered, both to model radio network updates, and as a useful subroutine for coloring. Second, as it appears that general graphs and bounded-degree graphs do not model real networks very well (with, respectively, pathological worst-case topologies and too strong assumptions), coloring has been studied in more specific graph classes. In this paper, we study the intersection of these two directions: distributed recoloring in two relevant graph classes, interval and chordal graphs. More formally, the question of recoloring a graph is as follows: we are given a network, an input coloring α and a target coloring β, and we want to find a schedule of colorings to reach β starting from α. In a distributed setting, the schedule needs to be found within the LOCAL model, where nodes communicate with their direct neighbors synchronously. The question we want to answer is: how many rounds of communication {are} needed to produce a schedule, and what is the length of this schedule? In the case of interval and chordal graphs, we prove that, if we have less than 2ω colors, ω being the size of the largest clique, extra colors will be needed in the intermediate colorings. For interval graphs, we produce a schedule after O(poly(Δ)log*n) rounds of communication, and for chordal graphs, we need O(ω²Δ²log n) rounds to get one. Our techniques also improve classic coloring algorithms. Namely, we get ω+1-colorings of interval graphs in O(ωlog*n) rounds and of chordal graphs in O(ωlog n) rounds, which improves on previous known algorithms that use ω+2 colors for the same running times.

Cite as

Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich, and Mikaël Rabie. Distributed Recoloring of Interval and Chordal Graphs. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.OPODIS.2021.19,
  author =	{Bousquet, Nicolas and Feuilloley, Laurent and Heinrich, Marc and Rabie, Mika\"{e}l},
  title =	{{Distributed Recoloring of Interval and Chordal Graphs}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.19},
  URN =		{urn:nbn:de:0030-drops-157941},
  doi =		{10.4230/LIPIcs.OPODIS.2021.19},
  annote =	{Keywords: Distributed coloring, distributed recoloring, interval graphs, chordal graphs, intersection graphs}
}
Document
Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics

Authors: Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhoň, and Zoltán Vidnyánszky

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
We study connections between three different fields: distributed local algorithms, finitary factors of iid processes, and descriptive combinatorics. We focus on two central questions: Can we apply techniques from one of the areas to obtain results in another? Can we show that complexity classes coming from different areas contain precisely the same problems? We give an affirmative answer to both questions in the context of local problems on regular trees: 1) We extend the Borel determinacy technique of Marks [Marks - J. Am. Math. Soc. 2016] coming from descriptive combinatorics and adapt it to the area of distributed computing, thereby obtaining a more generally applicable lower bound technique in descriptive combinatorics and an entirely new lower bound technique for distributed algorithms. Using our new technique, we prove deterministic distributed Ω(log n)-round lower bounds for problems from a natural class of homomorphism problems. Interestingly, these lower bounds seem beyond the current reach of the powerful round elimination technique [Brandt - PODC 2019] responsible for all substantial locality lower bounds of the last years. Our key technical ingredient is a novel ID graph technique that we expect to be of independent interest; in fact, it has already played an important role in a new lower bound for the Lovász local lemma in the Local Computation Algorithms model from sequential computing [Brandt, Grunau, Rozhoň - PODC 2021]. 2) We prove that a local problem admits a Baire measurable coloring if and only if it admits a local algorithm with local complexity O(log n), extending the classification of Baire measurable colorings of Bernshteyn [Bernshteyn - personal communication]. A key ingredient of the proof is a new and simple characterization of local problems that can be solved in O(log n) rounds. We complement this result by showing separations between complexity classes from distributed computing, finitary factors, and descriptive combinatorics. Most notably, the class of problems that allow a distributed algorithm with sublogarithmic randomized local complexity is incomparable with the class of problems with a Borel solution. We hope that our treatment will help to view all three perspectives as part of a common theory of locality, in which we follow the insightful paper of [Bernshteyn - arXiv 2004.04905].

Cite as

Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhoň, and Zoltán Vidnyánszky. Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 29:1-29:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{brandt_et_al:LIPIcs.ITCS.2022.29,
  author =	{Brandt, Sebastian and Chang, Yi-Jun and Greb{\'\i}k, Jan and Grunau, Christoph and Rozho\v{n}, V\'{a}clav and Vidny\'{a}nszky, Zolt\'{a}n},
  title =	{{Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{29:1--29:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.29},
  URN =		{urn:nbn:de:0030-drops-156259},
  doi =		{10.4230/LIPIcs.ITCS.2022.29},
  annote =	{Keywords: Distributed Algorithms, Descriptive Combinatorics}
}
  • Refine by Author
  • 2 Grunau, Christoph
  • 2 Rozhoň, Václav
  • 1 Bousquet, Nicolas
  • 1 Brandt, Sebastian
  • 1 Chang, Yi-Jun
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Sketching and sampling
  • 1 Theory of computation → Unsupervised learning and clustering

  • Refine by Keyword
  • 1 Approximate triangle counting
  • 1 Descriptive Combinatorics
  • 1 Distributed Algorithms
  • 1 Distributed coloring
  • 1 Fast matrix multiplication
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 3 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