## Event Date:

## Event Date Details:

Refreshments served at 3:15 PM

## Event Location:

- South Hall 5607F

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 the 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 emphasis 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.