Abstract
Thecorrelation between two Boolean functions ofn 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 twosymmetric Boolean functions. As a consequence of our main result, we get that every symmetric Boolean function having an odd period has anexponentially small correlation (inn) 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 Mod q gate over AND gates of small fan-in, whereq 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 isidentically zero for infinitely manyn. We characterize exactly those symmetric Boolean functions having this property.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. Ajtai, Σ 11 -formulae on finite structures,Annals of Pure and Applied Logic 24 (1983), 1–48.
L. Babai, A random oracle separates PSPACE from the polynomial-time hierarchy,Information Processing Letters 26 (1987), 51–53.
D. M. Barrington, R. Beigel, and S. Rudich, Representing Boolean functions as polynomials modulo composite numbers,Proceedings of the 24th ACM Symposium on Theory of Computing, 1992, pp. 455–461.
J.-Y. Cai, With probability one, a random oracle separates PSPACE from the polynomial-time hierarchyJournal of Computer and System Science 38 (1989), 68–85.
M. Furst, J. B. Saxe, and M. Sipser, Parity, circuits, and the polynomial-time hierarchy,Mathematical Systems Theory 17 (1984), 13–27.
F. Green, An oracle separating ⊕P from PPPH,Information Processing Letters 37 (1991), 149–153.
J. Håstad,Computational Limitations of Small-Depth Circuits, MIT Press, Cambridge, MA, 1987.
K. Ireland and M. Rosen,A Classical Introduction to Modern Number Theory, 2nd edn., Springer-Verlag, New York, 1990.
N. Katz, Sommes Exponentielles,Astérisque 79 (1980).
A. A. Razborov, Lower bounds on the size of bounded depth networks over a complete basis with logical addition,Matematicheskie Zametki 41 (1987), 598–607. English translation:Mathematical Notes of the Academy of Sciences of the USSR 41 (1987), 333–338.
W. M. Schmidt,Equations over Finite Fields: An Elementary Approach, Lecture Notes in Mathematics, vol. 536, Springer-Verlag, New York, 1976.
R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity,Proceedings of the 19thAnnual ACM Symposium on Theory of Computing, 1987, pp. 77–82.
C. Smorynski,Logical Number Theory, Vol. I, Springer-Verlag, New York, 1991.
A. C. Yao, Separating the polynomial-time hierarchy by oracles,Proceedings of the 26thAnnual IEEE Symposium on Foundations of Computer Science, 1985, pp. 1–10.
S. Zabek, Sur la périodicité modulom des suites de nombres (k n),Annals Universitatis Mariae Curie-Sklodowska Sectio A 10 (1956), 37–47.
Author information
Authors and Affiliations
Additional information
This research was supported in part by NSF Grant CCR-9057486. Jin-Yi Cai was supported in part by an Alfred T. Sloan Fellowship in computer science. The work of F. Green was done in part while visiting Princeton University, while the work of T. Thierauf was done in part while visiting Princeton University and the University of Rochester. The third author was supported in part by DFG Postdoctoral Stipend Th 472/1-1 and by NSF Grant CCR-8957604.
Rights and permissions
About this article
Cite this article
Cai, J.Y., Green, F. & Thierauf, T. On the correlation of symmetric functions. Math. Systems Theory 29, 245–258 (1996). https://doi.org/10.1007/BF01201278
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01201278