On the Power of Randomized Branching Programs
Title | On the Power of Randomized Branching Programs |
Publication Type | Technical Report |
Year of Publication | 1995 |
Authors | Ablayev, F., & Karpinski M. |
Other Numbers | 1004 |
Keywords | Lower 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))). |
URL | http://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 |