Event Date Details:
Refreshments served at 3:15 PM
- 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"(0
7 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.