In this paper we prove lower bounds on randomized multiparty communication complexity, both in the blackboard model (where each message is written on a blackboard for all players to see) and (mainly) in the message-pa...
详细信息
ISBN:
(纸本)9781611972108
In this paper we prove lower bounds on randomized multiparty communication complexity, both in the blackboard model (where each message is written on a blackboard for all players to see) and (mainly) in the message-passing model, where messages are sent player-to-player. We introduce a new technique for proving such bounds, called symmetriza-tion, which is natural, intuitive, and often easy to use. For example, for the problem where each of k players gets a bit-vector of length n, and the goal is to compute the coordinate-wise XOR of these vectors, we prove a tight lower bounds of Ω(nk) in the blackboard model. For the same problem with AND instead of XOR, we prove a lower bounds of roughly Ω(nk) in the message-passing model (assuming k ≤ n/3200) and Ω(n log k) in the blackboard model. We also prove lower bounds for bit-wise majority, for a graph-connectivity problem, and for other problems; the technique seems applicable to a wide range of other problems as well. The obtained communication lower bounds imply new lower bounds in the functional monitoring model (also called the distributed streaming model). All of our lower bounds allow randomized communication protocols with two-sided error.
We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (Nature, 433:312-316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an indivi...
详细信息
ISBN:
(纸本)9781611972108
We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (Nature, 433:312-316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is chosen at random with probability proportional to its assigned "fitness" value. It reproduces, placing a copy of itself on a neighbouring vertex chosen uniformly at random, replacing the individual that was there. The initial population consists of a single mutant of fitness r ＞ 0 placed uniformly at random, with every other vertex occupied by an individual of fitness 1. The main quantities of interest are the probabilities that the descendants of the initial mutant come to occupy the whole graph (fixation) and that they die out (extinction); almost surely, these are the only possibilities. In general, exact computation of these quantities by standard Markov chain techniques requires solving a system of linear equations of size exponential in the order of the graph so is not feasible. We show that, with high probability, the number of steps needed to reach fixation or extinction is bounded by a polynomial in the number of vertices in the graph. This bound allows us to construct fully polynomial randomized approximation schemes (FPRAS) for the probability of fixation (when r ＞ 1) and of extinction (for all r ＞ 0).
In our previous work, we developed a nested Petri net framework for modeling multi-agent systems. In this paper, we present a method to analyze the nested Petri net model using model checking. Our method systematicall...
详细信息
Authentication between mobile devices in ad-hoc computing environments is a challenging problem. Without pre-shared knowledge, existing applications rely on additional communication methods, such as out-of-band or loc...
详细信息
In ubiquitous computing environments services may be discovered and bound dynamically. Adaptive applications may utilize such services to improve their offered functional and nonfunctional properties. Generally, the a...
详细信息
Cloud computing is a paradigm that focuses on sharing data and computing resources over a scalable network of nodes, so it is becoming a preferred environment for those applications with large scalability, dynamic col...
详细信息
We consider the problem of computing rearrangement distance of every permutation in the symmetric group Sn and present a simple algorithm for doing it. By analysing the rearrangement distance distribution computed for...
详细信息
Prior works on traffic classification mainly focus their attentions on dividing Internet traffic into different categories based on their application layer protocols (such as BitTorrent, eDonkey etc.). Making traffic ...
详细信息
Cloud computing markets arise as an efficient way to allocate resources for the execution of tasks and services within a set of geographically dispersed providers from different organisations. Client applications and ...
详细信息
Specialized frameworks for highly scalable data processing continue to gain prominence over traditional databases in many environments including the cloud. Perhaps the most well-known such framework is Google MapReduc...
详细信息
暂无评论