Fetching the paper…

Reading the bibliography…

2015

Anti-concentration for polynomials of independent random variables

Meka, Raghu, Nguyen, Oanh, Vu, Van

Original
PDF
Post on X

Understand

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.

Anti-concentration for polynomials of independent random variables · Around

Built on

J. E. Littlewood and A. C. Offord
1943
Earlier work this paper cites.
P. Erdös
1945
Earlier work this paper cites.
A. Bonami
1970
Earlier work this paper cites.
L. Gross
1975
Earlier work this paper cites.
A. A. Razborov
1987
Earlier work this paper cites.
R. Smolensky
1987
Earlier work this paper cites.
R. Beigel, N. Reingold, and D. Spielman
1991
Earlier work this paper cites.
J. Aspnes, R. Beigel, M. Furst, and S. Rudich
1994
Earlier work this paper cites.
S. Janson, T. Luczak, and A. Rucinski
2000
Earlier work this paper cites.

Similar

J. H. Kim and V. H. Vu
2000
Cited alongside, same era.
B. Bollobás
2001
Cited alongside, same era.
A. Carbery and J. Wright
2001
Cited alongside, same era.
V. H. Vu
2002
Cited alongside, same era.
K. P. Costello, T. Tao, and V. Vu
2006
Cited alongside, same era.
I. Dinur, E. Friedgut, G. Kindler, and R. O’Donnell
2006
Cited alongside, same era.
E. Mossel, R. O’Donnell, and K. Oleszkiewicz
2010
Cited alongside, same era.
P. Austrin and J. Håstad

Then

H. H. Nguyen and V. H. Vu
2013
Later among the works it cites.
A. Razborov and E. Viola
2013
Later among the works it cites.
I. Diakonikolas, R. A. Servedio, L.-Y. Tan, and A. Wan
2014
Later among the works it cites.
J. Gilmer and S. Kopparty
Original
2014
Later among the works it cites.
P. Harsha, A. Klivans, and R. Meka
2014
Later among the works it cites.
D. M. Kane
2014
Later among the works it cites.
R. Williams
2014
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

2011

Cited alongside, same era.

K. P. Costello

2013

Cited alongside, same era.

R. R. Williams, V. Raman, and S. Suresh

2014

Later among the works it cites.

A. Abboud, R. Williams, and H. Yu

2015

Closest in time.