Dimension-free L2 maximal inequality for spherical means in the hypercube

Aram W. Harrow; Alexandra Kolla; Leonard J. Schulman

doi:10.4086/toc.2014.v010a003

Dimension-free L₂ maximal inequality for spherical means in the hypercube

Aram W. Harrow
, Alexandra Kolla
, Leonard J. Schulman

Siebel School of Computing and Data Science

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Pages (from-to)	55-75
Number of pages	21
Journal	Theory of Computing
Volume	10
DOIs	https://doi.org/10.4086/toc.2014.v010a003
State	Published - May 23 2014

Keywords

Boolean hypercube
Fourier analysis
Maximal inequality

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics

Online availability

10.4086/toc.2014.v010a003

Library availability

Discover UIUC Full Text

Cite this

@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 = "\textbackslash{}u2217Supported 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. \textbackslash{}u2020Was at Microsoft Research at the beginning and during part of this work. \textbackslash{}u2021Supported 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).",

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",

}

TY - JOUR

T1 - Dimension-free L2 maximal inequality for spherical means in the hypercube

AU - Harrow, Aram W.

AU - Kolla, Alexandra

AU - Schulman, Leonard J.

N1 - \u2217Supported 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. \u2020Was at Microsoft Research at the beginning and during part of this work. \u2021Supported 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).

PY - 2014/5/23

Y1 - 2014/5/23

N2 - 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.

AB - 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.

KW - Boolean hypercube

KW - Fourier analysis

KW - Maximal inequality

UR - https://www.scopus.com/pages/publications/85032793537

UR - https://www.scopus.com/pages/publications/85032793537#tab=citedBy

U2 - 10.4086/toc.2014.v010a003

DO - 10.4086/toc.2014.v010a003

M3 - Article

AN - SCOPUS:85032793537

SN - 1557-2862

VL - 10

SP - 55

EP - 75

JO - Theory of Computing

JF - Theory of Computing

ER -