[theory students] Theory Lunch and TCS+ tomorrow at noon

[Benjamin Miller <bmiller@xxxxxxxxxxx>]

Hi all,

We'll meet in CS 3310 at noon tomorrow for the TCS+ talk by Seth Pettie of the University of Michigan (see below for details). As usual, bring your own lunch. I know this overlaps slightly with Shuchi's lecture, but please come when you can! See you there.

Benjamin

Title: A Time Hierarchy Theorem for the LOCAL Model Abstract: 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.