Comptes Rendus
Number Theory
Estimation of certain exponential sums arising in complexity theory
[Estimations de certaines sommes exponentielles en theorie de complexité]
Comptes Rendus. Mathématique, Volume 340 (2005) no. 9, pp. 627-631.

It is shown that the correlation on {0,1}n between parity and a polynomial p(x1,,xn)Z[X1,,Xn](modq), q a fixed odd number and p(X) of degree d arbitrary but fixed, is exponentially small in n as n. An application to circuit complexity, from where the problem originates, is given.

On démontre que la corrélation sur {0,1}n de la fonction parité et un polynôme p(x1,,xn)Z[X1,,Xn](modq), q un entier impair donné et p(X) de degré d arbitraire mais fixé, est exponentiellement petite en n pour n. On obient une application en théorie de complexité où la question trouve son origine.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2005.03.008

Jean Bourgain 1

1 Institute for Advanced Study, Princeton, NJ 08540, USA
@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},
}
TY  - JOUR
AU  - Jean Bourgain
TI  - Estimation of certain exponential sums arising in complexity theory
JO  - Comptes Rendus. Mathématique
PY  - 2005
SP  - 627
EP  - 631
VL  - 340
IS  - 9
PB  - Elsevier
DO  - 10.1016/j.crma.2005.03.008
LA  - en
ID  - CRMATH_2005__340_9_627_0
ER  - 
%0 Journal Article
%A Jean Bourgain
%T Estimation of certain exponential sums arising in complexity theory
%J Comptes Rendus. Mathématique
%D 2005
%P 627-631
%V 340
%N 9
%I Elsevier
%R 10.1016/j.crma.2005.03.008
%G en
%F CRMATH_2005__340_9_627_0
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] N. Alon; R. Beigel Lower bounds for approximation by low degree polynomials over Zm, Annual IEEE Conference on Computational Complexity (formerly Annual Conference on Structure in Complexity Theory), vol. 16, 2001

[2] J.-Y. Cai; F. Green; T. Thierauf 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] F. Green The correlation between parity and quadratic polynomials mod3, J. Comput. System Sci., Volume 69 (2004) no. 1, pp. 28-44

