# Non-Local Probes Do Not Help with Graph Problems

arXiv: https://arxiv.org/abs/1512.05411 · HTML: https://mlsanity.com/paper/1512.05411/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2015.

## Built on by (most cited first, 1 of 1)

- [Agnostic proper learning of monotone functions: beyond the black-box correction barrier](https://mlsanity.com/paper/2304.02700/) (2023)

## Abstract (arXiv)

This work bridges the gap between distributed and centralised models of computing in the context of sublinear-time graph algorithms. A priori, typical centralised models of computing (e.g., parallel decision trees or centralised local algorithms) seem to be much more powerful than distributed message-passing algorithms: centralised algorithms can directly probe any part of the input, while in distributed algorithms nodes can only communicate with their immediate neighbours. We show that for a large class of graph problems, this extra freedom does not help centralised algorithms at all: for example, efficient stateless deterministic centralised local algorithms can be simulated with efficient distributed message-passing algorithms. In particular, this enables us to transfer existing lower bound results from distributed algorithms to centralised local algorithms.