Using relevance queries for identification of read-once functions

D. V. Chistikov

Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 183-217

Résumé

A Boolean function is called read-once if it can be expressed by a formula over $\{\land,\lor,\neg\}$ where no variable appears more than once. The problem of identifying an unknown read-once function $f$ depending on a known set of variables $x_1,\dots,x_n$ by making queries is considered. Algorithms are allowed to perform standard membership queries and queries of two special types, allowing to reveal the relevance of variables to projections of $f$. Two exact identification algorithms are developed: one makes $O(n^2)$ yes–no queries, and the other makes $O(n\log^2n)$ queries with logarithmically long answers. Information-theoretic lower bound on the number of bits transferred from oracles to identification algorithms in the worst case is $\Omega(n\log n)$.