## 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

## Repository Citation

Cai, Jin Yi; Green, F.; and Thierauf, T., "On the correlation of symmetric functions" (1996). *Computer Science*. 68.

https://commons.clarku.edu/faculty_computer_sciences/68

## APA Citation

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