Benjamín Jauregui

A Simple Construction of Locally Checkable Problems Filling the LOCAL Complexity Gaps in Graphs with Arbitrary Large Degrees

It is shown that there are infinitely many locally checkable problems (i.e., problems whose solutions can be checked locally) whose round complexities belongs to the two intervals $[omega(1),o(\log\log^\star n)]$ and $[\omega(\log^\star n),o(\log n)] whenever these problems are considered in networks with unbounded max...