Dr. Arnon Boneh (Tel Aviv University)

Title: Review of the classical group-testing problem and some new results

Abstract: The classical (I,N,q) group-testing (GT) problem is : In a (finite) population of N identical members each one either has a well defined property (="good") or does not have it (="bad"). There are N corresponding i.i.d. random variables each having probability q of being "good"(07 ?and? ?t?he best known algorithm for this problem is superexponential in N. Little is known about the optimal group-testing policy? although? there are several algorithms that provide fairly good sub-optimal solution for large N values and almost any q value?.? Some of these algorithms will be mentioned in the seminar. Special emphasi?s? will be given to a new "halving" algorithm which is simple to execute on one hand and is bounded away from the optimal solution by no more than 0,4% in the hard core of the problem.?