We consider the problem of building a binary decision tree, to locate an object within a set by way of the least number of membership queries. This problem is equivalent to the “20 questions game” of information theory and is closely related to lossless so ...
In conventional group testing, the goal is to detect a small subset of defecting items D in a large population N by grouping \textit{arbitrary} subset of N into different pools. The result of each group test $\mathcal{T} ...
We study the problem of navigating/searching through a database of objects with potentially different popularities using a membership oracle. The membership oracle, given a subset of objects A, and a target object t, determines whether A contains t ...
Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2011
We give two new randomized algorithms for tight renaming, both of which work against an adaptive adversary. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of n processes with step complexity $ ...
Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2011
