Image de couverture de livre

Distributed Triangle Detection is Hard in Few Rounds

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Assadi, Sepehr, Sundaresan, Janani
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms Computational Complexity Distributed, Parallel, and Cluster Computing
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
par: Assadi, Sepehr
Publié: (2023)

It's Hard to HAC with Average Linkage!
par: Bateni, MohammadHossein, et autres
Publié: (2024)

Coloring Graphs with Few Colors in the Streaming Model
par: Assadi, Sepehr, et autres
Publié: (2025)

Improved Massively Parallel Triangle Counting in $O(1)$ Rounds
par: Liu, Quanquan C., et autres
Publié: (2024)

$O(1)$-Round MPC Algorithms for Multi-dimensional Grid Graph Connectivity, EMST and DBSCAN
par: Gan, Junhao, et autres
Publié: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
par: Assadi, Sepehr, et autres
Publié: (2025)

Segmented Operations using Matrix Multiplications
par: Sobczyk, Aleksandros, et autres
Publié: (2025)

Parallel Hierarchical Agglomerative Clustering in Low Dimensions
par: Bateni, MohammadHossein, et autres
Publié: (2025)

Testing Spreading Behavior in Networks with Arbitrary Topologies
par: Modanese, Augusto, et autres
Publié: (2023)

Work-Efficient Parallel Counting via Sampling
par: Liu, Hongyang, et autres
Publié: (2024)

On Distributed Computation of the Minimum Triangle Edge Transversal
par: Censor-Hillel, Keren, et autres
Publié: (2024)

Distributed Santa Claus via Global Rounding
par: de Vos, Tijn, et autres
Publié: (2026)

Finding a Fair Scoring Function for Top-$k$ Selection: From Hardness to Practice
par: Cai, Guangya
Publié: (2025)

Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching
par: Khoury, Seri, et autres
Publié: (2025)

To Store or Not to Store: a graph theoretical approach for Dataset Versioning
par: Guo, Anxin, et autres
Publié: (2024)

Round-Delayed Amnesiac Flooding
par: Alafin, Oluwatobi, et autres
Publié: (2026)

Round and Communication Efficient Graph Coloring
par: Chang, Yi-Jun, et autres
Publié: (2024)

Sorting in One and Two Rounds using $t$-Comparators
par: Gelles, Ran, et autres
Publié: (2024)

What Can We Compute in a Single Round of the Congested Clique?
par: Robinson, Peter
Publié: (2022)

Tight Bounds for Constant-Round Domination on Graphs of High Girth and Low Expansion
par: Lenzen, Christoph, et autres
Publié: (2024)

Model-Agnostic Approximation of Constrained Forest Problems
par: Coupette, Corinna, et autres
Publié: (2024)

Perfect Matching with Few Link Activations
par: Mirault, Hugo, et autres
Publié: (2025)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
par: Assadi, Sepehr, et autres
Publié: (2024)

Optimal Distributed Replacement Paths
par: Chang, Yi-Jun, et autres
Publié: (2025)

Bounded Memory in Distributed Networks
par: Basat, Ran Ben, et autres
Publié: (2025)

Distributed Graph Algorithms with Predictions
par: Boyar, Joan, et autres
Publié: (2025)

Distributed Stochastic Graph Algorithms
par: Censor-Hillel, Keren, et autres
Publié: (2026)

Towards Optimal Distributed Delta Coloring
par: Jakob, Manuel, et autres
Publié: (2025)

Distributed Maximum Flow in Planar Graphs
par: Abd-Elhaleem, Yaseen, et autres
Publié: (2024)

Fast Deterministic Distributed Degree Splitting
par: Maus, Yannic, et autres
Publié: (2026)

Meta-Theorems for Cuttable Distributed Problems
par: Bonamy, Marthe, et autres
Publié: (2026)

Distributed Subgraph Finding: Progress and Challenges
par: Censor-Hillel, Keren
Publié: (2022)

Local Density and its Distributed Approximation
par: Christiansen, Aleksander Bjørn, et autres
Publié: (2024)

$k$-Center Clustering in Distributed Models
par: Biabani, Leyla, et autres
Publié: (2024)

Congested Clique Counting for Local Gibbs Distributions
par: Sobel, Joshua Z.
Publié: (2025)

A Simple and Robust Protocol for Distributed Counting
par: Cohen, Edith, et autres
Publié: (2025)

The Local Information Cost of Distributed Graph Spanners
par: Robinson, Peter
Publié: (2020)

Distributed Delta-Coloring under Bandwidth Limitations
par: Maus, Yannic, et autres
Publié: (2024)

Fully-Distributed Byzantine Agreement in Sparse Networks
par: Augustine, John, et autres
Publié: (2024)

A Simple Distributed Deterministic Planar Separator
par: Abd-Elhaleem, Yaseen, et autres
Publié: (2026)