Stasys Jukna
The graph of integer multiplication is hard for read-k times networks
Abstract
We prove that the graph of integer multiplication requires non-determi-
nistic read-k-times branching programs of exponential size. On the other
hand we show that one can add polynomially many integers by small deter-
ministic read-once-only branching programs. This shows that the reason
for the hardness of multiplication is not the necessity to add many in-
tegers (and hence, to get rid of the carry numbers) but the necessity to
add different subsets of these integers. [This is a revised version of
a manuscript distributed in April 1994]
Back
to my home page