Description
Abstract:
Group testing is a well-known search problem that consists in detecting
of $s$
defective members in a set of $t$ elements by carrying out tests on
properly chosen subsets. A test result is positive if there is at least
one defective element in a tested subset; otherwise, the result is
negative. Our goal is to find all defective elements by
using the minimal possible number of tests in the worst case.
Two types of algorithms are usually considered in group testing. {\it
Adaptive} algorithms can use results of previous tests to determine
which subset of samples to test at the next step. In {\it non-adaptive}
algorithms all tests are predetermined and can be carried out in parallel.
We consider multistage algorithms, which can be seen as a compromise
solution to the group testing problem. An algorithm is divided into $p$
stages. Tests from the $i$th stage may depend on outcomes of tests from
previous stages. The advantage of this approach is that we can greatly
reduce the total number of tests, but still perform a lot of them in
parallel. Our general goal is to construct a multistage search
procedure, having asymptotically the same number of tests as an adaptive
one. We solve that problem for $s=2, 3, 4$ by constructing 2-stage
algorithm for $s=2$ and 4-stage algorithms for $s=3, 4$.
Here is the zoom link (for the whole semester).
If a password is needed, it is 074746
https://zoom.us/j/93881000227?pwd=N1RKNFh6SkIzZmRqY3J3cWJPSm0yUT09