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. https://resolver.caltech.edu/CaltechAUTHORS:20130122-104220997
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Published Version
Creative Commons Attribution. 288kB |
Use this Persistent URL to link to this item: https://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: |
| ||||||||||||||||||
| ORCID: |
| ||||||||||||||||||
| 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 | ||||||||||||||||||
| Funders: |
| ||||||||||||||||||
| Subject Keywords: | maximal inequality, Fourier analysis, Boolean hypercube | ||||||||||||||||||
| Issue or Number: | 3 | ||||||||||||||||||
| Classification Code: | ACM Classification: G.3; AMS Classification: 42B25. | ||||||||||||||||||
| DOI: | 10.4086/toc.2014.v010a003 | ||||||||||||||||||
| Record Number: | CaltechAUTHORS:20130122-104220997 | ||||||||||||||||||
| Persistent URL: | https://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: | 09 Nov 2021 23:22 |
Repository Staff Only: item control page
