On Uncertainty versus Size in Branching Programs

0404260 - UIVT-O 20010201 RIV DE eng C - Conference Paper (international conference)
Jukna, S. - Žák, Stanislav
On Uncertainty versus Size in Branching Programs.
Electronic Colloquium on Computational Complexity. Report No.39. Trier, 2001, s. -. ISSN 1433-8092
R&D Projects: GA ČR GA201/98/0717; GA MŠMT LN00A056
Keywords : computational complexity * branching programs * decision trees * lower bounds * Kraft inequality
Subject RIV: BA - General Mathematics
http://www.eccc.uni-trier.de/report/2001/039

Using an information-theoretic approach we prove a lower bound for so-called 'balanced' branching programs which for some classes of Boolean functions are more powerful than the most of previously considered restricted branching programs. The argument of the proof is based on an inequality for the average amount of uncertainty during the computation.
Permanent Link: http://hdl.handle.net/11104/0124523