On the complexity of balanced Boolean functions

被引：5
|
作者：
Bernasconi, A [1 ]
机构：
[1] Tech Univ Munich, Inst Informat, D-80290 Munich, Germany
来源：
INFORMATION PROCESSING LETTERS | 1999年 / 70卷 / 04期
关键词：
balanced Boolean functions; strongly balanced Boolean functions; spectral characterization; harmonic analysis; computational complexity;
D O I：
10.1016/S0020-0190(99)00061-7
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
This paper introduces the notions of balanced and strongly balanced Boolean functions and examines the complexity of these functions using harmonic analysis on the hypercube. The results are applied to derive a lower bound related to AC(0) functions. (C) 1999 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：157 / 163
页数：7
相关论文
共 50 条
12345