Witness set

Key takeaways

Witness set belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Witness set to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Witness set from memory before moving on to harder problems.

Reference excerpt

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 {\displaystyle C} be a concept class over a domain X {\displaystyle X} (that is, a family of Boolean functions over X {\displaystyle X} ) and c {\displaystyle c} be a concept in X {\displaystyle X} (a single Boolean function). A subset S {\displaystyle S} of X {\displaystyle X} is a witness set for c {\displaystyle c} in X {\displaystyle X} if S {\displaystyle S} distinguishes c {\displaystyle c} from all the other functions in C {\displaystyle C} , in the sense that no other function in C {\displaystyle C} has the same values on S {\displaystyle S} . For a concept class with | C | {\displaystyle |C|} concepts, there exists a concept that has a witness of size at most log 2 ⁡ | C | {\displaystyle \log _{2}|C|} ; this bound is tight when C {\displaystyle C} consists of all Boolean functions over X {\displaystyle X} . By a result of Bondy (1972) there exists a single witness set of size at most | C | − 1 {\displaystyle |C|-1} that is valid for all concepts in C {\displaystyle C} ; this bound is tight when C {\displaystyle 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 {\displaystyle c} is called the witness size or specification number and is denoted by w C ( c ) {\displaystyle w_{C}(c)} . The value max { w C ( c ) : c ∈ C } {\displaystyle \max\{w_{C}(c):c\in C\}} is called the teaching dimension of C {\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. 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).

Worked examples

Example 1 — a first encounter with Witness set

Start with the simplest possible case. Write down what Witness set claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Witness set before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Witness set ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Witness set

In research: Witness set appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Witness set in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Witness set is common in secondary-school and first-year university syllabi. It links to neighbouring topics Computational learning theory, Machine learning stubs, Theoretical computer science stubs, so understanding it makes those chapters shorter.
In everyday life: Look for Witness set outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Witness set in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Witness set means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Witness set out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Witness set in simple terms?

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 {\displaystyle C} be a concept class over a domain X {\displaystyle X} (that is, a family of Boolean functions over…

Why does Witness set matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Witness set?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Witness set.