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 employs
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 Computes 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