5 papers
Online Algorithms with Unreliable Guidance
Julien Dallot, Yuval Emek, Yuval Gil +2
This paper introduces online algorithms with unreliable guidance (OAG), a model for ML-augmented online decision-making that cleanly separates the predictive and algorithmic compon…
On the Power of Graphical Reconfigurable Circuits
Yuval Emek, Yuval Gil, Noga Harlev
We introduce the \emph{graphical reconfigurable circuits (GRC)} model as an abstraction for distributed graph algorithms whose communication scheme is based on local mechanisms tha…
Online Algorithms with Randomly Infused Advice
Yuval Emek, Yuval Gil, Maciej Pacut +1
We introduce a novel method for the rigorous quantitative evaluation of online algorithms that relaxes the "radical worst-case" perspective of classic competitive analysis. In cont…
Locally Restricted Proof Labeling Schemes (Full Version)
Yuval Emek, Yuval Gil, Shay Kutten
Introduced by Korman, Kutten, and Peleg (PODC 2005), a proof labeling scheme (PLS) is a distributed verification system dedicated to evaluating if a given configured graph satisfie…
Twenty-Two New Approximate Proof Labeling Schemes (Full Version)
Yuval Emek, Yuval Gil
Introduced by Korman, Kutten, and Peleg (Distributed Computing 2005), a \emph{proof labeling scheme (PLS)} is a system dedicated to verifying that a given configuration graph satis…