{"id":667,"date":"2014-10-12T08:53:49","date_gmt":"2014-10-12T08:53:49","guid":{"rendered":"http:\/\/corner.mimuw.edu.pl\/?p=667"},"modified":"2014-10-12T08:53:49","modified_gmt":"2014-10-12T08:53:49","slug":"fpt-algorithms-and-syphilis","status":"publish","type":"post","link":"https:\/\/corner.mimuw.edu.pl\/?p=667","title":{"rendered":"FPT algorithms and syphilis"},"content":{"rendered":"

Long long time ago, ed<\/a> actually in 1943, US Army was recruiting a lot of soldiers. Each of the recruits had to be subject of some medical examination, and in particular they were tested against syphilis.\u00a0However, performing a single test was quite expensive. Then they came up with the following idea.\u00a0Pick blood samples from a group of soldiers,\u00a0mix them into a one big sample and perform the test on it.\u00a0If the test is positive, there is at least one infected soldier in the group.\u00a0But if it is negative, we know that all<\/em> of the soldiers in the group are healthy and we just saved a lot of tests. It becomes then an interesting problem to devise a method which uses this observation to find the exact group of infected recruits among all the candidates with some nice bound on the number of tests. Without any additional assumptions there is not much you can do (exercise: do you see why?) but in this case we expect that the number of infected candidates is quite small.\u00a0Then in fact you can save a lot and this story gave rise to the whole area called group testing<\/strong>.<\/p>\n

Group testing is a rich field and includes a variety of models.\u00a0Let us focus on the following one.\u00a0We are given a universe \"\"<\/span>