"0"^^ . "0"^^ . "2"^^ . "17"^^ . . "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...."@en . "On Uncertainity versus Size in Branching Programs."@en . "RIV/67985807:_____/03:06020142" . "\u017D\u00E1k, Stanislav" . "1851;1867" . "RIV/67985807:_____/03:06020142!RIV/2004/GA0/A06004/N" . . "NL - Nizozemsko" . "[DB8C2BBBF144]" . "P(GA201/02/1456), P(GA201/98/0717), P(LN00A056), Z(AV0Z1030915)" . "On Uncertainity versus Size in Branching Programs." . . "0304-3975" . . . . "Theoretical Computer Science" . . . . . "On Uncertainity versus Size in Branching Programs."@en . "N/A" . "Jukna, S." . "619524" . . . . "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...." . "On Uncertainity versus Size in Branching Programs." . . . . "290" . "computational complexity; branching programs; decision trees; lower bounds; kraft inequality; entropy"@en . . . . . . . "1"^^ .