50 citations · 61 across the 5 of their papers we have counts for
9 papers
A New Approach to Multi-Party Peer-to-Peer Communication Complexity
Adi Rosén, Florent Urrutia
We introduce new models and new information theoretic measures for the study of communication complexity in the natural peer-to-peer, multi-party, number-in-hand setting. We prove…
Multi-Party Protocols, Information Complexity and Privacy
Iordanis Kerenidis, Adi Rosén, Florent Urrutia
We introduce a new information theoretic measure that we call Public Information Complexity (PIC), as a tool for the study of multi-party computation protocols, and of quantities s…
A Constant Approximation Algorithm for Scheduling Packets on Line Networks
Guy Even, Moti Medina, Adi Rosén
In this paper we improve the approximation ratio for the problem of scheduling packets on line networks with bounded buffers, where the aim is that of maximizing the throughput. Ea…
Sublinear Random Access Generators for Preferential Attachment Graphs
Guy Even, Reut Levi, Moti Medina +1
We consider the problem of sampling from a distribution on graphs, specifically when the distribution is defined by an evolving graph model, and consider the time, space and random…
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…
Online Algorithms with Advice for Bin Packing and Scheduling Problems
Marc P. Renault, Adi Rosén, Rob van Stee
We consider the setting of online computation with advice, and study the bin packing problem and a number of scheduling problems. We show that it is possible, for any of these prob…