On Uncertainty versus Size in Branching Programs

0404104 - UIVT-O 20020142 RIV NL eng J - Journal Article
Jukna, S. - Žák, Stanislav
On Uncertainty versus Size in Branching Programs.
Theoretical Computer Science. Roč. 290, - (2003), s. 1851-1867. ISSN 0304-3975. E-ISSN 1879-2294
R&D Projects: GA ČR GA201/98/0717; GA MŠMT LN00A056; GA ČR GA201/02/1456
Keywords : computational complexity * branching programs * decision trees * lower bounds * kraft inequality * entropy
Subject RIV: BA - General Mathematics
Impact factor: 0.764, year: 2003

We propose an information-theoretic approach to proving lower bounds on the size of branching programs. The argument is based on Kraft type inequalities for the average amount of uncertainty about (or entropy of) a given input during the various stages of computation. We introduce a large class of 'balanced' branching programs and, using the suggested approach, prove that some explicit Boolean functions cannot be computed by balanced programs of polynomial size....
Permanent Link: http://hdl.handle.net/11104/0124375