03/08/2020

Brief announcement: Round eliminator: A tool for automatic speedup simulation

Dennis Olivetti

Keywords: locally checkable problems, round elimination, LOCAL model, speedup simulation, automatic lower bounds, automatic upper bounds, graph problems

Abstract: 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.In this work, we show that this technique can be automated also in practice: round eliminator is a computer program where we can feed our favorite locally checkable problem and obtain lower (and sometimes upper) bounds for it, automatically.

 0
 0
 0
 0
This is an embedded video. Talk and the respective paper are published at PODC 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd

Similar Papers