Solution geometry of a random k-XORSAT near the clustering threshold
| Speaker: | Jane Gao |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 5158 |
Abstract:
Since
early
2000s
statistical
physicists
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
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
O(log
n)
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).
These
clustering
phenomena
were
proved
to
be
true
for
several
random
CSPs
by
mathematicians.
In
this
talk,
I
will
depict
clustering
of
random
k-XORSAT
solutions,
in
particular
when
its
density
is
approaching
c*,
the
clustering
threshold:
we
investigate
how
clusters
are
born.
This is joint work with Mike Molloy.