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.
Healthy Algorithms 