3 Search Results for "Coy, Sam"

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.50

Fully-Scalable MPC Algorithms for Clustering in High Dimension

Authors: Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract

We design new parallel algorithms for clustering in high-dimensional Euclidean spaces. These algorithms run in the Massively Parallel Computation (MPC) model, and are fully scalable, meaning that the local memory in each machine may be n^σ for arbitrarily small fixed σ > 0. Importantly, the local memory may be substantially smaller than the number of clusters k, yet all our algorithms are fast, i.e., run in O(1) rounds. We first devise a fast MPC algorithm for O(1)-approximation of uniform Facility Location. This is the first fully-scalable MPC algorithm that achieves O(1)-approximation for any clustering problem in general geometric setting; previous algorithms only provide poly(log n)-approximation or apply to restricted inputs, like low dimension or small number of clusters k; e.g. [Bhaskara and Wijewardena, ICML'18; Cohen-Addad et al., NeurIPS'21; Cohen-Addad et al., ICML'22]. We then build on this Facility Location result and devise a fast MPC algorithm that achieves O(1)-bicriteria approximation for k-Median and for k-Means, namely, it computes (1+ε)k clusters of cost within O(1/ε²)-factor of the optimum for k clusters. A primary technical tool that we introduce, and may be of independent interest, is a new MPC primitive for geometric aggregation, namely, computing for every data point a statistic of its approximate neighborhood, for statistics like range counting and nearest-neighbor search. Our implementation of this primitive works in high dimension, and is based on consistent hashing (aka sparse partition), a technique that was recently used for streaming algorithms [Czumaj et al., FOCS'22].

Cite as

Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý. Fully-Scalable MPC Algorithms for Clustering in High Dimension. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{czumaj_et_al:LIPIcs.ICALP.2024.50,
  author =	{Czumaj, Artur and Gao, Guichen and Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Vesel\'{y}, Pavel},
  title =	{{Fully-Scalable MPC Algorithms for Clustering in High Dimension}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{50:1--50:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.50},
  URN =		{urn:nbn:de:0030-drops-201938},
  doi =		{10.4230/LIPIcs.ICALP.2024.50},
  annote =	{Keywords: Massively parallel computing, high dimension, facility location, k-median, k-means}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2023.46

Optimal (Degree+1)-Coloring in Congested Clique

Authors: Sam Coy, Artur Czumaj, Peter Davies, and Gopinath Mishra

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

Abstract

We consider the distributed complexity of the (degree+1)-list coloring problem, in which each node u of degree d(u) is assigned a palette of d(u)+1 colors, and the goal is to find a proper coloring using these color palettes. The (degree+1)-list coloring problem is a natural generalization of the classical (Δ+1)-coloring and (Δ+1)-list coloring problems, both being benchmark problems extensively studied in distributed and parallel computing. In this paper we settle the complexity of the (degree+1)-list coloring problem in the Congested Clique model by showing that it can be solved deterministically in a constant number of rounds.

Cite as

Sam Coy, Artur Czumaj, Peter Davies, and Gopinath Mishra. Optimal (Degree+1)-Coloring in Congested Clique. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{coy_et_al:LIPIcs.ICALP.2023.46,
  author =	{Coy, Sam and Czumaj, Artur and Davies, Peter and Mishra, Gopinath},
  title =	{{Optimal (Degree+1)-Coloring in Congested Clique}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{46:1--46: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.46},
  URN =		{urn:nbn:de:0030-drops-180987},
  doi =		{10.4230/LIPIcs.ICALP.2023.46},
  annote =	{Keywords: Distributed computing, graph coloring, parallel computing}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2021.11

Near-Shortest Path Routing in Hybrid Communication Networks

Authors: Sam Coy, Artur Czumaj, Michael Feldmann, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider, and Martijn Struijs

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

Abstract

Hybrid networks, i.e., networks that leverage different means of communication, become ever more widespread. To allow theoretical study of such networks, [Augustine et al., SODA'20] introduced the HYBRID model, which is based on the concept of synchronous message passing and uses two fundamentally different principles of communication: a local mode, which allows every node to exchange one message per round with each neighbor in a local communication graph; and a global mode where any pair of nodes can exchange messages, but only few such exchanges can take place per round. A sizable portion of the previous research for the HYBRID model revolves around basic communication primitives and computing distances or shortest paths in networks. In this paper, we extend this study to a related fundamental problem of computing compact routing schemes for near-shortest paths in the local communication graph. We demonstrate that, for the case where the local communication graph is a unit-disc graph with n nodes that is realized in the plane and has no radio holes, we can deterministically compute a routing scheme that has constant stretch and uses labels and local routing tables of size O(log n) bits in only O(log n) rounds.

Cite as

Sam Coy, Artur Czumaj, Michael Feldmann, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider, and Martijn Struijs. Near-Shortest Path Routing in Hybrid Communication Networks. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{coy_et_al:LIPIcs.OPODIS.2021.11,
  author =	{Coy, Sam and Czumaj, Artur and Feldmann, Michael and Hinnenthal, Kristian and Kuhn, Fabian and Scheideler, Christian and Schneider, Philipp and Struijs, Martijn},
  title =	{{Near-Shortest Path Routing in Hybrid Communication Networks}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{11:1--11:23},
  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.11},
  URN =		{urn:nbn:de:0030-drops-157863},
  doi =		{10.4230/LIPIcs.OPODIS.2021.11},
  annote =	{Keywords: Hybrid networks, overlay networks}
}

Refine by Author
3 Czumaj, Artur
2 Coy, Sam
1 Davies, Peter
1 Feldmann, Michael
1 Gao, Guichen
Show More...

Refine by Classification
2 Theory of computation → Distributed algorithms
2 Theory of computation → Massively parallel algorithms
1 Mathematics of computing → Graph algorithms
1 Theory of computation → Facility location and clustering
1 Theory of computation → Pseudorandomness and derandomization
Show More...

Refine by Keyword
1 Distributed computing
1 Hybrid networks
1 Massively parallel computing
1 facility location
1 graph coloring
Show More...

Refine by Type
3 document

Refine by Publication Year
1 2022
1 2023
1 2024