English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

This paper presents significantly improved deterministic algorithms for someof the key problems in the area of distributed graph algorithms, includingnetwork decomposition, hitting sets, and spanners. As the main ingredient inthese results, we develop novel randomized distributed algorithms that we cananalyze using only pairwise independence, and we can thus derandomizeefficiently. As our most prominent end-result, we obtain a deterministicconstruction for $O(\log n)$-color $O(\log n \cdot \log\log\log n)$-strongdiameter network decomposition in $\tilde{O}(\log^3 n)$ rounds. This is thefirst construction that achieves almost $\log n$ in both parameters, and itimproves on a recent line of exciting progress on deterministic distributednetwork decompositions [Rozho\v{n}, Ghaffari STOC'20; Ghaffari, Grunau,Rozho\v{n} SODA'21; Chang, Ghaffari PODC'21; Elkin, Haeupler, Rozho\v{n},Grunau FOCS'22].

Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization