[Estimations de certaines sommes exponentielles en theorie de complexité]
It is shown that the correlation on
On démontre que la corrélation sur
Accepté le :
Publié le :
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
[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
- 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
- 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
- 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
- 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
- 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
- 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
- Depth reduction for composites, SIAM Journal on Computing, Volume 48 (2019) no. 2, pp. 668-686 | DOI:10.1137/17m1129672 | Zbl:1421.68054
- 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
- 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
- , 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (2016), p. 99 | DOI:10.1109/focs.2016.20
- 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
- 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
- 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
- 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
- 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
- , 2011 IEEE 26th Annual Conference on Computational Complexity (2011), p. 300 | DOI:10.1109/ccc.2011.25
- Correlation bounds for poly-size
circuits with 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 - 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
- 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
- , 2010 IEEE 25th Annual Conference on Computational Complexity (2010), p. 270 | DOI:10.1109/ccc.2010.33
- 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
- Hardness Amplification Proofs Require Majority, SIAM Journal on Computing, Volume 39 (2010) no. 7, p. 3122 | DOI:10.1137/080735096
- , 2009 50th Annual IEEE Symposium on Foundations of Computer Science (2009), p. 43 | DOI:10.1109/focs.2009.17
- Guest Column, ACM SIGACT News, Volume 40 (2009) no. 1, p. 27 | DOI:10.1145/1515698.1515709
- , Proceedings of the fortieth annual ACM symposium on Theory of computing (2008), p. 589 | DOI:10.1145/1374376.1374461
- , 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) (2007), p. 449 | DOI:10.1109/focs.2007.30
- , Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07) (2007), p. 141 | DOI:10.1109/ccc.2007.15
- , 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) (2006), p. 709 | DOI:10.1109/focs.2006.46
- , 21st Annual IEEE Conference on Computational Complexity (CCC'06) (2006), p. 202 | DOI:10.1109/ccc.2006.29
- 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
- On the Correlation Between Parity and Modular Polynomials, Mathematical Foundations of Computer Science 2006, Volume 4162 (2006), p. 387 | DOI:10.1007/11821069_34
- 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