Derandomizing local distributed algorithms under bandwidth restrictions (Q2189176)

From MaRDI portal

Revision as of 21:58, 22 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Derandomizing local distributed algorithms under bandwidth restrictions	scientific article

Statements

scholarly article

0 references

Derandomizing local distributed algorithms under bandwidth restrictions (English)

0 references

Keren Censor-Hillel

0 references

0 references

Gregory Schwartzman

0 references

Distributed Computing

0 references

publication date

15 June 2020

0 references

full work available at URL

https://arxiv.org/abs/1608.01689

0 references

https://drops.dagstuhl.de/opus/volltexte/2017/7975/

0 references

MaRDI profile type

MaRDI publication profile

0 references

A fast and simple randomized parallel algorithm for the maximal independent set problem

0 references

Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic and Faulty Networks

0 references

Distributed Graph Coloring: Fundamentals and Recent Developments

0 references

A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation

0 references

Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time

0 references

The Locality of Distributed Symmetry Breaking

0 references

A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs

0 references

Simulating (log <sup>c</sup> <i>n</i> )-wise independence in NC

0 references

A lower bound for the distributed Lovász local lemma

0 references

Algebraic methods in the congested clique

0 references

Deterministic Algorithms for the Lovász Local Lemma

0 references

The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation

0 references

Brief Announcement

0 references

Fast Deterministic Distributed Algorithms for Sparse Spanners

0 references

Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time

0 references

On the locality of distributed sparse spanner construction

0 references

Local Computation of Nearly Additive Spanners

0 references

Sublinear fully distributed partition with applications

0 references

“Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting

0 references

On the power of the congested clique model

0 references

A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners

0 references

Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems

0 references

An Improved Distributed Algorithm for Maximal Independent Set

0 references

Distributed MIS via All-to-All Communication

0 references

MST in Log-Star Rounds of Congested Clique

0 references

A New Parallel Algorithm for the Maximal Independent Set Problem

0 references

A Fast Derandomization Scheme and Its Applications

0 references

Toward Optimal Bounds in the Congested Clique

0 references

Lessons from the Congested Clique Applied to MapReduce

0 references

A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

0 references

0 references

A fast and simple randomized parallel algorithm for maximal matching

0 references

0 references

Local Computation

0 references

Optimal deterministic routing and sorting on the congested clique

0 references

Tight bounds for parallel randomized load balancing

0 references

Locality in Distributed Graph Algorithms

0 references

Minimum-Weight Spanning Tree Construction in <i>O</i>(log log <i>n</i>) Communication Rounds

0 references

A Simple Parallel Algorithm for the Maximal Independent Set Problem

0 references

Removing randomness in parallel computation without a processor penalty

0 references

The probabilistic method yields deterministic parallel algorithms

0 references

Distributed approximation algorithms for weighted shortest paths

0 references

What Can be Computed Locally?

0 references

0 references

(Delta+1) Coloring in the Congested Clique Model

0 references

Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds

0 references

The round complexity of distributed sorting

0 references

0 references

Distributed algorithms for ultrasparse spanners and linear size skeletons

0 references

Automata, Languages and Programming

0 references

Chernoff–Hoeffding Bounds for Applications with Limited Independence

0 references

Survey of local algorithms

0 references

Pseudorandomness

0 references

Identifiers

zbMATH Open document ID

0 references

10.1007/s00446-020-00376-1

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2189176

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q2189176&oldid=36593773"