It is shown that the correlation on between parity and a polynomial , q a fixed odd number and of degree d arbitrary but fixed, is exponentially small in n as . An application to circuit complexity, from where the problem originates, is given.
On démontre que la corrélation sur de la fonction parité et un polynôme , q un entier impair donné et de degré d arbitraire mais fixé, est exponentiellement petite en n pour . On obient une application en théorie de complexité où la question trouve son origine.
Accepted:
Published online:
Jean Bourgain 1
@article{CRMATH_2005__340_9_627_0, author = {Jean Bourgain}, title = {Estimation of certain exponential sums arising in complexity theory}, journal = {Comptes Rendus. Math\'ematique}, pages = {627--631}, publisher = {Elsevier}, volume = {340}, number = {9}, year = {2005}, doi = {10.1016/j.crma.2005.03.008}, language = {en}, }
Jean Bourgain. Estimation of certain exponential sums arising in complexity theory. Comptes Rendus. Mathématique, Volume 340 (2005) no. 9, pp. 627-631. doi : 10.1016/j.crma.2005.03.008. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2005.03.008/
[1] Lower bounds for approximation by low degree polynomials over , Annual IEEE Conference on Computational Complexity (formerly Annual Conference on Structure in Complexity Theory), vol. 16, 2001
[2] On the correlation of symmetric functions, Math. Systems Theory, Volume 29 (1996) no. 3, pp. 245-258
[3] E. Dueñez, S. Miller, A. Roy, H. Straubing Incomplete quadratic exponential sums in several variables, preprint
[4] The correlation between parity and quadratic polynomials mod3, J. Comput. System Sci., Volume 69 (2004) no. 1, pp. 28-44
[5] Threshold circuits of bounded depth, J. Comput. System Sci., Volume 46 (1993) no. 2, pp. 129-154
Cited by Sources:
Comments - Policy