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 ${\displaystyle C}$ be a concept class over a domain ${\displaystyle X}$ (that is, a family of Boolean functions over ${\displaystyle X}$) and ${\displaystyle c}$ be a concept in ${\displaystyle X}$ (a single Boolean function). A subset ${\displaystyle S}$ of ${\displaystyle X}$ is a witness set for ${\displaystyle c}$ in ${\displaystyle X}$ if ${\displaystyle S}$ distinguishes ${\displaystyle c}$ from all the other functions in ${\displaystyle C}$, in the sense that no other function in ${\displaystyle C}$ has the same values on ${\displaystyle S}$.^[1]

For a concept class with ${\displaystyle |C|}$ concepts, there exists a concept that has a witness of size at most ${\displaystyle \log _{2}|C|}$; this bound is tight when ${\displaystyle C}$ consists of all Boolean functions over ${\displaystyle X}$.^[1] By a result of Bondy (1972) there exists a single witness set of size at most ${\displaystyle |C|-1}$ that is valid for all concepts in ${\displaystyle C}$; this bound is tight when ${\displaystyle C}$ consists of the indicator functions of the empty set and some singleton sets.^[1][2] 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.^[3]

The minimum size of a witness set for ${\displaystyle c}$ is called the witness size or specification number and is denoted by ${\displaystyle w_{C}(c)}$. The value ${\displaystyle \max\{w_{C}(c):c\in C\}}$ is called the teaching dimension of ${\displaystyle 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.^[4]

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