On the complexity of balanced Boolean functions

被引:0
作者
Bernasconi, A [1 ]
机构
[1] Univ Pisa, Dipartimento Informat, Pisa, Italy
[2] CNR, Ist Matemat Computaz, I-56100 Pisa, Italy
来源
ALGORITHMS AND COMPLEXITY | 1997年 / 1203卷
关键词
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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.
引用
收藏
页码:253 / 263
页数:11
相关论文
共 9 条
[1]  
BERNASCONI A, 1996, UNPUB FOURIER ANAL B
[2]  
BERNASCONI A, 1993, TR99030 ICSI
[3]   PARITY, CIRCUITS, AND THE POLYNOMIAL-TIME HIERARCHY [J].
FURST, M ;
SAXE, JB ;
SIPSER, M .
MATHEMATICAL SYSTEMS THEORY, 1984, 17 (01) :13-27
[4]  
HASTAD J, 1986, THESIS CAMBRIDGE MAS
[5]   SPECTRAL METHOD OF BOOLEAN FUNCTION COMPLEXITY [J].
HURST, SL ;
MILLER, DM ;
MUZIO, JC .
ELECTRONICS LETTERS, 1982, 18 (13) :572-574
[6]  
LECHNER RJ, 1971, RECENT DEV SWITCHING, P122
[7]   CONSTANT DEPTH CIRCUITS, FOURIER-TRANSFORM, AND LEARNABILITY [J].
LINIAL, N ;
MANSOUR, Y ;
NISAN, N .
JOURNAL OF THE ACM, 1993, 40 (03) :607-620
[8]  
SIMON HU, 1983, LECT NOTES COMPUTER, V158
[9]  
Wegener I., 1987, WILEY TEUBNER SERIES