Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
Martin Sauerhoff, Philipp Woelfel · 2003
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.