Matching Algorithms and Reproductive Health: Part 3, A Stylized Virginity Pledge

It’s been three weeks and one IHME retreat since I wrote about matching algorithms and virginity pledges, and I think I now understand what’s going on in Patient Teenagers well enough to describe it. I’ll try to give a stylized example of how the minimum-weight perfect matching algorithm makes itself useful in reproductive health research.

I think it’s helpful to focus on a concrete research question about the virginity pledge and its effects on reproductive health. Here’s one: “does taking the pledge reduce the chances that an individual contracts trichomoniasis?” If the answer is yes, or if the answer is no, people can still argue about the value of the virginity pledge programs, but this seems like relevant information for decision making. Continue reading

2 Comments

Filed under combinatorial optimization, global health

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

4 Comments

Filed under combinatorial optimization, global health

Matching Algorithms and Reproductive Health: Part 1, Matchings Emerge from Social Science

Earlier this week, I was inspired by current events to launch a bold, crazy-sounding series about matching theory and its application to reproductive health.  This first installment is a quick social history of the development of matching theory, largely influenced by (and fact-checked against) Lex Scrijver’s encyclopediac Combinatorial Optimization: Polyhedra and Efficiency.  His paper “On the history of combinatorial optimization (till 1960)” contains similar information in an easy-to-download form.

On to the story:  how social science applications drove the  development of matching theory. Continue reading

6 Comments

Filed under combinatorial optimization, global health

Matching Algorithms and Reproductive Health: Part 0

One of the first things on Obama’s agenda after being sworn in as President last week was lifting the “global gag rule”, a Regan-era innovation that tied US aid to strict anti-choice regulations. Meanwhile, the TCS reading group at UW has been studying matching problems and Edmond’s blossom algorithm. Together, this has been the motivation I needed to launch a series of posts about applications of matchings in reproductive health metrics. Part 1 will have more about matchings.

1 Comment

Filed under combinatorial optimization, global health, videos

Busy Week

Friday, already! Happy fragile ceasefire in Gaza, happy wedding to Daniel and Anna, happy Martin Luther King Day, and happy presidential inauguration.
I pass by this mural of MLK almost every day, and I find it incredibly expressive. Maybe it has something to do with the Seattle weather. Today I thought he was looking tired, but hopeful.

Maximum 1-out from search results graph of politicians and corporationsIs there some research paper out there to distract me from thinking about politics too much?  How about a networks paper with applications to politics?  An Arxiv paper from the Physics and Society section was updated recently, and it caught my eye with some beautiful pictures. I’ll explain a little, or you can head straight for their figure on the interactions between presidential candidates and corporations. Continue reading

Comments Off on Busy Week

Filed under combinatorial optimization

Big News Day for Industrial TCS

Today there are headlines from almost all of the computer companies with TCS research labs. Some sounds good, some sounds bad. How this will affect research?

This seems like a fine time to mention the Post-Graduate Fellowship Program at IHME (app deadline March 1, 2009). It would be fun to have more TCS people up here.

1 Comment

Filed under TCS

ACO in Python: PADS for Minimum Spanning Trees

Sometimes, instead of working, I like to see what search terms are bringing readers to my blog. The most common search that healthyalgorithms has been most useless for is “minimum spanning tree python”. Today, I’ll remedy that.

But first, dear searchers, consider this: why are you searching for minimum spanning tree code in python? Is it because you have a programming assignment due soon? High-school CS class is voluntary. All college is optional, and many you are paying to attend. You know what I’m talking about? Perhaps the short motivational comic Time Management for Anarchists is better than some Python code.

Still want to know how to do it? Ok, but I warned you.

Continue reading

10 Comments

Filed under combinatorial optimization

On Gaza

I need a break from the health and algorithms posts for a second, to include something about the situation in Palestine. For the last two weeks, the hot war has been on my mind too much. I can’t keep writing about math movies and python tutorials without acknowledging it. Continue reading

7 Comments

Filed under general