skip to main content

Title: Distributed MIS in O(log log n) Awake Complexity
Award ID(s):
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
PODC '23: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing
Page Range / eLocation ID:
135 to 145
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Dynamic connectivity is one of the most fundamental problems in dynamic graphalgorithms. We present a randomized Las Vegas dynamic connectivity datastructure with $O(\log n(\log\log n)^2)$ amortized expected update time and$O(\log n/\log\log\log n)$ worst case query time, which comes very close to thecell probe lower bounds of Patrascu and Demaine (2006) and Patrascu and Thorup(2011). 
    more » « less
  2. null (Ed.)
  3. null (Ed.)