On Nečiporuk's theorem for branching programs (Q1121017)

In 1966 Nečiporuk derived the following lower bound for the minimal size BP(f) of a branching program which computes the Boolean function f: \(BP(f)=\Omega (\sum^{p}_{i=1}(\log r_ i(f))/(\log \log r_ i(f)))\) where \(V_ 1,...,V_ p\) is a partition of the set of variables of f and \(r_ i(f)\) denotes the number of different restrictions of f to \(V_ i.\) Alon and Zwick determine the largest monotone nondecreasing function t for which Nečiporuk's theorem remains true if the above sum is replaced by \(\sum^{p}_{i=1}t(r_ i(f))\). They show t(m)\(\sim (1/2)(\log m)/(\log \log m)\) and derive an explicit formulae for t.