## Abstract

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_{1},..., 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.

Original language | English (US) |
---|---|

Pages (from-to) | 331-342 |

Number of pages | 12 |

Journal | Theoretical Computer Science |

Volume | 64 |

Issue number | 3 |

DOIs | |

State | Published - May 29 1989 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- General Computer Science