On Nečiporuk's theorem for branching programs

Noga Alon, Uri Zwick

Research output: Contribution to journalArticle

1 Scopus citations

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, V1,..., Vp is a partition of the set of variables of f{hook}, and rvi(f{hook}) is the number of different restrictions of f{hook} to Vi, then the size of every branching program which computes f{hook} is at least c = ∑ i=1 p logrvi(f{hook}) log log rvi(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 Σpi=1 t(rvi(f{hook})). We show that t(m) {all equal to} 1 2 log m/(log log m) and obtain explicit formulae for it.

Original languageEnglish (US)
Pages (from-to)331-342
Number of pages12
JournalTheoretical Computer Science
Volume64
Issue number3
DOIs
StatePublished - May 29 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On Nečiporuk's theorem for branching programs'. Together they form a unique fingerprint.

  • Cite this