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

Event Date: 

Wednesday, January 28, 2015 -
3:30pm to 5:00pm

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​ ​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.​