Shay Kutten

Matthias Bentert, Shay Kutten, Darya Melnyk et al.

The theoretical model behind the pigeon post as a link layer in a communication network was introduced by Shannon (under the guise of studying One-Time Pads for cryptography). That is, to send a one-hop message to $v$, a node $u$ needs a mail pigeon bred and raised at $v$. When sending a message using a pigeon to $v$, node $u$ loses the pigeon. To send another message to $v$, node $u$ needs another pigeon of $v$. It has been demonstrated that the communication bandwidth achievable with pigeon post can exceed that of networks using other media. This has already motivated the introduction of Internet standards that allow the use of pigeons as Internet link-layer media. In this paper, we begin to fill in the missing piece: designing algorithms for breeding and scheduling pigeons to meet a given communication demand efficiently, minimizing the number of pigeons required. We consider singlehop, 2-hop, and multihop pigeon use. While the singlehop variant admits a simple characterization, both the 2-hop and the multihop variants are NP-hard. For the latter variants, we present a polynomial-time algorithm based on demand aggregation that achieves a 2-approximation for the number of pigeons used. We believe that this pigeon-based perspective offers both amusing and instructive insights into network design and hopefully, into ornithology.

Yuval Emek, Shay Kutten, Yangguang Shi

This paper considers a variant of the online paging problem, where the online algorithm has access to multiple predictors, each producing a sequence of predictions for the page arrival times. The predictors may have occasional prediction errors and it is assumed that at least one of them makes a sublinear number of prediction errors in total. Our main result states that this assumption suffices for the design of a randomized online algorithm whose time-average regret with respect to the optimal offline algorithm tends to zero as the time tends to infinity. This holds (with different regret bounds) for both the full information access model, where in each round, the online algorithm gets the predictions of all predictors, and the bandit access model, where in each round, the online algorithm queries a single predictor. While online algorithms that exploit inaccurate predictions have been a topic of growing interest in the last few years, to the best of our knowledge, this is the first paper that studies this topic in the context of multiple predictors for an online problem with unbounded request sequences. Moreover, to the best of our knowledge, this is also the first paper that aims for (and achieves) online algorithms with a vanishing regret for a classic online problem under reasonable assumptions.

Yuval Emek, Shay Kutten, Ron Lavi et al.

Addressing a fundamental problem in programmable matter, we present the first deterministic algorithm to elect a unique leader in a system of connected amoebots assuming only that amoebots are initially contracted. Previous algorithms either used randomization, made various assumptions (shapes with no holes, or known shared chirality), or elected several co-leaders in some cases. Some of the building blocks we introduce in constructing the algorithm are of interest by themselves, especially the procedure we present for reaching common chirality among the amoebots. Given the leader election and the chirality agreement building block, it is known that various tasks in programmable matter can be performed or improved. The main idea of the new algorithm is the usage of the ability of the amoebots to move, which previous leader election algorithms have not used.