Change search
ReferencesLink to record
Permanent link

Direct link
Balanced K-satisfiability and biased random K-satisfiability on trees
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2013 (English)In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, Vol. 87, no 4, 042130- p.Article in journal (Refereed) Published
Abstract [en]

We study and solve some variations of the random K-satisfiability (K-SAT) problem-balanced K-SAT and biased random K-SAT-on a regular tree, using techniques we have developed earlier. In both these problems as well as variations of these that we have looked at, we find that the transition from the satisfiable to the unsatisfiable regime obtained on the Bethe lattice matches the exact threshold for the same model on a random graph for K = 2 and is very close to the numerical value obtained for K = 3. For higher K, it deviates from the numerical estimates of the solvability threshold on random graphs but is very close to the dynamical one-step-replica-symmetry-breaking threshold as obtained from the first nontrivial fixed point of the survey propagation algorithm.

Place, publisher, year, edition, pages
2013. Vol. 87, no 4, 042130- p.
National Category
Physical Sciences
URN: urn:nbn:se:kth:diva-124055DOI: 10.1103/PhysRevE.87.042130ISI: 000319003900004ScopusID: 2-s2.0-84877731686OAI: diva2:633253

QC 20130626

Available from: 2013-06-26 Created: 2013-06-25 Last updated: 2013-06-26Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Krishnamurthy, Supriya
By organisation
Theoretical Computer Science, TCS
In the same journal
Physical Review E. Statistical, Nonlinear, and Soft Matter Physics
Physical Sciences

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 25 hits
ReferencesLink to record
Permanent link

Direct link