Friday, November 15, 2013 3:30 pm
-
4:30 pm
EST (GMT -05:00)
Solution geometry of a random k-XORSAT near the clustering threshold
Speaker: | Jane Gao |
---|---|
Affiliation: | University of Toronto |
Room: | Mathematics and Computer Building (MC) 5158 |
Abstract
Since
the
early
2000s
statistical
physicists
have
predicted,
using
a
non-rigorous
technique
called
the
"cavity
method",
that
the
solution
spaces
of
many
random
constraint
satisfiability
problems
(CSPs)
and
combinatorial
problems
have
a
clustering
phenomenon.
When
the
density
of
a
random
CSP
(the
number
of
constraints
divided
by
the
number
of
variables)
is
below
a
critical
value
c*,
all
solutions
form
a
single
well-connected
cluster:
one
can
"walk"
from
one
solution
to
any
other,
via
a
path
of
solutions,
by
changing
a
small
number
of
variables
at
a
time.
Above
c*,
solutions
are
partitioned
into
exponentially
many
well-connected,
well-separated
clusters:
the
Hamming
distance
between
any
two
solutions
in
different
clusters
is
Ω(n).
This
clustering
phenomenon
was
proved
to
be
true
for
several
random
CSPs
by
mathematicians;
it
gives
insight
into
the
existence
of
an
"algorithmic
barrier"
observed
in
many
CSPs.
In
this
talk,
I
will
depict
the
clustering
of
random
k-XORSAT
solutions,
in
particular
when
the
k-XORSAT
density
is
approaching
c*,
the
clustering
threshold:
we
investigate
how
clusters
are
born.
This
is
joint
work
with
Mike
Molloy.