The Random K-SAT Problem: Solution Space Transitions and Random Walk Heuristics

Talk announcement:
HIIT Seminar Kumpula, Friday May 13 10:15, Exactum C222

SPEAKER:
Prof. Haijun Zhou
Chinese Academy of Sciences

TITLE:
The Random K-SAT Problem: Solution Space Transitions and Random Walk
Heuristics

ABSTRACT:
                        
The random K-satisfiability problem is an important problem for
studying typical-case complexity of NP-complete combinatorial
satisfaction.  We review recent efforts on the solution space fine
structures of the random K-SAT problem.  A heterogeneity transition is
predicted to occur in the solution space as the constraint density
alpha reaches a critical value alpha_{cm}. This transition marks the
emergency of exponentially many solution communities in the solution
space.  After the heterogeneity transition the solution space is still
ergodic until alpha reaches a larger threshold value alpha_d, at which
the solution communities disconnect from each other to become
different solution clusters (ergodicity-breaking).

The existence of solution communities in the solution space is
confirmed by numerical simulations of solution space random walking.
The performance of a simple random walk search algorithm, SEQSAT, is
also investigated.  This algorithm is very efficient for random 3-SAT,
but for random K>4-SAT instances, the search is blocked as alpha
approaches alpha_d from below.

BIO:

Haijun Zhou is a research professor at the Institute of Theoretical
Physics, Chinese Academy of Sciences.  He works in the area of
statistical physics and its interdisciplinary applications (spin
glasses, complex networks, and polymer physics). He was an invited
speaker at STATPHYS-24 (Austrialia, 2010), and now serves as an

editorial board member for the Journal of Statistical Mechanics.

Welcome!