Skip to content

History

Upper Bound

1986 - \(O(\log^*n)\) on rings for \(3\)-coloring, MIS, ...

1987 - \(O(\log^*n)\) for \(O(\Delta^2)\)-coloring

1998 - \(O(poly(\log n))\) for maximal matching

2012 - Shattering for MIS, maximal matching

2017 - \(O(\log n)\) deterministic and \(O(\log\log n)\) randomized for sinkless orientation

2020 - \(O(poly(\log n))\) for \((\Delta+1)\)-coloring, MIS

Lower Bound

1987 - \(\Omega(\log^*n)\) on rings for \(3\)-coloring, MIS, ...

2004 - \(\Omega(\sqrt{\frac{\log n}{\log\log n}})\) for MIS and maximal matching

2016 - Round Elimination: \(\Omega(\log n)\) for sinkless orientation and \(\Delta\)-coloring

2019 - Automatic Round Elimination: \(\Omega(\frac{\log n}{\log\log n})\) for MIS, MM, ruling set, ...

Locality

In \(i\)-th round, the node will learn about all other nodes at distance \(\leq i\).

Runtime = Distance

In \(O(n)\) time, every problem will be solved.

Round Elimination

Basic Idea

From the perspective of node \(v\): Given that we can solve some problem in \(T\) rounds, what can we do in \(T-1\) rounds?

Consider problem of sinkless orientation.

Sinkless Orientation

Orient the edges of a graph of minimum degree \(3\) s.t. no node is a sink.

Edge Algorithm

Now, we regard each "edge" as a computational entity: Given that we can solve sinkless orientation in \(T\) rounds, what can we do in \(T-1/2\) rounds?

In \(1/2\)-round, each edge knows the both incident vertices.

In \(3/2\)-round, each edge knows all the neighbors of both incident vertices.

...

Lower Bound on Sinkless Orientation

Graph class: \(3\)-regular graphs of girth at least \(k\cdot\log n\), for some suitable constant \(k\).

Given that we can solve sinkless orientation in \(T+1/2\) rounds, what can we do in \(T\) rounds?

What can a node \(v\) that sees only its \(T\)-hop neighborhood say about the output?

  • \(v\) can determine one outgoing edge by just looking at its \(T\)-hop neighborhood!

Edge Grabbing

Each node has to grab one incident edge s.t. no edge is grabbed by both endpoints.

If we can solve sinkless orientation in \(T+1/2\) rounds, we can solve edge grabbing in \(T\) rounds.

  • For \(T\leq\frac{k}{2}\cdot\log n-10\)

Edge Grabbing: Each node \(v\) grabs the edge that is always oriented away from \(v\) in Sinkless Orientation problem.

THEN, if there exists a \(T\)-round edge grabbing algorithm, what can we solve in \(T-1/2\) rounds?

What can an edge \(e\) that sees only its \(T-1/2\)-hop neighborhood say about the output?

  • \(e\) can determine one endpoint that does not grab it, by just looking at its \(T-1/2\)-hop neighborhood.
  • Each edge \(e\) orients itself towards some endpoint that never grabs it in Edge Grabbing algorithm. Equivalently, sinkless orientation.

If we can solve edge grabbing in \(T\) rounds, we can solve sinkless orientation in \(T-1/2\) rounds.

  • For \(T\leq\frac{k}{2}\cdot\log n-10\)

Combine Them

For \(T\leq\frac{k}{2}\cdot\log n-10\):

  • If there exists a \(T+1/2\)-round sinkless orientation algorithm, there also exists a \(T-1/2\) round sinkless orientation algorithm.
  • If there exists a \(T\)-round edge grabbing algorithm, there also exists a \(T-1\)-round edge grabbing algorithm.

By induction, if the condition is true, there also exists a \(0\)-round edge grabbing algorithm.

0-Round Solvability

Can we solve the edge grabbing problem in \(0\) rounds?

NO!!!

Thus, the condition is false. There doesn't exist a \(o(\log n)\) algorithm to solve edge grabbing problem.

Hence, Solving edge grabbing deterministically requires \(\Omega(\log n)\) rounds.

Therefore, Solving sinkless orientation deterministically requires \(\Omega(\log n)\) rounds.

Automatic Round Elimination

Coloring

\(T\)-round for \(3\)-coloring

\((T-1)\)-round for \(2^3\)-coloring

...

\(0\)-round for \(2\) power tower of \(2\)-coloring

Locally Checkable Problems

For any locally checkable problem, we can automatically find a locally checkable problem that is exactly \(1\) round easier.

Sometimes, every time we apply round elimination, the problem description grows exponentially.

  • In some special case, the description doesn't grow.
  • If the description doesn't grow, it is called a fixed point

Theorem: Any non-\(0\)-round-solvable fixed point has a deterministic lower bound of \(\Omega(\log n)\) rounds and a randomized lower bound of \(\Omega(\log\log n)\).