Polylogarithmic-time deterministic network decomposition and distributed derandomization

From MaRDI portal
Publication:5144922

DOI10.1145/3357713.3384298OpenAlexW3034790637MaRDI QIDQ5144922

Václav Rozhoň, Mohsen Ghaffari

Publication date: 19 January 2021

Published in: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1907.10937




Related Items (38)

Distributed independent sets in interval and segment intersection graphsSublinear-time distributed algorithms for detecting small cliques and even cyclesA fast distributed algorithm for \((\Delta+1)\)-edge-coloringDistributed strong diameter network decompositionDistributed minimum vertex coloring and maximum independent set in chordal graphsNetwork Decomposition and Distributed Derandomization (Invited Paper)Distributed Testing of Distance-k ColoringsNode and edge averaged complexities of local graph problemsLocal problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatoricsLocally checkable problems in rooted treesOn the Locality of Nash-Williams Forest Decomposition and Star-Forest DecompositionComponent stability in low-space massively parallel computationDistributed $(\Delta+1)$-Coloring via Ultrafast Graph ShatteringDistributed graph problems through an automata-theoretic lensDistributed coloring of hypergraphsThe Complexity of Distributed Approximation of Packing and Covering Integer Linear ProgramsEfficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their ApplicationsDistributed MIS in O(log log n) Awake ComplexityDistributed MIS with Low Energy and Time ComplexitiesDistributed Symmetry Breaking on Power Graphs via SparsificationA Near-Optimal Deterministic Distributed SynchronizerUniting General-Graph and Geometric-Based Radio Networks via Independence Number ParametrizationOptimal Message-Passing with Noisy BeepsMini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022Improved distributed \(\Delta\)-coloringDistributed distance-\(r\) covering problems on sparse high-girth graphsSuperfast coloring in CONGEST via efficient color samplingDistributed coloring and the local structure of unit-disk graphsDistributed distance-\(r\) covering problems on sparse high-girth graphsSuperfast coloring in CONGEST via efficient color samplingDistributed Spanner ApproximationLoosely-stabilizing maximal independent set algorithms with unreliable communicationsSimple, Deterministic, Constant-Round Coloring in Congested Clique and MPCDistributed Lower Bounds for Ruling SetsLinial for listsEfficient and competitive broadcast in multi-channel radio networksDistributed graph problems through an automata-theoretic LensConstant round distributed domination on graph classes with bounded expansion




This page was built for publication: Polylogarithmic-time deterministic network decomposition and distributed derandomization