Brief Announcement: Round eliminator: a tool for automatic speedup simulation
Dennis Olivetti · 2020
In the last years, the round elimination technique has been successfully used to prove many lower bounds for the LOCAL model of distributed computing. In 2019, Brandt proved that this technique can be theoretically automated: given a locally checkable problem Π that can be solved in T rounds of communication, it is possible to mechanically define a problem Π′ that requires T − 1 rounds, and by repeating this procedure many times one can obtain interesting lower and upper bounds.