5 Search Results for "Bury, Marc"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.82
Dimension Reduction for Clustering: The Curious Case of Discrete Centers

Authors: Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir, Sandeep Silwal, and Di Yue

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
The Johnson-Lindenstrauss transform is a fundamental method for dimension reduction in Euclidean spaces, that can map any dataset of n points into dimension O(log n) with low distortion of their distances. This dimension bound is tight in general, but one can bypass it for specific problems. Indeed, tremendous progress has been made for clustering problems, especially in the continuous setting where centers can be picked from the ambient space ℝ^d. Most notably, for k-median and k-means, the dimension bound was improved to O(log k) [Makarychev, Makarychev and Razenshteyn, STOC 2019]. We explore dimension reduction for clustering in the discrete setting, where centers can only be picked from the dataset, and present two results that are both parameterized by the doubling dimension of the dataset, denoted as ddim. The first result shows that dimension O_{ε}(ddim + log k + log log n) suffices, and is moreover tight, to guarantee that the cost is preserved within factor 1±ε for every set of centers. Our second result eliminates the log log n term in the dimension through a relaxation of the guarantee (namely, preserving the cost only for all approximately-optimal sets of centers), which maintains its usefulness for downstream applications. Overall, we achieve strong dimension reduction in the discrete setting, and find that it differs from the continuous setting not only in the dimension bound, which depends on the doubling dimension, but also in the guarantees beyond preserving the optimal value, such as which clusterings are preserved.
Cite as

Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir, Sandeep Silwal, and Di Yue. Dimension Reduction for Clustering: The Curious Case of Discrete Centers. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 82:1-82:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jiang_et_al:LIPIcs.ITCS.2026.82,
  author =	{Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Sapir, Shay and Silwal, Sandeep and Yue, Di},
  title =	{{Dimension Reduction for Clustering: The Curious Case of Discrete Centers}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{82:1--82:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.82},
  URN =		{urn:nbn:de:0030-drops-253698},
  doi =		{10.4230/LIPIcs.ITCS.2026.82},
  annote =	{Keywords: dimension reduction, clustering, k-median, k-means, doubling dimension}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.40
On the Randomized Locality of Matching Problems in Regular Graphs

Authors: Seri Khoury, Manish Purohit, Aaron Schild, and Joshua R. Wang

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

Abstract
The main goal in distributed symmetry-breaking is to understand the locality of problems: the radius of the neighborhood that a node must explore to determine its part of a global solution. In this work, we study the locality of matching problems in the family of regular graphs, which is one of the main benchmarks for establishing lower bounds on the locality of symmetry-breaking problems, as well as for obtaining classification results. Our main results are summarized as follows: 1) Approximate matching: We develop randomized algorithms to show that (1 + ε)-approximate matching in regular graphs is truly local, i.e., the locality depends only on ε and is independent of all other graph parameters. Furthermore, as long as the degree Δ is not very small (namely, as long as Δ ≥ poly(1/ε)), this dependence is only logarithmic in 1/ε. This stands in sharp contrast to maximal matching in regular graphs which requires some dependence on the number of nodes n or the degree Δ. 2) Maximal matching: Our techniques further allow us to establish a strong separation between the node-averaged complexity and worst-case complexity of maximal matching in regular graphs, by showing that the former is only O(1). Central to our main technical contribution is a novel martingale-based analysis for the ≈ 40-year-old algorithm by Luby. In particular, our analysis shows that applying one round of Luby’s algorithm on the line graph of a Δ-regular graph results in an almost Δ/2-regular graph.
Cite as

