@article{924cedfe4b0841b09c3591fe9f417253,

title = "Dimension-free L2 maximal inequality for spherical means in the hypercube",

abstract = "We establish the maximal inequality claimed in the title. In combinatorial terms this has the implication that for sufficiently small ε > 0, for all n, any marking of an e fraction of the vertices of the n-dimensional hypercube necessarily leaves a vertex x such that marked vertices are a minority of every sphere centered at x.",

keywords = "Boolean hypercube, Fourier analysis, Maximal inequality",

author = "Harrow, {Aram W.} and Alexandra Kolla and Schulman, {Leonard J.}",

note = "Funding Information: ∗Supported by NSF grants CCF-0916400 and CCF-1111382, DARPA QuEST contract FA9550-09-1-0044 and ARO contract W911NF-12-1-0486. Part of this work was done while working at the University of Washington. †Was at Microsoft Research at the beginning and during part of this work. ‡Supported by NSF grants CCF-0829909, CCF-1038578, CCF-1319745, and the NSF-supported Institute for Quantum Information and Matter. This work began during his visit in 2010 to the Theory Group at Microsoft Research, Redmond. 1This notation choice is because our paper is replete with operators acting on functions, and the associative composition pixA f is preferable to the cumbersome (A f )(x). Publisher Copyright: {\textcopyright} 2014 Prahladh Harsha, Adam Klivans, and Raghu Meka.",

year = "2014",

month = may,

day = "23",

doi = "10.4086/toc.2014.v010a003",

language = "English (US)",

volume = "10",

pages = "55--75",

journal = "Theory of Computing",

issn = "1557-2862",

publisher = "University of Chicago, Department of Computer Science",

}