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 | x|. 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.