  A notable result from analysis of Boolean functions is the Basic Invariance
Principle (BIP), a quantitative nonlinear generalization of the Central Limit
Theorem for multilinear polynomials. We present a generalization of the BIP for
bivariate multilinear polynomials, i.e., polynomials over two n-length
sequences of random variables. This bivariate invariance principle arises from
an iterative application of the BIP to bound the error in replacing each of the
two input sequences. In order to prove this invariance principle, we first
derive a version of the BIP for random multilinear polynomials, i.e.,
polynomials whose coefficients are random variables. As a benchmark, we also
state a naive bivariate invariance principle which treats the two input
sequences as one and directly applies the BIP. Neither principle is universally
stronger than the other, but we do show that for a notable class of bivariate
functions, which we term separable functions, our subtler principle is
exponentially tighter than the naive benchmark.
