Efficient Oblivious Branching Programs for Threshold and Mod Functions

✍ Scribed by Rakesh Kumar Sinha; Jayram S Thathachar

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 348 KB
• Volume: 55
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1997.1530

✦ Synopsis

In his survey paper on branching programs, Razborov asked the following question: Does every rectifier-switching network computing the majority of n bits have size n 1+0( 1) ? We answer this question in the negative by constructing a simple oblivious branching program of size O[n log 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 3Â2 ) due to Lupanov. We also construct oblivious branching programs of size o(n log 4 n) for computing general mod functions. All previously known constructions for computing general mod functions have size 0(n 3Â2 ).