A Caltech Library Service

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

Harrow, Aram W. and Kolla, Alexandra and Schulman, Leonard J. (2014) Dimension-free L_2 maximal inequality for spherical means in the hypercube. Theory of Computing, 10 (3). pp. 55-75. ISSN 1557-2862. doi:10.4086/toc.2014.v010a003.

[img] PDF - Published Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


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

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:© 2014 Aram W. Harrow, Alexandra Kolla, and Leonard J. Schulman. Licensed under a Creative Commons Attribution License (CC-BY). Received: February 21, 2013; Revised: November 12, 2013; Published: May 23, 2014. 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. 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. Thanks to Gil Kalai for a stimulating conversation which pointed us in the direction of maximal inequalities, to Konstantin Makarychev and Yury Makarychev for discussions about UGC on the hypercube, and to Yuval Peres and Terence Tao for helpful comments.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)FA9550-09-1-0044
Army Research Office (ARO)W911NF-12-1-0486
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Subject Keywords:maximal inequality, Fourier analysis, Boolean hypercube
Issue or Number:3
Classification Code:ACM Classification: G.3; AMS Classification: 42B25.
Record Number:CaltechAUTHORS:20130122-104220997
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:36505
Deposited By: Joy Painter
Deposited On:22 Jan 2013 22:27
Last Modified:09 Nov 2021 23:22

Repository Staff Only: item control page