Computability in Europe 2008
Logic and Theory of Algorithms 

Regular Talk:

Speaker:  Gabriel Istrate 
Author(s):  Gabriel Istrate and Romeo Negrea 
Slot:  Wed, 16:3016: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, 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  20080519 