Ambainis [1] proved the following fundamental result:

- Every element of
*X*is related to at least*m*elements of*Y*by*P*. - Every element of
*Y*is related to at least*m'*elements of*X*by*P*. - For all
*i*, every element*x**X*is related to at most*l*elements*y**Y*such that*x*_{i}*y*_{i} - For all
*i*, every element*y**Y*is related to at most*l'*elements*x**X*such that*x*_{i}*y*_{i}

*Then
*

This theorem will be the primary means of proving lower bounds in this thesis. Its appeal is twofold; first, it leads to reasonably simple proofs, and second, it unifies many existing lower bounds into a single framework.