List of Abbreviations

$A \times B$:

The Cartesian product of the sets $A$ and $B$.

AND:

The Boolean function that returns 1 if and only if every input bit is 1.

$D(f)$:

The decision tree complexity of the function $f$.

$D(f,x)$:

The minimum number of bits of input $x$ that determine the value of $f(x)$.

$D_{0}(f)$:

The nondeterministic decision tree complexity of verifying that $f(x) = 0$.

$D_{1}(f)$:

The nondeterministic decision tree complexity of verifying that $f(x) = 1$.

$N(f)$:

The nondeterministic decision tree complexity of the function $f$.

OR:

The Boolean function that returns 0 if and only if every input bit is 0.

PARITY:

The Boolean function that returns 1 if and only if the number of 1 bits in the input is even.

MAJORITY:

The Boolean function that returns 1 if and only if more than half of the input bits are 1.