Useful Definitions

We will prove lower bounds for functions from $\{0,1\}^{N}$ to $\{0,1\}$, we will call such functions $N$-bit Boolean functions, or just Boolean functions. In our proofs we will frequently need the notion of the Hamming weight of a bit string: this is the number of 1's in the string. We denote the Hamming weight of a bit string $x$ as $\vert x\vert$. We also will frequently refer to all inputs which differ from a particular input in only one bit, we will call inputs which differ in a single bit Hamming neighbors.