On the Locality of Hall’s Theorem
Sebastian Brandt, Yannic Maus, Ananth Narayanan, Florian Schager, Jara Uitto · Society for Industrial and Applied Mathematics eBooks · 2025
The last five years of research on distributed graph algorithms have seen huge leaps of progress, both regarding algorithmic improvements and impossibility results: new strong lower bounds have emerged for many central problems and exponential improvements over the state of the art have been achieved for the runtimes of many algorithms. Nevertheless, there are still large gaps between the best known upper and lower bounds for many important problems.