Alok Aggarwal
IEEE TC
We consider the following problem that is related to the notion of evasiveness: Suppose an oracle contains a symmetric n × n matrix in which all entries are either 0 or 1. And suppose an algorithm can ask the oracle how many 1s are present in the submatrix formed by rows and columns indexed i1, i2,..., ik, for any 1 ≤ k ≤ n. Then, determine the minimum number of questions that must be asked by the algorithm in order to correctly output the entire matrix. We show that n2 4 log n questions are sometimes necessary and there exists an algorithm that correctly outputs the matrix by asking at most ( 2n2 log n)+o( n2 log n) questions. In the corresponding generalized decision tree model, we observe an upper bound on the number of questions asked for determining the connected components of an n-vertex graph; this upper bound is away from the straightforward lower bound by a log n factor. © 1989.
Alok Aggarwal
IEEE TC
S. Sattanathan, N.C. Narendra, et al.
CONTEXT 2005
David A. Selby
IBM J. Res. Dev
Beomseok Nam, Henrique Andrade, et al.
ACM/IEEE SC 2006