A VERY SIMPLE FUNCTION THAT REQUIRES EXPONENTIAL SIZE READ-ONCE BRANCHING PROGRAMS

Authors
BOLLIG B WEGENER I
Citation
B. Bollig et I. Wegener, A VERY SIMPLE FUNCTION THAT REQUIRES EXPONENTIAL SIZE READ-ONCE BRANCHING PROGRAMS, Information processing letters, 66(2), 1998, pp. 53-57
Citations number
23
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
66
Issue
2
Year of publication
1998
Pages
53 - 57
Database
ISI
SICI code
0020-0190(1998)66:2<53:AVSFTR>2.0.ZU;2-Y
Abstract
A Boolean function in n variables is presented that is computable in d epth 2 monotone AC(0) and has prime implicants of length 2 only but re quires 2(Ohm(root n)) size read-once branching programs. The function considered is defined using (1, 1)-disjoint Boolean sums and the solut ion of the famous problem of Zarankiewicz. (C) 1998 Elsevier Science B .V.