Brief Announcement: Distributed Graph Algorithms with Predictions.

Joan Boyar, Faith Ellen, and Kim S. Larsen.
In 44th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pages 322-325. ACM, 2025.

We initiate the study of distributed graph algorithms with predictions in synchronous message passing systems. Each node in the graph is given a prediction, which is some extra information about the problem instance that may be incorrect. The better the prediction, the fewer rounds the algorithm should perform. We present a framework for evaluating distributed graph algorithms with predictions and some methods for transforming existing algorithms without predictions to effectively use predictions. Our approach is illustrated using the Maximal Independent Set problem.

---

publication

Link to the publication at the publisher's site - subscription may be required.

open access (371 KB)

The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.

other publications

Other publications by the author.