I’ve posted a new paper on random *k*-SAT on the arxiv. This is work I did towards the end of my post-doctoral stint at Microsoft Reseach with Danny Vilenchik and Uri Feige. It is an application of a cool technique that Danny and others came up with to study random instances *above* the satisfiability threshold that have been selected uniformly at random from *satisfiable instances* at that density. We use it to derive some bounds on the likely diameter of the set of satisfying solutions under this conditionally random distribution. Unfortunately, I don’t think that there are too many global health applications for random *k*-SAT with *k* large.

That’s too bad, because Amin Coja-Oghlan has also recently posted a paper about *k*-SAT on the arxiv, which sounds very promising. In A better algorithm for random *k*-SAT, Amin presents (from the abstract):

a polynomial time algorithm that finds a satisfying assignment of *F* with high probability for constraint densities , where . Previously no efficient algorithm was known to find solutions with non-vanishing probability beyond .

His algorithm is a combinatorial, local-search type algorithm. I’ll try to find time to read the paper even if I don’t come up with a compelling application of *k*-SAT to health metrics.

### Like this:

Like Loading...

*Related*

I think that this post is even more technical than my typical experts-only style! Sorry, mom!

For the non-expert-but-curious reader, I wrote a mini-survey on algorithms for random 3-SAT a little while back. It was fun to write, it could be fun to read.