Monthly Archives: February 2009

k-SAT and me

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 m/n<(1-\epsilon_k)2^k\ln(k)/k, where \epsilon_k \rightarrow 0. Previously no efficient algorithm was known to find solutions with non-vanishing probability beyond m/n=1.817.2^k/k.

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.

1 Comment

Filed under probability, TCS

Big opportunity for differential privacy

I wrote a few months ago about how research in differential privacy seems very applicable to global public health. There is a new report from the Institute of Medicine which calls for a new approach to protecting privacy in health research, Beyond the HIPAA privacy rule. The Lancet also has an editorial about the report, which is what made me think that I should pass this reference on to theoretical privacy researchers. Lancet’s summary: Continue reading

1 Comment

Filed under cryptography, science policy

Matching Algorithms and Reproductive Health: Part 2, Matching and Virginity Pledges

I might have been a little over-ambitious with this series. I wrote a little bit about the how matching theory emerged from the social sciences two weeks ago. But then I got really busy! And that was the part I actually knew something about ahead of time. The promised connection between matching algorithms and reproductive health (and more generally, how matching is being used in quasi-experiment design) is the part that I have to do some reading on before I can write knowledgeably about.

However, I have a plan: I’d like to “crowd-source” my library research. Continue reading


Filed under combinatorial optimization, global health