Anti-concentration for polynomials of independent random variables
From MaRDI portal
Publication:2830871
Abstract: We prove anti-concentration results for polynomials of independent random variables with arbitrary degree. Our results extend the classical Littlewood-Offord result for linear polynomials, and improve several earlier estimates. We discuss applications in two different areas. In complexity theory, we prove near optimal lower bounds for computing the Parity, addressing a challenge in complexity theory posed by Razborov and Viola, and also address a problem concerning OR functions. In random graph theory, we derive a general anti-concentration result on the number of copies of a fixed graph in a random graph.
Recommendations
- Combinatorial anti-concentration inequalities, with applications
- Concentration of multivariate polynomials and its applications
- Bilinear and quadratic variants on the Littlewood-Offord problem
- On the concentration of multivariate polynomials with small expectation
- An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
Cites work
- Bilinear and quadratic variants on the Littlewood-Offord problem
- Concentration of non‐Lipschitz functions and applications
- Faster all-pairs shortest paths via circuit complexity
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- On a lemma of Littlewood and Offord
- Small ball probability, inverse theorems, and applications
Cited in
(28)- On the concentration of multivariate polynomials with small expectation
- Combinatorial anti-concentration inequalities, with applications
- Singularity of the \(k\)-core of a random graph
- Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
- On polynomial approximations to \(\mathrm{AC}^0\)
- Geometric and o-minimal Littlewood-Offord problems
- Concentration for limited independence via inequalities for the elementary symmetric polynomials
- Anti-concentration Inequalities for Polynomials
- Anticoncentration for subgraph statistics
- scientific article; zbMATH DE number 7561310 (Why is no real title available?)
- A robust version of Hegedűs's lemma, with applications
- The least singular value of a random symmetric matrix
- The intransitive dice kernel: \( \frac{1\kern-2pt\mathrm{I}_{x\ge y}-1\kern-2pt\mathrm{I}_{x\le y}}{4} - \frac{3(x-y)(1+xy)}{8} \)
- Anti-concentration for subgraph counts in random graphs
- Local limit theorems for subgraph counts
- An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
- Almost sure behavior of the zeros of iterated derivatives of random polynomials
- Signature estimation and signal recovery using median of means
- A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
- On the permanent of a random symmetric matrix
- On the probabilistic degree of OR over the reals
- Anti-concentration of polynomials: dimension-free covariance bounds and decay of Fourier coefficients
- Quasi-random multilinear polynomials
- Concentration of multivariate polynomials and its applications
- Spectrum and pseudospectrum for quadratic polynomials in Ginibre matrices
- Polynomial threshold functions, hyperplane arrangements, and random tensors
- On the Probabilistic Degrees of Symmetric Boolean Functions
- Anticoncentration and Berry-Esseen bounds for random tensors
This page was built for publication: Anti-concentration for polynomials of independent random variables
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830871)
