Computer Science Colloquium
    Tuesday 01/03/2011
Time+Place : Tuesday 01/03/2011 14:30 room 337-8 Taub  Bld.
Speaker    : Leonid Barenboim
Affiliation: Dept. of Computer Science, Ben-Gurion University
Host       : Johann Makowsky
Title      : Deterministic Distributed Vertex Coloring in
             Polylogarithmic Time
Abstract   :
We consider the vertex coloring problem in the message-passing model of
distributed computing. In this model the network is represented by a graph G
of maximum degree Delta, in which the vertices host processors, and the
communication is performed over the edges of G.
Vertex coloring has numerous applications in communication networks, and
thus it has drawn a considerable attention of researchers in the last three
decades. The question of how many colors an efficient algorithm (that is, an
algorithm with polylogarithmic time) is required to use is a central
long-standing open question. Currently, efficient randomized algorithms that
employ Delta + 1 colors are known, but it is unknown whether this number of
colors can be achieved deterministically and efficiently.  In 1987, in a
seminal FOCS paper, Linial devised an efficient deterministic algorithm that
Delta^2 colors. In his paper Linial also asked whether it is possible to
employ a significantly smaller number of colors while still maintaining a
deterministic algorithm with polylogarithmic running time. Despite a very
intensive research in this direction in the last twenty years, this question
remained open prior to our work.
We present a deterministic algorithm that runs in polylogarithmic time, and
employs Delta^{1 + epsilon} colors, for an arbitrarily small positive
constant epsilon. Thus, our algorithm settles the long-standing question of
Linial. Moreover, our results give rise to significantly improved algorithm
for O(Delta)-coloring, and even for o(Delta)-coloring of very wide graph
families. These results are achieved using a novel graph-decomposition
technique. Specifically, the vertex set of the graph is partitioned into
subsets that satisfy certain helpful properties. In particular, the subsets
induce sparse subgraphs. This allows coloring the subgraphs with
sufficiently small number of colors while utilizing the parallelism of the
network to the full extent.
Our recent results show that this technique is very powerful, and is useful
for additional problems such as edge coloring.
Based on a joint work with Michael Elkin.
Received PODC2010 best paper award.
short bio:
I am currently a Ph.D. student in the department of Computer Science in
Ben-Gurion University under the supervision of Prof. Michael Elkin.  I
obtained my B.A in Computer Science from The Open University in 2005, and
M.Sc. in Computer Science from Ben-Gurion University in 2008 (Summa Cum
Laude). I completed my M.Sc. thesis in the field of Distributed
Symmetry-Breaking, under the supervision of prof. Elkin. The M.Sc. thesis
received the first prize in a national competition in 2010, conducted by the
Advanced Communication Center in Tel-Aviv University . My current research
interests include Distributed Graph Algorithms, Derandomization, and
Communication Networks, emphasizing on Coloring Problems.
Refreshments served from 14:15 on,
 	Lecture starts at 14:30
Visit our home page-   <>
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from: Hadas Heier   <>