Let A and B be matrices the entries of which are affine combinations of the variables over GF(2). Suppose that, for each i,, and the term is an element product matrix . What is the maximum value that m can have as a function of n? This question arises from a recent technique for improving the communication complexity of zero-knowledge proofs. The obvious upper bound of is improved to . Tighter bounds are obtained for smaller values of n. The bounds for , and are tight.
