Spectral analysis of Boolean functions as a graph eigenvalue problem

被引：55
作者：
Bernasconi, A [1 ]
Codenotti, B
机构：
[1] Univ Munich, Inst Informat, D-80290 Munich, Germany
[2] CNR, Ist Matemat Computaz, I-56126 Pisa, Italy
来源：
IEEE TRANSACTIONS ON COMPUTERS | 1999年 / 48卷 / 03期
关键词：
Boolean function; graph eigenvalue; Cayley graph; Walsh spectrum; spectral coefficient;
D O I：
10.1109/12.755000
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
Several problems in digital logic can be conveniently approached in the spectral domain. In this paper we show that the Walsh spectrum of Boolean functions can be analyzed by looking at algebraic properties of a class of Cayley graphs associated with Boolean functions. We use this idea to investigate the Walsh spectrum of certain special functions.
引用
收藏
页码：345 / 351
页数：7
相关论文
共 22 条
[1]   SIMPLE CONSTRUCTIONS OF ALMOST K-WISE INDEPENDENT RANDOM-VARIABLES [J].
ALON, N ;
GOLDREICH, O ;
HASTAD, J ;
PERALTA, R .
RANDOM STRUCTURES & ALGORITHMS, 1992, 3 (03) :289-304
[2]  
[Anonymous], THESIS U CALIFORNIA
[3]   SOME PROPERTIES OF HADAMARD MATRICES GENERATED RECURSIVELY BY KRONECKER PRODUCTS [J].
ARAZI, B .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1979, 25 (01) :27-39
[4]  
Beigel R., 1993, Proceedings of the Eighth Annual Structure in Complexity Theory Conference (Cat. No.93CH3281-3), P82, DOI 10.1109/SCT.1993.336538
[5]  
Biggs N., 1968, ALGEBRAIC GRAPH THEO
[6]   A SPECTRAL LOWER BOUND TECHNIQUE FOR THE SIZE OF DECISION TREES AND 2-LEVEL AND OR CIRCUITS [J].
BRANDMAN, Y ;
ORLITSKY, A ;
HENNESSY, J .
IEEE TRANSACTIONS ON COMPUTERS, 1990, 39 (02) :282-287
[7]   HARMONIC-ANALYSIS OF POLYNOMIAL THRESHOLD FUNCTIONS [J].
BRUCK, J .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1990, 3 (02) :168-177
[8]   NEURAL NETWORKS, ERROR-CORRECTING CODES, AND POLYNOMIALS OVER THE BINARY N-CUBE [J].
BRUCK, J ;
BLAUM, M .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1989, 35 (05) :976-987
[9]  
CVETKOVIC DM, 1979, SPECTRA GRAPHS
[10]   GENERALIZED TRANSFORMS FOR MULTIPLE VALUED CIRCUITS AND THEIR FAULT-DETECTION [J].
DAMARLA, T .
IEEE TRANSACTIONS ON COMPUTERS, 1992, 41 (09) :1101-1109
123