Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
Will Rosenbaum, Jukka Suomela · 2020
Assume we have a graph problem that is locally checkable but not locally solvable---given a solution we can check that it is feasible by verifying all constant-radius neighborhoods, but to find a feasible solution each node needs to explore the input graph at least up to distance Ω (log n) in order to produce its own part of the solution.