Adi Rosén

TCS Journal 2020 Journal Article

Paid exchanges are worth the price

• Alejandro López-Ortiz
• Marc P. Renault
• Adi Rosén

We consider the list update problem as defined in the seminal work on competitive analysis by Sleator and Tarjan [13]. An instance of the problem consists of a sequence of requests to access items in a linked list. After an item is accessed, that item can be moved to any position forward in the list at no cost (a move called free exchange), and, at any time, any two adjacent items can be swapped at a cost of 1 (a move called paid exchange). The cost to access an item is equal to its current position in the list. The goal is to dynamically rearrange the list so as to minimize the total cost (accrued from accesses and exchanges) over the request sequence. We show a lower bound of 12/11 on the worst-case ratio between the performance of an (offline) optimal algorithm that can only perform free exchanges and that of an (offline) optimal algorithm that can perform both paid and free exchanges. This answers the question of the asymptotic relative power of the two models which has been open since Reingold and Westbrook [11] showed in 1996 that Sleator and Tarjan erred in [13] when they claimed that the two models are equivalent.

MFCS Conference 2016 Conference Paper

Multi-Party Protocols, Information Complexity and Privacy

• Iordanis Kerenidis
• Adi Rosén
• Florent Urrutia

We introduce the new measure of Public Information Complexity (PIC), as a tool for the study of multi-party computation protocols, and of quantities such as their communication complexity, or the amount of randomness they require in the context of information-theoretic private computations. We are able to use this measure directly in the natural asynchronous message-passing peer-to-peer model and show a number of interesting properties and applications of our new notion: the Public Information Complexity is a lower bound on the Communication Complexity and an upper bound on the Information Complexity; the difference between the Public Information Complexity and the Information Complexity provides a lower bound on the amount of randomness used in a protocol; any communication protocol can be compressed to its Public Information Cost; an explicit calculation of the zero-error Public Information Complexity of the k-party, n-bit Parity function, where a player outputs the bit-wise parity of the inputs. The latter result establishes that the amount of randomness needed for a private protocol that computes this function is Omega(n).

TCS Journal 2015 Journal Article

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 problems, to arbitrarily approach a competitive ratio of 1 with only a constant number of bits of advice per request. For the bin packing problem, we give an online algorithm with advice that is ( 1 + ε ) -competitive and uses O ( 1 ε log ⁡ 1 ε ) bits of advice per request. For scheduling on m identical machines, with the objective function of any of makespan, machine covering and the minimization of the ℓ p norm, p > 1, we give similar results. We give online algorithms with advice which are ( 1 + ε ) -competitive ( ( 1 / ( 1 − ε ) ) -competitive for machine covering) and also use O ( 1 ε log ⁡ 1 ε ) bits of advice per request. We complement our results by giving a lower bound that shows that for any online algorithm with advice to be optimal, for any of the above scheduling problems, a non-constant number (namely, at least ( 1 − 2 m n ) log ⁡ m, where n is the number of jobs and m is the number of machines) of bits of advice per request is needed.

TCS Journal 2011 Journal Article

Online computation with advice

• Yuval Emek
• Pierre Fraigniaud
• Amos Korman
• Adi Rosén

We consider a model for online computation in which the online algorithm receives, together with each request, some information regarding the future, referred to as advice. The advice is a function, defined by the online algorithm, of the whole request sequence. The advice provided to the online algorithm may allow an improvement in its performance, compared to the classical model of complete lack of information regarding the future. We are interested in the impact of such advice on the competitive ratio, and in particular, in the relation between the size b of the advice, measured in terms of bits of information per request, and the (improved) competitive ratio. Since b = 0 corresponds to the classical online model, and b = ⌈ log ∣ A ∣ ⌉, where A is the algorithm’s action space, corresponds to the optimal (offline) one, our model spans a spectrum of settings ranging from classical online algorithms to offline ones. In this paper we propose the above model and illustrate its applicability by considering two of the most extensively studied online problems, namely, metrical task systems (MTS) and the k -server problem. For MTS we establish tight (up to constant factors) upper and lower bounds on the competitive ratio of deterministic and randomized online algorithms with advice for any choice of 1 ≤ b ≤ Θ ( log n ), where n is the number of states in the system: we prove that any randomized online algorithm for MTS has competitive ratio Ω ( log ( n ) / b ) and we present a deterministic online algorithm for MTS with competitive ratio O ( log ( n ) / b ). For the k -server problem we construct a deterministic online algorithm for general metric spaces with competitive ratio k O ( 1 / b ) for any choice of Θ ( 1 ) ≤ b ≤ log k.

SODA Conference 2005 Conference Paper

Distributed online call control on general networks

• Harald Räcke
• Adi Rosén

SODA Conference 2003 Conference Paper

Dynamic routing on networks with fixed-size buffers

