On Nečiporuk's theorem for branching programs

Nečiporuk's theorem yields lower bounds on the size of branching programs computing specific boolean functions. Specifically, if f{hook} is a boolean function, V₁,..., V_p is a partition of the set of variables of f{hook}, and r_vi(f{hook}) is the number of different restrictions of f{hook} to V_i, then the size of every branching program which computes f{hook} is at least c = ∑ i=1 p logr_vi(f{hook}) log log r_vi(f{hook}) where c is some positive constant. In this note we determine the largest monotone non-decreasing function t(·) for which Nečiporuk's theorem remains true when the above sum is replaced by Σ^p_i=1 t(r_vi(f{hook})). We show that t(m) {all equal to} 1 2 log m/(log log m) and obtain explicit formulae for it.