Publications (40)
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…
Hierarchical b-Matching
Yuval Emek, Shay Kutten, Mordechai Shalom +1
A matching of a graph is a subset of edges no two of which share a common vertex, and a maximum matching is a matching of maximum cardinality. In a -matching every vertex ha…
Dynamic Networks of Finite State Machines
Yuval Emek, Jara Uitto
Like distributed systems, biological multicellular processes are subject to dynamic changes and a biological system will not pass the survival-of-the-fittest test unless it exhibit…
SINR Diagrams: Towards Algorithmically Usable SINR Models of Wireless Networks
Chen Avin, Yuval Emek, Erez Kantor +3
The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model…
Selecting a Leader in a Network of Finite State Machines
Yehuda Afek, Yuval Emek, Noa Kolikant
This paper studies a variant of the \emph{leader election} problem under the \emph{stone age} model (Emek and Wattenhofer, PODC 2013) that considers a network of randomized fin…
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…
Stable Secretaries
Yakov Babichenko, Yuval Emek, Michal Feldman +3
We define and study a new variant of the secretary problem. Whereas in the classic setting multiple secretaries compete for a single position, we study the case where the secretari…
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…
Multicast Communications in Tree Networks with Heterogeneous Capacity Constraints
Yuval Emek, Shay Kutten, Mordechai Shalom +1
A widely studied problem in communication networks is that of finding the maximum number of communication requests that can be scheduled concurrently, subject to node and/or link c…
Stateful Posted Pricing with Vanishing Regret via Dynamic Deterministic Markov Decision Processes
Yuval Emek, Ron Lavi, Rad Niazadeh +1
In this paper, a rather general online problem called dynamic resource allocation with capacity constraints (DRACC) is introduced and studied in the realm of posted price mechanism…
Lower-Stretch Spanning Trees
Michael Elkin, Yuval Emek, Daniel A. Spielman +1
We prove that every weighted graph contains a spanning tree subgraph of average stretch O((log n log log n)^2). Moreover, we show how to construct such a tree in time O(m log^2 n).
On the Runtime of Chemical Reaction Networks Beyond Idealized Conditions
Anne Condon, Yuval Emek, Noga Harlev
This paper studies the (discrete) \emph{chemical reaction network (CRN)} computational model that emerged in the last two decades as an abstraction for molecular programming. The c…
Deterministic Leader Election in Programmable Matter
Yuval Emek, Shay Kutten, Ron Lavi +1
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…
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…
Communication Efficient Self-Stabilizing Leader Election (Full Version)
Xavier Défago, Yuval Emek, Shay Kutten +2
This paper presents a randomized self-stabilizing algorithm that elects a leader in a general -node undirected graph and constructs a spanning tree rooted at . The al…
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…
Ants: Mobile Finite State Machines
Yuval Emek, Tobias Langner, Jara Uitto +1
Consider the Ants Nearby Treasure Search (ANTS) problem introduced by Feinerman, Korman, Lotker, and Sereni (PODC 2012), where mobile agents, initially placed at the origin of…
Stone Age Distributed Computing
Yuval Emek, Jasmin Smula, Roger Wattenhofer
The traditional models of distributed computing focus mainly on networks of computer-like devices that can exchange large messages with their neighbors and perform arbitrary local…
Exploring an Infinite Space with Finite Memory Scouts
Lihi Cohen, Yuval Emek, Oren Louidor +1
Consider a small number of scouts exploring the infinite -dimensional grid with the aim of hitting a hidden target point. Each scout is controlled by a probabilistic finite auto…
Approximating the Statistics of various Properties in Randomly Weighted Graphs
Yuval Emek, Amos Korman, Yuval Shavitt
Consider the setting of \emph{randomly weighted graphs}, namely, graphs whose edge weights are chosen independently according to probability distributions with finite support over…
Beeping Shortest Paths via Hypergraph Bipartite Decomposition
Fabien Dufoulon, Yuval Emek, Ran Gelles
Constructing a shortest path between two network nodes is a fundamental task in distributed computing. This work develops schemes for the construction of shortest paths in randomiz…
Online Paging with a Vanishing Regret
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 arr…
Semi-Streaming Set Cover
Yuval Emek, Adi Rosen
This paper studies the set cover problem under the semi-streaming model. The underlying set system is formalized in terms of a hypergraph whose edges arrive one-by-one…
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…
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…
Signaling Schemes for Revenue Maximization
Yuval Emek, Michal Feldman, Iftah Gamzu +2
Signaling is an important topic in the study of asymmetric information in economic settings. In particular, the transparency of information available to a seller in an auction sett…
Fully Adaptive Self-Stabilizing Transformer for LCL Problems
Shimon Bitton, Yuval Emek, Taisuke Izumi +1
The first generic self-stabilizing transformer for local problems in a constrained bandwidth model is introduced. This transformer can be applied to a wide class of locally checkab…
Low Diameter Graph Decompositions by Approximate Distance Computation
Ruben Becker, Yuval Emek, Christoph Lenzen
In many models for large-scale computation, decomposition of the problem is key to efficient algorithms. For distance-related graph problems, it is often crucial that such a decomp…
Space-Constrained Interval Selection
Yuval Emek, Magnus M. Halldorsson, Adi Rosen
We study streaming algorithms for the interval selection problem: finding a maximum cardinality subset of disjoint intervals on the line. A deterministic 2-approximation streaming…
On the Additive Constant of the k-server Work Function Algorithm
Yuval Emek, Pierre Fraigniaud, Amos Korman +1
We consider the Work Function Algorithm for the k-server problem. We show that if the Work Function Algorithm is c-competitive, then it is also strictly (2c)-competitive. As a cons…
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…
A Thin Self-Stabilizing Asynchronous Unison Algorithm with Applications to Fault Tolerant Biological Networks
Yuval Emek, Eyal Keren
Introduced by Emek and Wattenhofer (PODC 2013), the \emph{stone age (SA)} model provides an abstraction for network algorithms distributed over randomized finite state machines. Th…
Online Matching: Haste makes Waste!
Yuval Emek, Shay Kutten, Roger Wattenhofer
This paper studies a new online problem, referred to as \emph{min-cost perfect matching with delays (MPMD)}, defined over a finite metric space (i.e., a complete graph with positiv…
Bayesian Generalized Network Design
Yuval Emek, Shay Kutten, Ron Lavi +1
We study network coordination problems, as captured by the setting of generalized network design (Emek et al., STOC 2018), in the face of uncertainty resulting from partial informa…
Deterministic Fault-Tolerant Connectivity Labeling Scheme
Taisuke Izumi, Yuval Emek, Tadashi Wadayama +1
The \emph{-fault-tolerant connectivity labeling} (-FTC labeling) is a scheme of assigning each vertex and edge with a small-size label such that one can determine the connect…
Message Reduction in the Local Model is a Free Lunch
Shimon Bitton, Yuval Emek, Taisuke Izumi +1
A new \emph{spanner} construction algorithm is presented, working under the \emph{LOCAL} model with unique edge IDs. Given an -node communication graph, a spanner with a constan…
Exploitation of Multiple Replenishing Resources with Uncertainty
Amos Korman, Yuval Emek, Simon Collet +2
We consider an optimization problem in which a (single) bat aims to exploit the nectar in a set of cacti with the objective of maximizing the expected total amount of nectar it…
Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency
Yuval Emek, Shay Kutten, Ron Lavi +1
In a generalized network design (GND) problem, a set of resources are assigned to multiple communication requests. Each request contributes its weight to the resources it uses and…
The Price of Matching Selfish Vertices
Yuval Emek, Tobias Langner, Roger Wattenhofer
We analyze the setting of minimum-cost perfect matchings with selfish vertices through the price of anarchy (PoA) and price of stability (PoS) lens. The underlying solution concept…