A time-space tradeoff for Boolean matrix multiplication

A time-space tradeoff is established in the branching program model for the problem of computing the product of two n× n matrices over a certain semiring. It is assumed that each element of each n×n input matrix is chosen independently to be 1 with probability n^-1/2 and to be 0 with probability 1-n^-1/2. Letting S and T denote expected space and time of a deterministic algorithm, the tradeoff is ST=Ω(n^3.5) for T<c₁n^2.5 and STΩ(n³) for T<c ₂n^2.5, where c₁, c₂ >0. The lower bounds are matched to within a logarithmic factor by upper bounds in the branching program model. Thus, the tradeoff possesses a sharp break at T=Θ( n^2.5). These expected case lower bounds are also the best known lower bounds for the worst case