• William Aiello
• Rafail Ostrovsky
• Eyal Kushilevitz
• Adi Rosén

STOC Conference 2003 Conference Paper

Lower bounds on the amount of randomness in private computation

• Anna Gál
• Adi Rosén

We consider the amount of randomness necessary in information-theoretic private protocols. We prove that at least Ω(log n) random bits are necessary for the t-private computation of the function xor by n players, for any t ≥ 2. In view of the upper bound of O(t 2 log(n/t))[19], this bound is tight, up to constant factors, for any fixed t. For a class of protocols obeying certain restrictions, we give stronger lower bounds of Ω(t log (n/t)). We note that all known randomness efficient private protocols designed specifically for xor belong to this class. All our lower bounds hold for the "trusted dealer" model as well, and the Ω(t log (n/t)) lower bound for restricted protocols is tight, up to constant factors, for any t ≥ 2 in this model.In comparison, the previous lower bounds on the amount of randomness required by t-private computation of explicit functions did not grow with n for constant values of t, and our results improve the previous lower bounds for xor for any 2 ≤ t = o(log n). Our results also show that already for t = 2, Ω(log n) random bits are necessary, while it is known that for the case of t = 1 a single random bit is sufficient for privately computing xor for any number of players.Our proofs use novel techniques by which we extract random variables from a t-private protocol, and then use the t-privacy property of the protocol to prove properties of these random variables. These properties in turn imply that the number of random bits used by the players is large.

STOC Conference 1999 Conference Paper

A Theorem on Sensitivity and Applications in Private Computation

• Anna Gál
• Adi Rosén

STOC Conference 1998 Conference Paper

Adaptive Packet Routing for Bursty Adversarial Traffic

• William Aiello
• Eyal Kushilevitz
• Rafail Ostrovsky
• Adi Rosén

SODA Conference 1998 Conference Paper

On-line Randomized Call Control Revisited

• Stefano Leonardi 0001
• Alberto Marchetti-Spaccamela
• Alessio Presciutti
• Adi Rosén

STOC Conference 1996 Conference Paper

Characterizing Linear Size Circuits in Terms of Privacy

• Eyal Kushilevitz
• Rafail Ostrovsky
• Adi Rosén

SODA Conference 1996 Conference Paper

Randomized Robot Navigation Algorithms

• Piotr Berman
• Avrim Blum
• Amos Fiat
• Howard J. Karloff
• Adi Rosén
• Michael E. Saks

FOCS Conference 1995 Conference Paper

Competitive Access Time via Dynamic Storage Rearrangement (Preliminary Version)

• Amos Fiat
• Yishay Mansour
• Adi Rosén
• Orli Waarts

We model the problem of storing items in some warehouse (modeled as an undirected graph) where a server has to visit items over time, with the goal of minimizing the total distance traversed by the server. Special cases of this problem include the management of a real industrial stacker crane warehouse, automatic robot run warehouses, disk track optimization to minimize access time, managing two dimensional memory (bubble memory and mass storage systems), doubly linked list management, and the process migration problem. The static version of this problem assumes some known probability distribution on the access patterns. We initiate the study of the dynamic version of the problem, where the robot may rearrange the warehouse to deal efficiently with future events. We require no statistical assumptions on the access pattern, and give competitive algorithms that rearrange the warehouse over time to deal efficiently with the true access patterns. We give non-trivial upper bounds for the general problem, along with some interesting lower bounds. In addition, we model realistic data access patterns on disk storage by considering two practically significant scenarios: access to some database via dynamically changing alternative indices and access patterns derived from root to leaf traversals of some (unknown) tree structure. In both cases we give greatly improved competitive ratios.

STOC Conference 1995 Conference Paper

Log-space polynomial end-to-end communication

• Eyal Kushilevitz
• Rafail Ostrovsky
• Adi Rosén

SODA Conference 1994 Conference Paper

Competitive Non-Preemptive Call Control

• Baruch Awerbuch
• Yair Bartal
• Amos Fiat
• Adi Rosén

FOCS Conference 1992 Conference Paper

The Distributed k-Server Problem-A Competitive Distributed Translator for k-Server Algorithms

• Yair Bartal
• Adi Rosén

The authors consider the k-server problem in a distributed setting. Given a network of n processors, and k identical mobile servers, requests for service appear at the processors and a server must reach the request point. Besides modeling problems in computer networks where k identical mobile resources are shared by the processors of the network, this models a realistic situation where the transfer of information is costly and there is no central control that governs the behavior of servers that move around to satisfy requests for service. The problem is that of devising algorithms that minimize not only the travel of the server but also the communication cost incurred for the transmission of control messages. The main contribution is a general translator to transform any deterministic global-control competitive k-server algorithm into a distributed competitive one. As consequences they get poly(k)-competitive distributed algorithms for the line, trees and the ring. >