On the Universality of Round Elimination Fixed Points

Recent work on distributed graph algorithms [e.g. STOC 2022, ITCS 2022, PODC 2020] has drawn attention to the following open question: are round elimination fixed points a universal technique for proving lower bounds? That is, given a locally checkable problem Π that requires at least Ω(log n) rounds in the deterministic LOCAL model, can we always find a relaxation Π ′ of Π that is a nontrivial fixed point for the round elimination technique [see STOC 2016, PODC 2019]? If yes, then a key part of distributed computational complexity would be also decidable.

The key obstacle so far has been a certain family of homomorphism problems [ITCS 2022], which require Ω(log n) rounds, but the only known proof is based on Marks' technique [J. AMS 2016].

We develop a new technique for constructing round elimination lower bounds systematically. Using so-called tripotent inputs we show that the aforementioned homomorphism problems indeed admit a lower bound proof that is based on round elimination fixed points. Hence we eliminate the only known obstacle for the universality of round elimination.

Yet we also present a new obstacle: we show that there are some problems with inputs that require Ω(log n) rounds, yet there is no proof that is based on relaxations to nontrivial round elimination fixed points. Hence round elimination cannot be a universal technique for problems with inputs (but it might be universal for problems without inputs).

We also prove the first fully general lower bound theorem that is applicable to any problem, with or without inputs, that is a fixed point in round elimination. Prior results of this form were only able to handle certain very restricted inputs.