Satisfiability thresholds beyond k-XORSAT

Details Satisfiability thresholds beyond k-XORSAT Satisfiability thresholds beyond k-XORSAT

2011-12-09

arxiv.org/abs/1112.2118v1

Computer Science

Discrete Mathematics

Scientific paper

We consider random systems of equations x_1 + ... + x_k = a; 0 <= a <= 2 which are interpreted as equations modulo 3: We show for k >= 15 that the satisfiability threshold of such systems occurs where the 2-core has density 1: We show a similar result for random uniquely extendible constraints over 4 elements. Our results extend previous results of Dubois/Mandler for equations mod 2 and k = 3 and Connamacher/Molloy for uniquely extendible constraints over a domain of 4 elements with k = 3 arguments. Our proof technique is based on variance calculations, using a technique introduced Dubois/Mandler. However, several additional observations (of independent interest) are necessary.

Affiliated with

Also associated with

No associations

Rating

Satisfiability thresholds beyond k-XORSAT does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Satisfiability thresholds beyond k-XORSAT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Satisfiability thresholds beyond k-XORSAT will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-44078