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

Creators: Harrow, Aram W.; Kolla, Alexandra; Schulman, Leonard J.

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.

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.

Attached Files

Published - v010a003.pdf

Files

v010a003.pdf

Files (288.7 kB)

Name	Size	Download all
v010a003.pdf md5:7754ece030083c3665debd3bb708518a	288.7 kB	Preview Download

Additional details

	All versions	This version
Views	0	0
Downloads	0	0
Data volume	0 Bytes	0 Bytes