On Uncertainty versus Size in Branching Programs

Number of the records: 1

1.

SYSNO ASEP	0404104
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	On Uncertainty versus Size in Branching Programs
Author(s)	Jukna, S. (DE) Žák, Stanislav (UIVT-O)_{SAI, RID}
Source Title	Theoretical Computer Science. - : Elsevier - ISSN 0304-3975 Roč. 290, - (2003), s. 1851-1867
Number of pages	17 s.
Language	eng - English
Country	NL - Netherlands
Keywords	computational complexity ; branching programs ; decision trees ; lower bounds ; kraft inequality ; entropy
Subject RIV	BA - General Mathematics
R&D Projects	GA201/98/0717 GA ČR - Czech Science Foundation (CSF)
	LN00A056 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
	GA201/02/1456 GA ČR - Czech Science Foundation (CSF)
UT WOS	000179441900027
DOI	10.1016/S0304-3975(02)00323-7
Annotation	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....
Workplace	Institute of Computer Science
Contact	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Year of Publishing	2003

Number of the records: 1