Source author record

Alexandre Nolin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

4works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Fast Distributed Vertex Splitting with Applications

We present ${\rm poly\log\log n}$ -round randomized distributed algorithms to compute vertex splittings, a partition of the vertices of a graph into $k$ parts such that a node of degree $d(u)$ has $\approx d(u)/k$ neighbors in each part. Our techniques can be seen as the first progress towards general ${\rm poly\log\log n}$ -round algorithms for the Lovász Local Lemma. As the main application of our result, we obtain a randomized ${\rm poly\log\log n}$ -round CONGEST algorithm for $(1+ε)Δ$ -edge coloring $n$ -node graphs of sufficiently large constant maximum degree $Δ$ , for any $ε>0$ . Further, our results improve the computation of defective colorings and certain tight list coloring problems. All the results improve the state-of-the-art round complexity exponentially, even in the LOCAL model.

preprint2022arXiv

Overcoming Congestion in Distributed Coloring

We present a new technique to efficiently sample and communicate a large number of elements from a distributed sampling space. When used in the context of a recent LOCAL algorithm for $(\operatorname{degree}+1)$ -list-coloring (D1LC), this allows us to solve D1LC in $O(\log^5 \log n)$ CONGEST rounds, and in only $O(\log^* n)$ rounds when the graph has minimum degree $Ω(\log^7 n)$ , w.h.p. The technique also has immediate applications in testing some graph properties locally, and for estimating the sparsity/density of local subgraphs in $O(1)$ CONGEST rounds, w.h.p.

preprint2021arXiv

Superfast Coloring in CONGEST via Efficient Color Sampling

We present a procedure for efficiently sampling colors in the {\congest} model. It allows nodes whose number of colors exceeds their number of neighbors by a constant fraction to sample up to $Θ(\log n)$ semi-random colors unused by their neighbors in $O(1)$ rounds, even in the distance-2 setting. This yields algorithms with $O(\log^* Δ)$ complexity for different edge-coloring, vertex coloring, and distance-2 coloring problems, matching the best possible. In particular, we obtain an $O(\log^* Δ)$ -round CONGEST algorithm for $(1+ε)Δ$ -edge coloring when $Δ\ge \log^{1+1/\log^*n} n$ , and a poly( $\log\log n$ )-round algorithm for $(2Δ-1)$ -edge coloring in general. The sampling procedure is inspired by a seminal result of Newman in communication complexity.

preprint2020arXiv

Coloring Fast Without Learning Your Neighbors' Colors

We give an improved randomized CONGEST algorithm for distance- $2$ coloring that uses $Δ^2+1$ colors and runs in $O(\log n)$ rounds, improving the recent $O(\log Δ\cdot \log n)$ -round algorithm in [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to $O(\log Δ) + 2^{O(\sqrt{\log\log n})}$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.