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.