Anti-concentration for polynomials of independent random variables

DOI10.4086/toc.2016.v012a011zbMath1392.68193arXiv1507.00829OpenAlexW2963188610MaRDI QIDQ2830871

Raghu Meka, Van H. Vu, Oanh Nguyen

Publication date: 1 November 2016

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.00829

zbMATH Keywords

random graphscomplexity theoryrandom polynomialsparityanti-concentration

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (21)

Quasi-random multilinear polynomials ⋮ Anti-concentration of polynomials: dimension-free covariance bounds and decay of Fourier coefficients ⋮ Singularity of the \(k\)-core of a random graph ⋮ On the probabilistic degree of OR over the reals ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics ⋮ Anticoncentration and Berry-Esseen bounds for random tensors ⋮ The least singular value of a random symmetric matrix ⋮ Local limit theorems for subgraph counts ⋮ Signature estimation and signal recovery using median of means ⋮ Anti-concentration Inequalities for Polynomials ⋮ On polynomial approximations to AC ⋮ Unnamed Item ⋮ An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs ⋮ Anti-concentration for subgraph counts in random graphs ⋮ Combinatorial anti-concentration inequalities, with applications ⋮ On the Probabilistic Degrees of Symmetric Boolean Functions ⋮ Anticoncentration for subgraph statistics ⋮ On the permanent of a random symmetric matrix ⋮ Spectrum and pseudospectrum for quadratic polynomials in Ginibre matrices ⋮ Geometric and o-minimal Littlewood-Offord problems ⋮ Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors

Cites Work

• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Bilinear and quadratic variants on the Littlewood-Offord problem
• Concentration of non‐Lipschitz functions and applications
• Faster all-pairs shortest paths via circuit complexity
• Small Ball Probability, Inverse Theorems, and Applications
• On a lemma of Littlewood and Offord

This page was built for publication: Anti-concentration for polynomials of independent random variables