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

}

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.

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 - http://www.scopus.com/inward/record.url?scp=85032793537&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85032793537&partnerID=8YFLogxK

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 -