syphilis
By anders pearson 02 Apr 2002
in crypto class today, prof. Rabin mentioned that in world war II, the government decided that they had to test all the soldiers for syphilis and a few other diseases. the problem was that blood tests were extremely expensive and they couldn’t afford to pay for blood tests for all N thousand soldiers knowing that probably less than 1% or so would actually be infected. they had to find the few soldiers who were infected but they didn’t want to spend all the money on expensive tests for soldiers who weren’t infected.
<p>the novel solution they came up with was to take groups of the blood samples, maybe 100 per group, mix them together and test the mixture. if it came back negative, they knew that all 100 of those soldiers were healthy; if it came back positive, they’d break it up into smaller and smaller groups until they’d isolated which soldier was infected. by picking the sizes of the groups intelligently, they could effectively test large numbers of soldiers quite cheaply.</p>
<p>Rabin then went on to explain an algorithm for doing mass verifications of digital signatures using a similar strategy.</p>
<p>i think the whole syphilis testing example is a wonderful example of how a good understanding of the problem and a little cleverness can really pay off. it’s probably also a good explanation/example for the layperson of what computer science is really about and why algorithms are important.</p>
<p>the actual algorithm used interests me as well. the trick to applying it would be to find a situation with something analogous to the mixing of the blood; you need a large scale boolean operation:(A or B or C or …) that will let you combine tests over large groups. then you also need the probabilities involved in the problem to be small enough that combining the tests will help you. eg, if 99% of the soldiers could be expected to be infected, the divide and conquer strategy would end up being more expensive than just testing each soldier individually.</p>