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 ƒ is a boolean function, V 1, …, V p is a partition of the set of variables of ƒ, and r vi (ƒ) is the number of different restrictions of ƒ to V i, then the size of every branching program which computes ƒ is at least c = ∑ i=1 p logrvi (ƒ) log log rvi (ƒ) 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 (ƒ)). We show that t(m) ≌ 1 2 log m/(log log m) and obtain explicit formulae for it.

Authors

• Noga Alon
• Uri Zwick

Keywords

No keywords are indexed for this paper.