Speaker
Prof.
Scott Kirkpatrick
(School of Engineering and CS, HUJI)
Description
Statistical mechanics turned a corner with Mezard and
Zecchina's realization that its methods could be applied to
solve individual combinatorial problems as well as to
characterize the expected outcome of classes of problems.
But the methods, such as message passing or simulated
annealing, that stay closest to the physical analogies can
be extremely time-consuming and may not scale to large
engineering problems. Experience with heuristics, which
work simply and fast when they work and fail miserably when
they do not, suggest that problem complexity and method
success have a phase structure in problems with parameters
to vary. Recent attacks on decoding simple but powerful
LPDC codes have called attention to the possibility of using
linear programming and other powerful, scalable methods to
solve problems where a unique solution is expected (or
guaranteed). We have recently extended this approach with
random retrial heuristics. Applying these methods to the
hardest known Sudoku problems, we establish that when a
unique solution is known to exist, it can be found by
scalable methods with probability epsilon with a cost
multiple delta(epsilon), a new way of expressing the
resulting complexity of this phase.
