Anti-concentration for polynomials of independent random variables

DOI10.4086/TOC.2016.V012A011zbMATH Open1392.68193arXiv1507.00829OpenAlexW2963188610MaRDI QIDQ2830871FDOQ2830871

Authors: Raghu Meka, Oanh Nguyen, Van Vu 

Publication date: 1 November 2016

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

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.

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

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

zbMATH Keywords

complexity theoryrandom polynomialsrandom graphsparityanti-concentration

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (28)

• Singularity of the \(k\)-core of a random graph
• Combinatorial anti-concentration inequalities, with applications
• Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
• On polynomial approximations to \(\mathrm{AC}^0\)
• Concentration for limited independence via inequalities for the elementary symmetric polynomials
• Geometric and o-minimal Littlewood-Offord problems
• Anti-concentration Inequalities for Polynomials
• Anticoncentration for subgraph statistics
• A robust version of Hegedűs's lemma, with applications
• Title not available (Why is that?)
• 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
• Concentration of multivariate polynomials and its applications
• Quasi-random multilinear polynomials
• 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
• On the concentration of multivariate polynomials with small expectation

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)