[5] A. Hajnal; W. Maass; P. Pudlák; M. Szegedy; G. Turán Threshold circuits of bounded depth, J. Comput. System Sci., Volume 46 (1993) no. 2, pp. 129-154

  • Jinjie Gao; Haibin Kan; Yuan Li; Jiahua Xu; Qichun Wang Monomial Boolean functions with large high-order nonlinearities, Information and Computation, Volume 297 (2024), p. 28 (Id/No 105152) | DOI:10.1016/j.ic.2024.105152 | Zbl:1536.94057
  • Rocco A. Servedio; Li-Yang Tan Improved pseudorandom generators from pseudorandom multi-switching lemmas, Theory of Computing, Volume 18 (2022), p. 46 (Id/No 4) | DOI:10.4086/toc.2022.v018a004 | Zbl:1547.68844
  • Lance Fortnow Worlds to Die Harder For Open Oracle Questions for the 21st Century, ACM SIGACT News, Volume 52 (2021) no. 3, p. 26 | DOI:10.1145/3494656.3494663
  • Lijie Chen; Xin Lyu Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR Lemma, Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC '21, virtual, Italy, June 21–25, 2021, New York, NY: Association for Computing Machinery (ACM), 2021, pp. 761-771 | DOI:10.1145/3406325.3451132 | Zbl:7765208
  • Eshan Chattopadhyay; Pooya Hatami; Kaave Hosseini; Shachar Lovett; David Zuckerman XOR lemmas for resilient functions against polynomials, Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC '20, Chicago, IL, USA, June 22–26, 2020, New York, NY: Association for Computing Machinery (ACM), 2020, pp. 234-246 | DOI:10.1145/3357713.3384242 | Zbl:7298244
  • Rocco A. Servedio; Li-Yang Tan Improved pseudorandom generators from pseudorandom multi-switching lemmas, Approximation, randomization, and combinatorial optimization. Algorithms and techniques, 22nd international conference, APPROX 2019, and 23rd international conference, RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20–22, 2019. Proceedings, Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019, p. 23 (Id/No 45) | DOI:10.4230/lipics.approx-random.2019.45 | Zbl:1547.68845
  • Shiteng Chen; Periklis A. Papakonstantinou Depth reduction for composites, SIAM Journal on Computing, Volume 48 (2019) no. 2, pp. 668-686 | DOI:10.1137/17m1129672 | Zbl:1421.68054
  • Richard Ryan Williams Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials, 33rd computational complexity, Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik, 2018, p. 24 (Id/No 6) | DOI:10.4230/lipics.ccc.2018.6 | Zbl:1441.68047
  • Frederic Green; Daniel Kreymer; Emanuele Viola Block-symmetric polynomials correlate with parity better than symmetric, Computational Complexity, Volume 26 (2017) no. 2, pp. 323-364 | DOI:10.1007/s00037-017-0153-3 | Zbl:1379.68153
  • Shiteng Chen; Periklis A. Papakonstantinou, 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (2016), p. 99 | DOI:10.1109/focs.2016.20
  • Shiteng Chen; Periklis A. Papakonstantinou Correlation lower bounds from correlation upper bounds, Information Processing Letters, Volume 116 (2016) no. 8, pp. 537-540 | DOI:10.1016/j.ipl.2016.03.012 | Zbl:1357.68079
  • Arkadev Chattopadhyay; Ricard Gavaldà; Kristoffer Arnsfelt Hansen; Denis Thérien Learning read-constant polynomials of constant degree modulo composites, Theory of Computing Systems, Volume 55 (2014) no. 2, pp. 404-420 | DOI:10.1007/s00224-013-9488-6 | Zbl:1319.68118
  • Andrej Bogdanov; Akinori Kawachi; Hidetoki Tanaka Hard Functions for Low-Degree Polynomials over Prime Fields, ACM Transactions on Computation Theory, Volume 5 (2013) no. 2, p. 1 | DOI:10.1145/2493246.2493248
  • Khodakhast Bibak Additive combinatorics: with a view towards computer science and cryptography – an exposition, Number theory and related fields. In memory of Alf van der Poorten. Based on the proceedings of the international number theory conference, Newcastle, Australia, March 12–16, 2012, New York, NY: Springer, 2013, pp. 99-128 | DOI:10.1007/978-1-4614-6642-0_4 | Zbl:1303.11022
  • Anna Gál; Vladimir Trifonov On the correlation between parity and modular polynomials, Theory of Computing Systems, Volume 50 (2012) no. 3, pp. 516-536 | DOI:10.1007/s00224-011-9332-9 | Zbl:1279.68098
  • Arkadev Chattopadhyay; Shachar Lovett, 2011 IEEE 26th Annual Conference on Computational Complexity (2011), p. 300 | DOI:10.1109/ccc.2011.25
  • Shachar Lovett; Srikanth Srinivasan Correlation bounds for poly-size AC0 circuits with n1o(1) symmetric gates, Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 14th international workshop, APPROX 2011, and 15th international workshop, RANDOM 2011, Princeton, NJ, USA, August 17–19, 2011. Proceedings, Berlin: Springer, 2011, pp. 640-651 | DOI:10.1007/978-3-642-22935-0_54 | Zbl:1343.68098
  • Arkadev Chattopadhyay; Ricard Gavaldà; Kristoffer Arnsfelt Hansen; Denis Thérien Learning read-constant polynomials of constant degree modulo composites, Computer science – theory and applications. 6th international computer science symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14–18, 2011. Proceedings, Berlin: Springer, 2011, pp. 29-42 | DOI:10.1007/978-3-642-20712-9_3 | Zbl:1330.68085
  • Andrej Bogdanov; Akinori Kawachi; Hidetoki Tanaka Hard Functions for Low-Degree Polynomials over Prime Fields, Mathematical Foundations of Computer Science 2011, Volume 6907 (2011), p. 120 | DOI:10.1007/978-3-642-22993-0_14
  • Kristoffer Arnsfelt Hansen; Vladimir V. Podolskii, 2010 IEEE 25th Annual Conference on Computational Complexity (2010), p. 270 | DOI:10.1109/ccc.2010.33
  • Frederic Green; Amitabha Roy Uniqueness of optimal mod 3 polynomials for parity, Journal of Number Theory, Volume 130 (2010) no. 4, pp. 961-975 | DOI:10.1016/j.jnt.2009.08.016 | Zbl:1200.11059
  • Ronen Shaltiel; Emanuele Viola Hardness Amplification Proofs Require Majority, SIAM Journal on Computing, Volume 39 (2010) no. 7, p. 3122 | DOI:10.1137/080735096
  • Arkadev Chattopadhyay; Avi Wigderson, 2009 50th Annual IEEE Symposium on Foundations of Computer Science (2009), p. 43 | DOI:10.1109/focs.2009.17
  • Emanuele Viola Guest Column, ACM SIGACT News, Volume 40 (2009) no. 1, p. 27 | DOI:10.1145/1515698.1515709
  • Ronen Shaltiel; Emanuele Viola, Proceedings of the fortieth annual ACM symposium on Theory of computing (2008), p. 589 | DOI:10.1145/1374376.1374461
  • Arkadev Chattopadhyay, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) (2007), p. 449 | DOI:10.1109/focs.2007.30
  • Emanuele Viola; Avi Wigderson, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07) (2007), p. 141 | DOI:10.1109/ccc.2007.15
  • Arkadev Chattopadhyay; Navin Goyal; Pavel Pudlak; Denis Therien, 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) (2006), p. 709 | DOI:10.1109/focs.2006.46
  • K.A. Hansen, 21st Annual IEEE Conference on Computational Complexity (CCC'06) (2006), p. 202 | DOI:10.1109/ccc.2006.29
  • Eduardo Dueñez; Steven J. Miller; Amitabha Roy; Howard Straubing Incomplete quadratic exponential sums in several variables, Journal of Number Theory, Volume 116 (2006) no. 1, pp. 168-199 | DOI:10.1016/j.jnt.2005.04.005 | Zbl:1162.11044
  • Anna Gál; Vladimir Trifonov On the Correlation Between Parity and Modular Polynomials, Mathematical Foundations of Computer Science 2006, Volume 4162 (2006), p. 387 | DOI:10.1007/11821069_34
  • Frederic Green; Amitabha Roy; Howard Straubing Bounds on an exponential sum arising in Boolean circuit complexity, Comptes Rendus. Mathématique. Académie des Sciences, Paris, Volume 341 (2005) no. 5, pp. 279-282 | DOI:10.1016/j.crma.2005.07.011 | Zbl:1113.11051

Cité par 32 documents. Sources : Crossref, zbMATH

Commentaires - Politique