Computability in Europe 2008
Logic and Theory of Algorithms

## 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)

### Abstract

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,
arxiv.org 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