Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-110 | 24th October 2007 00:00

The Optimal Read-Once Branching Program Complexity for the Direct Storage Access Function

RSS-Feed




TR07-110
Authors: Beate Bollig
Publication: 29th October 2007 10:41
Downloads: 3600
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint