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
Yun Mao, Hani Jamjoom, et al.
CoNEXT 2006
Michael D. Moffitt
ICCAD 2009
Joel L. Wolf, Mark S. Squillante, et al.
IEEE Transactions on Knowledge and Data Engineering