Computer Science

Block-symmetric polynomials correlate with parity better than symmetric

Document Type

Article

Abstract

We show that degree-d block-symmetric polynomials in n variables modulo any odd p correlate with parity exponentially better than degree-d symmetric polynomials, if n≥ cd2log d and d∈ [ 0.995 · pt- 1 , pt) for some t≥ 1 and some c> 0 that depends only on p. For these infinitely many degrees, our result solves an open problem raised by a number of researchers including Alon & Beigel (IEEE conference on computational complexity (CCC), pp 184–187, 2001). The only previous case for which this was known was d = 2 and p = 3 (Green in J Comput Syst Sci 69(1):28–44, 2004). The result is obtained through the development of a theory we call spectral analysis of symmetric correlation, which originated in works of Cai et al. (Math Syst Theory 29(3):245–258, 1996) and Green (Theory Comput Syst 32(4):453–466, 1999). In particular, our result follows from a detailed analysis of the correlation of symmetric polynomials, which is determined up to an exponentially small relative error when d= pt- 1.

Publication Title

Computational Complexity

Publication Date

2017

Volume

26

Issue

2

First Page

323

Last Page

364

ISSN

1016-3328

DOI

10.1007/s00037-017-0153-3

Keywords

68Q99, correlation, degree, mod m, parity, polynomial, symmetric

APA Citation

?

Link to Full Text

Share

COinS