Title: Using Lasserre Hierarchy for Graph Coloring
| Speaker: | Julian Romero Barbosa |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
In
this
talk,
I
will
go
over
a
technique
introduced
by
Arora
and
Ge
for
coloring
3-colorable
graphs
having
low
threshold
rank
(i.e.,
graphs
with
few
eigenvalues
below
certain
negative
constant).
For
regular
graphs
on
n
vertices,
such
techniques
allow
us
to
find
(with
constant
probability)
an
independent
set
of
size
at
least
n/12
in
time
nO(D)
where
D
is
the
threshold
rank
of
the
graph.
If
in
addition,
the
graph
is
vertex-transitive,
this
implies
that
a
coloring
with
O(log
n)
colors
can
be
found
in
nO(d)
time.
A
crucial
ingredient
in
the
proof
is
a
neat
interpretation
of
the
solutions
of
the
Lasserre
Hierarchy
relaxation
as
distributions
over
colorings
of
the
graph.
Informally
speaking,
when
these
distributions
have
a
small
”variance”,
it
is
possible
to
recover
a
large
partial
coloring
of
the
graph,
thus
obtaining
a
large
independent
set.
This
is
the
case
for
graphs
with
low
threshold
rank.