On the Power of Randomized Branching Programs

TitleOn the Power of Randomized Branching Programs
Publication TypeTechnical Report
Year of Publication1995
AuthorsAblayev, F., & Karpinski M.
Other Numbers1004
KeywordsLower Bounds, Randomized Branching Programs, Read-k Branching Programs, Two-way Communication Game
Abstract

We define the notion of a randomized branching program in the natural way similar to the definition of a randomized circuit. We exhibit an explicit function f_n for which we prove that:1) f_n can be computed by polynomial size randomized read-once ordered branching program with a small one-sided error;2) f_n cannot be computed in polynomial size by deterministic read-once branching programs;3) f_n cannot be computed in polynomial size by deterministic read-k-times ordered branching program for k=o(n/log n) (the required deterministic size is (Omega(n/k))).

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1995/tr-95-064.pdf
Bibliographic Notes

ICSI Technical Report TR-95-064

Abbreviated Authors

F. Ablayev and M. Karpinski

ICSI Publication Type

Technical Report