Abstract. We prove exponential size lower bounds for nondeterministic and randomized read-k BPs as well as a time-space tradeoff lower bound for unrestricted, deterministic multi-way BPs computing the middle bit of integer multiplication. The lower bound for randomized read-k BPs is superpolynomial as long as the error probability is superpolynomially small. For polynomially small error, we have a polynomial upper bound on the size of approximating read-once BPs for this function. The lower bounds follow from a more general result for the graphs of universal hash classes that is applicable to the graphs of arithmetic functions such as integer multiplication, convolution, and finite field multiplication.
Last modified: Thu Apr 22 17:57:23 CEST 2004