05694928

j

05694928 Bollig, Beate The optimal read-once branching program complexity for the direct storage access function. Inf. Process. Lett. 106, No. 4, 171-174 (2008). 2008 Elsevier Sciences Publishers (North-Holland), Amsterdam EN computational complexity lower bounds read-once branching programs

doi:10.1016/j.ipl.2007.11.009

Summary: Branching programs are computation models measuring the space of (Turing machine) computations. Read-once branching programs (BP1s) are the most general model where each graph-theoretical path is the computation path for some input. Exponential lower bounds on the size of read-once branching programs are known since a long time. Nevertheless, there are only few functions where the BP1 size is asymptotically known exactly. In this paper, the exact BP1 size of a fundamental function, the direct storage access function, is determined.