6 papers
Randomized Tree-Intersection Leader Election
Yuval Emek, Shay Kutten, Ido Rafael +1
We present a randomized leader election algorithm for synchronous complete -node graphs in the \textsf{CONGEST} model that introduces a highly tunable trade-off between time com…
Self-Stabilizing Algorithms in the Uniform Port Model
Liam Brinker, Yuval Emek, Oren Louidor
We introduce a distributed computational model referred to as the \emph{uniform port} model. An algorithm operating in this model is defined by means of local automata associated w…
Team Formation and Applications
Yuval Emek, Shay Kutten, Ido Rafael +1
A novel long-lived distributed problem, called Team Formation (TF), is introduced together with a message- and time-efficient randomized algorithm. The problem is defined over the…
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…
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…
Barter Exchange with Bounded Trading Cycles
Yuval Emek, Matan-El Shpiro
Consider a barter exchange problem over a finite set of agents, where each agent owns an item and is also associated with a (privately known) wish list of items belonging to the ot…