Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
q-Overlaps in the Random Exact Cover Problem

Edit abstract data

Speaker: Gabriel Istrate
Author(s): Gabriel Istrate and Romeo Negrea
Slot: Wed, 16:30-16:50, Room 20 (col. 1)


We prove lower and upper bounds for the threshold of the following
problem: given $q\in (0,1)$ and $c>0$ what is the probability that a
random instance of the $k$-Exact Cover problem (Kalapala and Moore, preprint cs/050837, 2005) has two solutions of overlap
$qn\pm o(n)$ ?

This problem is motivated by the connection with the {\em replica
symmetry breaking} approach of Statistical Physics, in the context of
Phase Transitions in Combinatorial Optimization.

websites: Arnold Beckmann 2008-05-19 Valid HTML 4.01! Valid CSS!