Sai Zeng, Angran Xiao, et al.
CAD Computer Aided Design
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.
Sai Zeng, Angran Xiao, et al.
CAD Computer Aided Design
Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008
Elena Cabrio, Philipp Cimiano, et al.
CLEF 2013
M.F. Cowlishaw
IBM Systems Journal