Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Publications
Theses and dissertations
Ad Astra association
 
Press releases
News
Events
Funding opportunities
 
Login
Registration
 
>> Românã
 
   
 

Gabriel Istrate. Geometric Properties of Satisfying Assignments of random $epsilon$-1-in-k SAT. International Journal of Computer Mathematics, 86(12), pp. 2029-2039, 2009.

Abstract: We study the geometric structure of the set of solutions of random $epsilon$-1-in-k SAT problem. For $l geq 1$, two satisfying assignments $A$ and $B$ are $l$-connected if there exists a sequence of satisfying assignments connecting them by changing at most $l$ bits at a time.

We first identify a subregion of the satisfiable phase where the set of solutions provably forms one cluster. Next we provide a range of parameters $(c,epsilon)$ such that w.h.p. two assignments of a random $epsilon$-1-in-$k$ SAT instance with $n$ variables and $cn$ clauses are $O(log n)$-connected, conditional on being satisfying assignments. Also, for random instances of 1-in-$k$ SAT in the satisfiable phase we show that there exists $nu_{k}in (0,frac{1}{k-2}]$ such that w.h.p. no two satisfying assignments at distance at least $nu_{k}cdot n$ form a "hole". We believe that this is true for all $nu_{k}>0$, and in fact solutions of a random 1-in-$k$ SAT instance in the satisfiable phase form one cluster.


A preliminary version of this paper can be freely downloaded from

http://xxx.lanl.gov/abs/0811.3116

Keywords: $epsilon$-1-in-k SAT, overlaps, random graphs, phase transition.

URL: http://dx.doi.org/10.1080/00207160903193970

Posted by Gabriel Istrate

Back

   
© Ad Astra 2001-2013