Anti-concentration for Polynomials of Independent Random Variables

by Raghu Meka, Oanh Nguyen, and Van Vu

Theory of Computing, Volume 12(11), pp. 1-17, 2016

Bibliography with links to cited articles

[1]   Amir Abboud, Richard Ryan Williams, and Huacheng Yu: More applications of the polynomial method to algorithm design. In Proc. 26th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’15), pp. 218–230. ACM Press, 2015. [doi:10.1137/1.9781611973730.17]

[2]   Noga Alon and Joel H. Spencer: The Probabilistic Method. John Wiley & Sons, 2004.

[3]   James Aspnes, Richard Beigel, Merrick L. Furst, and Steven Rudich: The expressive power of voting polynomials. Combinatorica, 14(2):135–148, 1994. Preliminary version in STOC’91. [doi:10.1007/BF01215346]

[4]   Richard Beigel, Nick Reingold, and Daniel A. Spielman: The perceptron strikes back. In Proc. 6th IEEE Conf. on Structure in Complexity Theory (SCTC’91), pp. 286–291. IEEE Comp. Soc. Press, 1991. [doi:10.1109/SCT.1991.160270]

[5]   Béla Bollobás: Random Graphs. Volume 73 of Cambridge Studies in Advanced Mathematics. Cambridge Univ. Press, 2001. [doi:10.1017/CBO9780511814068]

[6]   Anthony Carbery and James Wright: Distributional and Lq norm inequalities for polynomials over convex bodies in Rn. Math. Res. Lett., 8(3):233–248, 2001. [doi:10.4310/MRL.2001.v8.n3.a1]

[7]   Kevin P. Costello: Bilinear and quadratic variants on the Littlewood-Offord problem. Israel J. Math., 194(1):359–394, 2013. [doi:10.1007/s11856-012-0082-4, arXiv:0902.1538]

[8]   Kevin P. Costello, Terence Tao, and Van H. Vu: Random symmetric matrices are almost surely nonsingular. Duke Math. J., 135(2):395–413, 2006. [doi:10.1215/S0012-7094-06-13527-5, arXiv:math/0505156]

[9]   Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, and Li-Yang Tan: Average sensitivity and noise sensitivity of polynomial threshold functions. SIAM J. Comput., 43(1):231–253, 2014. Preliminary version in STOC’10. [doi:10.1137/110855223, arXiv:0909.5011]

[10]   Paul Erd˝o  s: On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc., 51(12):898–902, 1945. Available at Project Euclid.

[11]   Justin Gilmer and Swastik Kopparty: A local central limit theorem for triangles in a random graph. Random Structures Algorithms, 48(4):732–750, 2016. [doi:10.1002/rsa.20604, arXiv:1412.0257]

[12]   Craig Gotsman and Nathan Linial: Spectral properties of threshold functions. Combinatorica, 14(1):35–50, 1994. [doi:10.1007/BF01305949]

[13]   Svante Janson, Tomasz Łuczak, and Andrzej Ruciński: Random Graphs. Volume 45. Wiley-Interscience, 2000. [doi:10.1002/9781118032718]

[14]   Daniel M. Kane: The correct exponent for the Gotsman-Linial conjecture. Comput. Complexity, 23(2):151–175, 2014. Preliminary version in CCC’13. [doi:10.1007/s00037-014-0086-z, arXiv:1210.1283]

[15]   Jeong Han Kim and Van H. Vu: Concentration of multivariate polynomials and its applications. Combinatorica, 20(3):417–434, 2000. [doi:10.1007/s004930070014]

[16]   John Edensor Littlewood and Albert Cyril Offord: On the number of real roots of a random algebraic equation (III). Rec. Math. [Mat. Sbornik] N.S., 12(54)(3):277–286, 1943. MathNet.

[17]   Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz: Noise stability of functions with low influences: Invariance and optimality. Ann. of Math., 171(1):295–341, 2010. Preliminary version in FOCS’05. [doi:10.4007/annals.2010.171.295]

[18]   Fedor Nazarov, Mikhail Sodin, and Alexander Vol’berg: The geometric Kannan-Lovász-Simonovits lemma, dimension-free estimates for volumes of sublevel sets of polynomials, and distribution of zeros of random analytic functions. Algebra i Analiz, 14(2):214–234, 2002. Available at Math-Net.Ru. [arXiv:math/0108212]

[19]   Hoi H. Nguyen and Van H. Vu: Small ball probability, inverse theorems, and applications. In Erdʺo  s Centennial, volume 25 of Bolyai Soc. Math. Studies, pp. 409–463. Springer, 2013. [doi:10.1007/978-3-642-39286-3_16, arXiv:1301.0019]

[20]   Alexander A. Razborov: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Math. Notes, 41(4):333–338, 1987. [doi:10.1007/BF01137685]

[21]   Alexander A. Razborov and Emanuele Viola: Real advantage. ACM Trans. Comput. Theory, 5(4):17:1–17:8, 2013. Preliminary version in ECCC. [doi:10.1145/2540089]

[22]   Roman Smolensky: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proc. 19th STOC, pp. 77–82. ACM Press, 1987. [doi:10.1145/28395.28404]

[23]   Van H. Vu: Concentration of non-Lipschitz functions and applications. Random Structures Algorithms, 20(3):262–316, 2002. [doi:10.1002/rsa.10032]

[24]   Richard Ryan Williams: Faster all-pairs shortest paths via circuit complexity. In Proc. 46th STOC, pp. 664–673. ACM Press, 2014. [doi:10.1145/2591796.2591811, arXiv:1312.6680]

[25]   Richard Ryan Williams: The polynomial method in circuit complexity applied to algorithm design (invited talk). In Proc. 34th Internat. Conf. on Foundation of Software Tech. and Theoret. Comput. Sci. (FSTTCS’14), volume 29 of LIPIcs, pp. 47–60. Springer, 2014. [doi:10.4230/LIPIcs.FSTTCS.2014.47]