Witness set

In combinatorics and computational learning theory, a witness set is a set of elements that distinguishes a given Boolean function from a given class of other Boolean functions. Let $C$ be a concept class over a domain $X$ (that is, a family of Boolean functions over $X$) and $c$ be a concept in $X$ (a single Boolean function). A subset $S$ of $X$ is a witness set for $c$ in $X$ if $S$ distinguishes $c$ from all the other functions in $C$, in the sense that no other function in $C$ has the same values on $S$.

For a concept class with $|C|$ concepts, there exists a concept that has a witness of size at most $\log _{2}|C|$; this bound is tight when $C$ consists of all Boolean functions over $X$. By a result of Bondy (1972) there exists a single witness set of size at most $|C|-1$ that is valid for all concepts in $C$; this bound is tight when $C$ consists of the indicator functions of the empty set and some singleton sets. One way to construct this set is to interpret the concepts as bitstrings, and the domain elements as positions in these bitstrings. Then the set of positions at which a trie of the bitstrings branches forms the desired witness set. This construction is central to the operation of the fusion tree data structure.

The minimum size of a witness set for $c$ is called the witness size or specification number and is denoted by $w_{C}(c)$. The value $\max\{w_{C}(c):c\in C\}$ is called the teaching dimension of $C$. It represents the number of examples of a concept that need to be presented by a teacher to a learner, in the worst case, to enable the learner to determine which concept is being presented.

Witness sets have also been called teaching sets, keys, specifying sets, or discriminants. The "witness set" terminology is from Kushilevitz et al. (1996), who trace the concept of witness sets to work by Cover (1965).