CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:20130122-104220997

[img] PDF - Published Version
Creative Commons Attribution.

281Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20130122-104220997

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 ε 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
https://doi.org/10.4086/toc.2014.v010a003DOIArticle
https://arxiv.org/abs/1209.4148arXivDiscussion Paper
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, IQIM
Funders:
Funding AgencyGrant Number
NSFCCF-0916400
NSFCCF-1111382
Defense Advanced Research Projects Agency (DARPA)FA9550-09-1-0044
Army Research Office (ARO)W911NF-12-1-0486
NSFCCF-0829909
NSFCCF-1038578
NSFCCF-1319745
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Subject Keywords:maximal inequality, Fourier analysis, Boolean hypercube
Classification Code:ACM Classification: G.3; AMS Classification: 42B25.
Record Number:CaltechAUTHORS:20130122-104220997
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20130122-104220997
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:36505
Collection:CaltechAUTHORS
Deposited By: Joy Painter
Deposited On:22 Jan 2013 22:27
Last Modified:16 Nov 2018 22:03

Repository Staff Only: item control page