Algorithms for Random k-SAT and Colouring Random Graphs
| Speaker: | Mike Molloy |
|---|---|
| Affiliation: | University of Toronto |
| Room: | Mathematics 3 (M3) 3103 |
Abstract:
Random
instances
of
k-SAT
have
long
been
recognized
as
being
very
challenging
to
solve
algorithmically.
Random
graphs
are
also
very
difficult
to
colour.
A
series
of
hypotheses
arising
from
statistical
physics
provides
much
insight
into
why
these
problems
are
so
challenging.
These
hypotheses
also
give
rise
to
some
algorithms
which,
in
practice,
perform
remarkably
well
on
random
instances
of
k-SAT
and
on
k-colouring
random
graphs
for
small
values
of
k.
The
most
notable
such
algorithm
is
survey
propagation,
a
variation
of
belief
propagation.
This
talk
will
provide
an
overview
of
these
algorithms,
including
intuition
as
to
why
they
seem
to
perform
well
and
hypotheses
regarding
their
performance
for
large
values
of
k.
We
will
also
discuss
what
has
been
proven
and
what
we
hope
to
prove.