Invited Speaker

Eyal Kushilevitz

Communication Complexity: From Two-party to Multiparty

Abstract

We consider the multiparty communication complexity model, where k players holding inputs x_1,... ,x_k communicate to compute the value f(x_1, .... ,x_k) of a function f known to all of them. Yao's classic two-party communication complexity model [3] is the special case k=2 (see also [2]). In the first part of the talk, we survey some basic results regarding the two-party model, emphasizing methods for proving lower-bounds. In the second part of the talk, we consider the case where there are at least three parties (k >= 3). The main lower bound technique for the communication complexity of such multiparty problems is that of partition arguments: partition the k players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem. We discuss the power of partition arguments for both deterministic and randomized protocols. (This part is based on a joint work with Jan Draisma and Enav Weinreb [1])

References

Prize 2010 for Innovation In DC

Jean-Claude Bermond

The Prize for Innovation In Distributed Computing is awarded by the Colloquium on Structural Information and Communication Complexity (SIROCCO). It is established to recognize individuals whose research contributions on the relationships between information and efficiency in decentralized computing have expanded the collective investigative horizon by formulating new problems, or identifying new research areas, that were at the time of their introduction unorthodox and outside the mainstream. The prize recognizes originality, innovation, and creativity. The recipient of the Prize is chosen among the nominated persons for the current year.

The Award Committee has selected Jean-Claude BERMOND as the recipient of this year's Prize for Innovation In Distributed Computing.

The prize is given in recognition of Bermond for his contribution to the study of the impact of structure of networks on the efficiency of parallel or distributed algorithms, as illustrated by several papers, including some that appeared in the proceedings of past SIROCCO meetings. These papers tackled a wide variety of problems including routing, broadcasting, gossip protocols, traffic grooming, fault tolerant network design, monopolies, and other topics, illustrated, in particular, by the following papers:

The paper "De Bruijn and Kautz networks: a competitor for the hypercube?" is a pioneering paper investigating the design of networks for parallel and distributed computers. This paper promoted the de Bruijn graph as a suitable network for efficient communication and management. Under the reign of the hypercubes and meshes tightly- coupled multi-processors, this paper was definitively unorthodox. It was visionary too, as the de Bruijn graph was later found particularly rich in applications, especially in the framework of overlay network design for P2P systems.

The paper "Cycle Covering" appeared in SIROCCO 1995 deals with protection by cycles in wavelength division multiplexing networks, a subject originated in the operation of telecommunication networks. The most important contribution is the use of design theory to tackle the questions at hand, using tools developed in the paper "Shortest coverings of graphs with cycles" (J. Comb. Theory, Ser. B). This clever perspective can be used to show that other combinatorial problems in communication networks are special cases of traffic grooming, like, for instance, the problem of the minimization of the number of ADMs for all-to-all traffic in unidirectional rings. This allowed the tools and techniques developed in this article to be extended to answer all-to-all traffic grooming in unidirectional rings with larger grooming factors. Most of the techniques used in the literature to prove lower bounds in related problems were established in this article.

Last but not least, Bermond was among the first to identify the importance of designing efficient protocols for structured communication problems, including one-to-all broadcasting, multicasting, and all-to-all broadcasting (a.k.a. gossiping). His many contributions in this field enabled deep understanding of the capabilities and limitations of networks in terms of efficiently propagating informations and data.

By his results and ideas, Jean-Claude Bermond has enriched Distributed Computing considerably, in demonstrating the importance of network structural properties on the performances of distributed algorithms, with applications ranging from fundamental aspects of distributed computing to network design.

The prize will be officially delivered at the the Business meeting of the 17th edition of the Colloquium on Structural Information and Communication Complexity (SIROCCO), Sirince, Turkey, June 7-11, 2010.

2010 Award Committee