Computer Science

On the correlation of symmetric functions

Document Type

Article

Abstract

The correlation between two Boolean functions of n inputs is defined as the number of times the functions agree minus the number of times they disagree, all divided by 2n. In this paper we compute, in closed form, the correlation between any two symmetric Boolean functions. As a consequence of our main result, we get that every symmetric Boolean function having an odd period has an exponentially small correlation (in n) with the parity function. This improves a result of Smolensky [12] restricted to symmetric Boolean functions: the correlation between parity and any circuit consisting of a Modq gate over AND gates of small fan-in, where q is odd and the function computed by the sum of the AND gates is symmetric, is bounded by 2-Ω(n). In addition, we find that for a large class of symmetric functions the correlation with parity is identically zero for infinitely many ;i. We characterize exactly those symmetric Boolean functions having this property. © 1996 Springer-Verlag New York Inc.

Publication Title

Mathematical Systems Theory

Publication Date

1996

Volume

29

Issue

3

First Page

245

Last Page

258

ISSN

0025-5661

DOI

10.1007/BF01201278

Keywords

boolean function, symmetric function, parity function, random oracle, symmetric polynomial

APA Citation

Cai, J. Y., Green, F., & Thierauf, T. (1996). On the correlation of symmetric functions. Mathematical systems theory, 29(3), 245-258.

Link to Full Text

Share

COinS