Efficient Oblivious Branching Programs for Threshold Functions

In his survey paper on branching programs, A. A. Razborov (1991) asked the following question: Does every rectifier-switching network computing the majority of n bits have size n/sup 1+/spl Omega/(1/)? We answer this question in the negative by constructing a simple oblivious branching program of size O(n log/sup 3/ n/log log n log log log n) for computing any threshold function. This improves the previously best known upper bound of O(n/sup 3/2/) due to O. B. Lupanov (1965). >

Authors

• Rakesh K. Sinha
• T. S. Jayram

Keywords

• Binary decision diagrams
• Input variables
• Computer science
• Computer networks
• Upper bound
• Labeling
• Boolean functions
• Length measurement
• Size measurement
• Circuits
• Threshold Function
• Branching Program
• Paper Surveys
• Proof Of Theorem
• Interval Length
• Output Node
• Source Node
• Node Level
• Symmetric Function
• Boolean Function
• Sink Node
• Program Size
• Input Bits