Seri Khoury, Manish Purohit, Aaron Schild, and Joshua R. Wang. On the Randomized Locality of Matching Problems in Regular Graphs. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 40:1-40:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{khoury_et_al:LIPIcs.DISC.2025.40,
  author =	{Khoury, Seri and Purohit, Manish and Schild, Aaron and Wang, Joshua R.},
  title =	{{On the Randomized Locality of Matching Problems in Regular Graphs}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{40:1--40:20},
  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.40},
  URN =		{urn:nbn:de:0030-drops-248570},
  doi =		{10.4230/LIPIcs.DISC.2025.40},
  annote =	{Keywords: regular graphs, maximum matching, augmenting paths, distributed algorithms, Luby’s algorithm, martingales}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.119
Faster Semi-Streaming Matchings via Alternating Trees

Authors: Slobodan Mitrović, Anish Mukherjee, Piotr Sankowski, and Wen-Horng Sheu

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We design a deterministic algorithm for the (1+ε)-approximate maximum matching problem. Our primary result demonstrates that this problem can be solved in O(ε^{-6}) semi-streaming passes, improving upon the O(ε^{-19}) pass-complexity algorithm by [Fischer, Mitrović, and Uitto, STOC'22]. This contributes substantially toward resolving Open question 2 from [Assadi, SOSA'24]. Leveraging the framework introduced in [FMU'22], our algorithm achieves an analogous round complexity speed-up for computing a (1+ε)-approximate maximum matching in both the Massively Parallel Computation (MPC) and CONGEST models. The data structures maintained by our algorithm are formulated using blossom notation and represented through alternating trees. This approach enables a simplified correctness analysis by treating specific components as if operating on bipartite graphs, effectively circumventing certain technical intricacies present in prior work.
Cite as

Slobodan Mitrović, Anish Mukherjee, Piotr Sankowski, and Wen-Horng Sheu. Faster Semi-Streaming Matchings via Alternating Trees. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 119:1-119:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mitrovic_et_al:LIPIcs.ICALP.2025.119,
  author =	{Mitrovi\'{c}, Slobodan and Mukherjee, Anish and Sankowski, Piotr and Sheu, Wen-Horng},
  title =	{{Faster Semi-Streaming Matchings via Alternating Trees}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{119:1--119:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.119},
  URN =		{urn:nbn:de:0030-drops-234965},
  doi =		{10.4230/LIPIcs.ICALP.2025.119},
  annote =	{Keywords: streaming algorithms, approximation algorithms, maximum matching}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.28
Coresets for 1-Center in 𝓁₁ Metrics

Authors: Amir Carmel, Chengzhi Guo, Shaofeng H.-C. Jiang, and Robert Krauthgamer

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We explore the applicability of coresets - a small subset of the input dataset that approximates a predefined set of queries - to the 1-center problem in 𝓁₁ spaces. This approach could potentially extend to solving the 1-center problem in related metric spaces, and has implications for streaming and dynamic algorithms. We show that in 𝓁₁, unlike in Euclidean space, even weak coresets exhibit exponential dependency on the underlying dimension. Moreover, while inputs with a unique optimal center admit better bounds, they are not dimension independent. We then relax the guarantee of the coreset further, to merely approximate the value (optimal cost of 1-center), and obtain a dimension-independent coreset for every desired accuracy ε > 0. Finally, we discuss the broader implications of our findings to related metric spaces, and show explicit implications to Jaccard and Kendall’s tau distances.
Cite as

Amir Carmel, Chengzhi Guo, Shaofeng H.-C. Jiang, and Robert Krauthgamer. Coresets for 1-Center in 𝓁₁ Metrics. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{carmel_et_al:LIPIcs.ITCS.2025.28,
  author =	{Carmel, Amir and Guo, Chengzhi and Jiang, Shaofeng H.-C. and Krauthgamer, Robert},
  title =	{{Coresets for 1-Center in 𝓁₁ Metrics}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.28},
  URN =		{urn:nbn:de:0030-drops-226566},
  doi =		{10.4230/LIPIcs.ITCS.2025.28},
  annote =	{Keywords: clustering, k-center, minimum enclosing balls, coresets, 𝓁₁ norm, Kendall’s tau, Jaccard metric}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.23
On Finding the Jaccard Center

Authors: Marc Bury and Chris Schwiegelshohn

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We initiate the study of finding the Jaccard center of a given collection N of sets. For two sets X,Y, the Jaccard index is defined as |X\cap Y|/|X\cup Y| and the corresponding distance is 1-|X\cap Y|/|X\cup Y|. The Jaccard center is a set C minimizing the maximum distance to any set of N. We show that the problem is NP-hard to solve exactly, and that it admits a PTAS while no FPTAS can exist unless P = NP. Furthermore, we show that the problem is fixed parameter tractable in the maximum Hamming norm between Jaccard center and any input set. Our algorithms are based on a compression technique similar in spirit to coresets for the Euclidean 1-center problem. In addition, we also show that, contrary to the previously studied median problem by Chierichetti et al. (SODA 2010), the continuous version of the Jaccard center problem admits a simple polynomial time algorithm.
Cite as

Marc Bury and Chris Schwiegelshohn. On Finding the Jaccard Center. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bury_et_al:LIPIcs.ICALP.2017.23,
  author =	{Bury, Marc and Schwiegelshohn, Chris},
  title =	{{On Finding the Jaccard Center}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.23},
  URN =		{urn:nbn:de:0030-drops-73769},
  doi =		{10.4230/LIPIcs.ICALP.2017.23},
  annote =	{Keywords: Clustering, 1-Center, Jaccard}
}
  • Refine by Type
  • 5 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 3 2025
  • 1 2017

  • Refine by Author
  • 2 Jiang, Shaofeng H.-C.
  • 2 Krauthgamer, Robert
  • 1 Bury, Marc
  • 1 Carmel, Amir
  • 1 Guo, Chengzhi
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Random projections and metric embeddings
  • Show More...

  • Refine by Keyword
  • 2 clustering
  • 2 maximum matching
  • 1 1-Center
  • 1 Clustering
  • 1 Jaccard
  • 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact