TCS+ Talk

Abtract: The celebrated Time Hierarchy Theorem for Turing machines states, informally, that more problems can be solved given more time.
The extent to which a time hierarchy-type theorem holds in the classic distributed LOCAL model has been open for many years.  In particular, it is consistent with previous results that all natural problems in the LOCAL model can be classified according to a small constant number of complexities, such as O(log^* n), O(log n), 2^{O(\sqrt{log n})}, etc.

We establish the first time hierarchy theorem for the LOCAL model and prove that several gaps exist in the LOCAL time hierarchy.  One of the gap results can be interpreted as showing that the distributed Lovasz local lemma is complete for randomized sublogarithmic time.