DocumentCode
1219887
Title
A spectral lower bound technique for the size of decision trees and two-level AND/OR circuits
Author
Brandman, Yigal ; Orlitsky, Alon ; Hennessy, John
Author_Institution
Dept. of Electr. Eng., Stanford Univ., CA, USA
Volume
39
Issue
2
fYear
1990
fDate
2/1/1990 12:00:00 AM
Firstpage
282
Lastpage
287
Abstract
A universal lower-bound technique for the size and other implementation characteristics of an arbitrary Boolean function as a decision tree and as a two-level AND/OR circuit is derived. The technique is based on the power spectrum coefficients of the n dimensional Fourier transform of the function. The bounds vary from constant to exponential and are tight in many cases. Several examples are presented
Keywords
Boolean functions; Fourier transforms; logic circuits; trees (mathematics); arbitrary Boolean function; decision trees; n dimensional Fourier transform; power spectrum coefficients; spectral lower bound technique; two-level AND/OR circuits; Binary trees; Boolean functions; Circuit synthesis; Complexity theory; Decision trees; Fourier transforms; Input variables; Labeling; Logic circuits; Programmable logic arrays;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/12.45216
Filename
45216
Link To Document