About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Information Processing Letters
Paper
A generalized model for understanding evasiveness
Abstract
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.